Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning

We provide improved gap-dependent regret bounds for reinforcement learning in\nfinite episodic Markov decision processes. Compared to prior work, our bounds\ndepend on alternative definitions of gaps. These definitions are based on the\ninsight that, in order to achieve a favorable regret, an algorithm does not\nneed to learn how to behave optimally in states that are not reached by an\noptimal policy. We prove tighter upper regret bounds for optimistic algorithms\nand accompany them with new information-theoretic lower bounds for a large\nclass of MDPs. Our results show that optimistic algorithms can not achieve the\ninformation-theoretic lower bounds even in deterministic MDPs unless there is a\nunique optimal policy.\n