On Gap-dependent Bounds for Offline Reinforcement Learning
Authors: Xinqi Wang
Qiwen Cui
Simon Shaolei Du
Venue: NeurIPS 2022 Accept (2022)
Keywords: offline reinforcement learning
gap-dependent

Abstract: This paper presents a systematic study on gap-dependent sample complexity in offline reinforcement learning. Prior works showed when the density ratio between an optimal policy and the behavior policy is upper bounded (single policy coverage), then the agent can achieve an $O\left(\frac{1}{\epsilon^2}\right)$ rate, which is also minimax optimal. We show under the same single policy coverage assumption, the rate can be improved to $O\left(\frac{1}{\epsilon}\right)$ when there is a gap in the optimal $Q$-function. Furthermore, we show under a stronger uniform single policy coverage assumption, the sample complexity can be further improved to $O(1)$. Lastly, we also present nearly-matching lower bounds to complement our gap-dependent upper bounds.

On Gap-dependent Bounds for Offline Reinforcement Learning
Xinqi Wang
Institute for Interdisciplinary Information Sciences Tsinghua University
wangzqkaxdd@@mail.coo
Qiwen Cui
Simon S. Du
Paul G. Allen School of Computer Science
Paul G. Allen School Computer Science Engineering
Engineering.
University of Washington qwcui@cs. wwwwington. edu edu
University of Washington
ssduêcs. washington. edu
Abstract
This paper presents a systematic study on gap-dependent sample complexity offline reinforcement learning. Prior work showed when the density ratio between an optimal policy and the behavior policy is upper bounded (the optimal policy coverage assumption), then the agent achieve an O (+) rate, which also minimax optimal. We show under the optimal policy coverage assumption, the rate can improved O (?) when there is positive sub-optimality gap the optimal Q-function. Furthermore, we show when the visitation probabilities of the behavior policy are uniformly lower bounded for states where an optimal policy's visitation probabilities are positive (the uniform optimal policy coverage assumption), the sample complexity of identifying an optimal policy independent of 1 Lastly, we present nearly-m marrl-matchhig lower bounds to complement our gap-dependent upper bounds.
Introduction
Reinforcement Learning (RL) aims to learn policy that maximizes the long-term reward in unknown environments [Sutton and Barto 2018 The success of reinforcement learning often relies being able to deploy the algorithms that directly interact with the environment, However, such direct inter- actions with real environments can be expensive or even impossible many real-world applications. e.g., health and medicine (Murphy et al.. 2001 Gottesman et al. 2019]. education [Mandel et al. al. (0199 and recommendation systems [Chen al. 2019 Instead, we have access to a dataset generated from some past suboptimal policies. Offline reinforcement learning (offline RL) aims to find near-optimal policy using the offline dataset, and
2014,, conversational AI [Ghandeharioun
has achieved promising empirical successes [Lange et al. 2012 Levine et al. 2020].
Recently, line of works showed that under the single policy coverage assumption (Assumption $.2 one can obtain a near-optimal policy with polynomial number of samples (Rashidinejad et al. 2021
Xie et al. 2021b Yin and Wang 202T
2022]. In partieular, for the tabular Xie et al. 2021a Li al.
setting, recent works have obtained minimax optimal sample complexity bounds è SC" where
H is the planning horizon, S the number of states, C* is the constant for the single policy coverage
assumption, and is the target accuracy Xie et al. 2021b Li et al. 2022 The O (1/e) is for the
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

worst case and in many benign settings, one may use much fewer samples to learn a (near-)optings Joptimal policy.
How the benign problem structures help reduce the sample complexity has been extensively studied in the online bandits and reinforcement learning (Simchowitz and Jamieson 2019 Jonsson et al. 2020 Wagenmaker et al. 2021b Xu et al., 202T]. In particular, when there is suboptimality gap between the optimal policy and the rest, then one can obtain log T-ype regret in contrast to /T-type regret bounds in the worst case where 7 is the number of interactions. However, our knowledge, how the gap structure helps reduce sample complexity in offline RL has not been thoroughly investigated. This paper presents a systematic study on gap-dependent bounds for offline RL the canonical tabular setting, with seearl-matching upper and lower bounds in different regimes.
1.1 Main Contributions
We present novel analyses for the standard VI-LCB algorithm (Algorithm) Our main results summarized in Table [WI
1. We develop novel technique, deficit thresholding, to obtain sap-dependent bounds in offline RL. Different from the clip trick widely used in online RL (Simchowitz and Jamieson
2019. Xu et al. 202T] obtain gap-dependent bounds, our deficit thresholding technique is adaptive to the problem-instance As will be shown in Section 662, this technique helps reduce the dependency on H by adapting to the variance of the estimate.
2. Using the deficit thresholding technique, obtain the first gap-dependent bound under the optimal policy coverage assumption. Specifically, we obtain an Ô "''CC" bound
cgiPPmin
where gapmin is the minimum suboptimality gap between the optimal Q-value of the best action and that of the second-to-the-bes, action Notably, compared with the worst-case gap-indepdent, the rate improves from 1/e² to 1/c.
3. We also present the first gap-dependent lower bound for offline RL, S2
to show the O (1/e) is unimprovable even with the gap condition, and our upper bound tight up to an H factor. The main insight from our lower bound is that if there exists state whose visitation probability of the behavior policy and the optimal policy O (c). then we cannot learn much of the state using the offline dataset and will inevitably incur an O (c) error.
egap enin.
4. We further study what condition permits even faster rate than O (1/c). Leveraging our lower bound mentioned above, we propose new condition, uniform optimal policy coverage, which posits that the visitation probabilities of the behavior policy are uniformly lower bounded by P for states where optimal policy's visitation probabilities are positive.
Under this assumption, we obtain an Ô Pgapain
bound. Importantly, this bound is independent of 1/e (not even log(1/e)) a.k.a., one can identify an exact optimal policy. We lower bound to show our upper also complement this upper bound with an S2 Pgapp... bound is tight up to an 2 factor.
H
Lastly, we note that all of our bounds are obtained with the same algorithm, i.e., the algorithm automatically exploits the benign problem structure without any prior knowledge.
2
Related Work
We focus on existing theoretical results on gap-dependent bounds and offline RL in the tabular setting.
Theoretical Results on Offline Tabular RL. Theoretical analysis of offline RL can be traced back to Szepesvári and Munos 2005), under the uniform coverage assumption where every state-action
'The gap-dependent bounds in the online setting also depend on the suboptimality gaps of the actions other than the second-to-the-oe beet action. This dependency is not needed offline RL because even if the dataset does not have any information about the sub-optimal actions, the agent can still learn a near-optimal policy (as long the dataset covers an optimal action). On the other hand, this dependency is needed in the online setting because the agent needs to explore the all actions.
2

---

Condition
Upper bound
Lower bound
C*
S' log
Ω
H
SC 2²
e²
H² S**
H² SC"
C*, ".gapmin
B
22
cgapmin min
egapmin
P, Eagammi min
Ô
H log Pgap min
Ω
H Pgap min
Table Sample Complexity Bounds for different conditions about the sub-optimality and coverage. Cells in gray are the contributions of this work. The results in the first line without suboptimality
gap assumptions were obtained in Xie et al. 2021b) Li et al. [2022]. C stands for the relative
optimal policy coverage coefficient, i.e., max
[3 where (s) is the visitation probability of h,e [x](
the optimal policy for state 8 at level and d is the visitation probability of the behavior policy μa for state at level h. P stands for the uniform optimal policy coverage coefficient, i.e.,
min d) gap is the minimum non-zero suboptimality gap among all time-state-action (.)ld(()))0
tuples, i.e.,
min
(i(s) Q% ())
has,aaa optimal
pairs are visted by the behavior policy with a positive probability. Sharp sample complexity bounds have been obtained under this assumption [Xie and Jiang 2021 Xie al. 2019 Yin al. 2020
2021b Ren et al. 202T] Recently, a line works showed that under a much weaker assumption,
single policy coverage,
design sample efficient algorithms with both model-basse and model-
free methods based on the pessimism principle, [Rashidinejad et al. [022]] Yin and Wang [202] Xie
and Jiang 202T Jin et al. [001 Uehara and Sun] 202 Uehara al. [202]] Zanette al.) 2021].
Recently, Yin and Wang 2021 obtained a problem-dependent sample complexity in terms of the
variance.
Instance-dependent Sample Complexity in Online Learning and Generative Models. In online RL, a line of work studied the upper and lower bounds of gap-dependent sample complexity in both the regret and PAC settings (Simchowitz and Jamieson 2019 Xu al. 2021 Dann al. 202T Jonsson ee al. 2020 Wagenmaker et al.] 202 a ['irinzoni et al. 2021]. Besides gap-dependent bounds, there are other problem-dependent bounds such as first-order and variance-deeendent bounds Zanette and Brunskill (2019). For generative models, Zanette el al. 2019 derived an upper bound depending on both variance and gap information.
Gap-dependent bounds in Offline Learning. The most related work is by Hu et al. [2021 who studied the convergence rate of Q-learning in the discounted MDPs under the uni- form coverage assumption. They proved that one can obtain e-optimal policy with O (S3 A log(1/e)/(1 eters) for linear MDP. In comparison, we show that under the weaker uniform optimal policy coverage assumption, we can identify an exact optimal policy with (H3) /ggapiin) sample complexity, which has no dependency on 1/e.
Pagap samples for tabular MDP and Ö(1/e) (ignoring other param-
3 Preliminaries
Notations. We [n) = {1, 21, .1). For two vectors a, of the same length k. we use aob to denote
the Hadamard product (a1b1, -agbb.)) We use the standard definitions of O(-), ((), 2(-) to hide absolute constants, and tilded notations Ō(-). (.), (i-)) to hide absolute constants as well as poly-logarithmic factors except for log (Vr, = p TV V a V - (p VV2 refers to the variance of V with respect to the weight p. < b means < Cb for some positive absolute constant C, and similarly Z means a 2 Cb. T(E) the indicator function of the event ç, which equals when is true and 0 otherwise. ((X) is the probability simplex over X.
3

---

3.1 Markov Decision Processes
We consider tabular finite-horizon time-inhomogeneous MDPs described by the tuple M (S.A, H. P. Po. r). Here S is the state space with cardinality S, A is the action space with car- with ph.,.a E A(S) is the transition kernel at timestep h, state s and action a. po E (SS) is the initial state distribution of s1, and r {ri, .2..... TH} with Th S x A + [0, 1] is the reward function I For each episode, the player will generate trajectory (55, ah, Th) where 81 ~ po. 5h+1 Ph. and Tл Th an), by controlling the actions (an)a-r- The target of the player is to maximize the total reward Σ Th-
dinality A. ( (
Policies. A policy т ()..))))) refers to a set of distributions over A. With slight abuse of the notations, when a policy is deterministic, we use (s) to denote the action taken at timestep h and state We define E,, M[[]] A (g where ø {(sh, a/ TT) heem) is trajectory sampled using policy æ in the MDP . and the expectation over the randomness of both the policy and the transitions. M will be omitted when there is no confusion.
Value Functions, Q-Functions and Policy Distributions. For a given policy т and an MDP M. we define the state value function and the state-action value function to be
11
H
(8) 2 Ex
(wr(sw,a =h==h
Σ
| 8h =
QT a)
ET
Σ
The (ssss,a
| 8h 8, 8,a = a
We define the optimal Q-function as Q7 a) - sup, (8, a), and similarly (x sup, V for all (h, s, a) [H] x S A. It well known that there exists a deterministic optimal policy . that can achieve the above maximum for all s E S, E and h E [H] simultancously.
We denote the value of policy by Vă = Fxx [Σ#= rh(Sh, an)]
and the value of the optimal policy
by V/ = Vg A policy æ is c-optimal if
Suboptimal( & Vo V c.
We use d.)()) to denote the probability of reaching state under policy n.
d[( A [T(A (sh s}], (s) A [T on) (s, di (s) s)-
Sub-optimality Gap. For MDP instance M, we define the gap at (h, s, E [H]] S A be gap, (s, (s) - Q (s, a). which is always non-negative because of the definition of T*
Our results will depend on the smallest positive gap: gapmin A min (h.s,a)BAAD, (s.)>>
gap, (8, a), which
quantifies the difficulty of learning the optimal policy in the MDP instance
3.2 Offline Reinforcement Learning
Offline Learning. For offline reinforcement learning, we want to solve an MDP M (S,A, H, P,r) r) with unknown transitions by utilizing a given dataset collected by some unknown behavior policy μ. Note that the algorithm is not allowed to perform any kind of additional sampling. The dataset is D = {{(8), an.i: (h.i:.r.))) hej which contains N trajectories collected by the behavior policy μ independently. (e. 5). offline reinforcement learning algorithm is defined to output an c-optimal policy π with probability least 1 - 5.
Assumptions. We introduce two dataset assumptions that will be used this paper. Assumption 3.1 (Uniform optimal policy coverage). We define the uniform optimal policy coverage coefficient to be
A min min (8 a),
r' b,sd (s,a)>0
where म. is an optimal policy. We assume that P>0 0.
We assume a known deterministic reward function as main difficulty lies in learning transition probability. All the conclusions in this paper can he proved for MDPs with unknown I -subGuussiinn reward.
We assume that at least one gap is positive. Otherwise all the actions optimal and no learning is needed.

---

Algorithm 1: VI-LCB
input Dataset D,, reward function
Set Q #+1 (s, a) 0
Set V #+ 1 (s, a) =
for 4- H do
Compute the empirical transition kernel Pr.
(s') (r.o.")) with 0/0
(3,0))
for s E S, a E A do
Var Prin (a
()) VbV
+ Cb N,](aa where (2( as(s,))
2, (8,a) max max(0,ra(ss0)) + PIT Pho Va+i bs(s,))
for E S do
10
V, (s) + max
Q (8) aEA
In arg max Q (8,a) aEA
output:polic
Algorithm 2: Subsampled VI-LCB
input Datasst D, reward function r
Split D into halves containing same number of sample trajectories, Dmain and Daux
Du = O}
for 8) E [H] S do
(s) f- m0 (s) / Naaux log HS 5
Randomly subsample min (Nrri (s), No), Nmmain (s)} samples of transition from (h, s) from Dumai to add to Dp
+ VI-LCB(Pa,r)
output:polic
Assumption 3.1 states that the behavior policy covers all the state-action pairs that some *" will choose with positive probability. This is a natural assumption if we want recover the optimal policy.
closely related assumption is the uniform coverage assumption, i.e., all (h, a) tuples covered by the dataset (Yin and Wang 2020 Ren et al.] 2021 Yin et al.] 2021a| Hu et al.] [021]. Our assumption is significantly weaker it only assumes covering the optimal policy. We will prove that under this assumption, we can identify the optimal policy with finite samples.
Assumption 3.2 (Optimal policy coverage). We define the relative optimal policy coverage coefficient to be
di (s.a)
C max (h,8,0)
S d (s,a)
with convention that 0/0 0, where x² is an optimal policy. We assume that C* 600
Similar coverage assumption has been widely adopted in al 2022, Shi et 2022 Yan et al.) 2022 Jmm et al. 2021] Rashidinejad et al. [2221] Researchers have designed algorithms based on pessimism principle to efficiently solve offline RL problems under this assumption. Assumption
3.2 is usually weaker than Assumption 3.1 For example, if there exists one unique optimal policy and 1 = n., we have C = 1 while P can still be arbitrarily small. addition, we always have
C* p
5

---

3.3 Subsampled VI-LCB
We briefly introduce the algorithm (Algorithmp 2 that will be used in the analysis. Value Iteration with Lower Confidence Bound (VI-LCB) was first introduced by RRashidinejad et al. [202]] and improved by Li al. 2022]. The main idea to maintain pessimistic estimate on the value functions so that the suboptimality of the output policy only depends on the uncertainty of the optimal policy. By utilizing the subsampling technique and Bernstein-style bonus, subsampled VI-LCB achieves the minimax sample complexity Ō (ASs"))
In the algorithm, (s, a) refers to the number of sample transitions starting from state s, taking action a at time step of some given dataset, and (s) EasA (s, a). Superscripts stand for the dataset. See Li ct al. 2022 for more detailed description of the algorithm.
4 Finding an Exact Optimal Policy with Assumption 3.1
In this section, show that can identify the exact best policy with finite samples by utilizing the gap structure under Assumption 3.T On the other hand, for the minimax sample complexity
O(HASC it will become infinite when approaches O. Note that directly setting < gapmin does not imply that the output policy is optimal. Instead, we only have
VØ 2 Vo
while x can still be suboptimal at states visited with low probability.
Theorem 4.1. For an MDP M and behavior policy with uniform optimal coverage coefficient P. the number of sample trajectories satisfies
H log
Ö
Pgap 2
then with probability at least 1 - 8, Algorithm returns an optimal policy.
Sketch of Proof. First, if for all sh, [ S A satisfying di (8, a) > 0, we have
2, (8, a) Q (s, a) - gapmin'
(1)
then we have π is an optimal policy. This because as Q a pessimistic estimate of Q", we have Q₂ (8,a)) (7, a) gapmin 2 Q 2 2, (s,
for any action a' that is sub-optimal. As result, π chooses the optimal action for all (h, sh,s,,, a) [H] x S covered by the optimal policy, which implies æ is an optimal policy.
Second, we show that is satisfied with N 2 Prapp.... This is because if the number of
samples at (h, s, a) exceeds 0(H+/ /gap'mn)) we can guarantee that the estimation error at that step is smaller than gapmin/ /H by Hoeffding's inequality. Then the accumulated estimation error at 2, (s, a) can be bounded by (H h)gapmin// /H < gapmin- which implies ① To further improve the dependence on H, we will use Bernstein's 's inequality and the proof is deferred to Appendix
B,4
5 Gap-dependent Upper Bounds with Assumption 3.2
In the previous section, we show that the optimal policy can be identified if Assumption satisfied. However, the uniform optimal coverage coefficient P can be very small, which makes the bound N δ Pgapii..
useless. this section, we present two results on learning an e-optimal
policy with assumption (Assumption
3.2) and provide the proof sketch in the next section. The
full proof can be found in Appendix B
Theorem 5.1. For an MDP M and behavior policy p. with relative optimal policy coverage coefficient C*, the number of sample trajectories satisfies
H** log
N ZZŌ
cgapmin
Algorithm returns an e-suboptimal policy with probability at least 1 - 5.

---

Theorem 5.1 shows that to learn an e-optimal policy, we only need (11/ega samples, which significantly improves the minimax sample complexity ((1/c²) when gapmin-
Now we show that we can further improve the bound both Assumption and Assumption 3.2 are satisfied.
Theorem 5.2. For an MDP M and behavior policy with uniform optimal policy coverage coefficient P and relative optimal policy coverage coefficient C if the number of sample trajectories satisfies
"H*SC* log
log
2
egapmin
P
Algorithm 2 returns an c-suboptimal policy with probability at least 1 1 5.
Theorem 5.2 improves an H factor compared with Theorem 5.1 with the cost an extra H/P term. As the additional term is constant with respect and gapmin: the bound is improved when egapmin min is small. We believe this H/ can removed and we leave it to future works.
Main Proof Techniques
In this section, we will provide a proof sketch for Theorem 5.1 and Theorem 5.2
6.1 Pessimistic Algorithms
First, we define pessimistic algorithms and imaginary MDPs M (S, determined by the pessimistic algorithms. Our analysis will generally hold for all pessimistic algorithms defined by Definition A.2 and we will show that VI-LCB (Algorithm 2 is pessimistic algorithm. We use VI-LCB only to derive the final sample complexity guarantees.
Definition 6.1 (Pessimistic algorithms). An offline learning algorithm with output policy a is pessimistic with probability least 6, the following arguments hold,
1. It maintains a pessimistic estimate Q of the true Q-
2. Q is the optimal Q function of an imaginary MDP M (S,A,H,P, where In [s,s,,) a) S rn(ss, a) for all (h, 8, a) E [H] x S x
3. I is the greedy policy with respect to Q.
Most of the existing offline RI. algorithms are pessimistic algorithms and we will also prove it for VI-LCB LI et al. 2022 in Appendix B
Definition 6.2 (Deficit). For any pessimistic algorithm and the corresponding imaginary MDP (S, A, H, P, P.p. r), we define the deficit to be
(s rn(s,a) as) v(h,s,a) [H] x S A.
From the definition of pessimistic algorithms, we have (s, a) stands for how pessimistic the estimates are. Note that the deficit is related to the algorithm itself and usually can bound it by utilizing concentration inequalities.
> 0 immediately. Intuitively, deficit
6.2 Deficit Thresholding for Analysising LCB-style Algorithms
By defining V to be the value function of policy æ in A and recalling that x is the optimal policy V=
in M, we have Vi <
V < Vē and thus
H
H
Vi
V
Ex (rn and IA (Sh, an)] =
Σ E. ax)
'Here we loosen the definition of MDP by allowing the reward function to have negative value. z maybe negative, but will be shown in appendix, = and Q are still non-negative, thus does not affect our analysis.

---

can upper bound the suboptimality of т. Surprisingly, we will show that even if we threshold the deficit, similar upper bound still holds. Define the thresholded deficits and the corresponding reward functions
EN (s, a) - m, a) (x, Fn a) & (n(s, (x, - a). (1h,s,a) E [H] x X A, for any non-negative threshold function (n a). Then we can define a thresholded MDP M = AS,, P. and we use V to denote the value function in M. Now we present the key lemma showing that if the thresholding function satisfies certain conditions related to gapmin then the suboptimality of can still be bounded by the thresholded deficit.
Lemma 6.1. Suppose for a thresholding function en (s, for all (h, E [H] S, we have
(i) + gaP Vi(s).
(2)
2
Then we can bound the suboptimality of by the thresholded deficit:
H
suboptimal(T) = V V 0 V 2 Vi) = Σ Ex (sh, h=1
See Appendix A.2 for the rigorous proof, where this lemma decomposed and restated as Theorem A.1 and Definition A.S One way to satisfy 2 is to set (,,8, a) = gap for all (h, 8,) E H S x A. As result, the reward at each timestep h is increased by at most gapmin after thresholding, so the overall increase of the value function is bounded by gaPmin/ This kind of e fs a) leads to the following corollary.
2H 2H
2H
Corollary 6.1. For any pessimistic algorithm, we have
Vi VØ 2
Σ E. [0, (sh.
gapmin 2H
In addition, note that En (Sh, an) depends variance of the transition Ph. as if the transition variance small, the estimate will be accurate and the deficit will be small. This inspires us to threshold adaptively based on the variance. We design the following adaptive threshold function:
Var P. (V4+1)
(n(s, a) x
H gapmin-
turns out that 52( ) sample complexity is enough to guarantee this kind of threshold function satisfies 2 (See Lemma B. in Appendix B.S.I)
Corollary 6.2. For any pessimistic algorithm and number of samples N 2 O(H) we have
Var Phon
Wh+1)
Vū Vē 22
Ex
max (sh, an)
gapmin
gaP
H²
4H
To proceed from Lemma 6.1 we will utilize the following inequality
E (s.0) a)
(s, a) = max(0, (s, - (s, <
en (x a)
Then with different choices of (8. a) used Corollary 6.1 and Corollary 6.2
and the bonus function
used in the VI-LCB algorithm, we can derive Theorem 5. and Theorem 5.2 Here we briefly explain
the ((Lee) dependence. We have (s, a) S Obb (s, a)), where (s, a) the pessimistic bonus
scaling as O(1/ /n) (ignoring other dependences). Then by Lemma 6.1 and the above inequality, we
achieve (1/cc bound immediately. A more detailed proof is provided in Appendix B
Our technique is similar to the clip techique (Simchowitz and Jamieson 2019 in online MDP as both of them threshold the estimates (deficit here and surplus in their work) by some O(gapmin) terms.
Simchowitz and Jamieson [201 further clip another (s,4) term, and we can actually achieve that as well, but it does not improve the sample complexity in the offline setting as we do not need to explore the actions. In addition, we develop a new thresholding function based on the empirical variance, which can improve the H factor by utilizing the Bernstein's 's inequality and the total variance technique. We believe this new technique can also be applied to the online setting and improve the sample complexity there.
H
8

---

7 Gap-dependent Lower Bounds
In this section, we provide two lower bounds for uniform optimal coverage assumption (Assumption
3.1) and optimal policy coverage assumption (Assumption 3.2 respectively. Our lower bounds show that Theorem 4.1 and Theorem 5.1 are optimal up H factors and logarithm terms. We begin with general lower bound. Here the offline learning algorithm, ALG, is defined as the algorithm that takes dataset D input and output a policy ît. Note that ALG can stochastic.
Theorem 7.1. There exists some absolute constant C, such that for any A 2 2, 2, T, 2 X < 3: A 2 2 and offline RL algorithm ALG, if the number of sample trajectories satisfies
HSA1 Xr
N
there exists a MDP instance . and behavior policy is with gaPmin = T, P> ESA1' that the output policy of ALG has expected suboptimality
C S Å such
XHT
ALG Vo -Vol
12
By choosing 1/3,
3cP5 and gapmin Theorem
7.1 indicates the following corollary.
Corollary 7.1. For any given instance coefficients (H, g.ggammin PS ReS Hgapmin and any offline reinforcement learning algorithm ALG, there exists instance (M, p) such that if the number of trajectory samples satisfies
largel suboptimality
H
N S C- Pgapa min
the output policy ft would have expected suboptimality more than c, iee.
1
ELG V
Vo
Hgapmin Ze
36
By choosing
12c
- gapmin- Theorem 7.1 indicates the following corollary.
HgaPmin
Corollary 7.2. For any given instance coefficients (H, S.gaPmins C² 2). target suboptimality
E E HgaPmin and any offline learning algorithm ALG, there exists an instance (M, (1) such that if the number of trajectory samples satisfies
NSC H2SC
egapmin
the output policy â would have expected suboptimality more than c, i.e.,
EMGALGa V 2
The proof of the corollaries can be found Appendix
construct a family of MDPs that
involve solving H.S independent bandit problems, where each bandit requires 2 HA visits so that the estimation
be bounded by Similar constructions have been made in Yin al. (221aa. Dann et al. 2017). Xie et al. [2021b) Our key observation is that the initial state distribution can linearly determine the uniform optimal policy coverage coefficient P and the final suboptimality. Also, our proof can lead to another version of lower bound, where a s(E)) suboptimality occurs with a
constant probability. See Appendix C.2.3 for details.
8 Necessity of Pollyyy Coverage
As one may notice that Assumption 3. and Assumption 3 are not exactly the most widely adopted
versions [Li al. 2022 Xie al., 202 Rashidinejad et al. 202T Here the assumptions require a coverage of all the optimal policies instead of only one optimal policy. This assumption can not be weaken as long as we are using naive ICB-style algorithm, and a counterexample can be found in Appendix D

---

Intuitively, the problem lies in that we can not distinguish between different optimal policies. Gap information helps us distinguish optimal actions from sub-optimal ones when the estimation error relatively small, but a naive I.CB algorithm still has the probability of choosing an optimal action ((s,0g (2) in the counterexample) without fully exploring gap-dependent analysis, this problem can be addressed by some sophisticated exploration techniques [uu et al. 2021]. It is unclear if we can weaken the assumption to single policy coverage and we leave this to future work.
subsequent state-action pairs. In online
9
Conclusion
We presented a systematic study on gap-dependent upper and lower bounds for offline reinforcement learning. Depending different assumptions, the rates can be improved from Ō(1/e²) in the worst Ô (1/e) or even independent of 1/e. Also, we presented a counterexample show that overall optimal policy coverage is necessary in gap-dependent analysis.
One open question is that there still exists gap between the upper and lower bounds in terms of H. We note that this gap also exists in the online setting (Simehowitz and Jamieson, 2019 Xu et al. 2021 Another direction is generalize results to the function approximation setting [He et al. 2021
Acknowledgements
SSD acknowledges funding from NSF Award's CCF-2212261, IIS-2143493, DMS-2134106, CCF. 2019844 and IIS-2110170.
References
Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, and Ed H Chi. Top-k off- correction for reinforce recommender system. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pages 456-464, 2019.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
Christoph Dann, Teodor Vanislavov Marinov, Mehryar Mohri, and Julian Zimmert. Beyond value- function gaps: Improved instance-dependent regret bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
Asma Ghandeharioun, Judy Hanwen Shen, Natasha Jaques, Craig Ferguson, Noah Jones, Agata Lapedriza, and Rosalind Picard. Approximating interactive human evaluation with self-play for open-domain dialog systems. arXiv preprint arXiv: 1eXivv:9006.00 9930009338, 2019.
Omer Gottesman, Fredrik Johansson, Matthieu Komorowski, Aldo Faisal, David Sontag, Finale Doshi-Velez, and Leo Anthony Celi. Guidelines for reinforcement learning in healthcare. Nature medicine, 25(1): (61):16-18,,. 2019.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. In International Conference on Machine Learning, pages 4171- 4180. PMLR, 2021.
Yichun Hu, Nathan Kallus, and Masatoshi Uchara. Fast rates for the regret of offline reinforcement learning, 2021. URL BRLpstts:://// pattps://arxiie http://xxxvvvrr.eeee org/ atsp//ab./212000077
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rl? In International Conference on Machine Learning, pages 5084-5096. PMLR, 2021.
Anders Jonsson, Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Edouard Leurent, and Michal Valko. Planning markov decision processes with gap-dependent sample complexity. Advances in Neural Information Processing Systems, 33:1253-1266 2020.
10

---

Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In Reinforcement learning, pages 45-73. Springer, 2012.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint S0ti:20005006444 2020.
Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Settling the sample complexity of model-based offline reinforcement learning. arXiv preprint arXiv:2204.05275, 2022.
Travis Mandel, Yun-En Liu, Sergey Levine, Emma Brunskill, and Zoran Popovic. Offline policy evaluation across representations with applications to educational games. In AAMAS, pages 1077-1084, 2014.
Susan A Murphy, Mark van der Laan, James Robins, and Conduct Problems Prevention Re- search Group. Marginal mean models for dynamic regimes. Journal of the American Statistical Association, 96(456):1410-1423, 2001.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning; A tale of pessimism. Advances in Neural Information Processing Systems, 34, 2021.
Tongzheng Ren, Jialian Li, Bo Dai, Simon S Du, and Sujay Sanghavi. Nearly horizon-free offline reinforcement learning. Advances neural information processing systems, 34, 2021.
Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, and Yuejic Chi. Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity. arXiv preprint urXiv:2202.13880 2022.
Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. Advances in Neural Information Processing Systems, 32, 2019.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Csaba Szepesvári and Rémi Munos. Finite time bounds for sampling based fitted value iteration. In Proceedings of the 22nd international conference on Machine learming, pages 880-887, 2005.
Andrea Tirinzoni, Matteo Pirotta, and Alessandro Lazaric. A fully bound for finite-horizon mdps. arXiv preprint arXiv:2 13013, 2021.
regret lower
Masatoshi Uehara and Wen Sun. Pessimistic bosedl-based offline reinforcement learning under partial coverage. arXiv preprint arXiv:2107.06226 2021.
Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline in low-rank mdps. arXiv preprint urXiv:211000460 2021.
Andrew Wagenmaker, Max Simchowitz, and Kevin Jamieson. Beyond no regret: Instance-dependent pac reinforcement learning. arXiv preprint arX0::2108.02717, 2021a.
Andrew J Wagenmaker, Max Simchowitz, and Kevin Jamieson. Task-optimal exploration in linear dynamical systems. In International Conference on Machine Learning, pages 10641-10652. PMLR, 2021b.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. In International Conference on Machine Learning. pages 11404-11413, PMLL, 2021.
Tengyang Xie, Yifei Ma, and Yu- Xiang Wang. Towards optimal off- off-policy evaluation for reinforce- ment learning with marginalized importance sampling. Advances in Neural Information Processing Systems, 32, 2019.
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistee pessimism for offline reinforcement learning. Advances in neural information processing systems, 34:6683-6694, 2021a.

---

Tengyang Xie, Nan Jiang, Huan Wang. Caiming Xiong, and Yu Bai. Policy finetuning: Bridg- ing sample-efficiet offline and online reinforcement learning. Advances neural information processing systems, 34, 2021b.
Haike Xu, Tengyu Ma, and Simon Du Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap. Conference on Learning Theory, pages 4438 4472. PMLR, 2021.
Yuling Yan, Gen Li, Yuxin Chen, and Jianqing Fan. The efficacy of pessimism in asynchronous q-learning. arXiv preprint arXiv:2203.07366 2022.
Ming Yin and Yu-Xiang Wang. Asymptotically efficient off-po evaluation for tabular rein- forcement learning. In International Conference on Artificial Intelligence and Statistics, pages 3948-3958. PMLR, 2020.
Ming Yin and Yu-Xiang Wang. Towards nnstance-optimal offline reinforcement learning with pessimism. Advances neural information processing systems, 34, 2021.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal provable uniform convergence in offline policy evaluation for reinforcement learning, arXiv preprint arXiv:2007.03760, 2020.
Ming Yin. Yu Bai, and Yu-X Yu-Xiang Wang. Near-optimal provable uniform convergence in offline policy evaluation for reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 1567-1575, PMLR, 2021a.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal offline reinforcement learning via double
variance reduction. Advances neural information processing systems, 34, 2021b.
Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312. PMLR, 2019.
Andrea Zanette, Mykel J Kochenderfer, and Emma Brunskill. Almost horizon-free structure-aware best policy identification with generative model. Advances in Neural Information Processing Systems, 32, 2019.
Andrea Zanette, Martin Wainwright, and Emma Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning, Advances in neural information processing systems, 34, 2021.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] Our results contain no direct social or anthropology element.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 3.2
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type
of GPUs, internal cluster, cloud provider)? [N/A]
12

---

4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "e5_vU4JJaen", "reviewer": "Reviewer_xRSG", "summary": "This paper provides an analysis of gap-dependent sample complexity in offline reinforcement learning. The main contribution is to show that under the optimal policy coverage assumption, the sample complexity can be improved to $O(1/\\epsilon)$, compared to $O(1/\\epsilon^2)$ bounds in previous analysis. Nearly matching lower bounds are also provided by the authors. ", "questions": "This paper is well written and technically sound. I tend to vote for reject due to the following concerns and questions. Please address these in the rebuttal and correct me if I misunderstand some critical part of the work. \n\n1. I am wondering why Theorem 4.1 cannot be implied by previous results by setting $\\mathrm{gap}_{\\min}=\\epsilon$. If the output policy of an algorithm is $\\epsilon$-optimal for some $\\epsilon$ smaller than the gap, then we know that algorithm can identify the optimal policy. In fact, if I understand correctly, the proof of Theorem 4.1 indeed tries to argue this. \n\n2. I like the analysis in general. By applying the clip technique, the authors can first upper bound the regret by considering a not-so-pessimistic-MDP, then applying existing techniques to continue the analysis. This makes the proof very clear and easy to follow for readers that are familiar with the literature. My main concern is that the main idea is from existing techniques in the literature. Although the paper argues that the novelty of the analysis is to consider the variance during clipping, this contribution seems to be a marginal contribution to me. \n\n3. Theorem 5.1 shows the $\\tilde{O}(1/\\epsilon\\mathrm{gap})$ upper bound. The authors argue that this significantly improves the sample complexity of $\\epsilon$ is very small compared to the gap. I think this is a very nice contribution as it provides a sharper characterization of the sample complexity. However, I am wondering for $\\epsilon>\\mathrm{gap}$, does this also mean the proposed bound is actually worse than the existing results? Also, is $\\epsilon << \\mathrm{gap}$ really interesting? Again, if an algorithm can be $\\mathrm{gap}$-optimal, we know it can identify the optimal policy. \n\n4. I have some question related to the lower bound (Theorem 7.1). In the construction, C^* is fixed to be A. Does that mean this lower bound is only correct for some data collection policies? \n\n\n5. One reason we prefer instance (or gap) dependent analysis over minimax analysis is that it can tell us if an algorithm is adaptively optimal. That is, if the algorithm is optimal for both hard and easy problem instances. However, as a recent paper pointed out, no algorithm can be instance-dependent optimal in offline RL (Xiao el al., 2021). This makes the contribution of this paper less interesting. Also, I think the paper should give some discussion about how the gap-dependent analysis considered in the paper is different with the instance-dependent analysis used in the literature (Lattimore and Szepesvari, 2020)\n\n\nXiao, C., Wu, Y., Mei, J., Dai, B., Lattimore, T., Li, L., Szepesvari, C. and Schuurmans, D., 2021, July. On the optimality of batch policy optimization algorithms. In International Conference on Machine Learning (pp. 11362-11371). PMLR.\n\nLattimore, T. and Szepesvári, C., 2020. Bandit algorithms. Cambridge University Press.\n\n", "limitations": "Please see the previous section. ", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\nThe paper is well-written and technically sound. Studying instance-dependent analysis for offline RL is a very important topic. \n\n\nWeakness:\n\nThe proof technique is not very novel. The contributions might have limited impact. \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "ddUlDxa_Y9e", "reviewer": "Reviewer_xbq6", "summary": "In this paper, the authors considers the offline MDP problem with an episodic setting. For this type of problem, existing works provide a minimax optimal sample complexity of  $O(H^3 S C^* \\epsilon^{-2})$, given a finite single policy concentrability coefficient $C^*$. In this paper, the authors further extend the discussion on the problem based additional structure of a lower bounded Q-function gap or a lower bounded visitation probability of the behavioral policy on the support of the optimal policy. Based on these additional structures, $O(\\frac{C^*}{\\epsilon \\cdot gap_{min}})$ or $O(\\frac{1}{P \\cdot gap_{min}^2})$ sample complexity are derived. Lower bounds are established and almost matches the provided upperbounds except for a factor of $H^2$. \n\nOverall, the reviewer think this is a good submission that complete a missing part of the offline RL when the problem is simple (in terms of well lower bounded gaps). The discussion is complete and the presentation is clear. ", "questions": "The reviewer may need to make some more explanation of what the subsampled VI-LCB (Algorithm 2) is doing. In particular, it will be helpful if the authors could add some intuitive discussion on why it is needed instead of simply applying the VI-LCB. ", "limitations": "NA. This is a pure theoretical result.  ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength #1. This paper complete a missing part of the offline RL when the problem has some strictly lower bounded gaps in optimal Q function or behavioral policy. \n\nStrength #2. The discussion is complete in the sense that both lower and upper bounds are provided. \n\nStrength #3. The presentation is clear and easy to follow. \n\nWeakness: no obvious weakness found from the reviewer point of view. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "dbbMVyVLn_g", "reviewer": "Reviewer_dSJR", "summary": "This paper studies gap-dependent bounds for offline tabular RL. In particular, they show that under the optimal policy coverage assumption and the minimum positive gap, pessimistic algorithms achieve the rate of $1/N$. In the additional condition that the density of the behavior policy is uniformly lower bouned at the reachable states of an optimal policy, pessimistic algorithms precisely identify an optimal policy using finite samples. They also accompany with their upper bounds with nearly-matching lower bounds for each case. The paper also proposes the so-called deficit thresholding technique, based on the technique in an online counterpart, to analyze offline tabular RL with gap information. ", "questions": "- Lemma 6.1 is particularly interesting as it gives a stronger upper bound on the sub-optimality when pessimism and gap information is used than when the gap information is ignored. However, I seem not to be able to locate the proof of Lemma 6.1 in the appendix. Do I miss something?\n- Intuitively, what is the role of subsampling in Algorithm 2 and how does it contribute to the final bound?", "limitations": "See the weakness section. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths: \n- the problem is novel and interesting \n- the theoretical claims are sound and interesting to the offline RL community \n- the analysis is quite general and neat, with a new technique called deficit thresholding that seems interesting \n- every upper bound is backed up by nearly-matching lower bounds \n\n## Weaknesses: \n- The results and the techniques are only limited to tabular representation and require independence assumption on the episodes of the offline data. \n- It is sometimes not trivial to locate the proof of the main result in the paper", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "5BB7NRm5kPC", "reviewer": "Reviewer_P8NT", "summary": "This paper studies the gap dependent sample complexity of obtaining the optimal policy in episodic RL with offline data. The authors first define the notions of uniform optimal policy coverage coefficient and the relative optimal policy coverage. The uniform optimal policy coverage characterizes how \"explorative\" is the offline sampling policy, and relative optimal policy coverage characterizes how different are the offline sampling policy and the optimal policy. Further, the authors establish an upper bound on the sample complexity of offline RL using the optimal coverage coefficient. Next, the authors argue that optimal coverage coefficient might be too small. Hence, they provide a sample complexity based on relative optimal policy coverage coefficient. Next, the authors provide the main proof techniques in their results. Finally, the authors provide a gap dependent lower bound on the sample complexity of their algorithm.", "questions": "- In Assumption 3.1, are you implicitly assuming only deterministic optimal policies? The reason is that you are denoting \\pi^*(s), which is the action taken at state s in the deterministic policy \\pi^*.\n- In the result of Theorem 4.1, why do you hide the dependency on log(1/\\delta)? I believe it is more informative if you somehow represent that dependency here.\n- In Theorem 7.1 you introduce the notion of ALG, but you have not defined this notion.\n- The lower bound on Theorem 7.1 and Corollaries 7.1 and 7.2 are in terms of expectation. But the upper bound in Theorems 5.1 and 5.2 are in high probability. How do you relate these two? ", "limitations": "As mentioned earlier, the upper bound in the paper is stated in terms of high probability, but the lower bound is in terms of expectation. If the authors address this concern of mine, I am willing to increase my score.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main strength of the paper is a through study of offline RL in the episodic case. In particular, the authors provide both an upper bound and a lower bound, and they claim that they match up to some polynomial of length of the horizon H. \nThe main weakness is on the appearance of gap_m in the sample complexity. Although I understand this is the main motivation of the paper from the beginning, but this quantity can be arbitrary small. The authors might claim that gap_m also appears on the lower bound, and hence their bound is tight. But as I explained before, I am not yet convinced by the lower bound, since it is in terms of expectation rather than high probability. \nAnother issue is on the definition of ALG in the lower bound. This notion is not defined anywhere in the paper. This is critical, since it tells us about the kind of lower bound that the authors are claiming. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept