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 faces non-stationary dynamics as agents concurrently improve their policies. This monograph frames MARL around game theory, concluding that combining game theory with deep reinforcement learning can scale algorithms to complex multiagent systems and achieve superhuman performance.

  • Problem

    Concurrent policy improvement makes the environment non-stationary from each agent’s perspective, complicating learning.

    Source: §4.3 · p. 52

  • Method

    The monograph frames MARL through game theory, emphasizing equilibria and interactions between agents.

    Source: §1.2 · p. 14

  • Results

    The monograph concludes that combining game theory with deep reinforcement learning can scale MARL algorithms to complex multiagent systems and achieve superhuman performance.

    Source: §1.2 · p. 14

  • Takeaways & Limitations

    Understanding equilibria and interactions between agents is important for MARL.

    Source: §1.2 · p. 14

    Finding Nash equilibria is computationally demanding; even in two-player games, it is PPAD-hard and may take exponential time in the worst case.

    Source: Solution Concept–Nash Equilibrium · p. 28

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 supplied text lists the monograph’s authors.

Table des matières

  • The monograph lists Yaodong Yang, Chengdong Ma, Zihan Ding, Stephen McAleer, Chi Jin, Jun Wang, and Tuomas Sandholm as authors.It is dated 2025.Source: Table des matières · p. 5

Introduction

Reinforcement learning trains agents through interaction and rewards to pursue long-term goals, while multiagent settings add strategic interaction and non-stationarity. The monograph surveys MARL’s game-theoretic foundations and recent advances, emphasizing equilibria, convergence, and applications to complex games.

1.1 Deep Reinforcement Learning

  • RL agents learn through trial and error to maximize cumulative reward, requiring decisions that account for future consequences rather than immediate action value.Unlike supervised learning, RL learns without labeled data, and successful actions are reinforced in the agent’s behavior.Source: §1.1 · pp. 7–9
  • Deep Q-learning (DQN) used neural networks for approximate dynamic programming and achieved human-level Atari performance; AlphaGo later defeated top professional Go players (Silver et al., 2016, 2017a, 2018).Earlier Q-learning was limited by the curse of dimensionality, while DQN demonstrated human-level performance on 49 Atari games.Source: §1.1 · pp. 9–10

1.2 Multiagent Reinforcement Learning

  • MARL extends RL to interacting agents that learn their own policies while adapting to others, making non-stationarity and scalability central challenges.Early work introduced Minimax Q-learning for zero-sum games and Nash Q-learning for general-sum settings; convergence with multiple equilibria remained difficult.Source: §1.2 · pp. 10–12
  • Game theory supplies equilibrium concepts for analyzing agent interactions and designing MARL algorithms with theoretical properties and convergence guarantees.The monograph presents a game-theoretic assessment of modern MARL, with equilibrium understanding central to developing algorithms for complex systems.Source: §1.2 · pp. 12–14
  • MARL achieved grandmaster-level StarCraft II performance, superhuman Dota2 performance, and human-level capture-the-flag and hide-and-seek performance (Baker et al., 2019a).The capture-the-flag and hide-and-seek studies also reported emergent behaviors grounded in physical theory and understandable to humans.Source: §1.2 · pp. 13–14
  • DeepStack and Libratus beat professional poker players, and Libratus’s successor Pluribus won over one million dollars from five elite professionals (Moravcik et al., 2017; Brown and Sandholm, 2018, 2019).The passage notes that heads-up no-limit hold’em has more than 6×10^161 information states.Source: §1.2 · p. 14
  • Neural Replicator Dynamics reached expert-level Stratego performance, Cicero achieved human-level press Diplomacy performance, and game-theoretic MARL has been applied to LLM security and preference alignment.Cicero combined game-theoretic MARL with large language models (FAIR)† et al. (2022); LLM applications include red-team/blue-team security detection (Ma et al., 2023) and human-preference alignment (Wang et al., 2024).Source: §1.2 · p. 14

Single-Agent RL

Single-agent RL frames an agent’s trial-and-error search for a long-term reward-maximizing policy as an MDP. The section defines this formulation, justifies expected-reward maximization, and outlines occupancy-measure, value-based, and policy-based approaches to solving MDPs.

2.1 Problem Formulation: Markov Decision Process

  • An MDP is the tuple ⟨S, A, P, R, γ⟩: states and actions, state-transition probabilities, rewards for transitions, and a discount factor.At each step, the agent observes a state, acts, transitions, and receives a reward; its objective is to maximize discounted cumulative reward.Source: §2.1 · p. 15

2.2. Justification of Reward Maximisation

  • The von Neumann-Morgenstern utility theorem makes expected-reward maximization equivalent to rational preference under its necessary and sufficient conditions (Von Neumann and Morgenstern (2007)).Expected utility theory models rational choice as maximizing expected value (Schoemaker (2013)).Source: §2.2 · p. 17

2.2 Justification of Reward Maximisation

  • Rationality assumptions can fail for real decision-makers (Gigerenzer and Selten (2002)), while multi-objective MDP objectives can be scalarized into a single-objective MDP through a two-timescale process (Roijers et al. (2013)).Source: §2.2 · p. 17

2.3 Solving Markov Decision Processes

  • Occupancy measures encode discounted state-action visits and make MDP solving expressible as a linear program, but large or continuous spaces limit this approach.Classical policy and value iteration also require the exact transition and reward models; RL instead learns through interaction and trial and error.Source: §2.3 · pp. 17–18

Value-Based Methods

  • Q-learning estimates the optimal Q-function with temporal-difference updates, and converges under finite discrete state-action spaces when every pair is visited infinitely often.Munos and Szepesvári (2008) extended the analysis with a high-probability error bound for infinite state spaces using finitely many samples; DQN uses neural networks, replay-buffer samples, and a slowly updated target network.Source: §2.3 · p. 19

2.3. Solving Markov Decision Processes

  • Q-learning derives a greedy optimal policy from the optimal Q-function and uses temporal-difference learning to update its estimate.The Bellman optimality operator is a contraction with the optimal Q-function as its unique fixed point.Source: §2.3 · p. 19

Policy-Based Methods

  • Policy-based methods optimize a parameterized policy directly, while the policy-gradient theorem gives an analytical gradient that avoids dependence on the unknown effects of policy changes on state distributions.For deterministic policies with continuous actions, the deterministic policy-gradient theorem applies (Silver et al. (2014)).Source: Policy-Based Methods · p. 20
  • Policy-gradient methods include REINFORCE, which estimates Q with sampled returns, and actor-critic methods, which use a learned critic; variants include trust-region, soft actor-critic, and DDPG methods.The critic approximates Q and is updated via temporal-difference learning.Source: Policy-Based Methods · p. 20

