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

Abstract:
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.

heading: 1 Introduction
text: Reinforcement Learning (RL) is a general scenario where agents interact with the environment to achieve some goal. The environment and an agent’s interactions are typically modeled as a Markov decision process (MDP) [29], which can represent a rich variety of tasks. But, for which MDPs can an agent or an RL algorithm succeed? This requires a theoretical analysis of the complexity of an MDP. This paper studies this question in the tabular episodic setting, where an agent interacts with the environment in episodes of fixed length H and where the size of the state and action space is finite (S and A respectively).
While the performance of RL algorithms in tabular Markov decision processes has been the subject of many studies in the past [e.g. 11, 22, 28, 7, 4, 20, 34, 6], the vast majority of existing analyses focuses on worst-case problem-independent regret bounds, which only take into account the size of the MDP, the horizon H and the number of episodes K.
Recently, however, some significant progress has been achieved towards deriving more optimistic (problem-dependent) guarantees. This includes more refined regret bounds for the tabular episodic setting that depend on structural properties of the specific MDP considered [30, 25, 21, 13, 17]. Motivated by instance-dependent analyses in multi-armed bandits [24], these analyses derive gapdependent regret-bounds of the form O (∑ (s,a)∈S×A H log(K) gap(s,a) ) , where the sum is over state-actions pairs (s, a) and where the gap notion is defined as the difference of the optimal value function V ∗ of the Bellman optimal policy π∗ and the Q-function of π∗ at a sub-optimal action: gap(s, a) =
∗Author was at Johns Hopkins University during part of this work.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
V ∗(s)−Q∗(s, a). We will refer to this gap definition as value-function gap in the following. We note that a similar notion of gap has been used in the infinite horizon setting to achieve instance-dependent bounds [1, 31, 2, 12, 27], however, a strong assumption about irreducibility of the MDP is required.
While regret bounds based on these value function gaps generalize the bounds available in the multiarmed bandit setting, we argue that they have a major limitation. The bound at each state-action pair depends only on the gap at the pair and treats all state-action pairs equally, ignoring their topological ordering in the MDP. This can have a major impact on the derived bound. In this paper, we address this issue and formalize the following key observation about the difficulty of RL in an episodic MDP through improved instance-dependent regret bounds:
Learning a policy with optimal return does not require an RL agent to distinguish between actions with similar outcomes (small value-function gap) in states that can only be reached by taking highly suboptimal actions (large value-function gap).
To illustrate this insight, consider autonomous driving, where each episode corresponds to driving from a start to a destination. If the RL agent decides to run a red light on a crowded intersection, then a car crash is inevitable. Even though the agent could slightly affect the severity of the car crash by steering, this effect is small and, hence, a good RL agent does not need to learn how to best steer after running a red light. Instead, it would only need a few samples to learn to obey the traffic light in the first place as the action of disregarding a red light has a very large value-function gap.
To understand how this observation translates into regret bounds, consider the toy example in Figure 1. This MDP has deterministic transitions and only terminal rewards with c > 0. There are two decision points, s1 and s2, with two actions each, and all other states have a single action. There are three policies which govern the regret bounds: π∗ (red path) which takes action a1 in state s1; π1 which takes action a2 at s1 and a3 at s2 (blue path); and π2 which takes action a2 at s1 and a4 at s2 (green path). Since π∗ follows the red path, it never reaches s2 and achieves optimal return c+ , while π1 and π2 are both suboptimal with return and 0 respectively. Existing value-function gaps evaluate to gap(s1, a2) = c and gap(s2, a4) = which yields a regret bound of order H log(K)(1/c+ 1/ ). The idea behind these bounds is to capture the necessary number of episodes to distinguish the value of the optimal policy π∗ from the value of any other sub-optimal policy on all states. However, since π∗ will never reach s2 it is not necessary to distinguish it from any other policy at s2. A good algorithm only needs to determine that a2 is sub-optimal in s1, which eliminates both π1 and π2 as optimal policies after only log(K)/c2 episodes. This suggests a regret of order O(log(K)/c). The bounds presented in this paper achieve this rate up to factors of H by replacing the gaps at every state-action pair with the average of all gaps along certain paths containing the state action pair. We call these averaged gaps return gaps. The return gap at (s, a) is denoted as gap(s, a). Our new bounds replace gap(s2, a4) = by gap(s2, a4) ≈ 12 gap(s1, a2) + 1 2 gap(s2, a4) = Ω(c). Notice that and c can be selected arbitrarily in this example. In particular, if we take c = 0.5 and = 1/ √ K our bounds remain logarithmic O(log(K)), while prior regret bounds scale as √ K.
This work is motivated by the insight just discussed. First, we show that improved regret bounds are indeed possible by proving a tighter regret bound for STRONGEULER, an existing algorithm
based on the optimism-in-the-face-of-uncertainty (OFU) principle [30]. Our regret bound is stated in terms of our new return gaps that capture the problem difficulty more accurately and avoid explicit dependencies on the smallest value function gap gapmin. Our technique applies to optimistic algorithms in general and as a by-product improves the dependency on episode length H of prior results. Second, we investigate the difficulty of RL in episodic MDPs from an information-theoretic perspective by deriving regret lower-bounds. We show that existing value-function gaps are indeed sufficient to capture difficulty of problems but only when each state is visited by an optimal policy with some probability. Finally, we prove a new lower bound when the transitions of the MDP are deterministic that depends only on the difference in return of the optimal policy and suboptimal policies, which is closely related to our notion of return gap.

