PaperlayerView exact revision on arXiv

Source-linked AI summary

Game-Theoretic Multiagent Reinforcement Learning

Yaodong Yang, Chengdong Ma, Zihan Ding, Stephen McAleer, Chi Jin, Jun Wang, Tuomas Sandholm

arXiv:2011.00583v5cs.MAcs.AI

TL;DR

MARL has advanced substantially, but existing surveys do not provide a self-contained, up-to-date treatment of its game-theoretic foundations and developments since 2010. This monograph synthesizes MARL fundamentals and recent advances from a game-theoretic perspective, covering applications that achieve expert, grandmaster-level, and human-level performance.

  • Problem

    Existing MARL surveys are often outdated and do not fully cover modern methods, game-theoretic foundations, or developments since 2010.

  • Method

    The monograph provides a self-contained game-theoretic treatment of MARL, covering policy objectives, equilibrium representations, and sequence-form methods alongside recent advances.

  • Results

    MARL has achieved expert-level performance in Stratego, grandmaster-level performance in StarCraft II, and human-level performance in Diplomacy.

  • Takeaways & Limitations

    Combining game theory with deep reinforcement learning can scale MARL to complex multiagent systems and provide theoretical properties and convergence guarantees.

  • Takeaways & Limitations

    Finding Nash equilibria is computationally demanding, with worst-case solution time potentially exponential in game size.

Abstract

from arXiv · show

Tremendous advances have been made in multiagent reinforcement learning (MARL). MARL corresponds to the learning problem in a multiagent system in which multiple agents learn simultaneously. It is an interdisciplinary field of study with a long history that includes game theory, machine learning, stochastic control, psychology, and optimization. Despite great successes in MARL, there is a lack of a self-contained overview of the literature that covers game-theoretic foundations of modern MARL methods and summarizes the recent advances. The majority of existing surveys are outdated and do not fully cover the recent developments since 2010. In this work, we provide a monograph on MARL that covers both the fundamentals and the latest developments on the research frontier. The goal of this monograph is to provide a self-contained assessment of the current state-of-the-art MARL techniques from a game-theoretic perspective. We expect this work to serve as a stepping stone for both new researchers who are about to enter this fast-growing field and experts in the field who want to obtain a panoramic view and identify new directions based on recent advances.

Table des matières

The work is titled Game-Theoretic Multiagent Reinforcement Learning and is authored by Yaodong Yang and collaborators.

  • The monograph is titled Game-Theoretic Multiagent Reinforcement Learning.
  • Yaodong Yang, Chengdong Ma, Zihan Ding, Stephen McAleer, Chi Jin, Jun Wang, and Tuomas Sandholm are listed as authors.
  • The work is identified as a 2025 publication with DOI 10.1561/XXXXXXXXX.

Introduction

Reinforcement learning learns long-term decisions through trial and error, while MARL extends this setting to interacting agents whose policies and joint actions shape the environment. The monograph highlights major empirical successes alongside persistent coordination and non-stationarity challenges.

  • Deep Reinforcement Learning: RL trains agents through trial and error to achieve long-term goals without labeled data.
  • Deep Reinforcement Learning: AlphaGo achieved top-professional-level performance in Go despite a search space of 10^761 possible games.
  • Multiagent Reinforcement Learning: Persistent challenges include non-stationarity, multiple equilibria, coordination, scalability, and theoretical gaps in convergence.
  • Multiagent Reinforcement Learning: AlphaStar ranked above 99.8% of human players in StarCraft II, a partially observed game with 10^26 possible choices per move.
  • Multiagent Reinforcement Learning: MARL systems achieved superhuman or human-level performance in Dota2, capture-the-flag, hide-and-seek, poker, Stratego, and Diplomacy.

Single-Agent RL

Single-agent RL formulates sequential decision-making with MDPs and learns policies that maximize discounted rewards, using value-based or policy-based methods. Classical formulations offer guarantees under restrictive assumptions but face scalability and continuous-space limitations.

  • Problem Formulation: Markov Decision Process: An MDP consists of states, actions, transition probabilities, rewards, and a discount factor.
  • Problem Formulation: Markov Decision Process: At each step, the agent observes a state, executes an action, transitions under P, and receives an immediate reward.
  • Problem Formulation: Markov Decision Process: The Q-function gives expected return for an action in a state, while the value function gives return associated with a policy in that state.
  • Solving Markov Decision Processes: Linear-programming formulations become impractical for millions of variables and cannot directly solve continuous state-action spaces.
  • Solving Markov Decision Processes: Value-based methods learn Q-functions and derive policies greedily, whereas policy-based methods directly optimize parameterized policies.
  • Solving Markov Decision Processes: The Bellman optimality operator is a contraction, making the optimal Q-function its unique fixed point.
  • Solving Markov Decision Processes: Q-learning converges to the optimal Q-function for finite discrete state-action sets visited infinitely often, with later work providing high-probability bounds for infinite state spaces.

Multi-Agent RL

MARL extends sequential reinforcement learning to settings where agents’ joint actions determine state transitions and individual rewards. Stochastic games provide the core framework, while equilibrium concepts and game representations expose both solution methods and computational barriers.

  • In MARL, agents learn through trial and error while jointly determining environmental transitions and received rewards.
  • A stochastic game extends an MDP with multiple agents, shared states, individual action sets, joint-action transitions, rewards, and discounting.
  • At each time step, agents act simultaneously, their joint action induces a transition, and each agent receives an immediate reward.
  • Solution concepts: A mixed-strategy Nash equilibrium exists in discounted and average-reward stochastic games, although equilibrium uniqueness is NP-hard to check.
  • Solution concepts: Finding Nash equilibria is computationally demanding: two-player general-sum games are PPAD-hard, while pure-equilibrium existence in stochastic games is PSPACE-hard.
  • Game representations: Sequence-form representations avoid the exponential size of normal form, and zero-sum extensive-form games can be solved in polynomial time without expanding to normal form.

Grand Challenges of MARL

MARL faces interacting challenges from scale, conflicting objectives, changing opponents, and limited convergence theory. These difficulties make general-sum learning with many agents substantially harder than simpler cooperative or zero-sum settings.

  • Scalability: The joint action space grows exponentially with the number of agents, while general-sum Nash-equilibrium computation is PPAD-hard even for two players.
  • Scalability: Factorized reward or Q-function structures can yield polynomial-time equilibrium computation in restricted graphical games, but their application scope is limited.
  • Scalability: Factorized Q-function methods mainly apply to team games and generally lack theoretical guarantees about representational power and approximation error.
  • Learning objectives: MARL objectives include rationality and convergence because agents’ goals are not necessarily aligned by a single metric.
  • Learning objectives: Most MARL algorithms lack rigorous convergence guarantees, require strong assumptions such as a unique equilibrium, or are provably non-convergent in some settings.
  • Non-stationarity and opponents: Concurrent policy improvement makes the environment non-stationary, undermining Markovian assumptions and causing independent policy-gradient methods to be non-convergent in simple linear-quadratic games.
  • Non-stationarity and opponents: Competitive opponents may adaptively exploit weaknesses, requiring learners to account for dynamically changing adversarial strategies.
  • Overall challenge: General-sum learning with more than two agents remains an open challenge because combinatorial complexity, multidimensional objectives, and non-stationarity compound.

A Survey of MARL Surveys

MARL research can be surveyed through complementary taxonomies rather than a single universal categorization. The monograph organizes prior work by game type, information access, learning paradigm, and five research agendas while reviewing major historical perspectives.

  • The survey reviews algorithms across identical-interest, zero-sum, and infinite-player games using multiple taxonomies.
  • Because MARL has multiple objectives and solution concepts, identifying the right research question is itself known as the problem problem.
  • Taxonomies: Stage-game taxonomies distinguish team or potential games, zero-sum or harmonic games, general-sum games, and newer mean-field games.
  • Taxonomies: MARL methods also differ by agents’ local knowledge during training and execution, which affects behavior and theoretical-analysis difficulty.
  • Taxonomies: Learning-paradigm categories include centralized controllers, shared policies, centralized training with decentralized execution, and decentralized networked training.
  • Research agendas: The monograph adopts five established research agendas and structures subsequent discussions around constructing cooperative and noncooperative game-theoretic models and designing equilibrium-learning algorithms.
  • Prior surveys: Existing surveys cover cooperation, evolutionary-game connections, opponent modeling, knowledge reuse, and broader multiagent-learning perspectives, but no single survey can include every categorization.

