In standard reinforcement learning (RL), an agent learns by interacting with a stationary environment. The rules of the game—the rewards and the way the world changes—are fixed. However, in multi-agent reinforcement learning (MARL), this assumption collapses. Because all agents are learning simultaneously, the "environment" for any single agent includes the behaviors of all other agents. As Agent A improves its strategy, the world effectively changes for Agent B.
This phenomenon is known as non-stationarity. It creates a "moving target" problem where the optimal policy for one agent is constantly shifting, often leading to high gradient variance, unstable training, and a failure to converge to coordinated behaviors.
The Moving Target Problem
The core challenge of non-stationarity is the violation of the Markov property. In a single-agent setting, the probability of transitioning to a new state depends only on the current state and action. In MARL, as noted by Ryan Lowe and Yi Wu in Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments, the transition dynamics and rewards perceived by an individual agent are influenced by the evolving policies of others.
If an agent uses a standard experience replay buffer—a cornerstone of deep RL—it might try to learn from data collected hours ago. But if its teammates or opponents have changed their strategies since then, that old data becomes misleading or "stale," as explored by Jakob N. Foerster in Stabilising Experience Replay for Deep Multi-Agent Reinforcement Learning.
Stabilizing the Learning Signal
To combat this instability, researchers have developed several key mechanisms to ground the learning process:
Centralized Training, Decentralized Execution (CTDE) The most influential framework for addressing non-stationarity is CTDE. The intuition is simple: during training, we can afford to let agents see "extra" information, such as the states and actions of their peers. This global view makes the environment appear stationary from the perspective of a centralized critic. Once trained, the agents use their decentralized actors to perform tasks using only their local observations. MADDPG popularized this by using a centralized critic to provide a stable gradient for decentralized policies.
Opponent and Teammate Modeling If you cannot see the internal state of other agents, you must predict them. Gerald Tesauro introduced Hyper-Q Learning, which learns the value of mixed strategies by estimating opponent behavior. More recently, Zheng Tian proposed ROMMEO, which uses probabilistic inference to model an opponent's optimal future behavior, allowing an agent to adapt to changes before they fully manifest.
Fingerprinting and Importance Sampling To make experience replay viable again, researchers "tag" data. Jakob N. Foerster introduced Multi-Agent Fingerprints, which add the training iteration or exploration rate to the replay buffer. This allows the agent to disambiguate old behaviors from new ones. Alternatively, Multi-Agent Importance Sampling re-weights old transitions to reflect how likely they would be under the current policies of the other agents.
Coordination through Communication and Hierarchy
Beyond stabilization, agents must actively align their shifting strategies.
- Emergent Communication: Agents can learn to send signals to one another to reduce uncertainty. Jakob Nicolaus Foerster demonstrated in Learning to Communicate to Solve Riddles with Deep Distributed Recurrent Q-Networks that agents can develop their own protocols to solve coordination puzzles, effectively creating a shared "state" that resists environmental shifts.
- Information Design: Instead of just reacting, agents can influence others. Yue Lin and Wenhao Li explored Information Design in Multi-Agent Reinforcement Learning, where an agent strategically shares information to nudge peers toward mutually beneficial outcomes.
- Temporal Abstraction: In complex tasks, non-stationarity is exacerbated by sparse rewards. Hongyao Tang and Jianye HAO proposed Hierarchical Deep Multiagent Reinforcement Learning, which uses subgoals to decompose the problem. By coordinating on high-level goals rather than low-level motor actions, the system becomes more robust to the rapid, noisy changes in individual agent behaviors.
The Path to General Adaptation
The ultimate goal of this research is Ad Hoc Teamwork (AHT)—the ability to collaborate with completely unknown teammates on the fly. Frameworks like PADiff by Antao Xiang use generative diffusion models to capture the multimodal nature of cooperation, predicting teammate intentions to ensure that even as the team composition changes, the agent's policy remains aligned with the collective goal. By treating non-stationarity not as a bug to be suppressed, but as a dynamic to be modeled, these systems achieve a level of fluid coordination that mirrors human teamwork.