heading: 2 Problem setting and notation
text: We consider reinforcement learning in episodic tabular MDPs with a fixed horizon. An MDP can be described as a tuple (S,A, P,R,H), where S and A are state- and action-space of size S and A respectively, P is the state transition distribution with P (·|s, a) ∈ ∆S−1 the next state probability distribution, given that action a was taken in the current state s. R is the reward distribution defined over S ×A and r(s, a) = E[R(s, a)] ∈ [0, 1]. Episodes admit a fixed length or horizon H . We consider layered MDPs: each state s ∈ S belongs to a layer κ(s) ∈ [H] and the only non-zero transitions are between states s, s′ in consecutive layers, with κ(s′) = κ(s) + 1. This common assumption [see e.g. 23] corresponds to MDPs with time-dependent transitions, as in [20, 7], but allows us to omit an explicit time-index in value-functions and policies. For ease of presentation, we assume there is a unique start state s1 with κ(s1) = 1 but our results can be generalized to multiple (possibly adversarial) start states. Similarly, for convenience, we assume that all states are reachable by some policy with non-zero probability, but not necessarily all policies or the same policy.
We denote by K the number of episodes during which the MDP is visited. Before each episode k ∈ [K], the agent selects a deterministic policy πk : S → A out of a set of all policies Π and πk is then executed for all H time steps in episode k. For each policy π, we denote by wπ(s, a) = P(Sκ(s) = s,Aκ(s) = a | Ah = π(Sh) ∀h ∈ [H]) and wπ(s) = ∑ a w
π(s, a) probability of reaching stateaction pair (s, a) and state s respectively when executing π. For convenience, supp(π) = {s ∈ S : wπ(s) > 0} is the set of states visited by π with non-zero probability. The Q- and value function of a policy π are
Qπ(s, a) = Eπ
[ H∑
h=κ(s)
r(Sh, Ah) ∣∣∣∣∣ Sκ(s) = s,Aκ(s) = a ] , and V π(s) = Qπ(s, π(s))
and the regret incurred by the agent is the sum of its regret over K episodes
R(K) = K∑ k=1 v∗ − vπk = K∑ k=1 V ∗(s1)− V πk(s1), (1)
where vπ = V π(s1) is the expected total sum of rewards or return of π and V ∗ is the optimal value function V ∗(s) = maxπ∈Π V π(s). Finally, the set of optimal policies is denoted as Π∗ = {π ∈ Π : V π = V ∗}. Note that we only call a policy optimal if it satisfies the Bellman equation in every state, as is common in literature, but there may be policies outside of Π∗ that also achieve maximum return because they only take suboptimal actions outside of their support. The variance of the Q function at a state-action pair (s, a) of the optimal policy is V∗(s, a) = V[R(s, a)] + Vs′∼P (·|s,a)[V ∗(s′)], where V[X] denotes the variance of the r.v. X . The maximum variance over all state-action pairs is V∗ = max(s,a) V∗(s, a). Finally, our proofs will make use of the following clipping operator clip[a|b] = χ(a ≥ b)a that sets a to zero if it is smaller than b, where χ is the indicator function.

