Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited
By Omar Darwiche Domingues, Pierre M'enard, Emilie Kaufmann, Michal Valko. 2020
118 citations recorded by the source corpus.
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 $\Omega((H^3SA/\epsilon^2)\log(1/\delta))$ on the sample complexity of an $(\varepsilon,\delta)$-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 $\Omega(\sqrt{H^3SAT})$ regret bound for non-stationary MDPs. Finally, we discuss connections to PAC-MDP lower bounds.
Subfields: Reinforcement Learning
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Reinforcement Learning
Citations in the corpus
- Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, background): “…2013; Dann and Brunskill, 2015; Dann et al., 2017; Domingues et al., 2020a; Lattimore and Hutter, 2012) and minimizing regret via balancing exploration and exploitation (Zhang and Ji, 2019; Azar et al., 2017; Ortner, 2020; Talebi and Maillard, 2018; Efroni et al., 2020; Domingues et al., 2020b).”
- Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms (2021, background): “Moreover, the bound is proved to be minimax-optimal [29, 31].”