  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.
