Dealing with Non-Stationarity in Multi-Agent Deep Reinforcement Learning

Summary

This partial ingest is based on the extracted full PDF text. Papoudakis et al. survey approaches for handling Multi-Agent Non-Stationarity in multi-agent deep reinforcement learning. The paper frames non-stationarity as the fact that each agent’s effective transition and reward functions change while other agents’ policies are also learning, then categorizes mitigation strategies including centralized critics, decentralized self-play and replay stabilization, opponent modelling, opponent-learning-aware updates, meta-learning, and learned communication.

Key Claims

• Multi-agent deep RL inherits the instability of deep RL and adds a distinct non-stationarity problem caused by concurrently adapting agents.
• From one agent’s perspective, other agents’ changing policies alter the effective environment dynamics and rewards, breaking the stationarity assumptions behind many single-agent RL methods.
• Centralized critics stabilize training by conditioning value estimates on other agents’ observations and actions while retaining decentralized execution.
• Decentralized approaches such as self-play and experience-replay correction try to make independent learning robust to changing opponents.
• Opponent modelling and opponent-shaping methods explicitly represent other agents’ policies, goals, representations, or learning updates.
• Meta-learning and communication are presented as additional routes for adapting quickly or sharing information that reduces non-stationarity.
• Open problems include transfer across changing agent populations, limited access to opponent information, convergence theory, and multi-agent credit assignment.

Methods / Formalism

• A Markov game is written (I,S,A,r,T), where I is the agent set, A=A_1 x ... x A_N is the joint action space, r=(r_1,...,r_N) gives agent rewards, and T:S x A x S -> [0,1] gives next-state probabilities.
• Under partial observability, agent i conditions its policy on a local observation history h_i; the joint policy is

$$\pi (a\mid H)=({\pi }_1(a_1\mid h_1),\dots ,{\pi }_N(a_N\mid h_N)).$$

• The non-stationarity problem arises because T and r_i depend on all agents’ actions, while each pi_j changes during training. Agent i therefore faces an induced environment that changes as pi_{-i} changes.
• The surveyed method families are centralized critics and centralized training with decentralized execution; decentralized self-play and importance-corrected replay; opponent modelling, LOLA-style learning-aware updates, SOS, and learned opponent representations; meta-learning for fast adaptation to changing opponents; and learned communication channels such as CommNet, IC3Net, and differentiable inter-agent learning.

Evidence / Experiments

• This is a survey rather than a new experimental paper.
• The evidence is organized around representative prior systems and domains, including StarCraft, Go/self-play settings, locomotion, iterated games, and communication benchmarks.
• Table 1 categorizes surveyed algorithms by environment type, centralized/decentralized training and execution, modelling type, opponent information requirements, algorithm family, and number of agents.

Connections

• Creates Multi-Agent Non-Stationarity as a reusable concept for the wiki’s MARL cluster.
• Connects to Opponent Shaping through LOLA, SOS, and other methods that optimize with respect to opponent learning dynamics.
• Supports Safe Multi-Agent Reinforcement Learning because safety guarantees and learned policies can fail when other agents keep changing during training.
• Connects to Continual Learning because agent policies, opponents, and even the number of agents may change over time.
• Complements Alatur2024 - Provably Learning Nash Policies in Constrained Markov Potential Games, which focuses on equilibrium learning under constraints; Papoudakis et al. survey broader engineering strategies for stabilizing multi-agent deep RL.

Open Questions

• How should agents transfer knowledge when the number and type of agents changes in open multi-agent systems?
• Which opponent information should be assumed available during training and execution?
• What convergence guarantees are possible for deep MARL methods that adapt to other learners?
• How can centralized training or opponent modelling handle decentralized execution without unrealistic access to other agents’ observations and actions?
• How should credit be assigned when rewards depend on small subsets of agents in a changing multi-agent environment?

Citation

Papoudakis, G., Christianos, F., Rahman, A., and Albrecht, S. V. (2019). Dealing with Non-Stationarity in Multi-Agent Deep Reinforcement Learning. arXiv:1906.04737.