The Moving Target Problem in Multiagent Learning

47 concepts45 papers1 proposal

In standard reinforcement learning (RL), an agent learns by interacting with a environment that follows fixed rules. If the agent takes an action in a specific state, the resulting reward and the next state are determined by a stationary probability distribution. However, in multiagent reinforcement learning (MARL), the "environment" includes other agents who are also learning and adapting.

This creates the moving target problem: as Agent A updates its policy to perform better against Agent B, Agent B is simultaneously updating its own policy. From the perspective of any single agent, the environment’s dynamics are constantly shifting, rendering previously learned strategies obsolete.

The Breakdown of Stationarity

The core challenge of the moving target problem is the loss of the Markov property. In single-agent RL, the current state provides all the information needed to make an optimal decision. In MARL, the optimal action depends on the hidden, evolving internal states (the policies) of other agents.

Conitzer et al. identify this non-stationarity as the primary reason standard RL techniques fail to reach stable states. When multiple agents learn concurrently, the reward distribution for a specific action shifts over time, which Palmer et al. argue can cause agents to oscillate between strategies or settle for "safe" but mediocre sub-optimal behaviors to avoid the risk of miscoordination.

Temporal Separation and Two-Timescale Learning

One intuitive way to solve the moving target problem is to ensure that one part of the system changes much slower than the other, effectively "stabilizing" the environment for the faster component.

Sayin et al. and Sastry et al. propose two-timescale algorithms. In these frameworks, agents update their value estimates (how good a state is) much faster than they update their actual strategies. By the time an agent makes a significant change to its behavior, its internal model of the environment's current rewards has already converged. This separation allows independent agents to reach Nash Equilibria even without seeing their opponents' actions or rewards.

Leniency and Optimism

In cooperative settings, the moving target problem is often exacerbated by early exploration. If Agent A tries a potentially optimal action but Agent B happens to be exploring a random, poor action at the same time, Agent A will receive a low reward and may incorrectly conclude that its action was bad.

To counter this, Palmer et al. introduced Lenient Deep Q-Networks (LDQN). The intuition is to be "optimistic": agents initially ignore low rewards, assuming they resulted from a teammate's temporary exploration rather than a fundamentally flawed strategy. As training progresses, this leniency decays, forcing agents to eventually coordinate on stable, optimal policies. Similarly, Panait et al. suggest Biased Coevolution, which factors in an agent's best-ever historical performance to prevent high-potential strategies from being discarded due to unoptimized collaborators.

Sequential Coordination and Influence

If simultaneous updates cause chaos, another solution is to break the symmetry. Zhao et al. demonstrate that updating agents sequentially rather than simultaneously allows for provable convergence to global optimality in cooperative games. By letting one agent adapt to a fixed partner before the partner is allowed to change, the "moving target" is temporarily paused.

More advanced methods involve agents actively shaping the learning trajectories of their peers. Instead of just reacting to a moving target, algorithms like SILI (Wang et al.) and FURTHER (Kim et al.) proactively nudge other agents toward stable, predictable, or high-reward strategies. By accounting for how their own actions will influence the future policy updates of their teammates or opponents, these agents transform the moving target problem from a hurdle into a strategic tool for reaching superior equilibria.

Scaling to Complex Environments

As the number of agents grows, the moving target problem becomes a "nightmare" landscape of non-convexity. Subramanian et al. address this by using Mean-field Games, which treat a massive population of agents as a single aggregate distribution, effectively turning a multi-agent problem back into a stationary single-agent problem.

For competitive games, the Policy Space Response Oracles (PSRO) framework, surveyed by Bighashdel et al., manages non-stationarity by building a diverse population of strategies. Instead of chasing a single moving target, agents learn to respond to a distribution of historical strategies, ensuring that the resulting policy is robust against many different ways an opponent might adapt.

Key Foundational Work

Multi-Agent Systems (2001) — contributed 3 concept elements to this direction.
AWESOME: A General Multiagent Learning Algorithm that Converges in Self-Play and Learns a Best Response Against Stationary Opponents (2003) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_moving_target_problem_multi_agent_non_st_e6b67e8e,
  title = {moving target problem (multi-agent non-stationarity)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/moving-target-problem-multi-agent-non-stationarity/rdr_e6b67e8ee730449a8fc41eacb11839a0},
  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_moving_target_problem_multi_agent_non_st_e6b67e8e_v1,
  title = {moving target problem (multi-agent non-stationarity)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/moving-target-problem-multi-agent-non-stationarity/rdr_e6b67e8ee730449a8fc41eacb11839a0/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake