Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems — part 5/12
Cleaned-text code points [59638, 72743). Bibliography omitted here; source.md includes it.
The importance-weighted policy objective requires multiplying per-action importance weights over the time steps, which leads to very high variance. We can derive an approximate importance-sampled gradient by using the state distribution of the behavior policy, d π β ( 𝐬 ) d^{\pi_{\beta}}(\mathbf{s}) , in place of that of the current policy, d π ( 𝐬 ) d^{\pi}(\mathbf{s}) . This results in a biased gradient due to the mismatch in state distributions, but can provide reasonable learning performance in practice. The corresponding objective, which we will denote J π β ( π θ ) J_{\pi_{\beta}}(\pi_{\theta}) to emphasize its dependence on the behavior policy’s state distribution, is given by J π β ( π θ ) = 𝔼 𝐬 ∼ d π β ( 𝐬 ) [ V π ( 𝐬 ) ] . J_{\pi_{\beta}}(\pi_{\theta})=\mathbb{E}_{\mathbf{s}\sim d^{\pi_{\beta}}(\mathbf{s})}\left[V^{\pi}(\mathbf{s})\right]. Note that J π β ( π θ ) J_{\pi_{\beta}}(\pi_{\theta}) and J ( π θ ) J(\pi_{\theta}) differ in the distribution of states under which the return is estimated ( d π β ( 𝐬 ) d^{\pi_{\beta}}(\mathbf{s}) vs. d π ( 𝐬 ) d^{\pi}(\mathbf{s}) ), making J π β ( π θ ) J_{\pi_{\beta}}(\pi_{\theta}) a biased estimator for J ( π θ ) J(\pi_{\theta}) . This may lead to suboptimal solutions in certain cases (see Imani et al., (2018) for some examples). However, expectations under state distributions from d π β ( 𝐬 ) d^{\pi_{\beta}}(\mathbf{s}) can be calculated easily by sampling states from the dataset 𝒟 \mathcal{D} in the offline case, removing the need for importance sampling.
Recent empirical work has found that this bias is acceptable in practice ( Fu et al.,, 2019 ) . Differentiating the objective and applying a further approximation results in the off-policy policy gradient ( Degris et al.,, 2012 ) : ∇ θ J π β ( π θ ) \displaystyle\nabla_{\theta}J_{\pi_{\beta}}(\pi_{\theta}) = 𝔼 𝐬 ∼ d π β ( 𝐬 ) , 𝐚 ∼ π θ ( 𝐚 | 𝐬 ) [ Q π θ ( 𝐬 , 𝐚 ) ∇ θ log π θ ( 𝐚 | 𝐬 ) + ∇ θ Q π θ ( 𝐬 , 𝐚 ) ] \displaystyle=\mathbb{E}_{\mathbf{s}\sim d^{\pi_{\beta}}(\mathbf{s}),\mathbf{a}\sim\pi_{\theta}(\mathbf{a}|\mathbf{s})}\left[Q^{\pi_{\theta}}(\mathbf{s},\mathbf{a})\nabla_{\theta}\log\pi_{\theta}(\mathbf{a}|\mathbf{s})+\nabla_{\theta}Q^{\pi_{\theta}}(\mathbf{s},\mathbf{a})\right] ≈ 𝔼 𝐬 ∼ d π β ( 𝐬 ) , 𝐚 ∼ π θ ( 𝐚 | 𝐬 ) [ Q π θ ( 𝐬 , 𝐚 ) ∇ θ log π θ ( 𝐚 | 𝐬 ) ] . \displaystyle\approx\mathbb{E}_{\mathbf{s}\sim d^{\pi_{\beta}}(\mathbf{s}),\mathbf{a}\sim\pi_{\theta}(\mathbf{a}|\mathbf{s})}\left[Q^{\pi_{\theta}}(\mathbf{s},\mathbf{a})\nabla_{\theta}\log\pi_{\theta}(\mathbf{a}|\mathbf{s})\right]. Degris et al., (2012) show that under restrictive conditions, the approximate gradient preserves the local optima of J π β ( π ) J_{\pi_{\beta}}(\pi) . This approximate gradient is used as a starting point in many widely used deep reinforcement learning algorithms ( Silver et al.,, 2014 ; Lillicrap et al.,, 2015 ; Wang et al.,, 2016 ; Gu et al., 2017b, ) .
To compute an estimate of the approximate gradient, we additionally need to estimate Q π θ ( 𝐬 , 𝐚 ) Q^{\pi_{\theta}}(\mathbf{s},\mathbf{a}) from the off-policy trajectories. Basic methods for doing this were discussed in Section 2.1 , and we defer a more in-depth discussion of offline state-action value function estimators to Section 4 . Some estimators use action samples, which required an importance weight to correct from π β {\pi_{\beta}} samples to π θ \pi_{\theta} samples. Further improvements can be obtained by introducing control variates and clipping importance weights to control variance ( Wang et al.,, 2016 ; Espeholt et al.,, 2018 ) .
### 3.4 Marginalized Importance Sampling
If we would like to avoid the bias incurred by using the off-policy state distribution and the high variance from using per-action importance weighting, we can instead attempt to directly estimate the state-marginal importance ratio ρ π θ ( 𝐬 ) = d π θ ( 𝐬 ) d π β ( 𝐬 ) \rho^{\pi_{\theta}}(\mathbf{s})=\frac{d^{\pi_{\theta}}(\mathbf{s})}{d^{\pi_{\beta}}(\mathbf{s})} . An estimator using state marginal importance weights can be shown to be have no greater variance than using the product of per-action importance weights. However, computing this ratio exactly is generally intractable. Only recently have practical methods for estimating the marginalized importance ratio been introduced ( Sutton et al.,, 2016 ; Yu,, 2015 ; Hallak et al.,, 2015 ; Hallak et al.,, 2016 ; Hallak and Mannor,, 2017 ; Nachum et al., 2019a, ; Zhang et al., 2020a, ; Nachum et al., 2019b, ) . We discuss some key aspects of these methods next.
Most of these methods utilize some form of dynamic programming to estimate the importance ratio ρ π \rho^{\pi} . Based on the form of the underlying Bellman equation used, we can classify them into two categories: methods that use a “ forward ” Bellman equation to estimate the importance ratios directly, and methods that use a “ backward ” Bellman equation on a functional that resembles a value function and then derive the importance ratios from the learned value functional.
#### Forward Bellman equation based approaches.
The state-marginal importance ratio, ρ π ( 𝐬 ) \rho^{\pi}(\mathbf{s}) , satisfies a kind of “forward” Bellman equation: ∀ 𝐬 ′ , d π β ( 𝐬 ′ ) ρ π ( 𝐬 ′ ) ⏟ ≔ ( d π β ∘ ρ π ) ( 𝐬 ′ ) = ( 1 − γ ) d 0 ( 𝐬 ′ ) + γ ∑ 𝐬 , 𝐚 d π β ( 𝐬 ) ρ π ( 𝐬 ) π ( 𝐚 | 𝐬 ) T ( 𝐬 ′ | 𝐬 , 𝐚 ) ⏟ ≔ ( ℬ ¯ π ∘ ρ π ) ( 𝐬 ′ ) . \forall\mathbf{s}^{\prime},~~\underbrace{d^{\pi_{\beta}}(\mathbf{s}^{\prime})\rho^{\pi}(\mathbf{s}^{\prime})}_{\coloneqq(d^{\pi_{\beta}}\circ\rho^{\pi})(\mathbf{s}^{\prime})}=\underbrace{(1-\gamma)d_{0}(\mathbf{s}^{\prime})+\gamma\sum_{\mathbf{s},\mathbf{a}}d^{\pi_{\beta}}(\mathbf{s})\rho^{\pi}(\mathbf{s})\pi(\mathbf{a}|\mathbf{s})T(\mathbf{s}^{\prime}|\mathbf{s},\mathbf{a})}_{\coloneqq(\bar{\mathcal{B}}^{\pi}\circ\rho^{\pi})(\mathbf{s}^{\prime})}. (7) This relationship can be leveraged to perform temporal difference updates to estimate the state-marginal importance ratio under the policy.
For example, when stochastic approximation is used, Gelada and Bellemare, (2019) use the following update rule in order to estimate ρ π ( 𝐬 ′ ) \rho^{\pi}(\mathbf{s}^{\prime}) online: ρ ^ π ( 𝐬 ′ ) ← ρ ^ π ( 𝐬 ′ ) + α [ ( 1 − γ ) + γ π ( 𝐚 | 𝐬 ) π β ( 𝐚 | 𝐬 ) ρ ^ π ( 𝐬 ) − ρ ^ π ( 𝐬 ′ ) ] , \hat{\rho}^{\pi}(\mathbf{s}^{\prime})\leftarrow\hat{\rho}^{\pi}(\mathbf{s}^{\prime})+\alpha\left[(1-\gamma)+\gamma\frac{\pi(\mathbf{a}|\mathbf{s})}{{\pi_{\beta}}(\mathbf{a}|\mathbf{s})}\hat{\rho}^{\pi}(\mathbf{s})-\hat{\rho}^{\pi}(\mathbf{s}^{\prime})\right], (8) with 𝐬 ∼ d π β ( 𝐬 ) , 𝐚 ∼ π β ( 𝐚 | 𝐬 ) , 𝐬 ′ ∼ T ( 𝐬 ′ | 𝐬 , 𝐚 ) \mathbf{s}\sim d^{\pi_{\beta}}(\mathbf{s}),\mathbf{a}\sim{\pi_{\beta}}(\mathbf{a}|\mathbf{s}),\mathbf{s}^{\prime}\sim T(\mathbf{s}^{\prime}|\mathbf{s},\mathbf{a}) . Several additional techniques, including using TD( λ \lambda ) estimates and automatic adjustment of feature dimensions, have been used to stabilize learning. We refer the readers to Hallak and Mannor, (2017) and Gelada and Bellemare, (2019) for a detailed discussion. Gelada and Bellemare, (2019) also discusses several practical tricks, such as soft-normalization and discounted evaluation, to adapt these methods to deep Q-learning settings, unlike prior work that mainly focuses on linear function approximation. Wen et al., (2020) view to problem from the lens of power iteration, and propose a variational power method approach to combine function approximation and power iteration to estimate ρ π \rho^{\pi} . Imani et al., (2018) ; Zhang et al., (2019) show that similar methods can be used to estimate the off-policy policy gradient and thus be used in an off-policy actor critic method.
Alternatively, Liu et al., (2018) propose to use an adversarial approach to obtain the state-marginal importance ratios. From Eq. 7 , they derive a functional L ( ρ , f ) = γ 𝔼 𝐬 , 𝐚 , 𝐬 ′ ∼ 𝒟 [ ( ρ ( 𝐬 ) π ( 𝐚 | 𝐬 ) π β ( 𝐚 | 𝐬 ) − ρ ( 𝐬 ′ ) ) f ( 𝐬 ′ ) ] + ( 1 − γ ) 𝔼 𝐬 0 ∼ d 0 [ ( 1 − ρ ( 𝐬 ) ) f ( 𝐬 ) ] L(\rho,f)=\gamma\mathbb{E}_{\mathbf{s},\mathbf{a},\mathbf{s}^{\prime}\sim\mathcal{D}}\left[\left(\rho(\mathbf{s})\frac{\pi(\mathbf{a}|\mathbf{s})}{{\pi_{\beta}}(\mathbf{a}|\mathbf{s})}-\rho(\mathbf{s}^{\prime})\right)f(\mathbf{s}^{\prime})\right]+(1-\gamma)\mathbb{E}_{\mathbf{s}_{0}\sim d_{0}}[(1-\rho(\mathbf{s}))f(\mathbf{s})] (9) such that L ( ρ , f ) = 0 , ∀ f L(\rho,f)=0,\forall~f if and only if ρ = ρ π \rho=\rho^{\pi} . Therefore, we can learn ρ \rho by minimizing a worst-case estimate of L ( ρ , f ) 2 L(\rho,f)^{2} , by solving an adversarial, saddle-point optimization: min ρ max f L ( ρ , f ) 2 \min_{\rho}\max_{f}L(\rho,f)^{2} . Recent work ( Mousavi et al.,, 2020 ; Kallus and Uehara, 2019a, ; Kallus and Uehara, 2019b, ; Tang et al.,, 2019 ; Uehara and Jiang,, 2019 ) has refined this approach, in particular removing the need to have access to π β {\pi_{\beta}} . Once ρ ∗ \rho^{*} is obtained, Liu et al., (2019) use this estimator to compute the off-policy policy gradient.
Zhang et al., 2020a () present another off-policy evaluation method that computes the importance ratio for the state-action marginal, ρ π ( 𝐬 , 𝐚 ) := d π ( 𝐬 , 𝐚 ) d π β ( 𝐬 , 𝐚 ) \rho^{\pi}(\mathbf{s},\mathbf{a}):=\frac{d^{\pi}(\mathbf{s},\mathbf{a})}{d^{\pi_{\beta}}(\mathbf{s},\mathbf{a})} , by directly optimizing a variant of the Bellman residual error corresponding to a modified forward Bellman equation, that includes actions, shown in Equation 10 . d π β ( 𝐬 ′ , 𝐚 ′ ) ρ π ( 𝐬 ′ , 𝐚 ′ ) ⏟ ≔ ( d π β ∘ ρ π ) ( 𝐬 ′ , 𝐚 ′ ) = ( 1 − γ ) d 0 ( 𝐬 ′ ) π ( 𝐚 ′ | 𝐬 ′ ) + γ ∑ 𝐬 , 𝐚 d π β ( 𝐬 , 𝐚 ) ρ π ( 𝐬 , 𝐚 ) π ( 𝐚 | 𝐬 ) T ( 𝐬 ′ | 𝐬 , 𝐚 ) ⏟ ≔ ( ℬ ¯ π ∘ ρ π ) ( 𝐬 ′ , 𝐚 ′ ) . \underbrace{d^{\pi_{\beta}}(\mathbf{s}^{\prime},\mathbf{a}^{\prime})\rho^{\pi}(\mathbf{s}^{\prime},\mathbf{a}^{\prime})}_{\coloneqq(d^{\pi_{\beta}}\circ\rho^{\pi})(\mathbf{s}^{\prime},\mathbf{a}^{\prime})}\!=\!\underbrace{(1-\gamma)d_{0}(\mathbf{s}^{\prime})\pi(\mathbf{a}^{\prime}|\mathbf{s}^{\prime})\!+\!\gamma\sum_{\mathbf{s},\mathbf{a}}d^{\pi_{\beta}}(\mathbf{s},\mathbf{a})\rho^{\pi}(\mathbf{s},\mathbf{a})\pi(\mathbf{a}|\mathbf{s})T(\mathbf{s}^{\prime}|\mathbf{s},\mathbf{a})}_{\coloneqq(\bar{\mathcal{B}}^{\pi}\circ\rho^{\pi})(\mathbf{s}^{\prime},\mathbf{a}^{\prime})}. (10) Their approach can be derived by applying a divergence metric (such as an f-divergence, which we will review in Section 4 ) between the two sides of the modified forward Bellman equation in Equation 10 , while additionally constraining the importance ratio, ρ π ( 𝐬 , 𝐚 ) \rho^{\pi}(\mathbf{s},\mathbf{a}) , to integrate to 1 1 in expectation over the dataset, 𝒟 \mathcal{D} , to prevent degenerate solutions, as follows min ρ π D f ( ( ℬ ¯ π ∘ ρ π ) ( 𝐬 , 𝐚 ) , ( d π β ∘ ρ π ) ( 𝐬 , 𝐚 ) ) s.t. 𝔼 𝐬 , 𝐚 , 𝐬 ′ ∼ 𝒟 [ ρ π ( 𝐬 , 𝐚 ) ] = 1 . \min_{\rho^{\pi}}~~D_{f}\left(\left(\bar{\mathcal{B}}^{\pi}\circ\rho^{\pi}\right)(\mathbf{s},\mathbf{a}),\left(d^{\pi_{\beta}}\circ\rho^{\pi}\right)(\mathbf{s},\mathbf{a})\right)~~~\text{s.t.}~~~\mathbb{E}_{\mathbf{s},\mathbf{a},\mathbf{s}^{\prime}\sim\mathcal{D}}[\rho^{\pi}(\mathbf{s},\mathbf{a})]=1. (11) They further apply tricks inspired from dual embeddings ( Dai et al.,, 2016 ) to make the objective tractable, and to avoid the bias caused due to sampled estimates. We refer the readers to Zhang et al., 2020a () for further discussion.
Zhang et al., 2020b () show that primal-dual solvers may not be able to solve Eqn. 11 , and modify the objective in by replacing the f-divergence with a norm induced by 1 / d π β 1/d^{\pi_{\beta}} . This creates an optimization problem that is provably convergent under linear function approximation. min ρ π 1 2 | | ( ( ℬ ¯ π ∘ ρ π ) ( 𝐬 , 𝐚 ) − ( d π β ∘ ρ π ) ( 𝐬 , 𝐚 ) | | ( d π β ) − 1 2 + λ 2 ( 𝔼 𝐬 , 𝐚 , 𝐬 ′ ∼ 𝒟 [ ρ π ( 𝐬 , 𝐚 ) ] − 1 ) 2 . \min_{\rho^{\pi}}~~\frac{1}{2}||\left(\left(\bar{\mathcal{B}}^{\pi}\circ\rho^{\pi}\right)(\mathbf{s},\mathbf{a})-\left(d^{\pi_{\beta}}\circ\rho^{\pi}\right)(\mathbf{s},\mathbf{a})\right||^{2}_{(d^{\pi_{\beta}})^{-1}}+\frac{\lambda}{2}(\mathbb{E}_{\mathbf{s},\mathbf{a},\mathbf{s}^{\prime}\sim\mathcal{D}}[\rho^{\pi}(\mathbf{s},\mathbf{a})]-1)^{2}. (12)
#### Backward Bellman equation based approaches via convex duality.
Finally, we discuss methods for off-policy evaluation and improvement that utilize a backward Bellman equation – giving rise to a value-function like functional – by exploiting convex duality. Because these methods start from an optimization perspective, they can bring to bear the mature tools of convex optimization and online learning. Lee and He, (2018) extend a line of work applying to convex optimization techniques to policy optimization ( Chen and Wang,, 2016 ; Wang and Chen,, 2016 ; Dai et al., 2017a, ; Dai et al., 2017b, ) to the off-policy setting. They prove sample complexity bounds in the off-policy setting, however, extending these results to practical deep RL settings has proven challenging.