Nearly Horizon-Free Offline Reinforcement Learning
Authors: Tongzheng Ren
Jialian Li
Bo Dai
Simon Shaolei Du
sujay sanghavi
Venue: NeurIPS 2021 Poster (2021)
Keywords: Offline Reinforcement Learning
Statistical Reinforcement Learning
Horizon-free
Reinforcement Learning Theory

Abstract: We revisit offline reinforcement learning on episodic time-homogeneous Markov Decision Processes (MDP). For tabular MDP with $S$ states and $A$ actions, or linear MDP with anchor points and feature dimension $d$, given the collected $K$ episodes data with minimum visiting probability of (anchor) state-action pairs $d_m$, we obtain nearly horizon $H$-free sample complexity bounds for offline reinforcement learning when the total reward is upper bounded by 1. Specifically:
• For offline policy evaluation, we obtain an $\tilde{O}\left(\sqrt{\frac{1}{Kd_m}} \right)$ error bound for the plug-in estimator, which matches the lower bound up to logarithmic factors and does not have additional dependency on $\mathrm{poly}(H, S, A, d)$ in higher-order term.
• For offline policy optimization, we obtain an $\tilde{O}\left(\sqrt{\frac{1}{Kd_m}} + \frac{\min(S, d)}{Kd_m}\right)$ sub-optimality gap for the empirical optimal policy, which approaches the lower bound up to logarithmic factors and a high-order term, improving upon the best known result by [Cui and Yang 2020] that has additional $\mathrm{poly} (H, S, d)$ factors in the main term.
To the best of our knowledge, these are the first set of nearly horizon-free bounds for episodic time-homogeneous offline tabular MDP and linear MDP with anchor points. Central to our analysis is a simple yet effective recursion based method to bound a "total variance" term in the offline scenarios, which could be of individual interest.

Nearly Horizon-Free Offline Reinforcement Learning
Tongzheng Ren'
Bo Dai Tsinghua University Google Research, Brain Team University of Washington Amazon Search tongzheng@utexas..o 1f lijial an701 asduêcs washington, edu, sanghavi @mail. .utexas edu.
Jialian Li
Simon S. Du Sujay Sanghavi!,
UT Austin
11176660 63. com, boda @google com,
Abstract
We revisit offline reinforcement learning on episodic time-homogee homooeooogeesuus Markov Decision Processes (MDP). For tabular MDP with states and A actions, or linear MDP with anchor points and feature dimension d, given the collected K episodes data with minimum visiting probability of (anchor) state-action pairs dm. we obtain nearly horizon H-free sample complexity bounds for offline reinforcement learning when the total reward is upper bounded by 1. Specifically:
For offline policy evaluation, we obtain Ô
error bound for the
Kd
plug-in in estimator, which matches the lower bound to logarithmic factors and does have additional dependency on poly (H, S, A. d) higher-order term.
For offline policy optimization, we obtain an Ô (v Kdm. Kdm..
min(S,d) sub-
optimality gap for the empirical optimal policy, which approaches the lower bound up to logarithmic factors and a high-order term, improving upon the best known result by [1] that has additional poly (H, S, d) factors in the main term.
To the best of knowledge, these the first set of nearly horizon-free bounds for episodic time-homeee homogenooos offline tabular MDP and linear MDP with anchor points. Central our analysis simple yet effective recursion based method bound "total variance" term in the offline scenarios, which could be of individual interest.
Introduction
Reinforcement Learning (RI. aims learn make sequential decisions maximize the long-term reward in unknown environments, and has demonstrated success in game-playing [2, 3], robotics [4], and automatic algorithm design [5]. These successes rely on being able deploy the algorithms in way that directly interacts with the respective environment, allowing them to improve the policies trial-and-error way. However, such direct interactions with real environments can be expensive or even impossible in other real-world applications, e.g., education [6], health and medicine [7, 8]. conversational [9] and recommendation systems [10]. Instead, we are often given a collection of logged experiences generated by potentially multiple and possibly unknown policies in the past.
This lack of access real-time interactions with environment led the field of offline reinforcement learning [11]. Within this, offline policy evaluation (OPE) focuses on evaluating a policy, and offline policy optimization (OPO) focuses on improving policies; both rely only upon the given fixed past experiences without any further interactions. OPE and OPO are in general notoriously difficult, as unbiased estimators of the policy value can suffer from exponentially increasing variance in terms of horizon in the worst case [12, 13].
To overcome this "curse of horizon" in OPE, [14, 15] first introduced marginalized importance sampling (MIS) based estimators. They showed that if (1) all of the logged experiences are generated
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

from the same behavior policy, and (2) the behavior policy is known, then the exponential dependency on horizon can be improved to polynomial dependency. Subsequently, [16-18] showed that the polynomial dependency could be achieved even without assumptions (1) and (2). The basic idea for these MIS-based estimators is estimating the marginal state-action density ratio between the target policy and the empirical data, so as to adjust the distribution mismatch between them. On the algorithmic side, marginal density ratio estimation can be implemented by either plug-in estimators [15, 191, semporal-difference updates [20, 21], or solving min-max optimization [16, 17, 22, 18]. These OPE estimators can also be used as one component for OPO, resulting in the algorithms in [23-25], which also inherit the polynomial dependency horizon.
In a different but related line of work, [26, 27] recently showed that, for the online episodic time- homogeneous tabular Markov Decision Process (MDP) that allows for the interactions with environ- ments, the sample complexity only has poly log dependency on the horizon. This motivates us to consider the following question:
Can offline reinforcement learning escape from the polynomial dependency on the horizon?
In this paper, we provide an affirmative answer to this question. Specifically, considering the episodic homooenngss tabular MDP with S states, A actions and horizon H, or the linear MDP with anchor points and feature dimension d, assuming the total reward for any episode is upper bounded by almost surely, we obtain the following nearly H-free bounds:
For offline policy evaluation (OPE), we show that the plug-in in estimator has a finite-sample error (Theorem and 5), where K is the number of episodes and dm is the minimum
of Ō (V Kdm
visiting probability of (anchor) state-action pairs, that matches the lower bound up to logarithmic factors. We emphasize that the bound has no additional poly (H, S, S,A, d) dependency in the higher order term, unlike the known results of [19, 24].
For offline policy optimization (OPO), we show that the policy obtained by model- planning min{(S,]
on empirical MDP has a sub-optimality gap of Ô (V Kdm +
Kdm Kdm (Theorem 3 and 6), which
matches the lower bound up to logarithmic factors and a high-order term. This also improves upon the best known result from [1] by removing additional poly (H, d) factors in the main term.
To the best of our knowledge, these are the first set of nearly horizon-free bounds for both OPE and OPO on time-homogeneous tabular MDP and linear MDP with anchor points. To achieve such sharp bounds, we propose a novel recursion based method to bound a "total variance" term (introduced below) that is broadly emerged in the offline reinforcement learning, which could be of individual interest.
Technique Overview. With sequence of fairly standard steps in the literature, we can bound the error of the plug-in estimator via terms related to the square root of the "total variance" (also known as the Cramer-Rao type lower bound illustrated in [13]) v Emeean E., <7 (s, a) Varp(s.a) (1 (s)) where ex is the reaching probability, P is the transition and V is the value function under policy т. (For a more formal definition, see Section 3.). An improper bound of this term will introduce unnecessary dependency on the horizon, either in the main term or in the higher-order term. We instead bound this term with a recursive method, by observing that this "total variance" term can be approximately upper bounded by the square root of the "total variance of value square" Ene(H] Σsaa S% (s, a) Varp(..))
and some remaining term (see Lemma I and Lemma 3 for the detail). Applying this argument recursively, we can finally obtain a poly log H upper bound on the total variance, which eventually gets rid of the polynomial dependency on H.
The idea of higher order expansion has been investigated in [28, 27J. We notice that the recursion introduced in [28] was designed for the infinite horizon setting, and how to generalize their technique to finite horizon setting still unclear. Our recursion is conceptually more similar to the recursion in [27]. However, [27] considered the online setting, where we only need to bound the error on the visited state-action pairs. For the offline setting, we need to bound the error on every state-action pair that can be touched by the policy π. This introduces the reaching probability 5e in the "tttal v " term, which we need to deal with using the MDP structure. As a result, our recursion is significantly different from their counterpart, especially in the case of linear MDP.
2

---

Organization. Our paper is organized as follows: in Section 2, we review the related literature on offline reinforeement learning, and then briefly introduce the problem we consider in Section 3. In Section 4 and Section 5, we show our results of offiin policy evaluation and offline policy optimization on tabular MDP correspondingly, and in Section 6, we show how to generalize our results to linear MDP with anchor points. We finally conclude and discuss our results in Section 7.
2 Related Work
In this section, we briefly discuss the related literature in three categories. i.e., offline policy evaluation, offline policy optimization, and horizon-free frre online reinforcement learning. Notice that, for the setting that assumes an additional generative model, typical model-based algorithms first query equal number of data from each state-action pair, then perform offline policy evaluation/opiimiztionn based on the queried data. Thus we view the reinforcement learning with generative model special instance of offline reinforcement learning. To make the comparison fair, for method and analysis that do not assume Assumption 1, we scale the error and sample complexity, by assuming per-step reward is upper bounded by 1 7 and // under infinite-horize and finite-horizon setting correspondingly.
Table 1:
A comparison of existing offline policy evaluation results. The sample complexity in infinite horizon setting is the number of queries of transitions need while in episodic setting is the number of episodes we need. Non-Uniform Reward, the MDP we consider satisfies Assumption I; otherwise, assume the per-step reward is upper bounded by 1 1-7 and 1/H correspondingly.
Analysis
Setting
Non- Uniform Reward
Sample Complexity
[28]
Infinite Horizon Tabular
Yes
[29]
Infinite Horizon Tabular
Yes
[19]
Finite Horizon time-inhomogeneous Tabular
No
SSA
dm
[13]
Finite-Horizon time-inhomogeneous Tabular
No
d
This work
Finite Horizon time-homogeneous Tabular/I.nnes
Yes
Lower Bound
Finite Horizon time-homogeneous Tabular/Linear
Yes
Offline Policy Evaluation. For OPE in infinite horizon tabular MDP, [28] showed that plug-in (1-7) under Assumption 1, which matches the lower
estimator can achieve the error of Ô
bound in [29] up to logarithmic factors. For OPE in finite horizon time-inhomogeneous tabular MDP, [19, 24] provided an error bound of Ö Kd... +
VSA under the uniform reward assumption, Kd...
which matches the lower bound [13] up to logarithmic factors and an additional higher-order term.
We here consider the time-homogeneoos MDP, and obtain error bound of Ö( kdd.)) ), that does not have the additional VSA in higher-order term, which is different from [19, 24].
Beyond the tabular setting, [30] considered the performance of plug-in estimator with linear function approximation under the assumption of linear MDP without anchor points, and [31, 32] provided more detailed analyses on the statistical properties of different kinds of estimators under different assumptions, which are not directly comparable to our work. Recently, there are also works [c.g. 33] focusing on the interval estimation of the policy for practical application.
Offline Policy Optimization. Offline policy optimization for infinite horizon MDP date back to [35]. [28] recently showed that a perturbed version model- based planning can find c-optimal policy within δ d... (d.((1-))>>) queries of transitions in infinite horizon tabular MDP when the total reward is upper bounded by 1, that matches the lower bound up to logarithmic factors. For the finite horizon time-inhomogeneous tabular MDP setting, [24] showed that model-based planning can identify c-optimal policy with Ō
Hf episodes, that matches the lower bound for time-inhomogeneous
dmne
MDP up to logarithmic factors. When it comes to finite horizon tine-homogeneous tabular MDP and
linrar MDP with anchor points, [1] provided Ō min (.S.d) episode complexity for model-based

---

Table 2: A comparison of existing offline learning results. The sample complexity in infinite horizon setting is the number of queries of transitions we need while in episodic setting is the number of episodes we need. If Non-Unifoma Reward, the MDP consider satisfies Assumption I; otherwise, we assume the per-step reward is upper bounded by - and 1 I/H correspondingly.
Analysis
Setting
Non-Uniform Reward
Sample Complexity
[34]
Infinite Horizon Tabular
No
[28]
Infinite Horizon Tabular
Yes
[24]
Finite Horizon -mm-iinhomogeeeuu Tabular
No
[1]
Finite Horizon time-homogeneous Linear
No
mint H.S.A) G.n.
[27]
Finite Horizon time-homogeneous Tabular Online
Yes
Ö
This Work
Finite Horizon himehhomogeneuus Tabular/Linear
Yes
Ö
(iin(..)))
dmn
Lower Bound
Finite Horizon time-homageneous Tabular/Lineas
Yes
f
planning, which is min (H, S, df away from the lower bound. We provide a Ô Tineet episode complexity, that matches the lower bound up to logarithm factors and a higher order term.
+
min (S.d) dne
recent work [36] considered solving the offline policy optimization with model-free Q-learning with variance reduction. Although their algorithm match the sample complexity lower bound
Ω
when per-step reward is upper bounded by 1, model-free algorithms generally need at
least O H² episodes of data to finish the algorithm (a.k.a the sample size barrier in [28]) and is d.,. unclear how to translate their results to the setting with total reward upper bounded by
Horizon-Free Online Reinforcement Learning. There are several works obtained nearly horizon- free sample complexity bounds for online reinforcement learning. In the time- ooe-hhoogeeeous setting, whether the sample complexity needs to scale polynomially with H was an open problem raised by [37]. The problem first addressed by [26] who proposed e-nct over the optimal policies and a simulation- based algorithms to obtain a sample complexity that only scales logarithmically with H. though their dependency on S, A and is not optimal and their algorithm is not computationally efficient. The sample complexity bound was later substantially improved by [27] who obtained an
δ 0(5A
SA S²A) bound, which nearly matches the contextual bandits (tabular MDP with H 1)
lower bound Ω (SA) up an S factor [38]. Their key ideas are (1) new bonus function and (2) a recursion-baal based approach to obtain a tight bound on the sample complexity. Such kind of recursion-be basdd approach cannot be directly applied to the offline setting, and we develop novel recursion method to suit the offline scenarios.
3 Problem Setup
Notation:
Throughout this paper, we use [N] denote the set (1, .N for N Σ A(E) to denote the set of the probability measure over the event set E. Moreover, for simplicity, we use denote polylog (S, A, H, 1/8) factors (that can be changed in the context), where ò is the failure probability. We use and f2 denote the upper bound and lower bound up to logarithm factors.
3.1 Markoy Decision Process
Markov Decision Process (MDP) is one of the most standard models studied in the reinforcement learning, usually denoted as M = (S.AA (SS,,) R, P, n),, where S is the state space, A is the action space, R S x A ~> ((R+) is the reward, P: x A >> A(S) is the transition, and μ is the initial state distribution. We additionally define r: S x A + denote the expected reward.

---

We focus on the episodic MDP with the horizon' ! H E 2z and time-homogeneous setting" that P and R do not depend on the level h E [H) (potentially non-stationary) policy π is defined as = (Ii: u2. ... TH)) where TA S - (AA), wh E [H. Following the standard definition, we define the value function (s) = E. D H (s)s,
s] and the action-value function (i.e. the Q-function) 0% (s, a) == Ep.- ا>t=h R(s,. (e)](5h, a4)) = (s, a)), which are the expected cumulative rewards under the transition P and policy starting from 84
and (8h: o4) (s. a).
Notice that, even though P and R keep invariant under the change of h, V and Q always depend on h in the episodic setting, which introduces additional technical difficulties compared with the infinite horizon setting.
The expected cumulative reward under policy is defined as: o² := Ey (s)], and our ultimate goal is finding the optimal policy π' of M, which can be written as: π = arg max, (v"). We additionally define the reaching probabilities (s) = Pu.P. (sp s), (s, a) = P (sh s. a4 = a), that represent the probability of reaching state s and state-action pair (s, a) at time step h. Obviously have E, 5% (s) 1, Ee. 5% (s, = 1, vh (H), and we also have the following re- lations between 57. (8) and 5T (8, a): 57 (s, a) E (s){(a)s), 1 Es,a (
With Р at hand, we can write v"' in an equivalent way: v== = Σx,a ((Eneja) (+, r(s, r(s.a)), which provides dual perspective on the policy evaluation [18].
3.2 Offline Reinforcement Learning
Generally, P and r are not revealed to the learner, which means we can only learn about M and identify the optimal policy x² with data from different kinds of sources. In offline reinforcement learning, the learner can only have access
collection of data D = {(s,, ag Tú, se)) where rs R(s;, ai) and s P(-|s;, 0z). that is collected in K episodes with (known or unknown) behavior policy (so that n = HH), For simplicity, define n(ss, a) as the number of data that (s;, a.) (s, a). while niss a, s') is the number of data that (8,, 0g. s() (s, (s,,a,5 5')
With D. the learner is generally asked to do two kinds of tasks. The first one is the offline policy evaluation (a.k.a off ofllcy evaluation), that aims to estimate of for the given The second one is the offline policy optimization, that aims to find the H* that can perform well on M. We are interested in the statistical limit due to the limited number of data, and how to approach this statistical limit with simple and computationally efficient algorithms.
4 Offline Policy Evaluation
In this section, we first consider the offline policy evaluation for tabular MDP with number of state S = |S] < oo, number of action A = |A| < oc, which is the basis for the more general settings. We first introduce the plug-in estimator that are widely used in practice. Then we describe the assumptions we use, show the error bound of the plug-in estimator, and provide the proof sketch of the error bound.
consider, which is equivalent to different kinds of estimators
4.1 The Plug-in Estimator
Here we introduce the plug-in estimator. We first build the empirical MDP M with the data: P(s'|s, (is'|s,a) a) m(s.a.s')
n(s,a) f(s, a) Exe (a where 1 is the indicator function. Then correspondingly define Q7, V,, and finally the estimator 07 Vh E [H], by substituting the P and
n(s,a)
'A common belief is that we can always reproduce the results between episodic time- homogeoomge setting and infinite horizon setting via substitute the horizon H in episodic setting with the "effective horizon" 1 1- in episodic setting. However, this argument does always hold, for example the dependency decouple technique used [34, 28] cannot be directly applied in the episodic setting.
"Some previous work consider time-inhonogeneous setting [e.g. 39], where P and R can be varied for different h E [M.. It noteworthy that need additional H factor in the sample complexity identify e-optimal policy for time-inlle inhomogeneous MDP compared with homogenougs MDP. Transforming the improvement analysis from time- homooenoeen setting to time- inee-ionooggoouuss setting is trivial (we only need to replace S with H S). but not versa, as the analysis for time imn-iohooogsnssus setting probably do not exploit the invariant transition sufficiently.
5

---

in 2h V and o" with P and A. Such computation can be efficiently implemented with dynamic programming. We also introduce the reaching probabilities (s) IP p. (sh. s). (s, (s,a)
P P.P.. (5h 8, 04 a) in the empirical MDP M, which will be helpful in analysis.
The plug-in estimator has been studied in [30] under the assumption of linear transition. It's known that the plug-in estimator is equivalent to the MIS estimator proposed in [19] and a certain version of DualDICE estimator with batch update is proposed in [16], due to the observation that
6" = =E,,a ((neet (e, ((s,a)).
4.2 Theoretical Guarantee
Here first summarize the assumptions we use for the tabular MDP.
Assumption (Bounded Total Reward). VT, we have Enein Th S 1 almost surely, where 31 ~ p.. an T T(-Is)) ~ R(sh. an) and 8/41 P(-ss,, a,), vh E [H]. This also means P(r ~ R(s.a)rr >) 0, V(s.a).
This is the key assumption used in [26, 27] to escape the polynomial dependence of horizon in episodic setting. As discussed in [37, [37, 27], this assumption is also more general than the uniformly bounded reward assumption: ((s. r(s, a) S 1/H. Thus, all of the results in this paper can be generalized to the uniformly bounded reward with proper scaling of the bounded total reward.
Assumption 2 (Data Coverage). ((s,a). na(s.) a) 2 ndm-
This assumption has been used in [19, 24] and is similar concentration coefficient assumption originated from [40]. Intuitively, the performance of the offline reinforcement learning should depend on dm, since the state-action pair with less visitation will introduce more uncertainty.
Notice that, dm E (o, (S. Assuming access to the generative model, we can query equal num- ber of samples from each state action pair, where dm = (SA) For the offline data sampled with fixed behavior policy тBEH,
view dm ~ π min2,0 Enet Sn TBER (s,a), which measures
the quality of exploration for тBEE. When the number of episodes K Ω (1/dm), by standard concentration, we know ming,a (1,s a) 2 ndn = HKdm
We remark that, some of the recent Liu et al. [41], Yin et al. [36] define the data coverage via the coverage on the visitation of the optimal policy when considering offline policy optimization. This kind of data coverage can be covered by our Assumption 2, by considering the sub-MDP which only consists of the state-action pair that can visited by the optimal policy. As we already know that the optimal policy will not leave this sub-MDP, any near-optimal policy on this sub-MDP will be near-optimal on the original MDP, and hence our results can be directly applied under this alternative definition of data coverage.
With these assumptions hand, we can present our main results.
Theorem 1. Under Assumption and Assumption suppose K π (L/dm) then
6- 1
Kd...
holds with probability at least 1 - 8, where K is the number of episodes, dm is the minimum visiting probability and absorbs the poly log factors.
To demonstrate the tightness of our upper bound, we provide minimax lower bound in Theorem 23. Theorem 2. There exists a pair of MDPs Mi and M2, and offline data D with [D] KH and minimum visiting probability dmn such that for some absolute constant Co, we have
infę sup PM: (I0T -²
KK > 0.25,
where 1 is any estimator that lakes D inpul.
Remark Theorem and 2 show that, even with the simplest plug-in estimator, match the minimax lower bound Ω Kd... for offline policy evaluation in time-hoogennoous MDP up to logarithmic factors. As a result, we can conclude that time-homogeneous MDP is not harder than the bandits in offline policy evaluation.
'To the best of our knowledge, no lower bound has been provided for finite horizon Lime-homogeneon setting, so here provide minimax lower bound, and the proof can be found in Appendix B.

---

Remark The assumption that K = (0 (1/dm) is mild and necessary assumption, as with only (1/dm) episodes, there can exist some under-explored state-action pair which unavoidably leads to constant error (this is also how we construct the hard instance for the minimax lower bound).
Remark Central to our analysis is a recursion based upper bound on the "total variance" term (see Lemma 1), which enables us to have sharper bound for the plug-in estimator compared with previous work [e.g. 19, 24J that include the unnecessary poly(S, A) factors in the higher-order term.
4.3 Proof Sketch
The detailed proof can be found in Appendix A, and here we sketch our proof in short. With the value difference lemma (see Lemma in the Appendix A), we need focus on bounding the term:
Exem Ex, En (s, a) [>.' (P(s'ls, P(s")s, a)) (i++
which, by Bernstein's inequality and Cauchy-Schwand inequality associated with the Assumption 1 and Assumption 2, can be upper bounded by the following term with high probability:
kdm V Ene(m Es,a 5% (s, a) Varp(s, (Vi+ (s()) Kd
To bound the "total variance" term Enem Ex,a Sh recursion-based method based on the following observation: Lemma (Variance Recursion For Evaluation). For the value function V (8) induced by any we have that
( a) aar (6)),, use a novel
Σ Σ hE(H] 8.0
(s, a) Varr(na) [V++((3)28
$ Σ (s) a) hE(H] 8.0
(((s'ss,a) -P()l,a)))())ss
a() (n+z(5)22tt)
2
(I)
Here the term in (1) can be bounded with Enem Es,a (s a) Par Vi+ ( (1)) the total variance of higher-order value function via Bernstein's inequality. Thus Lemma be applied iteratively to obtain a tight bound for the "total variance" term. Define
A = Σ Σ (s) a)
(P((11s.))- P(s')s.)) (
RE(M] 8.a
Applying Lemma with V (s),
write the following recursion:
A (1)
Kd... (A 21-1) + Kd..
Solve this recursion, and we can obtain the results in Theorem 1.
Offline Policy Optimization
In this section, we further consider the offline policy optimization for tabular MDP, which is the ultimate goal for offline reinforcement learning. We first introduce the model-based planning algorithm, which is probably the simplest algorithm for offline policy optimization. Then we analyze the performance gap between the policy obtained by model-based planning and the optimal policy.
5.1 Model-Based Planning
We consider the optimal policy on the empirical MDP M, which can defined as
# arg max, 1
Here #* can be obtained by dynamic programming with the empirical MDP, which also known as model-based planning. We remark that our analysis is independent to the algorithm used for solving (2). In other words, the result also applies to the optimization-base planning with the empirical MDPs [42, 43], long it solves (2).
7

---

5.2 Theoretical Guarantee
Theorem provides an upper bound on the sub-optimality of #
Theorem 3. Under Assumption and Assumption suppose that K 22 (1/dm), and then
1 0
v
Kdm
Kdm
holds with probability at least 1 - 6, where K is the number of episodes, dm is the minimum visiting probability and absorbs the poly log factors.
We also provide minimax lower bound under the finite horizon time- homogeneuss setting.
Theorem 4. There exists pair of MDPs Mi and M2, and offline data DD with [D] KH and minimum state-action pair visiting frequency dems such that for some absolute constant Co, we have
inf M.) PM, (104(D) -² -
vKdm 0.25,
where ä is any planning algorithm that takes 'D as input.
Remark Theorem 3 provides bound approaching the minimax lower bound in Theorem up to logarithmic factors and higher-order term, which shows that the error of offline policy optimization does not scale polynomially on the horizon. Notice that if dn Ω (stz). we can obtain an error
bound of Ō (V
SA S²A) ) which can be translated to sample complexity Ō
SAA that
matches the best known result of sample complexity for online finite-horizon homoehooogsssuus setting [27]. We conjecture that the additional S factor in the higher-order term is only artifact (see Lemma 2) and can be eliminated with more delicate analysis. We leave this as an open problem.
Remark There are also works considering local policy optimization [e.g. 44-46] when the offline data are not sufficient exploratory. We want to emphasize that, as Theorem suggests, to identify the global optimal policy, we need the offline data sufficient exploratory.
5.3
Proof Sketch
The detailed proof can be found in Appendix A, and here sketch proof in short. Notice that
Error Fixed Policy Error Data Dependent Policy
We can directly apply Theorem 1 to bound the error on fixed policy. For the error on data-dependent policy, since the policy # depends on data, we need to consider
Σ Σ
(s,
Σ
P(ssls,)) P(8'1s, a)) Vitii(o)
hE(m 8,0
Σ
Σ
(s,
Σ ( p() Virts(ot)
(4)
hE[H] s.
Σ (s. a)
Σ a)) (Vita(6))
(5)
KE[H] 8,a
As x² is independent of P, the term in (4) can be similarly handled with the techniques used in offline policy evaluation. However, due the dependency of a* and P. we need to deal with the term in (5) more carefully. To decouple the dependency of #* and P. first introduce the following lemma:
Lemma 2, (s) E [0, 1). vh E [H) E S, then we have that with high probability Σ. (P(slss,a) P()'(s,a)) V/(62)/
S.r [r]
Sc
m(s,a)
(s.a))
8

---

Remark Lemma 2 has been widely used in the design and amalysis of online reinforcement learning algorithms, (e.g. 27J. It holds even (s) depends on P(s'|s, Is a), however, at the cost of an additional factor. This is the source of the additional S factor in the higher-order term, and we believe more fine-grained analysis can help avoid this additional S factor.
We also have the following recursion for (4) and (5):
Lemma (Variance Recursion For Optimization). For Vh((s) = Vi (s) and Vh(s) = Vi (s)
Vh (s), we have that
Σ
Σ
(s, Varp((a))
[V=+(())
he[H]
s Σ
Σ
(s,a) a)
Σ (( - P(s'(s,a) Vn+ (s+
(6)
hE[H] 8,a
Sh (s, a) Σ P(s'|s,a) P( (ilsssss)p( Vina(6)) 17)
+ 2
Σ (s))
Σ
11 8.0
Denote
A2
Σ Σ
(5,,aa) a)
Σ (P(5'(s,a) P(s')s.a) (o)
hE[H] 8.a
P() ( (Viti(6)) V viti(ss)) 24
As(1) Σ Σ
as)
hE[M] 8,0
Applying Bernstein inequality Lemma and then Lemma 3, we have that:
A2(1)= SV Kd
(A2(i + 1) + 2 + A2(())) Kdm
St
St
(1 SV Kdm
(A2(i + 2i a + Az())) +
Kdm
With Assumption know x < Also, with (3) and (4), we have that ux* 2 < As(()
O (v Kdn.. Solve this recursion, then obtain the results in Theorem 3.
6 Extensions to Linear MDP with Anchor Points
In this section, we first introduce the definition of the linear MDP with anchor points [47, 1]. and then generalize our results offline policy evaluation and optimization this setting.
Definition (Linear MDP with Anchor Points [47, 1)). For the MDP M (S,A, R, P. p). assume there is feature map : S x A RRd, such that and P admits linear representation:
r(s.a) (b(s,a),0,) a() (ō(s, a), H(s'))
where y is unknown (signed) measure S. S. Furthermore, assume there exists of anchor state-action pairs K. such that V(s, a) E S A. 3(x% "kEk,
a(s,a)= = EnEK Xx ((xx( ax), ΣNEK === 11
V.
With the definition of Linear MDP well the anchor points assumption, we find that r(s, a) = Σ*Ek >x'"T(sx r(kk, 0x), P(s'ls,a) a) = ΣkEK P(s'|sk 44), which can lead to an em- pirical estimation of P and by replacing (4)kkk {P(s') [s, ag HeE with the empirical counterpart (f(*2. a&) JEEK (P(s'|8k, [*)]sex estimated from the offline data. Following [47, 1]. additionally make the following assumption on the offline data:

---

Assumption 3 (Anchor Point Data [47, ID. Assume |K] = d For the offtine data D {(s,, Tr, kefmn) a,) {(Sg, ae) Vi E [n]. Furthermore, vk E K, n(sy, m(s),,a)) 2 ndm-
We now present the main theorem on the offline policy evaluation and offline policy improvement on the linear MDP with anchor points.
Theorem 5. Under Assumption and Assumption 3, suppose n n= ② (H/dm), and then for a given policy n, the plug-in estimator 6 satisfies
10-
H
ndm.
with probability at least 1 - 8, where is the number of offline data, dm is the minimum visiting probability of anchor points and absorbs the polylog factors.
Theorem 6. Under Assumption and Assumption 3, suppose that n2 52 (H/dm), and then for the a obtained by model-based planning,
He dHL mdm
mdm."
holds with probability at least 1 1 6, where n. is the number of offline data, is the feature dimension, dm is the minimum visiting probability of anchor points and absorbs the polylog factors.
Proof of both theorems can be found in Appendix C. From a high-level perspective, for the unseen state-action pair, we still have Bernstein-type concentration bound and a lemma similar to Lemma 2. Hence we can apply recursion introduced in Lemma 1 and use the similar techniques for tabular MDP to obtain the desired results. We want to remark that such results demonstrate the broad applicability of our recursion-based analysis in different kinds of offline scenarios.
observe that
Remark Compared with the results in [1], we remove the additional dependency of min [S] d] in the main term and approach the optimal complexity shown in the [47] up to logarithmic factors, which shows that model-based planning is minimax optimal for Linear MDP with anchor points and demonstrates the effectiveness of our recursion based analysis.
Remark Here do not directly replace the term n/ H with K, make relatively strong assumption on all of the offline data are sampled from the anchor points. One potential question is how general the anchor point assumption is. We notice that, [30] showed, the popular FQI algorithm for linear MDP provides an estimate of P
a()'ss,a) = a(8 a) A- -iEm ((81,,))1.
where Ả = -iiej ((5 a. (,),,,, As Eg ((5'|s, a) = 1, by Definition 1,
p(s 1= I. 8, a) ((s,a) H(s' = a) TA- (E),)))(s),,a))
Thus, if 6(s,
ai) 2 0, V(s, a), then it forms linear MDP with anchor points with K. ((s;, ((s),:)))ie (x()), A1 ((s, --a--i--sss a&) and our analysis can be simply adapted to this case where ndm is replaced with Amin (A) using Freedman's 's inequality [48]. and Amin(A) denotes the minimum eigenvalue of Å. We notice that if ((s, a) -1sss a;) < O. and s; are distinct for each i (which is probable for exponential large (S)), then P(s'|s, a) < O. which can be pathological for the algorithm and analysis. We expect well-behaved transition estimation (i.e. (P) for linear MDP shares the similar results, even without anchor point assumptions. We leave this as an open problem.
Conclusion
In this paper, we revisit the offline reinforcement learning on episodic time- tine-homogencous MDP. We show that, if the total reward properly normalized, offline reinforcement learning not harder than the offline bandits counterparts. Specifically, we provide performance guarantee for algorithms based on empirical MDPs, that match the lower bound up to logarithmic factors for offline policy evaluation. and up to logarithmic factors and higher-order term for offline policy optimization, and both do not have polynomial dependency on H. There are still several open problems. For example, can we provide a sharper analysis for the policy obtained by model-based planning without any additional factors on higher-order term? Can we extend to MDP with more general assumption? We leave these problems future work.
10

---

Acknowledgement
The authors thank the anonymous reviewer for their constructive feedback. TR would like thank for the helpful discussion with Ming Yin and Yu Bai. SS gratefully acknowledges the funding from NSF grants 1564000 and 1934932, and SSD gratefully acknowledges the funding from NSF Award's 10170 and DMS-2134106.
References
[1] Qiwen Cui and Lin F Yang. plug-in solver sample-efficient for feature-based reinforcement learning? arXiv preprint (rXiv:2010.05673. 2020.
[2] Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint MrXiv:1312.6602 2013.
[3] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che. Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, al. Mas- tering the game of go with deep neural networks and tree search. nature, 529(7587):484-48) 2016.
[4] OpenAI: Marcin Andrychowicz, Bowen Baker, Maciek Chociej, Rafal Jozefowicz, Bob Mc- Grew, Jakub Pachocki, Arthur Petron, Matthias Plappert, Glenn Powell, Alex Ray, et al. Learning dexterous in-hand manipulation. The International Journal of Roboties Research, 39(1):3-20, 2020.
[5] Hanjun Dai, Elias B Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. arXiv preprint arXiv: 1ee.:00045..5. 2017.
[6] Travis Mandel, Yun-En Liu, Sergey Levine, Emma Brunskill, and Zoran Popovic. Offline policy evaluation across representations with applications to educational games. AAMAS, pages 1077-1084, 2014.
[7] Susan A Murphy, Mark van der Laan, James M Robins, and Conduct Problems Prevention Re- search Group. Marginal mean models for dynamic regimes. Journal of the American Statistical Association, 96(456): 1423, 2001.
[8] 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 2019.
[9] 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
2019.
[10] Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, and Ed H Chi. Top-k off off-policy correction for reinforce recommender system. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pages 456-464, 2019.
[11] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01645 2020.
[12] Lihong Li, Rémi Munos, and Csaba Szepesvári. Toward minimax off-policy value estimation. In Artificial Intelligence and Statistics, pages 608-616. PMLR, 2015.
[13] Nan Jiang and Lihong Li. Doubly robust off-policy value evaluation for reinforcement learning. In International Conference on Machine Learning, pages 652-661. PMLR, 2016
[14] Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse horizon: Infinite-horizon off off-policy estimation. arXiv preprint arXiv: 02200.22422 /2429, 2018.
[15] Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. Towards optimal off off-ppoicy evaluation for rein- forcement learning with marginalized importance sampling. arXiv preprint arXiv: 1906.993999 2019.
11

---

[16] Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: aggosti estimation of discounted stationary distribution corrections. In Advances in Neural Information Processing Systems, pages 2318- 1-228,,, 2019.
[17] Masatoshi Uchara, Jiawei Huang, and Nan Jiang. Minimax weight and q-function learning for off-policy evaluation. In International Conference on Machine Learning, pages 9659-9668. PMLR, 2020.
[18] Mengjiao Yang, Ofir Nachum, Bo Dai, Lihong Li, and Dale Schuurmans. Off-policy evaluation via the regularized lagrangian. arXiv preprint arXiv:2007.085: 034388,, 2020.
[19] Ming Yin and Yu-Xiang Wang- Asymptotically efficient off-policy evaluation for tabular reinforcement learning. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the
Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 3948-3958, PMLR, 26-28 Aug 2020.
[20] Assaf Hallak and Shie Mannor. Consistent on-line off-policy evaluation. In International Conference Machine Learning, pages 1372-1383. PMLR, 2017.
[21] Carles Gelada and Mare G Bellemare. Off-policy deep reinforcement learning by bootstrapping the covariate shift. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3647-3655, 2019.
[22] Ruiyi Zhang, Bo Dai, Lihong Li, and Dale Schuurmans. Gendice: Generalized offline estimation of stationary values. arXiv preprint arXiv:2002.09072 2020.
[23] Ofir Nachum, Bo Dai, Ilya Kostrikov, Yinlam Chow, Lihong Li, and Dale Schuurmans. Al- gaedice: Policy gradient from arbitrary experience. arXiv preprint arXiv:1912.02074, 2019 2019.
[24] Ming Yin, Yu Bai, and Yu-Xian Xiang Wang. Near optimal provable uniform convergence in off-policy evaluation for reinforcement learning. arXiv preprint arXiv:2007.03760, 2020.
[25] Yao Liu, Adith Swaminathan, Alckh Agarwal, and Emma Brunskill. Off-policy policy gradient with stationary distribution correction. In Uncertainty in Artificial Intelligence, pages 1180-
1190. PMLR, 2020.
[26] Ruosong Wang, Simon S Du, Lin F Yang, and Sham M Kakade. Is long horizon reinforce- ment learning more difficult than short horizon reinforcement learning? arXiv preprint arXiv:2005.00527, 2020.
[27] Zihan Zhang, Xiangyang Ji, and Simon S Du. reinforcement learning more difficult than ban- dits? a near-optimal algorithm escaping the curse of horizon. arXiv preprint arXiv:2009. 13503, 2020.
[28] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with a generative model. arXiv preprint arXiv:2005.1 10005.12900 1900, 2020.
[29] Ashwin Pananjady and Martin J Wainwright. Instance-dependent l-infinity-bounds for policy evaluation in tabular reinforcement learning. IEEE Transactions on Information Theory, 67(1): 566-585, 2020.
[30] Yaqi Duan and Mengdi Wang. Minimax-optimal off-policy evaluation with linear function approximation. arXiv preprint arXiv:2002.095/ 2020.
[31] Nathan Kallus and Masatoshi Uehara. Efficiently breaking the curse of horizon in off-policy evaluation with double reinforcement learning. arXiv preprint
090000059900, 2019.
[32] Nathan Kallus and Masatoshi Uchara. Double reinforcement learning for efficient off-policy evaluation in markov decision processes. Journal of Machine Learning Research, 21(167):1-63, 2020.
[33] Yihao Feng, Tongzheng Ren, Ziyang Tang, and Qiang Liu. Accountabll off-policy evaluation with kernel bellman statistics. In International Conference on Machine Learning, pages 3102- 3111. PMLR, 2020.
12

---

[34] Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with generative model is minimax optimal. In Conference on Learning Theory, pages 67-83. PMLR, 2020.
[35] Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with generative model. Machine learning, 91 (3):325-349, 2013.
[36] Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal offline reinforcement learning via double variance reduction, 2021.
[37] Nan Jiang and Alekh Agarwal. Open problem: The dependence of sample complexity lower bounds on planning horizon. Conference On Learning Theory, pages 3395-3398. PMLR, 2018.
[38] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[39] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learning In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and Garnett, editors, Advances Neural Information Process- ing Systems, volume 31, pages 4863-4873. Curran Associates, Inc., 2018. URL http:://pcceeedn..eeeeeeep.ppppp ottp://iiii..i.oooooiiiiiooooooa dillecbbbfoocccaa665577776622222 Paper.pdf.
provably efficient?
[40] Rémi Munos. Error bounds for approximate policy iteration. In ICML, volume 3, pages 560-567, 2003.
[41] Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Off-policy policy gradient with state distribution correction. arXiv preprint 1904.0190.08847: 2019.
[42] Martin Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[43] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. The MIT Press, 2012. ISBN 026201825X,
[44] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In In Proc. 19th International Conference on Machine Learning. Citesecr, 2002.
[45] Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch reinforcement learning without great exploration. arXiv preprint arXiv:2007.08202. 2020.
[46] Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine, Conservative q gelearning for offline reinforcement learning. arXiv preprint arXiv:2006. 04779, 2020.
[47] Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Muchine Learning, pages 6995-7004. PMLR, 2019.
[48] David A Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100-118, 1975.
[49] Tor Lattimore and Marcus Hutter. Near-optimal pac bounds for discounted mdps. Theoretical Computer Science, 558:1 15-3 2014.
[50] Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[51] Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: uniform pac bounds for episodic reinforcement learning. In Proceedings of the 31st International Conference on Neural Information P Processing Systems, pages 5717-5727, 2017.
[52] Jinglin Chen and Nan Jiang. information-thhereel considerations in batch reinforce- ment learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceed- ings of the 36th International Conference on Machine Learning, volume 97 of Proceed- ings of Machine Learning Research, pages 1042-1051. PMLR, 09-15 Jun 2019. URL
13

---

[53] Tengyang Xie and Nan Jiang. Qa approximation schemes for batch reinforcement learn- ing: A theoretical comparison. In Jonas Peters and David Sontag, editors, Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), volume 124 of Pro- ceedings of Machine Learning Research, pages 550-559. PMLR, 03-06 Aug 2020. URL http://procceedings..o wwt.:/sss....pees/11111/.2.. http://proeedddggggmmmessess///p 2ttp///22/xxe22aammmmm
[54] Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizabilityy arXiv preprint arXiv:2008. 04990, 2020.
14


Reviews:
[{"review_id": "OC6kpesdJ_b", "reviewer": "Reviewer_PYbq", "summary": "The authors revisit offline RL on episodic MDPs both in the tabular and linear with anchors cases. They prove complexity bounds that are nearly horizon $H$ free (up to polylog terms in the horizon $H$), when the maximum return is 1 for both offline policy evaluation and offline policy optimization.", "questions": "", "limitations": "", "rating": 9, "confidence": 3, "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 is a remarkable theoretical paper. I took a great interest reviewing it and I think it will have a great impact in the offline policy evaluation/optimization community.\n\nMajor remarks:\n- The writing around the assumptions is not as sharp as everywhere else:\n   - line 197: almost surely -> It is with respect to the stochasticity or R and P? But since they are defined on a finite MDP, and since it is a finite sum, either this event is $0$ or $>0$.\n   - lines 201-202: Assumption 1 is equivalent to the uniformly bounded reward isn't it? When moving from one to another, and back, you lose a factor $H$, but otherwise, they are equivalent.\n   - line 203: it can be generalized but as I said in my previous remark, a factor $H$ appears, so it defeats the main arguments of the method.\n   - Assumption 2 seems unnecessary to me. The actual assumption that matters and that is not formalized as such (even though it is well recalled in theorems), is that $K= \\tilde{\\Omega}(1/d_m)$.\n- the actual dependency in $H$ is actually hidden in $d_m$: the longest horizon the MDP is the more skewed is going to be the state visitation distribution of any policy. And to prove that, many papers have shown that model-based planning (which may be wrongly called, because performing q-learning on the samples themselves until full convergence would lead to the same result) lead to worse performance than pessimistic/conservative planning **on average**. Maybe the authors should be more explicit about this effect.\n\nMinor remarks:\n- lines 64-66: I could not understand this sentence.\n- line 98: refers to assumption 1, while it is only enounced 2 pages later.\n- table 1: you use $\\epsilon$ in Table 1, but it is introduced only line 113. Also, the writing about table 1 does not use the same parameters for the bounds, so it is a bit inconsistent.\n- line 155: even -> even though.\n- line 158: of $\\pi$ -> delete\n- lines 171-172: $(s_i=s,a_i=a,r_i,s'_i)$ and $(s_i=s,a_i=a,r_i,s'_i=s')$\n- lines 275-276: local policy optimization was already done by Kakade2002, Petrik2016, and Laroche2019, just to name a few.\n- lines 282-284 are a repetition of lines 280-281?\n\n\n[Kakade2002] Kakade, S., & Langford, J. (2002). Approximately Optimal Approximate Reinforcement Learning. In International Conference on Machine Learning.\n\n[Petrik2016] Petrik, M., Ghavamzadeh, M., & Chow, Y. (2016). Safe policy improvement by minimizing robust baseline regret. In Advances in Neural Information Processing Systems (pp. 2298-2306).\n\n[Laroche2019] Laroche, R., Trichelair, P., & Des Combes, R. T. (2019, May). Safe policy improvement with baseline bootstrapping. In International Conference on Machine Learning (pp. 3652-3661).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"ethical_concerns": "none", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "HpQxy7-AAv0", "reviewer": "Reviewer_vD82", "summary": "The paper analyzes the plug-in approach to off-policy evaluation and optimization in reinforcement learning, and sharpens some of the sample complexity bounds (assuming sufficiently exploratory data, time-homogenous MDPs). The key novelty is in upper-bounding the variance of estimated values cleverly by using higher-order powers of appropriate values. By doing so, the paper's derived bounds do not directly depend on the horizon of the MDP. One benefit of the proposed analysis is that a very similar line of reasoning is sufficient to derive horizon-independent bounds for both evaluation and optimization, as well as for tabular MDPs as well as linear MDPs with additional structure.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "(After author feedback)\nThe authors' responses adequately addressed questions around significance, motivation and technical concerns. There were remaining questions about the novelty/originality and scope of contributions. The paper can be substantially stronger by addressing them (e.g. by weakening Assumption 2).\n\n-----\nThe paper had a reasonable exposition, and the high-level ideas were explained clearly. This review focuses only on the weaknesses.\n\nCorrectness: Stepping through the appendix, there were two confusing points (detailed below). This makes me confused about Theorem 1 and 2. If this confusion is clarified, the paper would improve to be borderline. Given the confusions, I have not carefully checked the proofs of the policy optimization theorems.\n\nOriginality: The main idea is to use the total variance bounding technique of [27] in the off-policy setting. This is done in a pretty brute-force way (assume that there is sufficient exploration via Assumption 2). The derivations become somewhat more tedious (keeping track of the coverage coefficient in each step) but not novel.\n\nSignificance: Disappointed to see that motivation of the work was not clear. Beyond an academic exercise in sharpening the upper bounds, does this help explain some previously unexplained phenomenon? For instance, in practical applications of the plug-in approach, do we see that it works surprisingly well as H increases (while existing theory suggested that it should not)? \nAre there practical applications where Assumptions 1 and 2 (and for linear MDPs, the anchor data assumption) can reliably hold? Under the exploratory data assumption, would other approaches have a H-dependence even in time-homogenous MDPs? For instance, an off-policy policy gradient approach might depend on H while the plug-in approach does not (and this might guide us to choose the latter in large-H regimes). \nThe anchor data assumption and construction was unusual to me. Are there practical applications where they are useful? (If not, they seemed to be just assumptions of convenience so as to transport results from tabular MDPs to linear MDPs without having to construct an epsilon-net). \nThe paper unfortunately does not address any of these questions to establish the motivation or significance of its contributions.\n\nConfusions:\nAppendix B [Proof of Theorem 2]\n0 <= c_1 <= 1. And 0 <= c_2 <= c_1. In Line 619, when setting c_2 = c_1 - ...(H), note that c_2 < 0 for large values of H which is not allowed.\nBut c_2 has to be set to such a term to witness a value gap that scales with H which is needed to assert the claim in Line 622.\nPlease clarify? I am skeptical that this MDP construction will witness an Omega(sqrt(H/(n*d_m))) estimation gap under Assumption 1 and 2.\n\nAppendix A [Line 555]\nPerhaps derive V_1(i) <= H for all i using Assumption 1 to make this more explicit.\nThis statement is easy to show under the uniform reward assumption that r_h < 1/H.\nHowever under assumption 1, it takes more to assert this claim constructively. For example, time-homogeneity rules out situations where r_H = 1 and r_h =0 for h < H; and situations where a set of states only become reachable at H. In such situations however, this claim is false. Does time-homogeneity rule out all pathological situations where V_1(i) > H for some i?\n\nMinor issues:\n- Since Table 2 and Section 2 require knowing what Assumption 1 refers to, it may be better to define it in Sec2, and simply re-state it in Sec 4.2.\n- Notation collision: r is defined as E[R] above. Unfortunately, r_i \\sim P(R). This makes some objects ambiguous.\nFor instance, the empirical reward in Line 186 should be hat{r}(s,a) = \\sum_i r_i 1{...}/n(s,a). As written currently, r(s_i, a_i) can be misunderstood as the expected reward of (s_i, a_i) rather than the realized reward r_i. This also affects the statement of Assumption 1 (what is r_h exactly? is there a typo in Line 198, r_i should be r_h?).\n- Clarify the empirical MDP construction hat{M} for P(.|s,a) and R(s,a) when n(s,a)=0. Or specify the regime (under Assumption 2) clearly.\nPerhaps bring Assumption 2 into Sec 3.2?\n\nTypos:\nLine 45 - related *line* of work\nLine 47 - only *has* poly log\nLine 65 - that *has* broadly\nLine 84 - we *need* to deal\nLine 155 - *even though P and R remain invariant when h changes*\nLine 158 - cumulative *reward under policy \\pi* is defined\nLine 165 - perspective *on* policy evaluation\nLine 177 - *computationally* efficient\nLine 212 - min_s,a n(s,a) \\approx H*K*d_m. The \\forall s,a is superfluous.\nFootnote 3 - lower bound *has* been provided", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not address the societal impact of their contributions. However, this is a completely theoretical work that aims to sharpen the analysis of an existing algorithm, incremental improvement by using a known technique. So there societal impact of this work is unlikely to be adverse.\nRe: the limitations, the authors do not discuss the plausibility of their assumptions nor the motivations of the linear MDP w/ anchor points setting. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {"ethical_concerns": "The paper does not raise any ethical concerns at this time, nor does it increase the scope of RL applications that can be attempted in the future (for instance, no new applications that may be problematic)."}}, {"review_id": "8ZvLlsqcpR0", "reviewer": "Reviewer_aVzM", "summary": "This paper provided horizon-free theoretical results for offline policy evaluation and improvement. It showed the bound for estimation error and sub-optimality under several assumption.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Originality. The proof of their results is origin.\n\nQuality. This is a complete work. The showed both upper bound and lower bound under their assumption. However, the assumption might be too strong. Apart from the assumption previously notice, time-homogeneous is also strong since some other work on offline RL does need it.\n\nClarity. This paper is well-written. \n\nSignificance. This paper is significance in the sense that horizon-free results can deepen our understanding for episodic RL.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The author addressed their limitation adequately.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "6qdQWrQFlJ", "reviewer": "Reviewer_ND3y", "summary": "This paper provides near-matching, horizon-free upper and lower-bounds on the Offline Policy Evaluation (OPE) and Offline Policy Optimization (OPO), in finite horizon time-homogeneous MDPs, with tabular and linear MDP structures with anchor points.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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 presentation of the paper is clear and illustrative, therefore I believe substantial improvements have been made since the previous submission in terms of paper polishing.\n\nThe additional setting of linear MDP with anchor points, on the other hand, seems not substantial. It's not a well-accepted setting and the analysis seems to be a straightforward extension of the tabular analysis, since after all anchor point means only d (s,a) pairs matter and so everything can be represented back into a table. Unlike the ICML reviewers, I think even the tabular results alone are worth publishing as a theoretical paper.\n\nBesides that my main complaint is also on the strong assumption of uniform data coverage, which is too strong for most applications. A recent line of work performs offline reinforcement learning without a uniformly lower-bounded data distribution with the principle of pessimism. It has been shown that the optimal policy can be found as long as the offline data properly covers the visitation distribution of the optimal policy. Can the author comment on whether horizon-free learning possible without the uniform data coverage assumption? Also, this line of work is also worth covering in the related work section. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: According to the reviews, which are all in favor of accepting the paper (although most of them only slightly), this is a solid contribution for which I recommend acceptance. The points raised in the reviews and discussed in the rebuttal (e.g. concerning motivation and some of the debated technical details) shall be taken into account when preparing the final version.
Decision: Accept (Poster)