In single-agent reinforcement learning (RL), an agent learns by interacting with a stationary environment. The environment acts as a stable sandbox: if the agent takes action $a$ in state $s$, the probability of transitioning to state $s'$ remains constant over time. This stability allows the agent to safely isolate cause and effect, gradually optimizing its policy through trial and error.
In multi-agent reinforcement learning (MARL), this foundational assumption shatters. When multiple agents learn simultaneously in a shared space, the environment ceases to be stationary. Because the state transitions and rewards depend on the joint actions of all agents, the environment effectively becomes a moving target. As Agent A updates its policy to counter Agent B, the world changes from the perspective of Agent B, rendering Agent B's historical data obsolete.
Understanding why this non-stationarity occurs—and how modern algorithms circumvent it—is central to designing scalable, cooperative, and competitive AI systems.
The Root of Non-Stationarity
To see why independent learning fails, consider how an individual agent perceives a multi-agent environment. In a standard Markov Decision Process (MDP), transition dynamics are governed by a fixed function $P(s' \mid s, a)$. In a multi-agent game, however, the transition depends on the joint action vector $\mathbf{a} = (a_1, \dots, a_n)$.
If an individual agent $i$ attempts to learn independently, it treats all other agents as part of the environment. From agent $i$'s isolated perspective, the transition probability appears to be:
$$P(s' \mid s, a_i) = \sum_{\mathbf{a}_{-i}} P(s' \mid s, a_i, \mathbf{a}_{-i}) \prod_{j \neq i} \pi_j(a_j \mid s)$$
Crucially, because the other agents are also updating their policies $\pi_j$ over time, the product $\prod_{j \neq i} \pi_j(a_j \mid s)$ is time-dependent. As a result, $P(s' \mid s, a_i)$ continuously shifts.
As Caroline Claus demonstrated in early foundational work, The Dynamics of Reinforcement Learning in Cooperative Multiagent Systems, this shifting landscape makes it incredibly difficult for independent learners to distinguish between random environmental noise and the intentional strategy updates of their teammates. An action that yielded a high reward yesterday might result in failure today simply because a teammate changed their behavior. This lack of mutual modeling, as noted by Vinícius Zambaldi et al. in Multi-agent Reinforcement Learning in Sequential Social Dilemmas, induces severe training instability and frequently prevents agents from converging to stable social equilibria.
The Consequences: Shadowing and High Variance
When agents ignore this non-stationarity, two primary pathologies emerge:
- High Gradient Variance: Because the underlying state-action relationships are always in flux, the target values used to compute policy gradients fluctuate wildly. This variance can stall learning entirely or cause policies to diverge.
- Coordination Failures (Action Shadowing): Agents can easily become trapped in suboptimal local extrema. As explained by Nancy Fulda et al. in Predicting and Preventing Coordination Problems in Cooperative Q-learning Systems, when agents update their policies simultaneously without synchronization, they often "shadow" each other's actions, misinterpreting a teammate's exploration as a permanent shift in the environment and prematurely converging to a poor joint strategy.
Restoring Stationarity via Centralized Training
The most prominent architectural solution to this dilemma is the Centralized Training with Decentralized Execution (CTDE) paradigm.
The intuition behind CTDE is straightforward: while agents must act independently during deployment (using only local observations), we can leverage global information during training to stabilize the learning process.
[Centralized Training]
Global Critic observes: (s, a_1, a_2, ..., a_n) ---> Outputs stable joint value
^
| (Updates policy gradients)
[Decentralized Execution] |
Agent 1 Policy ---> Acts on local obs o_1
Agent 2 Policy ---> Acts on local obs o_2
In a framework like MADDPG, introduced by Ryan Lowe et al. in Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments, each agent retains its own decentralized policy network, but training is guided by a centralized critic. This centralized critic is conditioned on the full global state $s$ and the actions of all agents $\mathbf{a} = (a_1, \dots, a_n)$.
By conditioning the evaluation function on the joint action, the environment becomes stationary from the perspective of the critic:
$$P(s' \mid s, a_1, \dots, a_n)$$
Because the joint action is explicitly accounted for, changes in a teammate's policy no longer manifest as mysterious, uncaused shifts in environment dynamics. The critic can accurately assign credit to individual actions, dampening gradient variance and allowing complex coordinated behaviors to emerge.
Communication as an Explicit Stabilizer
Another powerful mechanism for mitigating non-stationarity is the introduction of communication protocols. If agents can share their intents or observations, they can dynamically condition their policies on the state of their peers, effectively tracking the "moving target."
However, learning what and when to communicate in a non-stationary environment presents its own circular challenge: if an agent's policy is changing, its communication language is likely changing too. To prevent fragile coordination, Chuxiong Sun et al. developed T2MAC: Targeted and Trusted Multi-Agent Communication through Selective Engagement and Evidence-Driven Integration, which uses mathematical fusion rules from the Theory of Evidence rather than purely learned parameters to integrate messages. This ensures that even when peer behaviors shift, message interpretation remains consistent and reliable.
Similarly, shifting the learning objective itself can force stability. Sean L. Barton et al. argue in Coordination-driven Learning in Multi-agent Problem Spaces that coordination should not merely be an emergent byproduct of training. By utilizing causal metrics like Convergent Cross Mapping to explicitly reward agents for their mutual influence, the authors show that agents can actively learn to stabilize the joint policy space, making them far more resilient to environmental fluctuations.
Summary
Non-stationarity is the defining hurdle of multi-agent reinforcement learning. When agents learn independently, they invalidate each other's experiences, turning the optimization landscape into a chaotic, moving target. By restructuring the problem—either through centralized critics that view the joint action space or through explicit communication and coordination objectives—modern MARL frameworks restore the mathematical predictability required for stable, scalable collective intelligence.