A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponent
Not on the map. Why?
Abstract (arXiv)
In this paper, we propose Posterior Sampling Reinforcement Learning for Zero-sum Stochastic Games (PSRL-ZSG), the first online learning algorithm that achieves Bayesian regret bound of O(HS√AT) in the infinite-horizon zero-sum stochastic games with average-reward criterion. Here H is an upper bound on the span of the bias function, S is the number of states, A is the number of joint actions and T is the horizon. We consider the online setting where the opponent can not be controlled and can take any arbitrary time-adaptive history-dependent strategy. Our regret bound improves on the best existing regret bound of O(√[3]DS2AT2) by Wei et al. (2017) under the same assumption and matches the theoretical lower bound in T.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 21 of its 49 references that are in the map. First posted on arXiv 8 Sep 2021.
Builds on
21 of 49 references.
References · 21
- 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
- 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
- 2018Is Q-learning Provably Efficient?cited by 485
- 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
- 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
- 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
- 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
- 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
- 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
- 2020Game-Theoretic Multiagent Reinforcement Learningcited by 92
- 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
- 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
9 more
- 2017Online Reinforcement Learning in Stochastic Gamescited by 67
- 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
- 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
- 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 43
- 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 41
- 2019Feature-Based Q-Learning for Two-Player Stochastic Gamescited by 23
- 2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
- 2021Online Learning for Unknown Partially Observable MDPscited by 17
- 2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
Built on by
Citing papers per year: 2022: 1; 2023: 1; 2024: 0; 2025: 0; 2026: 1.
3 papers.