Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning
Authors: Christoph Dann
Teodor Vanislavov Marinov
Mehryar Mohri
Julian Zimmert
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: reinforcement learning
MDP
rl
instance-dependent regret bounds
theory
regret
gap-dependent

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.


Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning
Chris Dann
Teodor V. Marinov" Google Research t. Evmarinnvv@oogleecoom
Google Research chr i was.nnngoggle..ccomm
Mehryar Mohri
Julian Zimmert Google Research z zimmert wwmmmerrt@goglee..... com
Courant Institute and Google Research mohri com
Abstract
We provide improved gap-dependent regret bounds for reinforcement learning in finite episodic Markov decision processes. Compared to prior work, our bounds depend alternative definitions of gaps. These definitions are based on the insight that, order to achieve favorable regret, an algorithm does not need learn how to behave optimally in states that not reached by optimal policy. We prove tighter upper regret bounds for optimistic algorithms and accompany them with new information-theowe show that optimistic algorithms can not achieve the cooomationntthoreeie lower bounds even in deterministic MDPs unless there is unique optimal policy.
lower bounds for large class of MDPs. Our results
Introduction
Reinforcement Learning (RL) is 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 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 respectively).
While the performance of RL algorithms in tabular Markov decision processes has been the subject of many studies the past [e.g. 11, 22, 28, 4, 20, 34, 6]. the vast majority of existing analyses focuses on worst-case problen--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 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 gap-
dependent regret-bounds of the form O (Es.a)eSx.
H Hogg(K) where the sum is over state-actions
gap(s.a]
pairs (s, a) and where the gap notion is defined as the difference of the optimal value function V* of the Bellman optimal policy x² and the Q-function of nt at a sub-optimal action: gap(s, a)
Author Johns Hopkins University during part of this work.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Value-function gap (prior)
Return gap (ours)
a1
1222
General Regret bounds
Σ
l)
Σ
log K
gap(s.a)
gap(s, a)
n
T[
5,a
log(K)
A,a
log( K)
?
Σ
6,8: AE gap(s.a)
H Hgap(s,
5,8
gap(s1 a2) =
gapl $1, (81,12) =
a4
43
Example on the left
gap($2 04) =
gap $2, (4)
cte
11 2s
o SH log(K)
SH log(
== C+C
Figure 1: Comparison of our contributions in MDPs with deterministic transitions. Bounds only include the main terms and all sums over (s, a) are understood to only include terms where the respective gap is nonzero. gap is our alternative return gap definition introduced later (Definition 3.1).
V*(s)- a). We will refer this gap definition as value-function gap in the following. We note that similar notion of gap has been used in the infinite horizon setting to achieve instance 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 multi- armed bandit setting, we argue that they have major limitation. The bound 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 have 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- calue-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 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 RI. agent does not need to learn how to best steer after running 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 red light has 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 e >> >> O. There are two decision points, 81 and 82, with two actions each, and all other states have single action. There are three policies which govern the regret bounds: ' (red path) which takes action which takes action a2 at $1 and 0g $2 (blue path); and T2 which takes action d2 at $1 and aj at 82 (green path). Since x² follows the red path, it never reaches 82 and achieves optimal return e- while Ti and m2 are both suboptimal with return and respectively. Existing salue-function gaps evaluate to gap(s1, 02) = and gap($2, 04) = which yields a regret bound of order H log( K (1/c/c+ 1/c). The idea behind these bounds is to capture the necessary number of episodes to distinguish the value of the optimal policy n² from the value of any other sub-optimal policy on all states. However, since n will never reach 82 it is not necessary to distinguish from any other policy at 82. A good algorithm only needs to determine that dg is sub-optimal in 81, which eliminates both πı and m as optimal policies after only log(K)/c² episodes. This suggests a regret of order O (logg()) /c). The bounds presented in this paper achieve this rate up 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 gap(s, a). Our new bounds replace gap(82, 04) = c by gap(s2, a4) R gap($1, a2) + gap(s2. 04) = 2((c). Notice that and can be selected arbitrarily in this examplé. In particular, if we take 0.5 and 1/VK our bounds remain logarithmic O(log(K) while prior regret bounds scale vK.
in state m
This work is motivated by the insight just discussed. First, we show that improved regret bounds indeed possible by proving tighter regret bound for STRONGEULER, an existing algorithm

---

based on the optimism on-the-fatee faace-of-umceraalie (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-theores 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 new lower bound when the transitions of the MDP are deterministic that depends only the difference in return of the optimal policy and suboptimal policies, which is closely related to our notion of return gap.
2 Problem setting and notation
We consider reinforcement learning in episodic tabular MDPs with a fixed horizon. An MDP can be described as 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) E A the next state probability distribution, given that action was taken in the current state 8. R is the reward distribution defined over S x A and r(s, a)- = TE] (ss a)] [0, 1]. Episodes admit a fixed length or horizon H.
We consider layered MDPs: each state s E S belongs to layer x(s) E [H] and the only non-zero transitions are between states 8, s' in consecutive layers, with x(5") x(s) + 1. This common assumption [see e.g. 23] corresponds to MDPs with time-dependent transitions, as in [20, 7J, but allows us omit explicit time-index in value-functions and policies. For ease of presentation, we assume there is a unique start state $1 with k(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]. the agent selects a deterministic policy Ty. S > A out of a set of all policies IT and TT is then executed for all H time steps in episode k. For each policy æ, we denote by w (s,a) P(S.(.)
s, AR(s) = Ab, (T,))) vh [H] and w² (s) Σ. w" (s,, a) probability of reaching state- action pair (s. a) and state respectively when executing æ. For convenience, supp(=) = {s
S: wn (s) > 0} the set of states visited by æ with non-zero probability. The Q- and value function
of a policy π are
(= = E,
Σ
r(Sn, As) Sa(c) 88 An(s) a a
and (=(s)= (s,
(sm
and the regret incurred by the agent is the sum of its regret over K episodes
K
R(K)-
Σ
V (
(I)
where n | (s1( the expected total sum of rewards or return of x and V is the optimal value function (s) = max V*(s), (s). Finally, the set of optimal policies is denoted as II = { E II 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 IT* that also achieve maximum return because they only take suboptimal actions outside of their support. The variance of the Q function at state-action pair (s, a) of the optimal policy is V* a) V[R(s, a)] + V VPr-P(-leaa) (V* (s')), where V[X] denotes the variance of the r.v. X. The maximum variance over all state-action pairs V" (a V** a). Finally, our proofs will make use of the following clipping operator clip[a]b] x(a b)a that sets a to zero if it is smaller than b, where X is the indicator function.
3 Novel upper bounds for optimistic algorithms
In this section, we present tighter regret upper-bounds for optimistic algorithms through novel analysis technique. Our technique can be generally applied model-based optimistic algorithms such as STRONGEULER [30], UCBVI [3], ORLC [9] or EULER [34]. In the following, we will first
3

---

give 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) 2 Q* a), Y(s, a) S x A. During episode k E [K]] the optimistic with highest optimistic value function Vs. By definition, it holds that (s((s) 2 (s).. The optimistic value and Q-functions are constructed through finite- 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 s inequality [14] and empirical Bernstein's 's inequality for martingales [26].
algorithm selects the policy
The STRONGEULER algorithm not only satisfies optimism, i.e., V2 2 V*, but also stronger version called strong optimism. To define strong optimism we need the notion of surplus which roughly measures the optimism at fixed state-action pair. Formally the surplus at (s, a) during episode is defined as
(2) We say that an algorithm is strongly optimistic if (x a) 2 0, a() E x A. E [K]. Surpluses are also central to our new regret bounds and we will carefully discuss their use in Appendix F.
Ex(s, - (a(s,a)=Q(ss,4 a) - r(s, - (P()s, a), ViA)
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
H (og((K
H (og(K)
Σ
Σ
gap(s,a) +
8,0: gap(s.a)=0 gapmin
9 gap(s,a)>0
where state-action pairs with zero gap appear, with gapmin = mill..a gap(s,))00 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 H log(K) Hog((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:
0.1 State-action pairs that can only be visited by taking optimal actions: We should not pay the 1/ gapmin factor for such (s, as there are no other suboptimal policies distinguish from n.' in such states.
0.2 State-action pairs that can only be visited by taking at least one suboptimal action: We should not pay the 1/ gap(s2, 03) factor for state-action pair (s2, a3) and the 1/ gapmin factor for (s2, a4) because no optimal policy visits $2. Such state-action pairs should only be accounted for with the price to learn that 02 is not optimal in state $1. After all, learning to distinguish between Ti and T2 unnecessary for optimal return.
Both opportunities suggest that the price gap(s.a) or gapain. that each state-action pair (s, q) con- tributes to the regret bound can be reduced by taking into account the regret incurred by the time (s, a) is reached. Opportunity 0.1 postulates that if no regret can be incurred up (and including) the time step (s, a) is reached, then this statc-action pair should not appear in the regret bound. Similarly, if this regret 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 policy ग is simply the expected sum of value-function gaps visited (Lemma F.1 in the appendix),
H An)
E
Σ gapp(S,,
we can measure the regret incurred up to reaching (St, Ad) by the sum of value function gaps
Et gap(Sn, An) up to this point t. We are interested in the regret incurred up to visiting 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 k(8) time steps. We arrive at
K(s) Σ
gap An) Sk(s) 8, An(s) = = B.,Bsigy m(())
where = min(h E [H+ I]: gap Ab) As) > 0} is the first time a non-zero gap is visited. This quantity measures the regret incurred up visiting (s,a) a) through suboptimal actions. If this quantity large for all policies тr then a learner will stop visiting this state-action pair after few observations because it can rule out all actions that lead (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 in s) and incurs 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-uction pair (s, a) E x A define B(s, a) {B
n(s), Sk(s) s, An(s) a). where B is the first time non-zero gap is encountered. B(s, denotes the event that state-action pair (8, a) is visited and that suboptimal action was played at any time up to visiting (s, a). We define the return gap as
N(a) gap Sh. An) B(s,a)
gap(s, a) gap((s a)
min
Ex
Σ
BEll:
H
P. (((.0))
if there is a policy π E with (B(s,,
and gap(s, a) = 0 otherwise.
The additional I/H factor in the second term a required normalization suggesting that is the average gap rather than their sum that matters. We emphasize that Definition 3.1 is independent of the choice RL algorithm and in particular does not depend 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 as
('( a)
R(K)
RA
log K.
gap(s, gap(s,0)>0
(x.0)
In the above, we have restricted the bound only those terms that have inverse polynomial depen- dence 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
Σ
(v)
log K +
Σ
HV"
log K.
(4)
gap(s,
gapmin
(x.0)ESxA: gap(s,a)>0
(s.j)SSA: gap(s,a)=0
We here focus only terms that admit dependency on K and an inverse- pvverse-polynomial dependency on gaps as all other terms are comparable. Most notable is the absence of the second term of (4) in bound in Theorem 3.2. Thus, while state-action pairs with gap(s, a) 0 do not contribute regret bound, they appear with a /gaapmin factor in existing bounds. Therefore, our bound addresses 0.1 because it does not pay for state-action pairs that only be visited through optimal actions. and
Further, state-action pairs that do contribute to our bound satisfy gap(s.a) < gap(s.a) A gap thus never contribute more than in the existing bound in (4). Therefore, our regret bound is never worse. In fact, it significantly tighter when there are states that are only reachable by taking severely suboptimal actions, i.c., when the average Salue-function gaps are much larger than gap(s, a) or
5

---

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)) ) regret bound in the motivating example of Figure as opposed to the log( K'/e bound of prior work.
One of the limitations of optimistic algorithms is their 8/gePmi. dependence even when there is only one state with a gap of gap [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 8/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 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 II,,a be the set of all policies that visit (s, a) and have taken suboptimal action up to that visit, that is,
11 { Elll: (x(s) s, (l)(.)) a, k(s), gap(s) ax) 0).
where (sī, aj. 82 ,...,, T4. azj) are the state-action pairs visited (deterministically) by л. Further, let v ell rn be the best return of such policies. Definition 3.1 now evaluates to gap(s. gap(s, a) V H (v" vraa) and the bound Theorem 3.2 can be written as
H (og(K)
R(K)
Σ
8,0: 11
We show in Appendix F.7, that it is possible to further improve this bound when the optimal policy is unigue by only summing over state-action pairs which are not visited by the optimal policy.
3.1 Regret analysis with improved clipping: from minimum gap average gap
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&(s, a), which overestimates the optimal Q-function Q' (s, a) with high probability in all states actions and episodes k. We first give an overview of gap-dependent analyses and then describe our approach.
Overview gap-dependent analyses. A central quantity in regret analyses optimistic algorithms are the surpluses (s, a). defined in (2), which, roughly speaking, quantify the local amount of optimism. Worst-case regret analyses bound the regret in episode & as E(e.)) Wr, Ex,s, a), the expected surpluses under the optimistic policy тą executed in that episode. Instead, gap- dependent analyses rely tighter version and bound the instantancous regret by the clipped surpluses (e.g. Proposition 3.1 30]
(*(ss) v (s1) < 2e Σ n (s, a) clip
Ex(s,a)
gap(s, V gapmin
(6)
4H
2H
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 F& (s, a) be generated by optimistic algorithm. Then the instantaneous regret of Th is bounded as follows:
V*((s) V (s1) < 4 E = (s, clip Ea((, gap((s,) Vells,)))
where : S + RR is any clipping threshold function that satisfies
H1
ca (Sh, An)
E
Σ
< Ex
Σ gap(Sh, And
2
l=BB

---

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 (s, a). as long as their expected sum over time steps after the first non-7ero gap was encountered is at most half the expected sum of gaps. We will provide some intuition for this condition below. Note that (x, a) BaPaiin satisfies the condition because the LHS is bounded between gapmin P
ST (B S H) and gap uin Pxx (B - H). and there must be at least one positive gap in the sum Σm= gap(S,, An) on the RHS in event {B S. H);
2H
2H
}. Thus our bound recovers existing results. In addition, the first term 1 gap(s, a). Simchowitz and Jamieson [30] are able remove this spurious H factor only if the problem instance happens be bandit instance and the algorithm satisfies a condition called strong optimism where surpluses have to be non- -onnnggaevv. Our analysis does not require such conditions and therefore generalizes these existing results."
in our clipping thresholds is 1 3 gap(s, a) instead of 377
Choice of clipping thresholds for return gaps. The condition in Proposition 3.3 suggests that one can set ex (Sp, Ar, to be proportional to the average expected gap under policy gg:
1 2H
cx(s,a) a)
Σ gap(Sn. As) B(s,a)
if Pr, (B(s, a)) > 0 and (s,aa) do 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 Tk. 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 poliey-dependent regret bound which we discuss in the appendix.
4 Instance-dependent lower bounds
We here shed light on what properties on an episodic MDP determine the statistical difficulty of RL by deriving anformatiion-hhooreii lower bounds 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-fort 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 S (*(s) < 1 for all 8 E S. This assumption is common in the literature [e.g. 23, 19, 8) and can be considered harder than normalization of V*(s) E [0, H] [18].
4.1 General instance-dependent lower bound as an optimization problem
The idea behind deriving instance-dependent lower bounds for the stochastic MAB problem [24, 15] and infinite horizon MDPs [16, 27] based on first assuming that the algorithm studied is uniformly good, that is, on any instance of the problem and for any a >> O, the algorithm incurs regret at most o(T"), and then argue that, to achieve that guarantee, the algorithm must select 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 instance explicit in the notation. To that end, let θ be the problem class of possible MDPs and we use subscripts 0 and À for value functions, return, MDP parameters etc., to denote specific problem instances 0, À E O of those quantities. Further, for a policy π and MDP 0, IP7 denotes the law of one episode, i.e., the distribution of (S1, AI, R1, S2, A2, R2,... SH+1), 1). To state the general regret lower- bound we need to introduce the set of confusing MDPs. This set consists of all MDPs X in which there is at least one optimal policy π such that & IIg. i.c., is not optimal for the original MDP and no policy in II; has been changed.
to make the problem-instance
Definition 4.1. For any problem instance 0 E θ we define the set of confusing MDPs A(O) as
A(0 = (> e θ: IT, \ I + Ø and K KL( PT) = 0 VT E IT
*Our 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 penalty in H.
7

---

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 v be a uniformly good RL algorithm for θ that is, for all problem instances 0 E ④ and exponents
0, the regret of s is bounded as EiRg (K) S o(K)), and assume that 2g < H. Then. for any 8 E O the regret of
satisfies
E (K))
lim +00
2 C(O),
log K
where C(#) is the optimal value of the following optimization problem
minimize m(*]20
n(x (vg v
(8)
E KLPE
for all A(0)-
The optimization problem in Theorem 4.2 can be interpreted as follows. The variables (TT) 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 À E A(),, because otherwise it would incur linear regret. To do so, uniformly good algorithm needs to play policies π that induce different behavior in and which is precisely captured by the constraints Even ( ( (PT PT 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 anfinite-horiza 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 key role in converting the semi-infinite linear program (8), which typically has uncountably many constraints, into linear program with only O(S)) 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 convenient reduction of the set of constraints A(0) (see also Appendix E.2).
4.2 Gap-dependent lower bound when optimal policies visit all states
To derive closed-form gap-dependent bounds from the general optimization problem (8), we need to identify finite subset of confusing MDPs (()) that each require the RL agent to play distinet set of policies that do not help 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 horizon setting [31, 27). In this case, it is sufficient to raise the expected immediate reward of suboptimal (s, a) by gapa (8, a) in order to create 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 and let E @ be an MDP in this class. Then for any suboptimal state-action pair (s, a) with gapa a) such that is visited by some optimal policy with non-zero probability, there exists a confusing MDP X E A(0) with
X and 0 only differ in the immediate reward at (s,a)
KL PP) I gsp for all II.
By relaxing the problem (8) to only consider constraints from the confusing MDPs in Lemma 4.3 with K L(P,, PX) gap, (s, a)², 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 0 E θ be an instance where every state is visited by some optimal policy with non-zero probability. Then any uniformly good algorithm Q has expected regret on O that satisfies
E[Ri((K
lim inf K-000
Σ
log K
8,a: (s.a)=0 (s
8

---

Theorem 4.4 can be viewed as generalization of Proposition 2.2 in Simchowitz and Jamieson [30], which gives lower bound of order >..: sapy(s.a)>0 gapa(s.a] for certain of MDPs. While our lower bound is a factor of 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 cover the entire state space.
gaps characterize the rnstance-optimal regret when optimal policies
4.3 Gap-dependent lower bound for deterministii-transitton MDPs
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 Uzen; supp(T) & 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 Vπr, 8, a w= a) E {0, 1]. Here, a confusing MDP can be created by simply raising the reward of any (s,a) a) by
2
max 20
the regret of the best policy that visits (s, a), long it is positive and (s,a) a) is not visited by
any optimal policy. (9) is positive when no optimal policy visits (s,a) a) in which case suboptimal actions have to be taken to reach (s, a) and gapo a) O. Let ((sa) be any maximizer in (9),
which has to act optimally after visiting (s, a). From the regret decomposition in (3) and the fact that ((sa) visits (s, a) with probability 1, it follows that vg v0
((see)
2 gapo a). We further S Hgappls, a). Equipped with the subset of confusing MDPs À that each raise
Finnat have vg - Fi the reward of a single (s,a) as (x a) = ra a) + 1i 1 ( 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 I. Let E θ be an instance with deterministic transitions. Then any uniformly good algorithm & has expected regret 0 that satisfies
lim inf
E (()a(KK log K
Σ
1
Σ
10 x ((o)))
H² (
8.0E Zo (e.))00 H (vg
a EApa(s.a)>0
where Zq = {(s, a) E ES* x A: VT* E I1 wy" (s, = 03 is the set of state-action pairs that no
optimal policy in 0 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 gaps*
log( K')
log( (3) gap (s, a))
Σ
Eg [E())
Σ 8,0: (aPols.a)>0
Hsgapa(ss a)
8,0EZa: (x.))0
The difference between the two bounds, besides the extra 112 factor, the fact that (s, pairs that are visited by any optimal policy (s, a * Zg) do not appear in the lower-bound while the upper-bound pays for such pairs 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 12 (S AA) leading to large discrepancy. In Theorem E. in the appendix we show that there exists an MDP instance on which it is regret, however, any optimistic algorithm with confidence parameter 8 will incur expected regret of at least S2 (1 /5)/c). Theorem E. has two implications for optimistic algorithms in MDPs with deterministic transitions. Specifically, optimistic algorithms
possible to achieve O(log( K)
cannot be asymptotically optimal confidence parameter is tuned to the time horizon K; cannot have an anytime bound that matches the information-theone
lower bound.
e We translated their results to our setting where V* S which reduces the bound by a factor of H. Wee carry out the comparison in expectation, since our lower bounds do not apply with high probability.

---

Conclusion
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 informatiion-hhorretie 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.
References
[1] Peter Auer and Ronald Ortner. Logarithmic online regret bounds for undiscounted reinforcement learning. In Advances in Neural Information Processing Systems, pages 49-56, 2007.
[2] Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. In Advances in Neural Information Processing Systems, 2009.
[3] Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen. On the sample complexity of reinforcement learning with a generative model. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 1707-1714, Omnipress, 2012.
[4] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Leurning, pages 263-272, 2017.
[5] Richard Combes, Stefan Magureanu, and Alexandre Proutiere. Minimal exploration in structured stochastic bandits. In Advances in Neural Information Processing Systems, pages 2017.
[6] Christoph Dann.
Strategic Exploration in Reinforcement Learning New Algorithmss and Learning Guarantees. PhD thesis, Camegie Mellon University, 2019.
[7] Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying PAC and regret: Uniform pac bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems, pages 5713-5723, 2017.
[8] Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. On oracle-efficient PAC reinforcement learning with rich observations. arXiv preprini 1803. 2018.
[9] Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountable reinforcement learning. International Conference on Machine Learning, 2019.
[10] Simon S Du, Jason D Lee, Gaurav Mahajan, and Ruosong Wang. Agnostic Q-learning with function approximation deterministic systems: Tight bounds on approximation error and sample complexity. arXiv preprint arXiv:2002.07125, 2020.
[11] Claude-Nicolas Ficchter. Efficient reinforcement learning. In Proceedings of the seventh annual conference on Computational learning theory, pages 88-97. ACM, 1994.
[12] Sarah Filippi, Olivier Cappé, and Aurélien Garivier. Optimism in reinforcement learning and Kullback-Leible divergence. In 20/0 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 115-122, IEEE, 2010.
[13] Dylan J Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. Instance-dependent complexity of contextual handits and reinforcement learning: A disagreement- perspective. arXiv preprint arXiv:2010.03/04 2020.
[14] David Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100-118, 1975.
10

---

[15] Aurélien Garivier, Pierre Ménard, and Gilles Stoltz. Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 44(2):377-399, 2019.
[16] Todd L Graves and Tze Leung Lai. Asymptotically efficient adaptive choice of control laws incontrolled markov chains. SIAM journal on control and optimization, 35(3):115-743, 1997.
[17] Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. arXiv preprint arXiv:2011.11566, 2020.
[18] Nan Jiang and Alekh Agarwal. Open problem: The dependence of sample complexity lower bounds on planning horizon. In Conference On Learning Theory, pages 3395-3398, 2018.
[19] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contextual decision processes with low bellman rank are pac-learnable. Conference Machine Learning, pages 1704-1713, 2017.
International
[20] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is Q-learning provably efficient? arXiv preprint arXiv: 1807.0375, 2018.
[21] Tiancheng Jin and Haipeng Luo. Simultaneously learning stochastic and adversarial episodic MDPs with known transition. arXiv preprint urXiv:2006.05606 2020.
[22] Sham Kakade. On the sample complexity of reinforcement learning. PhD thesis, University College London, 2003.
[23] Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations. In Advances in Neural Information Processing Systems, pages 1840-184,, 2016.
[24] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Ad- vances in applied mathematics, 6(1):4 22, 1985.
[25] Thodoris Lykouris, Max Simchowitz, Aleksandrs Slivkins, and Wen Sun. Corruption robust exploration in episodic reinforcement learning. arXiv preprint arXiv: / 1.08689, 2019.
[26] Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penalization. arXiv preprint arXiv:0907.37440 2009.
[27] Jungseul Ok, Alexandre Proutiere, and Damianos Tranos. Exploration in structured reinforce- ment learning. In Advances in Neural Information Processing Systems, pages 8874-8882, 2018.
[28] Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems, pages 3003-3011, 2013.
[29] Martin Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Witey-Interscience, 1994.
[30] Max Simehowitz and Kevin Jamieson. Non-asymptotic gap-dependent regret bounds for tabular MDPs. arXiv preprint arxiv: /005.00990000039 2019.
[31] Ambuj Tewari and Peter L Bartlett. Optimistic linear programming gives logarithmic regret for irreducible MDPs. In Advances in Neural Information Processing Systems, pages 1505-1512, 2008.
[32] Haike Xu, Tengyu Ma, and Simon S Du. Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap. arXiv preprint arXiv:2102.04699 04692, 2021.
[33] Kunhe Yang, Lin F Yang, and Simon S Du. Q-learning with logarithmic regret. arXiv preprint arXiv:2006.091 18, 2020.
[34] A. Zanette and E. Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. hutp:///arzivor//aa////99...00 10, 2019.
11

---

[35] Alexander Zimin and Gergely Neu. Online learning in episodic markovian decision processes by relative entropy policy search. In Advances neural information processing systems, pages I 1583-1591, 2013.
12


Reviews:
[{"review_id": "PIWIR1O6gby", "reviewer": "Reviewer_56Wf", "summary": "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.\nRegret 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.\nThe 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem of online learning in finite MDPs is well understood at this point. However, this work has some elements of originality. The concept of return gaps allows to better capture the complexity of the learning problem, as made clear by the discussion of the theoretical results and the concrete MDP examples.\nHowever, the work also heavily relies on existing results, especially by Simchowitz and Jamieson. Lemmas from this previous work are often used in the proofs without much discussion, which makes the proofs hard to follow at times. I think the paper would be better if it was more self-contained. Notice, for instance, that the StrongEuler algorithm is never described in detail.\nThe more \"adaptive\" results also require more complicated formulations and more care in analyzing the subtle differences between the results, but I think the improved understanding of the problem is worth the effort. The authors make a good job in making the notation clear, providing intuitions, and carefully discussing the implications of their results. \n\nTo sum up, I think this is a valid and interesting paper that would greatly benefit from a more self-contained structure. I think it has some original ideas but the way they are presented gives the impression they are just a series of \"supplementary\" results to a well established theory. \n\nMore detailed comments/questions follow:\n1. Can you provide some intuition on why Theorem 3.2 removes the dependence on H w.r.t. [29]? The \"scale\" of the gap w.r.t. the horizon seems to be the same. So was the H factor in [29] an artifact of the proof?\n2. Line 197: where do you prove this equivalent expression for $\\overline{gap}(s,a)$?\n3. Line 220: \"the LHS evaluates to...\" why the extra H in the denominator?\n4. Lemma 4.3: how can an optimal policy visit a state-action pair with positive gap? I would understand if it was just the state, but if you also include the action then $a=\\pi^{\\star}(s)$ and the gap should be zero. Am I missing something?\n5. In the proof of Theorem C.1 there are several quantities that are not defined: $I_k$ (sequence of trajectories?), $Y_k$ (a single trajectory?) $\\psi(I_k)$ (strategy learned from the first $k$ trajectories?)\n\nMinor comments:\n- line 276: \"irreducability\"\n- line 328: $\\mathcal{X}$ is not defined\n- (10) $\\Lambda$ should be $\\Lambda'$\n- line 570: any measurable $Z$: with respect to what?\n- line 576: \"a uniformly good [policy]\"\n- line 687: I would include this discussion in the main paper\n- line 769: missing a $-1$ superscript?\n- I would at least mention tree-structured MDPs in the main paper", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a purely theoretical work and it does not propose new algorithms, just improve the understanding of existing problems and algorithms.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "MhA0TB0R0F", "reviewer": "Reviewer_Z9JX", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work proposes a new gap notion and provides corresponding instance-dependent regret upper bound and lower bound. The paper is well-written and structured. It also includes a detailed related work and proof. \n\nFrom my point of view, instance-dependent regret bound focuses on the structure of the MDP and provides tighter regret bound than instance-independent bound on specific MDPs. In this work, the authors make the observation that not every gap in the MDP is of equal importance and some of them can be avoided in the regret bound because the algorithm can quickly find out that it is in a suboptimal trajectory. This observation is interesting and exploits the inside structure of the MDP better than current analyses. \n\nIn addition, the authors provides both regret upper bound and lower bound based on their new gap notion, which makes the work quite complete. However, the upper bound and lower bound are not matched by a factor of H. It would be great if this gap can be closed.\n\nThough the work is lack of algorithmic contribution, I believe this is a minor issue. The main contribution of this work is the novel observation and if existing algorithm can be proved to enjoy a tighter regret based on the new gap notion, it varifies the observation.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper does not clearly show how the proof for the new upper bound differs from the existing proof. Is the proof a direct generalization or there is some novel techniques? Also is there technical novelty in the proof of lower bound?\n\nAnother question is that does the lower order terms in the regret upper bound only includes return gap? In addition, it would be great if the authors can conduct some numerical experiments to varify their result (small gaps in suboptimal trajectories will not affect the regret much).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "7TWYFn75mwD", "reviewer": "Reviewer_inqh", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Understanding the complexity of regret minimization in MDPs (especially from an instance-dependent) perspective is a relevant open problem and this paper provides novel significant results in this direction. I agree with the authors that properly analyzing and combining both value-function gaps and gaps between policy returns is a key step towards better characterizing the complexity of this setting. In this sense, I found quite interesting the definition of return gap considered in this paper and the role it plays in the analysis and in the final regret bound. Moreover, the instance dependent lower bound, while not very informative in the general case (where it is written as an optimization problem whose solution is not clear), provides further intuitions in the specific cases considered in Section 4 and in the appendix.\n\nI found the paper very well-written. Despite the many terms that needed to be introduced, I think the authors did a good job in stating all results without over-complicating the notation and in providing intuition behind every formal claim. Maybe one downside is that some of the key results in the main paper (especially Theorem 3.2) are a little bit sketchy and one needs to take a look at the appendix for the details, which in turn is more than 30 pages of very technical content.\n\nOverall I think this is a good paper with new insights on regret minimization in episodic RL and I tend to vote for acceptance. My detailed comments follow.\n\n\n1. In the evaluation of the regret bound from [29] on the MDP of Figure 1 (Line 126), the S dependence in the third term arises by counting all state-action pairs with zero gap. This is indeed by evaluating the bound as it is written in [29]. Still, to be fair, I believe that states with a unique possible action should not be counted, and in that MDP there are only two states with more than one action.\n\n2. Opportunity O.1 states that we should not pay an extra 1/gap_min dependence for playing optimal actions at states that are reachable *only* by playing optimal policies. However, the lower bound seems to suggest that the same should hold for states that are reachable by *some* optimal policy. In this sense, the upper bound seems to be sub-optimal in that dependence. This is partially discussed in Section 4 for the case of deterministic MDPs. Do the authors think that it would be impossible for an optimistic algorithm like StrongEuler to have a regret without any extra 1/gap_min dependences at all states reachable by an optimal policy? Is this already implied by the construction of the lower bound for optimistic algorithms of Theorem C.11? Or a more refined definition of return gap and/or of the analysis might yield such result?\n\n3. The work of [31] is labeled as concurrent and discussed in only a few lines. Since [31] has been around since a few months before the NeurIPS deadline, I would have liked to see more discussion and comparison between the two works. In particular, as in this paper, [31] builds on top of the clipping-based analysis of [29] using the classic notion of value-function gaps. I would be curious to see what is the result of analyzing the algorithm of [31] with the return gaps defined here. If the answer to the previous question is negative, so that optimistic algorithms cannot avoid paying 1/gap_min dependences in certain states that are visited by optimal policies, could the algorithm in [31] achieve so? Or do the authors think that new algorithmic techniques are needed to get closer to matching the information-theoretic lower bound?\n\n4. More generally, a question that is left open by this work (and which should be explicitly mentioned somewhere) is how and whether it is possible to build an algorithm that (nearly) matches the information-theoretic lower bound of Theorem 4.2. This is quite unclear since the lower bound is in a very implicit form except for specific MDP classes\n\n5. One limitation of Theorem 4.4 is that the set of confusing MDPs that are used to compute the lower bound differ from \\theta only in the immediate rewards. This basically means that, even by relaxing the assumption of \"value functions bounded by 1\" to \"value functions bounded by H\", the lower bound is likely not to show any dependence on H. On the other hand, I was expecting to see a H^2 dependence at the numerator (the counterpart of the squared span of the bias function in Ok. et al [26]). Related question: where is the assumption that value functions are bounded by 1 needed in the proof?\n\n6. It is mentioned that the second term in Definition 3.1 is an average of the gaps along some path. So does the normalizing term always need to be H or could it be \\kappa(s)?\n\n7. Theorem 4.2 assumes that v_\\theta^\\star \\leq 1 for all MDPs \\theta. I could not find where that assumption is needed for proving the general lower bound\n\n8. Unrelated comment: there are a few papers that appeared concurrently to this submission that might be of interest to the authors:\n   - Tirinzoni et al. \"A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs\", which derives similar instance-dependent lower bounds for the episodic setting\n   - Tranos & Proutiere. \"Regret Analysis in Deterministic Reinforcement Learning\", which studies instance-dependent lower bounds for deterministic MDPs in the infinite-horizon (average-reward) setting\n   - Marjani et al. \"Navigating to the Best Policy in Markov Decision Processes\", which studies best-policy identification in the infinite-horizon (discounted) setting\n\nTypos and other minor comments:\n\n- Line 22: I am not sure I understand what \"more optimistic\" means\n- Line 31: irreducible?\n- Caption of Figure 1: \"a our\"\n- Line 99: it would be clearer to write V^\\pi(s) = V^*(s) \\forall s\n- Line 105: I guess \\chi denotes the indicator. That should be stated explicitly \n- Line 113: P was introduced without \\mathbb\n- Line 118: StrongEuler is a only a slight variant of the Euler algorithm from [33], so I would also mention that paper there instead of only attributing the algorithm to [29]\n- LHS of the equation below line 328: there is an X instead of Z", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are discussed. I do not see any societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proposes a new gap notion and provides corresponding instance-dependent regret upper bound and lower bound. The new gap definition gives a better characterization of the complexity of an RL problem. The paper is well-written and structured. The reviewers believe the paper is good for publication in NeurIPS.
Decision: Accept (Spotlight)