Skip to content

Provable Memory Efficient Self-Play Algorithm for Model-free Reinforcement Learning

🕒 Published (v1): 2025-11-29 06:44 UTC · Source: Arxiv · Venue: ICLR 2024 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

ME-Nash-QL is a model-free self-play algorithm for two-player zero-sum Markov games that simultaneously achieves optimal space complexity O(SABH), near-optimal sample complexity Õ(H⁴SAB/ε²), and low computational complexity O(T·poly(AB)), while outputting a single Markov and Nash policy — a combination no prior algorithm achieved.

Problem

Existing MARL algorithms for two-player zero-sum Markov games suffer from at least one of: memory inefficiency (space growing with sample count T or quadratically in S), poor sample complexity for long horizons, high computational cost O(T·poly(SAB)), non-Markov output policies, non-Nash output policies, or high burn-in cost (minimum samples before near-optimal sample complexity kicks in, e.g., Õ(S³ABH⁴) for Nash-VI).

Method

ME-Nash-QL extends Nash Q-learning with two key techniques applied for the first time to two-player zero-sum Markov games:

  1. Reference-advantage decomposition: Decomposes Q-function updates into a fixed "reference" value and a smaller advantage term, reducing variance and shaving one factor of H from sample complexity compared to standard Nash Q-learning.
  2. Early-settlement: Reference values stop updating once V̄ₕ(s) − V̲ₕ(s) ≤ 1, locking in a stable reference early and enabling tight control of the burn-in cost.

Policy evaluation maintains UCB and LCB Q-function estimates alongside reference-decomposed variants; these are combined via min/max clipping (lines 11–12 of Algorithm 1) to preserve optimism/pessimism. Policy improvement computes a Coarse Correlated Equilibrium (CCE) via linear programming in O(poly(AB)) time, whose marginals yield a single Markov policy for each player — avoiding nested-mixture representations that require O(ST)-space.

Key Contributions

  • First TZMG algorithm achieving space complexity O(SABH) — matching the minimum needed to store Q-values — while outputting a Markov and Nash policy.
  • Sample complexity Õ(H⁴SAB/ε²), outperforming all prior algorithms when min{A,B} ≪ H²; optimal dependence on H and S.
  • Burn-in cost Õ(SABH¹⁰), versus at least Õ(S³ABH⁴) for Nash-VI at equivalent sample complexity.
  • Computational complexity O(T·poly(AB)), lower than prior algorithms requiring O(T·poly(SAB)).
  • Extension to M-player general-sum Markov games (Multi-ME-Nash-QL) with sample complexity Õ(H²S∏ᵢAᵢ/ε²).

Results

  • Space complexity: O(SABH) — best among all listed algorithms; Nash-VI requires O(S²ABH), Nash Q-learning requires O(SABT).
  • Sample complexity: Õ(H⁴SAB/ε²) — ties Nash-VI (best model-based), strictly better than V-learning Õ(H⁶S(A+B)/ε²) and Nash Q-learning Õ(H⁶SAB/ε²) for long horizons.
  • Burn-in cost: Õ(SABH¹⁰) versus Õ(S³ABH⁴) for Nash-VI — advantage scales as S² when S > H³, which holds in practical domains (e.g., Go: S = 2³⁶¹, H ≤ 722).
  • Markov + Nash policy: Only ME-Nash-QL and Nash-VI achieve both; ME-Nash-QL dominates Nash-VI on all complexity metrics.
  • Regret bound: Õ(H²√SABT).

Limitations

  • Analysis is restricted to tabular (finite state-action) episodic settings; no function approximation or continuous state space.
  • Burn-in cost Õ(SABH¹⁰) remains polynomial in H with a large exponent; for moderate H this threshold may be large in practice.
  • Open question: whether O(A+B) (instead of O(AB)) sample complexity is achievable for multi-player general-sum games without sacrificing other metrics.
  • CCE is used rather than exact Nash equilibrium for policy computation; while a Nash equilibrium is always a CCE, the converse need not hold.

Relevance to Agentic AI / LLM Agents

This work is foundational theory for multi-agent systems where agents must learn competitive or cooperative equilibria through self-play — a core primitive for training game-playing agents (AlphaGo, Atari, Poker) and increasingly relevant to LLM-based multi-agent frameworks where agents negotiate, compete, or coordinate. The memory efficiency result is directly pertinent to scaling self-play to large state spaces without prohibitive storage, and the Markov policy guarantee simplifies deployment since policies need not carry history. The burn-in cost improvement matters for sample-efficient online learning in agentic settings where environment interaction is expensive.