Multi-agent reinforcement learning

Multi-agent reinforcement learning (MARL) is the study of sequential decision-making systems in which several adaptive agents interact within a shared environment. Each agent modifies its behavior from experience while the behavior of other agents may change simultaneously. The resulting learning problem combines reinforcement learning with concepts from game theory, distributed artificial intelligence, and stochastic control.

The defining property of MARL is that an agent's transition and reward observations depend partly on policies controlled by other learners. From the perspective of any single agent, those policies form a changing component of the environment. Standard reinforcement-learning assumptions therefore cease to hold even when the physical dynamics remain stationary. Each learner is consequently presented with a moving target created by the attempts of every other learner to estimate its own moving target.

MARL includes cooperative systems whose agents share an objective, competitive systems with opposed incentives, and mixed-motive systems in which interests overlap only in particular states. These distinctions affect the appropriate solution concept and the information required during training. They do not, by themselves, determine whether independently learned behavior will coordinate, converge, or remain stable.

Formal framework

A common mathematical model is the stochastic game, also called a Markov game. A stochastic game consists of a set of agents (N), a state space (\mathcal{S}), and an action space (\mathcal{A}_i) for each agent (i). It also contains a transition kernel

[ P(s' \mid s,a_1,\ldots,a_n) ]

and an individual reward function

[ r_i(s,a_1,\ldots,a_n,s'). ]

At time (t), the agents select a joint action (\mathbf{a}t=(a{1,t},\ldots,a_{n,t})). The environment then produces a successor state according to (P), after which each agent receives its associated reward. Agent (i) seeks to maximize an expected discounted return,

[ J_i(\pi_1,\ldots,\pi_n)

\mathbb{E}\left[ \sum_{t=0}^{\infty}\gamma^t r_i(s_t,\mathbf{a}t,s{t+1}) \right], ]

where (\pi_i) is the agent's policy and (\gamma) is a discount factor.

This formulation differs from a Markov decision process because no single policy necessarily controls the joint action. A fixed joint policy induces an ordinary Markov chain, but learning changes the policies and therefore changes the induced process. Treating other agents as part of the environment restores the notation of single-agent reinforcement learning without restoring its stationarity.

When agents receive observations rather than complete states, the problem is represented as a decentralized partially observable Markov decision process, or Dec-POMDP. Each agent then conditions its action on a local action-observation history. A joint policy may depend on information that no individual participant possesses in full, making coordination an information-structure problem as well as a control problem.

Historical development

The mathematical basis of MARL developed from work on repeated games, stochastic games, and adaptive control. John von Neumann and Oskar Morgenstern established the strategic representation of interacting decision makers, while John Nash formalized equilibrium for general non-cooperative games. Lloyd Shapley subsequently demonstrated that discounted zero-sum stochastic games possess stationary values, connecting strategic interaction with dynamic programming.

During the 1990s, Michael Littman formulated Markov games as a framework for reinforcement learning and introduced minimax-based temporal-difference methods for two-player zero-sum environments. Junling Hu and Michael Wellman later developed equilibrium-based learning rules for general-sum stochastic games, where several equilibrium outcomes may coexist and the learning dynamics require an equilibrium-selection convention.

In 1998, You Watanabe analyzed adaptive policy updates in repeated stochastic games with partially aligned rewards. Her formulation separated changes caused by environmental transitions from changes caused by opponents' contemporaneous learning, and it was incorporated into subsequent analyses of non-stationarity in independent learners. The same period saw the consolidation of agent-based learning as a distinct subject within distributed artificial intelligence rather than as a direct extension of single-controller optimization.

The expansion of deep reinforcement learning during the 2010s shifted the field toward high-dimensional observations and parameterized policies. Ryan Lowe and collaborators introduced a centralized-critic formulation for continuous multi-agent control, while Tabish Rashid and collaborators developed monotonic value-function factorization for cooperative tasks. These approaches established centralized training with decentralized execution as a principal organizational framework for modern MARL.

Learning dynamics

Non-stationarity

In single-agent reinforcement learning, convergence analyses commonly assume that the transition and reward distributions are fixed. In MARL, an update to another agent's policy can alter both distributions as experienced by the learner. An identical state-action pair may therefore have a different expected return after other agents update their behavior.

This non-stationarity is endogenous rather than externally imposed. Slower learning rates may reduce the magnitude of successive changes, but they do not remove strategic dependence between policies. Replay buffers introduce an additional mismatch because stored transitions were generated under earlier joint policies. Historical data consequently describe environments that remain physically valid but are strategically obsolete.

A policy can also influence which data become available to other agents. Exploration by one participant changes the state distribution encountered by the group, while exploitation may suppress information about alternative joint behaviors. Data collection is therefore part of the strategic interaction instead of a neutral sampling process.

Equilibrium and convergence

For a zero-sum game, the minimax value provides a well-defined objective. Agent (i) selects a policy that maximizes its return under the least favorable response of its opponent:

[ \max_{\pi_i}\min_{\pi_{-i}} J_i(\pi_i,\pi_{-i}). ]

This structure permits extensions of value iteration and Q-learning because the equilibrium value of each local stage game can be incorporated into a temporal-difference target.

General-sum games do not provide a unique counterpart to the minimax value. A Nash equilibrium is a joint policy from which no agent can improve its expected return through unilateral deviation, but a game may contain several such equilibria with different welfare properties. Learning rules can converge to different outcomes because of initialization, exploration history, or approximation error. Convergence to an equilibrium also does not imply that the selected equilibrium maximizes collective return.

Other solution concepts represent different forms of coordination. A correlated equilibrium permits actions to be conditioned on signals generated by a correlation device. A coarse correlated equilibrium evaluates deviations chosen before such a signal is observed. In population settings, mean-field game theory replaces detailed pairwise interaction with dependence on an aggregate population distribution.

Policy-learning dynamics may cycle rather than converge. This behavior occurs in elementary games such as rock paper scissors, where improvement against the current opponent creates vulnerability to another response. The cycle is not merely failed optimization; it reflects the absence of a single scalar objective whose local ascent describes every participant's incentives.

Cooperative learning and credit assignment

In a fully cooperative stochastic game, every agent receives the same team reward. The shared objective removes direct conflict but does not identify which action caused an observed outcome. When a group receives one delayed reward, an individual learner must estimate its contribution while accounting for simultaneous actions chosen by its partners.

A centralized action-value function can represent interactions among all agents:

[ Q_{\mathrm{tot}}(s,\mathbf{a}). ]

Directly maximizing this function may require access to the complete joint action during execution. Its action space also grows exponentially with the number of agents when each participant has a fixed discrete action set.

Value decomposition addresses this problem by expressing a team value through agent-specific utilities. In the simplest additive form,

[ Q_{\mathrm{tot}}(s,\mathbf{a})

\sum_{i=1}^{n}Q_i(o_i,a_i), ]

where (o_i) denotes agent (i)'s local information. More expressive factorization architectures use a mixing function whose monotonicity ensures that individually greedy actions are jointly greedy with respect to the represented team value. The restriction permits decentralized action selection, although it excludes joint value functions whose optimal actions depend on non-monotonic interactions between utilities.

Counterfactual baselines provide another treatment of credit assignment. An agent's selected action is compared with alternative actions while the other agents' actions are held fixed. The resulting advantage estimate measures how the selected action changed expected team return under that local counterfactual. This separates an individual's policy-gradient signal from variation caused by its partners without requiring a separate environmental trial for every alternative.

Centralized training with decentralized execution

Centralized training with decentralized execution, abbreviated CTDE, permits additional information to be used while policies are being learned. A centralized critic may observe the global state and the joint action, while each actor receives only the observations available to its corresponding agent during execution.

For agent (i), a centralized critic can be written as

[ Q_i(s,a_1,\ldots,a_n). ]

The actor remains decentralized:

[ a_i \sim \pi_i(\cdot\mid o_i). ]

The critic reduces ambiguity during training because it conditions on variables that would otherwise appear as unexplained environmental variation. Execution remains decentralized because the critic is discarded or restricted after training. CTDE therefore separates the information needed to estimate learning signals from the information permitted for operational decisions.

This separation does not eliminate partial observability. If an actor's local observation cannot distinguish states requiring different actions, no centralized critic can supply the missing distinction after deployment. Training can shape memory or representation learning, but the executable policy remains bounded by its observation history and communication structure.

Communication and coordination

Communication can be represented as part of the joint action or as an explicit differentiable channel between policies. A message has operational significance only through its effect on another agent's action distribution. Learned communication protocols therefore need not reproduce human language or possess a fixed interpretation outside the training environment.

Bandwidth restrictions and message delays alter the decentralized information structure. When communication is costless and globally available, the system approaches centralized control even if actions remain physically distributed. When messages are constrained, agents must allocate channel capacity between immediate coordination and information useful for later decisions.

Coordination can also emerge without explicit messages. Shared conventions may be encoded in policies through recurring observations, timing, or environmental state. Such conventions remain vulnerable to policy replacement because an independently trained participant may attach a different behavioral meaning to the same observable cue.

Evaluation

Evaluation in MARL concerns the interaction between policies rather than the isolated performance of one policy. A return measured against a fixed set of partners or opponents characterizes behavior only relative to that set. Two policies with similar average returns can differ substantially in exploitability, coordination compatibility, and sensitivity to unseen participants.

Self-play evaluates and trains agents against versions of their own policy family. It generates opponents at an appropriate level without requiring a permanent external curriculum, but it can produce strategic conventions that are effective only within the resulting lineage. Population-based training broadens the distribution of encountered behaviors by maintaining several policies and selecting interactions among them.

In competitive settings, exploitability measures the improvement available to a best response. In cooperative settings, cross-play evaluates whether policies trained separately can coordinate when paired. These criteria address different properties, and neither is reducible to the return obtained by a single jointly trained team.

Random seeds have structural significance because early stochastic events can determine which convention a group adopts. Averaging only within teams trained together can conceal this dependence. The empirical object is therefore a distribution over learned joint behaviors rather than a single deterministic outcome.

Computational characteristics

The joint action space grows as

[ |\mathcal{A}|=\prod_{i=1}^{n}|\mathcal{A}_i|, ]

which makes direct representation expensive as the number of agents increases. The joint observation history grows further when agents operate under partial observability. Function approximation reduces storage requirements but does not remove the underlying dependence among participants.

Parameter sharing exploits symmetry when agents have comparable action and observation structures. A shared policy can treat the agent's local observation as input while applying the same parameters across the population. This reduces the number of learned models, although agents may still require identifiers or role information when optimal behavior is asymmetric.

Large populations are often approximated through local interaction graphs or aggregate distributions. Graph-based representations preserve selected relational structure, while mean-field approximations replace individual neighbors with a population statistic. Both approaches trade exact joint dependence for a representation whose complexity grows more slowly than the full game.