heading: 3 Novel upper bounds for optimistic algorithms
text: In this section, we present tighter regret upper-bounds for optimistic algorithms through a novel analysis technique. Our technique can be generally applied to model-based optimistic algorithms such as STRONGEULER [30], UCBVI [3], ORLC [9] or EULER [34]. In the following, we will first
give a brief overview of this class of algorithms (see Appendix B for more details) and then state our main results for the STRONGEULER algorithm [30]. We focus on this algorithm for concreteness and ease of comparison.
Optimistic algorithms maintain estimators of the Q-functions at every state-action pair such that there exists at least one policy π for which the estimator, Q̄π, overestimates the Q-function of the optimal policy, that is Q̄π(s, a) ≥ Q∗(s, a),∀(s, a) ∈ S×A. During episode k ∈ [K], the optimistic algorithm selects the policy πk with highest optimistic value function V̄k. By definition, it holds that V̄k(s) ≥ V ∗(s). The optimistic value and Q-functions are constructed through finite-sample estimators of the true rewards r(s, a) and the transition kernel P (·|s, a) plus bias terms, similar to estimators for the UCB-I multi-armed bandit algorithm. Careful construction of these bias terms is crucial for deriving min-max optimal regret bounds in S,A and H [4]. Bias terms which yield the tightest known bounds come from concentration of martingales results such as Freedman’s inequality [14] and empirical Bernstein’s inequality for martingales [26].
The STRONGEULER algorithm not only satisfies optimism, i.e., V̄k ≥ V ∗, but also a stronger version called strong optimism. To define strong optimism we need the notion of surplus which roughly measures the optimism at a fixed state-action pair. Formally the surplus at (s, a) during episode k is defined as
Ek(s, a) = Q̄k(s, a)− r(s, a)− 〈P (·|s, a), V̄k〉 . (2) We say that an algorithm is strongly optimistic if Ek(s, a) ≥ 0,∀(s, a) ∈ S ×A, k ∈ [K]. Surpluses are also central to our new regret bounds and we will carefully discuss their use in Appendix F.
As hinted to in the introduction, the way prior regret bounds treat value-function gaps independently at each state-action pair can lead to excessively loose guarantees. Bounds that use value-function gaps [30, 25, 21] scale at least as∑
s,a : gap(s,a)>0
H log(K) gap(s, a) + ∑ s,a : gap(s,a)=0 H log(K) gapmin ,
where state-action pairs with zero gap appear, with gapmin = mins,a : gap(s,a)>0 gap(s, a), the smallest positive gap. To illustrate where these bounds are loose, let us revisit the example in Figure 1. Here, these bounds evaluate to H log(K)c + H log(K) + SH log(K) , where the first two terms come from state-action pairs with positive value-function gaps and the last term comes from all the state-action pairs with zero gaps. There are several opportunities for improvement:
O.1 State-action pairs that can only be visited by taking optimal actions: We should not pay the 1/ gapmin factor for such (s, a) as there are no other suboptimal policies π to distinguish from π∗ in such states.
O.2 State-action pairs that can only be visited by taking at least one suboptimal action: We should not pay the 1/ gap(s2, a3) factor for state-action pair (s2, a3) and the 1/ gapmin factor for (s2, a4) because no optimal policy visits s2. Such state-action pairs should only be accounted for with the price to learn that a2 is not optimal in state s1. After all, learning to distinguish between π1 and π2 is unnecessary for optimal return.
Both opportunities suggest that the price 1gap(s,a) or 1 gapmin that each state-action pair (s, a) contributes to the regret bound can be reduced by taking into account the regret incurred by the time (s, a) is reached. Opportunity O.1 postulates that if no regret can be incurred up to (and including) the time step (s, a) is reached, then this state-action pair should not appear in the regret bound. Similarly, if this regret is necessarily large, then the agent can learn this with few observations and stop reaching (s, a) earlier than gap(s, a) may suggest. Thus, as claimed in O.2, the contribution of (s, a) to the regret should be more limited in this case.
Since the total regret incurred during one episode by a policy π is simply the expected sum of value-function gaps visited (Lemma F.1 in the appendix),
v∗ − vπ = Eπ [ H∑ h=1 gap(Sh, Ah) ] , (3)
we can measure the regret incurred up to reaching (St, At) by the sum of value function gaps∑t h=1 gap(Sh, Ah) up to this point t. We are interested in the regret incurred up to visiting a certain
state-action pair (s, a) which π may visit only with some probability. We therefore need to take the expectation of such gaps conditioned on the event that (s, a) is actually visited. We further condition on the event that this regret is nonzero, which is exactly the case when the agent encounters a positive value-function gap within the first κ(s) time steps. We arrive at
Eπ κ(s)∑ h=1 gap(Sh, Ah) ∣∣∣∣ Sκ(s) = s,Aκ(s) = a,B ≤ κ(s)  ,
where B = min{h ∈ [H + 1] : gap(Sh, Ah) > 0} is the first time a non-zero gap is visited. This quantity measures the regret incurred up to visiting (s, a) through suboptimal actions. If this quantity is large for all policies π, then a learner will stop visiting this state-action pair after few observations because it can rule out all actions that lead to (s, a) quickly. Conversely, if the event that we condition on has zero probability under any policy, then (s, a) can only be reached through optimal action choices (including a in s) and incurs no regret. This motivates our new definition of gaps that combines value function gaps with the regret incurred up to visiting the state-action pair: Definition 3.1 (Return gap). For any state-action pair (s, a) ∈ S × A define B(s, a) ≡ {B ≤ κ(s), Sκ(s) = s,Aκ(s) = a}, where B is the first time a non-zero gap is encountered. B(s, a) denotes the event that state-action pair (s, a) is visited and that a suboptimal action was played at any time up to visiting (s, a). We define the return gap as
gap(s, a) ≡ gap(s, a) ∨ min π∈Π:
Pπ(B(s,a))>0
1
H Eπ κ(s)∑ h=1 gap(Sh, Ah) ∣∣∣∣ B(s, a) 
if there is a policy π ∈ Π with Pπ(B(s, a)) > 0 and gap(s, a) ≡ 0 otherwise.
The additional 1/H factor in the second term is a required normalization suggesting that it is the average gap rather than their sum that matters. We emphasize that Definition 3.1 is independent of the choice of RL algorithm and in particular does not depend on the algorithm being optimistic. Thus, we expect our main ideas and techniques to be useful beyond the analysis of optimistic algorithms. Equipped with this definition, we are ready to state our main upper bound which pertains to the STRONGEULER algorithm proposed by Simchowitz and Jamieson [30]. Theorem 3.2 (Main Result (Informal)). The regret R(K) of STRONGEULER is bounded with high probability for all number of episodes K as
R(K) / ∑
(s,a)∈S×A : gap(s,a)>0
V∗(s, a) gap(s, a) logK.
In the above, we have restricted the bound to only those terms that have inverse polynomial dependence on the gaps.
Comparison with existing gap-dependent bounds. We now compare our bound to the existing gap-dependent bound for STRONGEULER by Simchowitz and Jamieson [30, Corollary B.1]
R(K) / ∑
(s,a)∈S×A : gap(s,a)>0
HV∗(s, a) gap(s, a)
logK + ∑
(s,a)∈S×A : gap(s,a)=0
HV∗
gapmin logK. (4)
We here focus only on terms that admit a dependency on K and an inverse-polynomial dependency on gaps as all other terms are comparable. Most notable is the absence of the second term of (4) in our bound in Theorem 3.2. Thus, while state-action pairs with gap(s, a) = 0 do not contribute to our regret bound, they appear with a 1/ gapmin factor in existing bounds. Therefore, our bound addresses O.1 because it does not pay for state-action pairs that can only be visited through optimal actions. Further, state-action pairs that do contribute to our bound satisfy 1gap(s,a) ≤ 1 gap(s,a) ∧ H gapmin
and thus never contribute more than in the existing bound in (4). Therefore, our regret bound is never worse. In fact, it is significantly tighter when there are states that are only reachable by taking severely suboptimal actions, i.e., when the average value-function gaps are much larger than gap(s, a) or
gapmin. By our definition of return gaps, we only pay the inverse of these larger gaps instead of gapmin. Thus, our bound also addresses O.2 and achieves the desired log(K)/c regret bound in the motivating example of Figure 1 as opposed to the log(K)/ bound of prior work.
One of the limitations of optimistic algorithms is their S/gapmin dependence even when there is only one state with a gap of gapmin [30]. We note that even though our bound in Theorem 3.2 improves on prior work, our result does not aim to address this limitation. Very recent concurrent work [32] proposed an action-elimination based algorithm that avoids the S/gapmin issue of optimistic algorithm but their regret bounds still suffer the issues illustrated in Figure 1 (e.g. O.2). We therefore view our contributions as complementary. In fact, we believe our analysis techniques can be applied to their algorithm as well and result similar improvements as for the example in Figure 1.
Regret bound when transitions are deterministic. We now interpret Definition 3.1 for MDPs with deterministic transitions and derive an alternative form of our bound in this case. Let Πs,a be the set of all policies that visit (s, a) and have taken a suboptimal action up to that visit, that is,
Πs,a ≡ { π ∈ Π : sπκ(s) = s, a π κ(s) = a,∃ h ≤ κ(s), gap(s π h, a π h) > 0 } .
where (sπ1 , a π 1 , s π 2 , . . . , s π H , a π H) are the state-action pairs visited (deterministically) by π. Further, let v∗s,a = maxπ∈Πs,a v π be the best return of such policies. Definition 3.1 now evaluates to gap(s, a) = gap(s, a) ∨ 1H (v ∗ − v∗s,a) and the bound in Theorem 3.2 can be written as
R(K) / ∑
s,a : Πs,a 6=∅
H log(K) v∗ − v∗s,a . (5)
We show in Appendix F.7, that it is possible to further improve this bound when the optimal policy is unique by only summing over state-action pairs which are not visited by the optimal policy.

