Multi-Agent Non-Stationarity

Definition

Multi-agent non-stationarity is the instability that arises when each learning agent treats other agents as part of the environment while those other agents’ policies are also changing.

Why It Matters

Many single-agent RL methods assume stationary transition and reward functions. In MARL, those functions are induced partly by other learners. As they update, replay data can become stale, value estimates can chase moving targets, and policies can cycle rather than converge.

Formalism / Key Objects

• A Markov game has agents I, global state S, joint action space A=A_1 x ... x A_N, rewards r_i:S x A x S -> R, and transition kernel T:S x A x S -> [0,1].
• Stochastic Games give the classical equilibrium-theory version of this model: state, joint action, transition probabilities, player-specific costs or payoffs, and discounted continuation values.
• If opponents follow policies pi_{-i}, agent i faces an induced transition kernel

$$T_i^{{\pi }_{-i}}(s^{\prime }\mid s,a_i)=\sum _{a_{-i}}T(s^{\prime }\mid s,a_i,a_{-i})\prod _{j\ne i}{\pi }_j(a_j\mid h_j).$$

• When the other agents update from pi_{-i}^t to pi_{-i}^{t+1}, the induced kernel and expected rewards for agent i change even if the underlying Markov game is fixed.
• Common mitigation families include centralized training with decentralized execution, centralized critics, self-play over current and historical policies, replay correction, opponent modelling, learning-aware updates, meta-learning, and communication.
• In cooperative MARL, even a shared reward does not remove non-stationarity: an agent’s TD target or policy-gradient advantage still depends on the other agents’ current policies.
• Cooperative MARL Baseline Formalisms records how this issue appears in VDN, MAPPO, and IPPO baselines.
• Learned communication protocols add another moving target: a population can stabilize reward while still leaving signal interpretations non-robust to new interaction partners.
• In aspiration-based repeated games, another agent’s satisfaction threshold and aspiration update are part of the effective dynamics, so even simple action-propensity learners can make each other’s environment non-stationary.
• In Social Learning in MARL, another agent may change the received reward itself, not only the transition distribution induced by others’ actions.

Connections

• Papoudakis2019 - Dealing with Non-Stationarity in Multi-Agent Deep Reinforcement Learning surveys method families for deep MARL.
• Fink1964 - Equilibrium in a Stochastic n-Person Game shows that finite discounted stochastic games can have stationary mixed-strategy equilibria before learning dynamics are added.
• Cooperative Multi-Agent Reinforcement Learning is a major site of non-stationarity because team reward aligns objectives without freezing the teammates’ learning processes.
• Multi-Agent Coordination names the broader coordination burden created by simultaneously acting and learning agents.
• Ad Hoc Teamwork adds partner uncertainty and open-team membership, so the teammate model may change at deployment as well as during training.
• Value Decomposition Networks reduce decentralized execution complexity through additive value factors, but their shared TD targets still move as policies change.
• Multi-Agent PPO studies show that limiting epochs and minibatch reuse can matter because stale on-policy data becomes more damaging in harder MARL tasks.
• Opponent Shaping deliberately optimizes through opponent learning updates, turning non-stationarity from a nuisance into a strategic object.
• Aspiration-Based Reinforcement Learning gives a lower-cognition version of the same strategic instability: other agents alter behavior after satisfactory or unsatisfactory payoff experiences.
• Constrained Markov Potential Games provide one equilibrium-focused route through constrained multi-agent learning, but rely on assumptions very different from open-ended deep MARL.
• Mean-Field Reinforcement Learning reduces some many-agent instability by replacing explicit pairwise adaptation with a representative-agent population distribution, at the cost of homogeneity and population-limit assumptions.
• Safe Multi-Agent Reinforcement Learning must handle non-stationarity because safety filters, constraints, and learned policies may interact with changing co-learners.
• Social Learning in MARL turns non-stationarity into a possible manipulation channel when agents can reshape each other’s rewards.
• Continual Learning is relevant when the agent population, opponent behavior, or task distribution changes over time.
• Emergent Communication and Successful Misunderstandings show how changes in population membership can expose latent semantic non-stationarity.

Common Confusions

• The underlying Markov game can be stationary while each agent’s induced learning problem is non-stationary.
• Equilibrium existence for a stationary stochastic game does not mean independent adaptive agents will find that equilibrium.
• Centralized training does not necessarily imply centralized execution; many methods use global information only while learning.
• Opponent modelling and opponent shaping are related but distinct: modelling predicts or represents other agents, while shaping acts to influence their future updates.

Key Sources

• Papoudakis2019 - Dealing with Non-Stationarity in Multi-Agent Deep Reinforcement Learning
• Fink1964 - Equilibrium in a Stochastic n-Person Game
• Sunehag2017 - Value-Decomposition Networks for Cooperative Multi-Agent Learning
• Yu2022 - The Surprising Effectiveness of PPO in Cooperative Multi-Agent Games
• Bendor2001 - Aspiration-Based Reinforcement Learning in Repeated Interaction Games
• Kondylidis2025 - Successful Misunderstandings: Learning to Coordinate Without Being Understood
• MacKinlay2026 - Opponent Shaping as a Model for Manipulation and Cooperation
• Ahmed2022 - Deep Reinforcement Learning for Multi-Agent Interaction
• Chelarescu2021 - Deception in Social Learning