# A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Games

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 52 references that are in the map.
- First posted on arXiv 4 Oct 2022.

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

- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning](https://mlsanity.com/paper/2106.04895/) (2021)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (2014)
- [Provable Self-Play Algorithms for Competitive Reinforcement Learning](https://mlsanity.com/paper/2002.04017/) (2020)
- [Generalization and Exploration via Randomized Value Functions](https://mlsanity.com/paper/1402.0635/) (2014)
- [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)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium](https://mlsanity.com/paper/2002.07066/) (2020)
- [Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions](https://mlsanity.com/paper/2010.01374/) (2020)
- [Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning](https://mlsanity.com/paper/2110.00871/) (2021)
- [Worst-Case Regret Bounds for Exploration via Randomized Value Functions](https://mlsanity.com/paper/1906.02870/) (2019)
- [Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game](https://mlsanity.com/paper/2205.15512/) (2022)
- [The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces](https://mlsanity.com/paper/2106.03352/) (2021)
- [Towards General Function Approximation in Zero-Sum Markov Games](https://mlsanity.com/paper/2107.14702/) (2021)
- [A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learning](https://mlsanity.com/paper/2208.10904/) (2022)
- [Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/2010.12163/) (2020)
- [A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponent](https://mlsanity.com/paper/2109.03396/) (2021)

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

- [Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint](https://mlsanity.com/paper/2312.11456/) (2023)
- [Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation](https://mlsanity.com/paper/2302.06606/) (2023)
- [Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback](https://mlsanity.com/paper/2303.02738/) (2023)
- [Feel-Good Thompson Sampling for Contextual Dueling Bandits](https://mlsanity.com/paper/2404.06013/) (2024)
- [Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Exploration](https://mlsanity.com/paper/2305.18258/) (2023)
- [On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2305.11283/) (2023)
- [A Reduction-based Framework for Sequential Decision Making with Delayed Feedback](https://mlsanity.com/paper/2302.01477/) (2023)
- [On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond](https://mlsanity.com/paper/2401.03301/) (2024)
- [Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences](https://mlsanity.com/paper/2602.23116/) (2026)
- [Refined Sample Complexity for Markov Games with Independent Linear Function Approximation](https://mlsanity.com/paper/2402.07082/) (2024)
- [Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2404.19292/) (2024)
- [Satellite Chasers: Divergent Adversarial Reinforcement Learning to Engage Intelligent Adversaries on Orbit](https://mlsanity.com/paper/2409.17443/) (2024)
- [Transformers as Game Players: Provable In-context Game-playing Capabilities of Pre-trained Models](https://mlsanity.com/paper/2410.09701/) (2024)
- [Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games](https://mlsanity.com/paper/2308.08858/) (2023)
- [Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximation](https://mlsanity.com/paper/2605.03125/) (2026)
- [Thompson Sampling for Learning in Zero-Sum Games](https://mlsanity.com/paper/2610.18899/) (2026)

## Abstract (arXiv)

Existing studies on provably efficient algorithms for Markov games (MGs) almost exclusively build on the "optimism in the face of uncertainty" (OFU) principle. This work focuses on a different approach of posterior sampling, which is celebrated in many bandits and reinforcement learning settings but remains under-explored for MGs. Specifically, for episodic two-player zero-sum MGs, a novel posterior sampling algorithm is developed with general function approximation. Theoretical analysis demonstrates that the posterior sampling algorithm admits a √T-regret bound for problems with a low multi-agent decoupling coefficient, which is a new complexity measure for MGs, where T denotes the number of episodes. When specialized to linear MGs, the obtained regret bound matches the state-of-the-art results. To the best of our knowledge, this is the first provably efficient posterior sampling algorithm for MGs with frequentist regret guarantees, which enriches the toolbox for MGs and promotes the broad applicability of posterior sampling.