The Moving Target Problem in Multi Agent Learning

1,380 concepts982 papers10 proposals

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:

  1. 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.
  2. 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.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 984 papers
  2. Version 1 · 2026-10-04 · 657 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_multi_agent_non_stationarity_774e37c7,
  title = {multi-agent non-stationarity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-agent-non-stationarity/rdr_774e37c734f2469ab4fc2f9783c8c305},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 2, frozen text):

@misc{lacuna_multi_agent_non_stationarity_774e37c7_v2,
  title = {multi-agent non-stationarity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-agent-non-stationarity/rdr_774e37c734f2469ab4fc2f9783c8c305/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake