mlsanityData to 14 Oct 2026

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

arXiv 2106.06279 ↗First posted 11 Jun 2021stat.ML cs.LGcited by 21

Not on the map. Why?

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.

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

16 of 42 references.

References · 16

  1. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  2. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 113
  3. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 109
  4. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 105
  5. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
  6. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  7. 2014Solving Large Imperfect Information Games Using CFR+cited by 78
  8. 2020Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descentcited by 57
  9. 2019Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functionscited by 26
  10. 2018Revisiting CFR+ and Alternating Updatescited by 19
  11. 2020Stochastic Regret Minimization in Extensive-Form Gamescited by 17
  12. 2018Solving Large Sequential Games with the Excessive Gap Techniquecited by 16
4 more
  1. 2021Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Gamescited by 15
  2. 2021Model-Free Online Learning in Unknown Sequential Decision Making Problems and Gamescited by 12
  3. 2014Computing Approximate Nash Equilibria and Robust Best-Responses Using Samplingcited by 6
  4. 2020Finding and Certifying (Near-)Optimal Strategies in Black-Box Extensive-Form Gamescited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 11; 2023: 2; 2024: 2; 2025: 2; 2026: 4.

21 papers.

Sort:

By area:

  1. 2024Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learningcited by 45
  2. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 30
  3. 2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 27
  4. 2022Near-Optimal Learning of Extensive-Form Games with Imperfect Informationcited by 26
  5. 2025Improving LLM General Preference Alignment via Optimistic Online Mirror Descentcited by 24
  6. 2022The Power of Regularization in Solving Extensive-Form Gamescited by 21
  7. 2022Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limitscited by 17
  8. 2022Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiencycited by 16
  9. 2022Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descentcited by 15
  10. 2022Sample-Efficient Learning of Correlated Equilibria in Extensive-Form Gamescited by 7
  11. 2026The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedbackcited by 5
  12. 2022A Survey of Decision Making in Adversarial Gamescited by 3
9 more
  1. 2022A Deep Reinforcement Learning Approach for Finding Non-Exploitable Strategies in Two-Player Atari Gamescited by 3
  2. 2023A Black-box Approach for Non-stationary Multi-agent Reinforcement Learningcited by 3
  3. 2025Best of Both Worlds: Regret Minimization versus Minimax Playcited by 2
  4. 2022Generalized Bandit Regret Minimizer Framework in Imperfect Information Extensive-Form Gamecited by 1
  5. 2024Configurable Mirror Descent: Towards a Unification of Decision Makingcited by 1
  6. 2026Differential Privacy in the Extensive-Form Bandit Problemcited by 1
  7. 2022Approximate Nash Equilibrium Learning for n-Player Markov Games in Dynamic Pricingcited by 0
  8. 2026Reinforcement Learning: From Algorithms To Foundation Modelscited by 0
  9. 2026Tracking the Best Strategy in an Extensive-Form Gamecited by 0