In a standard reinforcement learning (RL) setup, an agent interacts with a stationary environment: if the agent takes action $A$ in state $S$, the probability of ending up in state $S'$ remains constant over time. However, in decentralized multi-agent reinforcement learning (MARL), this assumption collapses. Because multiple agents are learning and updating their policies simultaneously, the "environment" for any single agent includes the behavior of all other agents.
As Raul Vicente, Ilya Kuzovkin, and Jaan Aru observe in Multiagent Cooperation and Competition with Deep Reinforcement Learning, the learning progress of one agent alters the transition dynamics and reward structures for everyone else. This creates a "moving target" problem known as non-stationarity.
The Moving Target Problem
The core intuition behind non-stationarity is a lack of global synchronization. In a decentralized system, agents often only observe local states. Gerald Tesauro notes in Online Resource Allocation Using Decompositional Reinforcement Learning that when agents cannot perceive the external factors driving global shifts—such as the changing strategies of their peers—they fail to adapt effectively.
From the perspective of a single agent, the world appears chaotic. An action that yielded a high reward yesterday might yield a low reward today, not because the environment changed, but because a teammate learned a new maneuver. As Simone C. Riedmiller and Martin A. Riedmiller argue in A Neural Reinforcement Learning Approach to Learn Local Dispatching Policies in Production Scheduling, this simultaneous adaptation leads to instability and coordination failures, preventing independent controllers from converging toward a globally optimal rhythm.
Taming Instability via Temporal and Structural Constraints
To combat this, researchers have developed mechanisms to "slow down" or structure the learning process so that the environment appears more stable.
- Multi-Timescale Learning: Akilesh Badrinaaraayanan and colleagues propose a "middle-ground" approach in Dealing With Non-stationarity in Decentralized Cooperative Multi-Agent Deep Reinforcement Learning via Multi-Timescale Learning. By designating "fast" and "slow" learners that rotate roles, the system ensures that while one agent adapts quickly, others provide a relatively stationary background, facilitating smoother convergence.
- Macro-Actions: Instead of coordinating on every millisecond-level primitive action, agents can use temporally extended "macro-actions." Yuchen Xiao, Christopher Amato, and others demonstrate in Asynchronous Actor-Critic for Multi-Agent Reinforcement Learning that high-level goals (e.g., "navigate to the kitchen") allow agents to ignore step-by-step jitter, making the joint policy more robust to the "curse of multiagents" Mao et al..
- Inertia and Persistence: Bora Yongacoglu and Serdar Yuksel prove in Unsynchronized Decentralized Q-Learning: Two Timescale Analysis By Persistence that using random inertia—where agents occasionally stick to their current policy despite new data—can "tame" non-stationarity and lead to stable equilibria in stochastic games.
Coordination Without Centralization
If agents cannot be managed by a "central brain," they must find ways to align their internal representations of the world.
One approach is Implicit Signaling. Daniel Lee and Niko A. Grupen show in Curriculum-Driven Multi-Agent Learning and the Role of Implicit Communication in Teamwork that agents can learn to communicate through physical movement. By maximizing mutual information between actions, agents treat correlation as a proxy for coordination, discovering cooperative strategies even in social dilemmas Emergent cooperation through mutual information maximization.
Another method involves Assume-Guarantee Contracts. In Assume-Guarantee Reinforcement Learning, agents make formal assumptions about their neighbors' behaviors to provide guarantees about their own. This modularity allows for independent training while mathematically bounding the performance of the entire system. Similarly, Haozhi Wang and Jianye HAO introduce Policy Reciprocity, allowing agents with different observation spaces to share knowledge by linking mismatched states through an "adjacency space" Multi-agent Policy Reciprocity with Theoretical Guarantee.
The Role of Global Awareness
While execution remains decentralized, training often benefits from a "global-aware" perspective to mitigate the consistency conflict. Meiqin Liu and Senlin Zhang explain in GAWM: Global-Aware World Model for Multi-Agent Reinforcement Learning that decentralized state reconstruction can lead agents to develop conflicting internal models. By using a unified global state during training—even if agents only use local observations during execution—systems can achieve the sample efficiency required for complex tasks like StarCraft micromanagement Kong et al..
Ultimately, the research direction focuses on moving from rigid, centralized optimization toward adaptive, decentralized intelligence that can survive the inherent instability of shared environments Hady et al.. By treating non-stationarity not as a bug to be removed, but as a fundamental property to be managed, these frameworks enable the emergence of collective intelligence in everything from traffic grids Tavares & Bazzan to massive-agent resource harvesting Chen et al..