Learning in Identical-Interest Games

Identical-interest games model agents with shared goals, enabling single-agent methods over joint actions but creating coordination and scalability challenges. The section also covers factorisation, decentralised execution, bounded-rationality reasoning, and convergence guarantees for partial-observation settings.

  • Most MARL algorithms assume homogeneous agents collaborating toward shared goals, often represented by symmetric payoffs.
  • Shared rewards allow single-agent reinforcement learning algorithms to operate over the joint action space because agents have identical Q-functions.
  • Multiple equilibria can produce inferior coordinated outcomes unless agents coordinate their equilibrium selection or model other agents’ policies.
  • Independent local Q-functions can avoid the combinatorial joint-action space, but independent Q-learning does not fully resolve multiagent coordination challenges.
  • Coordination graphs and factorised Q-functions exploit sparse dependencies to find globally optimal joint actions through message passing.
  • VDN, QMIX, and QTRAN impose structural constraints for decentralisable tasks, while Q-DPP removes those constraints and promotes diverse exploration.Q-DPP represents the VDN, QMIX, and QTRAN structures as exceptional cases of its broader formulation.
  • Probabilistic recursive reasoning models bounded rationality by nesting higher-level best responses to lower-level agents’ policies.PR2 introduced bounded-rationality reasoning in MARL, while ROMMEO and GR2 extended recursive policy decomposition and reasoning.
  • Dec-POMDPs are NEXP-complete, but occupancy-state methods converge with probability one to near-optimal finite-horizon plans.CTDE methods instead use centralized training with decentralized execution, commonly through a centralized critic and decentralized actors.

Learning in Zero-Sum Games

Zero-sum games provide a clear equilibrium objective through minimax reasoning, while larger games rely on iterative learning algorithms. The section compares gradient-based methods, their convergence rates, and their limitations under different objective geometries.

  • In two-player zero-sum games, each player selects a strategy that minimizes the opponent’s best-response utility, yielding a linear-program formulation.
  • The minimax theorem makes Nash equilibrium an unambiguous solution concept that guarantees the equilibrium game value even when the opponent knows the strategy.
  • For games too large for linear programming, learning algorithms iteratively approach potentially approximate Nash equilibria, with rates classified as linear, sublinear, or superlinear.
  • Gradient-based methods: GDA achieves average-iterate convergence at O(1/ϵ2) in smooth convex-concave cases, but can cycle, diverge, or fail in bilinear and nonconvex settings.
  • Gradient-based methods: OGDA achieves average-iterate convergence at O(1/ϵ) for smooth convex-concave objectives and has a reported last-iterate rate of O(1/ϵ9).
  • Gradient-based methods: Optimistic gradient methods achieve linear convergence in convex-concave cases, while proximal-point methods converge linearly for bilinear or strongly-convex-strongly-concave problems.Proximal-point implementation may be computationally costly because it requires matrix inverses.
  • Gradient-based methods: Stochastic GDA estimates gradients from samples and has convergence results for smooth nonconvex-strongly-concave and nonconvex-concave objectives.
  • Gradient-based methods: Two-time-scale methods use asymmetric learning rates, and their stochastic extension is provably convergent to Nash equilibrium with finite samples.

7.1. Minimax Optimization

Minimax optimization provides a core framework for solving equilibria in two-player zero-sum games and supports algorithms used in more complex games. The section compares best-response, gradient-based, and multiplicative-weights methods, emphasizing their differing convergence behavior and guarantees.

  • Multiplicative-weights methods: Vanilla Multiplicative Weights Update cycles and can fail to converge even in simple bilinear games.Consequently, it lacks a last-iterate convergence guarantee.
  • Multiplicative-weights methods: Optimistic Multiplicative Weights Update achieves linear convergence in bilinear games when the equilibrium is unique.OMWU uses the same learning-rate parameter as MWU.
  • Gradient-based methods: Extra-Gradient has average-iterate rate O(1/ϵ) and last-iterate rate O(1/ϵ^2) in convex-concave settings.For bilinear and smooth strongly convex-concave cases, it achieves a linear rate O(κ log 1/ϵ).
  • Equilibrium foundations: Minimax optimization directly formulates Nash equilibrium computation in two-player zero-sum normal-form games.The formulation also serves as a subroutine for stochastic and extensive-form games.
  • Best-response methods: Fictitious Play reaches ϵ-NE at rate (1/ϵ)Ω(A), while Double Oracle converges at rate O(|A|) in normal-form games.Fictitious Play responds to historical average strategies, whereas Double Oracle expands a restricted strategy set using best responses to its Nash equilibrium.
  • Regret-minimization methods: Hedge obtains regret O(√T log A), while Optimistic Hedge obtains O(N log A log^4 T) regret in multi-player general-sum games.These guarantees apply when each player has an action space of size A.

7.3 Continuous-Action Normal-Form Games

Continuous-action game optimization faces rotational dynamics and nonconvergence, motivating gradient, mirror-descent, and extragradient variants with increasingly broad convergence guarantees. Related stochastic-game results extend equilibrium learning to tabular, linear, and general function-approximation settings with explicit rates.

  • 7.3 Continuous-Action Normal-Form Games: Vanilla GDA can cycle or diverge in nonconvex-nonconcave games, while strict convex-concavity typically yields convergence to the von Neumann solution.Without strict convexity, GDA may fail to converge to any equilibrium.
  • 7.3 Continuous-Action Normal-Form Games: OMD variants establish convergence across coherent problems, distributed settings, alternating updates, and efficiency guarantees when equilibria are not approached.The cited results include extra-gradient, optimistic, distributed, and alternating mirror-descent methods.
  • 7.3 Continuous-Action Normal-Form Games: OGDA achieves last-iterate convergence to saddle points in unconstrained convex-concave min-max optimization.Related analyses report O(1/k) convergence rates for deterministic and stochastic variants.
  • 7.3 Continuous-Action Normal-Form Games: Extragradient methods provide convergence results for co-monotone inclusions, distributed stochastic minimax optimization, QRE computation, and nonlinear alternating updates.The surveyed methods include LocalAdaSEG, EG+, stochastic EG, and AGE.
  • 7.3 Continuous-Action Normal-Form Games: Rotational dynamics are a central obstacle in continuous zero-sum games, prompting physically motivated optimizers such as the second-order LEAD method.Existing approaches typically use hand-designed mechanisms to control these rotations.
  • 7.3 Continuous-Action Normal-Form Games: Projected nested-gradient and projection-free Stackelberg methods achieve global convergence guarantees at sublinear rates for zero-sum LQ games.These are identified as among the most promising results for that setting.
  • 7.4.1 Tabular Stochastic Games: Tabular value-based methods obtain explicit approximate-equilibrium rates, including ˜O(H^4S^2AB/ϵ^2) for VI-ULCB and improved ˜O(H^3SAB/ϵ^2) bounds for Nash-VI.Nash-VI also finds CCE in multiplayer general-sum games, while V-learning addresses the curse of multiagents.

7.5 Extensive-Form Games

The section surveys game-theoretic MARL methods for extensive-form games, emphasizing regret minimization, policy-gradient connections, oracle-based solvers, and scalability challenges. These methods provide convergence guarantees in selected settings, while practical performance and generalization remain constrained by variance, exploitability, and game size.

  • 7.5 Extensive-Form Games: In zero-sum games, average regret below ϵ for both players yields a 2ϵ-NE, while general-sum games yield an ϵ-coarse correlated equilibrium.These guarantees connect no-regret learning and Hannan consistency to equilibrium outcomes.
  • Counterfactual Regret Minimization (CFR): CFR-type methods achieve counterfactual regret bounds of O(√(T · |S|)) and generate average policies with O(|S|/√T) convergence behavior in two-player zero-sum games.CFR scales beyond linear-programming approaches, reaching games with up to 10^12 states, while CFR+ reaches up to 10^14 states.
  • Counterfactual Regret Minimization (CFR): Deep CFR methods improve poker performance but can become unstable because importance sampling produces high-variance counterfactual regret targets, especially over long horizons.DREAM reduces variance with learned baselines, while ESCHER directly estimates regret and is guaranteed to converge to an approximate Nash equilibrium with high probability.
  • Policy Gradient: Self-play scales to large video games, whereas regularized policy-gradient methods such as MMD provide last-iterate convergence to a QRE in normal-form and extensive-form games.Self-play itself does not converge to a Nash equilibrium; MMD adds policy regularization to obtain convergence guarantees.
  • Policy Gradient: Multiagent actor-critic methods can be formulated as special CFR methods because their advantage functions differ from counterfactual values only by a realization-probability constant.This equivalence transfers similar convergence guarantees and regret bounds to two-player zero-sum games.
  • Double Oracle: The general double-oracle framework recovers fictitious-play variants through choices of its metagame solver and best-response oracle, while later methods address sequential training and strategy-expansion costs.Pipeline PSRO trains best responses simultaneously, Anytime PSRO avoids increasing exploitability, and NXDO achieves iteration complexity linear in information sets rather than exponential.
  • Fictitious Play: Generalized weakened fictitious play incorporates approximate model-free best responses and perturbations, enabling deep Q-learning, policy exploration, and maximum-entropy reinforcement learning.In potential games, smooth fictitious play converges to a neighborhood of Nash equilibria and, in almost all N × 2 potential games, toward a pure-strategy equilibrium with probability one.
  • Imperfect-Information Subgame Solving: Imperfect-information subgame solving has demonstrated superhuman poker performance, but scalability, abstraction, exploitability control, and transfer beyond poker remain unresolved challenges.Generative and opponent-limited subgame solving reduce subgame sizes, yet applicability to economic models, security games, adversarial teams, and other domains remains underexplored.

7.6. Online Markov Decision Processes

Abstraction methods can be combined across domains to improve computational efficiency while retaining theoretical guarantees, with notable applications in complex games such as poker.

  • Abstraction methods can be applied cohesively across different domains.The passage connects this cohesion with computational efficiency and theoretical guarantees.
  • Systems can integrate Nash equilibrium solvers with abstraction pipelines.These integrations target massive strategy spaces in complex games such as poker.
  • Abstraction methods have shown practical success in real-world applications, particularly poker.

7.6 Online Markov Decision Processes

Online MDPs extend online learning to dynamic environments with state variables, seeking policies that perform well against arbitrary opponents by minimizing regret relative to the best retrospective stationary policy.

  • Online MDPs model real-world decision problems as dynamic environments with state variables.This extends online learning beyond stateless repeated decision problems such as multi-arm bandits.
  • The agent seeks policies that perform well against every possible opponent, including adversarial opponents.The opponent need not be rational or self-optimizing.
  • Regret compares the agent with the best stationary policy in retrospect.The learning objective is to minimize average loss during the learning process.
  • An adversary may control reward functions and transition dynamics without necessarily competing directly with the agent.
  • Sub-linear regret requires changing rewards to be chosen obliviously in the cited online MDP results.The oblivious assumption fixes reward functions and transition kernels in advance, although they remain unknown to the agent.
  • No polynomial-time solution is known for online shortest path when both rewards and transitions are adversarially chosen, even under an oblivious adversary.

7.6. Online Markov Decision Processes

Online MDP regret minimization uses local-global decomposition or online linear optimization, yielding algorithms with guarantees under different feedback, model-knowledge, and function-approximation settings.

  • Local regret minimization at each state can yield global no-regret performance.The decomposition uses the state occupancy induced by the comparator policy.
  • Under known transitions and full-information rewards, MDP-E uses Hedge as its regret minimizer.
  • The fixed-MDP regret lower bound is Ω(√(|S||A|T)).
  • Under bandit feedback, MDP-EXP3 achieves O(τ√(T|A| log |A|/β)) regret.Here τ is the MDP mixing-time bound and β lower-bounds the probability of reaching a state under a policy.
  • Q-FPL removes the requirement of knowing the transition kernel by incorporating Q-learning and achieves O(T^2/3) regret.
  • OPPO achieves O(d^2H^3T) regret when transitions are unknown but reward functions are fully observed.The feature dimension is d, the episode horizon is H, and T is the total number of steps.
  • Online mirror descent is recovered when the divergence is chosen as a Bregman divergence.The resulting method has nearly optimal regret for online linear optimization problems.
  • O(τT log(|S||A|)) regret is stated for the full-information setting, while the bandit setting has an O(√(T|S||A| log(|S||A|))) bound.

