# Posterior Sampling for Competitive RL: Function Approximation and Partial Observation

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 85 references that are in the map.
- First posted on arXiv 30 Oct 2023.

## Builds on (most cited first, 30 of 35)

- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [StarCraft II: A New Challenge for Reinforcement Learning](https://mlsanity.com/paper/1708.04782/) (2017)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Optimism in Reinforcement Learning with Generalized Linear Function Approximation](https://mlsanity.com/paper/1912.04136/) (2019)
- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game](https://mlsanity.com/paper/2205.15512/) (2022)
- [Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage](https://mlsanity.com/paper/2305.09659/) (2023)
- [The Complexity of Markov Equilibrium in Stochastic Games](https://mlsanity.com/paper/2204.03991/) (2022)
- [The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces](https://mlsanity.com/paper/2106.03352/) (2021)
- [GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyond](https://mlsanity.com/paper/2211.01962/) (2022)
- [Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets](https://mlsanity.com/paper/2202.07511/) (2022)
- [Towards General Function Approximation in Zero-Sum Markov Games](https://mlsanity.com/paper/2107.14702/) (2021)
- [PAC Reinforcement Learning for Predictive State Representations](https://mlsanity.com/paper/2207.05738/) (2022)
- [Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Games](https://mlsanity.com/paper/2110.05682/) (2021)
- [Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension](https://mlsanity.com/paper/2005.10804/) (2020)
- [Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systems](https://mlsanity.com/paper/2206.12020/) (2022)
- [Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexity](https://mlsanity.com/paper/2206.07659/) (2022)
- [A General Framework for Sample-Efficient Function Approximation in Reinforcement Learning](https://mlsanity.com/paper/2209.15634/) (2022)
- [Learning in Observable POMDPs, without Computationally Intractable Oracles](https://mlsanity.com/paper/2206.03446/) (2022)
- [Posterior sampling for reinforcement learning: worst-case regret bounds](https://mlsanity.com/paper/1705.07041/) (2017)
- [When is Offline Two-Player Zero-Sum Markov Game Solvable?](https://mlsanity.com/paper/2201.03522/) (2022)
- [Sample-Efficient Reinforcement Learning of Partially Observable Markov Games](https://mlsanity.com/paper/2206.01315/) (2022)
- [Planning in Observable POMDPs in Quasipolynomial Time](https://mlsanity.com/paper/2201.04735/) (2022)
- [On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces](https://mlsanity.com/paper/2011.04622/) (2020)
- [Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limits](https://mlsanity.com/paper/2203.06803/) (2022)
- [Representation Learning for General-sum Low-rank Markov Games](https://mlsanity.com/paper/2210.16976/) (2022)
- [Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Games](https://mlsanity.com/paper/2206.01588/) (2022)
- [Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddings](https://mlsanity.com/paper/2206.12081/) (2022)

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

- [Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2404.19292/) (2024)
- [Minimax-Optimal Policy Regret in Partially Observable Markov Games](https://mlsanity.com/paper/2606.02363/) (2026)
- [Thompson Sampling for Learning in Zero-Sum Games](https://mlsanity.com/paper/2610.18899/) (2026)

## Abstract (arXiv)

This paper investigates posterior sampling algorithms for competitive reinforcement learning (RL) in the context of general function approximations. Focusing on zero-sum Markov games (MGs) under two critical settings, namely self-play and adversarial learning, we first propose the self-play and adversarial generalized eluder coefficient (GEC) as complexity measures for function approximation, capturing the exploration-exploitation trade-off in MGs. Based on self-play GEC, we propose a model-based self-play posterior sampling method to control both players to learn Nash equilibrium, which can successfully handle the partial observability of states. Furthermore, we identify a set of partially observable MG models fitting MG learning with the adversarial policies of the opponent. Incorporating the adversarial GEC, we propose a model-based posterior sampling method for learning adversarial MG with potential partial observability. We further provide low regret bounds for proposed algorithms that can scale sublinearly with the proposed GEC and the number of episodes T. To the best of our knowledge, we for the first time develop generic model-based posterior sampling algorithms for competitive RL that can be applied to a majority of tractable zero-sum MG classes in both fully observable and partially observable MGs with self-play and adversarial learning.