The Challenge of Interaction-Mediated Nonstationarity in Multi-Agent Reinforcement Learning

In reinforcement learning, multi-agent systems face a fundamental problem: each agent may individually face a stationary environment, yet their interactions collectively create nonstationarity. A recent Reddit discussion thread, "Stationary Alone, Drifting Together," explores this in depth, introducing the concept of "interaction-mediated nonstationarity" and proposing adaptation strategies.

What Is Interaction-Mediated Nonstationarity?

In multi-agent reinforcement learning (MARL), it is typically assumed that when each agent's policy is fixed, the environment is stationary for each individual agent. However, when multiple agents learn and update their policies simultaneously, the environment each agent faces (including the behavior of other agents) keeps changing, resulting in nonstationarity. This nonstationarity does not originate from the environment itself but is mediated by interactions among agents.

The thread points out that this nonstationarity is dual in nature: from a single agent's perspective, if the other agents' policies are fixed, the environment is stationary; but from the system-wide view, all agents are learning, causing the joint policy distribution to drift continuously. This "stationary alone, drifting together" phenomenon is one of the core challenges of MARL.

Markov Games are the standard formal framework for MARL, typically described by the tuple $(\mathcal{N}, \mathcal{S}, {\mathcal{A}i}, P, {R_i}, \gamma)$: $\mathcal{N}$ is the set of agents, $\mathcal{S}$ is the joint state space, $\mathcal{A}i$ is the action space of agent $i$, $P(s'|s,\mathbf{a})$ is the state transition under joint actions, and $R_i$ is each agent's reward function. Crucially, each agent's transitions and rewards depend on the joint actions $\mathbf{a}=(a_1,\dots,a_n)$ of all agents. When the other agents' policies $\pi{-i}$ are fixed, the environment reduces to a standard MDP for agent $i$, hence "stationary alone"; but when all $\pi_i$ are updated simultaneously, the joint policy distribution $\pi(\mathbf{a}|s)$ drifts over time, and the effective transition $P_i(s'|s,a_i)=\mathbb{E}{a_{-i}\sim\pi_{-i}}[P(s'|s,a_i,a_{-i})]$ that agent $i$ actually faces changes accordingly. This is precisely the formal origin of "stationary alone, drifting together," and it explains why, under the Markov game framework, nonstationarity cannot be eliminated through a single-agent perspective.

Limitations of Traditional Methods

Common MARL methods such as Independent Q-Learning are simple but ignore nonstationarity, which easily leads to unstable learning. The centralized training with decentralized execution (CTDE) framework alleviates the problem by sharing global information, but it still struggles to fully eliminate the drift caused by interactions.

The thread mentions that many studies attempt to address this through experience replay, opponent modeling, or policy regularization, but these methods often assume that nonstationarity is bounded or predictable. In reality, interaction-mediated nonstationarity may be more dynamic and complex.

Centralized training with decentralized execution (CTDE) is a training paradigm rather than a single algorithm: during training, global state and all agents' action information may be used, while during execution each agent makes decisions independently based only on local observations. Representative works include VDN, QMIX (value decomposition), MADDPG (centralized critic), and COMA (counterfactual baseline). The mechanism by which CTDE mitigates nonstationarity is that a centralized critic takes joint state-action as input, effectively providing each agent with an evaluator that can "see through" others' policies during training, thereby reducing the variance of policy gradient estimates. However, it does not change the fact that the joint policy keeps drifting—the critic itself is fitted against a nonstationary target, and during execution agents can still only respond to changes in others' behavior based on local information. Therefore, CTDE can be regarded as mitigating rather than eliminating nonstationarity, which is consistent with the original text's judgment that it is "difficult to fully eliminate the drift caused by interactions."

Adaptation Strategies: From Theory to Practice

To address this challenge, the thread discusses several adaptation approaches. One direction is meta-learning, which enables agents to quickly adapt to changes in other agents' policies. Another is hierarchical learning, which abstracts interaction patterns into high-level policies to slow the drift of low-level policies.

In addition, the thread mentions using graph neural networks (GNNs) to model the interaction relationships among agents, thereby explicitly capturing the source of nonstationarity. By dynamically updating the interaction graph, agents can better predict changes in others' behavior and reduce the impact of environment drift.

Graph neural networks (GNNs) aggregate information across graph nodes and edges through message passing, with permutation-invariant/equivariant aggregation functions (such as sum or attention) at their core. In MARL, each agent is typically treated as a node and observable interaction relationships (distance, communication links, adjacency matrices) as edges; a GNN aggregates neighbor information at each time step to generate each agent's policy input. Its value lies in the fact that when the number of agents changes or the neighbor set changes dynamically, the GNN structure does not need to be redesigned, making it naturally suited to the requirement of "dynamically updating the interaction graph"; meanwhile, the learned edge weights or attention can be interpreted as estimates of the influence of other agents' behavior, providing explicit signals for predicting changes in others' policies. The limitation is that the graph structure is often given by heuristic rules; if the true interaction relationships are unobservable, the GNN can only infer them implicitly, and its effectiveness depends on the accuracy of the interaction graph estimate.

Implications for the Research Community

This discussion emphasizes the need to re-examine the stationarity assumption in MARL. The traditional stationarity assumption no longer holds in interaction-mediated settings, and new theoretical tools and algorithms need to be developed. The thread calls on researchers to focus on the design of interaction structures and on how to use interaction information to stabilize the learning process.

For practitioners, understanding this challenge helps in designing more robust multi-agent systems, for example in autonomous driving, robot collaboration, and game AI. In the future, combining causal reasoning with adaptive interaction modeling may become an important direction.

In summary, interaction-mediated nonstationarity is a frontier problem in MARL that deserves in-depth exploration and requires both theoretical innovation and algorithmic improvement.