Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms

• MARL spans cooperative, competitive, and mixed settings, but shared difficulties include equilibrium objectives, non-stationarity, combinatorial action spaces, and limited information.These challenges complicate theoretical analysis beyond single-agent RL, while communication, coordination, robustness, and scalability may matter beyond return optimization.Source: §1 · p. 2
• The review is motivated by rapid MARL growth alongside limited rigorous theory, making organization of theoretically guaranteed algorithms important for defining research boundaries and future directions.Theoretical foundations remain limited partly because single-agent deep RL is incompletely understood and multi-agent settings introduce inherent difficulties.Source: §1 · p. 3
• The chapter reviews MARL theories and algorithms with convergence or complexity guarantees across discrete-time Markov/stochastic and extensive-form games.Its coverage is selective rather than comprehensive and complements reviews focused on non-stationarity, deep MARL, or cooperative settings.Source: §1 · p. 3
• The chapter additionally discusses significant challenging applications and organizes its later sections around MARL background, theoretical challenges, algorithms, applications, conclusions, and open research directions.Source: §1 · pp. 3–4
• It highlights underexplored angles including extensive-form games, decentralized networked agents, mean-field MARL for huge populations, and policy-based methods’ (non-)convergence, especially in zero-sum games.The chapter also reviews partially observed MARL without relying on deep-RL heuristics.Source: §1 · p. 3

2.1 Single-Agent RL

• Single-agent RL models sequential decisions in an infinite-horizon discounted MDP tuple (S,A,P,R,γ), with RL learning policies from interaction rather than a known model.Value-based methods estimate Q-functions, whereas policy-based methods optimize parameterized policies; Q-learning converges under stated finite-space conditions, and policy-based methods offer convergence guarantees with neural approximators.Source: §2.1 · pp. 4–5, §2.1.1 · p. 5, §2.1.2 · p. 6

2.1.1 Value-Based Methods

• Value-based RL estimates state-action values and extracts greedy policies, with Q-learning convergence guarantees, deep Q-learning breakthroughs, SARSA convergence, MCTS search, and TD-based policy evaluation.MCTS builds search trees through Monte Carlo simulation, while TD and gradient-TD methods estimate values for specified policies.Source: §2.1.1 · pp. 5–6

2.1.2 Policy-Based Methods

• Policy-based RL directly optimizes parameterized policies through policy gradients and includes REINFORCE, actor-critic, PPO, TRPO, and soft actor-critic methods.Policy-based methods are described as having stronger convergence guarantees than value-based methods, especially with neural-network function approximation for massive or continuous spaces.Source: §2.1.2 · p. 6

2.2 Multi-Agent RL Framework

• MARL extends sequential decision-making to multiple agents whose joint actions influence system evolution and individual rewards, motivating Markov/stochastic games and extensive-form games.The two frameworks are illustrated as simultaneous-action Markov games versus alternating-action extensive-form games, with the latter representing imperfect information through nonsingleton information sets.Source: §2.2 · p. 7, Figure 1 · p. 7

2.2.1 Markov/Stochastic Games

• A Markov game generalizes an MDP with agent-specific rewards and joint actions, making each agent’s value depend on the joint policy and shifting the usual learning target toward Nash equilibrium.For finite-space infinite-horizon discounted games, Nash equilibria exist but need not be unique, and most MARL algorithms seek convergence to an equilibrium when one exists.Source: §2.2.1 · pp. 7–8

Cooperative Setting:

• Markov games encompass cooperative, competitive, and mixed settings: shared-reward teams can use coordinated single-agent methods, zero-sum games model adversarial or robust learning, and general-sum games allow unrestricted conflicts and alliances.Team-average rewards permit heterogeneous private rewards, preserve privacy, and motivate communication-efficient decentralized MARL; zero-sum equilibria optimize worst-case long-term reward.Source: Cooperative Setting · pp. 8–9, Competitive Setting · p. 9

Mixed Setting:

• General-sum MARL imposes no restriction on agent relationships, while team-based zero-sum games combine cooperation within teams with competition between them.Game-theoretic equilibrium concepts, especially Nash equilibrium, strongly influence algorithms for this mixed setting.Source: Mixed Setting · p. 9

