Minimax-Optimal Policy Regret in Partially Observable Markov Games
Not on the map. Why?
Abstract (arXiv)
We study sequential decision-making in partially observable environments against strategic, adaptive opponents, modeled as partially observable Markov games (POMGs). The central challenge is to learn latent dynamics from partial observations while facing an adversary whose behavior depends on the learner's strategy, making standard regret notions inadequate. We prove that an epoch-based optimistic maximum-likelihood algorithm achieves tildeO(√T) policy regret for fixed problem parameters, with explicit dependence on the horizon, adversary memory, confidence radius, and the aggregate Eluder dimension of the observable-operator error classes. The algorithm deploys one policy per epoch, with geometrically capped epoch lengths, confidence sets built cumulatively from past data, and a statistical termination test that ends an epoch as soon as the data refute the deployed optimistic model. We also prove a matching lower bound, and extend the framework to horizon-adaptive guarantees and geometrically fading adversary memory.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 31 of its 70 references that are in the map. First posted on arXiv 1 Jun 2026.
Builds on
31 of 70 references.
References · 31
- 2019Introduction to Online Convex Optimizationcited by 803
- 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
- 2018Is Q-learning Provably Efficient?cited by 487
- 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
- 2021The Statistical Complexity of Interactive Decision Makingcited by 218
- 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
- 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
- 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
- 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 113
- 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
- 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
- 2019Provably Efficient Q-Learning with Low Switching Costcited by 78
19 more
- 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
- 2013Online Learning with Switching Costs and Other Adaptive Adversariescited by 61
- 2016Reinforcement Learning of POMDPs using Spectral Methodscited by 52
- 2019Strategizing against No-regret Learnerscited by 50
- 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
- 2022GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyondcited by 46
- 2022PAC Reinforcement Learning for Predictive State Representationscited by 43
- 2013Bandits with Switching Costs: T^{2/3} Regretcited by 39
- 2016A PAC RL Algorithm for Episodic POMDPscited by 37
- 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
- 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
- 2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 27
- 2022Planning in Observable POMDPs in Quasipolynomial Timecited by 25
- 2019Bandits with Feedback Graphs and Switching Costscited by 17
- 2022Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limitscited by 17
- 2023On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoringcited by 15
- 2018Policy Regret in Repeated Gamescited by 7
- 2023Posterior Sampling for Competitive RL: Function Approximation and Partial Observationcited by 3
- 2024Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithmscited by 3
Built on by
Not cited yet.