  Imperfect information games (IIG) are games in which each player only
partially observes the current game state. We study how to learn
$\epsilon$-optimal strategies in a zero-sum IIG through self-play with
trajectory feedback. We give a problem-independent lower bound
$\widetilde{\mathcal{O}}(H(A_{\mathcal{X}}+B_{\mathcal{Y}})/\epsilon^2)$ on the
required number of realizations to learn these strategies with high
probability, where $H$ is the length of the game, $A_{\mathcal{X}}$ and
$B_{\mathcal{Y}}$ are the total number of actions for the two players. We also
propose two Follow the Regularized leader (FTRL) algorithms for this setting:
Balanced FTRL which matches this lower bound, but requires the knowledge of the
information set structure beforehand to define the regularization; and Adaptive
FTRL which needs
$\widetilde{\mathcal{O}}(H^2(A_{\mathcal{X}}+B_{\mathcal{Y}})/\epsilon^2)$
realizations without this requirement by progressively adapting the
regularization to the observations.
