Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems — part 4/12

Cleaned-text code points [44871, 59638). Bibliography omitted here; source.md includes it.

This means that, even with optimal action labels, we get an error bound that is at best quadratic in the time horizon H H in the offline case, but linear in H H in the online case. Intuitively, the reason for this gap in performance is that, in the offline case, the learned policy π ⁡ ( 𝐚 | 𝐬 ) \pi(\mathbf{a}|\mathbf{s}) may enter into states that are far outside of its training distribution, since d π ​ ( 𝐬 ) d^{\pi}(\mathbf{s}) may be very different from d π β ​ ( 𝐬 ) d^{{\pi_{\beta}}}(\mathbf{s}) . In these out-of-distribution states, the generalization error bound ϵ \epsilon no longer holds, since standard empirical risk minimization makes no guarantees about error when encountering out-of-distribution inputs that were not seen during training. Once the policy enters one of these out-of-distribution states, it will keep making mistakes and may remain out-of-distribution for the remainder of the trial, accumulating O ⁡ ( H ) O(H) error. Since there is a non-trivial chance of entering an out-of-distribution state at every one of the H H time steps, the overall error therefore scales as O ⁡ ( H 2 ) O(H^{2}) . In the on-policy case, such out-of-distribution states are not an issue. Of course, this example is somewhat orthogonal to the main purpose of this tutorial, which is to study offline reinforcement learning algorithms, rather than offline behavioral cloning methods. However, it should serve as a warning, as it indicates that the challenges of distributional shift are likely to cause considerable harm to any policy trained from an offline dataset if care is not taken to minimize its detrimental effects.

## 3 Offline Evaluation and Reinforcement Learning via Importance Sampling

In this section, we survey offline reinforcement learning algorithms based on direct estimation of policy return. These methods generally utilize some form of importance sampling to either evaluate the return of a given policy, or to estimate the corresponding policy gradient, corresponding to an offline variant of the policy gradient methods discussed in Section 2.1 . The most direct way to utilize this idea is to employ importance sampling to estimate J ⁡ ( π ) J(\pi) with trajectories sampled from π β ​ ( τ ) {\pi_{\beta}}(\tau) . This is known as off-policy evaluation . In principle, once we can evaluate J ⁡ ( π ) J(\pi) , we can select the most performant policy. In this section, we review approaches for off-policy evaluation with importance sampling and then discuss how these ideas can be used for offline reinforcement learning.

### 3.1 Off-Policy Evaluation via Importance Sampling

