DeLTA seminar by Haipeng Luo

Speaker

Haipeng Luo, University of Southern California

Title

The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition

Abstract

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 (FTRL) framework together with a set of new techniques. Specifically, we first propose a loss-shifting trick in the 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.

_____________________________
Upcoming DeLTA seminars:

6 September 2021 @ 10:00. Ola Rønning.
13 September 2021 @ 10:00. Shinji Ito.
-------------------
You can subscribe to DeLTA Seminar mailing list by sending an empty email to delta-seminar-join@list.ku.dk.
Information about DeLTA Seminars is available at DeLTA Lab page: https://sites.google.com/diku.edu/delta