Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
Year: 2021

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 tabular Markov Decision Processes (MDPs). In this paper, we propose Off-Policy Double Variance Reduction (OPDVR), a new variance reduction based algorithm for offline RL. Our main result shows that OPDVR provably identifies an -optimal policy with Õ(H/dm ) episodes of offline data in the finite-horizon stationary transition setting, where H is the horizon length and dm is the minimal marginal stateaction distribution induced by the behavior policy. This improves over the best known upper bound by a factor of H . Moreover, we establish an informationtheoretic lower bound of Ω(H/dm ) 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.

text: 2) episodes of offline data in the finite-horizon stationary transition setting, where H is the horizon length and dm is the minimal marginal stateaction distribution induced by the behavior policy. This improves over the best known upper bound by a factor of H . Moreover, we establish an informationtheoretic lower bound of Ω(H2/dm 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.

heading: 1 Introduction
text: Offline reinforcement learning (offline RL) aims at learning the near-optimal policy by using a static offline dataset that is collected by a certain behavior policy µ [Lange et al., 2012]. As offline RL agent has no access to interact with the environment, it 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, a 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 to 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 of 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 (NeurIPS 2021).
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 to the tabular setting, they give rather loose sample complexity bounds with suboptimal dependencies on various parameters 1.
The recent work of Yin et al. [2021] showed that the optimal sample complexity for finding an -optimal policy in offline RL is Õ(H3/dm 2) in the finite-horizon non-stationarysetting (with matching upper and lower bounds), where H is the horizon length and dm 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-horizon settings remains unknown. Further, the Õ(H3/dm 2) sample complexity is achieved by an off-policy evaluation + uniform convergence type algorithm; other more practical algorithms including (stochastic) optimal planning algorithms such as Q-Learning are 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., 2018a, Yang and Wang, 2019]. OPDVR performs stochastic (minibatch style) value iterations using the available offline data, and can be seen as a version of stochastic optimal planning that interpolates value iteration and Q-learning. Our main contributions are summarized as follows.
• We show that OPDVR finds an -optimal policy with high probability using Õ(H2/dm 2) 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 O(H2) horizon dependence, thus separating the stationary case with the non-stationary case for offline RL.
• We establish a sample (episode) complexity lower bound Ω(H2/dm 2) for offline RL in the finite-horizon stationary setting (Theorem 4.2), showing that the sample complexity of OPDVR is optimal up to logarithmic factors. • In the finite-horizon non-stationary setting, and infinite horizon γ-discounted setting, we
show that OPDVR achieves Õ(H3/dm 2) sample (episode) complexity (Section 3) and Õ((1−γ)−3/dm 2) sample complexity (Section 4.2) respectively. They are both optimal up to logarithmic factors and our infinite-horizon result improves over the best known results, e.g., those derived for the fitted Q-iteration style algorithms [Xie and Jiang, 2020b].
• On the technical end, our algorithm presents a sharp analysis of offline RL 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., 2018a] to be optimal, see Appendix F.4. Running [Sidford et al., 2018a] may not yield the desired accuracy as they stated and our result is robust in preserving the optimality.
Related work. There is a large and growing body of work on the theory of offline RL and RL in general. We could not hope to provide a comprehensive survey, thus will instead highlight the few
1See Table 1 for a 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 et 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 > 1 (see Section 5 and Appendix F.4 for more detailed discussions). We also used a fictitious estimator technique that originates from the OPE literature[Xie et al., 2019, Yin and Wang, 2020], but extended it to the stationary-transition 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 a 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 RL / generative model literature to Appendix A due to space constraint.

