Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibrium
Not on the map. Why?
Abstract (arXiv)
We consider learning Nash equilibria in two-player zero-sum Markov Games with nonlinear function approximation, where the action-value function is approximated by a function in a Reproducing Kernel Hilbert Space (RKHS). The key challenge is how to do exploration in the high-dimensional function space. We propose a novel online learning algorithm to find a Nash equilibrium by minimizing the duality gap. At the core of our algorithms are upper and lower confidence bounds that are derived based on the principle of optimism in the face of uncertainty. We prove that our algorithm is able to attain an O(√T) regret with polynomial computational complexity, under very mild assumptions on the reward function and the underlying dynamic of the Markov Games. We also propose several extensions of our algorithm, including an algorithm with Bernstein-type bonus that can achieve a tighter regret bound, and another algorithm for model misspecification that can be applied to neural function approximation.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 29 of its 59 references that are in the map. First posted on arXiv 10 Aug 2022.
Builds on
29 of 59 references.
References · 29
- 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
- 2017On Kernelized Multi-armed Banditscited by 352
- 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 311
- 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
- 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
- 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
- 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 222
- 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
- 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
- 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
- 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
- 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
17 more
- 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 114
- 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 113
- 2020Near-Optimal Reinforcement Learning with Self-Playcited by 109
- 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 105
- 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
- 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
- 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
- 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
- 2017Online Reinforcement Learning in Stochastic Gamescited by 67
- 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
- 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 43
- 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 42
- 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
- 2019Feature-Based Q-Learning for Two-Player Stochastic Gamescited by 24
- 2016Learning Nash Equilibrium for General-Sum Markov Games from Batch Datacited by 20
- 2021On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Gamecited by 20
- 2020Minimax Sample Complexity for Turn-based Stochastic Gamecited by 13
Built on by
Citing papers per year: 2023: 1.
1 paper.