Decentralized Policy Optimization in Multi-Agent Markov Games

This direction is split into other directions: decentralized equilibrium convergence. Its last version stays readable and citable here.

Version 1 of 1153 papers171 conceptsfrozen 2026-10-04

In standard reinforcement learning, an agent learns to navigate a static environment. But in multi-agent reinforcement learning (MARL), the environment is no longer static—it is composed of other learning agents. This creates a "moving target" problem: as Agent A adapts to Agent B, Agent B is simultaneously adapting to Agent A, often leading to cycles or instability.

The research direction explored here focuses on Independent Learning, where agents optimize their own policies using only local observations and rewards, yet still converge to a stable global Nash Equilibrium. This approach bypasses the "curse of dimensionality" inherent in centralized controllers by treating other agents not as complex adversaries to be modeled, but as part of the environment's underlying structure.

The Moving Target and Local Optimality

The simplest way to handle multiple agents is to let each run its own reinforcement learning algorithm. However, the non-stationarity of the environment usually breaks the convergence guarantees of single-agent RL. Anderson Rocha Tavares and Ana L. C. Bazzan demonstrated that in practical scenarios like traffic routing, independent Q-learners can actually reach stable distributions without any central coordination Reinforcement learning for route choice in an abstract traffic scenario.

The intuition is that if the collective behavior of the population stabilizes, the environment becomes "stationary enough" for individual agents to settle on a best response. This is formalized in Coagent Networks, where James E. Kostas and Philip S. Thomas proved that the global gradient of a system's reward is simply the sum of local policy gradients Asynchronous Coagent Networks. This means that even without a central "brain," individual nodes following local gradients are implicitly moving the entire system toward a global optimum.

Coordination via Potential Functions

Why should selfish agents ever coordinate? The answer often lies in the structure of the game itself. In Markov Potential Games (MPGs), there exists a single "potential function" that tracks the incentive changes of all players. When one player improves their own reward, the potential function increases.

Stefanos Leonardos and Georgios Piliouras showed that independent policy gradient methods are guaranteed to converge to a Nash Equilibrium in these games Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games. Because every agent is climbing the same hidden potential hill, their decentralized "selfish" updates naturally lead to a collective equilibrium. This was further refined by Youbang Sun and P. R. Kumar, who provided fast convergence rates for Independent Natural Policy Gradient (INPG), showing that coordination can emerge in polynomial time Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Games.

Scaling to Massive Populations

When the number of agents grows to thousands or millions, modeling every individual becomes impossible. Mean Field Games (MFGs) solve this by assuming agents are small enough that they only care about the aggregate distribution (the mean field) of the population.

Recent work has moved away from requiring a "population oracle" to tell agents what the mean field is. Sriram Ganapathi Subramanian and Mark Crowley introduced Decentralized Mean Field Games, where agents use local observations to estimate the population state Decentralized Mean Field Games. Similarly, Batuhan Yardim and Niao He developed Policy Mirror Ascent (PMA), which allows agents to learn optimal policies in large-scale symmetric games using only a single sample trajectory from a simulator Policy Mirror Ascent for Efficient and Independent Learning in Mean Field Games.

Beyond Self-Interest: History and Empathy

While independent learning often assumes "selfish" agents, the field is expanding to include historical context and social reasoning.

By focusing on local updates and leveraging the inherent mathematical structures of games (like potential functions or mean fields), this research direction proves that complex, large-scale coordination does not require a central authority. Instead, it can emerge from the independent, adaptive decisions of individual agents.

Papers in this version

Showing 60 of 153 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_decentralized_policy_optimization_in_mul_02f293ca,
  title = {Decentralized Policy Optimization in Multi-Agent Markov Games},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/decentralized-policy-optimization-in-multi-agent-markov-games/rdr_02f293cae1234da4b04920f8a1b2ed2d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_decentralized_policy_optimization_in_mul_02f293ca_v1,
  title = {Decentralized Policy Optimization in Multi-Agent Markov Games},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/decentralized-policy-optimization-in-multi-agent-markov-games/rdr_02f293cae1234da4b04920f8a1b2ed2d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}