Multi-Agent RL

This section surveys game-theoretic foundations for multi-agent reinforcement learning, framing agent interactions through stochastic and sequential games. It covers game formulations and information structures, sequence-form representations, and methods for analyzing or computing equilibria in perfect- and imperfect-information settings.

3.1.1 Problem Formulation

  • A stochastic game extends an MDP: agents act simultaneously, their joint action determines the next-state transition, and each agent receives a reward for that transition.Each agent seeks a policy that maximizes discounted cumulative reward, but its optimal policy depends on the other agents’ policies.Source: §3.1.1 · pp. 22–23

3.1.2 Solving Stochastic Games

  • Because agents’ selfish actions can produce unsafe outcomes, solving stochastic games requires strategic policies that account for others; general cases usually require nonlinear programming, with LP formulations for two special cases.The LP cases are single-controller games and separable-reward, state-independent-transition (SR-SIT) games.Source: §3.1.2 · p. 24

Value-Based MARL Methods

  • Value-based MARL retains the Q-learning update but replaces the single-agent maximum with equilibrium evaluation and solution across agents’ Q-functions.The evaluation operator gives an agent’s expected long-term reward at an equilibrium, while the solution operator returns its equilibrium policy component.Source: Value-Based MARL Methods · pp. 24–25

Policy-Based MARL Methods

  • Policy-based MARL uses function approximation to learn each agent’s policy; multiagent policy gradients extend the policy gradient theorem, and MADDPG addresses continuous actions with deterministic policies.The joint-policy expectation requires observing other agents’ policies, a potentially strong real-world assumption.Source: Policy-Based MARL Methods · p. 25

Solution Concept–Nash Equilibrium

  • A Markov perfect Nash equilibrium requires no agent to improve its value by deviating at any state; mixed-strategy equilibria exist for discounted and average-reward stochastic games, though they may not be unique.Checking equilibrium uniqueness is NP-hard.Source: Solution Concept–Nash Equilibrium · pp. 26–27
  • Two-player general-sum Nash equilibrium finding is PPAD-hard, while pure-strategy equilibrium existence in stochastic games is PSPACE-hard and finite-horizon calculation is NP-hard.The best known polynomial-time approximation cited for bimatrix games achieves ϵ = 0.3393.Source: Solution Concept–Nash Equilibrium · pp. 28–29

3.1.3 Special Types of Stochastic Games

  • Special stochastic games are studied for tractable solution concepts: normal-form games have one state, while identical-interest games share an objective and permit decentralized single-agent RL.The identical-interest description states that agents can independently choose actions maximizing their own reward.Source: §3.1.3 · pp. 29, 31
  • Team games assume homogeneous, interchangeable agents with the same reward function, whereas team-average-reward games allow different rewards but share an objective.Source: §3.1.3 · p. 31
  • Potential games guarantee pure-strategy NE and reduce to team games when reward equals potential; zero-sum equilibria can be solved by linear programming.The text also notes that zero-sum optimization is against a worst-case scenario.Source: §3.1.3 · p. 31
  • LQ games combine linear dynamics with quadratic rewards, and actor-critic methods can converge to NE in zero-sum LQ games (Al-Tamimi et al. (2007)).In multi-player general-sum LQ games, agents’ rewards need not sum to zero.Source: §3.1.3 · pp. 32–33

3.1.4 Partially Observable Settings

  • Even the simplest two-player cooperative finite-horizon POSG is NEXP-hard, while weakly-revealing POSGs admit polynomial sample-complexity learning and CTDE methods have empirical successes.The text also notes that deep neural networks combined with centralized training and decentralized execution hold promise.Source: §3.1.4 · p. 34

3.2.1 Problem Formulation

  • EFGs model alternating moves with game trees and information sets for indistinguishable histories; sequence-form EFGs are polynomial-time LP-solvable, unlike intractable Dec-POMDPs.Perfect-information EFGs are the special case in which each information set is a singleton.Source: §3.2.1 · pp. 35–36
  • Steering no-regret agents is impossible with finite total mediator budgets, but vanishing average payments can enable it; constant payments depend on what players’ strategies reveal.Constant per-round payments permit steering when full strategies are observable, but are generally infeasible in EFGs when only trajectories are observed; normal-form games or growing per-round budgets can allow steering with vanishing average payments (Zhang et al. (2023a,b)).Source: §3.2.1 · p. 38

3.2.2 Normal-Form Representation

  • Imperfect-information EFGs can be transformed into equivalent NFGs preserving equilibria, but the resulting large payoff matrices limit scalability and motivate direct sequence-form methods.The induced NFG can be solved with the Lemke-Howson algorithm.Source: §3.2.2 · p. 39

3.2.3 Sequence-Form Representation

  • Sequence form represents an extensive-form game with size linear in game states rather than exponential in information states, enabling polynomial-time solutions.In Kuhn poker, its payoff tensor has 30 terminal-node entries versus 64×64×32 in normal form. Under perfect recall, behavioral and mixed strategies induce the same outcome probabilities, so restricting to behavioral strategies leaves the Nash equilibria unchanged.Source: §3.2.3 · pp. 40, 42

3.2.4 Solving Extensive-Form Games

  • An extensive-form Nash equilibrium requires each agent’s policy to maximize expected reward against the other agents’ equilibrium policies.The expected reward sums over terminal nodes reached under the joint policy.Source: §3.2.4 · p. 43

Perfect-Information Games

  • In perfect-information games, subgame-perfect equilibrium rules out non-credible threats, and backward induction finds an equilibrium by depth-first search in time linear in the game tree.For two-player zero-sum games, alpha-beta pruning can avoid subtrees that will not be reached in equilibrium; deep-tree search may instead use approximate values at a cutoff depth (Shoham and Leyton-Brown, 2008, Chapter 5.1; Silver et al., 2016).Source: Perfect-Information Games · p. 44
  • Finding all Nash equilibria in a two-player perfect-information extensive-form game requires O(|T|^3), while backward induction identifies only one equilibrium (Shoham and Leyton-Brown, 2008, Theorem 5.1.6).Every finite perfect-information game has a pure-strategy Nash equilibrium.Source: Perfect-Information Games · pp. 43–44

Imperfect-Information Games

  • Sequence-form linear programs solve two-player zero-sum imperfect-information games in polynomial time, whereas transforming them to normal form makes the representation exponential in the original game size.For two-player general-sum games, the formulation becomes an LCP solvable by generalized Lemke-Howson, without a polynomial-time worst-case guarantee but exponentially faster than its normal-form counterpart.Source: Imperfect-Information Games · pp. 46–47
  • Recent model-free and balanced online-learning methods improve sample-complexity bounds for learning Nash equilibria in zero-sum imperfect-information games.IXOMD achieves high-probability convergence O(1/√T); BOMD and B-CFR attain Õ((XA + YB)/ϵ²), matching the information-theoretic lower bound up to logarithmic factors. Balanced FTRL matches a problem-independent lower bound with prior information-set structure, while Adaptive FTRL achieves Õ(H²(AX + BY)/ϵ²).Source: Imperfect-Information Games · p. 47
  • Communication and certification equilibria have polynomial-time optimality computation in extensive-form games, but computing an optimal extensive-form correlated equilibrium is NP-hard (Zhang and Sandholm, 2020; Zhang and Sandholm, 2022; Zhang et al., 2022a).The mediator-augmented framework includes full-certification equilibria, where players cannot lie about information but may remain silent.Source: Imperfect-Information Games · p. 48

Grand Challenges of MARL

MARL faces three linked grand challenges: combinatorial complexity, multidimensional learning objectives, and non-stationarity. Together, they leave general-sum learning with more than two agents an open challenge.

4.1 Combinatorial Complexity

  • Joint action spaces grow exponentially with agent count, while Nash equilibrium computation is PPAD-hard even in two-player games.Factorized structures can simplify computation, but graphical-game results are limited in scope, and neural Q-decomposition methods are generally team-game-specific with unresolved theoretical questions.Source: §4.1 · pp. 49–50

4.2 Multi-Dimensional Learning Objectives

  • MARL objectives include rationality and convergence: best response to stationary opponents and learning dynamics that reach a stable policy, respectively.Their joint attainment yields a Nash equilibrium; when rationality or tractability is limited, alternatives include recursive reasoning, mean-field, evolutionary stable, Stackelberg, and robust equilibria.Source: §4.2 · pp. 50–51

4.2. Multi-Dimensional Learning Objectives

  • Most MARL algorithms target Nash equilibrium, but convergence guarantees are often absent, depend on strong assumptions, or fail altogether.Value iteration in general-sum stochastic games may instead converge to cyclic equilibria; no-regret is another proposed convergence criterion, while gradient-descent-ascent can reach Stackelberg or local differential equilibria rather than general Nash equilibrium.Source: §4.2 · p. 51
  • Building convergent MARL objectives with deep neural networks remains uncharted, alongside limited study of global convergence for single-agent deep RL methods.Source: §4.2 · pp. 51–52

4.3 The Challenges of Non-Stationarity and Adaptive Opponents

  • Concurrent policy improvement makes each agent’s environment non-stationary, undermining Markovian assumptions and potentially causing non-convergence.Replay buffers worsen the issue because sampled opponent actions may poorly represent policies and become outdated as those policies change.Source: §4.3 · p. 52

4.4. Scalability Issue when N ≫2

  • In competitive games, adaptive opponents can exploit policy weaknesses, forcing agents to anticipate changing strategies and making learning unstable or even divergent.Source: §4.4 · p. 53

4.4 Scalability Issue when N ≫2

  • Most MARL algorithms solve only two-player games, especially zero-sum games; general-sum problems with more than two agents remain open.Progress requires game-theoretic solution concepts, convergent RL algorithms, and expressive deep-learning function approximators.Source: §4.4 · p. 53

A Survey of MARL Surveys

The section situates MARL surveys within a field too broad for a single review, then introduces a taxonomy organized around problems, information assumptions, learning paradigms, and research agendas. It selectively reviews MARL algorithms, emphasizing theoretical guarantees over empirical-only or application-specific work.

5.1 Taxonomy of MARL Algorithms

  • MARL taxonomies are driven chiefly by problem type, because agents face multiple learning objectives; choosing the right problem is itself a research problem.This contrasts with single-agent RL taxonomies, which are mainly organized by solution type.Source: §5.1 · pp. 55–56
  • Stage-game type, repetition or state-linked sequences, and local-knowledge assumptions distinguish MARL problems, while general-sum stochastic games are at least PSPACE-hard and provable convergence guarantees are scarce without strong assumptions.Stage games include team or potential, zero-sum or harmonic, and general-sum games; local knowledge ranges from observed rewards and actions to knowledge of other agents’ policies or equilibria.Source: §5.1 · pp. 56–57
  • Six learning paradigms range from independent decentralized policies to central control, centralized training with decentralized execution, and networked communication during training.Other paradigms allow shared policies across all agents or within a group; Figure 5.1 summarizes the six configurations.Source: §5.1 · pp. 57–58, Figure 5.1 · p. 58
  • The taxonomy incorporates five coherent AI agendas proposed by Shoham et al. (2007) and Sandholm (2007), each with a distinct motivation and success criterion.The following review is organized around these agendas and examines game-theoretic models in cooperative and noncooperative settings, with emphasis on equilibrium learning.Source: §5.1 · pp. 58, 60, Table 5.1 · p. 59

5.2 A Survey of Surveys

  • Because no single survey can cover all ways of categorizing MARL, the section reviews surveys spanning machine learning and RL perspectives before turning to algorithms.Stone and Veloso (2000) organized early MAS work by agent homogeneity and communication; Shoham et al. (2007) proposed five research agendas, while Stone (2007) and Tuyls and Weiss (2012) argued for broader conceptual scope.Source: §5.2 · p. 60
  • Existing surveys cover cooperative, competitive, and general-sum MARL, connect its dynamics to evolutionary game theory, and classify methods by opponent modelling or knowledge transfer.Buşoniu et al. (2010) presented a comprehensive survey of value-iteration and policy-search methods; Tuyls and Nowé (2005) and Bloembergen et al. (2015) examined links with evolutionary game theory; other reviews focused on non-stationarity and transfer learning.Source: §5.2 · pp. 61–62
  • Recent surveys address deep MARL challenges and applications, while Zhang et al. (2019b) selectively review methods with theoretical guarantees and complexity analysis, including networked, mean-field, and stochastic-potential-game MARL.Other deep MARL reviews focus on fully cooperative games or on incorporating traditional MAS ideas such as emergent behaviour, communication, and opponent modelling.Source: §5.2 · p. 62

Learning in Identical-Interest Games

Identical-interest learning ranges from team games with shared rewards to decentralized and stochastic settings, where coordination, tractability, and equilibrium selection shape the available methods. The section also describes probabilistic and potential-game approaches to modeling multiagent learning.

6.1 Stochastic Team Games

  • In identical-interest games, homogeneous agents share symmetric payoffs; in team games, identical rewards let agents apply single-agent RL over the joint action space.The agents’ Q-functions are identical in this setting.Source: Learning in Identical-Interest Games · p. 63, §6.1 · p. 63
  • Independent Q-learning may fail to converge in team games, while deterministic transitions permit a convergence guarantee; equilibrium selection can still yield suboptimal policies.OAL addresses selection by eliminating joint actions with suboptimal Nash-equilibrium values and applying adaptive play; later decentralized Q-learning methods provide convergence guarantees for weakly acyclic stochastic games.Source: §6.1 · pp. 63–64, Solutions via Q-function Factorisation · p. 64

