Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems — part 6/12
Cleaned-text code points [72743, 88316). Bibliography omitted here; source.md includes it.
Nachum et al., 2019a () develop similar ideas for off-policy evaluation. The key idea is to devise a convex optimization problem with ρ π \rho^{\pi} as its optimal solution. The chosen optimization problem is ρ π = arg min x : 𝒮 × 𝒜 → ℝ 1 2 𝔼 𝐬 , 𝐚 , 𝐬 ′ ∼ 𝒟 [ x ( 𝐬 , 𝐚 ) 2 ] − 𝔼 𝐬 ∼ d π ( 𝐬 ) , 𝐚 ∼ π ( 𝐚 | 𝐬 ) [ x ( 𝐬 , 𝐚 ) ] . \rho^{\pi}=\arg\min_{x:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}}~~\frac{1}{2}\mathbb{E}_{\mathbf{s},\mathbf{a},\mathbf{s}^{\prime}\sim\mathcal{D}}\left[x(\mathbf{s},\mathbf{a})^{2}\right]-\mathbb{E}_{\mathbf{s}\sim d^{\pi}(\mathbf{s}),\mathbf{a}\sim\pi(\mathbf{a}|\mathbf{s})}\left[x(\mathbf{s},\mathbf{a})\right]. (13) Unfortunately, this objective requires samples from the on-policystate-marginal distribution, d π ( 𝐬 ) d^{\pi}(\mathbf{s}) . The key insight is a change of variables, x ( s , a ) = ν ( 𝐬 , 𝐚 ) − 𝔼 𝐬 ′ ∼ T ( 𝐬 ′ | 𝐬 , 𝐚 ) , 𝐚 ′ ∼ π ( 𝐚 ′ | 𝐬 ′ ) [ ν ( 𝐬 ′ , 𝐚 ′ ) ] x(s,a)=\nu(\mathbf{s},\mathbf{a})-\mathbb{E}_{\mathbf{s}^{\prime}\sim T(\mathbf{s}^{\prime}|\mathbf{s},\mathbf{a}),\mathbf{a}^{\prime}\sim\pi(\mathbf{a}^{\prime}|\mathbf{s}^{\prime})}[\nu(\mathbf{s}^{\prime},\mathbf{a}^{\prime})] and introduce the variable ν ( 𝐬 , 𝐚 ) \nu(\mathbf{s},\mathbf{a}) to simplify the expression in Equation 13 , and obtain the “backward” dynamic programming procedure shown in Equation 14 . For brevity, we define a modified Bellman operator, ℬ ~ π ν ( 𝐬 , 𝐚 ) := 𝔼 𝐬 ′ ∼ T ( 𝐬 ′ | 𝐬 , 𝐚 ) , 𝐚 ′ ∼ π ( 𝐚 ′ | 𝐬 ′ ) [ ν ( 𝐬 ′ , 𝐚 ′ ) ] \tilde{\mathcal{B}}^{\pi}\nu(\mathbf{s},\mathbf{a}):=\mathbb{E}_{\mathbf{s}^{\prime}\sim T(\mathbf{s}^{\prime}|\mathbf{s},\mathbf{a}),\mathbf{a}^{\prime}\sim\pi(\mathbf{a}^{\prime}|\mathbf{s}^{\prime})}[\nu(\mathbf{s}^{\prime},\mathbf{a}^{\prime})] , that is similar to the expression for ℬ π \mathcal{B}^{\pi} without the reward term r ( s , a ) r(s,a) . min ν : 𝒮 × 𝒜 → ℝ 1 2 𝔼 𝐬 , 𝐚 , 𝐬 ′ ∼ 𝒟 [ ( ν ( 𝐬 , 𝐚 ) − ℬ ~ π ν ( 𝐬 , 𝐚 ) ) 2 ] − 𝔼 𝐬 0 ∼ d 0 ( 𝐬 0 ) , 𝐚 ∼ π ( 𝐚 | 𝐬 0 ) [ ν ( 𝐬 0 , 𝐚 ) ] . \min_{\nu:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}}~~\frac{1}{2}\mathbb{E}_{\mathbf{s},\mathbf{a},\mathbf{s}^{\prime}\sim\mathcal{D}}\left[\left(\nu(\mathbf{s},\mathbf{a})-\tilde{\mathcal{B}}^{\pi}\nu(\mathbf{s},\mathbf{a})\right)^{2}\right]-\mathbb{E}_{\mathbf{s}_{0}\sim d_{0}(\mathbf{s}_{0}),\mathbf{a}\sim\pi(\mathbf{a}|\mathbf{s}_{0})}\left[\nu(\mathbf{s}_{0},\mathbf{a})\right]. (14) Remarkably, Equation 14 does not require on-policy samples to evaluate. Given an optimal solution for the objective in Equation 14 , denoted as ν ∗ \nu^{*} , we can obtain the density ratio, ρ π \rho^{\pi} , using the relation, ρ π ( 𝐬 , 𝐚 ) = ν ∗ ( 𝐬 , 𝐚 ) − ℬ ~ π ν ∗ ( 𝐬 , 𝐚 ) \rho^{\pi}(\mathbf{s},\mathbf{a})=\nu^{*}(\mathbf{s},\mathbf{a})-\tilde{\mathcal{B}}^{\pi}\nu^{*}(\mathbf{s},\mathbf{a}) . The density ratio can then be used for off-policy evaluation and improvement.
Nachum et al., 2019b () ; Nachum and Dai, (2020) build on a similar framework to devise an off-policy RL algorithm. The key idea is to obtain an estimate of the on-policy policy gradient for a state-marginal regularized RL objective by solving an optimization problem. The regularizer applied in this family of methods is the f-divergence between the state(-action) marginal of the learned policy and the state-action marginal of the dataset. We will cover f-divergences in detail in Section 4 . The f-divergence regularized RL problem, with a tradeoff factor, α \alpha , is given by: max π 𝔼 𝐬 ∼ d π ( 𝐬 ) , 𝐚 ∼ π ( ⋅ | 𝐬 ) [ r ( 𝐬 , 𝐚 ) ] − α D f ( d π ( 𝐬 , 𝐚 ) , d π β ( 𝐬 , 𝐚 ) ) . \max_{\pi}~~\mathbb{E}_{\mathbf{s}\sim d^{\pi}(\mathbf{s}),\mathbf{a}\sim\pi(\cdot|\mathbf{s})}\left[r(\mathbf{s},\mathbf{a})\right]-\alpha D_{f}(d^{\pi}(\mathbf{s},\mathbf{a}),d^{\pi_{\beta}}(\mathbf{s},\mathbf{a})). (15) By exploiting the variational (dual) form of the f-divergence shown below D f ( p , q ) = max x : 𝒮 × 𝒜 → ℝ ( 𝔼 𝐲 ∼ p ( 𝐲 ) [ x ( 𝐲 ) ] − 𝔼 𝐲 ∼ q ( 𝐲 ) [ f ∗ ( x ( 𝐲 ) ) ] ) , D_{f}(p,q)=\max_{x:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}}\left(\mathbb{E}_{\mathbf{y}\sim p(\mathbf{y})}[x(\mathbf{y})]-\mathbb{E}_{\mathbf{y}\sim q(\mathbf{y})}[f^{*}(x(\mathbf{y}))]\right), (16) and then applying a change of variables from x x to Q Q (c.f., ( Nachum et al., 2019a, ) ) where Q Q satisfies Q ( 𝐬 , 𝐚 ) = 𝔼 𝐬 ′ ∼ T ( 𝐬 , 𝐚 ) , 𝐚 ′ ∼ π ( 𝐚 ′ | 𝐬 ′ ) [ r ( 𝐬 , 𝐚 ) − α x ( 𝐬 , 𝐚 ) + γ Q ( 𝐬 ′ , 𝐚 ′ ) ] Q(\mathbf{s},\mathbf{a})=\mathbb{E}_{\mathbf{s}^{\prime}\sim T(\mathbf{s},\mathbf{a}),\mathbf{a}^{\prime}\sim\pi(\mathbf{a}^{\prime}|\mathbf{s}^{\prime})}\left[r(\mathbf{s},\mathbf{a})-\alpha x(\mathbf{s},\mathbf{a})+\gamma Q(\mathbf{s}^{\prime},\mathbf{a}^{\prime})\right] , we obtain a saddle-point optimization problem for optimizing the regularized RL objective, max π min Q \displaystyle\max_{\pi}~\min_{Q} L ( Q , π β , π ) ≔ 𝔼 𝐬 0 ∼ d 0 ( 𝐬 0 ) , 𝐚 ∼ π ( ⋅ | 𝐬 0 ) [ Q ( 𝐬 0 , 𝐚 ) ] \displaystyle~~L(Q,{\pi_{\beta}},\pi)\coloneqq\mathbb{E}_{\mathbf{s}_{0}\sim d_{0}(\mathbf{s}_{0}),\mathbf{a}\sim\pi(\cdot|\mathbf{s}_{0})}\left[Q(\mathbf{s}_{0},\mathbf{a})\right] + α 𝔼 𝐬 , 𝐚 ∼ d π β ( 𝐬 , 𝐚 ) [ f ∗ ( r ( 𝐬 , 𝐚 ) + γ 𝔼 𝐬 ′ ∼ T ( 𝐬 , 𝐚 ) , 𝐚 ′ ∼ π ( 𝐚 ′ | 𝐬 ′ ) [ Q ( 𝐬 ′ , 𝐚 ′ ) ] − Q ( 𝐬 , 𝐚 ) α ) ] . \displaystyle~~~~~~~~+\alpha\mathbb{E}_{\mathbf{s},\mathbf{a}\sim d^{\pi_{\beta}}(\mathbf{s},\mathbf{a})}\left[f^{*}\left(\frac{r(\mathbf{s},\mathbf{a})+\gamma\mathbb{E}_{\mathbf{s}^{\prime}\sim T(\mathbf{s},\mathbf{a}),\mathbf{a}^{\prime}\sim\pi(\mathbf{a}^{\prime}|\mathbf{s}^{\prime})}[Q(\mathbf{s}^{\prime},\mathbf{a}^{\prime})]-Q(\mathbf{s},\mathbf{a})}{\alpha}\right)\right]. When f ( x ) = x 2 f(x)=x^{2} , f ∗ ( x ) = x 2 f^{*}(x)=x^{2} and this objective reduces to applying a regular actor-critic algorithm as discussed in Section 2.1 along with an additional term minimizing Q-values at the initial state 𝐬 0 \mathbf{s}_{0} .
It can also be shown that the derivative with respect to the policy of L ( Q ∗ , π β , π ) L(Q^{*},{\pi_{\beta}},\pi) , at the optimal Q-function, Q ∗ Q^{*} , is precisely equal to the on-policy policy gradient in the regularized policy gradient problem: ∂ ∂ π L ( Q ∗ , π β , π ) = 𝔼 𝐬 ∼ d π ( 𝐬 ) , 𝐚 ∼ π ( ⋅ | 𝐬 ) [ Q ~ π ( 𝐬 , 𝐚 ) ⋅ ∇ π log π ( 𝐚 | 𝐬 ) ] , \frac{\partial}{\partial\pi}L(Q^{*},{\pi_{\beta}},\pi)=\mathbb{E}_{\mathbf{s}\sim d^{\pi}(\mathbf{s}),\mathbf{a}\sim\pi(\cdot|\mathbf{s})}\left[\tilde{Q}^{\pi}(\mathbf{s},\mathbf{a})\cdot\nabla_{\pi}\log\pi(\mathbf{a}|\mathbf{s})\right], (17) where Q ~ π \tilde{Q}^{\pi} is the action-value function corresponding to the regularized RL problem.
Finally, we note that this is a rapidly developing area and recent results suggest that many of these methods can be unified under a single framework ( Tang et al.,, 2019 ; Nachum and Dai,, 2020 ) .
### 3.5 Challenges and Open Problems
The methods discussed in this section utilize some form of importance sampling to either estimate the return of the current policy π θ \pi_{\theta} , or estimate the gradient of this return. The policy improvement methods discussed in this section have been developed primarily for a classic off-policy learning setting, where additional data is collected online, but previously collected data is reused to improve efficiency. To the best of our knowledge, such methods have not generally been applied in the offline setting, with the exception of the evaluation and high-confidence improvement techniques in Section 3.1 .
Applying such methods in the fully offline setting poses a number of major challenges. First, importance sampling already suffer from high variance, and this variance increases dramatically in the sequential setting, since the importance weights at successive time steps are multiplied together (see, e.g., Equation ( 5 )), resulting in exponential blowup. Approximate and marginalized importance sampling methods alleviate this issue to some degree by avoiding multiplication of importance weights over multiple time steps, but the fundamental issue still remains: when the behavior policy π β {\pi_{\beta}} is too different from the current learned policy π θ \pi_{\theta} , the importance weights will become degenerate, and any estimate of the return or the gradient will have too much variance to be usable, especially in high-dimensional state and action spaces, or for long-horizon problems. For this reason, importance-sampled estimators are most suitable in the case where the policy only deviates by a limited amount from the behavior policy. In the classic off-policy setting, this is generally the case, since new trajectories are repeatedly collected and added to the dataset using the latest policy, but in the offline setting this is generally not the case. Thus, the maximum improvement that can be reliably obtained via importance sampling is limited by (i) the suboptimality of the behavior policy; (ii) the dimensionality of the state and action space; (iii) the effective horizon of the task. The second challenge is that the most effective of these off-policy policy gradient methods either requires estimating the value function, or the state-marginal density ratios via dynamic programming. As several prior works have shown, and as we will review in Section 4 , dynamic programming methods suffer from issues pertaining to out-of-distribution queries in completely offline settings, making it hard to stably learn the value function without additional corrections. This problem is not as severe in the classic off-policy setting, which allows additional data collection. Nonetheless, as we will discussion in Section 6 , a number of prior applications have effectively utilized importance sampling in an offline setting.
## 4 Offline Reinforcement Learning via Dynamic Programming
Dynamic programming methods, such as Q-learning algorithms, in principle can offer a more attractive option for offline reinforcement learning as compared to pure policy gradients. As discussed in Section 2.1 , dynamic programming methods aim to learn a state or state-action value function, and then either use this value function to directly recover the optimal policy or, as in the case of actor-critic methods, use this value function to estimate a gradient for the expected returns of a policy. Basic offline dynamic programming algorithms can be constructed on the basis of fitted Q-learning methods ( Ernst et al.,, 2005 ; Riedmiller,, 2005 ; Hafner and Riedmiller,, 2011 ) , as well as policy iteration methods ( Sutton and Barto,, 1998 ) . The generic Q-learning and actor-critic algorithms presented in Algorithm 2 and Algorithm 3 in Section 2.1 can in principle be utilized as offline reinforcement learning, simply by setting the number of collection steps S S to zero, and initializing the buffer to be non-empty. Such algorithms can be viable for offline RL, and indeed have been used as such even in recent deep reinforcement learning methods. We will discuss an older class of sucm methods, based on linear function approximation, in Section 4.1 , but such techniques have also been used effectively with deep neural network function approximators. For example, Kalashnikov et al., (2018) describes a Q-learning algorithm called QT-Opt that was able to learn effective vision-based robotic grasping strategies from about 500,000 grasping trials logged over the course of previous experiments, but observes that additional online fine-tuning still improved the performance of the policy considerably over the one trained purely from logged data. Some prior works on offline RL have also noted that, for some types of datasets, conventional dynamic programming algorithms, such as deep Q-learning or deterministic actor-critic algorithms, can in fact work reasonably well ( Agarwal et al.,, 2019 ) .
However, as we will discuss in Section 4.2 , such methods suffer from a number of issues when all online collection is halted, and only offline data is used. These issues essentially amount to distributional shift, as discussed in Section 2.4 . Solutions to this issue can be broadly grouped into two categories: policy constraint methods, discussed in Section 4.3 , which constrain the learned policy π \pi to lie close to the behavior policy π β {\pi_{\beta}} , thus mitigating distributional shift, and uncertainty-based methods, discussed in Section 4.4 , which attempt to estimate the epistemic uncertainty of Q-values, and then utilize this uncertainty to detect distributional shift. We will discuss both classes of distributional shift corrections, and then conclude with perspectives on remaining challenges and open problems in Section 4.6 .
### 4.1 Off-Policy Value Function Estimation with Linear Value Functions
We first discuss standard offline reinforcement learning methods based on value function and policy estimation with linear function approximators, which do not by themselves provide any mitigate for distributional shift, but can work well when good linear features are available. While modern deep reinforcement learning methods generally eschew linear features in favor of non-linear neural network function approximators, linear methods constitute an important class of offline reinforcement learning algorithms in the literature ( Lange et al.,, 2012 ; Lagoudakis and Parr,, 2003 ) . We begin with algorithms that use a linear function to approximate the Q-function, such that Q ϕ ≈ 𝐟 ( s , a ) T ϕ Q_{\phi}\approx\mathbf{f}(s,a)^{T}\phi , where 𝐟 ( s , a ) ∈ ℝ d \mathbf{f}(s,a)\in\mathbb{R}^{d} is a feature vector associated with a state-action pair. This parametric Q-function can then be estimated for a given policy π ( 𝐚 | 𝐬 ) \pi(\mathbf{a}|\mathbf{s}) using data from a different behavior policy π β ( 𝐚 | 𝐬 ) {\pi_{\beta}}(\mathbf{a}|\mathbf{s}) , with state visitation frequency d π β ( 𝐬 ) d^{{\pi_{\beta}}}(\mathbf{s}) . As discussed in Section 2.1 , the Q-function Q π Q^{\pi} for a given policy π ( 𝐚 | 𝐬 ) \pi(\mathbf{a}|\mathbf{s}) must satisfy the Bellman equation, given in full in Equation ( 3 ), and written in Bellman operator notation as Q π → = ℬ π Q π → \vec{Q^{\pi}}=\mathcal{B}^{\pi}\vec{Q^{\pi}} .
When linear function approximation is used to represent the Q-function, the Q-function for a policy can be represented as the solution of a linear system, and hence can be computed via least squares minimization, since the Bellman operator ℬ π \mathcal{B}^{\pi} is linear. This provides a convenient way to compute Q π Q^{\pi} directly in closed form, as compared to using gradient descent in Algorithm 3 . The resulting Q-value estimates can then be used to improve the policy. We start with a discussion of different ways of solving the linear system for computing Q π Q^{\pi} . To recap, the Q-function is a linear function on a feature vector 𝐟 ( 𝐬 , 𝐚 ) \mathbf{f}(\mathbf{s},\mathbf{a}) , which we can express in tabular form as 𝐅 ∈ ℝ | S | | A | × d \mathbf{F}\in\mathbb{R}^{|S||A|\times d} , such that Q → ϕ = 𝐅 ϕ \vec{Q}_{\phi}=\mathbf{F}\phi . Multiple procedures that can be used to obtain a closed form expression for the optimal ϕ \phi for a given policy π \pi and, as discussed in by Sutton et al., (2009) and Lagoudakis and Parr, (2003) , these procedures may each yield different solutions under function approximation. We first summarize two methods for selecting ϕ \phi to approximate Q π Q^{\pi} for a given policy π \pi , and then discuss how to utilize these methods in a complete reinforcement learning method.
#### Bellman residual minimization.