heading: 3.1 Regret analysis with improved clipping: from minimum gap to average gap
text: In this section, we present the main technical innovations of our tighter regret analysis. Our framework applies to optimistic algorithms that maintain a Q-function estimate, Q̄k(s, a), which overestimates the optimal Q-function Q∗(s, a) with high probability in all states s, actions a and episodes k. We first give an overview of gap-dependent analyses and then describe our approach.
Overview of gap-dependent analyses. A central quantity in regret analyses of optimistic algorithms are the surpluses Ek(s, a), defined in (2), which, roughly speaking, quantify the local amount of optimism. Worst-case regret analyses bound the regret in episode k as∑
(s,a)∈S×A wπk(s, a)Ek(s, a), the expected surpluses under the optimistic policy πk executed in that episode. Instead, gap-dependent analyses rely on a tighter version and bound the instantaneous regret by the clipped surpluses [e.g. Proposition 3.1 30]
V ∗(s1)− V πk(s1) ≤ 2e ∑ s,a wπk(s, a) clip [ Ek(s, a) ∣∣∣∣ 14H gap(s, a) ∨ gapmin2H ] . (6)
Sharper clipping with general thresholds. Our main technical contribution for achieving a regret bound in terms of return gaps gap(s, a) is the following improved surplus clipping bound:
Proposition 3.3 (Improved surplus clipping bound). Let the surpluses Ek(s, a) be generated by an optimistic algorithm. Then the instantaneous regret of πk is bounded as follows:
V ∗(s1)− V πk(s1) ≤ 4 ∑ s,a wπk(s, a) clip [ Ek(s, a) ∣∣∣∣ 14 gap(s, a) ∨ k(s, a) ] ,
where k : S ×A → R+0 is any clipping threshold function that satisfies
Eπk [ H∑ h=B k(Sh, Ah) ] ≤ 1 2 Eπk [ H∑ h=1 gap(Sh, Ah) ] .
Compared to previous surplus clipping bounds in (6), there are several notable differences. First, instead of gapmin /2H , we can now pair gap(s, a) with more general clipping thresholds k(s, a), as long as their expected sum over time steps after the first non-zero gap was encountered is at most half the expected sum of gaps. We will provide some intuition for this condition below. Note that k(s, a) ≡ gapmin2H satisfies the condition because the LHS is bounded between gapmin 2H Pπk(B ≤ H)
and gapmin Pπk(B ≤ H), and there must be at least one positive gap in the sum ∑H h=1 gap(Sh, Ah) on the RHS in event {B ≤ H}. Thus our bound recovers existing results. In addition, the first term in our clipping thresholds is 14 gap(s, a) instead of 1 4H gap(s, a). Simchowitz and Jamieson [30] are able to remove this spurious H factor only if the problem instance happens to be a bandit instance and the algorithm satisfies a condition called strong optimism where surpluses have to be non-negative. Our analysis does not require such conditions and therefore generalizes these existing results.2
Choice of clipping thresholds for return gaps. The condition in Proposition 3.3 suggests that one can set k(Sh, Ah) to be proportional to the average expected gap under policy πk:
k(s, a) = 1
2H Eπk [ H∑ h=1 gap(Sh, Ah) ∣∣∣∣ B(s, a) ] . (7)
if Pπk(B(s, a)) > 0 and k(s, a) =∞ otherwise. Lemma F.5 in Appendix F shows that this choice indeed satisfies the condition in Proposition 3.3. If we now take the minimum over all policies for πk, then we can proceed with the standard analysis and derive our main result in Theorem 3.2. However, by avoiding the minimum over policies, we can derive a stronger policy-dependent regret bound which we discuss in the appendix.

