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

Kaiqing ZhangZhuoran YangTamer Başar

article2019Handbook of Reinforcement Learning and Control1,750 citations

Synthesizes the theoretical foundations of multi-agent reinforcement learning across stochastic and extensive-form games, categorizing algorithmic guarantees for cooperative, competitive, decentralized, and mean-field settings.

Listen

Modern autonomous systems increasingly rely on reinforcement learning to make sequential decisions, but critical real-world deployments—including autonomous driving, drone swarms, robotics, and distributed energy systems—involve multiple interacting participants rather than a single actor. Multi-agent reinforcement learning addresses this setting, where agents optimize their individual or shared goals in a shared environment. Despite high-profile empirical successes in complex board games and real-time strategy environments, theoretical understanding has lagged behind practical implementations, creating uncertainty regarding system stability, scalability, and safety in high-stakes environments.

The article provides a systematic overview of multi-agent reinforcement learning theories and algorithms across cooperative, competitive, and mixed-sum environments. It examines theoretical convergence and sample complexity guarantees across two primary frameworks: Markov games and extensive-form games.

The authors conducted a structured literature review spanning dynamic programming, computational game theory, decentralized control, and optimization theory. They analyzed core mathematical foundations across fully cooperative teams, two-player zero-sum competitions, and general-sum mixed games. The review also examined key operating structures, comparing centralized coordination with fully decentralized execution over communication networks.

The article establishes several major findings regarding the theoretical guarantees of multi-agent systems. First, the core difficulty in multi-agent learning stems from environment non-stationarity, because concurrent learning by multiple agents invalidates the static environment assumption foundational to single-agent reinforcement learning. Second, theoretical guarantees vary substantially by game setting: two-player zero-sum competitive games and cooperative team problems have established convergence proofs, whereas general-sum mixed settings remain largely intractable without restrictive assumptions due to inherent computational complexity barriers. Third, decentralized networked cooperative algorithms can successfully reach global optima using local neighbor-to-neighbor communication, eliminating the need for single-point centralized controllers. Fourth, extensive-form games combined with regret minimization techniques offer provably convergent, polynomial-time frameworks for managing imperfect information and partial observability.

These findings indicate that deploying multi-agent learning in safety-critical systems requires carefully matching the problem setting to known theoretical boundaries. While cooperative systems and two-player competitive systems offer predictable behavior, mixed multi-agent environments carry significant risks of cycling or non-convergence when standard policy gradient methods are used. Practitioners cannot assume that methods performing well in single-agent environments will remain stable in multi-agent deployments.

Organizations developing multi-agent systems should select algorithmic architectures supported by proven convergence properties, such as consensus-based decentralized algorithms for collaborative fleets or regret-minimization methods for imperfect-information settings. Before adopting multi-agent reinforcement learning in high-risk operational domains, decision-makers should invest in rigorous simulation testing, establish formal safety constraints, and investigate model-based approaches that offer better sample efficiency and clearer stability profiles.

The conclusions are limited by the scarcity of non-asymptotic, finite-sample guarantees, as well as the absence of unified theoretical foundations for deep neural network function approximation. Additionally, general partially observable settings remain computationally hard in the worst case. Consequently, while stakeholders can place high confidence in the theoretical foundations of cooperative and two-player zero-sum tabular frameworks, they should exercise caution when scaling deep multi-agent learning to complex, unconstrained environments.

Princeton University University of Illinois Urbana-Champaign autonomous driving multi-agent reinforcement learning single-agent multi-agent reinforcement learning multi-agent actor-critic mean-field reinforcement learning

arXiv: 1911.10635

Paper: Markov Games as a Framework for Multi-Agent Reinforcement Learning, Michael L. Littman (1994). This seminal paper introduces the framework of Markov games to multi-agent reinforcement learning along with the Minimax-Q algorithm, providing the foundational theoretical problem formulation surveyed in the source.
Paper: Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments, Ryan Lowe et al. (2017). This paper establishes the centralized training with decentralized execution actor-critic paradigm (MADDPG) for mixed cooperative-competitive environments, a central algorithmic architecture analyzed in the survey.
Paper: QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning, Tabish Rashid et al. (2018). This work introduces monotonic value function factorisation for cooperative multi-agent RL, forming a key benchmark and theoretical mechanism discussed in cooperative game overviews.
Paper: Counterfactual Multi-Agent Policy Gradients, Jakob N. Foerster et al. (2017). This paper formulates counterfactual multi-agent policy gradients to solve the multi-agent credit assignment problem via centralized critics, providing crucial background for policy-based MARL theory.
Paper: Learning to Communicate with Deep Multi-Agent Reinforcement Learning, Jakob N. Foerster et al. (2016). This study introduces foundational centralized training with decentralized execution algorithms (DIAL/RIAL) for learning emergent inter-agent communication under partial observability.
Paper: Reinforcement Learning: A Survey, Leslie Pack Kaelbling et al. (1996). This survey provides the classical single-agent reinforcement learning and Markov decision process foundations that multi-agent theoretical frameworks directly generalize.
Paper: Technical Note: Q-Learning, CHRISTOPHER J.C.H. WATKINS et al. (2004). This foundational note proves the convergence of single-agent Q-learning, which serves as the core theoretical baseline from which multi-agent value-based algorithms are derived and analyzed.
Paper: Policy Gradient Methods for Reinforcement Learning with Function Approximation, Richard S. Sutton et al. (1999). This chapter establishes the Policy Gradient Theorem under function approximation, which is fundamental to understanding the convergence and non-convergence of policy-based methods in multi-agent games.

Paper: The Surprising Effectiveness of PPO in Cooperative Multi-Agent Games, Chao Yu et al. (2022). This paper empirically investigates and extends multi-agent policy optimization by systematically evaluating on-policy centralized and decentralized PPO variants across major cooperative MARL benchmarks.
Paper: Emergent Tool Use From Multi-Agent Autocurricula, Bowen Baker et al. (2020). This study demonstrates how multi-agent competitive games and autocurricula drive the spontaneous emergence of complex behaviors and tool use in physical multi-agent environments.
Paper: Deep Reinforcement Learning for Autonomous Driving: A Survey, Bangalore Ravi Kiran et al. (2020). This survey explores the application and operational scaling of deep reinforcement learning algorithms in autonomous driving, a key multi-agent sequential decision-making domain highlighted in the source.
Paper: The Rise and Potential of Large Language Model Based Agents: A Survey, Zhiheng Xi et al. (2023). This survey explores the modern extension of agent frameworks to large language model-based controllers, analyzing multi-agent collaboration and game-theoretic interaction architectures.
Paper: Towards a Science of Scaling Agent Systems, Yubin Kim et al. (2025). This work establishes scaling laws and architectural principles for multi-agent systems, providing empirical analysis of coordination costs versus single-agent performance.

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

Abstract

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
2 Background
2.1 Single-Agent RL
2.1.1 Value-Based Methods
2.1.2 Policy-Based Methods
2.2 Multi-Agent RL Framework
2.2.1 Markov/Stochastic Games
2.2.2 Extensive-Form Games
3 Challenges in MARL Theory
3.1 Non-Unique Learning Goals
3.2 Non-Stationarity
3.3 Scalability Issue
3.4 Various Information Structures
4 MARL Algorithms with Theory
4.1 Cooperative Setting
4.1.1 Homogeneous Agents
4.1.2 Decentralized Paradigm with Networked Agents
4.1.3 Partially Observed Model
4.2 Competitive Setting
4.2.1 Value-Based Methods
4.2.2 Policy-Based Methods
4.3 Mixed Setting
5 Application Highlights
5.1 Cooperative Setting
5.2 Competitive Setting
5.3 Mixed Settings
6 Conclusions and Future Directions
References

Knowls

