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

arXiv: https://arxiv.org/abs/2512.00351 · HTML: https://mlsanity.com/paper/2512.00351/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Multi-agent reinforcement learning, one of 15 directions in Deep reinforcement learning methods.
- First posted on arXiv 29 Nov 2025.

## Placed in

- Deep reinforcement learning methods / [Multi-agent reinforcement learning](https://mlsanity.com/deeprl/multi-agent-reinforcement-learning/)

## Abstract (arXiv)

The thriving field of multi-agent reinforcement learning (MARL) studies how a group of interacting agents make decisions autonomously in a shared dynamic environment. Existing theoretical studies in this area suffer from at least two of the following obstacles: memory inefficiency, the heavy dependence of sample complexity on the long horizon and the large state space, the high computational complexity, non-Markov policy, non-Nash policy, and high burn-in cost. In this work, we take a step towards settling this problem by designing a model-free self-play algorithm Memory-Efficient Nash Q-Learning (ME-Nash-QL) for two-player zero-sum Markov games, which is a specific setting of MARL. ME-Nash-QL is proven to enjoy the following merits. First, it can output an varepsilon-approximate Nash policy with space complexity O(SABH) and sample complexity widetildeO(H4SAB/varepsilon2), where S is the number of states, A, B is the number of actions for two players, and H is the horizon length. It outperforms existing algorithms in terms of space complexity for tabular cases, and in terms of sample complexity for long horizons, i.e., when minA, Bll H2. Second, ME-Nash-QL achieves the lowest computational complexity O(Tpoly(AB)) while preserving Markov policies, where T is the number of samples. Third, ME-Nash-QL also achieves the best burn-in cost O(SAB,poly(H)), whereas previous algorithms have a burn-in cost of at least O(S3 AB,poly(H)) to attain the same level of sample complexity with ours.