heading: 4 Instance-dependent lower bounds
text: We here shed light on what properties on an episodic MDP determine the statistical difficulty of RL by deriving information-theoretic lower bounds on the asymptotic expected regret of any (good) algorithm. To that end, we first derive a general result that expresses a lower bound as the optimal value of a certain optimization problem and then derive closed-form lower-bounds from this optimization problem that depend on certain notions of gaps for two special cases of episodic MDPs.
Specifically, in those special cases, we assume that the rewards follow a Gaussian distribution with variance 1/2. We further assume that the optimal value function is bounded in the same range as individual rewards, e.g. as 0 ≤ V ∗(s) < 1 for all s ∈ S . This assumption is common in the literature [e.g. 23, 19, 8] and can be considered harder than a normalization of V ∗(s) ∈ [0, H] [18].

heading: 4.1 General instance-dependent lower bound as an optimization problem
text: The idea behind deriving instance-dependent lower bounds for the stochastic MAB problem [24, 5, 15] and infinite horizon MDPs [16, 27] are based on first assuming that the algorithm studied is uniformly good, that is, on any instance of the problem and for any α > 0, the algorithm incurs regret at most o(Tα), and then argue that, to achieve that guarantee, the algorithm must select a certain policy or action at least some number of times as it would otherwise not be able to distinguish the current MDP from another MDP that requires a different optimal strategy.
Since comparison between different MDPs is central to lower-bound constructions, it is convenient to make the problem-instance explicit in the notation. To that end, let Θ be the problem class of possible MDPs and we use subscripts θ and λ for value functions, return, MDP parameters etc., to denote specific problem instances θ, λ ∈ Θ of those quantities. Further, for a policy π and MDP θ, Pπθ denotes the law of one episode, i.e., the distribution of (S1, A1, R1, S2, A2, R2, . . . , SH+1). To state the general regret lower-bound we need to introduce the set of confusing MDPs. This set consists of all MDPs λ in which there is at least one optimal policy π such that π 6∈ Π∗θ , i.e., π is not optimal for the original MDP and no policy in Π∗θ has been changed. Definition 4.1. For any problem instance θ ∈ Θ we define the set of confusing MDPs Λ(θ) as
Λ(θ) := {λ ∈ Θ: Π∗λ \Π∗θ 6= ∅ and KL(Pπθ ,Pπλ) = 0 ∀π ∈ Π∗θ}. 2Our layered state space assumption changes H factors in lower-order terms of our final regret compared to Simchowitz and Jamieson [30]. However, Proposition 3.3 directly applies to their setting with no penalty in H .
We are now ready to state our general regret lower-bound for episodic MDPs: Theorem 4.2 (General instance-dependent lower bound for episodic MDPs). Let ψ be a uniformly good RL algorithm for Θ, that is, for all problem instances θ ∈ Θ and exponents α > 0, the regret of ψ is bounded as E[Rθ(K)] ≤ o(Kα), and assume that v∗θ < H . Then, for any θ ∈ Θ, the regret of ψ satisfies
lim inf K→∞ E[Rθ(K)] logK ≥ C(θ),
where C(θ) is the optimal value of the following optimization problem
minimize η(π)≥0 ∑ π∈Π η(π) (v∗θ − vπθ )
s. t. ∑ π∈Π η(π)KL(Pπθ ,Pπλ) ≥ 1 for all λ ∈ Λ(θ). (8)
The optimization problem in Theorem 4.2 can be interpreted as follows. The variables η(π) are the (expected) number of times the algorithm chooses to play policy π which makes the objective the total expected regret incurred by the algorithm. The constraints encode that any uniformly good algorithm needs to be able to distinguish the true instance θ from all confusing instances λ ∈ Λ(θ), because otherwise it would incur linear regret. To do so, a uniformly good algorithm needs to play policies π that induce different behavior in λ and θ which is precisely captured by the constraints∑ π∈Π η(π)KL(Pπθ ,Pπλ) ≥ 1.
Although Theorem 4.2 has the flavor of results in the bandit and RL literature, there are a few notable differences. Compared to lower-bounds in the infinite-horizon MDP setting [16, 31, 27], we for example do not assume that the Markov chain induced by an optimal policy π∗ is irreducible. That irreducibility plays a key role in converting the semi-infinite linear program (8), which typically has uncountably many constraints, into a linear program with only O(SA) constraints. While for infinite horizon MDPs, irreducibility is somewhat necessary to facilitate exploration, this is not the case for the finite horizon setting and in general we cannot obtain a convenient reduction of the set of constraints Λ(θ) (see also Appendix E.2).