Solutions via Q-function Factorisation

  • Q-function factorization and coordination graphs can reduce joint-action search, while VDN, QMIX, and QTRAN impose structural constraints that Q-DPP avoids.Q-DPP uses a determinantal point process to promote diverse behaviors and naturally decompose the joint Q-function; the cited methods rely on specially designed architectures and can impair exploration.Source: §6.1 · pp. 65–66

Solutions via Multiagent Soft Learning

  • Multiagent soft learning casts policy search as probabilistic inference, adds entropy to the objective, and provides a framework for modeling bounded rationality.PR2 and ROMMEO (Tian et al., 2019) use recursive reasoning models to represent how agents account for others’ actions.Source: §6.1 · pp. 67–68

6.2. Dec-POMDPs

  • GR2 models agents reasoning at different hierarchy levels, with higher-level agents best responding to lower-level agents; practical multiagent soft actor-critic methods make large-K reasoning tractable.The cited methods are described as having a convergence guarantee.Source: §6.1 · p. 68, §6.2 · p. 69

6.2 Dec-POMDPs

  • Dec-POMDPs are NEXP-complete, and occupancy-state MDP methods guarantee near-optimal plans almost surely for finite problems, unlike RL methods that may reach only local optima.The occupancy state represents a distribution over hidden states and joint observation-action histories; the resulting value functions are piece-wise linear and convex.Source: §6.2 · pp. 69–70

6.3. Networked Multiagent MDPs

  • Networked MDPs use heterogeneous agents with local rewards and neighbor-only communication; consensus-based neural FQI may not reach exact consensus, and its generalization error has a finite-sample high-probability bound.Consensus updates combine neighbors’ estimates, and related actor-critic methods extend the approach to continuous actions and off-policy learning.Source: §6.3 · pp. 70, 72

6.4 Stochastic Potential Games

  • In stochastic potential games, gradient-based learning in Morse-Smale games has attractor limit sets almost surely: local Nash equilibria or non-Nash locally asymptotically stable equilibria, but not saddle points.Existing stochastic-potential-game methods have conditions or limitations including known transition dynamics and potential functions, disjoint state components, or centralized joint-action optimization.Source: §6.4 · pp. 73–74

Learning in Zero-Sum Games · 7.1 Minimax Optimization · 7.1. Minimax Optimization

In two-player zero-sum games, Nash equilibrium provides an unambiguous solution concept, while minimax optimization methods offer different convergence guarantees and limitations under particular assumptions. The section introduces methods ranging from proximal and gradient updates to stochastic and two-time-scale variants.

Learning in Zero-Sum Games

  • Nash equilibrium guarantees a player its game value even when the opponent knows its strategy, and equilibrium-seeking algorithms have achieved superhuman performance in chess, Go, and poker.The cited examples are Chess (Campbell et al., 2002), Go (Silver et al., 2016), and poker (Brown and Sandholm, 2018).Source: Learning in Zero-Sum Games · p. 76

7.1 Minimax Optimization

  • Minimax optimization jointly optimizes f(x, y), which need not be convex-concave; zero-sum games are equivalent to linear programs, and any LP can also be reduced to a zero-sum game.The convex-concave condition requires convexity in x and concavity in y; the reverse reduction may require careful treatment of degenerate solutions.Source: §7.1 · p. 76

7.1. Minimax Optimization

  • Proximal Point is implicit and may be computationally costly because it requires matrix inverses, but it converges linearly to Nash equilibrium in bilinear or strongly-convex-strongly-concave cases.The convergence result is attributed to Mokhtari et al. (2020a).Source: §7.1 · pp. 76–77
  • O(1/ϵ2) average-iterate convergence is guaranteed for GDA in L-Lipschitz or l-smooth convex-concave cases, but it lacks last-iterate guarantees and may cycle or diverge.GDA also has a rate O(κ2 log 1 µ) for l-smooth and µ-strongly-convex-strongly-concave cases; it fails in simple bilinear and non-convex or non-concave cases.Source: §7.1 · p. 77
  • For OGDA in l-smooth convex-concave cases, average-iterate convergence is O(1/ϵ) (Mokhtari et al. (2020b)); Golowich et al. (2020) prove last-iterate O(1/ϵ9), and OGDA also achieves a linear convergence rate.Source: §7.1 · pp. 77–78
  • SGDA estimates gradients from samples when oracle gradients are unavailable and converges in nonconvex-strongly-concave and nonconvex-concave settings; two-time-scale SGDA is provably convergent to Nash equilibrium with finite samples.Two-time-scale SGDA extends two-time-scale GDA to the stochastic setting and uses reinforcement-learning gradient estimation such as REINFORCE, which has sample-estimation variance.Source: §7.1 · p. 78
  • Two-time-scale GDA uses asymmetric learning rates for the max- and min-players and is proven to converge in l-smooth nonconvex-strongly-concave and nonconvex-concave cases.The method is attributed to Heusel et al. (2017).Source: §7.1 · p. 78
  • γ-GDA slows the min-player’s learning rate by a factor γ > 1, but does not necessarily converge to a local Nash equilibrium; taking γ →∞ gives ∞-GDA.γ-GDA is attributed to Jin et al. (2020a).Source: §7.1 · p. 78

7.1. Minimax Optimization … 7.2. Discrete-Action Normal-Form Games

The section presents minimax optimization as a foundation for finding equilibria in two-player zero-sum games, then surveys algorithms for continuous optimization and discrete-action normal-form games. It describes convergence guarantees and limitations alongside best-response, dynamics-based, and regret-minimization approaches.

7.1. Minimax Optimization

  • GDMax converges to local minimax stationary points, a superset of local Nash equilibria (Jin et al. (2020a)); OMDA unifies OGDA and OMWU through different Bregman divergences (Wei et al. (2020)).The Euclidean divergence recovers OGDA, while KL divergence recovers OMWU.Source: §7.1 · pp. 79–80
  • Vanilla MWU can cycle even in simple bilinear cases (Bailey and Piliouras (2018)), while self-play fails to converge in zero-sum games such as Rock-Paper-Scissors (Fudenberg et al. (1998)).Source: §7.1 · p. 79, §7.2 · p. 81
  • OMWU achieves linear convergence for bilinear cases when the equilibrium is unique (Daskalakis and Panageas (2018a)).Source: §7.1 · p. 79
  • Extra-Gradient achieves O(1/ϵ) average-iterate convergence for smooth convex-concave cases and linear O(κ log 1/ϵ) convergence in bilinear and smooth strongly convex-concave cases.It also has O(1/ϵ2) last-iterate convergence for convex-concave cases; whether it has a last-iterate guarantee more generally remains open, and it is faster than OGDA on bilinear problems.Source: §7.1 · p. 80