heading: 2 Preliminaries
text: We consider reinforcement learning problems modeled by finite Markov Decision Processes (MDPs) (we focus on the finite-horizon episodic setting, and defer the infinite-horizon discounted setting to Section 4.2.) An MDP is denoted by a tuple M = (S,A, r, T, d1, H), where S and A are the state and action spaces with finite cardinality |S| = S and |A| = A. Pt : S × A × S → [0, 1] is the transition kernel with Pt(s′|s, a) be the probability of entering state s′ after taking action a at state s. We consider both the stationary and non-stationary transition setting: The stationary transition setting assumes Pt ≡ P is identical for all t ∈ [H], and the non-stationary transition setting allows Pt to be different for different t. rt : S × A → [0, 1] is the reward function which we assume to be deterministic2. d1 is the initial state distribution, and H is the time horizon. A (non-stationary) policy π : S → PHA assigns to each state st ∈ S a distribution over actions at each time t. We use dπt (s, a) or d π t (s) to denote the marginal state-action/state distribution induced by policy π at time t, i.e. dπt (s) := Pπ(st = s) and dπt (s, a) := Pπ(st = s, at = a). Q-value and Bellman operator. For any policy π and any fixed time t, the value function V πt (·) ∈ RS and Q-value function Qπt (·, ·) ∈ RS×A, ∀s, a is defined as: V πt (s) = E [∑H
i=t ri ∣∣∣st = s] , Qπt (s, a) = E [∑Hi=t ri∣∣∣st, at = s, a] . For the ease of exposition, we always enumerate Qπ as a column vector and similarly for Pt(·|s, a). Moreover, for any vector Q ∈ RS×A, the induced value vector and policy is defined in the greedy way: ∀st ∈ S, VQ(st) = maxat∈AQ(st, at), πQ(st) = argmaxat∈AQ(st, at). Given an MDP, for any vector V ∈ R S and any deterministic policy π, ∀t ∈ [H] the Bellman operator T πt : RS → RS is defined as: [T πt (V )](s) := r(s, πt(s)) + P>t (·|s, πt(s))V , and the corresponding Bellman optimality operator Tt : RS → RS , [Tt(V )](s) := maxa∈A[r(s, a) + P>t (·|s, a)V ]. Lastly, for a given value function Vt, we define backup function zt(st, at) := P>t (·|st, at)Vt+1 and the one-step variance as σVt+1(st, at) := Varst+1 [Vt+1(st+1)|st, at]. 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 (i) t , a (i) t , r (i) t , s (i) t+1) }t∈[H] i∈[n]
.We assume that D is obtained by executing a pre-specified behavior policy µ (also known as the logging policy) for n episodes and collecting the trajectories τ (i) = (s
(i) 1 , a (i) 1 , r (i) 1 , . . . , s (i) H , a (i) H , r (i) H , s (i) H+1), where each episode is rendered in the form:
s (i) 1 ∼ d1, a (i) t ∼ µt(·|s (i) t ), r (i) t = r(s (i) t , a (i) t ), and s (i) t+1 ∼ Pt(·|s (i) t , a (i) t ). Given the dataset D, our goal is to find an -optimal policy πout, in the sense that ||V π ? 1 − V πout 1 ||∞ < .
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 dµt′(st′ , at′) > 0 if there exists t < t ′ such that dπ ?
t:t′(st′ , at′ |st, at) > 0, where dπ ?
t:t′(st′ , at′ |st, at) is the conditional multi-step transition probability from step t to t′. 2This 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.
Intuitively, Assumption 2.1 requires µ to “cover” certain optimal policy π?, in the sense that any st′ , at′ is reachable by µ if it is attainable from a previous state-action pair by π?. It is similar to [Liu et al., 2019, Assumption 1]. Note that this is weaker than the standard “concentrability” assumption [Munos, 2003, Le et al., 2019, Chen and Jiang, 2019]: Concentrability defines βµ := supπ∈Π ||dπ(st, at)/dµ(st, at)||∞ <∞ (cf. [Le et al., 2019, Assumption 1 & Example 4.1]), which requires the sufficient exploration for tabular case3 since we optimize over all policies (see Section F.2 for a discussion). In contrast, our assumption only requires µ to “trace” one single optimal policy.4
With Assumption 2.1, we define dm := min
t,st,at {dµt (st, at) : d µ t (st, at) > 0}, (1)
which is decided by the behavior policy µ 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 a multiplicative factor only requires Õ(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.

heading: 3 Variance reduction for offline RL
text: 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.

heading: 3.1 Review: variance reduction for RL
text: 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 a 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 an outer loop that performs multiple steps of such iterations to refine the estimates. Concretely, to obtain an reliable Qt(s, a) for some step t ∈ [H], by the Bellman equation Qt(s, a) = r(s, a) + P>t (·|s, a)Vt+1, we need to estimate P>t (·|s, a)Vt+1 with sufficient accuracy. VR handles this by decomposing:
P>t (·|s, a)Vt+1 = P>t (·|s, a)(Vt+1 − V int+1) + P>t (·|s, a)V int+1, (2)
where V int+1 is a reference value function obtained from previous calculation (See line 4,13 in the inner loop of Algorithm 1) and P>t (·|s, a)(Vt+1 − V int+1), P>t (·|s, a)V int+1 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 a discussion).
In addition, in order to translate the guarantees from learning values to learning policies5, we build on the following “monotonicity property”: For any policy π that satisfies the monotonicity condition Vt ≤ TπtVt+1 for all t ∈ [H], the performance of π is sandwiched as Vt ≤ V πt ≤ V ?t , i.e. π is guaranteed to perform the same or better than Vt. This property is first captured by [Sidford et al., 2018a] (for completeness we provide a proof in Lemma B.1), 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.
3Note Xie and Jiang [2020b] has a tighter concentration coefficient with Cµ := maxπ∈Π ∥∥wdπ/µ∥∥22,µ but it still requires full exploration when Π contains all policies. 4We admit that function approximation+concentrability assumption is powerful for handling realizability/agnostic case and related concepts (e.g. inherent Bellman error) and easier to scale up to general settings. 5Note in general, direct translation of learning a -optimal value to -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 m : R+ → N. Off-policy estimator zt,gt in function forms that
provides lower confidence bounds (LCB) of the two terms in the bootstrapped value function (2). 2: Static input: Initial value function V (0)t and π (0) t (which satisfy V
(0) t ≤ Tπ(0)t V (0) t+1 and V (0) H+1 ≡ 0).
A scalar u(0) satisfies u(0) ≥ supt ||V ?t − V (0) t ||∞. Outer loop iterations K. Offline dataset D = {{s(i)t , a (i) t , r (i) t }Ht=1}ni=1 from µ as a data-stream where n ≥ ∑K i=1 2 ·m(u
(0) · 2−(i−1)). 3: —————————–INNER LOOP —————————- 4: function QVI-VR (D1,D(1:H)2 , V int , πin, zt,gt, uin) 5: Computing reference with D1: Initialize Qt ← 0 ∈ RS×A for t ∈ [H + 1]. 6: for t ∈ [H] and each pair (st, at) ∈ S ×A do 7: Compute an LCB of P>t (·|st, at)V int+1: zt ← zt(D1, V int+1, uin) 8: end for 9: Value Iterations with D(1:H)2 :
10: for t = H + 1, H, ..., 1 do 11: Update value function: Vt ← max(VQt , V int ). 12: Update policy: ∀st, if Vt(st) = V int (st), set πt(st)← πint (st); else set πt(st)← πQt(st). 13: if t ≥ 1 then 14: LCB of P>(·|st−1, at−1)[Vt − V int ]: gt−1 ← gt−1(D (t−1) 2 , Vt, V in t , u
in). 15: Update Q function: Qt−1 ← r + zt−1 + gt−1 16: end if 17: end for 18: end function and Return: V1, ..., VH and π 19: —————————–OUTER LOOP —————————- 20: for i = 1, ...,K do 21: Set m(i) → m(u(i−1)); Get D1 with size m(i) and D(t)2 with size m (i) H (u(i−1))2 for all t ∈ [H] from the stream D. 22: Call V (i), π(i) ← QVI-VR(D1,D2, V (i−1), π(i−1), zt,gt, u(i−1)), Set u(i) ← u(i−1)/2. 23: end for and Output: V (K), π(K)

