The Moving Target Problem in Multi-Agent Reinforcement Learning

This direction is split into other directions: moving target problem (multi-agent non-stationarity). Its last version stays readable and citable here.

Version 1 of 1177 papers187 conceptsfrozen 2026-10-04

In standard reinforcement learning, an agent lives in a world that, while perhaps complex, is fundamentally consistent. If a robot pushes a block, the laws of physics don't change halfway through the experiment. However, as soon as you introduce a second learning agent, this consistency vanishes.

This is the moving target problem. Because every agent is updating its policy simultaneously, the environment becomes non-stationary from the perspective of any individual learner. As Vincent Conitzer and Tuomas Sandholm noted in their work on the AWESOME algorithm, the very act of one agent learning alters the optimal strategy for everyone else. The "ground truth" of the reward distribution shifts under the agents' feet, often leading to oscillations, divergence, or a collapse into mediocre, "safe" strategies.

The Mirage of Stationarity

In a single-agent Markov Decision Process (MDP), the transition dynamics $P(s'|s, a)$ and rewards $R(s, a)$ are fixed. In Multi-Agent Reinforcement Learning (MARL), these functions depend on the joint action of all agents. From the perspective of Agent A, the probability of reaching state $s'$ depends on what Agent B chooses to do. Since Agent B is also learning and changing its behavior, Agent A’s perceived transition function is constantly mutating.

This instability is particularly punishing in cooperative tasks. Gregory Palmer, Rahul Savani, and Karl Tuyls describe this in Negative Update Intervals in Deep Multi-Agent Reinforcement Learning as a coordination trap: agents may settle for sub-optimal "safe" behaviors because the path to the global optimum requires a level of coordination that is impossible to maintain while both partners are still "fiddling" with their strategies.

Stabilizing the Target through Leniency

One way to combat this is to make agents "lenient." In Lenient Multi-Agent Deep Reinforcement Learning, Gregory Palmer and colleagues propose that agents should initially ignore low rewards that might be the result of a teammate's exploration rather than a fundamentally bad strategy.

By using a temperature-based decay for leniency, agents are "optimistic" early on, giving their partners time to settle into a policy. This prevents the system from prematurely discarding the optimal joint strategy just because it resulted in a poor outcome during the chaotic early phases of learning.

Centralization as a Training Wheels Mechanism

If the moving target problem stems from decentralized agents acting on partial, shifting information, one solution is to temporarily remove the decentralization.

The CESMA framework, developed by Alex Tong Lin and others in Centralized Expert Supervises Multi-Agents, addresses this by training a single "all-knowing" centralized expert first. Because the expert controls all agents, the environment is stationary. Once the expert masters the task, the decentralized agents use imitation learning to mimic the expert's behavior. This bypasses the instability of simultaneous training entirely, providing a fixed behavioral anchor for the agents to follow.

Modeling the Shift

Rather than trying to make the environment stationary, some researchers argue we should embrace the movement by predicting it.

Standard agents react to what their peers did. Advanced frameworks like LeMOL (Learning to Model Opponent Learning), introduced by Ian Davies and Jun Wang, use meta-learning to model how an opponent’s policy is likely to change in the future. Similarly, Aryaman Reddi and Jan Peters propose K-Level Policy Gradients, which allow agents to anticipate the policy updates of their peers within the current training step. If you know how your partner is going to adapt, their "movement" is no longer a source of noise, but a predictable trajectory you can align with.

Scaling to the Mean Field

The moving target problem scales poorly; as the number of agents increases, the environment becomes exponentially more volatile. Jayakumar Subramanian and Aditya Mahajan suggest a "law of large numbers" approach in Reinforcement Learning in Stationary Mean-field Games.

In Mean-Field Games (MFGs), instead of tracking every individual moving target, an agent learns against the average distribution of the entire population. When there are thousands of agents, the shift of a single individual doesn't matter. The "mean field" becomes a relatively stable, stationary target, allowing independent learning algorithms to converge even in massive systems.

Papers in this version

Showing 60 of 177 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_the_moving_target_problem_in_multi_agent_11a35c41,
  title = {The Moving Target Problem in Multi-Agent Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-moving-target-problem-in-multi-agent-reinforcement-learning/rdr_11a35c41e6114da2bcbe1b1286db6adf},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_the_moving_target_problem_in_multi_agent_11a35c41_v1,
  title = {The Moving Target Problem in Multi-Agent Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-moving-target-problem-in-multi-agent-reinforcement-learning/rdr_11a35c41e6114da2bcbe1b1286db6adf/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}