Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems — part 7/12
Cleaned-text code points [88316, 102985). Bibliography omitted here; source.md includes it.
The first approach selects ϕ \phi such that the resulting linear Q-function satisfies the Bellman equation as closely as possible in terms of squared error, which can be obtained via the least squares solution. To derive the corresponding least squares problem, we first write the Bellman equation in terms of the Bellman operator, and expand it using the vectorized expression for the reward function, R → \vec{R} , and a linear operator representing the dynamics and policy backup, which we denote as P π P^{\pi} , such that ( P π Q → ) ( 𝐬 , 𝐚 ) = 𝔼 𝐬 ′ ∼ T ( 𝐬 ′ | 𝐬 , 𝐚 ) , 𝐚 ′ ∼ π ( 𝐚 ′ | 𝐬 ′ ) [ Q ( 𝐬 ′ , 𝐚 ′ ) ] (P^{\pi}\vec{Q})(\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})}[Q(\mathbf{s}^{\prime},\mathbf{a}^{\prime})] . The corresponding expression of the Bellman equation is given by 𝐅 ϕ ≈ ℬ π 𝐅 ϕ = R → + γ P π 𝐅 ϕ ⟹ ( 𝐅 − γ P π 𝐅 ) ϕ ≈ R → . \mathbf{F}\phi\approx\mathcal{B}^{\pi}\mathbf{F}\phi=\vec{R}+\gamma P^{\pi}\mathbf{F}\phi\implies\left(\mathbf{F}-\gamma P^{\pi}\mathbf{F}\right)\phi\approx\vec{R}. Writing out the least squares solution using the normal equations, we obtain ϕ = ( ( 𝐅 − γ P π 𝐅 ) T ( 𝐅 − γ P π 𝐅 ) ) − 1 ( 𝐅 − γ P π 𝐅 ) T R → . \phi=\left((\mathbf{F}-\gamma P^{\pi}\mathbf{F})^{T}(\mathbf{F}-\gamma P^{\pi}\mathbf{F})\right)^{-1}(\mathbf{F}-\gamma P^{\pi}\mathbf{F})^{T}\vec{R}. This expression minimizes the ℓ 2 \ell_{2} norm of the Bellman residual (the squared difference between the left-hand side and right-hand side of the Bellman equation), and is referred to as the Bellman residual minimizing solution.
#### Least-squares fixed point approximation.
An alternate approach is use projected fixed-point iteration, rather than direct minimization of the Bellman error, which gives rise to the least-squares fixed point approximation. In this approach, instead of minimizing the squared difference between the left-hand side and right-hand side of the Bellman equation, we instead attempt to iterate the Bellman operator to convergence. In the tabular case, as discussed in Section 2.1 , we know that iterating Q → k + 1 ← ℬ π Q → k \vec{Q}_{k+1}\leftarrow\mathcal{B}^{\pi}\vec{Q}_{k} converges, as k → ∞ k\rightarrow\infty , to Q → π \vec{Q}^{\pi} . In the case where we use function approximation to represent Q → k \vec{Q}_{k} , we cannot set Q → k + 1 \vec{Q}_{k+1} to ℬ π Q → k \mathcal{B}^{\pi}\vec{Q}_{k} precisely, because there may not be any value of the weights ϕ \phi that represent ℬ π Q → k \mathcal{B}^{\pi}\vec{Q}_{k} exactly. We therefore must employ a projected fixed point iteration method, where each iterate ℬ π Q → k = ℬ π 𝐅 ϕ k \mathcal{B}^{\pi}\vec{Q}_{k}=\mathcal{B}^{\pi}\mathbf{F}\phi_{k} is projected onto the span of 𝐅 \mathbf{F} to obtain ϕ k + 1 \phi_{k+1} . We can express this projection via a projection operator, Π \Pi , such that the projected Bellman iteration is given by Q → k + 1 = Π ℬ π Q → k \vec{Q}_{k+1}=\Pi\mathcal{B}^{\pi}\vec{Q}_{k} . We can obtain a solution for this operator by solving the normal equation, and observe that Π = 𝐅 ( 𝐅 T 𝐅 ) − 1 𝐅 T \Pi=\mathbf{F}(\mathbf{F}^{T}\mathbf{F})^{-1}\mathbf{F}^{T} . We can expand out the projected Bellman iteration expression as: Q → k + 1 \displaystyle\vec{Q}_{k+1} = 𝐅 ( 𝐅 T 𝐅 ) − 1 𝐅 T ( R → + γ P π Q → k ) \displaystyle=\mathbf{F}(\mathbf{F}^{T}\mathbf{F})^{-1}\mathbf{F}^{T}(\vec{R}+\gamma P^{\pi}\vec{Q}_{k}) 𝐅 ϕ k + 1 \displaystyle\mathbf{F}\phi_{k+1} = 𝐅 ( 𝐅 T 𝐅 ) − 1 𝐅 T ( R → + γ P π 𝐅 ϕ k ) \displaystyle=\mathbf{F}(\mathbf{F}^{T}\mathbf{F})^{-1}\mathbf{F}^{T}(\vec{R}+\gamma P^{\pi}\mathbf{F}\phi_{k}) ϕ k + 1 \displaystyle\phi_{k+1} = ( 𝐅 T 𝐅 ) − 1 𝐅 T ( R → + γ P π 𝐅 ϕ k ) . \displaystyle=(\mathbf{F}^{T}\mathbf{F})^{-1}\mathbf{F}^{T}(\vec{R}+\gamma P^{\pi}\mathbf{F}\phi_{k}). (18) By repeatedly applying this recurrence, we can obtain the fixed point of the projected Bellman operator as k → ∞ k\rightarrow\infty ( Sutton et al.,, 2009 ) .
Both methods have been used in the literature, and there is no clear consensus on which approach is preferred, though they yield different solutions in general when the true Q-function Q π Q^{\pi} is not in the span of 𝐅 \mathbf{F} (i.e., cannot be represented by any parameter vector ϕ \phi ) ( Lagoudakis and Parr,, 2003 ) . We might at first surmise that a good linear fitting method should find the Q-function 𝐅 ϕ \mathbf{F}\phi that corresponds to a least-squares projection of the true Q → π \vec{Q}^{\pi} onto the hyperplane defined by 𝐅 \mathbf{F} . Unfortunately, neither the Bellman residual minimization method nor the least-squares fixed point method in general obtains this solution. The Bellman residual minimization does not in general produce a fixed point of either the Bellman operator or the projected Bellman operator. However, the solution obtained via Bellman residual minimization may be closer to the true Q-function in terms of ℓ 2 \ell_{2} distance, since it is explicitly obtained by minimizing Bellman residual error. Least-squares fixed point iteration obtains a Q-function that is a fixed point of the projected Bellman operator, but may be arbitrarily suboptimal. However, least-squares fixed point iteration can learn solutions that lead, empirically, to better-performing policies ( Sutton et al.,, 2009 ; Lagoudakis and Parr,, 2003 ) . In general, there are no theoretical arguments that justify the superiority of one approach over the other. In practice, least-squares fixed-point iteration can give rise to more effective policies as compared to the Bellman residual, while the Bellman residual minimization approach can be more stable and predictable ( Lagoudakis and Parr,, 2003 ) .
#### Least squares temporal difference Q-learning (LSTD-Q).
Now that we have covered different approaches to solve a linear system of equations to obtain an approximation to Q π Q^{\pi} , we describe LSTD-Q, a method for estimating Q π Q^{\pi} from a static dataset, directly from samples. This method incrementally estimates the terms 𝐅 T ( 𝐅 − γ P π 𝐅 ) \mathbf{F}^{T}(\mathbf{F}-\gamma P^{\pi}\mathbf{F}) and 𝐅 T R → \mathbf{F}^{T}\vec{R} , which appear in Equation ( 18 ), and then inverts this sampled estimate to then obtain ϕ \phi . We defer further discussion on LSTD-Q to Lagoudakis and Parr, (2003) , which also describes several computationally efficient implementations of the LSTD-Q algorithm. Note that the LSTD-Q algorithm is not directly applicable to estimating Q ∗ Q^{*} , the optimal Q-function, since the optimal Bellman equation for Q ∗ Q^{*} is not linear due to the maximization, and thus cannot be solved in closed form.
#### Least squares policy iteration (LSPI).
Finally, we discuss least-squares policy iteration (LSPI), a classical offline reinforcement learning algorithm that performs approximate policy iteration (see discussion in Section 2.1 ) using a linear approximation to the Q-function. LSPI uses LSTD-Q as an intermediate sub-routine to perform approximate policy evaluation, thereby obtaining an estimate for Q π Q^{\pi} , denoted Q ϕ Q_{\phi} . Then, the algorithm sets the next policy iterate to be equal to the greedy policy corresponding to the approximate Q ϕ Q_{\phi} , such that π k + 1 ( 𝐚 | 𝐬 ) = δ ( 𝐚 = arg max 𝐚 Q ϕ ( 𝐬 , 𝐚 ) ) \pi_{k+1}(\mathbf{a}|\mathbf{s})=\delta(\mathbf{a}=\arg\max_{\mathbf{a}}Q_{\phi}(\mathbf{s},\mathbf{a})) . An important and useful characteristic of LSPI is that it does not require a separate approximate representation for the policy when the actions are discrete, and hence removes any source of error that arises due to function approximation in the actor in actor-critic methods. However, when the action space is continuous, a policy gradient method similar to the generic actor-critic algorithm in Algorithm 3 can be used to optimize a parametric policy.
### 4.2 Distributional Shift in Offline Reinforcement Learning via Dynamic Programming
Both the linear and non-linear dynamic programming methods discussed so far, in Section 2.1 and Section 4.1 above, can in principle learn from offline data, collected according to a different (unknown) behavioral policy π β ( 𝐚 | 𝐬 ) {\pi_{\beta}}(\mathbf{a}|\mathbf{s}) , with state visitation frequency d π β ( 𝐬 ) d^{{\pi_{\beta}}}(\mathbf{s}) . However, in practice, these procedures can result in very poor performance, due to the distributional shift issues alluded to in Section 2.4 .
Distributional shift affects offline reinforcement learning via dynamic programming both at test time and at training time. At test time, the state visitation frequency d π ( 𝐬 ) d^{\pi}(\mathbf{s}) induced by a policy trained with offline RL will differ systematically from the state visitation frequency of the training data, d π β ( 𝐬 ) d^{{\pi_{\beta}}}(\mathbf{s}) . This means that, as in the case of policy gradients, a policy trained via an actor-critic method may produce unexpected and erroneous actions in out-of-distribution states 𝐬 ∼ d π β ( 𝐬 ) \mathbf{s}\sim d^{{\pi_{\beta}}}(\mathbf{s}) , as can the implicit greedy policy induced by a Q-function in a Q-learning method. One way to mitigate this distributional shift is to limit how much the learned policy can diverge from the behavior policy. For example, by constraining π ( 𝐚 | 𝐬 ) \pi(\mathbf{a}|\mathbf{s}) such that D KL ( π ( 𝐚 | 𝐬 ) ∥ π β ( 𝐚 | 𝐬 ) ) ≤ ϵ D_{\text{KL}}(\pi(\mathbf{a}|\mathbf{s})\|{\pi_{\beta}}(\mathbf{a}|\mathbf{s}))\leq\epsilon , we can bound D KL ( d π ( 𝐬 ) ∥ d π β ( 𝐬 ) ) D_{\text{KL}}(d^{\pi}(\mathbf{s})\|d^{{\pi_{\beta}}}(\mathbf{s})) by δ \delta , which is O ( ϵ / ( 1 − γ ) 2 ) O(\epsilon/(1-\gamma)^{2}) ( Schulman et al.,, 2015 ) . This bound is very loose in practice, but nonetheless suggests that the effects of state distribution shift can potentially be mitigated by bounding how much the learned policy can deviate from the behavior policy that collected the offline training data. This may come at a substantial cost in final performance however, as the behavior policy – and any policy that is close to it – may be much worse than the best policy that can be learned from the offline data.
It should be noted that, for the algorithms discussed previously, state distribution shift affects test-time performance, but has no effect on training, since neither the policy nor the Q-function is ever evaluated at any state that was not sampled from d π β ( 𝐬 ) d^{{\pi_{\beta}}}(\mathbf{s}) . However, the training process is affected by action distribution shift, because the target values for the Bellman backups in Equation ( 3 ) depend on 𝐚 t + 1 ∼ π ( 𝐚 t + 1 | 𝐬 t + 1 ) \mathbf{a}_{t+1}\sim\pi(\mathbf{a}_{t+1}|\mathbf{s}_{t+1}) . While this source of distribution shift may at first seem insignificant, it in fact presents one of the largest obstacles for practical application of approximate dynamic programming methods to offline reinforcement learning. Since computing the target values in Equation ( 3 ) requires evaluating Q π ( 𝐬 t + 1 , 𝐚 t + 1 ) Q^{\pi}(\mathbf{s}_{t+1},\mathbf{a}_{t+1}) , where 𝐚 t + 1 ∼ π ( 𝐚 t + 1 | 𝐬 t + 1 ) \mathbf{a}_{t+1}\sim\pi(\mathbf{a}_{t+1}|\mathbf{s}_{t+1}) , the accuracy of the Q-function regression targets depends on the estimate of the Q-value for actions that are outside of the distribution of actions that the Q-function was ever trained on. When π ( 𝐚 | 𝐬 ) \pi(\mathbf{a}|\mathbf{s}) differs substantially from π β ( 𝐚 | 𝐬 ) {\pi_{\beta}}(\mathbf{a}|\mathbf{s}) , this discrepancy can result in highly erroneous target Q-values. This issue is further exacerbated by the fact that π ( 𝐚 | 𝐬 ) \pi(\mathbf{a}|\mathbf{s}) is explicitly optimized to maximize 𝔼 𝐚 ∼ π ( 𝐚 | 𝐬 ) [ Q π ( 𝐬 , 𝐚 ) ] \mathbb{E}_{\mathbf{a}\sim\pi(\mathbf{a}|\mathbf{s})}[Q^{\pi}(\mathbf{s},\mathbf{a})] . This means that, if the policy can produce out-of-distribution actions for which the learned Q-function erroneously produces excessively large values, it will learn to do so. This is true whether the policy is represented explicitly, as in actor-critic algorithms, or implicitly, as the greedy policy π ( 𝐚 | 𝐬 ) = δ ( 𝐚 = arg max 𝐚 ′ Q π ( 𝐬 , 𝐚 ′ ) ) \pi(\mathbf{a}|\mathbf{s})=\delta(\mathbf{a}=\arg\max_{\mathbf{a}^{\prime}}Q^{\pi}(\mathbf{s},\mathbf{a}^{\prime})) . In standard online reinforcement learning, such issues are corrected naturally when the policy acts in the environment, attempting the transitions it (erroneously) believes to be good, and observing that in fact they are not. However, in the offline setting, the policy cannot correct such over-optimistic Q-values, and these errors accumulate over each iteration of training, resulting in arbitrarily poor final results.
This problem manifests itself in practice as an “unlearning” effect when running offline RL via dynamic programming. The experiments in Figure 2 , from Kumar et al., (2019) , show this unlearning effect. The horizontal axis corresponds to the number of gradient updates to the Q-function, and the vertical axis shows the actual return obtained by running the greedy policy for the learned Q-function. The learning curve resembles what we might expect in the case of overfitting: the return first improves, and then sharply falls as training progresses. However, this “overfitting” effect remains even as we increase the size of the dataset, suggesting that the phenomenon is distinct from classic statistical overfitting. As the Q-function is trained longer and longer, the target values become more and more erroneous, and the entire Q-function degrades.
Thus, to effectively implement offline reinforcement learning via dynamic programming, it is crucial to address this out-of-distribution action problem. Previous works have observed several variants of this problem. Fujimoto et al., (2018) noted that restricting Q-value evaluation only to actions in the dataset avoids erroneous Q-values due to extrapolation error. Kumar et al., (2019) described the out-of-distribution action problem in terms of distributional shift, which suggests a less restrictive solution based on limiting distributional shift, rather than simply constraining to previously seen actions. A number of more recent works also observe that a variety of constraints can be used to mitigate action distribution shift ( Wu et al., 2019a, ) . We provide a unified view of such “policy constraint” methods in the following section.
### 4.3 Policy Constraints for Off-Policy Evaluation and Improvement