heading: 3.2 OPDVR: variance reduction for offline RL
text: 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(HSA/δ) as a short hand.
Prototypical offline VR. We first describe a prototypical version of our offline VR algorithm in Algorithm 1, which we will instantiate with different parameters twice (hence the name“Double”) in each of the three settings of interest.
Algorithm 1 takes estimators zt and gt that produce lower confidence bounds (LCB) of the two terms in (2) using offline data. Specifically, we assume zt,gt are both available in function forms in that they take an offline dataset (with an arbitrary size), fixed value function Vt+1, V int+1 and an external scalar input u then return zt, gt ∈ RS×A. zt, gt satisfies that
zt(st, at) ≤ P>(·|st, at)V int+1, gt(st, at) ≤ P>(·|st, at)[Vt+1 − V int+1], uniformly for all st, at with high probability.
Algorithm 1 then proceeds by taking the input offline dataset as a stream of iid sampled trajectories and use an exponentially increasing-sized batches of independent data to pass in zt and gt 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 Qt for t = H, ..., 1; and each outer loop iteration passes a new batch of data into the inner loop while ensuring reducing the suboptimality gap from the optimal policy by a factor of 2 in each outer loop iteration, provided that the estimators zt + gt are increasingly more accurate estimates of (2) as the suboptimality gap gets smaller.
Plug-in estimators and high-confidence LCBs. The estimators zt and gt we use for the three different settings are provided in Figure 3.2. They are essentially the natural plug-in estimators of P>t (·|s, a)(Vt+1 − V int+1) and P>t (·|s, a)V int+1 as well as their standard deviation by replacing Pt with P̂t except that we use two disjoint splits D1 and D(1)2 , . . . ,D (H) 2 for zt and gt so they remain
∑m
∑l
∗ m, l are the number of episodes in D1,D(t)2 respectively. ι is a logarithmic factor in HSA/δ in the finite horizon case and SA/δ in the infinite horizon cases. nst,at is the number of times st, at appears at time t in D1; and n′(st, at) is the that for D(t)2 . In the case when nst,at = 0, we simply output 0 for all quantities above.
Algorithm 2 (OPDVR) Off-Policy Doubled Variance Reduction input Offline Dataset D of size n as a stream. Target accuracy , δ such that the algorithm does not use up D. input Estimators zt,gt in function forms, m′1,m′2,K1,K2. 1: Stage 1. coarse learning: a “warm-up” procedure 2: Set V (0)t := 0 and any policy π
(0). Set initial u(0) := H . Set m(u) = m′1 log(16HSAK1)/u2. 3: Run Algorithm 1 with m, zt,gt, V (0) t , π
(0), u(0),K1,D and return V intermediatet , πintermediate. 4: Stage 2. fine learning: reduce error to given accuracy 5: Reset initial values V (0)t := V intermediate t and policy π(0) := πintermediate. Set u(0) := √ H . 6: Reset m(u) by replacing m′1 with m′2, K1 with K2. 7: Run Algorithm 1 with m, zt,gt, V (0) t , π
(0), u(0),K2,D and return V finalt , πfinal. output V finalt , πfinal
statistically independent. We also remark that Pt is of dimension S2A, 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̂t will be sparse as most of its coordinates are 0. The saving grace is that when we fix Vt+1 and V int+1, 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 to show that Algorithm 1 works.
The doubling procedure. It turns out that Algorithm 1 alone does not yield a tight sample complexity guarantee, due to its suboptimal dependence on the initial optimality gap u(0) ≥ supt ‖V ?t −V (0) t ‖∞ (recall u(0) 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.10). Suppose ∈ (0, 1] is the final target accuracy. Algorithm 1 outputs the -optimal policy with episode complexity:
• Õ(H4/dm 2), If u(0) > √ H; • Õ(H3/dm 2), If u(0) ≤ √ H.
Proposition 3.1 suggests that Algorithm 1 may have a suboptimal sample complexity when the initial optimality gap u(0) > √ H . Unfortunately, this is precisely the case for standard initializations such as V (0)t := 0, for which we must take u (0) = H . We overcome this issue by designing a two-stage doubling procedure: At stage 1, we use Algorithm 1 to obtain V intermediatet , π intermediate that
are ′ = √ H accurate; At stage 2, we then use Algorithm 1 again with V intermediatet , π
intermediate 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 Õ(H3/dm 2), therefore the total sample complexity optimality is preserved. The pseudo-code of the two-stage procedure OPDVR is summarized in Algorithm 2.
3.3 OPDVR for non-stationary transition settings
We now state our main theoretical guarantee for OPDVR in the finite-horizon 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, c2, c3 > 0 such that if we set m′1 = c1H4/dm for Stage 1, m′2 = c2H 3/dm for Stage 2, set K1 = K2 = log2( √ H/ ), take gt and zt according to Figure 3.2, then OPDVR (Algorithm 2) with probability 1− δ outputs an -optimal policy π̂ provided that the number of episodes in the offline data D exceeds (below can be readily simplified as Õ ( H3/dm 2 ) ):
c3 max[ m′1 H ,m′2] 2 ( ι+ log log2( √ H ) ) log2( √ H ),
Optimality of sample complexity. Theorem 3.2 shows that our OPDVR algorithm can find an -optimal policy with Õ(H3/dm 2) episodes of offline data. Compared with the sample complexity lower bound Ω(H3/dm 2) for offline learning (Theorem G.2. in Yin et al. [2021]), we see that our OPDVR algorithm matches the lower bound up to logarithmic factors. The same rate was achieved previously by the local uniform convergence argument of Yin et al. [2021] under a stronger assumption of full data coverage.
Proof sketch of Theorem 3.2. One challenge in analyzing OPDVR is that the number of statetransition samples are random and dependent. The idea of the proof is to first construct fictitious versions of estimators zt (or gt), that uses the empirical plug-in formula only if the event Em,t = {nst,at > 12m · d µ t (st, at)} (or El,t) are true, i.e., there are sufficient number of samples at st, at. When there aren’t, we plug in the ground truth transition kernel Pt instead. These fictitious estimators are not implementable in practice, but they simplify the analysis and are central to our extension of the Variance Reduction framework previously used in the generative model setting [Sidford et al., 2018a] to 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
P [ ⋃ i∈[K1], t∈[H] ( E (i)c l,t ∪ E (i)c m,t ) ⋃ j∈[K2], t∈[H] ( E (j)c l,t ∪ E (j)c m,t )] ≤ δ/2.
This means with probability 1− δ/2, fictitious estimators z̃t, g̃t, σ̃ are all identical to their practical versions (summarized in Figure 3.2).
By Proposition 3.3, it suffices to analyze the performance of OPDVR instantiated with fictitious estimators (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 zt and gt use lower confidence update to avoid over-optimism and the max operator in Vt = max(VQt , V in t ) helps prevent pessimism. By doing so the update Vt in Algorithm 1 always satisfies 0 ≤ Vt ≤ V ?t , which is always within valid range. The doubling procedure of Algorithm 2 then first decreases the accuracy to a coarse level ′ = √ H , and further lowers it to the given accuracy . The key technical lemma for achieving opti-
mal dependence in H is Lemma G.5, which bounds the term ∑H u=t E π? su,au [Var[V ? u+1(su+1)|su, au]] by O(H2) instead of the naive O(H3). The full proof of Theorem 3.2 can be found in Appendix B.
4 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: Pt(s′|s, a) :≡ P (s′|s, 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 t-th step is discounted by γt, where γ ∈ (0, 1) is a 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.

heading: 4.1 Finite-horizon stationary setting
text: We begin by considering the finite-horizon stationary setting. As this is a special case of the nonstationary setting, Theorem 3.2 implies that OPDVR achieves Õ(H3/dm 2) sample complexity. However, similar as in online RL [Azar et al., 2017], this result may be potentially loose by an O(H) 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-horizon stationary transition setting, there exists universal constants c′1, c ′ 2, c ′ 3 such that if we set m ′ 1 = c′1H 3/dm, m′2 = c ′ 2H 2/dm for Stage 1 and 2, set K1 = K2 = log2( √ H/ ), and take zt and gt according to Figure 3.2, then with probability 1 − δ, Practical OPDVR finds an -optimal policy provided that the number of episodes in the offline data D exceeds (which is of order Õ ( H2
dm 2
) ):
c′3 max[ m′1 H ,m′2]
2
( ι+ log log2( √ H ) ) log2( √ H ),
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 lowprobability with ground truth. Then the key challenge is how to analyze the stronger fictitious estimators that pools over steps within each roll-out. We design a martingale Xk =∑m i=1 ∑k−1 u=1 ( V int+1(s (i) u+1)− P>(·|s, a)V int+1 ) · 1[s(i)u = s, a(i)u = a]. under the filtration Fk := {s(i)u , a(i)u }u∈[k]i∈[m] for bounding zt(st, at) ≤ P >(·|st, at)V int+1. The conditional variance sum∑H
k=1 Var [Xk+1 | Fk] = ∑H k=1 ∑m i=1 1 [ s (i) k , a (i) k = s, a ] Var [ V int+1 ( s (i) k+1 ) | s(i)k , a (i) k = s, a ] . For stationary
case, s(i)k+1 ∼ P (·|s (i) k , a (i) k = s, a) is irrelevant to time k so above equals ∑H k=1 ∑m i=1 1 [ s (i) k , a (i) k = s, a ] σ V in t+1 (s, a) = ns,a · σV in t+1 (s, a), where V int+1 is later replaced by V ? t+1 and ∑H t=1 Eπ ? s,a[σV ?t (s, a)] can be bounded by H2 which is tight. In contrast, in non-stationary regime Pt is varying across time so we can only obtain ∑Hk=1 Var [Xk+1 | Fk] ≤ ns,a maxt σV int (s, a), which is later translated into∑H t=1 Eπ ? s,a[maxt σV ?t (s, a)] and are of order H 3 general. To sum, the fact that P is identical is carefully leveraged multiple times for obtaining Õ(H2/dm 2) rate. The detailed proof of Theorem 4.1 can be found in Appendix C.
Theorem 4.1 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, we need to fully exploit the property that transition P is identical across different times in a pinpoint way to obtain the H2 dependence in the sample complexity bound.
Improved dependence on H . Theorem 4.1 shows that OPDVR achieves a sample complexity upper bound Õ(H2/dm 2) 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 H3 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 a factor of H and there seems to be no direct ways in applying the same techniques in improving the uniform convergence-style results for the stationary-transition setting.
Optimality of Õ(H2/dm 2). 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 Õ(H3/dm 2) sample complexity lower bound in Yin et al. [2021], and can be found in Appendix E.
Theorem 4.2 (Information-theoretic lower bound). For all 0 < dm ≤ 1SA , let the family of problem be Mdm := { (µ,M) ∣∣ mint,st,at dµt (st, at) ≥ dm}. There exists universal constants c1, c2, c, p (with H,S,A ≥ c1 and 0 < < c2) such that when n ≤ cH2/dm 2, infvπalg sup(µ,M)∈Mdm Pµ,M (v ∗ − vπalg ≥ ) ≥ p.

heading: 4.2 Infinite-horizon discounted setting
text: Finally, we consider the infinite-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 = {s(i), a(i), r(i), s′(i)}i∈[n] are i.i.d off-policy pieces with (s, a) ∼ dµ and s′ ∼ P (·|s, a). The infinite horizon-versions of OPDVR (Algorithm 3 and 4) are stated in the Appendix due to the space limit. Theorem 4.3 (Sampe complexity of OPDVR in infinite-horizon discounted setting). Consider Algorithm 4. There are constants c′1, c ′ 2, c ′ 3, such that if we set m ′ 1 = O((1 − γ)−4/dm),m′2 = O((1− γ)−3/dm) (see more precise expressions in Lemma D.7), K1 = log2((1− γ)−1/ ),K2 = log2( √ (1− γ)−1/ ) , R = log(4/ (1− γ)), and choose LCB estimators z and g as in Figure 3.2, then with probability 1− δ, the infinite horizon version of OPDVR (Algorithm 4) outputs an -optimal policy provided that in offline data D has number of samples exceeding
c′3 max[ m′1 (1−γ)−1 ,m ′ 2]
2 · ι′ = Õ [ (1− γ)−3/dm 2 ] .
where ι′ := R · (log(32(1− γ)−1RSA/δ) + log log2( √ (1− γ)−1/ )) · log2( √ (1− γ)−1/ ).
We note that for the infinite horizon case, the sample-complexity measures the number of steps, thus (1 − γ)−3 is comparable to the H2 dependence. To the best of our knowledge, Theorem 4.1 and Theorem 4.3 are the first results that achieve H2, (1− γ)−3 dependence in the offline regime respectively for stationary transition and infinite horizon setting, see Table 1.

heading: 5 Discussions
text: 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) to leverage standard parameter-tuning tools (e.g. cross validation [Varma and Simon, 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̂µt (st, at) = nst,at/n and d̂m := mint,st,at{nst,at/n : nst,at > 0}, is sufficient for accurately estimating d µ t , dm simultaneously. Lemma 5.1. For the finite-horizon setting (either stationary or non-stationary), there exists universal constant c, s.t. when n ≥ c · 1/dm · log(HSA/δ), then w.p. 1− δ, we have ∀t, st, at, 12d µ t (st, at) ≤ d̂µt (st, at) ≤ 32d µ t (st, at) and, in particular, 1 2dm ≤ d̂m ≤ 3 2dm. See Appendix F.1 for the proof.
Lemma 5.1 ensures one can replace dµt by d̂ µ t (dm by d̂m) in OPDVR and we obtain a fully dataadaptive algorithm. Note that the requirement on n does not affect our near-minimax complexity bound in either Theorem 3.2 and 4.1—we only require n ≈ Θ̃(1/dm) additional episodes to estimate dm and it is of lower order compared to our upper bound Õ(H3/dm) or Õ(H2/dm)).
Computational and memory cost. OPDVR can be implemented as a streaming algorithm that uses only one pass of the dataset. Its computational cost is Õ(H4/dm 2) — the same as its sample complexity in steps (H steps is an episode), and the memory cost is O(HSA) for the episodic case and O(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 reduction 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, our 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 a more detailed discussion), which could be a critical issue when Sidford et al. [2018a] claims the optimality.

heading: 6 Conclusion
text: 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 a sharp analysis under stationary transitions, and use the doubling technique to resolve the initialization dependence in 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 as future work.

heading: Acknowledgment
text: The authors would like to thank Lin F. Yang for the discussions about [Sidford et al., 2018a]. Ming Yin and Yu-Xiang Wang are partially supported by NSF Awards #2007117 and #2003257. Yu Bai is partly funded through the employment with Salesforce.

Review summaries:
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.   Main 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]. 

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.