heading: 4.2 Gap-dependent lower bound when optimal policies visit all states
text: To derive closed-form gap-dependent bounds from the general optimization problem (8), we need to identify a finite subset of confusing MDPs Λ(θ) that each require the RL agent to play a distinct set of policies that do not help to distinguish the other confusing MDPs. To do so, we restrict our attention to the special case of MDPs where every state is visited with non-zero probability by some optimal policy, similar to the irreducibility assumptions in the infinite-horizon setting [31, 27]. In this case, it is sufficient to raise the expected immediate reward of a suboptimal (s, a) by gapθ(s, a) in order to create a confusing MDP, as shown in Lemma 4.3: Lemma 4.3. Let Θ be the set of all episodic MDPs with Gaussian immediate rewards and optimal value function uniformly bounded by 1 and let θ ∈ Θ be an MDP in this class. Then for any suboptimal state-action pair (s, a) with gapθ(s, a) > 0 such that s is visited by some optimal policy with non-zero probability, there exists a confusing MDP λ ∈ Λ(θ) with
• λ and θ only differ in the immediate reward at (s, a)
• KL(Pπθ ,Pπλ) ≤ gapθ(s, a)2 for all π ∈ Π.
By relaxing the problem in (8) to only consider constraints from the confusing MDPs in Lemma 4.3 with KL(Pπθ ,Pπλ) ≤ gapθ(s, a)2, for every (s, a), we can derive the following closed-form bound: Theorem 4.4 (Gap-dependent lower bound when optimal policies visit all states). Let Θ be the set of all episodic MDPs with Gaussian immediate rewards and optimal value function uniformly bounded by 1. Let θ ∈ Θ be an instance where every state is visited by some optimal policy with non-zero probability. Then any uniformly good algorithm on Θ has expected regret on θ that satisfies
lim inf K→∞ E[Rθ(K)] logK
≥ ∑
s,a : gapθ(s,a)>0
1
gapθ(s, a) .
Theorem 4.4 can be viewed as a generalization of Proposition 2.2 in Simchowitz and Jamieson [30], which gives a lower bound of order ∑ s,a : gapθ(s,a)>0 H gapθ(s,a)
for a certain set of MDPs.3 While our lower bound is a factor of H worse, it is significantly more general and holds in any MDP where optimal policies visit all states and with appropriate normalization of the value function. Theorem 4.4 indicates that value-function gaps characterize the instance-optimal regret when optimal policies cover the entire state space.