2.2.2 Extensive-Form Games

• Markov games primarily model fully observed environments, whereas extensive-form games represent imperfect information by grouping indistinguishable histories into information sets.Under finite games with perfect recall, behavioral policies suffice for finding Nash equilibria, and extensive-form games admit polynomial-time algorithms under mild conditions.Source: §2.2.2 · pp. 9–10

3.1 Non-Unique Learning Goals

• MARL lacks a unique learning objective: analyses may target Nash equilibrium, stability and rationality, regret, communication, generalization, or robustness to faulty agents.Nash convergence may be unjustifiable under bounded rationality; no-regret learning instead protects agents from exploitation and can guarantee equilibrium convergence in certain games.Source: §3.1 · pp. 12–13

3.2 Non-Stationarity

• Concurrent learning makes each agent’s environment non-stationary, invalidating the stationary Markov assumptions underlying single-agent convergence analyses.Independent learners may fail to converge, although they can achieve satisfactory empirical performance.Source: §3.2 · p. 13

3.3 Scalability Issue

• MARL scalability is hindered by exponentially growing joint action spaces, while deep neural function approximation remains theoretically poorly understood.Factorized value or reward structures offer one possible remedy, with recent theory establishing convergence only for a special dependence structure.Source: §3.3 · p. 14

3.4 Various Information Structures

• MARL information structures range from centralized control to networked decentralization and full decentralization, with partial observability making opponents’ behavior difficult to infer.Centralized learning with decentralized execution simplifies cooperative analysis, whereas communication networks can enable convergence analyses between single-agent and general MARL difficulty.Source: §3.4 · pp. 14–16, Figure 2 · p. 15

Scope and organization

• The review categorizes theoretically studied MARL algorithms by task, focusing mainly on fully observed Markov games and extensive-form games.It also briefly covers cooperative Dec-POMDPs because their theory is more mature than that of general partially observed Markov games.Source: §4 · p. 16

4.1 Cooperative Setting

• Cooperative MARL focuses on agents collaborating to achieve a shared goal, with most theoretically analyzed algorithms targeting more specific cooperative settings.Source: §4.1 · p. 16

4.1.1 Homogeneous Agents

• Most cooperative settings use homogeneous agents with a common reward aligning their interests, while large populations make agents effectively interchangeable.Source: §4.1.1 · p. 16

Multi-Agent MDP & Markov Teams

• With identical rewards and finite state-action spaces, independent agents can apply joint-action Q-learning, which converges to the optimal or equilibrium Q-function.Source: Multi-Agent MDP & Markov Teams · p. 16
• Q-function convergence does not ensure equilibrium-policy convergence when equilibria are non-unique; policy convergence requires uniqueness or coordinated equilibrium selection.Optimal adaptive learning (OAL) learns the game structure, constructs weakly acyclic virtual games, and provably converges to the Nash equilibrium.Source: Multi-Agent MDP & Markov Teams · p. 17
• Scalability remains central because independent Q-learning may fail, motivating distributed Q-learning for deterministic finite MMDPs and theory on value factorization and structured local policies.A decentralized algorithm using only states, local actions, and rewards converges to team-optimal equilibrium policies, avoiding potentially arbitrarily worse suboptimal equilibria [38].Source: Multi-Agent MDP & Markov Teams · p. 17
• The only stated policy-based convergence guarantee uses two-timescale actor-critic fictitious play, with slower actor updates and faster critic evaluation.Source: Multi-Agent MDP & Markov Teams · p. 17
• This policy-based method converges for simultaneous-move multistage games with common rewards, including a special Markov team with initial and absorbing states where each state is visited once.Source: Multi-Agent MDP & Markov Teams · p. 18

Markov Potential Games

• Markov potential games (MPGs) extend potential games to sequential decision-making, with state evolution affected by joint actions and unilateral policy changes aligned with changes in a shared potential function.MMDPs/Markov teams are a special case in which the potential function is the common reward.Source: Markov Potential Games · p. 18
• [93] gives verifiable conditions for a Markov game to be an MPG and establishes that finding closed-loop Nash equilibria is equivalent to solving a single-agent optimal control problem.This equivalence enables single-agent RL algorithms to solve the corresponding MARL problem.Source: Markov Potential Games · p. 18

