I2Q: A Fully Decentralized Q-Learning Algorithm

Jiechuan Jiang, Zongqing LuNeurIPS 2022 · OpenReview

TL;DR

I2Q (Ideal Independent Q-learning) is a new algorithm for fully decentralized multi-agent reinforcement learning that solves the pervasive "non-stationarity" problem. By having each agent model an "ideal" transition function based on the optimal behavior of others, I2Q allows agents to converge to global optima using only their own local experiences, significantly outperforming standard independent learning methods.

What Problem Does This Paper Address?

In Multi-Agent Reinforcement Learning (MARL), most state-of-the-art methods rely on Centralized Training and Decentralized Execution (CTDE). This means that during training, a central "god-view" learner sees everyone's actions and states. However, in many real-world scenarios—like autonomous cars from different manufacturers or privacy-sensitive industrial robots—agents cannot share their internal actions or observations.

The simplest solution is Independent Q-Learning (IQL), where each agent treats others as part of the environment. The problem? As other agents learn and change their strategies, the environment appears "non-stationary" to an individual agent. This moving target makes it theoretically impossible for standard Q-learning to guarantee convergence to an optimal solution, often leading to agents getting stuck in mediocre, "sub-optimal" behaviors.

Methods

The authors introduce I2Q, which tackles non-stationarity by shifting the focus from what other agents are doing to what they should be doing.

  1. Ideal Transition Probabilities: The authors define "ideal" transitions as those induced by the optimal joint policy of all other agents. They prove that if an agent performs Q-learning on these ideal transitions, it will converge to the global optimum.
  2. QSS-Learning: Since agents don't know the "ideal" transitions upfront, they use QSS-learning to estimate the value of a state-to-next-state transition ($Q^{ss}(s, s')$). Crucially, this value is independent of the current (and changing) actions of other agents, making it a stationary target even in a multi-agent setting.
  3. The Transition Model ($f_i$): Each agent trains a neural network to predict the next state $s'$ that would maximize the $Q^{ss}$ value. This acts as a "hallucination" of the ideal outcome.
  4. Decentralized Update: Instead of updating their Q-values based on the noisy, non-stationary transitions actually stored in their replay buffer, agents update their values based on the "ideal" next state predicted by their model.

Datasets

The authors evaluated I2Q across a diverse range of benchmarks to test its limits:

  • Random Matrix Games: Multi-stage games designed to test convergence to global vs. local optima.
Illustration of the multi-stage matrix games used for evaluation.
  • MPE-based Differential Games: Continuous action tasks where agents must reach a specific configuration to get a high reward.
  • Multi-Agent MuJoCo: A benchmark where different agents control different joints of a robot (e.g., a 2-agent HalfCheetah).
  • StarCraft Multi-Agent Challenge (SMAC): A high-dimensional, discrete-action environment involving complex combat micro-management.

Key Insights and Ideas

  • Consensus through Environment Dynamics: Because all agents live in the same environment, they all observe the same state transitions. By learning $Q^{ss}$ (state-to-state values), they can independently reach a consensus on what "good" states look like without ever talking to each other.
  • Solving the Exploration Dilemma: In standard IQL, if your teammates explore (act randomly), it creates noise that hurts your learning. In I2Q, more exploration by teammates actually helps you see more states, allowing you to build a better model of the ideal transition function.
  • Stationarity via Modeling: By performing Q-learning on a modeled transition rather than the actual observed transition, the agent effectively filters out the "noise" caused by other agents' evolving policies.

Key Results

  • Global Optimality: In matrix games where IQL consistently failed or hit local optima, I2Q reached the global optimum even as the complexity (number of stages, $L$) increased.
Learning curves comparing I2Q and IQL on matrix games of varying lengths (L=3 to 6).
  • Superior Performance: In MPE differential games, I2Q significantly outperformed IDDPG and Hysteretic IDDPG. Visualizations showed that I2Q's learned value functions were remarkably close to the theoretical "ideal" values.
  • Scalability: I2Q proved effective in high-dimensional tasks like SMAC and partially observable continuous tasks like Multi-Agent MuJoCo, showing it isn't just a theoretical toy but a practical tool for complex MARL.
  • Stochastic Robustness: While the theory is built on deterministic environments, the authors provided a theoretical bound for the "value gap" in stochastic settings and showed empirically that I2Q remains robust to environmental noise.

Limitations and Future Work

  • Single vs. Multiple Optima: The core theory assumes a unique optimal joint policy. While the authors suggest a reward-shaping "tie-breaking" trick to handle multiple optima, more formal methods for coordination in these cases could be explored.
  • Deterministic Assumption: The strongest theoretical guarantees apply to deterministic environments. Extending the proof to fully stochastic MDPs is a noted area for future theoretical work.
  • Coordination Complexity: I2Q focuses on the base learning algorithm. The authors note that for extremely complex coordination (like explicit communication), I2Q could serve as a foundation upon which more specialized coordination layers are built.

Summary updated

Abstract

Fully decentralized multi-agent reinforcement learning has shown great potentials for many real-world cooperative tasks, where the global information, \textit{e.g.}, the actions of other agents, is not accessible. Although independent Q-learning is widely used for decentralized training, the transition probabilities are non-stationary since other agents are updating policies simultaneously, which leads to non-guaranteed convergence of independent Q-learning. To deal with non-stationarity, we first introduce stationary ideal transition probabilities, on which independent Q-learning could converge to the global optimum. Further, we propose a fully decentralized method, I2Q, which performs independent Q-learning on the modeled ideal transition function to reach the global optimum. The modeling of ideal transition function in I2Q is fully decentralized and independent from the learned policies of other agents, helping I2Q be free from non-stationarity and learn the optimal policy. Empirically, we show that I2Q can achieve remarkable improvement in a variety of cooperative multi-agent tasks.
BibTeX
@inproceedings{jiang2022i,
  author = {Jiechuan Jiang and Zongqing Lu},
  title = {{I2Q: A Fully Decentralized Q-Learning Algorithm}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=xdZs1kf-va},
}
Figure