Neural Information Processing Systems http://nips.cc/

The environment and an agent's interactions are typically modeled as a Markov

Neural Information Processing Systems http://nips.cc/

Thus, the multiplicity of the optimal policies does not break the assumption. A.2 Omitted Algorithms Algorithm 4 Model-Free Sampling Routine Require: In this section, our main goal is to prove Theorem 3.1. The proofs of the supporting lemmas are postponed to Appendix B.1. The regret decomposition in [HZG21], gives us that 15 Lemma B.1. The following lemma resembles Lemma 6.3 [HZG21].

In this paper, we study the problem of regret minimization for episodic Reinforcement Learning (RL) both in the model-free and the model-based setting.

We begin with the proof of thresholding technique. A.1 Definitions We first restate the notations. Definition A.2 (Pessimistically estimated MDP) . F or a given successful pessimistic algorithm execution instance, where the arguments in Definition A.1 are simultaneously satisfied, we call In the following proof of Corollary A.1, we will set Rigorous proof is deferred to Appendix A.4 With Theorem A.1, we just need to prove that The following lemmas will be frequently used throughout the proof of Theorem A.1 and upper Algorithm used here is Lower Confidence Bound V alue Iteration(VI-LCB)[Xie et al., 2021b] with The basic idea of LCB is to pessimistically estimate the Q function so that the algorithm won't over estimate some hardly seen suboptimal actions in The subsampling trick introduced by Li et al. [2022] helps solve the independence problem Superscripts stand for the dataset. See Li et al. [2022] for a more detailed description of the algorithm.

Instead, we have access to a dataset generated from some past suboptimal policies.

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

This paper presents a systematic study on gap-dependent sample complexity in offline reinforcement learning. Prior work showed when the density ratio between an optimal policy and the behavior policy is upper bounded (the optimal policy coverage assumption), then the agent can achieve an $O\left(\frac{1}{\epsilon^2}\right)$ rate, which is also minimax optimal. We show under the optimal policy coverage assumption, the rate can be improved to $O\left(\frac{1}{\epsilon}\right)$ when there is a positive sub-optimality gap in the optimal $Q$-function. Furthermore, we show when the visitation probabilities of the behavior policy are uniformly lower bounded for states where an optimal policy's visitation probabilities are positive (the uniform optimal policy coverage assumption), the sample complexity of identifying an optimal policy is independent of $\frac{1}{\epsilon}$. Lastly, we present nearly-matching lower bounds to complement our gap-dependent upper bounds.