Mean-Field Regime

• Mean-field models consider extremely large populations of homogeneous agents whose individual effects vanish, so each agent responds to an aggregate state or action quantity.This framework includes mean-field games, mean-field-sharing teams, and games with mean-field actions.Source: Mean-Field Regime · p. 18
• In cooperative mean-field teams, agents share a reward depending on local state and the finite-population empirical state average, unlike MFGs’ infinite-population expectation or distribution.The cooperative model encourages coordination, while mean-field games are primarily noncooperative and use equilibrium rather than optimum as their solution concept [176].Source: Mean-Field Regime · p. 18
• Several standard reinforcement-learning algorithms can be adapted to cooperative Markov teams with mean-field sharing.The adaptation follows the specified model’s dynamic-programming decomposition.Source: Mean-Field Regime · pp. 18–19
• Policy gradients converge for linear-quadratic mean-field control, while mean-field Q-learning converges for general mean-field control models [177] [178].These results target large populations of cooperative decision-makers through the mean-field control formulation.Source: Mean-Field Regime · p. 19

Problem setting

• Heterogeneous cooperative agents may have private reward functions while jointly maximizing the team-average reward, creating a setting relevant to sensor networks, smart grids, intelligent transportation, and robotics.The team-average reward is defined as the average of agents’ individual rewards.Source: §4.1.2 · p. 19

Coordination challenge

• Without access to other agents’ rewards, agents cannot locally estimate the global value function, making this setting more coordination-intensive than the homogeneous case.Source: §4.1.2 · p. 19

Decentralized paradigm

• A central controller would enable existing centralized MARL algorithms by collecting and averaging rewards and distributing information, but cost, scalability, and robustness concerns often preclude one.Source: §4.1.2 · p. 19
• Instead, agents exchange information with neighbors over sparse, possibly time-varying communication networks, although decentralized MARL remains less investigated than distributed optimization without dynamics or long-term sequential objectives.Source: §4.1.2 · p. 19

Decentralized Q-learning

• QD-learning combines consensus and innovation with standard Q-learning and converges to the optimal tabular Q-function under suitable stepsize conditions.The innovation term captures differences between neighboring agents’ Q-value estimates.Source: Learning Optimal Policy · pp. 19–20

Decentralized actor-critic

• Decentralized actor-critic methods achieve almost sure convergence with linear value approximation, while extensions cover continuous spaces, on-policy variance reduction, and off-policy critics or consensus actors.These methods use consensus-based TD critics and stochastic policy-gradient actor updates; related guarantees are also established for continuous-space and off-policy settings.Source: Learning Optimal Policy · p. 20

Multi-task learning

• In multi-task settings, distributed actor-critic algorithms drive the gradient of the average return to zero, while Diff-DAC interprets actor-critic updates as dual ascent for a linear program.Agents use local TD critics and consensus-based actor updates based on neighbor-exchanged information.Source: Learning Optimal Policy · p. 21

Finite-sample analysis

• Existing convergence guarantees are asymptotic and largely limited to linear approximation, motivating decentralized fitted-Q iterations that analyze finite-sample accuracy with nonlinear function classes.The analysis relates output accuracy to the function class, per-iteration sample size, and number of iterations, while accounting for incomplete consensus and nonlinear approximation error.Source: Learning Optimal Policy · pp. 21–22

Policy Evaluation

