The Complexity of Markov Equilibrium in Stochastic Games
summary
Proves that computing stationary Markov CCE is PPAD-hard even for two-player turn-based stochastic games with a constant discount factor and constant approximation (via a reduction from the ε-generalized-circuit using small-state gadgets), and shows a matching membership result; complements hardness by giving a decentralized algorithm (needs shared randomness) that learns a nonstationary Markov CCE with polynomial time/sample complexity using bandit no-regret learners, policy-cover stages and RMAX-style bonuses (current sample rate ~ε^-3).
AI-written summary · about