Regret Minimization and Convergence to Equilibria in General-sum Markov Games

Liad Erez, Tal Lancewicki, Uri Sherman, Tomer Koren, Yishay Mansour

Introduction

In the field of Multiagent Reinforcement Learning (MARL), the challenge of achieving stable, decentralized learning in complex environments has remained a significant hurdle. While single-agent reinforcement learning has seen immense success, multi-agent settings introduce non-stationarity: as one agent learns and adapts, the environment effectively changes for all other agents. This paper addresses this complexity by providing the first decentralized algorithm for general-sum Markov games that guarantees sublinear swap regret for all agents, leading to a natural convergence toward a correlated equilibrium.

The Challenge of General-Sum Markov Games

In general-sum Markov games, agents’ interests are neither perfectly aligned nor perfectly opposed. Finding a Nash Equilibrium in these settings is computationally intractable (PPAD-complete), and traditional "no-regret" learning against adversarial opponents was previously thought to be statistically impossible in Markovian environments.

However, this paper shifts the focus. Instead of attempting to minimize regret against an arbitrary adversary, it asks whether a group of rational agents, all utilizing the same decentralized learning procedure, can collectively achieve low regret. The goal is to design an algorithm that allows agents to reach a correlated equilibrium—a solution concept more general than Nash Equilibrium—without requiring a central controller or explicit communication between agents.

The Decentralized Learning Framework

The authors propose a decentralized policy optimization algorithm characterized by three primary technical pillars:

  1. Optimistic Online Mirror Descent (OOMD): Unlike standard gradient-based methods, OOMD incorporates the loss from the previous time step as a "hint" for the current step. This optimism helps the learner anticipate the movement of the other agents, effectively mitigating the "moving target" problem inherent in MARL.
  2. Log-Barrier Regularization: The algorithm employs a log-barrier regularizer rather than the more common entropic regularization. This choice is critical for stability; it ensures that the "path length" of policy updates remains bounded, preventing the drastic policy shifts that often lead to instability in multi-agent systems.
  3. Swap Regret Meta-Algorithm: To achieve the stronger guarantee of swap regret, the authors wrap their base learner in a framework that considers whether an agent would have been better off consistently swapping one action for another throughout the game. Minimizing swap regret is a sufficient condition for convergence to a correlated equilibrium.

Theoretical Insights: Stability and Non-Stationarity

A key insight of the paper is the reduction of the Markov game from an individual agent's perspective to a non-stationary Markov Decision Process (MDP). In this view, policy optimization becomes a form of weighted regret minimization where the weights—representing state occupancy measures—are unknown and constantly shifting as other agents update their strategies.

The authors demonstrate that OOMD with log-barrier regularization is uniquely suited for this task. They provide a lower bound argument showing that the popular Follow-the-Regularized-Leader (FTRL) algorithm fails in this setting because it cannot adapt quickly enough to the non-stationary weights. In contrast, the stability provided by the log-barrier ensures that the agents' policies change slowly enough for the system to remain within a regime where convergence is possible.

Key Results and Convergence Rates

The paper establishes several groundbreaking theoretical bounds:

  • Sublinear Swap Regret: In general Markov games, the algorithm achieves a swap regret of $\tilde{O}(T^{1/2+\alpha})$, where $T$ is the number of episodes. This ensures that the average regret vanishes over time.
  • Convergence to Correlated Equilibrium: As a direct consequence of the swap regret bound, the joint empirical distribution of the agents' policies converges to a correlated equilibrium at a rate of $\tilde{O}(T^{-1/2+\alpha})$.
  • Independent Transitions: In simplified settings where agents influence each other’s rewards but not the underlying state transitions, the algorithm achieves a significantly faster logarithmic regret of $O(\log T)$.

Limitations and Future Directions

While the paper represents a major theoretical advancement, the authors note several areas for further refinement. A significant technical correction (detailed in the paper's addendum) clarifies that the regret bound includes an execution-dependent term ($D^i_{max}$, the maximal Bregman divergence). In the worst-case scenario, without specific assumptions on the game structure, this term could potentially lead to a linear (vacuous) bound.

Additionally, the current framework assumes "full information," meaning agents have access to exact state-action value functions ($Q$-functions). Extending these results to the bandit setting—where agents must explore based only on realized rewards—remains a primary challenge. Finally, while the algorithm is polynomial-time, the constants involved are currently high, suggesting that further optimization is needed for practical implementation in large-scale environments.

Summary updated

BibTeX
@inproceedings{erez2023regret,
  author = {Liad Erez and Tal Lancewicki and Uri Sherman and Tomer Koren and Yishay Mansour},
  title = {{Regret Minimization and Convergence to Equilibria in General-sum Markov Games}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=ILMHlUn4k6},
}
Figure