Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited
This work addresses foundational theoretical limits in reinforcement learning for non-stationary environments, which is incremental as it revisits and refines existing lower bounds.
The paper tackles the problem of establishing lower bounds on sample complexity and regret in episodic reinforcement learning for non-stationary MDPs, where transition kernels change per stage, and provides a new lower bound of Ω((H^3SA/ε^2)log(1/δ)) for best policy identification and a proof of Ω(√(H^3SAT)) regret.
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 novel lower bound of $Ω((H^3SA/ε^2)\log(1/δ))$ on the sample complexity of an $(\varepsilon,δ)$-PAC algorithm for best policy identification in a non-stationary MDP. This lower bound relies 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 $Ω(\sqrt{H^3SAT})$ regret bound for non-stationary MDPs. Finally, we discuss connections to PAC-MDP lower bounds.