7.2 Discrete-Action Normal-Form Games

  • In two-player zero-sum normal-form games, finding a Nash equilibrium reduces to bilinear minimax optimization over players’ mixed strategies.The payoff is x⊺Ay, with A the payoff matrix and the strategies drawn from probability simplices.Source: §7.2 · pp. 81–82
  • Fictitious Play uses best responses to opponents’ historical average strategies and achieves ϵ-NE at rate (1/ϵ)Ω(A) (Daskalakis and Pan (2014)); Double Oracle expands a restricted strategy set with best responses and has rate O(|A|) (McMahan et al. (2003)).Source: §7.2 · pp. 81–82
  • Replicator Dynamics provides continuous gradient-flow updates for symmetric games and has an asymmetric form for two-player games with different payoff matrices; Regret Matching chooses actions in proportion to positive cumulative regrets.In standard CFR, positive cumulative regrets at each information set determine action probabilities.Source: §7.2 · pp. 82, 84
  • Hedge achieves O(√(T log A)) regret in multiplayer general-sum games, while Optimistic Hedge achieves O(N log A log4 T) regret in N-player general-sum games (Daskalakis et al. (2021)).EXP3 adapts Hedge to partial-information games, where players observe only the reward of the chosen action (Auer et al. (1995)).Source: §7.2 · pp. 83–84

7.3 Continuous-Action Normal-Form Games · 7.4 Stochastic Games

These parts survey learning methods for continuous-action normal-form games and stochastic games, from approaches to stabilizing game dynamics and computing equilibria to value-based guarantees. They cover tabular, linear, general, and turn-based settings, including sample-complexity and regret results under differing assumptions.

7.3 Continuous-Action Normal-Form Games

  • Vanilla GDA can cycle, diverge, or settle at non-equilibrium stationary points in nonconvex-nonconcave games, although strict convex-concavity can ensure convergence.The cited discussion also notes that some equilibria are not GDA attractors and that non-smooth objectives and intransitive dynamics contribute to these failures.Source: §7.3 · pp. 85–86
  • Two alternatives simplify the problem by optimizing an outer minimax objective or shifting the target from Nash to Stackelberg equilibrium.The outer-loop approach uses an inner best response; local Stackelberg equilibria connect to stable GDA limit points, and alternating updates can outperform simultaneous updates in bilinear games.Source: §7.3 · pp. 86–87
  • Game-landscape methods use curvature, consensus optimization, smoothing, or other gradient-based techniques to mitigate oscillations and improve convergence guarantees.Examples include guarantees that stable limit points are local Nash equilibria and convergence results for stochastic methods under expected cocoercivity.Source: §7.3 · pp. 87, 90
  • Optimistic methods use opponent-gradient prediction to obtain last-iterate convergence in bilinear convex-concave games, while extragradient methods offer rates for monotone or Lipschitz problems.The survey also covers OMD variants, including extra-gradient OMD for coherent problems, and extragradient applications to stochastic, distributed, and quantal-response-equilibrium problems.Source: §7.3 · pp. 88–90
  • Physical-system perspectives address rotational dynamics, and projected nested-gradient and projection-free Stackelberg methods achieve global, sublinear convergence for zero-sum linear-quadratic games.The survey also describes LEAD as a second-order min-max optimizer and relates multiagent dynamics to Hamiltonian dynamics.Source: §7.3 · p. 92

7.4 Stochastic Games

  • A stochastic or Markov game extends an MDP to multiple agents with joint state transitions; in two-player zero-sum games, its value corresponds to the minimax Nash equilibrium.Shapley’s value iteration is a contraction when transitions and rewards are known, so values converge to a fixed point and the corresponding policies to Nash equilibrium.Source: §7.4 · p. 93, §7.4.1 · p. 94

7.4.1 Tabular Stochastic Games

  • Minimax-Q is model-free and provably converges to the Nash-equilibrium value in two-player zero-sum stochastic games; Nash Q-learning converges in general-sum games when each stage game has a unique equilibrium.Minimax-Q uses stochastic sampling to approximate the Bellman fixed point without knowledge of the environment.Source: §7.4.1 · p. 95
  • ˜O(H^4S^2AB/ϵ^2) is the VI-ULCB convergence rate for an ϵ-approximate NE, with higher S and lower H dependence than Nash Q-learning; the model-free lower bound is Ω(H^2S(A+B)/ϵ^2).VI-ULCB is model-based and uses an upper confidence bound exploration bonus; Nash Q-learning is model-free.Source: §7.4.1 · p. 97
  • Nash-VI uses optimistic value estimation with an auxiliary exploration bonus apart from the upper/lower confidence-bound exploration bonus; its convergence rate is ˜O(H^3SAB/ϵ^2), removing an S term compared with UCBVI.Source: §7.4.1 · p. 97
  • V-learning avoids the action-space product dependence of earlier value-based methods by estimating V values with decentralized learning, while CCE-V-learning has the same rate for multiplayer general-sum games.V values have dimensional dependence O(S), versus O(S∏_{i=1}^N A_i) for Q values.Source: §7.4.1 · p. 97

7.4.2 Linear Function Approximation

  • OMNI-VI achieves ˜O(d^3H^3T) regret for finding a Nash equilibrium in two-player zero-sum Markov games, corresponding to sample complexity ˜O(d^3H^4).It uses an optimistic version of Least Square Value Iteration, changing the single-agent Bellman operator to a Nash/Minimax Bellman operator.Source: §7.4.2 · p. 99
  • ˜O(d^2H^3/ϵ^2) is Nash-UCRL’s sample complexity for finding a CCE, and its ˜O(dH√T) regret matches the linear-game information-theoretic lower bound.Nash-UCRL applies optimism in the face of uncertainty to two-player zero-sum Markov games.Source: §7.4.2 · p. 99

7.4.3 General Function Approximation

  • ˜O(H^2d log NF/ϵ^2) is GOLF-with-Exploiter’s rate for an ϵ-approximate NE, while ONEMG has ˜O(H√(d_EK) log NF) regret and ˜O(1/ϵ^2) sample complexity.GOLF-with-Exploiter uses optimistic policy and exploiter updates; ONEMG’s d_E is the minimax Eluder dimension.Source: §7.4.3 · pp. 99–100
  • √(Kd_BEE log N) regret is achieved by decentralized DORIS for general-function zero-sum games, under realizability and generalized completeness assumptions.d_BEE is the Bellman Evaluation Eluder dimension; the rate depends on episodes K and logarithmically on function-class cardinality N.Source: §7.4.3 · p. 100

