# Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recall

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 42 references that are in the map.
- First posted on arXiv 11 Jun 2021.

## Builds on (most cited first, 16 of 16)

- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Provable Self-Play Algorithms for Competitive Reinforcement Learning](https://mlsanity.com/paper/2002.04017/) (2020)
- [Near-Optimal Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2006.12007/) (2020)
- [A Sharp Analysis of Model-based Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2010.01604/) (2020)
- [Learning Adversarial MDPs with Bandit Feedback and Unknown Transition](https://mlsanity.com/paper/1912.01192/) (2019)
- [Online Convex Optimization in Adversarial Markov Decision Processes](https://mlsanity.com/paper/1905.07773/) (2019)
- [Solving Large Imperfect Information Games Using CFR+](https://mlsanity.com/paper/1407.5042/) (2014)
- [Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent](https://mlsanity.com/paper/2007.14358/) (2020)
- [Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions](https://mlsanity.com/paper/1910.10906/) (2019)
- [Revisiting CFR+ and Alternating Updates](https://mlsanity.com/paper/1810.11542/) (2018)
- [Stochastic Regret Minimization in Extensive-Form Games](https://mlsanity.com/paper/2002.08493/) (2020)
- [Solving Large Sequential Games with the Excessive Gap Technique](https://mlsanity.com/paper/1810.03063/) (2018)
- [Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Games](https://mlsanity.com/paper/2103.04546/) (2021)
- [Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games](https://mlsanity.com/paper/2103.04539/) (2021)
- [Computing Approximate Nash Equilibria and Robust Best-Responses Using Sampling](https://mlsanity.com/paper/1401.4591/) (2014)
- [Finding and Certifying (Near-)Optimal Strategies in Black-Box Extensive-Form Games](https://mlsanity.com/paper/2009.07384/) (2020)

## Built on by (most cited first, 21 of 21)

- [Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learning](https://mlsanity.com/paper/2407.00617/) (2024)
- [Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation](https://mlsanity.com/paper/2302.06606/) (2023)
- [Sample-Efficient Reinforcement Learning of Partially Observable Markov Games](https://mlsanity.com/paper/2206.01315/) (2022)
- [Near-Optimal Learning of Extensive-Form Games with Imperfect Information](https://mlsanity.com/paper/2202.01752/) (2022)
- [Improving LLM General Preference Alignment via Optimistic Online Mirror Descent](https://mlsanity.com/paper/2502.16852/) (2025)
- [The Power of Regularization in Solving Extensive-Form Games](https://mlsanity.com/paper/2206.09495/) (2022)
- [Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limits](https://mlsanity.com/paper/2203.06803/) (2022)
- [Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency](https://mlsanity.com/paper/2204.09787/) (2022)
- [Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descent](https://mlsanity.com/paper/2205.15294/) (2022)
- [Sample-Efficient Learning of Correlated Equilibria in Extensive-Form Games](https://mlsanity.com/paper/2205.07223/) (2022)
- [The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2604.16087/) (2026)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [A Deep Reinforcement Learning Approach for Finding Non-Exploitable Strategies in Two-Player Atari Games](https://mlsanity.com/paper/2207.08894/) (2022)
- [A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2306.07465/) (2023)
- [Best of Both Worlds: Regret Minimization versus Minimax Play](https://mlsanity.com/paper/2502.11673/) (2025)
- [Generalized Bandit Regret Minimizer Framework in Imperfect Information Extensive-Form Game](https://mlsanity.com/paper/2203.05920/) (2022)
- [Configurable Mirror Descent: Towards a Unification of Decision Making](https://mlsanity.com/paper/2405.11746/) (2024)
- [Differential Privacy in the Extensive-Form Bandit Problem](https://mlsanity.com/paper/2605.05266/) (2026)
- [Approximate Nash Equilibrium Learning for n-Player Markov Games in Dynamic Pricing](https://mlsanity.com/paper/2207.06492/) (2022)
- [Reinforcement Learning: From Algorithms To Foundation Models](https://mlsanity.com/paper/2607.17560/) (2026)
- [Tracking the Best Strategy in an Extensive-Form Game](https://mlsanity.com/paper/2608.09501/) (2026)

## Abstract (arXiv)

We study the problem of learning a Nash equilibrium (NE) in an imperfect information game (IIG) through self-play. Precisely, we focus on two-player, zero-sum, episodic, tabular IIG under the perfect-recall assumption where the only feedback is realizations of the game (bandit feedback). In particular, the dynamic of the IIG is not known -- we can only access it by sampling or interacting with a game simulator. For this learning setting, we provide the Implicit Exploration Online Mirror Descent (IXOMD) algorithm. It is a model-free algorithm with a high-probability bound on the convergence rate to the NE of order 1/√T where T is the number of played games. Moreover, IXOMD is computationally efficient as it needs to perform the updates only along the sampled trajectory.