Research map / Multi-agent systems and games / Games and equilibria
Provable Memory Efficient Self-Play Algorithm for Model-free Reinforcement Learning
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 ME-Nash-QL, a model-free self-play Nash Q-learning algorithm for two-player zero-sum Markov games with O(SABH) space, O(T poly(AB)) computation, H^4SAB/eps^2 sample complexity and low burn-in cost, outputting Markov Nash policies.
Problem
Model-free self-play learning of approximate Nash equilibria in two-player zero-sum tabular Markov games with good memory, sample, computational efficiency and burn-in cost, while outputting Markov Nash policies.
Approach
Combines Nash Q-learning with UCB/LCB exploration, reference-advantage decomposition for variance reduction, and an early-settlement rule for reference values, using CCE computed by linear programming to output a single Markov policy.
Key results
- ME-Nash-QL achieves epsilon-approximate Nash equilibrium with sample complexity H^4SAB/eps^2 (up to logs) and space complexity O(SABH).
- Burn-in cost is O(SABH^10) versus at least O(S^3ABH^4) for Nash-VI at the same sample complexity.
- Computational complexity is O(T poly(AB)), lower than Nash-VI's O(T poly(SAB)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ME-Nash-QL instead of V-learning | Tabular two-player zero-sum Markov games · Tabular two-player zero-sum Markov games | sample complexity: \widetilde{O}(H^6S(A+B)/\varepsilon^2) -> \widetilde{O}(H^4SAB/\varepsilon^2) | Helped |
| Use ME-Nash-QL instead of Nash-VI | Tabular two-player zero-sum Markov games · Tabular two-player zero-sum Markov games | space complexity: O(S^2ABH) -> O(SABH) | Helped |
| Use ME-Nash-QL instead of Nash-VI | Tabular two-player zero-sum Markov games · Tabular two-player zero-sum Markov games | computational complexity: O(T\mathrm{poly}(SAB)) -> O(T\mathrm{poly}(AB)) | Helped |
| Use ME-Nash-QL instead of Nash-VI | Tabular two-player zero-sum Markov games · Tabular two-player zero-sum Markov games | burn-in cost: \widetilde{O}(S^3ABH^4) -> \widetilde{O}(SABH^{10}) | Helped |
| Use ME-Nash-QL instead of Nash Q-learning | Tabular two-player zero-sum Markov games · Tabular two-player zero-sum Markov games | sample complexity: H^6SAB/\varepsilon^2 -> \widetilde{O}(H^4SAB/\varepsilon^2) | Helped |
Limitations
- Purely theoretical analysis with no empirical experiments.
- Sample complexity depends on A*B product, so no improvement to A+B dependence.
- Burn-in cost SABH^10 is large in H.
Experimental setup
Metrics: sample complexity space complexity computational complexity burn-in cost regret
Baselines: V-learning Nash V-learning Nash Q-learning PReFI PReBO OMNI-VI Nash-UCRL Optimistic PO VI-Explore VI-ULCB Nash-VI Q-learning
Builds on: Nash Q-learning Q-learning with UCB reference-advantage decomposition Nash-VI V-learning
Closest papers by meaning
- Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games (ICML 2024 · similarity 0.90)
- Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints (ICML 2024 · similarity 0.89)
- Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games (ICML 2025 · similarity 0.89)
- Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RL (ICML 2024 · similarity 0.88)
- Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamics (NeurIPS 2026 · similarity 0.88)
- Sample-Efficient Multi-Agent RL: An Optimization Perspective (ICLR 2024 · similarity 0.88)
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.