7.4.4 Turn-Based Stochastic Games

  • In two-player zero-sum turn-based stochastic games, offline Q-learning has near-optimal polynomial sample complexity, while online learning has polynomial sample complexity against an optimistic best response and sublinear regret against arbitrary opponents.With transition models embedded in a state-action feature space, the two-player Q-learning sample complexity for finding an ϵ-NE is linear in the number of features.Source: §7.4.4 · p. 101

7.5 Extensive-Form Games

This section surveys learning and search methods for extensive-form games, including regret minimization, fictitious play, double-oracle approaches, imperfect-information subgame solving, and abstraction, alongside tradeoffs in exactness, scalability, convergence guarantees, and computation.

7.5 Extensive-Form Games

  • Against stationary-policy opponents, Q-learning is Hannan-consistent while Minimax-Q cannot exploit suboptimal play; in zero-sum games, both players’ regret below ε yields a 2ε-NE average strategy.In general-sum games, an ε-regret algorithm’s average strategy reaches an ε-coarse correlated equilibrium; regret-minimizing self-play motivates fictitious play and CFR methods.Source: §7.5 · p. 103

7.5.1 Model-Free Approaches

  • Four model-free families address different limitations: tree-based methods solve small problems but scale poorly, Double Oracle expands strategy spaces, fictitious play uses iterative best responses, and policy gradients parameterize strategies.Fictitious play converges to Nash equilibria under specific conditions; policy gradients suit continuous or extremely large strategy spaces where enumeration is infeasible.Source: §7.5.1 · pp. 103–104

Counterfactual Regret Minimization (CFR)

  • CFR minimizes total regret by bounding it through immediate counterfactual regret at each information state, then uses regret matching to select actions in proportion to positive cumulative regret.CFR is analyzed through online learning and online convex optimization, enabling regret-bound analysis of convergence speed.Source: Counterfactual Regret Minimization (CFR) · pp. 104–106
  • CFR self-play yields an O(|S|/T)-approximate Nash equilibrium in two-player zero-sum games, while full-tree traversal per iteration motivates sampling, pruning, and other efficiency variants.MCCFR reduces per-iteration traversal by sampling part of the tree; PDCFR+ combines PCFR+ and DCFR principles with predictions to mitigate dominated-action effects and accelerate convergence.Source: Counterfactual Regret Minimization (CFR) · pp. 106–107
  • Deep CFR approximates regret with neural networks trained on sampled trajectories, but importance-sampling variance can destabilize learning, especially over long horizons.DREAM uses a history-value baseline, while ESCHER estimates regret with a history advantage function and is reported to outperform DREAM and NFSP in large games; Deep CFR methods require an average policy.Source: Counterfactual Regret Minimization (CFR) · pp. 107–108

Policy Gradient

  • Self-play policy gradients scale to large video games but do not generally converge to Nash equilibrium; actor-critic methods can be formulated as CFR and inherit similar two-player zero-sum guarantees.The connection follows from the relationship between counterfactual regret and MARL advantage functions, up to a realization-probability constant.Source: Policy Gradient · pp. 108–109
  • F-FoReL reaches approximate last-iterate Nash equilibrium in normal-form games but lacks extensive-form guarantees, whereas MMD has last-iterate QRE guarantees in extensive-form games using sequence form and dilated entropy.F-FoReL’s model-free, search-free self-play beat top human players at Stratego; MMD’s deep-RL behavioral-strategy update outperforms NFSP on large games without convergence guarantees, and ACH is competitive with NeuRD, RPG, and QPG.Source: Policy Gradient · pp. 109–110

Double Oracle

  • Double Oracle and PSRO iteratively solve a policy-population meta-game and add best responses, with PSRO using an RL oracle; PSRO may terminate early but trains responses sequentially and can increase exploitability between iterations.PSRO can require exponentially many pure strategies; it may suit highly transitive games or games whose skills need not be mixed, and provides an approximate-exploitability measure.Source: Double Oracle · pp. 110–112
  • PSRO variants improve response training or restricted distributions, while NXDO switches policies across information sets and converges in iterations linear in their number; regret bounds and sample complexity remain challenges.Regret-Minimizing Double Oracle provides a framework for convergence rates and sample complexity, extends ODO to extensive-form games, and highlights XDO’s exponential sample complexity.Source: Double Oracle · p. 112

Fictitious Play

  • Fictitious play converges in zero-sum, potential, and generic-payoff two-player games, though worst-case convergence is inefficient; smooth FP has Hannan-consistency and potential-game convergence results.Sampled FP with Bernoulli sampling is also Hannan consistent.Source: Fictitious Play · pp. 113–114
  • GWFP combines approximate best responses and perturbed strategy updates, enabling model-free RL and exploration; extensive-form FP adapts it to information states and supports neural variants.GWFP recovers maximum-entropy RL with entropy perturbation; Perolat et al. (2018) implemented it with actor-critic, while NFSP uses deep Q-learning and supervised learning for its two update steps.Source: Fictitious Play · pp. 115–116

7.5.2 Search

  • Search improves a blueprint policy at test time by approximately solving the remaining subgame at an information set, aiming for a better strategy against an opponent.Blueprint policies approximate Nash equilibrium but may be insufficient for superhuman performance in games such as chess, go, and poker.Source: §7.5.2 · p. 116

Perfect-Information Search

  • Perfect-information search recursively solves subgames by minimax, while larger-game methods truncate search with state heuristics, including learned value estimates in AlphaGo and AlphaZero.AlphaGo trained its value network and policy using human data; AlphaZero learned them from self-play rollouts.Source: Perfect-Information Search · p. 117

Imperfect-Information Search

  • Imperfect-information search must account for information beyond the current state, using gadget games or public belief states; safe solving limits exploitability, while k-KLSS prunes unreachable nodes.Safe solving gives the opponent a blueprint-utility opt-out; k-KLSS uses low-order knowledge instead of enumerating the common-knowledge closure, which can be infeasibly large.Source: Imperfect-Information Search · pp. 117–118

Imperfect-Information Subgame Solving

  • Imperfect-information subgame-solving methods have advanced in decomposition, real-time refinement, and scalability, but abstraction and generalization beyond poker remain unresolved challenges.Libratus and DeepStack demonstrate superhuman poker performance, whereas scalability and exploitability control remain challenges in non-poker domains.Source: Imperfect-Information Subgame Solving · pp. 118–119

