# Adapting to game trees in zero-sum imperfect information games

**Authors:** Côme Fiegel, Pierre Ménard, Tadashi Kozuno, Rémi Munos, Vianney Perchet, Michal Valko  
**arXiv:** [2212.12567](https://arxiv.org/abs/2212.12567)  
**Date:** 2022-12-23  
**Summary page:** https://www.summarizepaper.com/en/paper/2212.12567v2/

## Key points

- Learning $\epsilon$-optimal strategies in zero-sum imperfect information games (IIGs) through self-play with trajectory feedback
- Challenge of determining optimal strategies in IIGs due to partial observation of game state
- Problem-independent lower bound on required number of realizations: $\widetilde{\mathcal{O}}(H(A_{\mathcal{X}}+B_{\mathcal{Y}})/\epsilon^2)$
- Proposed Follow the Regularized Leader (FTRL) algorithms: Balanced FTRL and Adaptive FTRL
- Balanced FTRL matches lower bound but requires prior knowledge of information set structure for regularization
- Adaptive FTRL progressively adapts regularization without requiring prior knowledge, but needs $\widetilde{\mathcal{O}}(H^2(A_{\mathcal{X}}+B_{\mathcal{Y}})/\epsilon^2)$ realizations
- Table summarizing sample complexity of different algorithms for episodic, finite, two-player, zero-sum IIGs in terms of $H$, $A_{\mathcal{X}}$, $B_{\mathcal{Y}}$, and $\epsilon$
- Some algorithms mentioned in Table 1 do not require prior knowledge of information set structure
- Contributes to understanding learning $\epsilon$-optimal strategies in zero-sum IIGs and provides algorithms with trade-offs in sample complexity and prior knowledge requirements.

## Summary

The paper titled "Adapting to game trees in zero-sum imperfect information games" discusses the problem of learning $\epsilon$-optimal strategies in zero-sum imperfect information games (IIGs) through self-play with trajectory feedback. In IIGs, each player only partially observes the current game state, which makes it challenging to determine the optimal strategies. The authors provide a problem-independent lower bound on the required number of realizations to learn these strategies with high probability. The lower bound is given as $\widetilde{\mathcal{O}}(H(A_{\mathcal{X}}+B_{\mathcal{Y}})/\epsilon^2)$, where $H$ represents the length of the game and $A_{\mathcal{X}}$ and $B_{\mathcal{Y}}$ are the total number of actions for the two players. To address this problem, the authors propose two Follow the Regularized Leader (FTRL) algorithms: Balanced FTRL and Adaptive FTRL. The Balanced FTRL algorithm matches the lower bound but requires prior knowledge of the information set structure to define regularization. On the other hand, Adaptive FTRL progressively adapts regularization to observations without requiring prior knowledge of the information set structure. However, Adaptive FTRL needs $\widetilde{\mathcal{O}}(H^2(A_{\mathcal{X}}+B_{\mathcal{Y}})/\epsilon^2)$ realizations. The paper also provides a table summarizing different algorithms' sample complexity for episodic, finite, two-player, zero-sum IIGs. The sample complexities are expressed in terms of $H$, $A_{\mathcal{X}}$, $B_{\mathcal{Y}}$, and $\epsilon$. It is worth noting that some algorithms mentioned in Table 1 do not require prior knowledge of the information set structure. Overall, this paper contributes to our understanding of learning $\epsilon$-optimal strategies in zero-sum IIGs and provides algorithms with different trade-offs in terms of sample complexity and prior knowledge requirements.