Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
Authors: Ming Yin
Yu Bai
Yu-Xiang Wang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Theory
Reinforcement Learning Theory
Markov Decision Process Theory

Abstract: We consider the problem of offline reinforcement learning (RL)  --- a well-motivated setting of RL that aims at policy optimization using only historical data. Despite its wide applicability, theoretical understandings of offline RL, such as its optimal sample complexity, remain largely open even in basic settings such as \emph{tabular} Markov Decision Processes (MDPs). 
 In this paper, we propose \emph{Off-Policy Double Variance Reduction} (OPDVR), a new variance reduction-based algorithm for offline RL. Our main result shows that OPDVR provably identifies an $\epsilon$-optimal policy with $\widetilde{O}(H^2/d_m\epsilon^2)$ episodes of offline data in the finite-horizon \emph{stationary transition} setting, where $H$ is the horizon length and $d_m$ is the minimal marginal state-action distribution induced by the behavior policy. This improves over the best-known upper bound by a factor of $H$. Moreover, we establish an information-theoretic lower bound of $\Omega(H^2/d_m\epsilon^2)$ which certifies that OPDVR is optimal up to logarithmic factors.  
Lastly, we show that OPDVR also achieves rate-optimal sample complexity under alternative settings such as the finite-horizon MDPs with non-stationary transitions and the infinite horizon MDPs with discounted rewards.

Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
Ming Yin 1,3 Yu Bai?, and Yu-Xiang Wang'
Department of Computer Science, UC Santa Barbara
"Salesforce Research
'Department of Statistics and Applied Probability, UC Santa Barbara ming.yin@ucsb.cc edu
yu. baiesalessorrre....oooooo...
yuxi angians wws.buubu.. edu
Abstract
We consider the problem of offline reinforcement learning (RL) - well-motivated setting of RL that aims at policy optimization using only historical data. Despite wide applicability, theoretical understandings of offline RL, such as its optimal sample complexity, remain largely open
in basic settings such tabular Markov Decision Processes (MDPs). In this paper, we propose Off- off-Policy Double Variance Reduction (OPDVR), new variance reduction based algorithm for offline RI. Our main result shows that OPDVR provably identifies an e-optimal policy with D(1I//dm,e episodes of offline data in the finite-horizon stationary transition setting, where H the horizon length and dm is the minimal marginal state- action distribution induced by the behavior policy. This improves over the best known upper bound by a factor of H. Moreover, we establish an information- theoretic lower bound of 22(H2/dmm to logarithmic factors. Lastly, we show that OPDVR also achieves rate-optimal sample complexity under alternative settings such as the finite-horizon MDPs with non-stationary transitions and the infinite horizon MDPs with discounted rewards.
which certifies that OPDVR is optimal up
Introduction
Offline reinforcement learning (offline RL) aims at learning the near-optimal policy by using a static offline dataset that is collected by certain behavior policy [Lange et al., 2012]. As offline RL agent has no access to interact with the environment, is more widely applicable to problems where online interaction is infeasible, e.g. when trials-and-errors are expensive (robotics, education), risky (autonomous driving) or even unethical (healthcare) [see,e.g., a recent survey Levine et al., 2020).
Despite its practical significance, precise theoretical understanding of offline RL has been lacking. Previous sample complexity bounds for RL has primarily focused on the online setting [Azar et al.. 2017, Jin et al., 2018, Zanette and Brunskill, 2019, Simchowitz and Jamieson, 2019, Efroni et al., 2019, Cai et al., 2019] or the generative model (simulator) setting [Azar et al., 2013, Sidford et al., 2018a,b, Yang and Wang, 2019, Agarwal et al., 2020, Wainwright, 2019, Lattimore and Szepesvari, 2019], both of which assuming interactive access the environment and not applicable to offline RL. On the other hand, the sample complexity of offline RL remains unsettled even for environments with finitely many state and actions, a.k.a, the tabular MDPs (Markov Decision Processes). One major line of work is concerned with the off-policy evaluation (OPE) problem [Li et al., 2015, Jiang and Li, 2016, Liu et al., 2018, Kallus and Uehara, 2019a.b, Uehara and Jiang, 2019, Xie et al., 2019, Yin and Wang, 2020, Duan and Wang. 2020]. These works provide sample complexity bounds for evaluating the performance a fixed policy, and do not imply guarantees for policy optimization. Another line of work studies the sample complexity of offline policy optimization in conjunction with function
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Table 1: Comparison of sample complexities for tabular offline RL interpretation.
Methou//mallsis
Setting
Assumptions
Sample complexity
BFVT [Xie and Jiang, 2020a]
oc-horizon
only realizubility
+ MDP
- 0(11-)) -00))))
concentrubility"
MBS-PIQQ [Liu et al., 2020b]
oc-horizon
completeness bounded den-
Ōi(1- D(L1-))-03/6) -02/60)
sity estimation crror
Le et al. [2019]
oc-horizon
Full Concentrability
Ō((1 7) (8/(2)
FQI [Chen and Jiung. 2019]
oc-horizon
Full Concentrability
Õ(11 7) -0/6))
MSBO/MABO [Xie Jiang, 2020b]
oc-horizon
Full Concentrability
0(11 - 7) Cn((e)
OPEMA [Yin et al., 2021]
H- -o-oorzoon non-stationary
Full Concentrabilitt
(d
OPDVR (Section 3)
H H-horizon non-stationary
Weak Coverage
OPDVR (Section 4)
H -oorrrzonn stationary
Weak Coverage
(d O(11 9
OPDVR (Section 4.2)
oc-horizon
Weak Coverage
Number of episodes in finite horizon setting and number steps in infinite horizon. Su. C, Cj., 1/dm are the concentrability-yye coefficients that measure the state-action coverage. See Assumption 2.1 and also Section F.2 for discussions.
approximation [Chen and Jiang, 2019, Xie and Jiang, 2020b,a, Jin et al., 2020]. These results apply to offline RL with general function classes, but when specialized the tabular setting, they give rather loose sample complexity bounds with suboptimal dependencies on various parameters
The recent work of Yin et al. [2021] showed that the optimal sample complexity for finding an e-optimal policy in offline RL is 0(11//mm+ in the finite-horizon non-staationarssetinng (with matching upper and lower bounds), where H is the horizon length and d, is a constant related to the data coverage of the behavior policy in the given MDP. However, the optimal sample complexity in alternative settings such as stationary transition or infinite- horizoo settings remains unknown. Further, the Õ(1²/ / sample complexity is achieved by an off- evaluation + uniform convergence type algorithm; other more practical algorithms including (stochastic) optimal planning algorithms such Q-Learning not well understood in offline RL.
Our Contributions In this paper, we propose an algorithm OPDVR (Off-Policy Doubled Variance Reduction) for offline reinforcement learning based on an extension of the variance reduction technique initiated in [Sidford et al., 201 8a, Yang and Wang, 2019]. OPDVR performs stochastic (minibatch style) value iterations using the available offline data, and can be seen as version of stochastic optimal planning that interpolates value iteration and Q-learning. Our main contributions summarized as follows.
We show that OPDVR finds an e-optimal policy with high probability using Õ(H² /dm episodes of offline data (Section 4.1). This improves upon the best known sample complexity by an H factor and to the best of our knowledge is the first that achieves an (HH2 horizon dependence, thus separating the stationary case with the non-stationary case for offline RL. We establish sample (episode) complexity lower bound 9(H² /dm==) for offline RL in the finite-horizon stationary setting (Theorem 4.2), showing that the sample complexity of OPDVR optimal up to logarithmic factors.
In the finite-horizon non-stationary setting, and infinite horizon 7-discounted setting, we show that OPDVR achieves Õ(H²) /dm=²) sample (episode) complexity (Section 3) and ((117)~~/d =m) sample complexity (Section 4.2) respectively. They are both optimal up result improves over the best known results, e.g., those derived for the fitted Q-iteration style algorithms [Xie and Jiang, 2020b]
to logarithmic factors and our
On the technical end, our algorithm presents a sharp analysis of offline RI. with stationary transitions, and, importantly, the use of the doubling technique to resolve the initialization dependence defect which fails to make the original variance reduction algorithm of [Sidford et al., 20] to be optimal, see Appendix E.4. Running [Sidford et al., 201 2018a] may not yield the desired accuracy they stated and our result is robust in preserving the optimality.
Related work. There is large and growing body of work on the theory of offline RL and RL in general. We could not hope provide a comprehensive survey, thus will instead highlight the few
'See Table for clear comparison.

---

prior work that we depend upon on the technical level. The variance reduction techniques that we use in this paper builds upon the work of [Sidford al., 2018a] in the generative model setting, though it is nontrivial in adapting their techniques to the offline setting; and our two-stage variance reduction appears essential for obtaining optimal rate for < > (see Section and Appendix F.4 for more detailed discussions). We also used fictitious estimator technique that originates from the OPE literature[Xie et al., 2019, Yin and Wang. 2020], but extended it to the coationary-transittin case, and to the policy optimization problem. As we mentioned earlier, the optimal sample complexity in offline RL in the tabular MDPs with stationary transitions was not settled. The result of [Yin et al., 2021] is optimal in the non-stationary case, but is suboptimal by factor of H in the stationary case. Our lower bound is a variant of the construction of [Yin et al., 2021] that applies to the stationary case. Other existing work on offline RL has even weaker parameters (sometimes due to their setting being more general, see details in Table 1). We defer more detailed discussion related to the OPE literature and online / generative model literature Appendix A due to space constraint.
2 Preliminaries
We consider reinforcement learning problems modeled by finite Markov Decision Processes (MDPs) (we focus on the finite-horizon episodic setting, and defer the infinite-horizonn discounted setting to Section 4.2.) An MDP is denoted by tuple M = (S, A. r. d1 H), where S and A are the state and action spaces with finite cardinality |S] = S and |A| = A. Pt : S x A x S - [0, 1] is the transition kernel with (s''ss, a) be the probability of entering state s' after taking action at state 8. We consider both the stationary and non-stationary transition setting: The stationary transition setting assumes P: = P is identical for all / E [H]. and the non-stationary transition setting allows P, to be different for different L. rt : S A - [0, 1] is the reward function which we assume to be deterministic".. dj is the initial state distribution, and H is the time horizon. A (non-stationary) policy π.: : S + I assigns to each state 8, E S a distribution over actions at each time t. We use df (s, a) or di to denote the marginal state-action/state distribution induced by policy at time t, Le. (s) := (s = s) and d7 (s) == Pr (s+ = 8, a = a).
Q-value and Bellman operator. For any policy and any fixed time t, the value func- tion (.) E R and Q-value function O7 (-.-) E R Vs, a is defined as: ()) E [-
E [ T = ..
= s.a]. For the ease of exposition, we always
enumerate Q" as column vector and similarly for Pr(-(s,a). Moreover, for any vector Q e RSxA, the induced value vector and policy is defined in the greedy way: Vs, E S, (s(ss) = maxa,cA Q(st, dt), mQ(s)) argmax,, Q(st, Given an MDP, for any vector V R and any deterministic policy n, Vt e [H] the Bellman operator T." RS + RS is defined as: (TE (s) == (s)) + P. ( and the corresponding Bellman optimality operator Te : R + R.S (s) == max.e a) + P. (-|s, V). Lastly, for a given value func- tion V,, we define backup function (=))),)) == P (1)s,,,,) Ve+1 and the one-step variance as (s,,, 0x) = Var.. [V++ 0r)-
Offline learning problem. In this paper we investigate the offline learning problem, where we do not have interactive access to the MDP, and can only observe a static dataset D ((s)) : of .r
ME(M]
KE[N] .e assume that D is obtained by executing a pre-specified behav-
ior policy 1e (also known as the logging policy) for n episodes and collecting the trajectories
7(0) (s)8) , .ri , &H TH 8 H8H1)) where each episode is rendered in the form:
(1) (0)
(0) (8) (2) (6)
(1) di, at ( pe((1s)))
(0) ), Tt.
(1) -(ss() a, (.).), and $141 P:(-]s)" (6) a..)). Given the dataset
(t)
(4)
81
D. our goal is to find an e-optimal policy Teut, in the sense that || - -VTT"" <.
Assumption on data coverage Due to the curse of distributional shift, efficient offline RL is only possible under certain data coverage properties for the behavior policy μ. Throughout this paper we assume the following:
Assumption 2.1 (Weak coverage). The behavior policy μ satisfies the following: There exists some optimal policy π² such that di (se, av) ) > 0 if there exists 1. < 1' such that oi (se, or St. 0z) > O, where di (sy, / at) is the conditional multi-step step transition probability from step t to t'.
Thhis is commonly assumed in the RL literature. The randomness in the reward will only cause a lower order error (than the randomness in the transition) for learning.
3

---

Intuitively, Assumption 2.1 requires μ to "cover" certain optimal policy π², in the sense that any Sp, Og is reachable by μ if attainable from a previous state-action pair by x². It is similar to [Liu et al., 2019, Assumption 1J. Note that this is weaker than the standard "concentrability" assumption [Munos, 2003, Le et al., 2019, Chen and Jiang, 2019]: Concentrability defines 8, == || ddd (s)) /dd dd (st, d2)l < co (cf. [Le et al., 2019, Assumption 1 & Example 4.1 which requires the sufficient exploration for tabular case' since we optimize over all policies (see Section F22 for a discussion). In contrast, our assumption only requires μ to "trace" one single optimal policy.*
suPxen
With Assumption 2.1, we define
dm := min (st, 0e) : (sc, a1) > 0}, 1,6,.
which is decided by the behavior policy j and is required by offline learning (see Theorem G.2 in Yin et al. [2021]) In general, dm is unknown yet we assume dm is known for the moment and will utilize dm in our algorithms. Indeed, in Lemma 5.1, we show that estimating dm up to multiplicative factor only requires ((1/dm) episodes of offline data; replacing the exact dm with this estimator suffices for our purpose and, importantly, will not affect our downstream sample complexities.
3 Variance reduction for offline RL
In this section, we introduce our main algorithm Off-Policy Double Variance Reduction (OPDVR), and present its theoretical guarantee in the finite-horizion non-stationary setting.
3.1 Review: variance reduction for RL
We begin by briefly reviewing the variance reduction algorithm for online reinforcement learning, where we have the interactive access to the environment.
Variance reduction (VR) initially emerged as technique for obtaining fast convergence in large scale optimization problems, for example in the Stochastic Variance Reduction Gradient method (SVRG, [Johnson and Zhang, 2013, Zhang et al., 2013]). This technique is later brought into reinforcement learning for handling policy evaluation [Du et al., 2017] and policy optimization problems [Sidford et al., 2018b,a, Yang and Wang, 2019, Wainwright, 2019, Sidford et al., 2020, Li et al., 2020, Zhang et al., 2020].
In the case of policy optimization, VR is an algorithm that approximately iterating the Bellman optimality equation, using an inner loop that performs an approximate value (or Q-value) iteration using fresh interactive data to estimate V*, and outer loop that performs multiple steps of such iterations to refine the estimates. Concretely,
obtain an reliable Qe a) for some step E [H)
by the Bellman equation (s a) = r(s, a) + P. (-Is, als,.))V=s V we need to estimate P, (1)8, a)++1 with sufficient accuracy. VR handles this by decomposing:
P. (-Is, V)4 = P, a),,4)(V41+ - v/ + P. (-Is,
(2)
where Vin is reference value function obtained from previous calculation (See line 4,13 in the inner loop of Algorithm 1) and P. (V - 1) PT (-Is, V) are estimated separately at different stages. This technique can help in reducing the "effective variance" along the learning process (see Wainwright [2019] Section 2 for discussion).
In addition, in order translate the guarantees from learning values to learning policies", we build on the following "monotonicity property": : For any policy π that satisfies the monotonicity condition Vi S Tax V141 for all t E [H] the performance of æ is sandwiched as Vn S V," < V,,,, i.e. w is guaranteed to perform the same or better than Vz. This property is first captured by [Sidford et al., 2018a] (for completeness we provide a proof Lemma B. I), and later reused by Yang and Wang [2019], Sidford et al. [2020] under different settings. We rely on this property in our offline setting as well for providing policy optimization guarantees.
'Noe Xie and Jiang [2020b] has tighter concentration coefficient with C₁ = max || Ma 11 but it still requires full exploration when 11 contains all policies.
"We admit that function approximation contmatiiiotttooottaaaiiiiiiiiii assumption is powerful for handling realizabil- ity/agnostic case and related concepts (e.g. inherent Bellman error) and easier to scale up to general settings.
"Note in general, direct translation of learning e-optimal value to c-optimal policy will cause additional suboptimal complexity dependency of H.

---

Algorithm 1 OPVRT: A Prototypical Off-Policy Variance Reduction Template
1: Functional input: Integer valued function R, - N. Off-policy estimator zı; in function forms that
provides lower confidence bounds (LCB) of the terms in the bootstrapped value function (2).
2: Static input: Initial value function V,()) and x.()) (which satisfy vith s [_o Vi and V:00
11+1 = 0).
scalar u(") satisfies ( 2 sup, I|V? - lbo.. Outer loop iterations K. Offline dataset
) Je-Ji- from μl as data-stream where n Σ 2 m(u .20()))2-(1)))) (1(1))) [1s,), ae iTe
3:
INNER LOOP n," .V=.==", gt. u²))
4: function QVI-VR (Di, D2 .V
5: o -Computing reference with Dr: Initialize Qi 6- 0 R.SAA for E (M
6: for L E [H] and each pair (st, ar) E x do
7: Compute an LCB of P,T (-18t, ([)s,,a)VV? 1-1 Zt (D Vin (4i1 end for
o Value Iterations with D. (
9:
10: for t= .. + H...., do
11:
Update value function: V2 max (Ve V(th)
12:
o Update policy: Vsz, if V(((t) = (se), set (e(s)) + xï (a+): clse
clst set me(e)) + (8)
13:
if 2 then
14:
o LCB of P.P (- -1- V: 9 1 (D! Ve, ,"")
15:
o Update Q function: Qi11 + r 21-1 + 91-1
16: end if
17: end for
18:
end function and Return: Vi,,.., Vu and π
19:
OUTERR LOOP
20:
for = 1, K do
(9 21: Set m + m(u(1=1)); Get D1 with size ( and D with size
#f (n(t for all t (M] from
the stream D.
22: Call ((()) (+) + QVI-VR(D,, D2, v(i1), (f-1) (6-1), 2e Be, u 1) Set () + 12/11
23: end for and Output: (*K,, x(K)
3.2 OPDVR: variance reduction for offline RL
We now explain how we design the VR algorithm in the offline setting. Even though our primary novel contribution is for the stationary case (Theorem 4.1), we begin with non-stationary setting for the ease of explaining algorithmic design. We let == log( A/8) as a short hand.
Prototypical offline VR. We first describe prototypical version of our offline VR algorithm in Algorithm 1, which we will instantiate with different parameters twice (hence the name hame"Double"" in each of the three settings of interest.
Algorithm takes estimators z, and gi that produce lower confidence bounds (LCB) of the two terms in (2) using offline data. Specifically, assume 2,, gi are both available in function forms in that they take an offline dataset (with an arbitrary size), fixed value function V441, Vit and an external scalar input u then return 9t E SxA, 21, satisfies that
2,(8e; 04) S PT a1) ge(se, at) S PP (11s,, - Vit
uniformly for all 8t. ar with high probability.
Algorithm then proceeds by taking the input offline dataset as stream of iid sampled trajectories and use an exponentially increasing-sizee batches of independent data to pass in z, and while updating the estimated Q value function by applying the Bellman backup operator except that the update is based on a conservative and variance reduced estimated values. Each inner loop iteration backs up from the last time-step and update all Q₂ for H..... 1; and each outer loop iteration passes new batch of data into the inner loop while ensuring reducing the suboptimality gap from the optimal policy by factor of each outer loop iteration, provided that the estimators z, + g: are increasingly more accurate estimates of (2) as the suboptimality gap gets smaller.
Plug-in estimators and high-confidence LCBs. The estimators 2, and ge different settings are provided in Figure 3.2. They are essentially the natural plug-in estimators of P. (-Is, (V 1) and P. (-Is, a) Viiz as well as their standard deviation by replacing Pt with P. except that we use two disjoint splits D1 and (( ,..., (....) for and g: they remain
for the three
5

---

Figure 1: The implementable "plug-in" lower confidence bound estimators Zy and ge.
Setring
8:lDs, Vis
Non-stativeary
En Mis ((1(094) 1i afllo (((erne)
2-111 ( Va (AED) (p I11
Statioary
5 Dm_ (it((10s)) "pi--aa--00 (((ss))
(i) ) (2 - "100 (390)31-00) AlA,0,
oc Ho-iiin
Enj,, viegan1)) 1pm o(4.0)
_ (V10 (*(2)) "prratnnen
11,, 8)
Setting
coloe.
Non-stationay
R4p0 E. (1 '19 (4944-mm)) (((r))))
22y8Va myy-,) ) 16V Bay
4u
Stationary
J ETh
EEL.0 A - (f(.,))
+ 22/0V (ntt.) 16V Boa
du
Xc-Horizon
2/6 Vanxx
m, I are the number of episodes in D1, D respectively. is logarithmic factor in ISSA/8 in the finite horizon case and SA/8 in the infinite horizon cases. Ragior is the number of times St, Oe appears time t in
D1; and vz' (st; az) the that for D.". In the case when Tay,, we simply output for all quantities above.
Algorithm 2 (OPDVR) Off- Policy Doubled Variance Reduction
input Offline Dataset D of size n as stream. Target accuracy e, such that the algorithm does not use up D. input Estimators zı, g in function forms, mí, m2, K1, K2.
1: o Stage 1. coarse learning: a "warm-up" procedure
2: Set v,(0)= := 0 and any policy (00), Set initial (0))= := H. Set m(u) = mi log (6g(16HS
3: Run Algorithm with m, 21, ge, v((), क 20 ,,, D and return V V/intemeelitee π
intermediatee
4: o Stage 2. fine learning: reduce error to given accuracy
5: Reset initial values v-(h_ := vyintermediate and policy x (0) == n intermediate Set ()) = V H.
6: Reset mn) by replacing vn1 with mé2 K1 with K2.
7: Run Algorithm with 2., gr, vi0), x (0)) K2, D and return V.fral, x 6mal
output V.tuall π
Boal
statistically independent. We also remark that P; is of dimension S²A, and we operates in the sparse regime where the number of observed samples could be drastically smaller than the total number of coordinates there are. In other words, P: will be sparse as most of its coordinates are O. The saving grace is that when we fix V and Viin the output space collapsed to only SA dimensional, which ensures that we have sufficient number of data points to produce accurate estimates.
A key difference from the generative model setting is that these estimators are dependent across t, thus it requires new technical steps to establish the convergence of these estimators as well as putting them together show that Algorithm works.
The doubling procedure. It turns out that Algorithm alone does not yield a tight sample complexity
guarantee, due to its suboptimal dependence the initial optimality gap (0) > sup, VVV v2 |0x (recall (9) is the initial parameter in the outer loop of Algorithm 1). This is captured in the following (for the non-stationary case):
Proposition 3.1 (Informal version of Lemma B.) Suppose e E (0, 1] is the final target accuracy. Algorithm I outputs the 6-optimal policy with episode complexity:
O(H+/dme²)
of > H: Omm))dmm²)) Of S VH.
Proposition 3.1 suggests that Algorithm may have a suboptimal sample complexity when the initial optimality gap (0)) > VH. Unfortunately, this is precisely the case for standard initializations
such as v: == o, for which we must take ())) = H. We overcome this issue by designing a two-stage doubling procedure: At stage we use Algorithm 1 to obtain Vintermediate iintermediate that are = VHe accurate; At stage 2, we then use Algorithm again with V/internediatee intermodiate as the input and further reduce the error from é' to The main take-away of this doubling procedure is that the episode complexity of both stage is only Ó(H3/ ed therefore the total sample complexity optimality is preserved. The pseudo-code of the two-stage procedure OPDVR summarized in Algorithm 2.

---

3.3 OPDVR for non-stationary transition seftings
We now state our main theoretical guarantee for OPDVR in the fmite-horizon non non-stationary transition setting.
Theorem 3.2 (OPDVR in episodic non-stationary setting.. For the H-horizon non-stationary setting. there exist universal constants c1, C22 C3 > 0 such that if we set m4 = ci H /dm for Stage 1, m/2 eg dm for Stage 2, set K1 K2 logz! /e), take gi and z, according to Figure 3.2. then OPDVR (Algorithm 2) with probability 1 1-8 outputs an e-optimal policy â provided that the number of episodes in the offline data DD exceeds (below can be readily simplified as Ô (H3 ()mme)):
eg max m'a
VH (HI)
VH
(e + log loga(
loga
Optimality of sample complexity. Theorem 3.2 shows that OPDVR algorithm find an e-optimal policy with OHH /mm=")))))))))))))))))))))) episodes of offline data. Compared with the sample complexity lower bound (2H /dm²)dmm²) for offline learning (Theorem G.2. in Yin et al. [2021]), we see that our OPDVR algorithm matches the lower bound up logarithmic factors. The same rate was achieved previously by the local uniform convergence argument of Yin et al. [2021] under stronger assumption of full data coverage.
Proof sketch of Theorem 3.2. One challenge in analyzing OPDVR is that the number of state- transition samples are random and dependent. The idea of the proof is to first construct ficti- tious versions of estimators Z₁ (or g:), that uses the empirical plug-in in formula only if the event Em, ., 1/m d'' (s1, } (or Ei,)) are true, i.e., there are sufficient number of samples 8t, at- When there aren't, we plug in the ground truth transition kernel P: instead. These fictitious estimators not implementable in practice, but they simplify the analysis and central to our ex- tension of the Variance Reduction framework previously used in the generative model setting [Sidford al., 2018a] the offline setting. The following proposition shows that practical implementations (summarized in Figure 3.2) are identical to these fictitious estimators with high probability:
Proposition 3.3 (Summary of Section B.4). Under the condition of Theorem 3.2, we have
(ElLe
U E
(EL2e J JE(())
< 8/2.
(E(K))
JE[Kg). (E(A]
8E[M
This means with probability 1 - fictitiou estimators 2,, 9c, ô are all identical to their practical versions (summarized in Figure 3.2).
By Proposition 3.3, it suffices analyze the performance of OPDVR instantiated with fictitious esti- mators (60) and (59). Theorem 3.2 then relies on analyzing the the prototypical OPDVR (Algorithm 1) with the fictitious estimators. In particular, both off-policy estimators
and gr lower confidence update to avoid over-optimism and the max operator in Vg = max( VQ. vii") helps prevent pessimism. By doing so the update V; in Algorithm I always satisfies range. The doubling procedure of Algorithm 2 then first decreases the accuracy to a coarse level é' = VHe, and further lowers it to the given accuracy e. The key technical lemma for achieving opti- mal dependence in H is Lemma G.5, which bounds the term > EE [Var[V (su+1) Iss. a..]] by (HH2) instead of the naive O(H3). The full proof of Theorem 3.2 can be found in Appendix B.
V S V which is always within valid
OPDVR for stationary transition settings
In this section, we switch gears to the stationary transition setting, in which the transition probabilities are identical at all time steps: (s a) : P(s'|ss a). We will consider both the (a) finite-horizon case where each episode is consist of H steps: and (b) the infinite-horizon case where the reward at the (-th step is discounted by 7², where 7 E (0. 1) is discount factor. These settings encompass additional challenges compared with the non-stationary case, as in theory the transition probabilities can now be estimated more accurately due to the shared information across time steps.
7

---

4.1 Finite-horizon stationary setting
We begin by considering the fimite-horizon stationary setting, As this is special case of the non- stationary setting, Theorem 3.2 implies that OPDVR achieves Õ(H3 /dm, sample complexity. However, similar as in online RL [Azar et al., 2017], this result may be potentially loose by an (()) factor, as the algorithm does not take into account the stationarity of the transitions. This motivates us to design an algorithm that better leverages the stationarity by aggregating state-action pairs across different time steps (see the second rows of the two tables in Figure 3.2).
Theorem 4.1 (Sample complexity of OPDVR in finite- horizon stationary setting). In the H H-horizon stationary transition selting, there exists universal constants e 622 C3 such that if we set mi o₂ /dm ml c211² dm for Stage 1 and set K2 = K2 = log, (VH (e),,, and take ze and ge according to Figure 3.2, then with probability 1 - 6, Practical OPDVR finds an e-optimal policy provided that the number of episodes in the offtine data D exceeds (which is of order Ô
H2
dg max mi
mla
(H)
VH
log log logz(
log2(
2
Proof sketch. Similar to the proof of the non-stationary case, we start by reducing the problem to a fictitious version that replace the pathological events that happen with low- probability with ground truth. Then the key challenge is how to analyze the stronger ficti- tious estimators that pools over steps within each roll-out. We design a martingale X, =
En Et=l (V - PT (+)s,,)) 1[sh") =s,a = a]. under the filtration Fx :=
( (i) we(k] ())ee for bounding (1 0+) S PT (+(s,, V The conditional variance sum EE Var [N Fa] Σt Ems, [of9 , .o s.a] Var [vit, (4%)1) 1 a =a.]] For stationary (t) ,0 = a, irrelevant to time l so above equals D ET- 1. .4 (9) s.a]
(ou Ga Jie(m)
case, (0) ~ P(115) (9)
ovm, (b.0) = nx,a oym (s, where t+1 is later replaced by V4 and Ei le a)] can be bounded by H² which is tight. In contrast, in non-stationary regime Pe is varying across time so we can only obtain E' Var [Xx+1 [Fe] S Raya maxi dyiu(e (8, a), which is later translated into LE
vv. (s, a)] and are of order H general. To sum, the fact that P is identical is care- fully leveraged multiple times for obtaining Õ(H² /dme?//mm?) rate. The detailed proof of Theorem 4.1 can be found in Appendix C.
Theorem 4. I encompasses our main technical contribution, as the compact data aggregation among different time steps make analyzing the estimators (61) and (62) knotty due to data-dependence (unlike the non-stationary transition setting where estimators are designed using data at specific time). In particular, need to fully exploit the property that transition P is identical across different times in pinpoint way to obtain the 22 dependence in the sample complexity bound.
Improved dependence on H. Theorem 4.1 shows that OPDVR achieves sample complexity upper bound HHH2/dm.. in the stationary setting. To the best of our knowledge, this is the first result that achieves an H2 dependence for offline RL with stationary transitions, and improves over the H dependence in either the (non-stationary) OPDVR (Theorem 3.2) or the "off-policy evaluation + uniform convergence" algorithm of Yin et al. [2021]. We exploit specific properties of OPDVR in our techniques for knocking off factor of H and there seems be no direct ways in applying the same techniques in improving the uniform convergence-style results for the stationary-transiiin setting.
Optimality of O(H2/dme))) /dm=²). We accompany Theorem 4.1 by a establishing a sample complexity lower bound for this setting, showing that our algorithm achieves the optimal dependence of all parameters up to logarithmic factors. The proof of Theorem 4.2 builds on modifying the Ö(H3 /dm=²) sample complexity lower bound in Yin et al. [2021], and can be found in Appendix E.
Theorem 4.2 (Information-theorrtie lower bound). For all 0 dm S SA let the family of problem be Man. := {(H, M) | min di (Sc, at) 2 dm
}. There exists universal con- stants Ci, C22 C.P (with H,S, 2 Ci and 0 < < 62) such that when n S scH2/dme
inf, M))( Pu,M (u* Tata 2 t) 2 p.
8

---

4.2 Infinite-horizon discounted setting
Finally, we consider the infinite-horie horizon discounted setting. The setting is slightly different to the finite horizon case as we adopt the same assumption of Chen and Jiang [2019], Xie and Jiang [2020b] that data D = {8(*) at+)) , hE|[) are i.idd off-policy pieces with (*, a) ~ d and ~ P(.|s, a). The infinite horizon-versions of OPDVR (Algorithm 3 and 4) are stated in the Appendix due the space limit.
Theorem 4.3 (Sampe complexity of OPDVR in infinite-horizon discounted setting). Consider
Algorithm 4. There are constants c,, c2 d3. such that if we set m/ = O(11 - -)- /dm mdmm ) m2
O((1 - 7) -3 //mm (see more precise expressions in Lemma D.7), K1 = 1og2(() - ()
-e) -0) K2
log2( (1-1)--1/40
R = log (1944/((111)) 7)), and choose LCB estimators z and g as in Figure 3.2.
then with probubility 1 - 5, the infinite horizon version of OPDVR (Algorithm 4) oulputs an e-oplimal
policy provided that in offline data 'D has number of samples exceeding
(1-7)-1 m²} 2 where d' == R. (log(32(1 7) - + log logo (0gg(V(1-1))1///// 1og2 1ogg(V(1-7)-)
C/ max
ml
.'' = (1
We note that for the infinite horizon case, the sample-complexity measures the number of steps, thus (1 (1-2)-- -3 is comparable the H dependence. To the best of our knowledge, Theorem 4.1 and Theorem 4.3 are the first results that achieve H², (1 - -) dependence in the offline regime respectively for stationary transition and infinite horizon setting, see Table 1.
Discussions
Estimating dm- It is worth mentioning that the input of OPDVR depends on unknown system quantity dm- Nevertheless, dm is only one-dimensional scalar and thus it is plausible (from a statistical perspective) leverage standard 2006]) for obtaining a reliable estimate in practice. On the theoretical side, we provide the following result to show plug-in on-policy estimator d' (st, dz) R,,,,,, and dm mina, (Ma /n. Taspa > 0}, is sufficient for accurately estimating d' dm simultaneously.
cauumeeer-tuinng tools (e.g. cross validation [Varma and Simon,
Lemma 5.1. For the finite-horizon setting (either stationary or non-stationary), there exists universal constant c, s.t. when n 2 e- 1/dm log H A/5), then w.p. 6, we have Vt., St, at 2dt (st,at) S 3 d See Appendix F. for the proof. Zi (st, ax) S d (8t: 0z) and, in particular, _dm S dm S
Lemma 5.1 ensures one can replace d'' by di (dm by d in OPDVR and we obtain a fully data- adaptive algorithm. Note that the requirement n does not affect our near-minimax complexity bound in either Theorem 3.2 and we only require x ((1/dm) additional episodes to estimate dm and it of lower order compared to our upper bound Õ(H²3) /dm) or ((H²
Computational and memory cost. OPDVR can be implemented as a streaming algorithm that uses only one pass of the dataset. Its computational cost is /dme?? - the same as its sample complexity in steps (H steps an episode), and the memory cost (HSA)) for the episodic case and ((SA) for the stationary or infinite horizon case. In particular, the double variance reduction technique does not introduce additional overhead beyond constant factors.
Improvement over VR in the generative model setting. This work extends of the variance reduc- tion framework for RL in the generative model setting [Sidford et al., 2018a, Yang and Wang, 2019]. However, we make two improvements to these works. First, the data collected in the offline case are highly dependent (in contrast in the generative model setting each simulator call is independent). and disentangling the dependent structure makes the offline setting inherently more challenging. Second, doubling mechanism always guarantee the minimax rate with any initialization and the single VR procedure does not have this property (see Appendix F.4 for more detailed discussion), which could be a critical issue when Sidford et al. [2018a] claims the optimality.
6 Conclusion
This paper proposes OPDVR (off-policy double variance reduction), a new variance reduction algorithm for offline reinforcement learning. We show that OPDVR achieves tight sample complexity

---

for offline RL in tabular MDPs; in particular, OPDVR is the first algorithm that achieves the optimal sample complexity for offline RL in the stationary transition setting. On the technical end, we present sharp analysis under stationary transitions, and use the doubling technique to resolve the initialization dependence variance reduction, both of which could be of broader interest. There are several interesting next directions. For example, can our analysis shed light on other commonly used algorithms (such as Q-Learning) for offline RL? How can we better deal with insufficient data coverage? Can we go beyond the tabular setting? We would like to leave these future work.
Acknowledgment
The authors would like to thank Lin F. Yang for the discussions about [Sidford et al., 2018a]. Ming Yin and Yu-Xiang Wang partially supported by NSF Awards #2007117 and #2003257. Yu Bai is partly funded through the employment with Salesforce.
References
Alckh Agarwal, Nan Jiang, and Sham M Kakade. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 2019.
Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with a generative model is minimax optimal. In Conference on Learning Theory, pages 67-83. PMLR, 2020.
András Antos, Csaba Szepesvári, and Rémi Munos. Fitted q-iteration in continuous action-space mdps. In Advances in neural information processing systems, pages 9-16, 2008a.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71 (1):89-129, 2008b.
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.
Mohammad Gheshlaghi Azar, lan Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In Proceedings the 34th International Conference on Machine Learning Volume 70, pages 263-272. JMLR. org, 2017.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimiza- tion. arXiv preprini arXiv:
2019.
Jinglin Chen and Nan Jiang. inoommtiiontthoreelie considerations in batch reinforcement learning. arXiv preprini arXiv: 1905. 9905000660 2019.
Herman Chernoff et al. measure of asymptotic efficiency for tests hypothesis based on the sum of observations. The Annals of Mathematical Statistics, 23(4):493-507, 1952.
Fan Chung and Linyun Lu. Concentration inequalities and martingale inequalities: a survey, Internet Mathematics, 3(1):79-127, 2006.
Christoph Dann and Emma Brunskill. Sample complexity of episodic fxed-horizon reinforcement learning. Advances in Neural Information Processing Systems, pages 2818-2826, 2015.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accontaablc reinforcement learning. arXiv preprint arXiv: / 1.00066, 2018.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic reinforce- ment learning in finite mdps: Minimax lower bounds revisited. arXiv preprint arXiv:2010.03531, 2020.
Simon S Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 1049-1058. JMLR. org, 2017.
10

---

Yaqi Duan and Mengdi Wang. Minimax Minimax-optimal off aff--policy evaluation with linear function approxi- mation, arXiv preprint 1XXi:2002.009566, 2020.
Yonathan Efroni, Nadav Merlis, Mohammad Ghavamzadeh, and Shie Mannor. Tight regret bounds for model-based reinforcement learning with greedy policies. In Advances in Neural Information Processing Systems, pages 12203-12213 2019.
Yihao Feng. Tongzheng Ren, Ziyang Tang, and Qiang Liu. Accountable off-policy evaluation with kernel bellman statistics. In International Conference on Machine Learning, pages 3102-3111. PMLR, 2020.
Nan Jiang and Lihong Li. Doubly robust off off-policy value evaluation for reinforcement learning. In Proceedings of the 33rd International Conference on International Conference on Machine Learning-Volen Volume 48. pages 652-661. JMLR. org. 2016.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Con- textual decision processes with low bellman rank are pac-learnable. In Proceedings of the 34th International Conference on Machine Learning-Voluce 70, pages 1704-1713. JMLR. org, 2017.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably efficient? In Advances in Neural Information Processing Systems, pages 4863-4873 2018
Ying Jin, Zhuoran Yang, and Zhaoran Wang. pessimism provably efficient for offline rl? arXiv preprint 2tti::20022.508... 2020.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in neural information processing systems, pages 315-323, 2013.
Nathan Kallus and Masatoshi Uehara. Double reinforcement learning for efficient off off-policy evalua- tion in markov decision processes, arXiv preprint arXiv: 1908. 08526, 2019a.
Nathan Kallus and Masatoshi Uehara. Efficiently breaking the curse of horizon: Double reinforcement learning in infinite-horizon processes. arXiv preprint arXiv:1909.0558 2019b.
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations. In Advances in Neural Information Processing Systems, pages 1448-188,, 2016.
Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In Reinforcement learning, pages 45-73. Springer, 2012.
Tor Lattimore and Csaba Szepesvari. Learning with good feature representations in bandits and in rl with a generative model. arXiv preprint arXiv: 1911.0777 2019.
Hoang M Le. Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. arXiv 2019.
preprint
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems, arXiv preprint arXiv:2005.01643, 2020.
Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Sample complexity of asynchronous q-learning: Sharper analysis and variance reduction. arXiv preprint arXiv:2006.0304/ 2020.
Lihong Li, Rémi Munos, and Csaba Szepesvári. Toward minimax off-policy value estimation. 2015.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite- horizon off aff-policy estimation. Advances in Neural Information Processing Systems, pages 5361-5371, 2018.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Off-policy policy gradient with state distribution correction. In Uncertainty in Artificial Intelligence, 2019.
Yao Liu, Pierre-Luc Bacon, and Emma Brunskill. Understanding the curse of horizon in off-polic, evaluation via conditional importance sampling. In International Conference on Machine Learning, pages 6184-6193, PMLR, 2020a.

---

Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch reinforce- ment learning without great exploration. arXiv preprint arXiv:2007.08202, 2020b.
Rémi Munos. Error bounds for approximate policy iteration. In ICML, volume 3, pages 560-567, 2003.
Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving markov decision processes with a generative model. In Advances in Neural Information Processing Systems, pages 51 5186-5196, 2018a.
Aaron Sidford, Mengdi Wang. Xian Wu, and Yinyu Ye. Variance reduced value iteration and faster algorithms for solving markov decision processes. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 770-787, SIAM, 2018b.
Aaron Sidford, Mengdi Wang, Lin Yang, and Yinyu Ye. Solving discounted stochastic two-player games with near-optimal time and sample complexity. In International Conference on Artificial intelligence and Statistics, pages 2992-3002 PMLR, 2020.
Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. In Advances Neural Information Processing Systems, pages 1151-1160, 2019.
Joel Tropp et al. Freedman's 's inequality for matrix martingales. Electronic Communications in Probability, 16:262-270, 2011.
Masatoshi Uehara and Nan Jiang. Minimax weight and q-function learning for off-policy evaluation. arXiv preprint arXiv: /2809, 2019.
Sudhir Varma and Richard Simon. Bias in error estimation when using cross-validation for model selection. BMC bioinformatics, 7(1):91, 2006.
Martin J Wainwright. Variance-reduced q-learning is minimax optimal. arXiv preprint
arXiv: 04697, 2019.
Ruosong Wang, Dean P Foster, and Sham M Kakade, What are the statistical limits of offline rl with linear function approximation? arXiv preprint arXiv:2010.11895, 2020.
Tengyang Xie and Nan Jiang. Batch falue-function approximation with only realizability. arXiv preprint arXiv:2008. 200,:2008.049900, 2020a.
Tengyang Xie and Nan Jiang. Qa approximation schemes for batch reinforcement learning: A theoretical comparison. arXiv preprint arXiv:2003.03924 2020b.
Tengyang Xie, Yifei Ma, and Yu-Xiang. Wang. Towards optimal off-policy evaluation for rein- forcement learning with marginalized importance sampling. In Advances in Neural Information Processing Systems, 2019.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004, 2019.
Ming Yin and Yu-Xiang Wang. Asymptotically efficient off-policy evaluation for tabular reinforce- ment learning. In AISTATS-20, 2020.
Ming Yin, Yu Bai, and Xiani Wang. Near optimal provable uniform convergence in off-policy evaluation for reinforeement learning. In AISTATS-21, 21, 2021.
Andrea Zanette. Exponential lower bounds for batch reinforcement learning: Batch rl can be exponentially harder than online rl. arXiv preprint arXiv:20/2.080005 2020.
Andrea Zanette and Emma Brunskill. Tighter learning without domain knowledge using value function bounds, arXiv preprint 190.v01901.002100 2019.
regret bounds in reinforcement
Lijun Zhang, Mehrdad Mahdavi, and Rong Jin. Linear convergence with condition number indepen- dent access of full gradients. Advances in Neural Information Processing Systems, 26:980-988, 2013.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via aavaatag decomposition. arXiv preprint arXiv:2004.10019, 2020.
12


Reviews:
[{"review_id": "X7hYGdtSBQ_", "reviewer": "Reviewer_yHp3", "summary": "The paper focuses on the theoretical understanding of offline reinforcement learning. Assuming weak coverage (Assumption 2.1), which appears to be necessary, the authors propose a double variance deduction learning algorithm. The algorithm has two key components: variance reduction (Eq. (2)) that decompose the key estimation of P_t(\\cdot|s,a)V_{t+1} into two components that are estimated separately at different stages; and doubling where parameters are instantiated twice. The authors show strong theoretical results of the proposed algorithm: (new) order-optimal sample complexity for the stationary case, order optimal results for the finite-horizon non-stationary setting and improved results for the infinite horizon discounted setting.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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 paper is well written. Although highly theoretical, the paper presents clear structure and intuition to facilitate its understanding.  \n\nThe work is a bit outside my area of expertise. While I understood the ideas in the paper, I was not able to fully follow its analysis. The results look good to me with sufficient novelty and technical depth. However, I will yield to reviewers with better expertise in this area. \n\nI understand that the paper is theoretical in nature and such papers often do not have numerical evaluations. Still, I wonder about the empirical performance and implications of the proposed algorithm. After all, one purpose of theoretical work is to inspire practitioners to develop useful algorithms in practice. Therefore, it would be desirable to see some numerical evaluations of the proposed algorithm, as well as the comparisons with existing algorithms. \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I would like to suggest some discussions on the practical implications of the proposed algorithm. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "UJdXoVW9jCF", "reviewer": "Reviewer_9aNL", "summary": "The papers presents an algorithms called OPDVR (Off-Policy Double Variance Reduction) based on variance reduction, which is seemingly designed with offline RL in mind, even though the main attribute of offline RL (data constraint and lack of support) is fully missed. The paper contains several theoretical results; their core contribution (among others) is for the stationary case, where transition probabilities are not function of time. They basically present a sample complexity that grows with $H^2$, an improvement over previous results by a factor of $H$. The authors provide similar result for the infinite-horizon (discounted) case as well, and expand their findings for the non-stationary case too. \n\nMain weakness: While this paper is a nice theoretical contribution, discussions on the \"practical\" impact of the basic assumptions, and how they can be relaxed to become useful in real-world, are missing, [see the comments below]. ", "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 data coverage assumption, even though it is less strong than others in the literature, is still non-realistic. It must be remarked that in practice (where offline RL matters and indeed aims for), data is given; hence, any assumption about data is meaningless. As a matter of course, in almost all the problems that I know as someone who has been involved in real-world offline RL, only a tiny fraction of the state-action joint space is covered by the data. While I appreciate an interesting theoretical work like the results of this paper, the authors must note that the first step to make something useful in the offline RL literature is to set aside coverage assumptions. Note also that when dealing with situations under data constraints (which should be the definition of offline RL), optimality is no longer a concern, since we know it in advance that it is not feasible; yet in many domains of interest (like healthcare) even small data still contains valuable information and must be used. My strong recommendation always is to focus on how to use limited information in such data, if you hope that your algorithm goes beyond interesting mathematical proofs. \n\n-- Line 157-160: A policy that satisfies monotonicity condition -> this needs explanation and example. In particular, if you are given an offline fixed data, how likely is this assumption to hold? Without such intuitions the results can easily become misleading.\n\n-- No experimental result is given. Most importantly, you need to justify why someone should care about improving sample complexity by a factor of $H$. As a suggestion, you may start with some fixed dataset and shrink its size in a few stages by randomly removing trajectories from the dataset. And, show the final/best performance of your algorithm against others. Also note that in fixed data scenarios, convergence rate is not a concern for offline RL, almost always.\n\nMinor: Line 87: in the definition of MDP, T is used for transition probability, but replaced by P right after. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "A theoretical work; no direct societal impact. ", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "S9-kmCLpBkF", "reviewer": "Reviewer_YWeJ", "summary": "This paper considers a variance-reduced Q learning algorithm for offline policy optimization, and shows that the proposed algorithm is minimax-optimal up to logarithmic factors.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors extend the variance reduction technique from the generative model to offline scenarios, and achieve sharp error bound on finite horizon homogeneous, finite horizon inhomogeneous and infinite horizon setting. The results are technically sound. I have some minor concerns on the significance of the paper. I want to remark that, such doubling procedure have already been introduced in [1], see Section 3.4 of the corresponding paper. Meanwhile, as the authors point out, in the offline scenarios, the data are highly dependent which leads to additional technical difficulties. However, if I understand correctly, what the author do is only sampling sufficient episodes to guarantee each state-action pair has sufficient number of data with high probability, then we can follow the analysis of the generative model setting. I think the authors should make this difference between generative model setting more clear, if there are some other technical efforts to deal with this issue. Furthermore, I have a question regarding the range of $\\epsilon$, as in [1], the results only hold when the number of data exceeds certain threshold, which means the result can only hold for $\\epsilon \\in (0, 1]$. Does the same issue come here? I think the authors better make some discussions on that.\n\n[1] Martin J Wainwright. Variance-reduced q-learning is minimax optimal. arXiv preprint arXiv:1906.04697, 2019. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have properly discussed them.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The submission proposes OPDVR for offline policy optimization, and sample complexities for finite-horizon case and discounted infinite-horizon case are presented. Though some concerns on the pratical side are proposed, all reviewers agree that the paper has a great theoretical contribution. Thus I recommend accept, and also encourage the authors to have some pratical results in the camera ready version. 
Decision: Accept (Poster)