Knowl 1 — Markov Game and Stationary Nash Equilibrium Formulation
definition
An $N$ -player Markov game (also termed a stochastic game) in the infinite-horizon discounted setting is defined by a tuple $(\mathcal{N}, \mathcal{S}, \{\mathcal{A}^i\}_{i\in\mathcal{N}}, \mathcal{P}, \{R^i\}_{i\in\mathcal{N}}, \gamma)$ , where:
- $\mathcal{N} = \{1, \dots, N\}$ is the set of $N > 1$ agents;
- $\mathcal{S}$ denotes the joint state space observed by all agents;
- $\mathcal{A}^i$ is the action space of agent $i$ , with the joint action space defined as $\mathcal{A} := \mathcal{A}^1 \times \dots \times \mathcal{A}^N$ ;
- $\mathcal{P} : \mathcal{S} \times \mathcal{A} \to \Delta(\mathcal{S})$ is the transition probability function mapping a state-joint action pair $(s, a)$ to a probability distribution over next states $s' \in \mathcal{S}$ ;
- $R^i : \mathcal{S} \times \mathcal{A} \times \mathcal{S} \to \mathbb{R}$ is the reward function determining the immediate scalar payoff received by agent $i$ upon transition $(s, a, s')$ ;
- $\gamma \in [0, 1)$ is the discount factor.
Each agent $i \in \mathcal{N}$ acts according to a stationary policy $\pi^i : \mathcal{S} \to \Delta(\mathcal{A}^i)$ . Under a joint policy $\pi(a|s) := \prod_{i\in\mathcal{N}} \pi^i(a^i|s)$ , the expected discounted return (value function) of agent $i$ initialized at state $s_0 = s$ is:

$V_{\pi^i, \pi^{-i}}^i(s) := \mathbb{E}\left[ \sum_{t=0}^\infty \gamma^t R^i(s_t, a_t, s_{t+1}) \;\middle|\; a_t^j \sim \pi^j(\cdot|s_t) \; \forall j \in \mathcal{N}, s_0 = s \right],$

where $\pi^{-i}$ denotes the joint policy of all agents excluding agent $i$ .

A stationary Nash equilibrium (NE) is a joint policy $\pi^* = (\pi^{1,*}, \dots, \pi^{N,*})$ satisfying, for all states $s \in \mathcal{S}$ and all agents $i \in \mathcal{N}$ :

$V_{\pi^{i,*}, \pi^{-i,*}}^i(s) \ge V_{\pi^i, \pi^{-i,*}}^i(s), \quad \forall \pi^i : \mathcal{S} \to \Delta(\mathcal{A}^i).$

Markov games encompass three primary task categories:
1. Fully cooperative: agents share a common objective, formalized either as identical rewards $R^1 = \dots = R^N = R$ or team-average reward $\bar{R}(s, a, s') := N^{-1} \sum_{i\in\mathcal{N}} R^i(s, a, s')$ .
2. Fully competitive: two agents compete in a zero-sum setting where $R^1(s, a, s') + R^2(s, a, s') = 0$ .
3. Mixed: general-sum setting with arbitrary, unconstrained reward functions across self-interested agents.
Knowl 2 — Extensive-Form Game with Imperfect Information and Approximate Nash Equilibrium
definition
An extensive-form game with imperfect information is defined by the tuple $(\mathcal{N} \cup \{c\}, \mathcal{H}, \mathcal{Z}, \mathcal{A}, \{R^i\}_{i\in\mathcal{N}}, \tau, \pi^c, \mathcal{S})$ , where:
- $\mathcal{N} = \{1, \dots, N\}$ is the set of agents, and $c$ is a chance player executing a fixed stochastic policy $\pi^c$ ;
- $\mathcal{A}$ is the set of all available actions;
- $\mathcal{H}$ is the set of all possible histories (sequences of actions taken from game start), $\mathcal{A}(h) = \{a \mid ha \in \mathcal{H}\}$ denotes actions available at nonterminal history $h$ , and $\mathcal{Z} \subseteq \mathcal{H}$ is the set of terminal histories;
- $R^i : \mathcal{Z} \to \mathbb{R}$ is the utility function assigning terminal payoffs to player $i \in \mathcal{N}$ ;
- $\tau : \mathcal{H} \to \mathcal{N} \cup \{c\}$ identifies the acting agent at history $h$ ;
- $\mathcal{S}$ partitions nonterminal histories $\mathcal{H} \setminus \mathcal{Z}$ into information sets (information states) $s \in \mathcal{S}$ such that for any $h, h' \in s$ , $\tau(h) = \tau(h')$ and $\mathcal{A}(h) = \mathcal{A}(h')$ . An information state is imperfectly informed when $|s| > 1$ .
Let $\mathcal{S}^i = \{s \in \mathcal{S} \mid \tau(s) = i\}$ . Under a joint behavioral policy $\pi = (\pi^1, \dots, \pi^N)$ with $\pi^i : \mathcal{S}^i \to \Delta(\mathcal{A}(s))$ , the reach probability of history $h$ is defined by:

$\eta_\pi(h) = \prod_{i \in \mathcal{N}\cup\{c\}} \prod_{h': h'a \sqsubseteq h, \tau(h')=i} \pi^i(a \mid I(h')),$

where $h' \sqsubseteq h$ denotes that $h'$ is a prefix sequence of $h$ , and $I(h') \in \mathcal{S}$ is the information set containing $h'$ . The reach probability of information state $s$ is $\eta_\pi(s) = \sum_{h \in s} \eta_\pi(h)$ , and the expected utility of player $i$ is $R^i(\pi) = \sum_{z \in \mathcal{Z}} \eta_\pi(z) R^i(z)$ .

An $\epsilon$ -Nash equilibrium is a joint policy $\pi^* = (\pi^{1,*}, \dots, \pi^{N,*})$ satisfying, for all $i \in \mathcal{N}$ and all valid policies $\pi^i$ of agent $i$ :

$R^i(\pi^{i,*}, \pi^{-i,*}) \ge R^i(\pi^i, \pi^{-i,*}) - \epsilon.$

When $\epsilon = 0$ , $\pi^*$ is an exact Nash equilibrium.
Knowl 3 — Bellman Optimality Operator and Minimax-Q Learning for Two-Player Zero-Sum Markov Games
theoretical result
In a two-player zero-sum Markov game with state space $\mathcal{S}$ , action spaces $\mathcal{A}^1, \mathcal{A}^2$ , transition probability $\mathcal{P}$ , discount factor $\gamma \in [0,1)$ , and $R^1 + R^2 = 0$ , the value function satisfies $V^1_{\pi^1,\pi^2} = -V^2_{\pi^1,\pi^2}$ . The optimal value function $V^* : \mathcal{S} \to \mathbb{R}$ defined by:

$V^*(s) = \max_{\pi^1} \min_{\pi^2} V^1_{\pi^1, \pi^2}(s) = \min_{\pi^2} \max_{\pi^1} V^1_{\pi^1, \pi^2}(s)$

is the unique solution to the game Bellman equation $V = T^* V$ . The Bellman optimality operator $T^*$ acts on value functions $V : \mathcal{S} \to \mathbb{R}$ according to:

$(T^* V)(s) = \text{Value}\left[ Q_V(s, \cdot, \cdot) \right] = \max_{u \in \Delta(\mathcal{A}^1)} \min_{v \in \Delta(\mathcal{A}^2)} \sum_{a \in \mathcal{A}^1} \sum_{b \in \mathcal{A}^2} u_a v_b Q_V(s, a, b),$

where $Q_V(s, a, b) = \mathbb{E}_{s' \sim \mathcal{P}(\cdot|s,a,b)} [R^1(s, a, b, s') + \gamma V(s')]$ , and $\text{Value}[\cdot]$ denotes the minimax value of the matrix game evaluated by linear programming. The operator $T^*$ is a $\gamma$ -contraction in the $\ell_\infty$ -norm:

$\|T^* V - T^* V'\|_\infty \le \gamma \|V - V'\|_\infty.$

Minimax-Q learning maintains a tabular action-value estimate $Q : \mathcal{S} \times \mathcal{A}^1 \times \mathcal{A}^2 \to \mathbb{R}$ updated upon observing transition $(s_t, a_t^1, a_t^2, r_t, s_{t+1})$ via:

$Q(s_t, a_t^1, a_t^2) \leftarrow (1 - \alpha_t) Q(s_t, a_t^1, a_t^2) + \alpha_t \left( r_t + \gamma \cdot \text{Value}\left[ Q(s_{t+1}, \cdot, \cdot) \right] \right),$

where $\alpha_t \in (0,1)$ is the learning rate. Under standard Robbins-Monro stepsize conditions $\sum_t \alpha_t = \infty$ and $\sum_t \alpha_t^2 < \infty$ , the sequence $Q_t$ converges almost surely to the unique optimal action-value function $Q^*$ , from which a stationary Nash equilibrium policy pair is obtained by solving the matrix game at each state.
Knowl 4 — Decentralized Multi-Agent Actor-Critic with Networked Consensus
algorithm
In cooperative MARL with $N$ networked agents connected by a time-varying communication graph, agents aim to maximize the team-average expected return $J(\theta)$ corresponding to reward $\bar{R}(s,a,s') = N^{-1} \sum_{i=1}^N R^i(s,a,s')$ . Each agent $i \in \mathcal{N}$ maintains a policy $\pi_{\theta^i}^i(a^i|s)$ parameterized by $\theta^i \in \mathbb{R}^{m_i}$ and a local parameter vector $\omega^i \in \mathbb{R}^d$ approximating the global Q-function $Q_\theta(s,a) \approx Q(s,a;\omega^i)$ .

The policy gradient with respect to local parameters is:

$\nabla_{\theta^i} J(\theta) = \mathbb{E}\left[ \nabla_{\theta^i} \log \pi_{\theta^i}^i(s, a^i) \cdot Q_\theta(s,a) \right].$

Agents execute the following decentralized actor-critic procedure:
Input: Initial parameters $\theta_0^i, \omega_0^i$ for all $i \in \mathcal{N}$ , stepsizes $\alpha_{\theta,t} > 0, \beta_{\omega,t} > 0$ , communication matrices $C_t = [c_t(i,j)]$
Initialize: State $s_0$
for each time step $t = 0, 1, 2, \dots$ do
    for each agent $i \in \mathcal{N}$ in parallel do
        Sample and execute action $a_t^i \sim \pi_{\theta_t^i}^i(\cdot|s_t)$
    Observe next state $s_{t+1}$ and private reward $R^i(s_t, a_t, s_{t+1})$ for each agent $i$
    for each agent $i \in \mathcal{N}$ in parallel do
        Sample next action $a_{t+1}^i \sim \pi_{\theta_t^i}^i(\cdot|s_{t+1})$
        Compute local TD-error $\delta_t^i = R^i(s_t, a_t, s_{t+1}) + \gamma Q(s_{t+1}, a_{t+1}; \omega_t^i) - Q(s_t, a_t; \omega_t^i)$
        Local critic update: $\tilde{\omega}_t^i = \omega_t^i + \beta_{\omega,t} \delta_t^i \nabla_\omega Q(s_t, a_t; \omega_t^i)$
        Transmit $\tilde{\omega}_t^i$ to neighboring agents $j \in \mathcal{N}_t^i$
        Consensus critic update: $\omega_{t+1}^i = \sum_{j \in \mathcal{N}} c_t(i,j) \tilde{\omega}_t^j$
        Local actor update: $\theta_{t+1}^i = \theta_t^i + \alpha_{\theta,t} \nabla_{\theta^i} \log \pi_{\theta_t^i}^i(a_t^i|s_t) Q(s_t, a_t; \omega_t^i)$
When linear function approximation is used for the critic and the communication matrices $C_t$ are doubly stochastic in expectation, the critic iterates achieve consensus across agents and the policy parameters converge almost surely to a stationary point of $J(\theta)$ under standard two-timescale stepsize conditions.
Knowl 5 — Distributed Saddle-Point Formulation of Multi-Agent Policy Evaluation
theoretical result
In cooperative multi-agent policy evaluation with $N$ networked agents under a fixed joint policy $\pi$ , each agent parameterizes the value function linearly as $V_\omega(s) = \phi(s)^\top \omega$ using global feature vectors $\phi(s) \in \mathbb{R}^d$ and parameter $\omega \in \mathbb{R}^d$ . The agents seek to minimize the Mean Square Projected Bellman Error (MSPBE) for the team-average reward $\bar{R}^\pi(s) = N^{-1} \sum_{i=1}^N \mathbb{E}[R^i(s, a, s') \mid s]$ :

$\min_\omega \text{MSPBE}(\omega) := \left\| \Pi_\Phi \left( V_\omega - \gamma P^\pi V_\omega - \bar{R}^\pi \right) \right\|_D^2 = \|A\omega - b\|_{C^{-1}}^2,$

where $\Phi = [\dots; \phi(s)^\top; \dots] \in \mathbb{R}^{|\mathcal{S}| \times d}$ , $D = \text{diag}(\{\eta_\pi(s)\}_{s\in\mathcal{S}})$ is the diagonal matrix of state occupancy measures $\eta_\pi$ , $\Pi_\Phi = \Phi(\Phi^\top D \Phi)^{-1} \Phi^\top D$ is the projection operator, $A = \mathbb{E}[\phi(s)(\phi(s) - \gamma \phi(s'))^\top]$ , $C = \mathbb{E}[\phi(s)\phi(s)^\top]$ , and $b = N^{-1} \sum_{i\in\mathcal{N}} b^i$ with $b^i = \mathbb{E}[R^{i,\pi}(s)\phi(s)]$ .

Using Fenchel duality, the empirical MSPBE minimization over a dataset of size $n$ is reformulated as a distributed saddle-point problem:

$\min_\omega \max_{\{\lambda^i\}_{i\in\mathcal{N}}} \frac{1}{N n} \sum_{i\in\mathcal{N}} \sum_{j=1}^n \left[ 2(\lambda^i)^\top A_j \omega - 2(b_j^i)^\top \lambda^i - (\lambda^i)^\top C_j \lambda^i \right],$

where $\lambda^i \in \mathbb{R}^d$ is a local dual variable private to agent $i$ , and $A_j, C_j, b_j^i$ are sample estimates of $A, C, b^i$ from data point $j$ . This problem is convex in $\omega$ and concave in each $\lambda^i$ , enabling primal-dual distributed consensus algorithms to converge with linear convergence rates.
Knowl 6 — No-Regret Learning and Nash Equilibrium Convergence in Two-Player Zero-Sum Games
theoretical result
Let two players play a repeated or extensive-form game over $T$ stages generating joint policies $\{\pi_t = (\pi_t^1, \pi_t^2)\}_{t=1}^T$ . The external regret of player $i \in \{1, 2\}$ relative to the best fixed policy in hindsight is:

$\text{Reg}_T^i = \max_{\pi^i} \sum_{t=1}^T \left[ R^i(\pi^i, \pi_t^{-i}) - R^i(\pi_t^i, \pi_t^{-i}) \right].$

An algorithm is Hannan consistent (no-regret) if $\lim_{T\to\infty} T^{-1} \text{Reg}_T^i \le 0$ .

In two-player zero-sum games ( $R^1 + R^2 = 0$ ), if both players independently employ Hannan consistent algorithms such that their average regrets satisfy:

$\frac{1}{T} \text{Reg}_T^1 \le \epsilon \quad \text{and} \quad \frac{1}{T} \text{Reg}_T^2 \le \epsilon,$

then the time-averaged policies $\bar{\pi}^1 = \frac{1}{T} \sum_{t=1}^T \pi_t^1$ and $\bar{\pi}^2 = \frac{1}{T} \sum_{t=1}^T \pi_t^2$ constitute a $2\epsilon$ -approximate Nash equilibrium:

$R^1(\bar{\pi}^1, \bar{\pi}^2) \ge \max_{\pi^1} R^1(\pi^1, \bar{\pi}^2) - 2\epsilon, \qquad R^2(\bar{\pi}^1, \bar{\pi}^2) \ge \max_{\pi^2} R^2(\bar{\pi}^1, \pi^2) - 2\epsilon.$

Consequently, any Hannan consistent single-agent reinforcement learning algorithm applied via self-play converges to the Nash equilibrium of a two-player zero-sum game.
Knowl 7 — Equivalence Between Counterfactual Regret Minimization and Policy Gradient Methods
theoretical result
In an extensive-form game with imperfect information, the counterfactual value function $Q_{\text{CF}}^i(\pi, s, a)$ of agent $i$ at information state $s \in \mathcal{S}^i$ for action $a \in \mathcal{A}(s)$ under joint policy $\pi$ is defined as:

$Q_{\text{CF}}^i(\pi, s, a) = \sum_{(h, z) \in \mathcal{Z}(s, a)} \eta_\pi^{-i}(h) \cdot \eta_\pi(z \mid ha) \cdot R^i(z),$

where $\mathcal{Z}(s, a) = \{(h, z) \in \mathcal{H} \times \mathcal{Z} \mid h \in s, ha \sqsubseteq z\}$ , and $\eta_\pi^{-i}(h) = \prod_{j \in (\mathcal{N}\setminus\{i\}) \cup \{c\}} \prod_{h': h'a' \sqsubseteq h, \tau(h')=j} \pi^j(a' \mid I(h'))$ .

The counterfactual value relates to the standard information-state action-value function $Q_\pi^i(s, a) = \frac{1}{\eta_\pi(s)} \sum_{(h, z) \in \mathcal{Z}(s, a)} \eta_\pi(h) \eta_\pi(z \mid ha) R^i(z)$ by:

$Q_{\text{CF}}^i(\pi, s, a) = Q_\pi^i(s, a) \cdot \left[ \sum_{h \in s} \eta_\pi^{-i}(h) \right].$

For a tabular policy $\pi = \{\pi^i(a|s) \mid s \in \mathcal{S}^i, a \in \mathcal{A}(s)\}$ , the policy gradient of the expected utility $R^i(\pi)$ satisfies:

$\frac{\partial R^i(\pi)}{\partial \pi^i(a|s)} = \eta_\pi(s) Q_\pi^i(s, a) = \eta_\pi^i(s) Q_{\text{CF}}^i(\pi, s, a),$

where $\eta_\pi^i(s) = \prod_{h': h'a' \sqsubseteq h, \tau(h')=i} \pi^i(a' \mid I(h'))$ for any $h \in s$ .

As a result, Advantage Actor-Critic (A2C) with generalized infinitesimal gradient ascent is structurally identical to counterfactual regret minimization (CFR), and softmax tabular A2C is equivalent to CFR with Hedge updates.
Knowl 8 — Counterfactual Regret Minimization Regret Bound and Decomposition
theoretical result
In an extensive-form game with perfect recall, the cumulative external regret $\text{Reg}_T^i$ of agent $i$ over $T$ iterations is bounded above by the sum of positive counterfactual regrets accumulated at each information state $s \in \mathcal{S}^i$ :

$\text{Reg}_T^i \le \sum_{s \in \mathcal{S}^i} \left[ \text{Reg}_T^i(s) \right]^+, \quad \text{where } [x]^+ := \max\{x, 0\},$

and the local counterfactual regret at state $s$ is:

$\text{Reg}_T^i(s) = \max_{a \in \mathcal{A}(s)} \sum_{t=1}^T \left[ Q_{\text{CF}}^i(\pi_t, s, a) - V_{\text{CF}}^i(\pi_t, s) \right],$

with $V_{\text{CF}}^i(\pi_t, s) = \sum_{a \in \mathcal{A}(s)} Q_{\text{CF}}^i(\pi_t, s, a) \cdot \pi_t^i(a|s)$ .

When each information state updates its behavioral strategy locally via regret matching, the local counterfactual regret satisfies $\text{Reg}_T^i(s) \le R_{\max}^i \sqrt{A_i} \sqrt{T}$ , which yields the overall regret bound:

$\text{Reg}_T^i \le R_{\max}^i |\mathcal{S}^i| \sqrt{A_i} \sqrt{T},$

where $R_{\max}^i = \max_{z\in\mathcal{Z}} R^i(z) - \min_{z\in\mathcal{Z}} R^i(z)$ and $A_i = \max_{h: \tau(h)=i} |\mathcal{A}(h)|$ . In two-player zero-sum extensive-form games, self-play CFR guarantees that the time-average joint policy profile converges to an $\epsilon$ -Nash equilibrium at an $O(1/\sqrt{T})$ rate.
Knowl 9 — Discrete-Time Mean-Field Games Model and Equilibrium
definition
A discrete-time Mean-Field Game (MFG) models sequential decision-making for an infinite population of symmetric, interchangeable agents. For a representative agent $i$ , let $s_t^i \in \mathcal{S}$ and $a_t^i \in \mathcal{A}$ denote its local state and action at time step $t$ . The collective distribution of the population states is given by the mean-field term $\mu_t \in \Delta(\mathcal{S})$ .

At time $t$ , given state $s_t^i$ , action $a_t^i$ , and mean field $\mu_t$ , agent $i$ receives immediate reward $R(s_t^i, a_t^i, \mu_t)$ and its local state evolves according to transition kernel:

$s_{t+1}^i \sim \mathcal{P}(\cdot \mid s_t^i, a_t^i, \mu_t) \in \Delta(\mathcal{S}).$

From the viewpoint of an individual agent, the interaction reduces to a time-varying Markov Decision Process parameterized by the deterministic sequence of mean-field measures $\boldsymbol{\mu} = \{\mu_t\}_{t \ge 0}$ .

A Mean-Field Equilibrium (MFE) is a pair $(\pi^*, \boldsymbol{\mu}^*) = (\{\pi_t^*\}_{t\ge 0}, \{\mu_t^*\}_{t\ge 0})$ satisfying two conditions:
1. Policy optimality: $\pi^*$ is an optimal policy for the time-varying MDP specified by $\boldsymbol{\mu}^*$ : $\pi^* \in \arg\max_\pi \mathbb{E}\left[ \sum_{t=0}^\infty \gamma^t R(s_t, a_t, \mu_t^*) \;\middle|\; a_t \sim \pi_t(\cdot|s_t), s_{t+1} \sim \mathcal{P}(\cdot|s_t, a_t, \mu_t^*) \right].$
2. Mean-field consistency: The measure flow $\boldsymbol{\mu}^*$ is the exact forward state distribution flow generated when all agents execute policy $\pi^*$ from initial distribution $\mu_0$ : $\mu_{t+1}^*(s') = \sum_{s \in \mathcal{S}} \sum_{a \in \mathcal{A}} \mathcal{P}(s' \mid s, a, \mu_t^*) \pi_t^*(a \mid s) \mu_t^*(s), \quad \forall s' \in \mathcal{S}, \; t \ge 0.$
Knowl 10 — Nash-Q Learning Operator for General-Sum Markov Games
model/method
Nash-Q learning extends Q-learning to $N$ -player general-sum Markov games by maintaining $N$ action-value functions $Q_N = (Q^1, \dots, Q^N) : \mathcal{S} \times \mathcal{A} \to \mathbb{R}^N$ . Letting $R_N(s,a,s') = (R^1(s,a,s'), \dots, R^N(s,a,s'))$ , the theoretical multi-agent Bellman operator $T^*$ is defined by:

$(T^* Q_N)(s, a) = \mathbb{E}_{s' \sim \mathcal{P}(\cdot|s,a)} \left[ R_N(s, a, s') + \gamma \cdot \text{Nash}\left[ Q_N(s', \cdot) \right] \right], \quad \forall (s, a) \in \mathcal{S} \times \mathcal{A},$

where $\text{Nash}[Q_N(s', \cdot)] \in \mathbb{R}^N$ denotes the vector of expected payoffs under a selected Nash equilibrium of the static stage game with payoff matrices $Q^1(s', \cdot), \dots, Q^N(s', \cdot)$ .

The sample-based Nash-Q update for agent $i \in \mathcal{N}$ given experience tuple $(s_t, a_t, r_t^1, \dots, r_t^N, s_{t+1})$ is:

$Q^i(s_t, a_t) \leftarrow (1 - \alpha_t) Q^i(s_t, a_t) + \alpha_t \left[ r_t^i + \gamma \cdot \text{Nash}^i\left[ Q_N(s_{t+1}, \cdot) \right] \right].$

Because stage-game Nash equilibria can be non-unique and discontinuous with respect to payoff matrices, $T^*$ is generally not a contraction mapping. Convergence of Nash-Q learning to a stationary Markov Nash equilibrium is guaranteed only under the restrictive assumption that every stage game encountered during training possesses a unique Nash equilibrium or a global optimum.
Knowl 11 — Instabilities and Pathologies of Multi-Agent Policy Gradient Dynamics in Continuous Games
theoretical result
In continuous multi-agent games with parameterized policies, updating policies along individual policy gradients corresponds to continuous-time Gradient Descent Ascent (GDA) dynamics:

$\frac{d\theta^i}{dt} = \nabla_{\theta^i} J^i(\theta^1, \dots, \theta^N), \quad \forall i \in \mathcal{N},$

where $J^i(\theta)$ is the expected return of agent $i$ parameterized by $\theta^i$ .

In non-cooperative settings, the Jacobian $J(\theta)$ of the game vector field decomposes into a symmetric component (potential game dynamics) and an antisymmetric component (Hamiltonian game dynamics). The presence of the Hamiltonian component introduces structural failure modes for vanilla policy gradient methods:
1. Non-convergence and limit cycles: The rotational dynamics induced by the antisymmetric component cause policy parameters to oscillate in persistent limit cycles around local Nash equilibria rather than converging.
2. Non-Nash stable attractors: Stable limit points of GDA dynamics exist that do not correspond to local Nash equilibria.
To stabilize convergence and eliminate limit cycling, curvature-regularized vector fields such as Symplectic Gradient Adjustment (SGA) adjust the update by:

$\Delta \theta^i = \nabla_{\theta^i} J^i(\theta) - \xi \sum_{j \neq i} \nabla_{\theta^i \theta^j}^2 J^j(\theta) \nabla_{\theta^j} J^j(\theta),$

where $\xi > 0$ dampens rotational oscillations, ensuring that stable stationary points of the modified dynamics coincide with local Nash equilibria.

Coverage note — Omitted high-level descriptions of domain-specific empirical applications (Go, Poker, Dota 2, StarCraft II, UAVs) and general background on single-agent MDPs and standard single-agent value/policy iteration, as they do not constitute core theoretical MARL contributions of the chapter.

References

1.Silver, D., Huang, A., Maddison, C.J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al.: Mastering the game of Go with deep neural networks and tree search. Nature 529(7587), 484–489 (2016)
2.Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al.: Mastering the game of Go without human knowledge. Nature 550(7676), 354 (2017)
3.OpenAI: Openai five. https://blog.openai.com/openai-five/ (2018)
4.Vinyals, O., Babuschkin, I., Chung, J., Mathieu, M., Jaderberg, M., Czarnecki, W.M., Dudzik, A., Huang, A., Georgiev, P., Powell, R., Ewalds, T., Horgan, D., Kroiss, M., Danihelka, I., Agapiou, J., Oh, J., Dalibard, V., Choi, D., Sifre, L., Sulsky, Y., Vezhnevets, S., Molloy, J., Cai, T., Budden, D., Paine, T., Gulcehre, C., Wang, Z., Pfaff, T., Pohlen, T., Wu, Y., Yogatama, D., Cohen, J., McKinney, K., Smith, O., Schaul, T., Lillicrap, T., Apps, C., Kavukcuoglu, K., Hassabis, D., Silver, D.: AlphaStar: Mastering the Real-Time Strategy Game StarCraft II. https://deepmind.com/blog/alphastar-mastering-real-time-strategy-game-starcraft-ii/ (2019)
5.Kober, J., Bagnell, J.A., Peters, J.: Reinforcement learning in robotics: A survey. International Journal of Robotics Research 32(11), 1238–1274 (2013)
6.Lillicrap, T.P., Hunt, J.J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., Wierstra, D.: Continuous control with deep reinforcement learning. In: International Conference on Learning Representations (2016)
7.Brown, N., Sandholm, T.: Libratus: the superhuman ai for no-limit Poker. In: International Joint Conference on Artificial Intelligence, pp. 5226–5228 (2017)
8.Brown, N., Sandholm, T.: Superhuman AI for multiplayer Poker. Science 365, 885–890 (2019)
9.Shalev-Shwartz, S., Shammah, S., Shashua, A.: Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1610.03295 (2016)
10.Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A.A., Veness, J., Bellemare, M.G., Graves, A., Riedmiller, M., Fidjeland, A.K., Ostrovski, G., et al.: Human-level control through deep reinforcement learning. Nature 518(7540), 529–533 (2015)
11.Busoniu, L., Babuska, R., De Schutter, B., et al.: A comprehensive survey of multiagent reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C 38(2), 156–172 (2008)
12.Adler, J.L., Blue, V.J.: A cooperative multi-agent transportation management and route guidance system. Transportation Research Part C: Emerging Technologies 10(5), 433–454 (2002)
13.Wang, S., Wan, J., Zhang, D., Li, D., Zhang, C.: Towards smart factory for industry 4.0: A self-organized multi-agent system with big data based feedback and coordination. Computer Networks 101, 158–168 (2016)
14.O, J., Lee, J.W., Zhang, B.T.: Stock trading system using reinforcement learning with cooperative agents. In: International Conference on Machine Learning, pp. 451–458 (2002)
15.Lee, J.W., Park, J., Jangmin, O., Lee, J., Hong, E.: A multiagent approach to Q-learning for daily stock trading. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans 37(6), 864–877 (2007)
16.Cortes, J., Martinez, S., Karatas, T., Bullo, F.: Coverage control for mobile sensing networks. IEEE Transactions on Robotics and Automation 20(2), 243–255 (2004)
17.Choi, J., Oh, S., Horowitz, R.: Distributed learning and cooperative control for multi-agent systems. Automatica 45(12), 2802–2814 (2009)
18.Castelfranchi, C.: The theory of social functions: Challenges for computational social science and multi-agent learning. Cognitive Systems Research 2(1), 5–38 (2001)
19.Leibo, J.Z., Zambaldi, V., Lanctot, M., Marecki, J., Graepel, T.: Multi-agent reinforcement learning in sequential social dilemmas. In: International Conference on Autonomous Agents and Multi-Agent Systems, pp. 464–473 (2017)
20.Hernandez-Leal, P., Kartal, B., Taylor, M.E.: A survey and critique of multiagent deep reinforcement learning. arXiv preprint arXiv:1810.05587 (2018)
21.Foerster, J., Assael, Y.M., de Freitas, N., Whiteson, S.: Learning to communicate with deep multi-agent reinforcement learning. In: Advances in Neural Information Processing Systems, pp. 2137–2145 (2016)
22.Zazo, S., Macua, S.V., Sánchez-Fernández, M., Zazo, J.: Dynamic potential games with constraints: Fundamentals and applications in communications. IEEE Transactions on Signal Processing 64(14), 3806–3821 (2016)
23.Zhang, K., Yang, Z., Liu, H., Zhang, T., Bas¸ar, T.: Fully decentralized multi-agent reinforcement learning with networked agents. In: International Conference on Machine Learning, pp. 5867–5876 (2018)
24.Subramanian, J., Mahajan, A.: Reinforcement learning in stationary mean-field games. In: International Conference on Autonomous Agents and Multi-Agent Systems, pp. 251–259 (2019)
25.Heinrich, J., Silver, D.: Deep reinforcement learning from self-play in imperfect-information games. arXiv preprint arXiv:1603.01121 (2016)
26.Lowe, R., Wu, Y., Tamar, A., Harb, J., Abbeel, P., Mordatch, I.: Multi-agent actor-critic for mixed cooperative-competitive environments. In: Advances in Neural Information Processing Systems, pp. 6379–6390 (2017)
27.Foerster, J., Farquhar, G., Afouras, T., Nardelli, N., Whiteson, S.: Counterfactual multi-agent policy gradients. arXiv preprint arXiv:1705.08926 (2017)
28.Gupta, J.K., Egorov, M., Kochenderfer, M.: Cooperative multi-agent control using deep reinforcement learning. In: International Conference on Autonomous Agents and Multi-Agent Systems, pp. 66–83 (2017)
29.Omidshafiei, S., Pazis, J., Amato, C., How, J.P., Vian, J.: Deep decentralized multi-task multiagent reinforcement learning under partial observability. In: International Conference on Machine Learning, pp. 2681–2690 (2017)
30.Kawamura, K., Mizukami, N., Tsuruoka, Y.: Neural fictitious self-play in imperfect information games with many players. In: Workshop on Computer Games, pp. 61–74 (2017)
31.Zhang, L., Wang, W., Li, S., Pan, G.: Monte Carlo neural fictitious self-play: Approach to approximate Nash equilibrium of imperfect-information games. arXiv preprint arXiv:1903.09569 (2019)
32.Mazumdar, E., Ratliff, L.J.: On the convergence of gradient-based learning in continuous games. arXiv preprint arXiv:1804.05464 (2018)
33.Jin, C., Netrapalli, P., Jordan, M.I.: Minmax optimization: Stable limit points of gradient descent ascent are locally optimal. arXiv preprint arXiv:1902.00618 (2019)
34.Zhang, K., Yang, Z., Bas¸ar, T.: Policy optimization provably converges to Nash equilibria in zero-sum linear quadratic games. In: Advances in Neural Information Processing Systems (2019)
35.Sidford, A., Wang, M., Yang, L.F., Ye, Y.: Solving discounted stochastic two-player games with near-optimal time and sample complexity. arXiv preprint arXiv:1908.11071 (2019)
36.Oliehoek, F.A., Amato, C.: A Concise Introduction to Decentralized POMDPs, vol. 1. Springer (2016)
37.Arslan, G., Yüksel, S.: Decentralized Q-learning for stochastic teams and games. IEEE Transactions on Automatic Control 62(4), 1545–1558 (2017)
38.Yongacoglu, B., Arslan, G., Yüksel, S.: Learning team-optimality for decentralized stochastic control and dynamic games. arXiv preprint arXiv:1903.05812 (2019)
39.Zhang, K., Miehling, E., Bas¸ar, T.: Online planning for decentralized stochastic control with partial history sharing. In: IEEE American Control Conference, pp. 167–172 (2019)
40.Hernandez-Leal, P., Kaisers, M., Baarslag, T., de Cote, E.M.: A survey of learning in multiagent environments: Dealing with non-stationarity. arXiv preprint arXiv:1707.09183 (2017)
41.Nguyen, T.T., Nguyen, N.D., Nahavandi, S.: Deep reinforcement learning for multiagent systems: A review of challenges, solutions and applications. arXiv preprint arXiv:1812.11794 (2018)
42.Oroojlooy Jadid, A., Hajinezhad, D.: A review of cooperative multi-agent deep reinforcement learning. arXiv preprint arXiv:1908.03963 (2019)
43.Zhang, K., Yang, Z., Bas¸ar, T.: Networked multi-agent reinforcement learning in continuous spaces. In: IEEE Conference on Decision and Control, pp. 2771–2776 (2018)
44.Zhang, K., Yang, Z., Liu, H., Zhang, T., Bas¸ar, T.: Finite-sample analyses for fully decentralized multi-agent reinforcement learning. arXiv preprint arXiv:1812.02783 (2018)
45.Monahan, G.E.: State of the art—A survey of partially observable Markov decision processes: Theory, models, and algorithms. Management Science 28(1), 1–16 (1982)
46.Cassandra, A.R.: Exact and approximate algorithms for partially observable Markov decision processes. Brown University (1998)
47.Bertsekas, D.P.: Dynamic Programming and Optimal Control, vol. 1. Athena Scientific Belmont, MA (2005)
48.Watkins, C.J., Dayan, P.: Q-learning. Machine Learning 8(3-4), 279–292 (1992)
49.Szepesvári, C., Littman, M.L.: A unified analysis of value-function-based reinforcement-learning algorithms. Neural Computation 11(8), 2017–2060 (1999)
50.Singh, S., Jaakkola, T., Littman, M.L., Szepesvári, C.: Convergence results for single-step on-policy reinforcement-learning algorithms. Machine Learning 38(3), 287–308 (2000)
51.Chang, H.S., Fu, M.C., Hu, J., Marcus, S.I.: An adaptive sampling algorithm for solving Markov decision processes. Operations Research 53(1), 126–139 (2005)
52.Kocsis, L., Szepesvári, C.: Bandit based Monte-Carlo planning. In: European Conference on Machine Learning, pp. 282–293. Springer (2006)
53.Coulom, R.: Efficient selectivity and backup operators in Monte-Carlo tree search. In: International Conference on Computers and Games, pp. 72–83 (2006)
54.Agrawal, R.: Sample mean based index policies by O(logn) regret for the multi-armed bandit problem. Advances in Applied Probability 27(4), 1054–1078 (1995)
55.Auer, P., Cesa-Bianchi, N., Fischer, P.: Finite-time analysis of the multiarmed bandit problem. Machine Learning 47(2-3), 235–256 (2002)
56.Jiang, D., Ekwedike, E., Liu, H.: Feedback-based tree search for reinforcement learning. In: International Conference on Machine Learning, pp. 2284–2293 (2018)
57.Shah, D., Xie, Q., Xu, Z.: On reinforcement learning using Monte-Carlo tree search with supervised learning: Non-asymptotic analysis. arXiv preprint arXiv:1902.05213 (2019)
58.Tesauro, G.: Temporal difference learning and TD-Gammon. Communications of the ACM 38(3), 58–68 (1995)
59.Tsitsiklis, J.N., Van Roy, B.: Analysis of temporal-diffference learning with function approximation. In: Advances in Neural Information Processing Systems, pp. 1075–1081 (1997)
60.Sutton, R.S., Barto, A.G.: Reinforcement Learning: An Introduction. MIT Press (2018)
61.Sutton, R.S., Szepesvári, C., Maei, H.R.: A convergent O(n) algorithm for off-policy temporal-difference learning with linear function approximation. Advances in Neural Information Processing Systems 21(21), 1609–1616 (2008)
62.Sutton, R.S., Maei, H.R., Precup, D., Bhatnagar, S., Silver, D., Szepesvári, C., Wiewiora, E.: Fast gradient-descent methods for temporal-difference learning with linear function approximation. In: International Conference on Machine Learning, pp. 993–1000 (2009)
63.Liu, B., Liu, J., Ghavamzadeh, M., Mahadevan, S., Petrik, M.: Finite-sample analysis of proximal gradient TD algorithms. In: Conference on Uncertainty in Artificial Intelligence, pp. 504–513 (2015)
64.Bhatnagar, S., Precup, D., Silver, D., Sutton, R.S., Maei, H.R., Szepesvári, C.: Convergent temporal-difference learning with arbitrary smooth function approximation. In: Advances in Neural Information Processing Systems, pp. 1204–1212 (2009)
65.Dann, C., Neumann, G., Peters, J., et al.: Policy evaluation with temporal differences: A survey and comparison. Journal of Machine Learning Research 15, 809–883 (2014)
66.Sutton, R.S., McAllester, D.A., Singh, S.P., Mansour, Y.: Policy gradient methods for reinforcement learning with function approximation. In: Advances in Neural Information Processing Systems, pp. 1057–1063 (2000)
67.Williams, R.J.: Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning 8(3-4), 229–256 (1992)
68.Baxter, J., Bartlett, P.L.: Infinite-horizon policy-gradient estimation. Journal of Artificial Intelligence Research 15, 319–350 (2001)
69.Konda, V.R., Tsitsiklis, J.N.: Actor-critic algorithms. In: Advances in Neural Information Processing Systems, pp. 1008–1014 (2000)
70.Bhatnagar, S., Sutton, R., Ghavamzadeh, M., Lee, M.: Natural actor-critic algorithms. Automatica 45(11), 2471–2482 (2009)
71.Silver, D., Lever, G., Heess, N., Degris, T., Wierstra, D., Riedmiller, M.: Deterministic policy gradient algorithms. In: International Conference on Machine Learning, pp. 387–395 (2014)
72.Schulman, J., Wolski, F., Dhariwal, P., Radford, A., Klimov, O.: Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 (2017)
73.Schulman, J., Levine, S., Abbeel, P., Jordan, M., Moritz, P.: Trust region policy optimization. In: International Conference on Machine Learning, pp. 1889–1897 (2015)
74.Haarnoja, T., Zhou, A., Abbeel, P., Levine, S.: Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. arXiv preprint arXiv:1801.01290 (2018)
75.Yang, Z., Zhang, K., Hong, M., Bas¸ar, T.: A finite sample analysis of the actor-critic algorithm. In: IEEE Conference on Decision and Control, pp. 2759–2764 (2018)
76.Zhang, K., Koppel, A., Zhu, H., Bas¸ar, T.: Global convergence of policy gradient methods to (almost) locally optimal policies. arXiv preprint arXiv:1906.08383 (2019)
77.Agarwal, A., Kakade, S.M., Lee, J.D., Mahajan, G.: Optimality and approximation with policy gradient methods in Markov decision processes. arXiv preprint arXiv:1908.00261 (2019)
78.Liu, B., Cai, Q., Yang, Z., Wang, Z.: Neural proximal/trust region policy optimization attains globally optimal policy. arXiv preprint arXiv:1906.10306 (2019)
79.Wang, L., Cai, Q., Yang, Z., Wang, Z.: Neural policy gradient methods: Global optimality and rates of convergence. arXiv preprint arXiv:1909.01150 (2019)
80.Chen, Y., Wang, M.: Stochastic primal-dual methods and sample complexity of reinforcement learning. arXiv preprint arXiv:1612.02516 (2016)
81.Wang, M.: Primal-dual π learning: Sample complexity and sublinear run time for ergodic Markov decision problems. arXiv preprint arXiv:1710.06100 (2017)
82.Shapley, L.S.: Stochastic games. Proceedings of the National Academy of Sciences 39(10), 1095–1100 (1953)
83.Littman, M.L.: Markov games as a framework for multi-agent reinforcement learning. In: International Conference on Machine Learning, pp. 157–163 (1994)
84.Filar, J., Vrieze, K.: Competitive Markov Decision Processes. Springer Science & Business Media (2012)
85.Bas¸ar, T., Olsder, G.J.: Dynamic Noncooperative Game Theory, vol. 23. SIAM (1999)
86.Boutilier, C.: Planning, learning and coordination in multi-agent decision processes. In: Conference on Theoretical Aspects of Rationality and Knowledge, pp. 195–210 (1996)
87.Lauer, M., Riedmiller, M.: An algorithm for distributed reinforcement learning in cooperative multi-agent systems. In: International Conference on Machine Learning (2000)
88.Yoshikawa, T.: Decomposition of dynamic team decision problems. IEEE Transactions on Automatic Control 23(4), 627–632 (1978)
89.Ho, Y.C.: Team decision theory and information structures. Proceedings of the IEEE 68(6), 644–654 (1980)
90.Wang, X., Sandholm, T.: Reinforcement learning to play an optimal Nash equilibrium in team Markov games. In: Advances in Neural Information Processing Systems, pp. 1603–1610 (2003)
91.Mahajan, A.: Sequential decomposition of sequential dynamic teams: Applications to real-time communication and networked control systems. Ph.D. thesis, University of Michigan (2008)
92.González-Sánchez, D., Hernández-Lerma, O.: Discrete-Time Stochastic Control and Dynamic Potential Games: The Euler-Equation Approach. Springer Science & Business Media (2013)
93.Valcarcel Macua, S., Zazo, J., Zazo, S.: Learning parametric closed-loop policies for Markov potential games. In: International Conference on Learning Representations (2018)
94.Kar, S., Moura, J.M., Poor, H.V.: QD-learning: A collaborative distributed strategy for multiagent reinforcement learning through consensus + innovations. IEEE Transactions on Signal Processing 61(7), 1848–1862 (2013)
95.Doan, T., Maguluri, S., Romberg, J.: Finite-time analysis of distributed TD (0) with linear function approximation on multi-agent reinforcement learning. In: International Conference on Machine Learning, pp. 1626–1635 (2019)
96.Wai, H.T., Yang, Z., Wang, Z., Hong, M.: Multi-agent reinforcement learning via double averaging primal-dual optimization. In: Advances in Neural Information Processing Systems, pp. 9649–9660 (2018)
97.OpenAI: Openai dota 2 1v1 bot. https://openai.com/the-international/ (2017)
98.Jacobson, D.: Optimal stochastic linear systems with exponential performance criteria and their relation to deterministic differential games. IEEE Transactions on Automatic Control 18(2), 124–131 (1973)
99.Bas¸ar, T., Bernhard, P.: H∞ Optimal Control and Related Minimax Design Problems: A Dynamic Game Approach. Birkhäuser, Boston. (1995)
100.Zhang, K., Hu, B., Bas¸ar, T.: Policy optimization for H2 linear control with H∞ robustness guarantee: Implicit regularization and global convergence. arXiv preprint arXiv:1910.09496 (2019)
101.Hu, J., Wellman, M.P.: Nash Q-learning for general-sum stochastic games. Journal of Machine Learning Research 4(Nov), 1039–1069 (2003)
102.Littman, M.L.: Friend-or-Foe Q-learning in general-sum games. In: International Conference on Machine Learning, pp. 322–328 (2001)
103.Lagoudakis, M.G., Parr, R.: Learning in zero-sum team Markov games using factored value functions. In: Advances in Neural Information Processing Systems, pp. 1659–1666 (2003)
104.Bernstein, D.S., Givan, R., Immerman, N., Zilberstein, S.: The complexity of decentralized control of Markov decision processes. Mathematics of Operations Research 27(4), 819–840 (2002)
105.Osborne, M.J., Rubinstein, A.: A Course in Game Theory. MIT Press (1994)
106.Shoham, Y., Leyton-Brown, K.: Multiagent Systems: Algorithmic, Game-theoretic, and Logical Foundations. Cambridge University Press (2008)
107.Koller, D., Megiddo, N.: The complexity of two-person zero-sum games in extensive form. Games and Economic Behavior 4(4), 528–552 (1992)
108.Kuhn, H.: Extensive games and the problem op information. Contributions to the Theory of Games 2, 193–216 (1953)
109.Zinkevich, M., Johanson, M., Bowling, M., Piccione, C.: Regret minimization in games with incomplete information. In: Advances in Neural Information Processing Systems, pp. 1729–1736 (2008)
110.Heinrich, J., Lanctot, M., Silver, D.: Fictitious self-play in extensive-form games. In: International Conference on Machine Learning, pp. 805–813 (2015)
111.Srinivasan, S., Lanctot, M., Zambaldi, V., Pérolat, J., Tuyls, K., Munos, R., Bowling, M.: Actor-critic policy optimization in partially observable multiagent environments. In: Advances in Neural Information Processing Systems, pp. 3422–3435 (2018)
112.Omidshafiei, S., Hennes, D., Morrill, D., Munos, R., Perolat, J., Lanctot, M., Gruslys, A., Lespiau, J.B., Tuyls, K.: Neural replicator dynamics. arXiv preprint arXiv:1906.00190 (2019)
113.Rubin, J., Watson, I.: Computer Poker: A review. Artificial Intelligence 175(5-6), 958–987 (2011)
114.Lanctot, M., Lockhart, E., Lespiau, J.B., Zambaldi, V., Upadhyay, S., Pérolat, J., Srinivasan, S., Timbers, F., Tuyls, K., Omidshafiei, S., et al.: Openspiel: A framework for reinforcement learning in games. arXiv preprint arXiv:1908.09453 (2019)
115.Claus, C., Boutilier, C.: The dynamics of reinforcement learning in cooperative multiagent systems. AAAI Conference on Artificial Intelligence 1998(746-752), 2 (1998)
116.Bowling, M., Veloso, M.: Rational and convergent learning in stochastic games. In: International Joint Conference on Artificial Intelligence, vol. 17, pp. 1021–1026 (2001)
117.Kapetanakis, S., Kudenko, D.: Reinforcement learning of coordination in cooperative multiagent systems. AAAI Conference on Artificial Intelligence 2002, 326–331 (2002)
118.Conitzer, V., Sandholm, T.: Awesome: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents. Machine Learning 67(1-2), 23–43 (2007)
119.Hansen, E.A., Bernstein, D.S., Zilberstein, S.: Dynamic programming for partially observable stochastic games. In: AAAI Conference on Artificial Intelligence, pp. 709–715 (2004)
120.Amato, C., Chowdhary, G., Geramifard, A., Üre, N.K., Kochenderfer, M.J.: Decentralized control of partially observable markov decision processes. In: IEEE Conference on Decision and Control, pp. 2398–2405 (2013)
121.Amato, C., Oliehoek, F.A.: Scalable planning and learning for multiagent POMDPs. In: AAAI Conference on Artificial Intelligence (2015)
122.Shoham, Y., Powers, R., Grenager, T.: Multi-agent reinforcement learning: A critical survey. Technical Report (2003)
123.Zinkevich, M., Greenwald, A., Littman, M.L.: Cyclic equilibria in Markov games. In: Advances in Neural Information Processing Systems, pp. 1641–1648 (2006)
124.Bowling, M., Veloso, M.: Multiagent learning using a variable learning rate. Artificial Intelligence 136(2), 215–250 (2002)
125.Bowling, M.: Convergence and no-regret in multiagent learning. In: Advances in Neural Information Processing Systems, pp. 209–216 (2005)
126.Blum, A., Mansour, Y.: Learning, regret minimization, and equilibria. Algorithmic Game Theory pp. 79–102 (2007)
127.Hart, S., Mas-Colell, A.: A reinforcement procedure leading to correlated equilibrium. In: Economics Essays, pp. 181–200. Springer (2001)
128.Kasai, T., Tenmoto, H., Kamiya, A.: Learning of communication codes in multi-agent reinforcement learning problem. In: IEEE Conference on Soft Computing in Industrial Applications, pp. 1–6 (2008)
129.Kim, D., Moon, S., Hostallero, D., Kang, W.J., Lee, T., Son, K., Yi, Y.: Learning to schedule communication in multi-agent reinforcement learning. In: International Conference on Learning Representations (2019)
130.Chen, T., Zhang, K., Giannakis, G.B., Bas¸ar, T.: Communication-efficient distributed reinforcement learning. arXiv preprint arXiv:1812.03239 (2018)
131.Lin, Y., Zhang, K., Yang, Z., Wang, Z., Bas¸ar, T., Sandhu, R., Liu, J.: A communication-efficient multi-agent actor-critic algorithm for distributed reinforcement learning. In: IEEE Conference on Decision and Control (2019)
132.Ren, J., Haupt, J.: A communication efficient hierarchical distributed optimization algorithm for multi-agent reinforcement learning. In: Real-world Sequential Decision Making Workshop at International Conference on Machine Learning (2019)
133.Kim, W., Cho, M., Sung, Y.: Message-dropout: An efficient training method for multi-agent deep reinforcement learning. In: AAAI Conference on Artificial Intelligence (2019)
134.He, H., Boyd-Graber, J., Kwok, K., Daumé III, H.: Opponent modeling in deep reinforcement learning. In: International Conference on Machine Learning, pp. 1804–1813 (2016)
135.Grover, A., Al-Shedivat, M., Gupta, J., Burda, Y., Edwards, H.: Learning policy representations in multiagent systems. In: International Conference on Machine Learning, pp. 1802–1811 (2018)
136.Gao, C., Mueller, M., Hayward, R.: Adversarial policy gradient for alternating Markov games. In: Workshop at International Conference on Learning Representations (2018)
137.Li, S., Wu, Y., Cui, X., Dong, H., Fang, F., Russell, S.: Robust multi-agent reinforcement learning via minimax deep deterministic policy gradient. In: AAAI Conference on Artificial Intelligence (2019)
138.Zhang, X., Zhang, K., Miehling, E., Basar, T.: Non-cooperative inverse reinforcement learning. In: Advances in Neural Information Processing Systems, pp. 9482–9493 (2019)
139.Tan, M.: Multi-agent reinforcement learning: Independent vs. cooperative agents. In: International Conference on Machine Learning, pp. 330–337 (1993)
140.Matignon, L., Laurent, G.J., Le Fort-Piat, N.: Independent reinforcement learners in cooperative Markov games: A survey regarding coordination problems. The Knowledge Engineering Review 27(1), 1–31 (2012)
141.Foerster, J., Nardelli, N., Farquhar, G., Torr, P., Kohli, P., Whiteson, S., et al.: Stabilising experience replay for deep multi-agent reinforcement learning. In: International Conference of Machine Learning, pp. 1146–1155 (2017)
142.Tuyls, K., Weiss, G.: Multiagent learning: Basics, challenges, and prospects. AI Magazine 33(3), 41–41 (2012)
143.Guestrin, C., Lagoudakis, M., Parr, R.: Coordinated reinforcement learning. In: International Conference on Machine Learning, pp. 227–234 (2002)
144.Guestrin, C., Koller, D., Parr, R.: Multiagent planning with factored MDPs. In: Advances in Neural Information Processing Systems, pp. 1523–1530 (2002)
145.Kok, J.R., Vlassis, N.: Sparse cooperative Q-learning. In: International Conference on Machine learning, pp. 61–69 (2004)
146.Sunehag, P., Lever, G., Gruslys, A., Czarnecki, W.M., Zambaldi, V., Jaderberg, M., Lanctot, M., Sonnerat, N., Leibo, J.Z., Tuyls, K., et al.: Value-decomposition networks for cooperative multi-agent learning based on team reward. In: International Conference on Autonomous Agents and Multi-Agent Systems, pp. 2085–2087 (2018)
147.Rashid, T., Samvelyan, M., De Witt, C.S., Farquhar, G., Foerster, J., Whiteson, S.: QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning. In: International Conference on Machine learning, pp. 681–689 (2018)
148.Qu, G., Li, N.: Exploiting fast decaying and locality in multi-agent MDP with tree dependence structure. In: IEEE Conference on Decision and Control (2019)
149.Mahajan, A.: Optimal decentralized control of coupled subsystems with control sharing. IEEE Transactions on Automatic Control 58(9), 2377–2382 (2013)
150.Oliehoek, F.A., Amato, C.: Dec-POMDPs as non-observable MDPs. IAS Technical Report (IAS-UVA-14-01) (2014)
151.Foerster, J.N., Farquhar, G., Afouras, T., Nardelli, N., Whiteson, S.: Counterfactual multiagent policy gradients. In: AAAI Conference on Artificial Intelligence (2018)
152.Dibangoye, J., Buffet, O.: Learning to act in decentralized partially observable MDPs. In: International Conference on Machine Learning, pp. 1233–1242 (2018)
153.Kraemer, L., Banerjee, B.: Multi-agent reinforcement learning as a rehearsal for decentralized planning. Neurocomputing 190, 82–94 (2016)
154.Macua, S.V., Chen, J., Zazo, S., Sayed, A.H.: Distributed policy evaluation under multiple behavior strategies. IEEE Transactions on Automatic Control 60(5), 1260–1274 (2015)
155.Macua, S.V., Tukiainen, A., Hernández, D.G.O., Baldazo, D., de Cote, E.M., Zazo, S.: Diff-dac: Distributed actor-critic for average multitask deep reinforcement learning. arXiv preprint arXiv:1710.10363 (2017)
156.Lee, D., Yoon, H., Hovakimyan, N.: Primal-dual algorithm for distributed reinforcement learning: Distributed GTD. In: IEEE Conference on Decision and Control, pp. 1967–1972 (2018)
157.Doan, T.T., Maguluri, S.T., Romberg, J.: Finite-time performance of distributed temporal difference learning with linear function approximation. arXiv preprint arXiv:1907.12530 (2019)
158.Suttle, W., Yang, Z., Zhang, K., Wang, Z., Bas¸ar, T., Liu, J.: A multi-agent off-policy actor-critic algorithm for distributed reinforcement learning. arXiv preprint arXiv:1903.06372 (2019)
159.Littman, M.L.: Value-function reinforcement learning in Markov games. Cognitive Systems Research 2(1), 55–66 (2001)
160.Young, H.P.: The evolution of conventions. Econometrica: Journal of the Econometric Society pp. 57–84 (1993)
161.Son, K., Kim, D., Kang, W.J., Hostallero, D.E., Yi, Y.: QTRAN: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In: International Conference on Machine Learning, pp. 5887–5896 (2019)
162.Perolat, J., Piot, B., Pietquin, O.: Actor-critic fictitious play in simultaneous move multistage games. In: International Conference on Artificial Intelligence and Statistics (2018)
163.Monderer, D., Shapley, L.S.: Potential games. Games and Economic Behavior 14(1), 124–143 (1996)
164.Bas¸ar, T., Zaccour, G.: Handbook of Dynamic Game Theory. Springer (2018)
165.Huang, M., Caines, P.E., Malhamé, R.P.: Individual and mass behaviour in large population stochastic wireless power control problems: Centralized and Nash equilibrium solutions. In: IEEE Conference on Decision and Control, pp. 98–103 (2003)
166.Huang, M., Malhamé, R.P., Caines, P.E., et al.: Large population stochastic dynamic games: Closed-loop Mckean-Vlasov systems and the Nash certainty equivalence principle. Communications in Information & Systems 6(3), 221–252 (2006)
167.Lasry, J.M., Lions, P.L.: Mean field games. Japanese Journal of Mathematics 2(1), 229–260 (2007)
168.Bensoussan, A., Frehse, J., Yam, P., et al.: Mean Field Games and Mean Field Type Control Theory, vol. 101. Springer (2013)
169.Tembine, H., Zhu, Q., Bas¸ar, T.: Risk-sensitive mean-field games. IEEE Transactions on Automatic Control 59(4), 835–850 (2013)
170.Arabneydi, J., Mahajan, A.: Team optimal control of coupled subsystems with mean-field sharing. In: IEEE Conference on Decision and Control, pp. 1669–1674 (2014)
171.Arabneydi, J.: New concepts in team theory: Mean field teams and reinforcement learning. Ph.D. thesis, McGill University (2017)
172.Yang, Y., Luo, R., Li, M., Zhou, M., Zhang, W., Wang, J.: Mean field multi-agent reinforcement learning. In: International Conference on Machine Learning, pp. 5571–5580 (2018)
173.Witsenhausen, H.S.: Separation of estimation and control for discrete time systems. Proceedings of the IEEE 59(11), 1557–1566 (1971)
174.Yüksel, S., Bas¸ar, T.: Stochastic Networked Control Systems: Stabilization and Optimization Under Information Constraints. Springer Science & Business Media (2013)
175.Subramanian, J., Seraj, R., Mahajan, A.: Reinforcement learning for mean-field teams. In: Workshop on Adaptive and Learning Agents at International Conference on Autonomous Agents and Multi-Agent Systems (2018)
176.Arabneydi, J., Mahajan, A.: Linear quadratic mean field teams: Optimal and approximately optimal decentralized solutions. arXiv preprint arXiv:1609.00056 (2016)
177.Carmona, R., Laurière, M., Tan, Z.: Linear-quadratic mean-field reinforcement learning: Convergence of policy gradient methods. arXiv preprint arXiv:1910.04295 (2019)
178.Carmona, R., Laurière, M., Tan, Z.: Model-free mean-field reinforcement learning: Mean-field MDP and mean-field Q-learning. arXiv preprint arXiv:1910.12802 (2019)
179.Rabbat, M., Nowak, R.: Distributed optimization in sensor networks. In: International Symposium on Information Processing in Sensor Networks, pp. 20–27 (2004)
180.Dall’Anese, E., Zhu, H., Giannakis, G.B.: Distributed optimal power flow for smart microgrids. IEEE Transactions on Smart Grid 4(3), 1464–1475 (2013)
181.Zhang, K., Shi, W., Zhu, H., Dall’Anese, E., Bas¸ar, T.: Dynamic power distribution system management with a locally connected communication network. IEEE Journal of Selected Topics in Signal Processing 12(4), 673–687 (2018)
182.Zhang, K., Lu, L., Lei, C., Zhu, H., Ouyang, Y.: Dynamic operations and pricing of electric unmanned aerial vehicle systems and power networks. Transportation Research Part C: Emerging Technologies 92, 472–485 (2018)
183.Corke, P., Peterson, R., Rus, D.: Networked robots: Flying robot navigation using a sensor net. Robotics Research pp. 234–243 (2005)
184.Zhang, K., Liu, Y., Liu, J., Liu, M., Bas¸ar, T.: Distributed learning of average belief over networks using sequential observations. Automatica (2019)
185.Nedic, A., Ozdaglar, A.: Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control 54(1), 48–61 (2009)
186.Agarwal, A., Duchi, J.C.: Distributed delayed stochastic optimization. In: Advances in Neural Information Processing Systems, pp. 873–881 (2011)
187.Jakovetic, D., Xavier, J., Moura, J.M.: Cooperative convex optimization in networked systems: Augmented lagrangian algorithms with directed gossip communication. IEEE Transactions on Signal Processing 59(8), 3889–3902 (2011)
188.Tu, S.Y., Sayed, A.H.: Diffusion strategies outperform consensus strategies for distributed estimation over adaptive networks. IEEE Transactions on Signal Processing 60(12), 6217–6234 (2012)
189.Varshavskaya, P., Kaelbling, L.P., Rus, D.: Efficient distributed reinforcement learning through agreement. In: Distributed Autonomous Robotic Systems, pp. 367–378 (2009)
190.Ciosek, K., Whiteson, S.: Expected policy gradients for reinforcement learning. arXiv preprint arXiv:1801.03326 (2018)
191.Sutton, R.S., Mahmood, A.R., White, M.: An emphatic approach to the problem of off-policy temporal-difference learning. Journal of Machine Learning Research 17(1), 2603–2631 (2016)
192.Yu, H.: On convergence of emphatic temporal-difference learning. In: Conference on Learning Theory, pp. 1724–1751 (2015)
193.Zhang, Y., Zavlanos, M.M.: Distributed off-policy actor-critic reinforcement learning with policy consensus. arXiv preprint arXiv:1903.09255 (2019)
194.Pennesi, P., Paschalidis, I.C.: A distributed actor-critic algorithm and applications to mobile sensor network coordination problems. IEEE Transactions on Automatic Control 55(2), 492–497 (2010)
195.Lange, S., Gabel, T., Riedmiller, M.: Batch reinforcement learning. In: Reinforcement Learning, pp. 45–73. Springer (2012)
196.Riedmiller, M.: Neural fitted Q iteration–first experiences with a data efficient neural reinforcement learning method. In: European Conference on Machine Learning, pp. 317–328 (2005)
197.Antos, A., Szepesvári, C., Munos, R.: Fitted Q-iteration in continuous action-space MDPs. In: Advances in Neural Information Processing Systems, pp. 9–16 (2008)
198.Hong, M., Chang, T.H.: Stochastic proximal gradient consensus over random networks. IEEE Transactions on Signal Processing 65(11), 2933–2948 (2017)
199.Nedic, A., Olshevsky, A., Shi, W.: Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization 27(4), 2597–2633 (2017)
200.Munos, R.: Performance bounds in `p-norm for approximate value iteration. SIAM Journal on Control and Optimization 46(2), 541–561 (2007)
201.Munos, R., Szepesvári, C.: Finite-time bounds for fitted value iteration. Journal of Machine Learning Research 9(May), 815–857 (2008)
202.Antos, A., Szepesvári, C., Munos, R.: Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning 71(1), 89–129 (2008)
203.Farahmand, A.m., Szepesvári, C., Munos, R.: Error propagation for approximate policy and value iteration. In: Advances in Neural Information Processing Systems, pp. 568–576 (2010)
204.Cassano, L., Yuan, K., Sayed, A.H.: Multi-agent fully decentralized off-policy learning with linear convergence rates. arXiv preprint arXiv:1810.07792 (2018)
205.Qu, G., Li, N.: Harnessing smoothness to accelerate distributed optimization. IEEE Transactions on Control of Network Systems 5(3), 1245–1260 (2017)
206.Schmidt, M., Le Roux, N., Bach, F.: Minimizing finite sums with the stochastic average gradient. Mathematical Programming 162(1-2), 83–112 (2017)
207.Ying, B., Yuan, K., Sayed, A.H.: Convergence of variance-reduced learning under random reshuffling. In: IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 2286–2290 (2018)
208.Singh, S.P., Sutton, R.S.: Reinforcement learning with replacing eligibility traces. Machine Learning 22(1-3), 123–158 (1996)
209.Bhandari, J., Russo, D., Singal, R.: A finite time analysis of temporal difference learning with linear function approximation. In: Conference On Learning Theory, pp. 1691–1692 (2018)
210.Srikant, R., Ying, L.: Finite-time error bounds for linear stochastic approximation and TD learning. In: Conference on Learning Theory, pp. 2803–2830 (2019)
211.Stanković, M.S., Stanković, S.S.: Multi-agent temporal-difference learning with linear function approximation: Weak convergence under time-varying network topologies. In: IEEE American Control Conference, pp. 167–172 (2016)
212.Stanković, M.S., Ilić, N., Stanković, S.S.: Distributed stochastic approximation: Weak convergence and network design. IEEE Transactions on Automatic Control 61(12), 4069–4074 (2016)
213.Zhang, H., Jiang, H., Luo, Y., Xiao, G.: Data-driven optimal consensus control for discrete-time multi-agent systems with unknown dynamics using reinforcement learning method. IEEE Transactions on Industrial Electronics 64(5), 4091–4100 (2016)
214.Zhang, Q., Zhao, D., Lewis, F.L.: Model-free reinforcement learning for fully cooperative multi-agent graphical games. In: International Joint Conference on Neural Networks, pp. 1–6 (2018)
215.Bernstein, D.S., Amato, C., Hansen, E.A., Zilberstein, S.: Policy iteration for decentralized control of Markov decision processes. Journal of Artificial Intelligence Research 34, 89–132 (2009)
216.Amato, C., Bernstein, D.S., Zilberstein, S.: Optimizing fixed-size stochastic controllers for POMDPs and decentralized POMDPs. Autonomous Agents and Multi-Agent Systems 21(3), 293–320 (2010)
217.Liu, M., Amato, C., Liao, X., Carin, L., How, J.P.: Stick-breaking policy learning in Dec-POMDPs. In: International Joint Conference on Artificial Intelligence (2015)
218.Dibangoye, J.S., Amato, C., Buffet, O., Charpillet, F.: Optimally solving Dec-POMDPs as continuous-state MDPs. Journal of Artificial Intelligence Research 55, 443–497 (2016)
219.Wu, F., Zilberstein, S., Chen, X.: Rollout sampling policy iteration for decentralized POMDPs. In: Conference on Uncertainty in Artificial Intelligence (2010)
220.Wu, F., Zilberstein, S., Jennings, N.R.: Monte-Carlo expectation maximization for decentralized POMDPs. In: International Joint Conference on Artificial Intelligence (2013)
221.Best, G., Cliff, O.M., Patten, T., Mettu, R.R., Fitch, R.: Dec-MCTS: Decentralized planning for multi-robot active perception. International Journal of Robotics Research pp. 1–22 (2018)
222.Amato, C., Zilberstein, S.: Achieving goals in decentralized POMDPs. In: International Conference on Autonomous Agents and Multi-Agent Systems, pp. 593–600 (2009)
223.Banerjee, B., Lyle, J., Kraemer, L., Yellamraju, R.: Sample bounded distributed reinforcement learning for decentralized POMDPs. In: AAAI Conference on Artificial Intelligence (2012)
224.Nayyar, A., Mahajan, A., Teneketzis, D.: Decentralized stochastic control with partial history sharing: A common information approach. IEEE Transactions on Automatic Control 58(7), 1644–1658 (2013)
225.Arabneydi, J., Mahajan, A.: Reinforcement learning in decentralized stochastic control systems with partial history sharing. In: IEEE American Control Conference, pp. 5449–5456 (2015)
226.Papadimitriou, C.H.: On inefficient proofs of existence and complexity classes. In: Annals of Discrete Mathematics, vol. 51, pp. 245–250. Elsevier (1992)
227.Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. SIAM Journal on Computing 39(1), 195–259 (2009)
228.Von Neumann, J., Morgenstern, O., Kuhn, H.W.: Theory of Games and Economic Behavior (commemorative edition). Princeton University Press (2007)
229.Vanderbei, R.J., et al.: Linear Programming. Springer (2015)
230.Hoffman, A.J., Karp, R.M.: On nonterminating stochastic games. Management Science 12(5), 359–370 (1966)
231.Van Der Wal, J.: Discounted markov games: Generalized policy iteration method. Journal of Optimization Theory and Applications 25(1), 125–138 (1978)
232.Rao, S.S., Chandrasekaran, R., Nair, K.: Algorithms for discounted stochastic games. Journal of Optimization Theory and Applications 11(6), 627–637 (1973)
233.Patek, S.D.: Stochastic and shortest path games: Theory and algorithms. Ph.D. thesis, Massachusetts Institute of Technology (1997)
234.Hansen, T.D., Miltersen, P.B., Zwick, U.: Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. Journal of the ACM 60(1), 1 (2013)
235.Al-Tamimi, A., Abu-Khalaf, M., Lewis, F.L.: Adaptive critic designs for discrete-time zero-sum games with application to H∞ control. IEEE Transactions on Systems, Man, and Cybernetics, Part B 37(1), 240–247 (2007)
236.Al-Tamimi, A., Lewis, F.L., Abu-Khalaf, M.: Model-free Q-learning designs for linear discrete-time zero-sum games with application to H∞ control. Automatica 43(3), 473–481 (2007)
237.Lagoudakis, M.G., Parr, R.: Value function approximation in zero-sum Markov games. In: Conference on Uncertainty in Artificial Intelligence, pp. 283–292 (2002)
238.Farahmand, A.m., Ghavamzadeh, M., Szepesvári, C., Mannor, S.: Regularized policy iteration with nonparametric function spaces. Journal of Machine Learning Research 17(1), 4809–4874 (2016)
239.Yang, Z., Xie, Y., Wang, Z.: A theoretical analysis of deep Q-learning. arXiv preprint arXiv:1901.00137 (2019)
240.Jia, Z., Yang, L.F., Wang, M.: Feature-based Q-learning for two-player stochastic games. arXiv preprint arXiv:1906.00423 (2019)
241.Sidford, A., Wang, M., Wu, X., Yang, L., Ye, Y.: Near-optimal time and sample complexities for solving Markov decision processes with a generative model. In: Advances in Neural Information Processing Systems, pp. 5186–5196 (2018)
242.Wei, C.Y., Hong, Y.T., Lu, C.J.: Online reinforcement learning in stochastic games. In: Advances in Neural Information Processing Systems, pp. 4987–4997 (2017)
243.Auer, P., Ortner, R.: Logarithmic online regret bounds for undiscounted reinforcement learning. In: Advances in Neural Information Processing Systems, pp. 49–56 (2007)
244.Jaksch, T., Ortner, R., Auer, P.: Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research 11(Apr), 1563–1600 (2010)
245.Koller, D., Megiddo, N., von Stengel, B.: Fast algorithms for finding randomized strategies in game trees. Computing 750, 759 (1994)
246.Von Stengel, B.: Efficient computation of behavior strategies. Games and Economic Behavior 14(2), 220–246 (1996)
247.Koller, D., Megiddo, N., Von Stengel, B.: Efficient computation of equilibria for extensive two-person games. Games and economic behavior 14(2), 247–259 (1996)
248.Von Stengel, B.: Computing equilibria for two-person games. Handbook of Game Theory with Economic Applications 3, 1723–1759 (2002)
249.Parr, R., Russell, S.: Approximating optimal policies for partially observable stochastic domains. In: International Joint Conference on Artificial Intelligence, pp. 1088–1094 (1995)
250.Rodriguez, A.C., Parr, R., Koller, D.: Reinforcement learning using approximate belief states. In: Advances in Neural Information Processing Systems, pp. 1036–1042 (2000)
251.Hauskrecht, M.: Value-function approximations for partially observable Markov decision processes. Journal of Artificial Intelligence Research 13, 33–94 (2000)
252.Buter, B.J.: Dynamic programming for extensive form games with imperfect information. Ph.D. thesis, Universiteit van Amsterdam (2012)
253.Cowling, P.I., Powley, E.J., Whitehouse, D.: Information set Monte Carlo tree search. IEEE Transactions on Computational Intelligence and AI in Games 4(2), 120–143 (2012)
254.Teraoka, K., Hatano, K., Takimoto, E.: Efficient sampling method for Monte Carlo tree search problem. IEICE Transactions on Information and Systems 97(3), 392–398 (2014)
255.Whitehouse, D.: Monte Carlo tree search for games with hidden information and uncertainty. Ph.D. thesis, University of York (2014)
256.Kaufmann, E., Koolen, W.M.: Monte-Carlo tree search by best arm identification. In: Advances in Neural Information Processing Systems, pp. 4897–4906 (2017)
257.Hannan, J.: Approximation to Bayes risk in repeated play. Contributions to the Theory of Games 3, 97–139 (1957)
258.Brown, G.W.: Iterative solution of games by fictitious play. Activity Analysis of Production and Allocation 13(1), 374–376 (1951)
259.Robinson, J.: An iterative method of solving a game. Annals of Mathematics pp. 296–301 (1951)
260.Benaïm, M., Hofbauer, J., Sorin, S.: Stochastic approximations and differential inclusions. SIAM Journal on Control and Optimization 44(1), 328–348 (2005)
261.Hart, S., Mas-Colell, A.: A general class of adaptive strategies. Journal of Economic Theory 98(1), 26–54 (2001)
262.Monderer, D., Samet, D., Sela, A.: Belief affirming in learning processes. Journal of Economic Theory 73(2), 438–452 (1997)
263.Viossat, Y., Zapechelnyuk, A.: No-regret dynamics and fictitious play. Journal of Economic Theory 148(2), 825–842 (2013)
264.Kushner, H.J., Yin, G.G.: Stochastic Approximation and Recursive Algorithms and Applications. Springer, New York, NY (2003)
265.Fudenberg, D., Levine, D.K.: Consistency and cautious fictitious play. Journal of Economic Dynamics and Control 19(5-7), 1065–1089 (1995)
266.Hofbauer, J., Sandholm, W.H.: On the global convergence of stochastic fictitious play. Econometrica 70(6), 2265–2294 (2002)
267.Leslie, D.S., Collins, E.J.: Generalised weakened fictitious play. Games and Economic Behavior 56(2), 285–298 (2006)
268.Benaïm, M., Faure, M.: Consistency of vanishingly smooth fictitious play. Mathematics of Operations Research 38(3), 437–450 (2013)
269.Li, Z., Tewari, A.: Sampled fictitious play is hannan consistent. Games and Economic Behavior 109, 401–412 (2018)
270.Ernst, D., Geurts, P., Wehenkel, L.: Tree-based batch mode reinforcement learning. Journal of Machine Learning Research 6(Apr), 503–556 (2005)
271.Heinrich, J., Silver, D.: Self-play Monte-Carlo tree search in computer Poker. In: Workshops at AAAI Conference on Artificial Intelligence (2014)
272.Browne, C.B., Powley, E., Whitehouse, D., Lucas, S.M., Cowling, P.I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., Colton, S.: A survey of Monte Carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games 4(1), 1–43 (2012)
273.Sutton, R.S., Barto, A.G.: A temporal-difference model of classical conditioning. In: Proceedings of the Annual Conference of the Cognitive Science Society, pp. 355–378 (1987)
274.Borkar, V.S.: Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press (2008)
275.Cesa-Bianchi, N., Lugosi, G.: Prediction, Learning, and Games. Cambridge University Press (2006)
276.Auer, P., Cesa-Bianchi, N., Freund, Y., Schapire, R.E.: The nonstochastic multiarmed bandit problem. SIAM Journal on Computing 32(1), 48–77 (2002)
277.Vovk, V.G.: Aggregating strategies. Proceedings of Computational Learning Theory (1990)
278.Littlestone, N., Warmuth, M.K.: The weighted majority algorithm. Information and Computation 108(2), 212–261 (1994)
279.Freund, Y., Schapire, R.E.: Adaptive game playing using multiplicative weights. Games and Economic Behavior 29(1-2), 79–103 (1999)
280.Hart, S., Mas-Colell, A.: A simple adaptive procedure leading to correlated equilibrium. Econometrica 68(5), 1127–1150 (2000)
281.Lanctot, M., Waugh, K., Zinkevich, M., Bowling, M.: Monte Carlo sampling for regret minimization in extensive games. In: Advances in Neural Information Processing Systems, pp. 1078–1086 (2009)
282.Burch, N., Lanctot, M., Szafron, D., Gibson, R.G.: Efficient Monte Carlo counterfactual regret minimization in games with many player actions. In: Advances in Neural Information Processing Systems, pp. 1880–1888 (2012)
283.Gibson, R., Lanctot, M., Burch, N., Szafron, D., Bowling, M.: Generalized sampling and variance in counterfactual regret minimization. In: AAAI Conference on Artificial Intelligence (2012)
284.Johanson, M., Bard, N., Lanctot, M., Gibson, R., Bowling, M.: Efficient Nash equilibrium approximation through Monte Carlo counterfactual regret minimization. In: International Conference on Autonomous Agents and Multi-Agent Systems, pp. 837–846 (2012)
285.Lisy̌, V., Lanctot, M., Bowling, M.: Online Monte Carlo counterfactual regret minimization for search in imperfect information games. In: International Conference on Autonomous Agents and Multi-Agent Systems, pp. 27–36 (2015)
286.Schmid, M., Burch, N., Lanctot, M., Moravcik, M., Kadlec, R., Bowling, M.: Variance reduction in Monte Carlo counterfactual regret minimization (VR-MCCFR) for extensive form games using baselines. In: AAAI Conference on Artificial Intelligence, vol. 33, pp. 2157–2164 (2019)
287.Waugh, K., Morrill, D., Bagnell, J.A., Bowling, M.: Solving games with functional regret estimation. In: AAAI Conference on Artificial Intelligence (2015)
288.Morrill, D.: Using regret estimation to solve games compactly. Ph.D. thesis, University of Alberta (2016)
289.Brown, N., Lerer, A., Gross, S., Sandholm, T.: Deep counterfactual regret minimization. In: International Conference on Machine Learning, pp. 793–802 (2019)
290.Brown, N., Sandholm, T.: Regret-based pruning in extensive-form games. In: Advances in Neural Information Processing Systems, pp. 1972–1980 (2015)
291.Brown, N., Kroer, C., Sandholm, T.: Dynamic thresholding and pruning for regret minimization. In: AAAI Conference on Artificial Intelligence (2017)
292.Brown, N., Sandholm, T.: Reduced space and faster convergence in imperfect-information games via pruning. In: International Conference on Machine Learning, pp. 596–604 (2017)
293.Tammelin, O.: Solving large imperfect information games using CFR+. arXiv preprint arXiv:1407.5042 (2014)
294.Tammelin, O., Burch, N., Johanson, M., Bowling, M.: Solving heads-up limit Texas Hold’em. In: International Joint Conference on Artificial Intelligence (2015)
295.Burch, N., Moravcik, M., Schmid, M.: Revisiting CFR+ and alternating updates. Journal of Artificial Intelligence Research 64, 429–443 (2019)
296.Zhou, Y., Ren, T., Li, J., Yan, D., Zhu, J.: Lazy-CFR: A fast regret minimization algorithm for extensive games with imperfect information. arXiv preprint arXiv:1810.04433 (2018)
297.Zinkevich, M.: Online convex programming and generalized infinitesimal gradient ascent. In: International Conference on Machine Learning, pp. 928–936 (2003)
298.Lockhart, E., Lanctot, M., Pérolat, J., Lespiau, J.B., Morrill, D., Timbers, F., Tuyls, K.: Computing approximate equilibria in sequential adversarial games by exploitability descent. arXiv preprint arXiv:1903.05614 (2019)
299.Johanson, M., Bard, N., Burch, N., Bowling, M.: Finding optimal abstract strategies in extensive-form games. In: AAAI Conference on Artificial Intelligence, pp. 1371–1379 (2012)
300.Schaeffer, M.S., Sturtevant, N., Schaeffer, J.: Comparing UCT versus CFR in simultaneous games (2009)
301.Lanctot, M., Lisý, V., Winands, M.H.: Monte Carlo tree search in simultaneous move games with applications to Goofspiel. In: Workshop on Computer Games, pp. 28–43 (2013)
302.Lisý, V., Kovařík, V., Lanctot, M., Bošanský, B.: Convergence of Monte Carlo tree search in simultaneous move games. In: Advances in Neural Information Processing Systems, pp. 2112–2120 (2013)
303.Tak, M.J., Lanctot, M., Winands, M.H.: Monte Carlo tree search variants for simultaneous move games. In: IEEE Conference on Computational Intelligence and Games, pp. 1–8 (2014)
304.Kovařík, V., Lisý, V.: Analysis of hannan consistent selection for Monte Carlo tree search in simultaneous move games. arXiv preprint arXiv:1804.09045 (2018)
305.Mazumdar, E.V., Jordan, M.I., Sastry, S.S.: On finding local Nash equilibria (and only local Nash equilibria) in zero-sum games. arXiv preprint arXiv:1901.00838 (2019)
306.Bu, J., Ratliff, L.J., Mesbahi, M.: Global convergence of policy gradient for sequential zero-sum linear quadratic dynamic games. arXiv preprint arXiv:1911.04672 (2019)
307.Mescheder, L., Nowozin, S., Geiger, A.: The numerics of GANs. In: Advances in Neural Information Processing Systems, pp. 1825–1835 (2017)
308.Adolphs, L., Daneshmand, H., Lucchi, A., Hofmann, T.: Local saddle point optimization: A curvature exploitation approach. arXiv preprint arXiv:1805.05751 (2018)
309.Daskalakis, C., Panageas, I.: The limit points of (optimistic) gradient descent in min-max optimization. In: Advances in Neural Information Processing Systems, pp. 9236–9246 (2018)
310.Mertikopoulos, P., Zenati, H., Lecouat, B., Foo, C.S., Chandrasekhar, V., Piliouras, G.: Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In: International Conference on Learning Representations (2019)
311.Fiez, T., Chasnov, B., Ratliff, L.J.: Convergence of learning dynamics in Stackelberg games. arXiv preprint arXiv:1906.01217 (2019)
312.Balduzzi, D., Racaniere, S., Martens, J., Foerster, J., Tuyls, K., Graepel, T.: The mechanics of n-player differentiable games. In: International Conference on Machine Learning, pp. 363–372 (2018)
313.Sanjabi, M., Razaviyayn, M., Lee, J.D.: Solving non-convex non-concave min-max games under Polyak-Łojasiewicz condition. arXiv preprint arXiv:1812.02878 (2018)
314.Nouiehed, M., Sanjabi, M., Lee, J.D., Razaviyayn, M.: Solving a class of non-convex min-max games using iterative first order methods. arXiv preprint arXiv:1902.08297 (2019)
315.Mazumdar, E., Ratliff, L.J., Jordan, M.I., Sastry, S.S.: Policy-gradient algorithms have no guarantees of convergence in continuous action and state multi-agent settings. arXiv preprint arXiv:1907.03712 (2019)
316.Chen, X., Deng, X., Teng, S.H.: Settling the complexity of computing two-player Nash equilibria. Journal of the ACM 56(3), 14 (2009)
317.Greenwald, A., Hall, K., Serrano, R.: Correlated Q-learning. In: International Conference on Machine Learning, pp. 242–249 (2003)
318.Aumann, R.J.: Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics 1(1), 67–96 (1974)
319.Pérolat, J., Strub, F., Piot, B., Pietquin, O.: Learning Nash Equilibrium for General-Sum Markov Games from Batch Data. In: International Conference on Artificial Intelligence and Statistics, pp. 232–241 (2017)
320.Maillard, O.A., Munos, R., Lazaric, A., Ghavamzadeh, M.: Finite-sample analysis of Bellman residual minimization. In: Asian Conference on Machine Learning, pp. 299–314 (2010)
321.Letcher, A., Balduzzi, D., Racaniere, S., Martens, J., Foerster, J.N., Tuyls, K., Graepel, T.: Differentiable game mechanics. Journal of Machine Learning Research 20(84), 1–40 (2019)
322.Chasnov, B., Ratliff, L.J., Mazumdar, E., Burden, S.A.: Convergence analysis of gradient-based learning with non-uniform learning rates in non-cooperative multi-agent settings. arXiv preprint arXiv:1906.00731 (2019)
323.Hart, S., Mas-Colell, A.: Uncoupled dynamics do not lead to Nash equilibrium. American Economic Review 93(5), 1830–1836 (2003)
324.Saldi, N., Bas¸ar, T., Raginsky, M.: Markov–Nash equilibria in mean-field games with discounted cost. SIAM Journal on Control and Optimization 56(6), 4256–4287 (2018)
325.Saldi, N., Bas¸ar, T., Raginsky, M.: Approximate Nash equilibria in partially observed stochastic games with mean-field interactions. Mathematics of Operations Research (2019)
326.Saldi, N.: Discrete-time average-cost mean-field games on Polish spaces. arXiv preprint arXiv:1908.08793 (2019)
327.Saldi, N., Bas¸ar, T., Raginsky, M.: Discrete-time risk-sensitive mean-field games. arXiv preprint arXiv:1808.03929 (2018)
328.Guo, X., Hu, A., Xu, R., Zhang, J.: Learning mean-field games. arXiv preprint arXiv:1901.09585 (2019)
329.Fu, Z., Yang, Z., Chen, Y., Wang, Z.: Actor-critic provably finds Nash equilibria of linear-quadratic mean-field games. arXiv preprint arXiv:1910.07498 (2019)
330.Hadikhanloo, S., Silva, F.J.: Finite mean field games: Fictitious play and convergence to a first order continuous mean field game. Journal de Mathématiques Pures et Appliquées (2019)
331.Elie, R., Pérolat, J., Laurière, M., Geist, M., Pietquin, O.: Approximate fictitious play for mean field games. arXiv preprint arXiv:1907.02633 (2019)
332.Anahtarci, B., Kariksiz, C.D., Saldi, N.: Value iteration algorithm for mean-field games. arXiv preprint arXiv:1909.01758 (2019)
333.Zaman, M.A.u., Zhang, K., Miehling, E., Bas¸ar, T.: Approximate equilibrium computation for discrete-time linear-quadratic mean-field games. Submitted to IEEE American Control Conference (2020)
334.Yang, B., Liu, M.: Keeping in touch with collaborative UAVs: A deep reinforcement learning approach. In: International Joint Conference on Artificial Intelligence, pp. 562–568 (2018)
335.Pham, H.X., La, H.M., Feil-Seifer, D., Nefian, A.: Cooperative and distributed reinforcement learning of drones for field coverage. arXiv preprint arXiv:1803.07250 (2018)
336.Tožička, J., Szulyovszky, B., de Chambrier, G., Sarwal, V., Wani, U., Gribulis, M.: Application of deep reinforcement learning to UAV fleet control. In: SAI Intelligent Systems Conference, pp. 1169–1177 (2018)
337.Shamsoshoara, A., Khaledi, M., Afghah, F., Razi, A., Ashdown, J.: Distributed cooperative spectrum sharing in UAV networks using multi-agent reinforcement learning. In: IEEE Annual Consumer Communications & Networking Conference, pp. 1–6 (2019)
338.Cui, J., Liu, Y., Nallanathan, A.: The application of multi-agent reinforcement learning in UAV networks. In: IEEE International Conference on Communications Workshops, pp. 1–6 (2019)
339.Qie, H., Shi, D., Shen, T., Xu, X., Li, Y., Wang, L.: Joint optimization of multi-UAV target assignment and path planning based on multi-agent reinforcement learning. IEEE Access (2019)
340.Hochreiter, S., Schmidhuber, J.: Long short-term memory. Neural computation 9(8), 1735–1780 (1997)
341.Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, Ł., Polosukhin, I.: Attention is all you need. In: Advances in neural information processing systems, pp. 5998–6008 (2017)
342.Hausknecht, M., Stone, P.: Deep recurrent q-learning for partially observable mdps. In: 2015 AAAI Fall Symposium Series (2015)
343.Jorge, E., Kågebäck, M., Johansson, F.D., Gustavsson, E.: Learning to play guess who? and inventing a grounded language as a consequence. arXiv preprint arXiv:1611.03218 (2016)
344.Sukhbaatar, S., Fergus, R., et al.: Learning multiagent communication with backpropagation. In: Advances in Neural Information Processing Systems, pp. 2244–2252 (2016)
345.Havrylov, S., Titov, I.: Emergence of language with multi-agent games: Learning to communicate with sequences of symbols. In: Advances in neural information processing systems, pp. 2149–2159 (2017)
346.Das, A., Kottur, S., Moura, J.M., Lee, S., Batra, D.: Learning cooperative visual dialog agents with deep reinforcement learning. In: Proceedings of the IEEE International Conference on Computer Vision, pp. 2951–2960 (2017)
347.Peng, P., Wen, Y., Yang, Y., Yuan, Q., Tang, Z., Long, H., Wang, J.: Multiagent bidirectionally-coordinated nets: Emergence of human-level coordination in learning to play starcraft combat games. arXiv preprint arXiv:1703.10069 (2017)
348.Mordatch, I., Abbeel, P.: Emergence of grounded compositional language in multi-agent populations. In: AAAI Conference on Artificial Intelligence (2018)
349.Jiang, J., Lu, Z.: Learning attentional communication for multi-agent cooperation. In: Advances in Neural Information Processing Systems, pp. 7254–7264 (2018)
350.Jiang, J., Dun, C., Lu, Z.: Graph convolutional reinforcement learning for multi-agent cooperation. arXiv preprint arXiv:1810.09202 2(3) (2018)
351.Celikyilmaz, A., Bosselut, A., He, X., Choi, Y.: Deep communicating agents for abstractive summarization. arXiv preprint arXiv:1803.10357 (2018)
352.Das, A., Gervet, T., Romoff, J., Batra, D., Parikh, D., Rabbat, M., Pineau, J.: TarMAC: Targeted multi-agent communication. arXiv preprint arXiv:1810.11187 (2018)
353.Lazaridou, A., Hermann, K.M., Tuyls, K., Clark, S.: Emergence of linguistic communication from referential games with symbolic and pixel input. arXiv preprint arXiv:1804.03984 (2018)
354.Cogswell, M., Lu, J., Lee, S., Parikh, D., Batra, D.: Emergence of compositional language with deep generational transmission. arXiv preprint arXiv:1904.09067 (2019)
355.Allis, L.: Searching for solutions in games and artificial intelligence. Ph.D. thesis, Maastricht University (1994)
356.Krizhevsky, A., Sutskever, I., Hinton, G.E.: Imagenet classification with deep convolutional neural networks. In: Advances in neural information processing systems, pp. 1097–1105 (2012)
357.Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., Lillicrap, T., Simonyan, K., Hassabis, D.: A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science 362(6419), 1140–1144 (2018)
358.Billings, D., Davidson, A., Schaeffer, J., Szafron, D.: The challenge of Poker. Artificial Intelligence 134(1-2), 201–240 (2002)
359.Kuhn, H.W.: A simplified two-person Poker. Contributions to the Theory of Games 1, 97–103 (1950)
360.Southey, F., Bowling, M., Larson, B., Piccione, C., Burch, N., Billings, D., Rayner, C.: Bayes’ bluff: Opponent modelling in Poker. In: Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence, pp. 550–558. AUAI Press (2005)
361.Bowling, M., Burch, N., Johanson, M., Tammelin, O.: Heads-up limit hold’em Poker is solved. Science 347(6218), 145–149 (2015)
362.Heinrich, J., Silver, D.: Smooth UCT search in computer Poker. In: Twenty-Fourth International Joint Conference on Artificial Intelligence (2015)
363.Moravčík, M., Schmid, M., Burch, N., Lisý, V., Morrill, D., Bard, N., Davis, T., Waugh, K., Johanson, M., Bowling, M.: Deepstack: Expert-level artificial intelligence in heads-up no-limit Poker. Science 356(6337), 508–513 (2017)
364.Brown, N., Sandholm, T.: Superhuman ai for heads-up no-limit Poker: Libratus beats top professionals. Science 359(6374), 418–424 (2018)
365.Burch, N., Johanson, M., Bowling, M.: Solving imperfect information games using decomposition. In: Twenty-Eighth AAAI Conference on Artificial Intelligence (2014)
366.Moravcik, M., Schmid, M., Ha, K., Hladik, M., Gaukrodger, S.J.: Refining subgames in large imperfect information games. In: Thirtieth AAAI Conference on Artificial Intelligence (2016)
367.Brown, N., Sandholm, T.: Safe and nested subgame solving for imperfect-information games. In: Advances in neural information processing systems, pp. 689–699 (2017)
368.Vinyals, O., Ewalds, T., Bartunov, S., Georgiev, P., Vezhnevets, A.S., Yeo, M., Makhzani, A., Küttler, H., Agapiou, J., Schrittwieser, J., et al.: Starcraft II: A new challenge for reinforcement learning. arXiv preprint arXiv:1708.04782 (2017)
369.Vinyals, O., Babuschkin, I., Czarnecki, W.M., Mathieu, M., Dudzik, A., Chung, J., Choi, D.H., Powell, R., Ewalds, T., Georgiev, P., et al.: Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature pp. 1–5 (2019)
370.Mnih, V., Badia, A.P., Mirza, M., Graves, A., Lillicrap, T., Harley, T., Silver, D., Kavukcuoglu, K.: Asynchronous methods for deep reinforcement learning. In: International conference on machine learning, pp. 1928–1937 (2016)
371.Lerer, A., Peysakhovich, A.: Maintaining cooperation in complex social dilemmas using deep reinforcement learning. arXiv preprint arXiv:1707.01068 (2017)
372.Hughes, E., Leibo, J.Z., Phillips, M., Tuyls, K., Dueñez-Guzman, E., Castañeda, A.G., Dunning, I., Zhu, T., McKee, K., Koster, R., et al.: Inequity aversion improves cooperation in intertemporal social dilemmas. In: Advances in neural information processing systems, pp. 3326–3336 (2018)
373.Cai, Q., Yang, Z., Lee, J.D., Wang, Z.: Neural temporal-difference learning converges to global optima. arXiv preprint arXiv:1905.10027 (2019)
374.Arora, S., Cohen, N., Hazan, E.: On the optimization of deep networks: Implicit acceleration by overparameterization. arXiv preprint arXiv:1802.06509 (2018)
375.Li, Y., Liang, Y.: Learning overparameterized neural networks via stochastic gradient descent on structured data. In: Advances in Neural Information Processing Systems, pp. 8157–8166 (2018)
376.Brafman, R.I., Tennenholtz, M.: A near-optimal polynomial time algorithm for learning in certain classes of stochastic games. Artificial Intelligence 121(1-2), 31–47 (2000)
377.Brafman, R.I., Tennenholtz, M.: R-max-A general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research 3(Oct), 213–231 (2002)
378.Tu, S., Recht, B.: The gap between model-based and model-free methods on the linear quadratic regulator: An asymptotic viewpoint. arXiv preprint arXiv:1812.03565 (2018)
379.Sun, W., Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J.: Model-based RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. In: Conference on Learning Theory, pp. 2898–2933 (2019)
380.Lin, Q., Liu, M., Rafique, H., Yang, T.: Solving weakly-convex-weakly-concave saddle-point problems as weakly-monotone variational inequality. arXiv preprint arXiv:1810.10207 (2018)
381.García, J., Fernández, F.: A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research 16(1), 1437–1480 (2015)
382.Chen, Y., Su, L., Xu, J.: Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM on Measurement and Analysis of Computing Systems 1(2), 44 (2017)
383.Yin, D., Chen, Y., Ramchandran, K., Bartlett, P.: Byzantine-robust distributed learning: Towards optimal statistical rates. arXiv preprint arXiv:1803.01498 (2018)

Citation

MLA

Zhang, K., et al. “Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms”. arXiv, 2019, http://arxiv.org/abs/1911.10635v2.

APA

Zhang, K., Yang, Z., & Başar, T. (2019). Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms. arXiv. http://arxiv.org/abs/1911.10635v2

Chicago

Zhang, K., Z. Yang, and T. Başar. 2019. “Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms”. arXiv. http://arxiv.org/abs/1911.10635v2.

Harvard

Zhang, K., Yang, Z. and Başar, T. (2019) “Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms”, arXiv [Preprint]. Available at: http://arxiv.org/abs/1911.10635v2.

Vancouver

1. Zhang K, Yang Z, Başar T (2019) Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms. arXiv

BibTeX

@article{zhang2019multi,
  title = {Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms},
  author = {Zhang, Kaiqing and Yang, Zhuoran and Başar, Tamer},
  year = {2019},
  journal = {arXiv},
  url = {http://arxiv.org/abs/1911.10635v2},
  eprint = {1911.10635}
}

Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

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

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Markov Game and Stationary Nash Equilibrium Formulation

Knowl 2 — Extensive-Form Game with Imperfect Information and Approximate Nash Equilibrium

Knowl 3 — Bellman Optimality Operator and Minimax-Q Learning for Two-Player Zero-Sum Markov Games

Knowl 4 — Decentralized Multi-Agent Actor-Critic with Networked Consensus

Knowl 5 — Distributed Saddle-Point Formulation of Multi-Agent Policy Evaluation

Knowl 6 — No-Regret Learning and Nash Equilibrium Convergence in Two-Player Zero-Sum Games

Knowl 7 — Equivalence Between Counterfactual Regret Minimization and Policy Gradient Methods

Knowl 8 — Counterfactual Regret Minimization Regret Bound and Decomposition

Knowl 9 — Discrete-Time Mean-Field Games Model and Equilibrium

Knowl 10 — Nash-Q Learning Operator for General-Sum Markov Games

Knowl 11 — Instabilities and Pathologies of Multi-Agent Policy Gradient Dynamics in Continuous Games

References

Citation

BibTeX

Access the Paper