Source-linked AI summary
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms
Kaiqing Zhang, Zhuoran Yang, Tamer Başar
TL;DR
MARL has empirically advanced while its theoretical foundations and learning objectives remain limited or contested. This chapter selectively reviews theoretically analyzed algorithms across major game frameworks and task types, highlighting new taxonomies and research directions.
Problem
MARL theory faces unclear learning goals and unresolved convergence criteria across cooperative, competitive, and mixed settings.
Method
The chapter selectively synthesizes theoretically analyzed MARL algorithms across Markov/stochastic and extensive-form games, organized by task type and information structure.
Results
The overview categorizes cooperative, competitive, and mixed MARL methods while highlighting extensive-form, networked, mean-field, and policy-convergence perspectives.
Takeaways & Limitations
The chapter provides a focused assessment of MARL theory and identifies future directions for theoretical studies.
Takeaways & Limitations
Theoretical analysis of deep MARL remains limited, particularly with function approximation and deep neural networks.
Abstract
from arXiv · showhide
Recent years have witnessed significant advances in reinforcement learning (RL), which has registered great success in solving various sequential decision-making problems in machine learning. Most of the successful RL applications, e.g., the games of Go and Poker, robotics, and autonomous driving, involve the participation of more than one single agent, which naturally fall into the realm of multi-agent RL (MARL), a domain with a relatively long history, and has recently re-emerged due to advances in single-agent RL techniques. Though empirically successful, theoretical foundations for MARL are relatively lacking in the literature. In this chapter, we provide a selective overview of MARL, with focus on algorithms backed by theoretical analysis. More specifically, we review the theoretical results of MARL algorithms mainly within two representative frameworks, Markov/stochastic games and extensive-form games, in accordance with the types of tasks they address, i.e., fully cooperative, fully competitive, and a mix of the two. We also introduce several significant but challenging applications of these algorithms. Orthogonal to the existing reviews on MARL, we highlight several new angles and taxonomies of MARL theory, including learning in extensive-form games, decentralized MARL with networked agents, MARL in the mean-field regime, (non-)convergence of policy-based methods for learning in games, etc. Some of the new angles extrapolate from our own research endeavors and interests. Our overall goal with this chapter is, beyond providing an assessment of the current state of the field on the mark, to identify fruitful future research directions on theoretical studies of MARL. We expect this chapter to serve as continuing stimulus for researchers interested in working on this exciting while challenging topic.
1 Introduction
The chapter surveys MARL theories and algorithms across cooperative, competitive, and mixed settings, emphasizing theoretically analyzed methods in Markov/stochastic and extensive-form games. It also highlights underexplored directions, including decentralized networked agents and other emerging MARL regimes.
- MARL settings: MARL spans fully cooperative, fully competitive, and mixed settings, distinguished by common, zero-sum, and general-sum returns.Cooperative agents optimize a shared long-term return, competitive agents’ returns usually sum to zero, and mixed settings combine cooperative and competitive agents.
- Motivation: Despite rapid growth driven by single-agent RL and related fields, MARL efforts are not uniformly supported by rigorous theoretical foundations.The chapter attributes the resurgence and large volume of work partly to advances in deep learning, operations research, and multi-agent systems, while noting limited theoretical understanding.
- Scope and organization: The chapter selectively reviews MARL in Markov/stochastic games and extensive-form games, prioritizing algorithms with convergence and complexity analyses.The review uses discrete-time settings and organizes algorithms according to the cooperative, competitive, and mixed task types they address.
- Applications and outlook: The chapter also connects theoretical MARL algorithms to significant, challenging applications and identifies future directions for theoretical study.Its stated goal is to assess the field’s current theoretical state while stimulating further research on this challenging topic.
- New angles: The review extends existing taxonomies by discussing extensive-form games alongside Markov games and decentralized MARL with networked agents.These topics are presented as comparatively underexplored angles in prior MARL reviews.
2 Background
The section introduces reinforcement learning through discounted Markov decision processes, then distinguishes value-based and policy-based approaches before extending the setting to multi-agent decision-making and imperfect-information games.
- Markov Decision Processes: An MDP is defined by (S,A,P,R,γ), representing states, actions, transitions, rewards, and discounting between immediate and future returns.The discount factor satisfies γ ∈[0,1).
- Reinforcement Learning: Reinforcement learning learns an optimal policy from environment interaction without requiring prior knowledge of transition probabilities or reward functions.Dynamic programming methods instead require the model.
- Value-Based Methods: Value-based methods estimate the optimal Q-function and extract a policy greedily, while Q-learning and SARSA have convergence guarantees in finite spaces.Q-learning converges almost surely under certain stepsize conditions, and deep Q-learning has achieved human-level control results with neural networks.
- Policy-Based Methods: Policy-based methods optimize parameterized policies through policy gradients, with methods including REINFORCE, G(PO)MDP, and actor-critic algorithms.Policy-based methods are described as having better convergence guarantees, particularly with neural-network function approximation.
- Multi-Agent Reinforcement Learning: Multi-agent reinforcement learning extends sequential decision-making to multiple agents whose joint actions influence system evolution and individual rewards, which depend on other agents’ policies.The framework supports broad practical applications and includes imperfect-information extensive-form games in which agents cannot distinguish histories within the same information set.
3 Challenges in MARL Theory
MARL theory faces challenges beyond single-agent RL, including unclear and multidimensional learning objectives, non-stationary interactions, combinatorial scaling, limited deep-MARL theory, and complex information structures. These challenges make convergence analysis difficult and motivate centralized or networked decentralized learning schemes.
- Learning goals: MARL objectives can be unclear and multidimensional, making convergence to Nash equilibrium an insufficiently settled primary criterion.The text identifies problem formulation as a fundamental flaw in early MARL work and notes controversy over convergence as the dominant criterion.
- Non-stationarity: Multi-agent learning is non-stationary because each agent’s actions affect other agents’ rewards and the evolving state, invalidating stationarity assumptions.Independent learners that ignore this issue may fail to converge, although they can achieve satisfactory empirical performance in some settings.
- Scalability: Accounting for joint actions creates a combinatorial space whose dimension grows exponentially with the number of agents, complicating scalability and convergence analysis.Theoretical development is described as more advanced for two-player zero-sum settings than for larger multi-agent settings.
- Deep MARL: Deep MARL remains an almost uncharted theoretical territory because scalability requires function approximation while deep learning and deep RL theory remain limited.The passage characterizes deep-MARL analysis as currently limited despite empirical success.
- Information structure: MARL has more involved information structures across training and execution, with different learning schemes producing different levels of theoretical difficulty.Central controllers can aggregate joint information and design policies, whereas decentralized schemes may require agents to share local information over communication networks.
4 MARL Algorithms with Theory
This section selectively reviews theoretically grounded MARL algorithms, organized by task and primarily developed within fully observed Markov games and extensive-form games, with a brief discussion of cooperative Dec-POMDPs.
- 4 MARL Algorithms with Theory: The review covers MARL algorithms focused exclusively on theoretical studies and categorizes them according to the tasks they address.Its main frameworks are fully observed Markov games and extensive-form games, with a brief cooperative Dec-POMDP discussion.
4.1 Cooperative Setting · 4.1.1 Homogeneous Agents · Multi-Agent MDP & Markov Teams
The section surveys cooperative MARL with homogeneous agents, emphasizing common rewards, joint-action Q-learning, equilibrium-selection challenges, scalable distributed methods, and limited policy-based convergence guarantees.
- 4.1 Cooperative Setting: Cooperative MARL has agents collaborate toward a shared goal, forming a major class of multi-agent reinforcement-learning settings.
- 4.1.1 Homogeneous Agents: Most cooperative settings use homogeneous agents with a common reward that aligns their interests and can make agents interchangeable in large populations.
- Multi-Agent MDP & Markov Teams: With identical rewards, all agents share one Q-function, enabling each to apply standard Q-learning while maximizing over the joint action space.
- Multi-Agent MDP & Markov Teams: Q-function convergence does not ensure equilibrium-policy convergence when equilibrium policies are non-unique and agents fail to coordinate their selection.NE-policy convergence is guaranteed under a unique equilibrium or coordinated equilibrium selection.
- Multi-Agent MDP & Markov Teams: Scalability is essential because independent Q-learning may fail to converge; distributed Q-learning instead converges for deterministic finite MMDPs using local state-action Q-tables.
- Multi-Agent MDP & Markov Teams: The only noted policy-based convergence guarantee uses two-timescale actor-critic fictitious play, combining actor policy mixing with faster-timescale critic evaluation.
- Multi-Agent MDP & Markov Teams: Convergence is established for simultaneous-move multistage games with common rewards, including zero-sum rewards, under special Markov-team conditions where each state is visited once.
Markov Potential Games
Markov potential games extend potential games to sequential decision-making while preserving a shared potential function that links unilateral policy changes to changes in individual rewards.
- Markov Potential Games: Markov potential games extend potential games—where unilateral policy changes alter an agent’s reward in proportion to the shared potential function—to sequential decision-making.Potential games provide a game-theoretic framework for modeling cooperation through a potential function shared by all agents.
Mean-Field Regime
The mean-field regime addresses scalability by modeling extremely large populations of homogeneous, interchangeable agents through aggregate quantities such as average states or empirical state distributions. Recent theory covers both noncooperative mean-field games and cooperative teams/control, including convergence results for policy-gradient and mean-field Q-learning methods.
- Mean-Field Regime: Mean-field modeling targets scalability by making each agent’s effect infinitesimal and representing interactions through aggregate quantities such as average states or empirical state distributions.Agents become interchangeable or indistinguishable, and each agent needs to determine the best specified action from this reduced interaction model.
- Mean-Field Regime: Recent mean-field MARL work has focused mainly on noncooperative mean-field games, while cooperative research studies Markov teams with shared rewards depending on local state and the mean field.The shared reward structure encourages cooperation among agents.
- Mean-Field Regime: Mean-field teams seek an optimum, whereas mean-field games seek an equilibrium, reflecting the distinction between dynamic team theory and game theory.Mean-field teams can be viewed as a special case of mean-field games, but the literature commonly reviews them separately.
- Mean-Field Regime: Several popular RL algorithms can be translated to mean-field teams, while policy gradients converge for linear quadratic mean-field control and mean-field Q-learning converges for general mean-field control.These results concern large populations of cooperative decision-makers modeled through mean-field control.
4.1.2 Decentralized Paradigm with Networked Agents
This section considers decentralized cooperative MARL with heterogeneous agents whose private reward functions differ, while the team optimizes the average reward. Such settings require greater coordination because global value estimation cannot be done locally without others’ reward functions, and centralized controllers may be unavailable.
- Decentralized Paradigm with Networked Agents: Agents may have different private reward functions while cooperating to maximize the team-average reward.The team-average reward is defined as ¯R(s,a,s′) = N −1 · P_i∈N Ri(s,a,s′).
- Decentralized Paradigm with Networked Agents: The framework applies broadly to sensor networks, smart grids, intelligent transportation systems, and robotics.
- Decentralized Paradigm with Networked Agents: This heterogeneous setting encompasses the homogeneous case but requires more coordination because agents cannot locally estimate the global value function without others’ reward functions.
- Decentralized Paradigm with Networked Agents: With a central controller, algorithms for the homogeneous setting can generally apply because it aggregates rewards and distributes information, but such a controller may not exist in practice.
Learning Optimal Policy
The section examines decentralized MARL methods for learning an optimal joint policy from local and neighboring information, emphasizing consensus-based Q-learning and actor-critic approaches. It also highlights convergence guarantees and their limitations under finite iterations, samples, and nonlinear function approximation.
- Networked decentralized learning: QD-learning combines standard Q-learning with consensus and innovation terms, and converges to the optimal tabular Q-function under suitable stepsize conditions.The innovation term captures differences between neighboring agents’ Q-value estimates.
- Networked decentralized learning: Decentralized actor-critic methods use consensus-based temporal-difference learning for local critic estimates and stochastic policy gradients for individual actors.Communication weights follow the network topology and satisfy a doubly stochastic property in expectation, enabling critic consensus.
- Networked decentralized learning: Almost sure convergence is established for decentralized actor-critic algorithms with linear value-function approximation, with extensions to continuous spaces using deterministic policy gradients and off-policy exploration.Deterministic on-policy behavior may not provide sufficient exploration in the continuous-space setting.
- Multi-task decentralized learning: Distributed actor-critic learning also addresses multi-task settings, where independent agents optimize a joint policy based on the average reward across agents.This setting treats each agent as solving an independent MDP unaffected by the others.
- Finite-sample and nonlinear limitations: Existing convergence guarantees are asymptotic and largely restricted to linear function approximation, leaving finite-sample performance and nonlinear approximators insufficiently quantified.Finite distributed optimization and nonlinear approximation can prevent exact consensus and create errors in agents’ Q-function estimates.
Policy Evaluation
Policy evaluation studies the critic step with a fixed joint policy, yielding a stationary sampling distribution and a convex objective under linear value-function approximation. The section formulates evaluation as distributed MSPBE minimization and reviews convergence results for gradient-TD, saddle-point, variance-reduced, and networked-agent methods.
- Policy Evaluation: With the joint policy fixed, policy evaluation uses linear value-function approximation and becomes convex because the sampling distribution is stationary.Each agent parameterizes V_ω(s) as φ(s)^⊤ω.
- Policy Evaluation: Agents jointly minimize the mean square projected Bellman error associated with the team-average reward.The formulation uses the projection operator Π_Φ and matrices A, C, and b under the state-occupancy measure.
- Policy Evaluation: Fenchel duality converts the finite-sum MSPBE objective into a distributed saddle-point problem that is convex in ω and concave in the dual variables {λ_i}i∈N.The saddle-point formulation uses empirical estimates of A, C, and each agent’s reward vector b_i.
- Policy Evaluation: Distributed gradient-TD methods achieve asymptotic convergence, while dynamic-consensus plus SAG solves the saddle-point problem with a linear rate and AVRG provides variance reduction.These results are reported for distributed policy evaluation based on the MSPBE formulation.
- Policy Evaluation: For independent agents interacting with independent MDPs, diffusion-based distributed GTD converges in mean square, while GTD2 and TDC have weak convergence over time-varying communication networks.Off-policy evaluation uses importance sampling, and agents need not know other agents’ actions when MDPs are uncoupled.
Other Learning Goals
Beyond standard decentralized MARL objectives, research has examined optimal consensus and communication-efficient learning with networked agents. These efforts include policy-iteration and actor-critic methods for consensus, alongside distributed policy-gradient and hierarchical algorithms designed to reduce communication.
- Consensus Learning: Optimal consensus learning minimizes network-wide consensus error while agents track neighboring states and a leader’s state.A policy-iteration algorithm and a neural-network actor-critic implementation are introduced for this objective.
- Communication Efficiency: Communication-efficient MARL reduces exchanges through trigger rules and hierarchical distributed algorithms.Lazily Aggregated Policy Gradient reduces communication rounds between agents and a central controller, while another method addresses policy evaluation.
4.1.3 Partially Observed Model
Partially observed cooperative MARL is commonly modeled as a decentralized POMDP, but theoretical analysis remains scarce. Existing approaches emphasize centralized learning with decentralized execution, while also exploring sampling-based planning and decentralized learning under shared information.
- 4.1.3 Partially Observed Model: Dec-POMDPs model cooperative settings in which agents face partial observability, a practically common regime with relatively scarce theoretical analysis.The framework shares core elements such as reward and transition structure with fully observed models.
- 4.1.3 Partially Observed Model: Most Dec-POMDP planning and learning algorithms use centralized learning with decentralized execution.The decentralized problem is reformulated centrally, solved using joint observation data, and the resulting policies are distributed to agents for execution.
- 4.1.3 Partially Observed Model: Finite-state controllers commonly represent local policies by mapping each agent’s observation histories to actions.Bayesian nonparametric methods can determine the controller size for variable-size finite-state controllers.
- 4.1.3 Partially Observed Model: Sampling-based methods improve computational efficiency through Monte Carlo policy iteration, expectation-maximization, and Monte Carlo tree search.Tree search has been applied to multi-agent POMDPs and multi-robot active perception.
- 4.1.3 Partially Observed Model: Decentralized learning can exploit shared information by reformulating Dec-POMDPs as centralized POMDPs observed by a virtual central controller.Another approach approximates the reformulated POMDP with finite-state MDPs with exponentially decreasing approximation error.
4.2 Competitive Setting
Competitive MARL theory establishes Nash equilibria through contractive Bellman operators and convergent value-based methods in zero-sum Markov games. In extensive-form games, fictitious play and CFR provide convergence or regret guarantees, while computational scalability remains a central limitation.
- Zero-sum Markov games: The optimal value is the unique solution of a γ-contractive Bellman equation, and policies attaining the supremum and infimum constitute a Nash equilibrium.A Nash equilibrium can be constructed from the optimal value using solutions to the associated optimization problem.
- Zero-sum Markov games: Value iteration converges linearly to the optimal value, satisfying ∥Vt+1 − V∗∥∞ ≤ γt+1 · ∥V0 − V∗∥∞.The contraction argument directly yields the stated error bound.
- Zero-sum Markov games: Minimax-Q learning is an online, off-policy, tabular extension of Q-learning for zero-sum Markov games and converges to the optimal action-value function under analogous conditions.Finite-sample Q-function error bounds are also established in the two-player zero-sum Markov-game setting, whereas guarantees with linear function approximation remain poorly understood.
- Fictitious play: Continuous-time fictitious play is Hannan consistent, and smoothed or stochastically perturbed discrete-time variants can converge to it.Data-driven fictitious self-play avoids iterating over every game state but the state-wise method suffers from the curse of dimensionality.
- Counterfactual regret minimization: CFR minimizes total regret through local counterfactual-regret minimization, yielding an O(1/T)-approximate Nash equilibrium for average self-play policies.Vanilla CFR traverses the entire game tree each iteration, motivating sampling, regression, and pruning variants; A2C and some policy-gradient methods are equivalent to CFR variants.
4.3 Mixed Setting
Mixed-setting MARL is notably less understood because equilibrium computation is hard and standard value-iteration or independent-learning approaches can fail. The literature therefore studies restrictive-convergence Q-learning variants, regret-based approximate equilibria, continuous-game dynamics, and mean-field formulations.
- Challenges: Mixed-setting MARL is notoriously challenging: Nash equilibrium computation is PPAD-complete even in two-player general-sum normal-form games, while value iteration can fail in general-sum Markov games.The cited results concern stationary Nash or correlated equilibria in general-sum Markov games.
- Value-based methods: Nash-Q maintains action-value functions for all agents and converges to Nash equilibrium under the restrictive condition that each iteration’s stage game has a unique Nash equilibrium.For zero-sum games, its Bellman operator reduces to the minimax-Q operator.
- Value-based methods: Decentralized Q-learning addresses scalability through a two-timescale modification and converges almost surely in weakly acyclic Markov games using only local actions and rewards.Independent learning is preferred for scalability but fails to converge in general.
- Policy-based methods: If every agent’s external regret is at most ϵ, average policies form an ϵ-approximate coarse correlated equilibrium, enabling self-play despite the general difficulty of finding Nash equilibria.This connection links game theory and online learning.
- Mean-field methods: Mean-field Nash-Q approximates other agents’ actions by their empirical average, yielding action values parameterized by each agent’s state, action, and empirical distribution.This approach is presented as a way to alleviate scalability in non-cooperative general-sum games.
- Mean-field methods: Recent mean-field-game work considers possibly non-stationary infinite-horizon equilibria and develops equilibrium-computation algorithms that lay foundations for model-free reinforcement learning.Earlier studies focused on finite-horizon or stationary mean-field equilibria.
5 Application Highlights
MARL has achieved representative practical successes across cooperative decentralized systems, imperfect-information games, and partially observed team-battle games. Highlighted applications include UAV coordination, Go, Texas hold’em poker, and StarCraft II.
- Unmanned aerial vehicles: UAV applications use cooperative decentralized MARL for link selection, navigation, spectrum sharing, and multi-target coverage while avoiding threats and collisions.Representative formulations include Markov teams, joint-action multi-agent Q-learning with linear function approximation, and probabilistic channel availability.
- Game of Go: AlphaGo became the first computer Go program to defeat a human professional on a full-sized board using deep CNN-based policy and value functions.AlphaGo Zero subsequently trained both networks solely through reinforcement learning and self-play, defeated stronger previous AlphaGo versions, and discovered non-standard strategies.
- Poker games: Texas hold’em exemplifies multiplayer extensive-form games with incomplete information because players remain unaware of opponents’ private cards and receive payoffs only after each hand ends.The heads-up no-limit variant has more than 6×10^161 information sets, making exhaustive traversal infeasible with contemporary computational power.
- Poker games: 3.9 × 10^14 information sets make heads-up limit hold’em challenging, while Pluribus surpassed top human professionals in six-player no-limit Texas hold’em.Pluribus combines abstraction, sub-game decomposition, Monte-Carlo CFR, self-play, and depth-limited search.
- Team-battle video games: OpenAI Five achieved superhuman performance and defeated human world champions in an imperfect-information team game by combining LSTM representations, PPO, and self-play.The setting requires decisions under uncertainty and incomplete information while balancing coordination with communication cost.
6 Conclusions and Future Directions
The chapter surveys theoretically analyzed MARL algorithms across cooperative, competitive, and mixed settings while emphasizing that theoretical understanding remains limited. It identifies partially observed, deep, model-based, policy-gradient, and safety-oriented MARL as important directions for future work.
- Chapter contributions: The chapter reviews mostly recent MARL algorithms with theoretical analysis, categorizing them as fully cooperative, fully competitive, or mixed.It also highlights several angles orthogonal to existing MARL reviews.
- Partially observed settings: Partially observed MARL can be modeled as partially observed stochastic games, but even cooperative Dec-POMDPs are NEXP-complete and difficult to solve.Heterogeneous beliefs arise from agents’ observations and differing information structures.
- Deep MARL theory: Deep neural networks improve MARL scalability and underpin many empirical successes, yet theoretical guarantees for deep MARL remain insufficiently developed.The chapter therefore calls for understanding global convergence in deep MARL, building on recent single-agent results.
- Model-based MARL: Model-based MARL remains scarce, with existing examples focused on single-controller stochastic games and zero-sum Markov games using optimism under uncertainty.The cited later algorithm is R-MAX for zero-sum Markov games.
- Convergence of policy gradient methods: Vanilla policy gradient methods generally lack convergence guarantees in MARL and may avoid even local Nash equilibria because of non-stationarity.Proposed stabilization assumptions are difficult to verify or satisfy in MARL, including simple linear-quadratic settings.
- MARL with robustness/safety concerns: Robustness and safety constraints are relatively uncharted in MARL, where conflicting objectives make guarantees involve coupling all agents.Constrained multiagent MDPs or Markov games provide a direct model for safety-critical applications such as autonomous driving.