Equilibrium in Multi-Agent Reinforcement Learning
2026-08-24 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors explore why common solution ideas for complicated games with random events are hard to compute and can't usually be learned by simple methods. They propose a new way to think about equilibrium in these games, called Markov Bayes coarse correlated equilibrium (MBCCE), where players have no incentive to change their action after seeing the current state but before their recommended move. The authors connect this concept to known ideas in simpler games and create a way to measure learning progress called adaptive Markov coarse regret (AMCR). They prove that two common learning algorithms will get closer and closer to MBCCE over time and provide precise rates for how fast this happens.
stochastic gamesMarkov perfect equilibriumMarkov coarse correlated equilibriumMarkov Bayes coarse correlated equilibriumregret minimizationreinforcement learningactor-critic algorithmpolicy-gradient methodstochastic approximationequilibrium concepts
Authors
Maurizio D'Andrea, Bar Light
Abstract
Standard solution concepts for stochastic games, such as Markov perfect equilibrium and Markov coarse correlated equilibrium, are computationally difficult, and thus, standard decentralized reinforcement-learning algorithms should not generally be expected to converge to them. In this paper, we study the equilibrium generated by such algorithms. In particular, we introduce a new solution concept for stochastic games, Markov Bayes coarse correlated equilibrium (MBCCE), defined as a distribution over states and stationary policy profiles such that, after observing the state but before observing her recommended action, no player can gain by choosing a different current action, with the sampled policy profile governing play thereafter. We discuss the parallels between MBCCE and coarse correlated equilibrium (CCE) in finite normal-form games and show that MBCCE retains several of its key properties. We then introduce a corresponding regret notion, adaptive Markov coarse regret (AMCR), and show that vanishing AMCR implies that every accumulation point of the empirical distribution of realized states and policy profiles is an MBCCE. Crucially, we show that achieving AMCR reduces to two standard learning tasks: minimizing external regret at each state and accurately evaluating the current joint policy. We then prove that under mild conditions these properties hold for two natural RL algorithmic designs: a decentralized asynchronous actor--critic algorithm through a new two-timescale stochastic-approximation analysis, and a standard episodic multi-agent projected policy-gradient method. Hence, both algorithms generate approximate MBCCEs, and we establish explicit finite-time convergence rates for both.