heading: 4.3 Gap-dependent lower bound for deterministic-transition MDPs
text: We expect that optimal policies do not visit all states in most MDPs of practical interest (e.g. because certain parts of the state space can only be reached by making an egregious error). We therefore now consider the general case where ⋃ π∈Π∗θ
supp(π) ( S but restrict our attention to MDPs with deterministic transitions where we are able to give an intuitive closed-form lower bound. Note that deterministic transitions imply ∀π, s, a : wπ(s, a) ∈ {0, 1}. Here, a confusing MDP can be created by simply raising the reward of any (s, a) by
v∗θ − max π : wπθ (s,a)>0 vπθ , (9)
the regret of the best policy that visits (s, a), as long as it is positive and (s, a) is not visited by any optimal policy. (9) is positive when no optimal policy visits (s, a) in which case suboptimal actions have to be taken to reach (s, a) and gapθ(s, a) > 0. Let π ∗ (s,a) be any maximizer in (9), which has to act optimally after visiting (s, a). From the regret decomposition in (3) and the fact
that π∗(s,a) visits (s, a) with probability 1, it follows that v ∗ θ − v π∗(s,a) θ ≥ gapθ(s, a). We further have v∗θ − v π∗(s,a) θ ≤ Hgapθ(s, a). Equipped with the subset of confusing MDPs λ that each raise the reward of a single (s, a) as rλ(s, a) = rθ(s, a) + v∗θ − v π∗(s,a) θ , we can derive the following gap-dependent lower bound:
Theorem 4.5. Let Θ be the set of all episodic MDPs with Gaussian immediate rewards and optimal value function uniformly bounded by 1. Let θ ∈ Θ be an instance with deterministic transitions. Then any uniformly good algorithm on Θ has expected regret on θ that satisfies
lim inf K→∞ E[Rθ(K)] logK
≥ ∑
s,a∈Zθ : gapθ(s,a)>0
1
H · (v∗θ − v π∗ (s,a) θ ) ≥ ∑ s,a∈Zθ : gapθ(s,a)>0
1
H2 · gapθ(s, a) ,
where Zθ = {(s, a) ∈ S × A : ∀π∗ ∈ Π∗θ wπ ∗
θ (s, a) = 0} is the set of state-action pairs that no optimal policy in θ visits.
We now compare the above lower bound to the upper bound guaranteed by STRONGEULER in (5). The comparison is only with respect to number of episodes and gaps4∑
s,a∈Zθ : gapθ(s,a)>0
log(K)
H2gapθ(s, a) ≤ Eθ[R(K)] ≤ ∑ s,a : gapθ(s,a)>0 log(K) gapθ(s, a) .
The difference between the two bounds, besides the extra H2 factor, is the fact that (s, a) pairs that are visited by any optimal policy (s, a 6= Zθ) do not appear in the lower-bound while the upper-bound pays for such pairs if they can also be visited after playing a suboptimal action. This could result in cases where the number of terms in the lower bound is O(1) but the number of terms in the upper bound is Ω(SA) leading to a large discrepancy. In Theorem E.11 in the appendix we show that there exists an MDP instance on which it is information-theoretically possible to achieve O(log(K)/ ) regret, however, any optimistic algorithm with confidence parameter δ will incur expected regret of at least Ω(S log(1/δ)/ ). Theorem E.11 has two implications for optimistic algorithms in MDPs with deterministic transitions. Specifically, optimistic algorithms
• cannot be asymptotically optimal if confidence parameter δ is tuned to the time horizon K; • cannot have an anytime bound that matches the information-theoretic lower bound.
3We translated their results to our setting where V ∗ ≤ 1 which reduces the bound by a factor of H . 4We carry out the comparison in expectation, since our lower bounds do not apply with high probability.

heading: 5 Conclusion
text: In this work, we prove that optimistic algorithms such as STRONGEULER, can suffer substantially less regret compared to what prior work had shown. We do this by introducing a new notion of gap, while greatly simplifying and generalizing existing analysis techniques. We further investigated the information-theoretic limits of learning episodic layered MDPs. We provide two new closed-form lower bounds in the special case where the MDP has either deterministic transitions or the optimal policy is supported on all states. These lower bounds suggest that our notion of gap better captures the difficulty of an episodic MDP for RL.

Review summaries:
This paper is on instance-dependent regret bounds for RL in finite episodic MDPs. The authors observe that existing bounds fail to capture some fundamental properties of the problem. Specifically, bounds based on value function gaps $gap(s,a)=V^{\star}(s)-Q^{\star}(s,a)$ ignore the fact that only state-action pairs that are relevant from telling optimal policies apart from suboptimal ones should contribute to the regret. So, the authors introduce a new concept of gap, the return gap, denoted $\overline{gap}(s,a)$, that is the average gap encountered up to reaching $(s,a)$ through some suboptimal action. Regret upper bounds are established for the StrongEuler algorithm by Simchowitz and Jamieson (2019). The main result replaces the inverse dependence on value function gaps with (larger) return gaps, and eliminates the dependence on the minimum gap. When transitions are deterministic, the result can be improved by ruling out state-action pairs that can only be reached by optimal policies. These results are complemented by an example MDP that shows why existing bounds can predict a much larger regret. The authors also provide asymptotic lower bounds for consistent algorithms. First they provide a general bound expressed in terms of an abstract optimization problem. Then they consider two special cases. For the case when every state is visited by some optimal policy, they lower bound the regret in terms of value function gaps, generalizing a result by Simchowitz and Jamieson (albeit for a worse dependence on the horizon). For MDPs with deterministic transitions, the lower bound is in terms of the return gaps, and only state-actions pairs that are not visited by any optimal policy count. The corresponding upper bound pays for these pairs if they can also be visited after playing a suboptimal action. This shows the intrinsic limitations of optimistic algorithms.

This work studies instance-dependent regret bound in episodic tabular MDP. The main observation is that the gaps in state-action pairs that can only be reached by optimal/suboptimal policy should have little contribution in the regret. Based on this observation, the authors defined a new notion "return gap", which is never smaller than the original gap notion. Then the authors proved that STRONGEULER enjoys a regret upper bound that only depends on return gap. In addition, instance-dependent regret lower bound based on return gap is provided.

The paper studies regret minimization in episodic tabular MDPs. First, the authors derive a novel instance-dependent regret upper bound for the StrongEuler algorithm. The proposed bound scales with a novel notion of sub-optimality gap, called return gap, which is defined as the maximum between the standard value-function gap at some s,a and the expected average of such gaps along the path to reach such s,a. This notion of gap allows to better characterize the complexity of this setting wrt existing works, eg, by formalizing the intuition that a good algorithm should not pay regret for learning optimal actions in states that are not reachable by optimal policies. These results are complemented with an information-theoretic lower bound that holds for a large class of MDPs. The lower bound is written in the form of an implicit optimization problem, and a closed-form expression in terms of sub-optimality gaps is provided for the specific cases of deterministic MDPs and MDPs where each state is reachable by an optimal policy.