We can naïvely use importance sampling to derive an unbiased estimator of J ⁡ ( π ) J(\pi) that relies on off-policy trajectories: J ⁡ ( π θ ) \displaystyle J(\pi_{\theta}) = 𝔼 τ ∼ π β ​ ( τ ) ​ [ π θ ​ ( τ ) π β ​ ( τ ) ​ ∑ t = 0 H γ t ​ r ​ ( 𝐬 , 𝐚 ) ] \displaystyle=\mathbb{E}_{\tau\sim{\pi_{\beta}}(\tau)}\left[\frac{\pi_{\theta}(\tau)}{{\pi_{\beta}}(\tau)}\sum_{t=0}^{H}\gamma^{t}r(\mathbf{s},\mathbf{a})\right] = 𝔼 τ ∼ π β ​ ( τ ) ​ [ ( ∏ t = 0 H π θ ​ ( 𝐚 t | 𝐬 t ) π β ​ ( 𝐚 t | 𝐬 t ) ) ​ ∑ t = 0 H γ t ​ r ​ ( 𝐬 , 𝐚 ) ] ≈ ∑ i = 1 n w H i ​ ∑ t = 0 H γ t ​ r t i , \displaystyle=\mathbb{E}_{\tau\sim{\pi_{\beta}}(\tau)}\left[\left(\prod_{t=0}^{H}\frac{\pi_{\theta}(\mathbf{a}_{t}|\mathbf{s}_{t})}{{\pi_{\beta}}(\mathbf{a}_{t}|\mathbf{s}_{t})}\right)\sum_{t=0}^{H}\gamma^{t}r(\mathbf{s},\mathbf{a})\right]\approx\sum_{i=1}^{n}w_{H}^{i}\sum_{t=0}^{H}\gamma^{t}r_{t}^{i}, (5) where w t i = 1 n ​ ∏ t ′ = 0 t π θ ​ ( 𝐚 t ′ i | 𝐬 t ′ i ) π β ​ ( 𝐚 t ′ i | 𝐬 t ′ i ) w_{t}^{i}=\frac{1}{n}\prod_{t^{\prime}=0}^{t}\frac{\pi_{\theta}(\mathbf{a}_{t^{\prime}}^{i}|\mathbf{s}_{t^{\prime}}^{i})}{{\pi_{\beta}}(\mathbf{a}_{t^{\prime}}^{i}|\mathbf{s}_{t^{\prime}}^{i})} and { ( 𝐬 0 i , 𝐚 0 i , r 0 i , 𝐬 1 i , … ) } i = 1 n \{(\mathbf{s}_{0}^{i},\mathbf{a}_{0}^{i},r_{0}^{i},\mathbf{s}_{1}^{i},\ldots)\}_{i=1}^{n} are n n trajectory samples from π β ​ ( τ ) {\pi_{\beta}}(\tau) ( Precup,, 2000 ) . Unfortunately, such an estimator can have very high variance (potentially unbounded if H H is infinite) due to the product of importance weights. Self-normalizing the importance weights (i.e., dividing the weights by ∑ i = 1 n w H i \sum_{i=1}^{n}w_{H}^{i} ) results in the weighted importance sampling estimator ( Precup,, 2000 ) , which is biased, but can have much lower variance and is still a strongly consistent estimator.

To improve this estimator, we need to take advantage of the statistical structure of the problem. Because r t r_{t} does not depend on 𝐬 t ′ \mathbf{s}_{t^{\prime}} and 𝐚 t ′ \mathbf{a}_{t^{\prime}} for t ′ > t t^{\prime}>t , we can drop the importance weights from future time steps, resulting in the per-decision importance sampling estimator ( Precup,, 2000 ) : J ⁡ ( π θ ) = 𝔼 τ ∼ π β ​ ( τ ) ​ [ ∑ t = 0 H ( ∏ t ′ = 0 t π θ ​ ( 𝐚 t | 𝐬 t ) π β ​ ( 𝐚 t | 𝐬 t ) ) ​ γ t ​ r ​ ( 𝐬 , 𝐚 ) ] ≈ 1 n ​ ∑ i = 1 n ∑ t = 0 H w t i ​ γ t ​ r t i . J(\pi_{\theta})=\mathbb{E}_{\tau\sim{\pi_{\beta}}(\tau)}\left[\sum_{t=0}^{H}\left(\prod_{t^{\prime}=0}^{t}\frac{\pi_{\theta}(\mathbf{a}_{t}|\mathbf{s}_{t})}{{\pi_{\beta}}(\mathbf{a}_{t}|\mathbf{s}_{t})}\right)\gamma^{t}r(\mathbf{s},\mathbf{a})\right]\approx\frac{1}{n}\sum_{i=1}^{n}\sum_{t=0}^{H}w_{t}^{i}\gamma^{t}r_{t}^{i}. As before, this estimator can have high variance, and we can form a weighted per-decision importance estimator by normalizing the weights. Unfortunately, in many practical problems, the weighted per-decision importance estimator still has too much variance to be effective.

