The Complexity of Computing Coarse Correlated Equilibria in Markov Games with a Single Controller

Gabriele Farina, Andreas Kontogiannis, Ioannis Panageas +1

We study the complexity of computing stationary Markov coarse correlated equilibria (CCE) in discounted single-controller stochastic (Markov) games [PR81, FV97], a fundamental subc…