The complexity of approximate (coarse) correlated equilibrium for incomplete information games

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ᵖᵒˡʸˡᵒᵍ⁽ⁿ⁾), any polynomial-time learning algorithms must take at least 2^log₂¹⁻ᵒ⁽¹⁾(|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.