Near-Optimal $\sqrt{K}$-Regret for Online Learning in Uninformed Markov Games
We study online learning in two-player uninformed Markov games, where the opponent may follow an arbitrary, unknown policy in each episode and the learner does not observe the opponent's actions. [TWYS21] showed that achieving sublinear external regret requires an exponential dependence on the episode length $H$. Motiv...