Episodic reinforcement learning in finite MDPs: Minimax lower bounds revisited
2021 · in (ALT 2021)
Abstract
In this paper, we propose new problem-independent lower bounds on the sample complexity and regret in episodic MDPs, with a particular focus on the non-stationary case in which the transition kernel is allowed to change in each stage of the episode. Our main contribution is a lower bound of Omega((H^3SA/epsilon^2)log(1/delta)) on the sample complexity of an (epsilon,delta)-PAC algorithm for best policy identification in a non-stationary MDP, relying on a construction of "hard MDPs" which is different from the ones previously used in the literature. Using this same class of MDPs, we also provide a rigorous proof of the Omega(sqrt(H^3SAT)) regret bound for non-stationary MDPs. Finally, we discuss connections to PAC-MDP lower bounds.
PDF · Algorithmic Learning Theory · arXiv preprint · video · bibtex · DOI