• With a fixed joint policy and linear value approximation, policy evaluation has stationary sampling and a convex objective, enabling finite-time analyses unlike most control algorithms.The common objective is the mean square projected Bellman error for the team-average reward.Source: Policy Evaluation · p. 22
• Sample-based MSPBE minimization can be reformulated as a distributed saddle-point problem that is convex in value parameters and concave in dual variables.The formulation uses empirical estimates of transition, feature-covariance, and reward-feature quantities; H-truncated λ-weighted MSPBE can reduce bias relative to the mean square Bellman error minimizer [204].Source: Policy Evaluation · p. 23
• Distributed policy-evaluation algorithms include gradient-TD with asymptotic ODE convergence, double averaging with linear rate, and variance-reduced AVRG methods with linear rate and reduced synchronization or memory requirements [204].The AVRG method additionally supports eligibility traces and does not require synchronization in sampling [204].Source: Policy Evaluation · p. 23
• Distributed TD(0) and TD(λ) provide finite-sample guarantees, with TD(λ) requiring neither projection of iterates nor i.i.d. noise assumptions [95, 157].Distributed TD(0) uses projection and i.i.d. samples, whereas the more general TD(λ) analysis removes both requirements [157].Source: Policy Evaluation · p. 23
• For independent agents interacting with independent MDPs, off-policy diffusion GTD achieves mean-square convergence at a sublinear rate, while GTD2 and TDC have weak convergence over time-varying communication networks.The lack of coupling means agents need not know other agents’ actions.Source: Policy Evaluation · pp. 23–24

Consensus learning

• Networked-agent MARL studies optimal consensus, minimizing agents’ joint-policy consensus error while tracking neighbors’ and a leader’s states; related work uses cooperative graphical games and centralized-critic-decentralized-actor off-policy RL.[213] combines policy iteration with a neural-network actor-critic algorithm, while adopts a similar consensus-error objective.Source: Other Learning Goals · p. 24

Communication efficiency

• Communication-efficient methods reduce information exchange through triggered policy-gradient communication, unidirectional mixing matrices, or transmitting one scalar state entry per iteration while retaining provable convergence [130].LAPG reduces rounds with communication-trigger rules; hierarchical policy evaluation enables unidirectional exchange; distributed actor-critic preserves convergence while sending only one scalar state-vector entry each iteration.Source: Other Learning Goals · p. 24

Problem setting

• Dec-POMDPs are theoretically difficult because agents observe only local information, cannot maintain a global belief state, and require super-exponential worst-case solution time.Dec-POMDPs share the reward and transition structure of Markov team models but restrict each agent to local observations; their solution is NEXP-complete.Source: §4.1.3 · p. 24

Centralized learning and execution

• Most Dec-POMDP algorithms use centralized learning with decentralized execution, reformulating the problem so a central controller can optimize policies from all agents’ observation data.Finite-state controllers commonly map local observation histories to actions, and Bayesian nonparametric methods can determine variable-size controller sizes.Source: §4.1.3 · pp. 24–25

Centralized reformulations

• Centralized solution methods convert Dec-POMDPs to NOMDPs or occupancy-state MDPs, enabling heuristic search, tractable planning, and value-based learning through piece-wise linear and convex value functions.Occupancy states represent distributions over hidden states and joint observation histories.Source: §4.1.3 · p. 25

Sampling and policy-gradient methods

• Sampling-based approaches improve computational efficiency through Monte Carlo policy iteration, expectation-maximization, and Monte Carlo tree search, while centralized-critic policy gradients admit finite-sample analysis in tabular settings.Tree search has been applied to multi-agent POMDPs and multi-robot active perception.Source: §4.1.3 · p. 25

Decentralized learning

• Decentralized learning can exploit shared observations by reformulating Dec-POMDPs as centralized POMDPs, approximating them with finite-state MDPs, or applying tree search, with common randomness avoiding inter-agent communication.The finite-state MDP approximation has exponentially decreasing error, while the tree-search approach provides a more theoretically grounded counterpart to direct Dec-POMDP heuristics.Source: §4.1.3 · p. 25

4.2 Competitive Setting

• Two-player zero-sum games dominate competitive MARL research because even three-player matrix games are PPAD-complete, and the reviewed methods seek Nash equilibria in Markov or extensive-form games.The methods are categorized into value-based and policy-based approaches.Source: §4.2 · pp. 25–26

4.2.1 Value-Based Methods