If we have an approximate model that can be used to obtain an approximation to the Q-values for each state-action tuple ( 𝐬 t , 𝐚 t ) (\mathbf{s}_{t},\mathbf{a}_{t}) , which we denote Q ^ π ​ ( 𝐬 t , 𝐚 t ) \hat{Q}^{\pi}(\mathbf{s}_{t},\mathbf{a}_{t}) , we can incorporate it into this estimate. Such an estimate can be obtained, for example, by estimating a model of the MDP transition probability T ⁡ ( 𝐬 t + 1 | 𝐬 t , 𝐚 t ) T(\mathbf{s}_{t+1}|\mathbf{s}_{t},\mathbf{a}_{t}) and then solving for the corresponding Q-function, or via any other method for approximating Q-values. We can incorporate these estimates as control variates into the importance sampled estimator to get the best of both: J ⁡ ( π θ ) ≈ ∑ i = 1 n ∑ t = 0 H γ t ​ ( w t i ​ ( r t i − Q ^ π θ ​ ( 𝐬 t , 𝐚 t ) ) − w t − 1 i ​ 𝔼 𝐚 ∼ π θ ​ ( 𝐚 | 𝐬 t ) ​ [ Q ^ π θ ​ ( 𝐬 t , 𝐚 ) ] ) . J(\pi_{\theta})\approx\sum_{i=1}^{n}\sum_{t=0}^{H}\gamma^{t}\left(w_{t}^{i}\left(r_{t}^{i}-\hat{Q}^{\pi_{\theta}}(\mathbf{s}_{t},\mathbf{a}_{t})\right)-w_{t-1}^{i}\mathbb{E}_{\mathbf{a}\sim\pi_{\theta}(\mathbf{a}|\mathbf{s}_{t})}\left[\hat{Q}^{\pi_{\theta}}(\mathbf{s}_{t},\mathbf{a})\right]\right). (6) This is known as the doubly robust estimator ( Jiang and Li,, 2015 ; Thomas and Brunskill,, 2016 ) because it is unbiased if either π β {\pi_{\beta}} is known or if the model is correct. We can also form a weighted version by normalizing the weights. More sophisticated estimators can be formed by training the model with knowledge of the policy to be evaluated ( Farajtabar et al.,, 2018 ) , and by trading off bias and variance more optimally ( Thomas and Brunskill,, 2016 ; Wang et al.,, 2017 ) .

Beyond consistency or unbiased estimates, we frequently desire a (high-probability) guarantee on the performance of a policy. Thomas et al., (2015) derived confidence bounds based on concentration inequalities specialized to deal with the high variance and potentially large range of the importance weighted estimators. Alternatively, we can construct confidence bounds based on distributional assumptions (e.g., asymptotic normality) ( Thomas et al.,, 2015 ) or via bootstrapping ( Thomas et al.,, 2015 ; Hanna et al.,, 2017 ) which may be less conservative at the cost of looser guarantees.

Such estimators can also be utilized for policy improvement, by searching over policies with respect to their estimated return. In safety-critical applications of offline RL, we would like to improve over the behavior policy with a guarantee that with high probability our performance is no lower than a bound. Thomas et al., (2015) show that we can search for policies using lower confidence bounds on importance sampling estimators to ensure that the safety constraint is met. Alternatively, we can search over policies in a model of the MDP and bound the error of the estimated model with high probability ( Ghavamzadeh et al.,, 2016 ; Laroche et al.,, 2017 ; Nadjahi et al.,, 2019 ) .

### 3.2 The Off-Policy Policy Gradient

Importance sampling can also be used to directly estimate the policy gradient, rather than just obtaining an estimate of the value for a given policy. As discussed in Section 2.1 , policy gradient methods aim to optimize J ⁡ ( π ) J(\pi) by computing estimates of the gradient with respect to the policy parameters. We can estimate the gradient with Monte Carlo samples, as in Equation ( 2 ), but this requires on-policy trajectories (i.e., τ ∼ π θ ​ ( τ ) \tau\sim\pi_{\theta}(\tau) ). Here, we extend this approach to the offline setting.

Previous work has generally focused on the off-policy setting, where trajectories are sampled from a distinct behavior policy π β ​ ( 𝐚 | 𝐬 ) ≠ π ⁡ ( 𝐚 | 𝐬 ) {\pi_{\beta}}(\mathbf{a}|\mathbf{s})\neq\pi(\mathbf{a}|\mathbf{s}) . However, in contrast to the offline setting, such methods assume we can continually sample new trajectories from π β {\pi_{\beta}} , while old trajectories are reused for efficiency. We begin with the off-policy setting, and then discuss additional challenges in extending such methods to the offline setting.

