Corruption-Robust Exploration in Episodic Reinforcement Learning

The authors thank Christina Lee Yu, Sean Sinclair, and Éva Tardos for useful discussions that helped improve the presentation of this paper, as well as the anonymous review teams at the 34th Annual Conference on Learning Theory and Mathematics of Operations Research for their valuable feedback. A previous version of this paper appeared on arXiv.org in November 2019, focusing on tabular RL (Theorem 2.1). The extension to linear MDPs (Theorem 2.2) was added in April 2020. A one-page abstract appeared in the Proceedings of the 34th Annual Conference on Learning Theory. All results were obtained while T. Lykouris and W. Sun were postdocs and M. Simchowitz was an intern at Microsoft Research Lab–New York City.