# Online Learning in Unknown Markov Games

arXiv: https://arxiv.org/abs/2010.15020 · HTML: https://mlsanity.com/paper/2010.15020/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Oct 2020.

## Built on by (most cited first, 9 of 9)

- [Decentralized Q-Learning in Zero-sum Markov Games](https://mlsanity.com/paper/2106.02748/) (2021)
- [Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback](https://mlsanity.com/paper/2303.02738/) (2023)
- [Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?](https://mlsanity.com/paper/2112.13521/) (2021)
- [Provably Efficient Algorithms for Multi-Objective Competitive RL](https://mlsanity.com/paper/2102.03192/) (2021)
- [Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2306.00212/) (2023)
- [Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions](https://mlsanity.com/paper/2207.12463/) (2022)
- [Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Games](https://mlsanity.com/paper/2112.07859/) (2021)
- [Imprecise Multi-Armed Bandits](https://mlsanity.com/paper/2405.05673/) (2024)
- [Taming Equilibrium Bias in Risk-Sensitive Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2405.02724/) (2024)

## Abstract (arXiv)

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 tildeO(K2/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.