• Value iteration uniquely converges to the Bellman fixed point V ∗ at a linear rate, from which a Nash equilibrium is constructed using optimal matrix-game policies.The contraction guarantee gives ∥Vt+1 − V ∗∥∞ ≤ γt+1 · ∥V0 − V ∗∥∞.Source: §4.2.1 · pp. 26–27
• Value-based learning extends from model-based iteration to minimax-Q and batch methods, with convergence established in tabular and LQ settings but remaining poorly understood for general linear function approximation.Finite-sample Q-function bounds and sublinear-regret guarantees for UCSG further address turn-based and average-reward settings, while imperfect-information methods are efficient only at small scale.Source: §4.2.1 · pp. 27–29

4.2.2 Policy-Based Methods

• Policy-based self-play converts no-regret learning into approximate Nash convergence: Hannan-consistent players with average regret at most ϵ achieve a 2ϵ-approximate equilibrium, while fictitious-play variants and CFR provide broader guarantees.Continuous-time or modified fictitious play is Hannan consistent; CFR yields an O(1/T)-approximate Nash equilibrium after T steps, and actor-critic methods can be formulated as CFR methods.Source: §4.2.2 · pp. 29–33
• Vanilla GDA can fail to converge to local Nash equilibria through limit cycling or non-Nash stable limit points, motivating consensus, symplectic, and extragradient methods [308] [305].Curvature-exploiting updates ensure all stable limit points are local Nash equilibria [308] [305].Source: §4.2.2 · pp. 34–35
• For Stackelberg equilibria, GDA converges to local minimax points under mild conditions [33], while two-timescale and nested-gradient methods converge to Stackelberg or stationary minimax solutions [311] [313] [314].Nested gradient descent achieves a sublinear rate under gradient dominance [313] [314].Source: §4.2.2 · p. 35
• Because global smoothness assumptions are restrictive and fail for LQ games, projected nested policy gradients achieve global NE convergence in LQ settings, later removing projection [100] and improving results independently [306].The LQ result is presented as the first of its kind in MARL, with convergence rates established.Source: §4.2.2 · p. 35

4.3 Mixed Setting

• Mixed-setting MARL is notoriously challenging: Nash equilibrium is PPAD-complete in two-player general-sum normal-form games, while value iteration and vanilla policy gradients can fail [32] [315].These negative results motivate exploiting additional structure in either the games or the algorithms to obtain provably convergent methods.Source: §4.3 · p. 35

Value-Based Methods

• Value-based methods achieve equilibrium guarantees under restrictive assumptions, including unique stage-game equilibria, weak acyclicity, special two-player structures, or finite-sample Bellman-residue analyses [44].Nash-Q, Friend-or-Foe Q-learning, correlated Q-learning, batch RL, decentralized FQI, and decentralized two-timescale Q-learning cover increasingly structured mixed settings.Source: Value-Based Methods · pp. 35–36

Policy-Based Methods

• For continuous games, convergence results cover Morse-Smale, potential, Hamiltonian, zero-sum, and Stackelberg structures, but most guarantees are local rather than global [32] [322] [311].Source: Policy-Based Methods · p. 37

Mean-Field Regime

• Mean-field methods improve scalability by replacing other agents’ actions with empirical averages, while mean-field-game algorithms iteratively solve policies and update population distributions toward equilibrium [172, 324, 325, 326, 327].Earlier methods focus on finite-horizon or stationary equilibria, whereas recent work addresses possibly non-stationary infinite-horizon equilibria and develops computation algorithms supporting future model-free RL [328] [329] [331] [332].Source: Mean-Field Regime · pp. 37–38

Unmanned Aerial Vehicles

• MARL supports decentralized cooperative UAV teams despite time-varying communication links, with applications including link selection, field coverage, spectrum sharing, and collision-free target assignment.Methods include independent or distributed Q-learning and MADDPG with centralized learning and decentralized execution.Source: Unmanned Aerial Vehicles · pp. 39–40

Learning to Communicate

• In partially observed cooperative tasks, agents learn communication through recurrent representations and centralized training, with deep Q-learning and neural architectures producing emergent communication protocols [343] [347] [350] [351] [352] [353] [354].Noisy observations make communication useful for inferring the underlying state and maximizing shared returns; RNNs, LSTMs, weight sharing, and attention address growing histories and computational cost.Source: Learning to Communicate · pp. 40–41

5.2 Competitive Setting

