We study the iteration complexity of decentralized learning of approximate correlated equilibria in incomplete information games. On the negative side, we prove that in $\mathit{ extensive}$-$\mathit{ form}$ $\mathit{ games}$, assuming $\mathsf{ PPAD} \not\subset \mathsf{ TIME}(n^{ \mathsf{ polylog}(n)})$, any polynomial-time learning algorithms must take at least $2^{ \log_2^{ 1-o(1)}(|\mathcal{ I}|)}$ iterations to converge to the set of $\epsilon$-approximate correlated equilibrium, where $|\mathcal{ I}|$ is the number of nodes in the game and $\epsilon > 0$ is an absolute constant. This nearly matches, up to the $o(1)$ term, the algorithms of [PR'24, DDFG'24] for learning $\epsilon$-approximate correlated equilibrium, and resolves an open question of Anagnostides, Kalavasis, Sandholm, and Zampetakis [AKSZ'24]. Our lower bound holds even for the easier solution concept of $\epsilon$-approximate $\mathit{ coarse}$ correlated equilibrium On the positive side, we give uncoupled dynamics that reach $\epsilon$-approximate correlated equilibria of a $\mathit{ Bayesian}$ $\mathit{ game}$ in polylogarithmic iterations, without any dependence of the number of types. This demonstrates a separation between Bayesian games and extensive-form games.
Categories: cs.GT cs.AI cs.DS cs.LG