Efficient $Φ$-Regret Minimization in Extensive-Form Games via Online Mirror Descent
A conceptually appealing approach for learning Extensive-Form Games (EFGs) is
to convert them to Normal-Form Games (NFGs). This approach enables us to
directly translate state-of-the-art techniques and analyses in NFGs to learning
EFGs, but typically suffers from computational intractability due to the
exponential blow-up of the game size introduced by the conversion. In this
paper, we address this problem in natural and important setups for the
\emph{$\Phi$-Hedge} algorithm -- A generic algorithm capable of learning a
large class of equilibria for NFGs. We show that $\Phi$-Hedge can be directly
used to learn Nash Equilibria (zero-sum settings), Normal-Form Coarse
Correlated Equilibria (NFCCE), and Extensive-Form Correlated Equilibria (EFCE)
in EFGs. We prove that, in those settings, the \emph{$\Phi$-Hedge} algorithms
are equivalent to standard Online Mirror Descent (OMD) algorithms for EFGs with
suitable dilated regularizers, and run in polynomial time. This new connection
further allows us to design and analyze a new class of OMD algorithms based on
modifying its log-partition function. In particular, we design an improved
algorithm with balancing techniques that achieves a sharp
$\widetilde{\mathcal{O}}(\sqrt{XAT})$ EFCE-regret under bandit-feedback in an
EFG with $X$ information sets, $A$ actions, and $T$ episodes. To our best
knowledge, this is the first such rate and matches the information-theoretic
lower bound.