Online Learning In Unknown Markov Games

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 \(\tilde\{\mathcal\{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.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keytian2020online

Related papers

• Online Learning For Uninformed Markov Games: Empirical Nash-value Regret And Non-stationarity Adaptation (2026)0.00
• Regret Minimization And Convergence To Equilibria In General-sum Markov Games (2022)0.00
• No-regret Learning In Unknown Games With Correlated Payoffs (2019)0.00
• Online Reinforcement Learning In Markov Decision Process Using Linear Programming (2023)3.58
• Model-free Online Learning In Unknown Sequential Decision Making Problems And Games (2021)5.24
• Learning In Markov Games With Adaptive Adversaries: Policy Regret, Fundamental Barriers, And Efficient Algorithms (2024)0.00
• Dynamic Regret Of Online Markov Decision Processes (2022)0.00
• Towards Optimal Regret In Adversarial Linear Mdps With Bandit Feedback (2023)0.00