Noting the similar structure between J ⁡ ( π ) J(\pi) and the policy gradient, we can adapt the techniques for estimating J ⁡ ( π ) J(\pi) off-policy to the policy gradient ∇ θ J ​ ( π θ ) \displaystyle\nabla_{\theta}J(\pi_{\theta}) = 𝔼 τ ∼ π β ​ ( τ ) ​ [ π θ ​ ( τ ) π β ​ ( τ ) ​ ∑ t = 0 H γ t ​ ∇ θ ​ log ⁡ π θ ​ ( 𝐚 t | 𝐬 t ) ​ A ^ ​ ( 𝐬 t , 𝐚 t ) ] \displaystyle=\mathbb{E}_{\tau\sim{\pi_{\beta}}(\tau)}\left[\frac{{\pi_{\theta}}(\tau)}{{\pi_{\beta}}(\tau)}\sum_{t=0}^{H}\right.\gamma^{t}\nabla_{\theta}\log\pi_{\theta}(\mathbf{a}_{t}|\mathbf{s}_{t})\hat{A}(\mathbf{s}_{t},\mathbf{a}_{t})\left.\vphantom{\sum_{t=0}^{H}}\right] = 𝔼 τ ∼ π β ​ ( τ ) ​ [ ( ∏ t = 0 H π θ ​ ( 𝐚 t | 𝐬 t ) π β ​ ( 𝐚 t | 𝐬 t ) ) ​ ∑ t = 0 H γ t ​ ∇ θ ​ log ⁡ π θ ​ ( 𝐚 t | 𝐬 t ) ​ A ^ ​ ( 𝐬 t , 𝐚 t ) ] \displaystyle=\mathbb{E}_{\tau\sim{\pi_{\beta}}(\tau)}\left[\left(\prod_{t=0}^{H}\frac{\pi_{\theta}(\mathbf{a}_{t}|\mathbf{s}_{t})}{{\pi_{\beta}}(\mathbf{a}_{t}|\mathbf{s}_{t})}\right)\sum_{t=0}^{H}\right.\gamma^{t}\nabla_{\theta}\log\pi_{\theta}(\mathbf{a}_{t}|\mathbf{s}_{t})\hat{A}(\mathbf{s}_{t},\mathbf{a}_{t})\left.\vphantom{\sum_{t=0}^{H}}\right] ≈ ∑ i = 1 n w H i ​ ∑ t = 0 H γ t ​ ∇ θ ​ log ⁡ π θ ​ ( 𝐚 t i | 𝐬 t i ) ​ A ^ ​ ( 𝐬 t i , 𝐚 t i ) , \displaystyle\approx\sum_{i=1}^{n}w_{H}^{i}\sum_{t=0}^{H}\gamma^{t}\nabla_{\theta}\log\pi_{\theta}(\mathbf{a}_{t}^{i}|\mathbf{s}_{t}^{i})\hat{A}(\mathbf{s}_{t}^{i},\mathbf{a}_{t}^{i}), where { ( 𝐬 0 i , 𝐚 0 i , r 0 i , 𝐬 1 i , … ) } i = 1 n \{(\mathbf{s}_{0}^{i},\mathbf{a}_{0}^{i},r_{0}^{i},\mathbf{s}_{1}^{i},\ldots)\}_{i=1}^{n} are n n trajectory samples from π β ​ ( τ ) {\pi_{\beta}}(\tau) ( Precup,, 2000 ; Precup et al.,, 2001 ; Peshkin and Shelton,, 2002 ) . Similarly, we can self-normalize the importance weights resulting in the weighted importance sampling policy gradient estimator ( Precup,, 2000 ) , which is biased, but can have much lower variance and is still a consistent estimator.

If we use the Monte Carlo estimator with baseline for A ^ \hat{A} (i.e., A ^ ​ ( 𝐬 t i , 𝐚 t i ) = ∑ t ′ = t H γ t ′ − t ​ r t ′ − b ⁡ ( 𝐬 t i ) \hat{A}(\mathbf{s}_{t}^{i},\mathbf{a}_{t}^{i})=\sum_{t^{\prime}=t}^{H}\gamma^{t^{\prime}-t}r_{t^{\prime}}-b(\mathbf{s}_{t}^{i}) ), then because r t r_{t} does not depend on 𝐬 t ′ \mathbf{s}_{t^{\prime}} and 𝐚 t ′ \mathbf{a}_{t^{\prime}} for t ′ > t t^{\prime}>t , we can drop importance weights in the future, resulting in the per-decision importance sampling policy gradient estimator ( Precup,, 2000 ) : ∇ θ J ​ ( π θ ) ≈ ∑ i = 1 n ∑ t = 0 H w t i ​ γ t ​ ( ∑ t ′ = t H γ t ′ − t ​ w t ′ i w t i ​ r t ′ − b ⁡ ( 𝐬 t i ) ) ​ ∇ θ ​ log ⁡ π θ ​ ( 𝐚 t i | 𝐬 t i ) . \nabla_{\theta}J(\pi_{\theta})\approx\sum_{i=1}^{n}\sum_{t=0}^{H}w_{t}^{i}\gamma^{t}\left(\sum_{t^{\prime}=t}^{H}\gamma^{t^{\prime}-t}\frac{w_{t^{\prime}}^{i}}{w_{t}^{i}}r_{t^{\prime}}-b(\mathbf{s}_{t}^{i})\right)\nabla_{\theta}\log\pi_{\theta}(\mathbf{a}_{t}^{i}|\mathbf{s}_{t}^{i}). As before, this estimator can have high variance, and we can form a weighted per-decision importance estimator by normalizing the weights. Paralleling the development of doubly robust estimators for policy evaluation, doubly robust estimators for the policy gradient have also been derived ( Gu et al., 2017a, ; Huang and Jiang,, 2019 ; Pankov,, 2018 ; Cheng et al.,, 2019 ) . Unfortunately, in many practical problems, these estimators have too high variance to be effective.

Practical off-policy algorithms derived from such estimators can also employ regularization, such that the learned policy π θ ​ ( 𝐚 | 𝐬 ) \pi_{\theta}(\mathbf{a}|\mathbf{s}) does not deviate too far from the behavior policy π β ​ ( 𝐚 | 𝐬 ) {\pi_{\beta}}(\mathbf{a}|\mathbf{s}) , thus keeping the variance of the importance weights from becoming too large. One example of such a regularizer is the soft max over the (unnormalized) importance weights ( Levine and Koltun,, 2013 ) . This regularized gradient estimator ∇ θ J ¯ ​ ( π θ ) \nabla_{\theta}\bar{J}(\pi_{\theta}) has the following form: ∇ θ J ¯ ​ ( π θ ) ≈ ( ∑ i = 1 n w H i ​ ∑ t = 0 H γ t ​ ∇ θ ​ log ⁡ π θ ​ ( 𝐚 t i | 𝐬 t i ) ​ A ^ ​ ( 𝐬 t i , 𝐚 t i ) ) + λ ​ log ⁡ ( ∑ i = 1 n w H i ) . \nabla_{\theta}\bar{J}(\pi_{\theta})\approx\left(\sum_{i=1}^{n}w_{H}^{i}\sum_{t=0}^{H}\gamma^{t}\nabla_{\theta}\log\pi_{\theta}(\mathbf{a}_{t}^{i}|\mathbf{s}_{t}^{i})\hat{A}(\mathbf{s}_{t}^{i},\mathbf{a}_{t}^{i})\right)+\lambda\log\left(\sum_{i=1}^{n}w_{H}^{i}\right). It is easy to check that ∑ i w H i → 1 \sum_{i}w_{H}^{i}\rightarrow 1 as n → ∞ n\rightarrow\infty , meaning that this gradient estimator is consistent. However, with a finite number of samples, such an estimator automatically adjusts the policy π θ \pi_{\theta} to ensure that at least one sample has a high (unnormalized) importance weight. More recent deep reinforcement learning algorithms based on importance sampling often employ a sample-based KL-divergence regularizer ( Schulman et al.,, 2017 ) , which has a functional form mathematically similar to this one when also utilizing an entropy regularizer on the policy π θ \pi_{\theta} .

### 3.3 Approximate Off-Policy Policy Gradients