7.7 Team Games

Team games give teammates shared utilities; in two-team zero-sum games, solution concepts distinguish whether teammates can coordinate before play.

  • Team-game members share the same utility functions.
  • In two-team zero-sum games, TMEC allows players on the same team to coordinate before playing.
  • A team-maxmin equilibrium describes settings where team members cannot coordinate.A TME yields the maximum expected utility for the team within that non-coordinating setting.

Learning in General-Sum Games

Learning in general-sum games ranges from nonlinear programming and value-based methods to policy-based and mean-field approaches. The literature establishes convergence and tractability results under specific conditions, while general-sum multiagent learning remains challenging.

  • Finding Nash equilibria in general-sum games is computationally difficult, with static two-player normal-form equilibrium known to be PPAD-complete.
  • The stochastic-game nonlinear program minimizes temporal-difference error while enforcing policy-improvement and policy-validity constraints.Its quadratic inequality constraints make the optimization nonlinear.
  • Optimistic Nash-VI and related value-based methods provably find correlated equilibria in multiplayer general-sum stochastic games with finite sample-complexity rates.The cited methods target coarse correlated, correlated, and Nash equilibria under their respective guarantees.
  • Policy-gradient learning in multiagent games lacks the single-agent gradient-flow structure needed for straightforward almost-sure convergence, especially with deep networks and stochastic gradient descent.
  • Mean-field approximation transforms many-body interactions into agent-population interactions, making large-N learning more tractable.For cooperative control, the resulting dimension is independent of N and can approximate game values and optimal strategies.
  • Mean-field game equilibria can exist and may be unique under small-parameter conditions, while general models can admit multiple equilibria.Mean-field control also avoids exponential growth in N under its infinite-population formulation.
  • For large β, the Boltzmann policy is a contraction mapping, making the optimal action unique given the mean action and resolving the chicken-and-egg problem.
  • MF-Q has demonstrated strong empirical performance against humans in Uber China taxi dispatching and has been extended to heterogeneous agents and partial observability.The partially observable variant maintains a distribution representing uncertainty about the system mean field.

Future Directions

MARL theory remains substantially less developed than MARL’s empirical practice, especially for multiagent extensions of reinforcement-learning guarantees and deep methods.

  • Theoretical understanding of MARL techniques remains under-explored despite the field’s remarkable empirical success.
  • Extending single-agent convergence properties and finite-sample bounds to multiagent, many-agent settings is non-trivial.
  • Deep MARL methods require theories that explain and provide insight into their effectiveness when neural networks represent value functions.

144 Future Directions

Future MARL research spans theoretical guarantees, safety, model-based learning, task generalization, and foundation-model integration. These directions seek broader applicability, improved efficiency, and stronger understanding of multiagent decision-making.

  • MARL Theory: A comprehensive summary of existing MARL algorithms with theoretical convergence guarantees remains a research need.
  • Safe and Robust MARL: Safe and robust MARL must incorporate constraints for deployment in real-world environments such as autonomous driving.
  • Model-Based MARL: Model-based MARL explicitly learns state-transition dynamics, extending a well-studied single-agent approach that merits greater community attention.Most algorithms in the monograph are model-free and learn through interaction without knowing how the environment works.
  • Multiagent Meta-RL: Multiagent meta-RL aims to use one model across multiple tasks instead of requiring a bespoke MARL model for each task.
  • Multiagent Meta-RL: Meta-learning trains generalized models across tasks so new tasks can be solved with few or no additional training samples.
  • Multiagent Meta-RL: Meta-learning for games has achieved faster convergence to equilibria than solving games in isolation while recovering single-game guarantees for arbitrary sequences.Poker endgame experiments with varying stack sizes showed efficiency gains often by an order of magnitude.
  • Multiagent Meta-RL: MAML is compatible with any model trained by gradient descent, but extending meta-learning to MARL remains largely uncharted.Making groups of agents master multiple games requires automatically discovering identities and roles across games.
  • Foundation Models for MARL: Foundation models for MARL combine pretrained models’ knowledge-transfer capabilities with multiagent sequential decision-making.
Loading 2011.00583v5…