Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model

Gen Li, Yuejie Chi, Yuting Wei, Yuxin Chen

Presented at NeurIPS 2022, this paper represents a significant theoretical milestone in Multi-Agent Reinforcement Learning (MARL). The authors introduce Q-FTRL, the first algorithm to achieve minimax-optimal sample complexity for learning equilibria in general-sum Markov games using a generative model. By doing so, it effectively resolves two long-standing bottlenecks in the field: the curse of multiple agents and the barrier of long horizons.

The Challenge: Scaling MARL

Reinforcement learning becomes exponentially more difficult when multiple agents are involved. In a Markov Game, an agent's environment is non-stationary because other agents are simultaneously learning and adapting their strategies.

Historically, researchers faced a "pick your poison" scenario regarding sample complexity:

  1. The Curse of Multiple Agents: Traditional model-based methods scale with the product of the agents' action spaces ($\prod A_i$). For example, a system with 10 agents having 2 actions each scales by $2^{10}$, rendering these methods unusable for large multi-agent systems.
  2. The Barrier of Long Horizon: Newer "V-learning" methods managed to scale with the sum of actions ($\sum A_i$), but they were highly inefficient regarding the game's horizon ($H$). These methods often scaled at $H^5$ or $H^6$, far from the theoretical lower bound.

This paper successfully designs an algorithm that is efficient in both the number of agents and the length of the game.

The Q-FTRL Algorithm

The authors assume access to a generative model (a simulator), which allows the learner to query any state-action pair and receive a sample transition. Their proposed algorithm, Q-FTRL, leverages this model using several key techniques:

  • Backward Induction: Utilizing the simulator, the algorithm solves the game from the last time step ($H$) back to the first ($1$). This eliminates the need for complex global exploration strategies required in standard online settings.
  • Follow-the-Regularized-Leader (FTRL): Instead of a simple greedy update, agents update their policies using an online adversarial learning framework. This is the critical mechanism that allows the sample complexity to scale with the sum of actions ($\sum A_i$) rather than the product.
  • Variance-Aware Bonuses: To achieve optimal $H$ dependency, the authors employ Bernstein-style upper confidence bounds (UCBs). They derive a new, refined regret bound for FTRL that explicitly accounts for the variance of the value functions, allowing for much tighter estimation.
  • Decentralization: Each player can run the Q-FTRL update independently without needing to observe the specific actions of their opponents, provided they can estimate their own expected rewards.

Key Theoretical Results

As a theoretical paper focused on fundamental limits, the primary results are mathematical proofs of sample complexity bounds rather than empirical benchmarks.

The paper proves that Q-FTRL finds an $\varepsilon$-approximate Coarse Correlated Equilibrium (CCE) in a general-sum Markov game using:

$$ \widetilde{O}\bigg( \frac{H^4 S \sum_{i=1}^m A_i}{\varepsilon^2} \bigg) \text{ samples} $$

Where:

  • $H$ is the horizon (game length).
  • $S$ is the number of states.
  • $m$ is the number of players.
  • $A_i$ is the number of actions for player $i$.

This result is minimax-optimal (up to logarithmic factors), meaning no algorithm can theoretically perform better in this setting. Furthermore, unlike many RL algorithms that require a massive "burn-in" period of data before becoming optimal, this bound holds for the entire range of the accuracy parameter ($\varepsilon$). For two-player zero-sum games, the same logic applies to finding a Nash Equilibrium with minimal samples.

Limitations and Future Directions

While a major theoretical leap, the approach has a few constraints:

  • Generative Model Requirement: The algorithm relies heavily on a simulator. In many real-world applications (like robotics or live financial markets), agents only have "online" access and must follow a continuous trajectory. Extending this optimal $H$ dependency to the online setting remains an open challenge.
  • Computational Hardness: While the algorithm finds a CCE efficiently for general-sum games, finding a true Nash Equilibrium in general-sum games remains computationally "PPAD-hard."
  • Fixed Number of Players: The optimality holds strictly when the number of players $m$ is relatively small or grows slowly (logarithmically) with other parameters. If $m$ is very large, other factors might dominate the complexity.

Summary updated

Abstract

This paper studies multi-agent reinforcement learning in Markov games, with the goal of learning Nash equilibria or coarse correlated equilibria (CCE) sample-optimally. All prior results suffer from at least one of the two obstacles: the curse of multiple agents and the barrier of long horizon, regardless of the sampling protocol in use. We take a step towards settling this problem, assuming access to a flexible sampling mechanism: the generative model. Focusing on non-stationary finite-horizon Markov games, we develop a fast learning algorithm called Q-FTRL and an adaptive sampling scheme that leverage the optimism principle in online adversarial learning (particularly the Follow-the-Regularized-Leader (FTRL) method). Our algorithm learns an $\varepsilon$-approximate CCE in a general-sum Markov game using $$ \widetilde{O}\bigg( \frac{H^4 S \sum_{i=1}^m A_i}{\varepsilon^2} \bigg) $$ samples, where $m$ is the number of players, $S$ indicates the number of states, $H$ is the horizon, and $A_i$ denotes the number of actions for the $i$-th player. This is minimax-optimal (up to log factor) when $m$ is fixed. When applied to two-player zero-sum Markov games, our algorithm provably finds an $\varepsilon$-approximate Nash equilibrium with a minimal number of samples. Along the way, we derive a refined regret bound for FTRL that makes explicit the role of variance-type quantities, which might be of independent interest.
BibTeX
@inproceedings{li2022minimax,
  author = {Gen Li and Yuejie Chi and Yuting Wei and Yuxin Chen},
  title = {{Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=WHj9MyVE8h},
}
Figure