Online Learning in Unknown Markov Games

2020/10/28 by Yi Tian, Tian, Yi, Yuanhao Wang +5
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Search Problems #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2010.15020

openalex publication_date 2020/10/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study online learning in unknown Markov games, a problem that arises in episodic multi-agent reinforcement learning where the actions of the opponents are unobservable. We show that in this challenging setting, achieving sublinear regret against the best response in hindsight is statistically hard. We then consider a weaker notion of regret by competing with the minimax value of the game, and present an algorithm that achieves a sublinear O(K^2/3) regret after K episodes. This is the first sublinear regret bound (to our knowledge) for online learning in unknown Markov games. Importantly, our regret bound is independent of the size of the opponents' action spaces. As a result, even when the opponents' actions are fully observable, our regret bound improves upon existing analysis (e.g., (Xie et al., 2020)) by an exponential factor in the number of opponents.

Citations

• Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
• Provably efficient RL with Rich Observations via Latent State Decoding
• Online Convex Optimization in Adversarial Markov Decision Processes
• Feature-Based Q-Learning for Two-Player Stochastic Games
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• Provable Self-Play Algorithms for Competitive Reinforcement Learning

Related

• Model-Free Online Learning in Unknown Sequential Decision Making\n Problems and Games
• Regret Minimization and Convergence to Equilibria in General-sum Markov Games
• Online Reinforcement Learning in Stochastic Games
• Adaptive Regret Minimization in Bounded-Memory Games
• Online Prediction in Sub-linear Space