Game Abstraction in Imperfect-Information Games

  • Game abstraction reduces large imperfect-information games through state, action, or information simplification; lossy abstractions trade strategic accuracy for tractability, with theoretical error and exploitability guarantees.Dynamic and adaptive refinement can adjust abstractions as play progresses to improve computational efficiency and solution quality.Source: Game Abstraction in… · p. 120

7.6. Online Markov Decision Processes

Abstraction methods combine computational efficiency with theoretical guarantees and have succeeded in poker, but still lack solution-quality guarantees in multi-agent and non-zero-sum games.

7.6. Online Markov Decision Processes

  • Integrating Nash equilibrium solvers with abstraction pipelines can address massive strategy spaces in complex games such as poker.Libratus demonstrated superhuman poker performance by continuously refining abstractions during play.Source: §7.6 · p. 121
  • Abstraction methods have shown practical success in poker, where Libratus demonstrated superhuman performance by continuously refining abstractions throughout games.Source: §7.6 · p. 121
  • In multi-agent and non-zero-sum games, abstraction methods struggle to provide guarantees on solution quality.Future research may address these limitations, extend abstractions to more dynamic multi-agent environments, and explore temporal abstractions and long-horizon decisions.Source: §7.6 · p. 121

7.6 Online Markov Decision Processes

Online MDPs extend online learning to dynamic environments where rewards and transition dynamics may change over time. They seek policies with low regret against any opponent, including an adversary that need not be rational or competitive.

7.6 Online Markov Decision Processes

  • Online MDPs model changing rewards and transitions, with an adversary that controls them but need not be rational or competitive.The goal is to perform well against every possible opponent, not only adversarial ones.Source: §7.6 · p. 121
  • The target is regret against the best stationary policy in retrospect, with RegT →0 as T →∞ with probability 1.This regret differs from the repeated-game formulation, and the reward and transition sequences are set by the adversary rather than influenced by the retrospective policy sequence.Source: §7.6 · p. 122
  • No-regret learning requires obliviously chosen changing rewards; with both rewards and transitions adversarial, no polynomial-time solution is known even for an oblivious adversary.An oblivious adversary fixes reward functions and transition kernels in advance, without knowing the agent’s actions; Yadkori et al. (2013) demonstrated the polynomial-time limitation using online shortest path.Source: §7.6 · p. 122
  • Most no-regret algorithms assume an oblivious reward adversary and differ in whether transitions are known and reward feedback is full-information or bandit.Ortner et al. (2020); Cheung et al. (2020) studied slowly changing transition dynamics bounded by a total-variation budget.Source: §7.6 · p. 122

7.6. Online Markov Decision Processes

Online MDP regret methods use both local-to-global regret decomposition and online linear optimization, with algorithms addressing full-information, bandit-feedback, function-approximation, and unknown-transition settings.

7.6. Online Markov Decision Processes

  • Global no-regret can be achieved by running a local regret-minimization algorithm at each state, with a similar result noted for CFR.The local regret is defined statewise using reward function Qt(s, ·).Source: §7.6 · p. 123
  • A later MDP-EXP3 result removed the β dependency and achieved O(T log T) regret under bandit feedback.The earlier MDP-EXP3 bound depended on β, a lower bound on the probability of reaching a state under a policy.Source: §7.6 · p. 123
  • Q-FPL avoids requiring a known transition kernel and achieves O(T 2/3) regret, while OPPO permits unknown transitions but requires full information about rewards.OPPO’s stated regret bound is O(d^2H^3T), where d is feature dimension, H is episode horizon, and T is total steps.Source: §7.6 · p. 123
  • Jin et al. (2019a) addressed online MDP learning with unknown transition dynamics and bandit feedback.The section also describes MDP-Expert under known transitions and full-information rewards, and MDP-EXP3 under bandit feedback.Source: §7.6 · p. 123
  • O-REPS achieves O(τT log(|S||A|)) regret with full information and O(T|S||A| log(|S||A|)) with bandit feedback.The OLO approach can handle different model constraints and extensions; UC-O-REPS extends O-REPS to unknown transition dynamics.Source: §7.6 · p. 124

7.7 Team Games · 7.7. Team Games

Team games give teammates a shared utility, and in two-team zero-sum games, TMECor allows teammates to coordinate before play. Compared with TME, TMECor guarantees at least as much expected utility, has a convex objective, and is generally NP-hard and inapproximable to find.

7.7 Team Games

  • Team games give members of the same team shared utility functions, and two-team zero-sum games involve competing teams.Source: §7.7 · p. 124

7.7. Team Games

  • TMECor allows teammates to coordinate before play, whereas TME is an equilibrium strategy for team members who cannot coordinate.A TME gives the team maximum expected utility against a best-responding opponent (von Stengel and Koller (1997); Basilico et al. (2017); Zhang and An (2020a,b); Kalogiannis et al. (2021)).Source: §7.7 · pp. 124–125
  • TMECor guarantees the team at least as much expected utility as TME (Celli and Gatti (2018)).Source: §7.7 · p. 125
  • TMECor has a convex objective, while the TME objective is not convex; finding a TMECor strategy is generally NP-hard and inapproximable (Celli and Gatti (2018)).The passage also notes that real-world scenarios may not permit communication.Source: §7.7 · p. 125

Learning in General-Sum Games

This section surveys approaches to learning in general-sum stochastic games, including mathematical-programming, value-based, two-timescale, policy-based, and mean-field methods. It covers mean-field approaches for non-cooperative equilibrium learning, cooperative control, and Q-function approximation, along with their convergence, scalability, equilibrium, and learning challenges.

Learning in General-Sum Games

  • Even static two-player normal-form Nash-equilibrium finding is PPAD-complete, and solving general-sum stochastic games is more difficult than solving team or zero-sum games.Source: Learning in General-Sum Games · p. 126

8.1. Solutions by Mathematical Programming

  • Filar and Vrieze (2012) formulate two-player general-sum stochastic-game solving as a nonlinear program, but its nonconvex feasible region and need for a global optimum impede solution.Other formulations include nonlinear objectives with linear constraints, multi-objective linear programming, and homotopy; these methods are tractable only for games with at most tens of states and two players.Source: §8.1 · pp. 126–128

8.2 Solutions by Value-Based Methods

  • Centralized Q-learning methods use Nash, correlated, or friend-or-foe equilibria, but convergence guarantees rely on restrictive assumptions, and multiagent Q-values may not reconstruct stationary equilibrium policies.Nash-Q convergence requires a unique Nash equilibrium in every encountered stage game; a negative result excludes value-iteration methods from computing stationary Nash or correlated equilibria in general-sum games.Source: §8.2 · pp. 129–130
  • Optimistic Nash-VI provably finds coarse correlated equilibria, while V-learning avoids the multiagent action-space dependence by estimating values with O(S) rather than Q-values with O(SΠN) dimensions.Optimistic V-learning with stabilized online mirror descent and CCE-/CE-V-learning have similar rates to V-learning, with slightly worse dependence on horizon H.Source: §8.2 · p. 130

