mlsanityData to 7 Oct 2026

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

arXiv 2210.01907 ↗First posted 4 Oct 2022cs.LG cs.AI cs.GTcited by 14

Not on the map. Why?

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.

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

Builds on

24 of 52 references.

References · 24

  1. 2019Dota 2 with Large Scale Deep Reinforcement Learningcited by 1,084
  2. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  3. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
  4. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  5. 2013Learning to Optimize Via Posterior Samplingcited by 253
  6. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  7. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  8. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  9. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  10. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  11. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  12. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
12 more
  1. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  2. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  3. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  4. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  5. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 65
  6. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  7. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  8. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  9. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  10. 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 30
  11. 2020Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iterationcited by 19
  12. 2021A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponentcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 7; 2024: 5; 2025: 0; 2026: 2.

14 papers.

Sort:

By area:

  1. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 346
  2. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  3. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 28
  4. 2024Feel-Good Thompson Sampling for Contextual Dueling Banditscited by 23
  5. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
  6. 2023On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximationcited by 13
  7. 2023A Reduction-based Framework for Sequential Decision Making with Delayed Feedbackcited by 7
  8. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyondcited by 6
  9. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  10. 2024Refined Sample Complexity for Markov Games with Independent Linear Function Approximationcited by 3
  11. 2024Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learningcited by 2
  12. 2024Transformers as Game Players: Provable In-context Game-playing Capabilities of Pre-trained Modelscited by 1
2 more
  1. 2023Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Gamescited by 0
  2. 2026Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximationcited by 0