• Competitive MARL applications center on Go and Texas hold’em poker as perfect-information and incomplete-information extensive-form games, respectively.Both settings require methods that cope with enormous state or information-set spaces and delayed terminal payoffs.Source: §5.2 · p. 41, The Game of Go · p. 42, Texas Hold’em Poker · p. 44

The Game of Go

• AlphaGo defeated a human professional on full-sized Go by combining CNN policy and value networks with supervised learning, reinforcement learning, self-play, and MCTS.AlphaGo Zero removed human initialization, trained a shared policy-value network solely through reinforcement learning and self-play, defeated earlier AlphaGo versions, and inspired AlphaZero for chess, shogi, and Go.Source: The Game of Go · pp. 42–43

Texas Hold’em Poker

• 6-player no-limit Texas hold’em was mastered by Pluribus, which exceeded top human professionals using abstraction, subgame decomposition, Monte-Carlo CFR, self-play, and depth-limited search.Earlier breakthroughs solved heads-up limit hold’em with CFR+ [361], while DeepStack and Libratus first defeated professionals in heads-up no-limit hold’em despite more than 6×10^161 information sets.Source: Texas Hold’em Poker · pp. 44–45

Other Applications

• AlphaStar achieved superhuman performance in full-game, zero-sum two-player StarCraft II by combining LSTM policy and value representations, asynchronous actor-critic updates, and Neural Fictitious Self-Play.The game remains challenging because agents act under partial observation, uncertainty, long-term strategic requirements, and difficult reward design.Source: Other Applications · p. 45

5.3 Mixed Settings

• Mixed-setting MARL is less explored and includes six-player poker, social dilemmas, and team-based zero-sum games that require cooperation within teams and competition between them.Social-dilemma methods commonly use RNNs or LSTMs to represent partial histories, with performance typically demonstrated experimentally [371].Source: §5.3 · p. 45
• OpenAI Five achieved superhuman Dota 2 performance and defeated human world champions using LSTM representations, PPO, self-play, and team-spirit reward shaping.The team-spirit hyperparameter balances each hero’s individual reward against the team-average reward without explicit inter-team communication channels.Source: §5.3 · p. 46

Scope and contribution

• The chapter presents a selective, rather than comprehensive, theory-focused overview organized around fully cooperative, fully competitive, and mixed tasks, while highlighting new taxonomies and future research directions.Its scope is explicitly shaped by the authors’ interests and expertise.Source: §6 · p. 46

Partially observed settings

• Partial observability makes MARL difficult because optimal POSG decisions may require beliefs over states and opponents’ policies, with heterogeneous beliefs arising from agents’ observations.Even cooperative Dec-POMDPs are NEXP-complete; centralized-learning-decentralized-execution is suggested as a starting point for POSGs.Source: §6 · pp. 46–47

Deep MARL theory

• Deep MARL theory should extend recent convergence analyses for overparameterized neural networks from single-agent neural TD learning and policy optimization to multi-agent settings.DNNs underpin most recent empirical MARL successes [25] [27], but their theoretical foundations remain insufficiently developed.Source: §6 · p. 47

Model-based MARL

• Model-based MARL remains underdeveloped, motivating extensions of optimism-based results to improve sample efficiency, especially given provable advantages of model-based RL in some regimes [378].Existing examples include single-controller stochastic games and R-MAX for zero-sum Markov games.Source: §6 · p. 47

Convergence of policy gradient methods

• Vanilla policy gradients can avoid even local Nash equilibria in general MARL, so convergence should be explored beginning with general-sum linear-quadratic games and informed by nonconvex-(non)concave optimization.Proposed stabilization assumptions [312, 321, 322, 311] may be difficult to verify because they depend on both the model and policy parameterization, even in simple LQ settings [315].Source: §6 · p. 47

MARL with robustness/safety concerns

• Robustness and safety are largely uncharted in MARL, where safety constraints must couple agents’ behavior and robustness may require protection against anonymous adversarial disturbances.Provable guarantees are important for safety-critical applications such as autonomous driving [9] and robotics, while Byzantine-robust distributed learning [383] may provide useful ideas.Source: §6 · pp. 47–48