8.3 Solutions by Two-Timescale Analysis

  • Two-timescale updates support convergence to equilibria in several settings, including weakly acyclic stochastic games and general-sum Stackelberg games, but balancing timescales and ensuring convergence remain challenges.The cited applications include almost-sure convergence in specified two-player games, stationary local Nash equilibria when the critic learns faster than the actor, and asymptotic Stackelberg-equilibrium convergence.Source: §8.3 · pp. 131–132

8.4. Solutions by Policy-Based Methods

  • In continuous games, multiagent gradient dynamics need not form a proper gradient flow, and gradient methods can miss local Nash equilibria; symplectic gradient adjustment finds all local equilibria in zero-sum games and a subset in general-sum games.These results do not automatically extend to stochastic games, where value functions need not be globally smooth in policy parameters, even in linear-quadratic games.Source: §8.4 · pp. 132–134

9.1. Non-cooperative Mean-Field Game

  • For N→∞, mean-field approximation turns many-agent interactions into agent-versus-population-mean interactions; MFG, MFC, and MF-MARL differ in game type and when the population limit is taken.Source: §8.4 · pp. 135–136, §9.1 · p. 137

9.1 Non-cooperative Mean-Field Game

  • MFG assumes homogeneous, interchangeable agents with weak interactions through a population mean field, and computes equilibrium by alternating best responses with mean-field updates.The iteration continues until its mean-field estimate reaches a fixed point; the meeting-time example reduces the start time to a population quantile as N → +∞.Source: §9.1 · pp. 138–139
  • Discrete-time discounted MFG equilibrium existence is established for population-state models, while Guo et al. (2019) establish NE existence with state and action distributions; uniqueness depends on conditions, and multiple equilibria can occur.Small-parameter conditions yield uniqueness in L*, while monotonic costs are a common uniqueness assumption; general MFGs may admit multiple equilibria.Source: §9.1 · p. 140
  • Single-agent-order sample complexity is reported for value- and policy-based MFG learning, which combines single-agent RL best responses with mean-field updates or fictitious play.Softmax policies and projection of the mean-field quantity onto a finite-cover ϵ-net can stabilize forward propagation.Source: §9.1 · p. 140, §9.2 · p. 141

9.2. Cooperative Mean-Field Control

  • MFC takes N → +∞ to avoid the exponential sample-complexity growth of cooperative Q-learning, yielding a dimension independent of N and approximating game values and optimal strategies.The approximation relies on the law of large numbers and propagation of chaos; Lacker (2017) and Motte and Pham (2019) support approximation of values and strategies.Source: §9.2 · p. 141
  • Unlike MFG, MFC uses a central controller to maximize aggregate reward and seeks a Pareto optimum, but its mean-field-dependent policy makes the problem time-inconsistent.Adding common noise permits use of MDP learning theory, but has high sample complexity and weak empirical performance; lifting the state-action space is another proposed remedy.Source: §9.2 · p. 142

9.3. Mean-Field MARL

  • Mean-field MARL approximates each agent’s Q-function using local pairwise interactions and neighbors’ mean actions, without requiring an infinite population or including state distributions in the mean field.Larger neighborhoods can reduce approximation error under the law of large numbers.Source: §9.3 · p. 144
  • For large β, the Boltzmann policy makes the optimal action unique given the mean action, resolving the coupling problem; MF-Q update convergence is established under conditions including a unique stage-game NE.MF-Q modifies Nash-Q by changing its solution concept to mean-field NE.Source: §9.3 · p. 145
  • MF-Q achieved strong performance against humans in Uber China taxi dispatching, while extensions address multiple agent types and partially observable mean-field behavior.Subramanian and Mahajan (2019) applied a multi-type extension to predator-prey simulation; Ganapathi Subramanian et al. (2020) modeled uncertainty about the mean field with a distribution.Source: §9.3 · pp. 145–146

Future Directions

The section identifies MARL theory as under-explored, especially for extending single-agent results to multiagent settings and explaining deep MARL’s effectiveness.

MARL Theory

  • MARL theory remains under-explored: extending single-agent convergence and finite-sample analyses to multiagent settings is nontrivial, while deep MARL needs theories explaining DNN effectiveness.The authors estimate an approximate ten-year gap between single-agent and multiagent RL theory, and propose extending single-agent results by addressing multiagent-specific difficulties before generalizing to DNNs; they recommend Zhang et al. (2019b).Source: Future Directions · p. 147

144 Future Directions

Future work should strengthen theoretical guarantees and address safety, robustness, model-based learning, cross-game adaptation, and foundation models for MARL.

Future Directions

  • A comprehensive summary of existing MARL algorithms with theoretical convergence guarantees remains a needed direction.Source: 144 Future Directions · p. 148

Safe and Robust MARL

  • MARL needs safety and robustness frameworks that account for inter-agent coupling, conflicting interests, and environmental-dynamics uncertainty.Robustness concerns generalization beyond training conditions, while safety constrains actions to a predefined zone with minimal violations, including during training.Source: 144 Future Directions · p. 148

Model-Based MARL

  • Model-based MARL deserves renewed attention: it can reduce environment samples, but progress has stalled since early work such as R-MAX.The passage notes model-based methods' strong results in single-agent RL and argues for further development in MARL.Source: 144 Future Directions · pp. 148–149

Multiagent Meta-RL

  • Meta-learning guarantees cover fundamental game classes, with faster equilibrium convergence than solving games in isolation and poker-endgame efficiency gains often around an order of magnitude.Harris et al. (2022) also recover single-game guarantees for arbitrary game sequences; Anagnostides et al. (2024) show meta-learning can sharpen variation-dependent regret bounds and convergence guarantees in dynamic games.Source: 144 Future Directions · p. 149
  • Multiagent meta-RL remains uncharted and must handle agents discovering roles across games and computing outer-loop gradients through MARL inner-loop algorithms.The proposed ambition is to solve many tasks in one or a few shots; candidate inner loops include multiagent policy gradient and mean-field Q-learning.Source: 144 Future Directions · pp. 149–150

Foundation Models for MARL

  • Foundation models may bring broad prior knowledge to sequential decision-making, improving task-solving speed and generalization while raising challenges in feedback, modalities, and long-term planning.The approach aims to address start-from-scratch methods' limitations in generalization and sample efficiency.Source: 144 Future Directions · pp. 150–151

Related papers

Loading 2011.00583v5…