Research map / Reinforcement learning / MDPs and planning
Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a model-free stage-based Q-learning with min-gap reference-advantage decomposition for two-player zero-sum Markov games, achieving H^3SAB/ε² sample complexity (optimal in H, S, ε) for the first time among model-free methods.
Problem
Sample-efficient model-free learning of epsilon-optimal Nash equilibria in two-player zero-sum episodic Markov games, where existing model-free methods scale sub-optimally in horizon H while model-based methods are optimal in H.
Approach
Extends reference-advantage decomposition (variance reduction from single-agent RL) to Markov games by maintaining optimistic and pessimistic reference value functions chosen as the pair with minimal value gap in history, since CCE-based policies break value monotonicity; combined with stage-based updates with growing stage lengths.
Key results
- Algorithm finds an epsilon-optimal Nash equilibrium in tilde-O(H^3SAB/epsilon^2) episodes, matching the best model-based sample complexity in H, S and epsilon (except AB term).
- Improves upon all prior model-free algorithms for zero-sum Markov games in horizon dependence, which previously scaled as H^4 or worse.
- Lower bound Omega(H^3S(A+B)/epsilon^2) shows minimax optimality in H, S, epsilon, while the AB dependence is not tight.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Q-learning with min-gap reference-advantage decomposition | Model-free learning in two-player zero-sum Markov games · Tabular episodic two-player zero-sum Markov games | sample complexity (episodes): existing model-free algorithms have sub-optimal dependence on H; proposed: \widetilde{O}(H^3SAB/\epsilon^2) | Helped |
| Use Q-learning with min-gap reference-advantage decomposition instead of V-learning | Model-free learning in two-player zero-sum Markov games · Tabular episodic two-player zero-sum Markov games | horizon dependence of sample complexity: O(H^5S(A+B)/\epsilon^2) -> \widetilde{O}(H^3SAB/\epsilon^2) | Helped |
| Use Q-learning with min-gap reference-advantage decomposition instead of V-learning | Model-free learning in two-player zero-sum Markov games · Tabular episodic two-player zero-sum Markov games | action-count dependence of sample complexity: proposed: \widetilde{O}(H^3SAB/\epsilon^2); V-learning: O(H^5S(A+B)/\epsilon^2) | Mixed |
| Use the proposed model-free algorithm rather than the minimax lower-bound rate as a reference | Model-free learning in two-player zero-sum Markov games · Tabular episodic two-player zero-sum Markov games | dependence on H, S, and ε in sample complexity: \widetilde{O}(H^3SAB/\epsilon^2); lower bound: \Omega(H^3S(A+B)/\epsilon^2) | No clear effect |
Surprising findings
- Value functions from optimistic/pessimistic CCE-based updates do not preserve monotonicity, breaking the standard reference-advantage argument used in single-agent RL.
Limitations
- Dependence on the action counts A and B is AB rather than the tight A+B.
- Horizon-dependence in V-learning remains H^5 and not addressed by this method.
- Output policies are correlated (CCE-based) and require cooperation of both players to execute.
Experimental setup
Metrics: sample complexity (number of episodes to epsilon-optimal Nas
Baselines: Optimistic Nash Q-learning Nash V-learning V-learning model-based algorithms for Markov games
Builds on: Nash Q-learning UCB-advantage optimistic Nash Q-learning certified policies
Closest papers by meaning
- A Sharp Analysis of Model-based Reinforcement Learning with Self-Play (ICML 2021 · similarity 0.94)
- Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games (ICML 2025 · similarity 0.91)
- Sample-Efficient Multi-Agent RL: An Optimization Perspective (ICLR 2024 · similarity 0.91)
- Provable Memory Efficient Self-Play Algorithm for Model-free Reinforcement Learning (ICLR 2024 · similarity 0.90)
- Solving Zero-Sum Convex Markov Games (ICML 2025 · similarity 0.89)
- Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence beyond the Minty Property (AAAI 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.