Near-Optimal Offline Reinforcement Learning via Double Variance Reduction

Introduction

Offline reinforcement learning (offline RL, also known as batch RL) aims at learning the near-optimal policy by using a static offline dataset that is collected by a certain behavior policy $\mu$ (Lange et al., 2012). As offline RL agent works without needing 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; Bai et al., 2019; Zanette & Brunskill, 2019; Simchowitz & Jamieson, 2019; Efroni et al., 2019; Dann & Brunskill, 2015; Cai et al., 2019) or the generative model (simulator) setting (Azar et al., 2013; Sidford et al., 2018a, b; Yang & Wang, 2019; Agarwal et al., 2019; Wainwright, 2019; Lattimore & 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 & Li, 2016; Liu et al., 2018; Kallus & Uehara, 2019a, b; Uehara & Jiang, 2019; Xie et al., 2019; Yin & Wang, 2020; Duan & 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 approximation (Chen & Jiang, 2019; Xie & 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 See Table 1 for a clear comparison..

The recent work of Yin et al. (2021) showed that the optimal sample complexity for finding an $\epsilon$-optimal policy in offline RL is $\widetilde{O}(H^{3}/d_{m}\epsilon^{2})$ in the finite-horizon non-stationaryThis is also known as the finite-horizon time-inhomogeneous or time-varying setting, where the transition dynamics and rewards could differ by time steps. The stationary case is expected to be easier in the information-theoretical sense, but is more challenging to analyze due to the more complex dependence structure in the observed data. setting (with matching upper and lower bounds), where $H$ is the horizon length and $d_{m}$ 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 $\widetilde{O}(H^{3}/d_{m}\epsilon^{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. This motivates us to ask:

What algorithm achieves the optimal sample complexity for offline RL in tabular MDPs?

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 & 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 $\epsilon$-optimal policy with high probability using $\widetilde{O}(H^{2}/d_{m}\epsilon^{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(H^{2})$ horizon dependence offlinely, thus formally separating the stationary case with the non-stationary case for offline RL.

We establish a sample (episode) complexity lower bound $\Omega(H^{2}/d_{m}\epsilon^{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 $\gamma$-discounted setting, we show that OPDVR achieves $\widetilde{O}(H^{3}/d_{m}\epsilon^{2})$ sample (episode) complexity (Section 3) and $\widetilde{O}((1-\gamma)^{-3}/d_{m}\epsilon^{2})$ sample (step) 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 & Jiang, 2020b).

On the technical end, our algorithm presents a sharp analysis of offline RL with stationary transitions, and uses a doubling technique to resolve the initialization dependence in the original variance reduction algorithm (e.g. of (Sidford et al., 2018a)), both of which could be of broader interest.

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 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 $\epsilon>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 & 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.

Additional paper organization

We present the problem setup in Section 2, present some discussions related to our algorithm in Section 5, and conclude in Section 6. Proofs and some additional technical materials are deferred to the Appendix.

Preliminaries

1 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 $\mathcal{D}=\left\{(s^{(i)}_{t},a^{(i)}_{t},r^{(i)}_{t},s^{(i)}_{t+1})\right\}_{i\in[n]}^{t\in[H]}$.We assume that $\mathcal{D}$ is obtained by executing a pre-specified behavior policy $\mu$ (also known as the logging policy) for $n$ episodes and collecting the trajectories $\tau^{(i)}=(s_{1}^{(i)},a_{1}^{(i)},r_{1}^{(i)},\dots,s_{H}^{(i)},a_{H}^{(i)},r_{H}^{(i)},s_{H+1}^{(i)})$, where each episode is rendered in the form: $s_{1}^{(i)}\sim d_{1}$, $a_{t}^{(i)}\sim\mu_{t}(\cdot|s_{t}^{(i)})$, $r_{t}^{(i)}=r(s_{t}^{(i)},a_{t}^{(i)})$, and $s_{t+1}^{(i)}\sim P_{t}(\cdot|s_{t}^{(i)},a_{t}^{(i)})$. Given the dataset $\mathcal{D}$, our goal is to find an $\epsilon$-optimal policy $\pi_{\text{out}}$, in the sense that $||V_{1}^{\pi^{\star}}-V_{1}^{\pi_{\text{out}}}||_{\infty}<\epsilon$.

Due to the curse of distributional shift, efficient offline RL is only possible under certain data coverage properties for the behavior policy $\mu$. Throughout this paper we assume the following:

The behavior policy $\mu$ satisfies the following: There exists some optimal policy $\pi^{\star}$ such that $d_{t^{\prime}}^{\mu}(s_{t^{\prime}},a_{t^{\prime}})>0$ if there exists $t<t^{\prime}$ such that $d^{\pi^{\star}}_{t:t^{\prime}}(s_{t^{\prime}},a_{t^{\prime}}|s_{t},a_{t})>0$, where $d^{\pi^{\star}}_{t:t^{\prime}}(s_{t^{\prime}},a_{t^{\prime}}|s_{t},a_{t})$ is the conditional multi-step transition probability from step $t$ to $t^{\prime}$.

Intuitively, Assumption 2.1 requires $\mu$ to “cover” certain optimal policy $\pi^{\star}$, in the sense that any $s_{t^{\prime}},a_{t^{\prime}}$ is reachable by $\mu$ if it is attainable from a previous state-action pair by $\pi^{\star}$. 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 & Jiang, 2019): Concentrability defines $\beta_{\mu}:=\sup_{\pi\in\Pi}||d^{\pi}(s_{t},a_{t})/d^{\mu}(s_{t},a_{t})||_{\infty}<\infty$ (cf. (Le et al., 2019, Assumption 1 & Example 4.1)), which requires the sufficient exploration for tabular caseNote Xie & Jiang (2020b) has a tighter concentration coefficient with $C_{\mu}:=\max_{\pi\in\Pi}\left\lVert w_{d_{\pi}/\mu}\right\rVert^{2}_{2,\mu}$ but it still requires full exploration when $\Pi$ contains all policies. since we optimize over all policies (see Section F.2 for a discussion). In contrast, our assumption only requires $\mu$ to “trace” one single optimal policy.Nevertheless, we point out 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.

which is decided by the behavior policy $\mu$ and is an intrinsic quantity required by offline learning (see Theorem G.2 in Yin et al. (2021)). Our sample complexity bounds will depend on $1/d_{m}$ and in general $d_{m}$ is unknown. Yet, we assume $d_{m}$ is known for the moment and will utilize the knowledge of $d_{m}$ in our algorithms. Indeed, in Lemma 5.1, we show that estimating $d_{m}$ (using on-policy Monte Carlo estimator) up to a multiplicative factor only requires $\widetilde{O}(1/d_{m})$ episodes of offline data; replacing the exact $d_{m}$ with this estimator suffices for our purpose and, importantly, will not affect our downstream sample complexities.

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.

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 & 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 & 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^{\star}$, and an outer loop that performs multiple steps of such iterations to refine the estimates. Concretely, to obtain an reliable $Q_{t}(s,a)$ for some step $t\in[H]$, by the Bellman equation $Q_{t}(s,a)=r(s,a)+P_{t}^{\top}(\cdot|s,a)V_{t+1}$, we need to estimate $P_{t}^{\top}(\cdot|s,a)V_{t+1}$ with sufficient accuracy. VR handles this by decomposing:

where $V_{t+1}^{\text{in}}$ is a reference value function obtained from previous calculation (See line 4,13 in the inner loop of Algorithm 1) and $P_{t}^{\top}(\cdot|s,a)(V_{t+1}-V_{t+1}^{\text{in}})$, $P_{t}^{\top}(\cdot|s,a)V_{t+1}^{\text{in}}$ 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 policiesNote in general, direct translation of learning a $\epsilon$-optimal value to $\epsilon$-optimal policy will cause additional suboptimal complexity dependency of $H$. , we build on the following “monotonicity property”: For any policy $\pi$ that satisfies the monotonicity condition $V_{t}\leq\mathcal{T}_{\pi_{t}}V_{t+1}$ for all $t\in[H]$, the performance of $\pi$ is sandwiched as $V_{t}\leq V^{\pi}_{t}\leq V^{\star}_{t}$, i.e. $\pi$ is guaranteed to perform the same or better than $V_{t}$. 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 & 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.

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 $\iota:=\log(HSA/\delta)$ as a short hand.

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.

uniformly for all $s_{t},a_{t}$ 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 $\mathbf{z}_{t}$ and $\mathbf{g}_{t}$ 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_{t}$ 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.

Now let us introduce our estimators $\mathbf{z}_{t}$ and $\mathbf{g}_{t}$ in the finite-horizon non-stationary case (the choices for the stationary case and the infinite-horizon case will be introduced later).

where $E_{m,t}=\{n_{s_{t},a_{t}}>\frac{1}{2}m\cdot d^{\mu}_{t}(s_{t},a_{t})\}$ and $n_{s_{t},a_{t}}$ is the number of episodes visited $(s_{t},a_{t})$ at time $t$. We also note that we only aggregate the data at the same time step $t$, so that the observations are from different episodes and thus independentThis is natural for the non-stationary transition setting; for the stationary transition setting we have an improved way for defining this estimators. See Section 4..

Here, $E_{l,t}=\{n^{\prime}_{s_{t},a_{t}}>\frac{1}{2}l\cdot d^{\mu}_{t}(s_{t},a_{t})\}$ and $f(s_{t},a_{t},u)\mathrel{\mathop{:}}=4u\sqrt{{\iota}/{ld^{\mu}_{t}(s_{t},a_{t})}}$. Notice that $f(s_{t},a_{t},u)$ depends on the additional input $u^{\text{in}}$ which measures the certified suboptimality of the input.

Fictitious vs. actual estimators.

Careful readers must have noticed that that the above estimators $\mathbf{z}_{t}$ and $\mathbf{g}_{t}$ are infeasible to implement as they require the unobserved (population level-quantities) in some cases. We call them fictitious estimators as a result. Readers should rest assured since by the following proposition we can show their practical implementations (summarized in Figure 1) are identical to these fictitious estimators with high probability:

Under the condition of Theorem 3.3, we have

These fictitious estimators, however, are easier to analyze and they 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 idea is that it replaces the low-probability, but pathological cases due to random $n_{s_{t},a_{t}}$ with ground truths. Another challenge of the offline setting is due to the dependence of data points within a single episode. Note that the estimators are only aggregating the data at the same time steps. Since the data pair at the same time must come from different episodes, then conditional independence (given data up to current time steps, the states transition to the next step are independent of each other) can be recovered by this design (3), (4).

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)}\geq\sup_{t}\|V^{\star}_{t}-V^{(0)}_{t}\|_{\infty}$ (recall $u^{(0)}$ is the initial parameter in the outer loop of Algorithm 1). This is captured in the following:

Suppose $\epsilon\in(0,1]$ is the final target accuracy. Algorithm 1 outputs the $\epsilon$-optimal policy with episode complexity:

Full algorithm description

We describe our full algorithm OPDVR in Algorithm 2.

3 OPDVR for non-stationary transition settings

We now state our main theoretical guarantee for the OPDVR algorithm in the finite-horizon non-stationary transition setting.

For the $H$-horizon non-stationary setting, there exist universal constants $c_{1},c_{2},c_{3}>0$ such that if we set $m^{\prime}_{1}=c_{1}H^{4}/d_{m}$ for Stage $1$, $m^{\prime}_{2}=c_{2}H^{3}/d_{m}$ for Stage $2$, set $K_{1}=K_{2}=\log_{2}(\sqrt{H}/\epsilon)$, take $\mathbf{g}_{t}$ and $\mathbf{z}_{t}$ according to Figure 1, then OPDVR (Algorithm 2) with probability $1-\delta$ outputs an $\epsilon$-optimal policy $\hat{\pi}$ provided that the number of episodes in the offline data $\mathcal{D}$ exceeds:

Theorem 3.3 shows that our OPDVR algorithm can find an $\epsilon$-optimal policy with $\widetilde{O}(H^{3}/d_{m}\epsilon^{2})$ episodes of offline data. Compared with the sample complexity lower bound $\Omega(H^{3}/d_{m}\epsilon^{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.

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: $P_{t}(s^{\prime}|s,a):\equiv P(s^{\prime}|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 $\gamma^{t}$, where $\gamma\in(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, and we would like our sample complexity to reflect such an improvement.

We begin by considering the finite-horizon stationary setting. As this is a special case of the non-stationary setting, Theorem 3.3 implies that OPDVR achieves $\widetilde{O}(H^{3}/d_{m}\epsilon^{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. Indeed, we modify the fictitious estimators (3) and (4) into the following:

where $E_{m}=\{n_{s,a}>\frac{1}{2}m\cdot\sum_{t=1}^{H}d^{\mu}_{t}(s,a)\}$ and $n_{s,a}=\sum_{i=1}^{m}\sum_{t=1}^{H}\mathbf{1}{[s^{(i)}_{t}=s,a^{(i)}_{t}=a]}$ is the number of data pieces visited $(s,a)$ over all $m$ episodes. Moreover, $f_{t}(s,a,u)=4u\sqrt{\frac{\iota}{l}\sum_{t=1}^{H}{d^{\mu}_{t}(s,a)}}$ and

In the $H$-horizon stationary transition setting, there exists universal constants $c^{\prime}_{1},c^{\prime}_{2},c^{\prime}_{3}$ such that if we set $m^{\prime}_{1}=c^{\prime}_{1}H^{3}/d_{m}$, $m^{\prime}_{2}=c^{\prime}_{2}H^{2}/d_{m}$ for Stage $1$ and $2$, set $K_{1}=K_{2}=\log_{2}(\sqrt{H}/\epsilon)$, and take $\mathbf{z}_{t}$ and $\mathbf{g}_{t}$ according to Figure 1, then with probability $1-\delta$, Practical OPDVR finds an $\epsilon$-optimal policy provided that the number of episodes in the offline data $\mathcal{D}$ exceeds:

Theorem 4.1 encompasses our main technical contribution, as the compact data aggregation among different time steps make analyzing the estimators (5) and (6) knotty due to data-dependence (unlike the non-stationary transition setting where estimators are designed using data at specific time so the conditional independence remains). In particular, we need to fully exploit the property that transition $P$ is identical across different times in a pinpoint way to obtain the $H^{2}$ dependence in the sample complexity bound.

Theorem 4.1 shows that OPDVR achieves a sample complexity upper bound $\widetilde{O}(H^{2}/d_{m}\epsilon^{2})$ in the stationary setting. To the best of our knowledge, this is the first result that achieves an $H^{2}$ dependence for offline RL with stationary transitions, and improves over the vanilla $H^{3}$ dependence in either the vanilla (non-stationary) OPDVR (Theorem 3.3) or the “off-policy evaluation + uniform convergence” algorithm of Yin et al. (2021). We emphasize that 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.

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.

For all $0<d_{m}\leq\frac{1}{SA}$, let the family of problem be \mathcal{M}_{d_{m}}:=\big{\{}(\mu,M)\;\big{|}\;\min_{t,s_{t},a_{t}}d_{t}^{\mu}(s_{t},a_{t})\newline \geq d_{m}\big{\}}. There exists universal constants $c_{1},c_{2},c,p$ (with $H,S,A\geq c_{1}$ and $0<\epsilon<c_{2}$) such that when $n\leq cH^{2}/d_{m}\epsilon^{2}$, we always have

The proof of Theorem 4.2 builds on modifying the $\widetilde{O}(H^{3}/d_{m}\epsilon^{2})$ sample complexity lower bound in the non-stationary case (Yin et al., 2021), and can be found in Appendix E.

2 Infinite-horizon discounted setting

We now consider the infinite-horizon discounted setting.

Algorithm 1 and 2 are slighted modified slightly modified to cater to the infinite horizon setting (detailed pseudo-code in Algorithm 3 and 4 in the appendix). Our result is stated as follows. The proof can be found in Appendix D.

Consider Algorithm 4. There are constants $c^{\prime}_{1},c^{\prime}_{2},c^{\prime}_{3}$, such that if we set $m^{\prime}_{1}=O((1-\gamma)^{-4}/d_{m}),m^{\prime}_{2}=O((1-\gamma)^{-3}/d_{m})$ (see more precise expressions in Lemma D.7), $K_{1}=\log_{2}({(1-\gamma)^{-1}}/\epsilon),K_{2}=\log_{2}(\sqrt{(1-\gamma)^{-1}}/\epsilon)$ , $R=\log(4/\epsilon(1-\gamma))$, and choose LCB estimators $\mathbf{z}$ and $\mathbf{g}$ as in Figure 1, then with probability $1-\delta$, the infinite horizon version of OPDVR (Algorithm 4) outputs an $\epsilon$-optimal policy provided that in offline data $\mathcal{D}$ has number of samples exceeding

where $\iota^{\prime}:=R\cdot(\log(32(1-\gamma)^{-1}RSA/\delta)+\log\log_{2}(\sqrt{(1-\gamma)^{-1}}/\epsilon))\cdot\log_{2}(\sqrt{(1-\gamma)^{-1}}/\epsilon)$.

The proof, deferred to Appendix D, again rely on the analyzing fictitious versions of Algorithm 3 and Algorithm 4 with similar techniques described in our proof sketch of Theorem 4.1.

We note again that for the infinite horizon case, the sample-complexity measures the number of steps, while in the finite horizon case our sample complexity measures the number of episodes (each episode is $H$ steps) thus $(1-\gamma)^{-3}$ is comparable to the $H^{2}$ dependence. To the best of our knowledge, Theorem 4.1 and Theorem 4.3 are the first results that achieve $H^{2}$, $(1-\gamma)^{-3}$ dependence in the offline regime respectively for stationary transition and infinite horizon setting, see Table 1. Although we note that our result relies on the tabular structure whereas these prior algorithms work for general function classes, their bounds do not improve when reduced to tabular case. In particular, Chen & Jiang (2019); Xie & Jiang (2020b, a) consider using function approximation for exactly tabular problem. Lastly, in the tabular regime, our Assumption 2.1 is much weaker than the $\beta_{\mu},C$ considered in these prior work; see Appendix F.2 for a discussion.

Discussions

It is worth mentioning that the input of OPDVR depends on unknown system quantity $d_{m}$. Nevertheless, $d_{m}$ 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 & 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 $\widehat{d}^{\mu}_{t}(s_{t},a_{t})=n_{s_{t},a_{t}}/n$ and $\widehat{d}_{m}:=\min_{t,s_{t},a_{t}}\{n_{s_{t},a_{t}}/n:n_{s_{t},a_{t}}>0\},$ is sufficient for accurately estimating $d^{\mu}_{t},d_{m}$ simultaneously.

For the finite-horizon setting (either stationary or non-stationary), there exists universal constant $c$, s.t. when $n\geq c\cdot 1/d_{m}\cdot\log(HSA/\delta)$, then w.p. $1-\delta$, we have $\forall t,s_{t},a_{t}$, $\frac{1}{2}d^{\mu}_{t}(s_{t},a_{t})\leq\widehat{d}^{\mu}_{t}(s_{t},a_{t})\leq\frac{3}{2}d^{\mu}_{t}(s_{t},a_{t})$ and, in particular, $\frac{1}{2}d_{m}\leq\widehat{d}_{m}\leq\frac{3}{2}d_{m}.$

Computational and memory cost.

OPDVR can be implemented as a streaming algorithm that uses only one pass of the dataset. Its computational cost is $\widetilde{O}(H^{4}/d_{m}\epsilon^{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 variance reduction under generative models.

This work may be considered as an extension of the variance reduction framework for RL in the generative model setting (e.g. (Sidford et al., 2018a; Yang & Wang, 2019)), as some of proving techniques such as VR and monotone preserving $V_{t}\leq\mathcal{T}_{\pi_{t}}V_{t+1}$ are inherited from previous works. However, two improvements are made. First, the data pieces collected in offline case are highly dependent (in contrast for generative model setting each simulator call is independent) therefore how to disentangle the dependent structure and analyze tight results 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). Lastly, on the other hand it is not very surprising technique (like VR) from generative model setting can be leveraged for offline RL. While generative model assumes access to the strong simulator $P(s^{\prime}|s,a)$, for offline RL $\mu$ serves as a surrogate simulator where we can simulate episodes. If we can treat the distributional shift appropriately and decouple the data dependence in a pinpoint manner, it is hopeful that generic ideas still work.

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, ODPVR is the first algorithm that acheives 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. We believe this paper leads to some interesting next steps. For example, can our understandings about the variance reduction algorithm shed light on other commonly used algorithms (such as Q-Learning) for offline RL? How can we better deal with insufficient data coverage? We would like to leave these as future work.

Acknowledgment

The authors would like to thank Lin F. Yang for the discussions about (Sidford et al., 2018a).

References

Appendix A More Discussion on Related Work

There is a growing body of work on offline RL recently (Levine et al., 2020) in both offline policy evaluation (OPE) and offline policy optimization. OPE (also known as Off-Policy Evaluation (Li et al., 2015)) requires estimating the value of a target policy $\pi$ from an offline dataset that is often generated using another behavior policy $\mu$. A variety of algorithms and theoretical guarantees have been established for offline policy evaluation (Li et al., 2015; Jiang & Li, 2016; Liu et al., 2018; Kallus & Uehara, 2019a, b; Uehara & Jiang, 2019; Xie et al., 2019; Yin & Wang, 2020; Duan & Wang, 2020; Liu et al., 2020a, b; Feng et al., 2020). The majority of these work uses (vanilla or more advanced versions of) importance sampling to correct for the distribution shift, or uses minimax formulation to approximate the task and solves the questions through convex/non-convex optimization.

Meanwhile, the offline policy optimization problem needs to find a near-optimal policy given the offline dataset. The study of offline policy optimization can be dated back to the classical Fitted Q-Iteration algorithm (Antos et al., 2008a, b). The sample complexity for offline policy optimization is studied in a line of recent work (Chen & Jiang, 2019; Le et al., 2019; Xie & Jiang, 2020b, a; Liu et al., 2020b). The focus on these work is on the combination of offline RL and function approximation; when specialized to the tabular setting, the sample complexities have a rather suboptimal dependence on the horizon $H$ (or $(1-\gamma)^{-1}$ in the discounted setting). In particular, Chen & Jiang (2019); Le et al. (2019) first established finite sample guarantees with complexity $\widetilde{O}((1-\gamma)^{-6}\beta_{\mu}/\epsilon^{2})$ (where $\beta_{\mu}$ is the concentration coefficient) and it is later improved to $\widetilde{O}((1-\gamma)^{-4}\beta_{\mu}/\epsilon^{2})$ by Xie & Jiang (2020b) with a finer analysis. Later, Xie & Jiang (2020a) considers offline RL under weak realizability assumption and Liu et al. (2020b) considers offline RL without good exploration. Those are challenging offline settings but their dependence on horizon $(1-\gamma)^{-1}$ (or $H$) is very suboptimal. The recent work of Yin et al. (2021) (OPE + uniform convergence) first achieves the sample complexity $\widetilde{O}(H^{3}/d_{m}\epsilon^{2})$ in the finite-horizon non-stationary transition setting for tabular offline RL, and establishes a lower bound $\Omega(H^{3}/d_{m}\epsilon^{2})$ (where $d_{m}$ is a constant related to the data coverage of the behavior policy in the given MDP that is similar to the concentration coefficient $\beta_{\mu}$) that matches the upper bound up to logarithmic factors. Compared with these work, we analyze a new variance reduction algorithm for offline policy learning, which is a more generic approach as it adapts to all typical settings (finite horizon stationary/non-stationary transition, infinite horizon setting) with optimal sample complexity while the technique in Yin et al. (2021) only works for non-stationary setting and cannot directly reduce to $\widetilde{O}(H^{2}/d_{m}\epsilon^{2})$ when the transition becomes stationary. Concurrent to this work, Jin et al. (2020) study pessimism-based algorithms for offline policy optimization under insufficient coverage of the data and Wang et al. (2020); Zanette (2020) provide some negative results (exponential lower bound) for offline RL with linear MDP structure.

Reinforcement learning in online settings

In the generative model setting (where one has a simulator that samples $(r_{t},s_{t+1})$ from any $(s_{t},a_{t})$, (Azar et al., 2013; Wainwright, 2019) prove sample complexity $\widetilde{O}((1-\gamma)^{-3}SA/\epsilon^{2})$ is sufficient for the output $Q$-function to be $\epsilon$-optimal, i.e. $||Q^{\star}-Q^{\text{out}}||_{\infty}<\epsilon$, however this does not imply $\epsilon$-optimal policy with the same sample complexity. The most related to our work among this line is (Sidford et al., 2018a), which designs an variance reduction algorithm that overcomes the above issue and obtains $\widetilde{O}((1-\gamma)^{-3}SA/\epsilon^{2})$ sample complexity or finding the optimal policy as well. Later (Yang & Wang, 2019) again uses VR to obtain the sample optimality under the linear transition models. The design of our algorithm builds upon the variance reduction technique; our doubling technique and analysis in the offline setting can be seen as a generalization of (Sidford et al., 2018a); see Section 5 and Appendix F.4 for more detailed discussions.

Appendix B Proofs for finite-horizon non-stationary setting

The roadmap of our analysis in this section consists of first doing concentration analysis, then iteratively reasoning using induction, analyzing the doubling procedure and proving from prototypical version to the practical version. At a high level, we arrange the proving pipeline to be similar to that of Sidford et al. (2018a) and let exquisite readers feel the difference between generative model setting and offline setting in tabular case (and why VR works under weak offline Assumption 2.1). We also address one defect in Sidford et al. (2018a) later (see Section F.4) to contrast that our doubling VR procedure is necessary.

Even before that, let us start with the simple monotone preservation lemma.

Suppose $V$ and $\pi$ is any value and policy satisfy $V_{t}\leq\mathcal{T}_{\pi_{t}}V_{t+1}$ for all $t\in[H]$. Then it holds $V_{t}\leq V^{\pi}_{t}\leq V^{\star}_{t}$, for all $t\in[H]$.

We only need to show $V_{t}\leq V^{\pi}_{t}$. Since $V_{t}\leq\mathcal{T}_{\pi_{t}}V_{t+1}$, we can use it repeatedly to obtain

where “$\circ$” denotes operator composition. Note by default $V_{H+1}=V_{H+1}^{\pi}=V_{H+1}^{\star}=\mathbf{0}$, therefore

where we use the definition of Bellman equation that $V_{t}^{\pi}=\mathcal{T}_{\pi_{t}}V_{t+1}^{\pi}$ for all $t$. Combining (7) and (8) gives the stated result. ∎

First fix $s_{t},a_{t}$. Let $E_{t}:=\{n_{s_{t},a_{t}}\geq\frac{1}{2}m\cdot d^{\mu}_{t}(s_{t},a_{t})\}$, then by definition,

Next we conditional on $n_{s_{t},a_{t}}$. Then from above expression and Bernstein inequality G.3 we have with probability at least $1-\delta$

i.e. for fixed $(s_{t},a_{t})$ we have with probability at least $1-\delta$,

Apply the union bound over all $t,s_{t},a_{t}$, we obtain

where the inequality is element-wise and this is (9). ∎

From the definition we have for fixed $(s_{t},a_{t})$

By using the same conditional on $n_{s_{t},a_{t}}$ as in Lemma B.2, applying Hoeffding’s inequality and law of total expectation, we obtain with probability $1-\delta/2$, the first term in above is bounded by

and similarly with probability $1-\delta/2$,

Note for $a,b,c>0$, if $|a-b|\leq c$, then $|a^{2}-b^{2}|=|a-b|\cdot|a+b|\leq|a-b|\cdot(|a|+|b|)\leq|a-b|\cdot(2|b|+c)\leq c\cdot(2|b|+c)=2bc+c^{2}$, therefore by (12) we have

where the last inequality comes from $|P^{\top}(\cdot|s_{t},a_{t})V^{\text{in}}_{t+1}|\leq||P(\cdot|s_{t},a_{t})||_{1}||V^{\text{in}}_{t+1}||_{\infty}\leq V_{\max}$. Combining (11), (13) and a union bound, we have with probability $1-\delta$,

apply again the union bound over $t,s_{t},a_{t}$ gives the desired result.

Fix time $t\in[H]$. Let $g_{t}$ be the estimator in (4) in Algorithm 1. Then if $||V_{t+1}-V^{\text{in}}_{t+1}||_{\infty}\leq 2u^{\text{in}}$, then with probability $1-\delta/H$,

Recall $g_{t},d^{\mu}_{t}$ are vectors. By definition of $g_{t}(s_{t},a_{t})$, applying Hoeffding’s inequality we obtain with probability $1-\delta/H$

Now use assumption $||V_{t+1}-V_{t+1}^{\text{in}}||_{\infty}\leq 2u^{\text{in}}$ and a union bound over $s_{t},a_{t}$, we have with probability $1-\delta/H$,

use $f=4u^{\text{in}}\sqrt{{\log(2HSA/\delta)}/{ld^{\mu}_{t}}}$, we obtain the stated result. ∎

The marginal state-action distribution $d^{\mu}_{t}$ entails the hardness in off-policy setting. If the current logging policy $\mu$ satisfies there exists some $s_{t},a_{t}$ such that $d^{\mu}_{t}(s_{t},a_{t})$ is very small, then learning the MDP using this off-policy data will be generically hard, unless $d^{\pi^{*}}_{t}(s_{t},a_{t})$ is also relatively small for this $s_{t},a_{t}$, see analysis in the following sections.

B.2 Iterative update analysis

Step1: For any $a,b\geq 0$, we have the basic inequality $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$, and apply to Lemma B.4 we have with probability $1-\delta/4$,

Next, similarly for any $a,b\geq 0$, we have $\sqrt{a}\leq\sqrt{|a-b|}+\sqrt{b}$, conditional on above then apply to Lemma B.2 (with probability $1-\delta/4$) and we obtain with probability $1-\delta/2$,

Next note $\sqrt{\sigma_{(\cdot)}}$ is a norm, so by norm triangle inequality (for the second inequality) and $\sqrt{a}\leq\sqrt{b}+\sqrt{|b-a|}$ with (15) (for the first inequality) we have

To sum up, so far we have shown that (16), (18) hold with probability $1-\delta/2$ and we condition on that.

First of all, $V^{\star}_{H+1}=V_{H+1}=V_{H+1}^{\text{in}}=0$ implies $V^{\star}_{H+1}\leq V_{H+1}\leq V_{H+1}^{\text{in}}$ and

Now for certain $t$, using induction assumption we can assume with probability at least $1-(H-t-1)\delta/H$, for all $t^{\prime}=t+1,...,H$,

In particular, since $V^{\text{in}}_{t+1}\leq V_{t+1}^{\star}\leq V^{\text{in}}_{t+1}+u^{\text{in}}\mathbf{1}$, so combine this and (20) for $t^{\prime}=t+1$ we get

By Lemma B.5, with probability $1-\delta/H$,

By the right hand side of above and (16) we acquire with probability $1-(H-t)\delta/H$,

where the second equality already gives the proof of the first part of claim (19) and the second inequality is by induction assumption. Moreover, above $Q_{t}\leq Q_{t}^{\star}$ also implies $V_{Q_{t}}\leq V_{Q_{t}^{\star}}=V_{t}^{\star}$, so together with Lemma B.1 (note $V_{t}^{\text{in}}\leq\mathcal{T}_{\pi_{t}^{\text{in}}}V_{t+1}^{\text{in}}$) we have

this completes the proof of the second part of claim (19).

Step3: Next we prove $V_{t}\leq\mathcal{T}_{\pi_{t}}V_{t+1}$.

where the first equal sign comes from the definition of $V_{t}$ when $V_{Q_{t}}(s_{t})\geq V^{\text{in}}_{t}(s_{t})$ and the first inequality is from Step2.

On the other hand, if $\pi_{t}(s_{t})=\pi^{\text{in}}(s_{t})$, then

where the first inequality is the property of input $V^{\text{in}}$, $\pi^{\text{in}}$ and the second inequality is from Step2.

Step4: It remains to prove $Q^{\star}_{t}-Q_{t}\leq\textit{{P}}^{\pi^{\star}}_{t}[Q^{\star}_{t+1}-Q_{t+1}]+{\xi}_{t}$. Indeed, using the construction of $Q_{t}$, we have

where the second equation uses Bellman optimality equation and the third equation uses the definition of ${\xi}_{t}=\textit{{P}}_{t}(V_{t+1}-V^{\text{in}}_{t+1})-g_{t}+\textit{{P}}_{t}V_{t+1}^{\text{in}}-z_{t}$. By (18) and (21),

Lastly, note $\textit{{P}}_{t}V_{t+1}^{\star}=\textit{{P}}^{\pi^{\star}}_{t}Q^{\star}_{t+1}$ and by definition $V_{t+1}\geq V_{Q_{t+1}}$, so we have $\textit{{P}}_{t}V_{t+1}\geq\textit{{P}}_{t}V_{Q_{t+1}}=\textit{{P}}^{\pi_{Q_{t+1}}}_{t}Q_{t+1}\geq\textit{{P}}^{\pi^{\star}}_{t}Q_{t+1}$, the last inequality holds true since $\pi_{Q_{t+1}}$ is the greedy policy over $Q_{t+1}$. Threfore (22) becomes $Q^{\star}_{t}-Q_{t}=\textit{{P}}_{t}V_{t+1}^{\star}-\textit{{P}}_{t}V_{t+1}+{\xi_{t}}\leq\textit{{P}}^{\pi^{\star}}_{t}Q^{\star}_{t+1}-\textit{{P}}^{\pi^{\star}}_{t}Q_{t+1}+{\xi_{t}}$. This completes the proof.

Suppose the input $V^{\text{in}}_{t}$, $t\in[H]$ of Algorithm 1 satisfies $V^{\text{in}}_{t}\leq\mathcal{T}_{\pi^{\text{in}}_{t}}V_{t+1}^{\text{in}}$ and $V^{\text{in}}_{t}\leq V^{\star}_{t}\leq V^{\text{in}}_{t}+u^{\text{in}}\mathbf{1}$. Let $V_{t}$, $\pi$ be the return of inner loop of Algorithm 1 and choose $m=l:=m^{\prime}\cdot\log(16HSA)/(u^{\text{in}})^{2}$, where $m^{\prime}$ is a parameter will be decided later. Then in addition to the results of Lemma B.7, we have with probability $1-\delta$,

Note if $u^{\text{in}}\geq\sqrt{H}$, the first term in $V_{t}-V_{t}^{\star}$ requires sample $m^{\prime}$ of order $O(H^{4})$, which is suboptimal. This is the main reason why we need the doubling procedure in Algorithm 2 to keep the whole algorithm optimal.

By Lemma B.7, we have with probability $1-\delta$, for all $t\in[H]$,

Applying the recursion repeatedly, we obtain

Now by our choice of $m=l:=m^{\prime}\cdot\log(16HSA/\delta)/(u^{\text{in}})^{2}$, then (23) further less than

Case1. If $u^{\text{in}}\leq\sqrt{H}$, then (24) is less than

Case2. If $u^{\text{in}}\geq\sqrt{H}$, then (24) is less than

B.3 The doubling procedure

Before we explain the doubling procedure, let us first finish the proof the Algorithm 1.

Recall $\epsilon$ is the target accuracy in the outer loop of Algorithm 1. Then:

If $u^{(0)}\leq\sqrt{H}$, then choose $m^{(i)}=l^{(i)}=B\log(16HSAK/\delta)/(u^{(i-1)})^{2}$, where

If $u^{(0)}>\sqrt{H}$, then choose $m^{(i)}=l^{(i)}=B\log(16HSAK/\delta)/(u^{(i-1)})^{2}$, where

Then Algorithm 1 guarantees with probability $1-\delta$, the output $\pi^{(K)}$ is a $\epsilon$-optimal policy, i.e. $||V_{1}^{\star}-V_{1}^{\pi^{(K)}}||_{\infty}<\epsilon$ with total episode complexity:

for both cases. Moreover, $B$ can be simplified as:

If $u^{(0)}\leq\sqrt{H}$,then $B\leq cH^{3}/d_{m}$;

If $u^{(0)}>\sqrt{H}$, then $B\leq cH^{4}/d_{m}$.

Step1: proof in general. First, using induction it is easy to show for all $0<a_{1},...,a_{n}<1$, it follows

and this directly implies $(1-\frac{\delta}{K})^{K}\geq 1-\delta$. By the choice of $m^{\prime}$ and $K$, for both situation by Lemma B.8 we always have $||V_{t}^{\star}-V_{t}^{\pi^{(i)}}||_{\infty}<u^{(i-1)}/2=u^{(i)}$ with probability $1-\delta/K$ (this is because we choose $m^{(i)}=l^{(i)}=B\log(16HSAK/\delta)/(u^{(i-1)})^{2}$ instead of $B\log(16HSA/\delta)/(u^{(i-1)})^{2}$).

In particular, in both situationThe last equal sign holds since if $u^{(0)}\leq\sqrt{H}$ (or $u^{(0)}\leq{H}$), you can always reset $u^{(0)}=\sqrt{H}$ (or $u^{(0)}={H}$).

Step2: simplified expression for $m^{\prime}$. Indeed,

Plug all these numbers back, we have the simplified bound for $B$. ∎

The Assumption 2.1 comes into picture for the validity of the bound for $A_{2}$ since when $d^{\pi^{\star}}_{t:t^{\prime}}(s^{\prime}_{t},a^{\prime}_{t}|s_{t},a_{t})>0$, by Assumption 2.1 we always have $d_{t^{\prime}}^{\mu}(s^{\prime}_{t},a^{\prime}_{t})>0$ so the bound will never be the trivial $+\infty$.

Note choose any $m^{\prime}>B$ (in Lemma B.10) yields the similar complexity bound of

therefore by the simplified bound of $B$, we choose $m^{\prime}=O(H^{4}/d_{m})$ for stage1 and $m^{\prime}=O(H^{3}/d_{m})$ for stage2.

Stage1. Denote $\epsilon^{\prime}=\sqrt{H}\epsilon$ and $u^{(0)}=H$, then by the choice of $K$ and $m^{\prime}_{H}=cH^{4}/d_{m}$ for the case of $u^{(0)}\geq\sqrt{H}$ in Lemma B.10, it outputs $V_{t}^{\text{intermediate}}$, $\pi^{\text{intermediate}}$ which is $\epsilon^{\prime}$ optimal with complexity:

where $K_{\epsilon^{\prime}}=\log_{2}(H/\epsilon^{\prime})$;

Stage2. Use $V_{t}^{\text{intermediate}}$, $\pi^{\text{intermediate}}$ as input, since $\epsilon^{\prime}=\sqrt{H}\epsilon\leq\sqrt{H}$, we can set $u^{(0)}=\sqrt{H}$. Now by Lemma B.10 again (with $m^{\prime}_{\sqrt{H}}=cH^{3}/d_{m}$), Algorithm 2 has the final output $V_{t}^{\text{final}}$, $\pi^{\text{final}}$ that is $\epsilon$ optimal with complexity

where $K_{\epsilon}=\log_{2}(\sqrt{H}/\epsilon)$.

Plug back $\epsilon^{\prime}=\sqrt{H}\epsilon$, Algorithm 2 guarantees $\epsilon$-optimal policy with probability $1-\delta$ using total complexity

where the last inequality uses $m^{\prime}_{\sqrt{H}}\leq cH^{3}/d_{m}$ and $m^{\prime}_{H}\leq cH^{4}/d_{m}$ in Lemma B.10 and above holds with probability $1-\delta$ .

B.4 Practical OPDVR

To go from non-implementable version to the practical version, the idea is to bound the event $\{n_{s_{t},a_{t}}\leq\frac{1}{2}m\cdot d^{\mu}_{t}(s_{t},a_{t})\}$ and $\{n^{\prime}_{s_{t},a_{t}}\leq\frac{1}{2}l\cdot d^{\mu}_{t}(s_{t},a_{t})\}$ so that with high probability, the non-implementable version is identical to the practical OPDVR in Algorithm 2. Specifically, when $m^{\prime}\geq 8H^{2}/d_{m}$ (this is satisfied since for each stage we set $m^{\prime}$ to be at least $O(H^{3}/d_{m})$), then

and repeat this analysis for both stages, we have with probability $1-\delta/2$, Practical OPDVR is identical to the non-implementable version.

B.5 Proof of Theorem 3.3

The proof consists of two parts. The first part is to use (27) to show OPDVR in Algorithm 2 outputs $\epsilon$-optimal policy using episode complexity

with probability $1-\delta/2$, and the second part is to use (28) to let Practical OPDVR is identical to the non-implementable version with probability $1-\delta/2$. Apply a union bound of these two gives the stated results in Theorem 3.3 with probability $1-\delta$. ∎

Appendix C Proofs for finite-horizon stationary setting

and recall $f(s,a)=4u^{\text{in}}\sqrt{{\log(2HSA/\delta)}/{l\sum_{t=1}^{H}d^{\mu}_{t}(s,a)}}$.

Consdier fixed $s,a$. Let $E_{s,a}:=\{n_{s,a}\geq\frac{1}{2}m\cdot\sum_{t=1}^{H}d^{\mu}_{t}(s,a)\}$, then by definition,

Next we conditional on $n_{s,a}$. Define $\mathcal{F}_{k}:=\{s_{u}^{(i)},a_{u}^{(i)}\}_{i\in[m]}^{u\in[k]}$ is an increasing filtration and denote

Note if $\mathbf{1}[s^{(i)}_{u}=s,a^{(i)}_{u}=a]=1$, then

if $\mathbf{1}[s^{(i)}_{u}=s,a^{(i)}_{u}=a]=0$, then still

First of all by Hoeffding’s inequality, we have the martingale difference satisfies with probability $1-\delta/2$,

where we use shorthand notation $V^{\text{in}}_{t+1}(s^{(i)}_{k+1}|s,a)$ to denote the value of $V^{\text{in}}_{k+1}(s^{(i)}_{k+1})$ given $s^{(i)}_{k}=s$ and $a^{(i)}_{k}=a$ and $n_{k,s,a}=\sum_{i=1}^{m}\mathbf{1}[s^{(i)}_{k}=s,a^{(i)}_{k}=a]\leq n_{s,a}$.

where the second equal sign uses episodes are independent, the third equal sign uses Markov property, the fourth uses $\mathbf{1}[s^{(i)}_{k}=s,a^{(i)}_{k}=a]$ is measurable w.r.t $s^{(i)}_{k},a^{(i)}_{k}$ and $P^{\top}(\cdot|s,a)V^{\text{in}}_{t+1}$ is constant, the fifth equal sign uses the identity

and sixth line is true since we have stationary transition, the underlying transition is always $P(\cdot|s,a)$ regardless of time step. This is the key for further reducing the dependence on $H$ and is NOT shared by non-stationary transition setting!

which means with probability at least $1-\delta$

Now we get rid of the conditional on $n_{s_{t},a_{t}}$. Denote

Finally, apply the union bound over all $t,s,a$, we obtain

where the inequality is element-wise and this is (9). ∎

From the definition we have for fixed $(s,a)$

Now we conditional on $n_{s,a}$. The key point is we can regroup $m$ episodic data into $mH$ data pieces, in order. (This is valid since within each episode data is generated by time and between different episodes are independent, so we can concatenate one episode after another and end up with $mH$ pieces that comes in sequentially.) This key reformulation allows us to apply Azuma Hoeffding’s inequality and obtain with probability $1-\delta/2$,

where the first equal sign comes from the reformulation trick and the first inequality is by $X_{k}:=\sum_{u^{\prime}=1}^{k}\left[V^{\text{in}}_{t+1}(s^{(i)}_{u^{\prime}+1})^{2}-P^{\top}(\cdot|s_{t},a_{t})(V^{\text{in}}_{t+1})^{2}\right]\mathbf{1}[s^{(i)}_{u^{\prime}}=s,a^{(i)}_{u^{\prime}}=a]$ is martingale. Similarly with probability $1-\delta/2$,

Note for $a,b,c>0$, if $|a-b|\leq c$, then $|a^{2}-b^{2}|=|a-b|\cdot|a+b|\leq|a-b|\cdot(|a|+|b|)\leq|a-b|\cdot(2|b|+c)\leq c\cdot(2|b|+c)=2bc+c^{2}$, therefore by (35) we have

where the last inequality comes from $|P^{\top}(\cdot|s,a)V^{\text{in}}_{t+1}|\leq||P(\cdot|s,a)||_{1}||V^{\text{in}}_{t+1}||_{\infty}\leq V_{\max}$. Combining (34), (36) and a union bound, we have with probability $1-\delta$,

apply again the union bound over $t,s,a$ gives the desired result.

Fix time $t\in[H]$. Let $g_{t}$ be the estimator in (4) in Algorithm 1. Then if $||V_{t+1}-V^{\text{in}}_{t+1}||_{\infty}\leq 2u^{\text{in}}$, then with probability $1-\delta/H$,

Recall $g_{t},d^{\mu}_{t}$ are vectors. By definition of $g_{t}(s,a)$, use similar regrouping trick and apply Azuma Hoeffding’s inequality we obtain with probability $1-\delta/H$

Now use assumption $||V_{t+1}-V_{t+1}^{\text{in}}||_{\infty}\leq 2u^{\text{in}}$ and a union bound over $s,a$, we have with probability $1-\delta/H$,

use $f=4u^{\text{in}}\sqrt{{\log(2HSA/\delta)}/{l\sum_{t=1}^{H}d^{\mu}_{t}}}$, we obtain the stated result. ∎

Note that Lemma C.1,C.2,C.3 updates Lemma B.2,B.4,B.5 by replacing $d^{\mu}_{t}$ with $\sum_{t=1}^{H}d^{\mu}_{t}$ and keeping the rest the same except the second order term $\sqrt{\frac{16V_{\max}\cdot\log(2HSA/\delta)}{9m\sum_{t=1}^{H}d^{\mu}_{t}}}\cdot\log(HSA/\delta)$ in Lemma C.1 is different from Lemma C.1. However, this is still lower order term since it is of order $\widetilde{O}(\sqrt{\frac{H}{m\sum_{t=1}^{H}d^{\mu}_{t}}})$. To avoid redundant reasoning, by following the identical logic as Section B.2 we have a similar expression of (18) as follows:

where the last term is additional. However, note when $u^{\text{in}}\leq\sqrt{H}$, then

so the last term $c\sqrt{\frac{V_{\max}\cdot\log(16HSA/\delta)}{m\cdot\sum_{t=1}^{H}d^{\mu}_{t}}}$ can be assimilated by previous one. If $u^{\text{in}}>\sqrt{H}$, it is of even lower order. Therefore following the same reasoning we can complete the proof for Algorithm 1.

From non-implementable version to the practical version, we need to bound the event of $\{n_{s,a}\leq\frac{1}{2}m\cdot\sum_{t=1}^{H}d^{\mu}_{t}(s,a)\}$, where $n_{s,a}=\sum_{i=1}^{m}\sum_{t=1}^{H}\mathbf{1}{[s^{(i)}_{t}=s,a^{(i)}_{t}=a]}$. In this case, $n_{s,a}$ is no longer binomial random variable so Lemma G.2 cannot be applied. However, the trick we use for resolving this issue is the following decomposition

where $n_{s,a}=\sum_{t=1}^{H}n_{t,s,a}$ and $n_{t,s,a}=\sum_{i=1}^{m}\mathbf{1}{[s^{(i)}_{t}=s,a^{(i)}_{t}=a]}$ are binomial random variables. Lemma G.2 can then be used together with union bounds to finish the proof.

Appendix D Proofs for infinite-horizon discounted setting

First recall data $\mathcal{D}=\{s^{(i)},a^{(i)},r^{(i)},s^{\prime(i)}\}_{i\in[n]}$ are i.i.d off-policy pieces with $(s^{(i)},a^{(i)})\sim d^{\mu}$ and $s^{\prime(i)}\sim P(\cdot|s^{(i)},a^{(i)})$. Moreover, $d^{\mu}$ is defined as: