Abstract
We study the iteration complexity of decentralized learning of approximate correlated equilibria in incomplete information games. On the negative side, we prove that in extensive-form games, assuming PPAD ⊂ TIME(n^polylog(n)), any polynomial-time learning algorithms must take at least 2^log₂^1-o(1)(|I|) iterations to converge to the set of ε-approximate correlated equilibrium, where |I| is the number of nodes in the game and ε > 0 is an absolute constant. This nearly matches, up to the o(1) term, the algorithms of [PR'24, DDFG'24] for learning ε-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 ε-approximate coarse correlated equilibrium On the positive side, we give uncoupled dynamics that reach ε-approximate correlated equilibria of a Bayesian game in polylogarithmic iterations, without any dependence of the number of types. This demonstrates a separation between Bayesian games and extensive-form games.