Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited

In this paper, we propose new problem-independent lower bounds on the sample\ncomplexity and regret in episodic MDPs, with a particular focus on the\nnon-stationary case in which the transition kernel is allowed to change in each\nstage of the episode. Our main contribution is a novel lower bound of\n$\\Omega((H^3SA/\\epsilon^2)\\log(1/\\delta))$ on the sample complexity of an\n$(\\varepsilon,\\delta)$-PAC algorithm for best policy identification in a\nnon-stationary MDP. This lower bound relies on a construction of "hard MDPs"\nwhich is different from the ones previously used in the literature. Using this\nsame class of MDPs, we also provide a rigorous proof of the\n$\\Omega(\\sqrt{H^3SAT})$ regret bound for non-stationary MDPs. Finally, we\ndiscuss connections to PAC-MDP lower bounds.\n