Online Learning in Unknown Markov Games
This addresses a fundamental challenge in multi-agent reinforcement learning for scenarios with unobservable opponents, offering a novel regret bound that scales better than existing methods.
The paper tackles the problem of online learning in unknown Markov games, where opponents' actions are unobservable, and shows that achieving sublinear regret against the best response is statistically hard; it then presents an algorithm that achieves sublinear regret of $ ilde{\mathcal{O}}(K^{2/3})$ against the minimax value, which is the first such bound and improves upon prior work by an exponential factor in the number of opponents.
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 \emph{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.