Non-Stationarity in Multi-Agent Learning
Why every guarantee from single-agent RL dissolves when other learners are present, what breaks in the Markov assumption, and the two architectural responses.
Single-agent reinforcement learning rests on an environment that is fixed: the transition and reward functions do not change, so a policy that improves against them stays improved. Put two learning agents in the same environment and each becomes part of the other's environment, so both are learning against a target that moves in response to their own learning.
What breaks
From any single agent's perspective, the environment's dynamics depend on the other agents' current policies. Those policies change every update, so the effective transition function is time-varying and the process is no longer a Markov decision process from that agent's view. Every convergence result that assumes a stationary MDP is inapplicable.
The practical consequences are concrete. Experience in a replay buffer was generated when the other agents had different policies, so it describes an environment that no longer exists, and replay, which is what makes off-policy single-agent methods sample-efficient, becomes a source of stale and misleading data. Policies can cycle indefinitely, each best-responding to the last, in the same way that fictitious play cycles in rock-paper-scissors. And an agent can appear to improve while the joint outcome worsens, because it is climbing against a moving benchmark.
The two responses
Centralised training with decentralised execution is the dominant architecture. During training, a critic sees the full joint state and all agents' actions, so from its perspective the environment is stationary: conditioning on everyone's actions removes the dependence on their unknown policies. Each agent's policy conditions only on its own observation, so execution remains decentralised. MADDPG and MAPPO are the standard instances, and the approach works because training is where the non-stationarity bites and training is where extra information is available.
Opponent modelling has each agent learn a model of the others' policies and condition on it, so the changing behaviour becomes an observed variable rather than unmodelled drift. It is more general and it introduces a recursion, since the model is of an agent that is also modelling you, that has to be truncated at some depth.
When it breaks
Centralised critics scale badly. The joint action space grows exponentially in the number of agents, so the critic's input dimension and the data required to fit it grow with it. Beyond a modest number of agents, factorised critics or attention over agents are required.
Decentralised execution assumes the observation suffices. If an agent's local observation is insufficient to select a good action, no amount of centralised training fixes it, because the information is absent at execution time. Communication protocols are the response and they change the problem.
Self-play converges to a narrow equilibrium. Agents trained against themselves become strong against their own strategy distribution and can be brittle against strategies outside it. Population-based training against a league of past and diverse opponents is the standard mitigation and multiplies the compute cost.
Reward design determines the game. Whether agents cooperate, compete or ignore each other follows from the reward structure, and a design intended to be cooperative can be competitive in effect if the reward creates scarcity between agents. The equilibrium reached is a property of the game the designer specified, not of the learning algorithm.
12 flashcards for this concept
Click a card to reveal the answer.