We consider the best-of-both-worlds problem for learning an episodic Markov Decision Process through $T$ episodes, with the goal of achieving $\widetilde{ \mathcal{ O}}(\sqrt{ T})$ regret when the losses are adversarial and simultaneously $\mathcal{ O}(\text{ polylog}(T))$ regret when the losses are (almost) stochastic. Recent work by [Jin and Luo, 2020] achieves this goal when the fixed transition is known, and leaves the case of unknown transition as a major open question. In this work, we resolve this open problem by using the same Follow-the-Regularized-Leader ($\text{ FTRL}$) framework together with a set of new techniques. Specifically, we first propose a loss-shifting trick in the $\text{ FTRL}$ analysis, which greatly simplifies the approach of [Jin and Luo, 2020] and already improves their results for the known transition case. Then, we extend this idea to the unknown transition case and develop a novel analysis which upper bounds the transition estimation error by (a fraction of) the regret itself in the stochastic setting, a key property to ensure $\mathcal{ O}(\text{ polylog}(T))$ regret.
Categories: cs.LG