Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems β part 9/12
Cleaned-text code points [117996, 133966). Bibliography omitted here; source.md includes it.
The KL-divergence constraint, as well as other f f -divergences, represent a particularly convenient class of constraints, since they readily lend themselves to be used in a policy penalty algorithm by simply augmenting the reward function according to r Β― β ( π¬ , π ) = r β‘ ( π¬ , π ) β Ξ± β f β ( Ο β‘ ( π | π¬ ) / Ο Ξ² β ( π | π¬ ) ) \bar{r}(\mathbf{s},\mathbf{a})=r(\mathbf{s},\mathbf{a})-\alpha f(\pi(\mathbf{a}|\mathbf{s})/{\pi_{\beta}}(\mathbf{a}|\mathbf{s})) , with the important special case of the KL-divergence corresponding to r Β― β ( π¬ , π ) = r β‘ ( π¬ , π ) + Ξ± β log β‘ Ο Ξ² β ( π | π¬ ) β Ξ± β log β‘ Ο β‘ ( π | π¬ ) \bar{r}(\mathbf{s},\mathbf{a})=r(\mathbf{s},\mathbf{a})+\alpha\log{\pi_{\beta}}(\mathbf{a}|\mathbf{s})-\alpha\log\pi(\mathbf{a}|\mathbf{s}) , with the last term subsumed inside the entropy regularizer β ( Ο ( β
| π¬ ) ) \mathcal{H}(\pi(\cdot|\mathbf{s})) when using a maximum entropy reinforcement learning algorithm ( Levine,, 2018 ) . However, KL-divergences and other f f -divergences are not necessarily ideal for offline reinforcement learning. Consider a setting where the behavior policy is uniformly random. In this case, offline reinforcement learning should, in principle, be very effective. In fact, even standard actor-critic algorithms without any policy constraints can perform very well in this setting, since when all actions have equal probability, there are no out-of-distribution actions ( Kumar et al.,, 2019 ) . However, a KL-divergence constraint in this setting would restrict the learned policy Ο β‘ ( π | π¬ ) \pi(\mathbf{a}|\mathbf{s}) from being too concentrated, requiring the constrained algorithm to produce a highly stochastic (and therefore highly suboptimal) policy. Intuitively, an effective policy constraint should prevent the learned policy Ο β‘ ( π | π¬ ) \pi(\mathbf{a}|\mathbf{s}) from going outside the set of actions that have a high probability in the data, but would not prevent it from concentrating around a subset of high-probability actions. This suggests that a KL-divergence constraint is not in general the ideal choice.
In contrast, as argued by Kumar et al., (2019) and Laroche et al., (2017) , restricting the support of the learned policy Ο β‘ ( π | π¬ ) \pi(\mathbf{a}|\mathbf{s}) to the support of the behavior distribution Ο Ξ² β ( π | π¬ ) {\pi_{\beta}}(\mathbf{a}|\mathbf{s}) may be sufficient to theoretically and empirically obtain an effective offline RL method. In the previous example, if only the support of the learned policy is constrained to lie in the support of the behavior policy, the learned policy can be deterministic and optimal. However, when the behavior policy does not have full support, a support constraint will still prevent out-of-distribution actions. Kumar, (2019) formalize this intuition and present a simple example of a 1D-lineworld environment, which we reproduce in Figure 3 where constraining distributions can lead to highly suboptimal behavior, that strongly prefers moving leftwards, thus reaching the goal location with only very low likelihood over the course of multiple intermediate steps of decision making, while support constraints still allow for learning the optimal policy, since they are agnostic to the probability density function in this setting.
Which divergence metrics can be used to constrain policy supports? In a finite sample setting, the family of f f -divergences measures the difference in the probability densities , which makes it unsuitable for support matching. In an MDP with a discrete action-space, a simple choice for constraining the support is a metric that penalizes the total amount of probability mass on out-of-distribution actions under the Ο \pi distribution, as shown below: D support , Ξ΅ ( Ο ( β
| s ) , Ο Ξ² ( β
| s ) ) = β π β A , Ο Ξ² β ( π | π¬ ) β€ Ξ΅ Ο ( π | π¬ ) . D_{\text{support},\varepsilon}(\pi(\cdot|s),{\pi_{\beta}}(\cdot|s))=\sum_{\mathbf{a}\in A,{\pi_{\beta}}(\mathbf{a}|\mathbf{s})\leq\varepsilon}\pi(\mathbf{a}|\mathbf{s}). (23) This metric has been used in the context of off-policy bandits ( Sachdeva et al.,, 2020 ) , but not in the context of offline reinforcement learning. When the underlying MDP has a continuous action space and exact support cannot be estimated, Kumar et al., (2019) show that a finite sample estimate of the MMD distance can be used to approximately constrain supports of the learned policy. Similar to f f -divergences, the MMD distance still converges to a divergence estimate between the distribution functions of its arguments. However, Kumar et al., (2019) show experimentally (Figure 7) that, in the finite sample setting, MMD resembles a support constraining metric. The intuition is that the MMD distance does not depend on the specific densities of the behavior distribution or the policy, and can be computed via a kernel-based distance on samples from each distribution, thus making it just sufficient enough for constraining supports when finite samples are used. Some variants of the asymmetric f f -divergence that asymmetrically penalize the density ratios Ο ( β
| π¬ ) / Ο Ξ² ( β
| π¬ ) \pi(\cdot|\mathbf{s})/{\pi_{\beta}}(\cdot|\mathbf{s}) can also be used to approximately constrain supports ( Wu et al., 2019b, ; Wu et al., 2019a, ) .
### 4.4 Offline Approximate Dynamic Programming with Uncertainty Estimation
As discussed in Section 4.3 , policy constraints can prevent out-of-distribution action queries to the Q-function when computing the target values. Aside from directly constraining the policy, we can also mitigate the effect of out-of-distribution actions by making the Q-function resilient to such queries, via effective uncertainty estimation. The intuition behind these uncertainty-based methods is that, if we can estimate the epistemic uncertainty of the Q-function, we expect this uncertainty to be substantially larger for out-of-distribution actions, and can therefore utilize these uncertainty estimates to produce conservative target values in such cases. In this section, we briefly review such uncertainty-aware formulations of offline approximate dynamic programming methods.
Formally, such methods require learning an uncertainty set or distribution over possible Q-functions from the dataset π \mathcal{D} , which we can denote π« π β ( Q Ο ) \mathcal{P}_{\mathcal{D}}(Q^{\pi}) . This can utilize explicit modeling of confidence sets, such as by maintaining upper and lower confidence bounds ( Jaksch et al.,, 2010 ) , or directly representing samples from the distribution over Q-functions, for example via bootstrap ensembles ( Osband et al.,, 2016 ) , or by parameterizing the distribution over Q-values using a known (e.g., Gaussian) distribution with learned parameters ( OβDonoghue et al.,, 2018 ) . If calibrated uncertainty sets can be learned, then we can improve the policy using a conservative estimate of the Q-function, which corresponds to the following policy improvement objective: Ο k + 1 β arg β‘ max Ο β πΌ π¬ βΌ π β [ πΌ π βΌ Ο β‘ ( π | π¬ ) β [ πΌ Q k + 1 Ο βΌ π« π β ( Q Ο ) β [ Q k + 1 Ο β ( π¬ , π ) ] β Ξ± β Unc β ( π« π β ( Q Ο ) ) ] ] β conservative estimate , \pi_{k+1}\leftarrow\arg\max_{\pi}\mathbb{E}_{\mathbf{s}\sim\mathcal{D}}\underbrace{\left[\mathbb{E}_{\mathbf{a}\sim\pi(\mathbf{a}|\mathbf{s})}\left[\mathbb{E}_{Q^{\pi}_{k+1}\sim\mathcal{P}_{\mathcal{D}}(Q^{\pi})}[Q^{\pi}_{k+1}(\mathbf{s},\mathbf{a})]-\alpha\text{Unc}(\mathcal{P}_{\mathcal{D}}(Q^{\pi}))\right]\right]}_{\text{conservative estimate}}, (24) where Unc denotes a metric of uncertainty, such that subtracting it provides a conservative estimate of the actual Q-function. The choice of the uncertainty metric Unc depends on the particular choice of uncertainty estimation method, and we discuss this next.
When bootstrap ensembles 3 3 3 It is known in the deep learning literature that, although a true bootstrap ensemble requires resampling the dataset with replacement for every bootstrap, omitting this resampling step and simply using different random initialization for every neural network in the ensemble is sufficient to differentiate the models and provide reasonable uncertainty estimates ( Osband et al.,, 2016 ) . In fact, previous work has generally observed little benefit from employ proper resampling ( Osband et al.,, 2016 ) , which technically means that all of these methods simply employ regular (non-bootstrapped) ensembles, although the quality of their uncertainty estimates is empirically similar. are used to represent the Q-function, as is common in prior work ( Osband et al.,, 2016 ; Eysenbach et al.,, 2017 ; Kumar et al.,, 2019 ; Agarwal et al.,, 2019 ) , typical choices of β Unc β include variance across Q-value predictions of an ensemble of Q-functions ( Kumar et al.,, 2019 ) , or maximizing the Q-value with respect to the worst case or all convex combinations of the Q-value predictions of an ensemble ( Agarwal et al.,, 2019 ) . When a parametric distribution, such as a Gaussian, is used to represent the Q-function ( OβDonoghue et al.,, 2018 ) , a choice of Unc , previously used for exploration, is to use a standard deviation above the mean as an optimistic Q-value estimate for policy improvement. When translated to offline RL, an analogous estimate would be to use conservative Q-values, such as one standard deviation below the mean, for policy improvement.
### 4.5 Conservative Q-Learning and Pessimistic Value Functions
As an alternative to imposing constraints on the policy in an actor-critic framework, an effective approach to offline RL can also be developed by regularizing the value function or Q-function directly to avoid overestimation for out-of-distribution actions ( Kumar et al., 2020b, ) . This approach can be appealing for several reasons, such as being applicable to both actor-critic and Q-learning methods, even when a policy is not represented explicitly, and avoiding the need for explicit modeling of the behavior policy. The practical effect of such a method resembles the conservative estimate in Equation ( 24 ), but without explicit uncertainty estimation. As discussed by Kumar et al., 2020b () , one simple way to ensure a conservative Q-function is to modify the objective for fitting the Q-function parameters Ο \phi on Line 14 of the Q-learning method in Algorithm 2 or Line 14 of the actor-critic method in Algorithm 3 to add an additional conservative penalty term, yielding a modified objective β° ~ β ( B , Ο ) = Ξ± β π β ( B , Ο ) + β° β‘ ( B , Ο ) , \tilde{\mathcal{E}}(B,\phi)=\alpha\mathcal{C}(B,\phi)+\mathcal{E}(B,\phi), where different choices for π β‘ ( B , Ο ) \mathcal{C}(B,\phi) lead to algorithms with different properties. A basic example is the penalty π CQL 0 β ( B , Ο ) = πΌ π¬ βΌ B , π βΌ ΞΌ β‘ ( π | π¬ ) β [ Q Ο β ( π¬ , π ) ] \mathcal{C}_{\text{CQL}_{0}}(B,\phi)=\mathbb{E}_{\mathbf{s}\sim B,\mathbf{a}\sim\mu(\mathbf{a}|\mathbf{s})}[Q_{\phi}(\mathbf{s},\mathbf{a})] . Intuitively, this penalty minimizes the Q-values at all of the states in the buffer, for actions selected according to the distribution ΞΌ β‘ ( π | π¬ ) \mu(\mathbf{a}|\mathbf{s}) . If ΞΌ β‘ ( π | π¬ ) \mu(\mathbf{a}|\mathbf{s}) is chosen adversarially , for example by maximizing the penalty π CQL 0 β ( B , Ο ) \mathcal{C}_{\text{CQL}_{0}}(B,\phi) , the effect is that the conservative penalty will push down on high Q-values. Note that the standard Bellman error term β° β‘ ( B , Ο ) \mathcal{E}(B,\phi) will still enforce that the Q-values obey the Bellman backup for in-distribution actions. Therefore, if the penalty weight Ξ± \alpha is chosen appropriately, the conservative penalty should mostly push down on Q-values for out-of-distribution actions for which the Q-values are (potentially erroneously) high, since in-distribution actions would be βanchoredβ by the Bellman error β° β‘ ( B , Ο ) \mathcal{E}(B,\phi) . Indeed, Kumar et al., 2020b () show that, for an appropriately chosen value of Ξ± \alpha , a Q-function trained with this conservative penalty will represent a lower bound on the true Q-function Q β‘ ( π¬ , π ) Q(\mathbf{s},\mathbf{a}) for the current policy, both in theory and in practice. This results in a provably conservative Q-learning or actor-critic algorithm. A simple and practical choice for ΞΌ β‘ ( π , π¬ ) \mu(\mathbf{a},\mathbf{s}) is to use a regularized adversarial objective, such that ΞΌ = arg max ΞΌ πΌ π¬ βΌ π [ πΌ π βΌ ΞΌ β‘ ( π | π¬ ) [ Q Ο ( π¬ , π ) ] + β ( ΞΌ ( β
| π¬ ) ) ] . \mu=\arg\max_{\mu}\mathbb{E}_{\mathbf{s}\sim\mathcal{D}}\left[\mathbb{E}_{\mathbf{a}\sim\mu(\mathbf{a}|\mathbf{s})}[Q_{\phi}(\mathbf{s},\mathbf{a})]+\mathcal{H}(\mu(\cdot|\mathbf{s}))\right]. This choice inherits the lower bound guarantee above, and is simple to compute. The solution to the above optimization is given by ΞΌ β‘ ( π | π¬ ) β exp β‘ ( Q β‘ ( π¬ , π ) ) \mu(\mathbf{a}|\mathbf{s})\propto\exp(Q(\mathbf{s},\mathbf{a})) , and we can express π CQL 0 β ( B , Ο ) \mathcal{C}_{\text{CQL}_{0}}(B,\phi) under this choice of ΞΌ β‘ ( π | π¬ ) \mu(\mathbf{a}|\mathbf{s}) in closed form as π CQL 0 ( B , Ο ) = E π¬ βΌ B [ log β π exp ( Q Ο ( π¬ , π ) ) ] \mathcal{C}_{\text{CQL}_{0}}(B,\phi)=E_{\mathbf{s}\sim B}[\log\sum_{\mathbf{a}}\exp(Q_{\phi}(\mathbf{s},\mathbf{a}))] . This expression has a simple intuitive interpretation: the log-sum-exp is dominated by the action with the largest Q-value, and hence this type of penalty tends to minimize whichever Q-value is largest at each state. When the action space is large or continuous, we can estimate this quantity by sampling and reweighting. For example, Kumar et al., 2020b () propose sampling from the current actor (in an actor-critic algorithm) and computing importance weights.
While the approach described above has the appealing property of providing a learned Q-function Q Ο β ( π¬ , π ) Q_{\phi}(\mathbf{s},\mathbf{a}) that lower bounds the true Q-function, and therefore provably avoids overestimation, it tends to suffer from excessive underestimation β that is, it is too conservative. A simple modification, which we refer to as π CQL 1 β ( B , Ο ) \mathcal{C}_{\text{CQL}_{1}}(B,\phi) , is to also add a value maximization term to balance out the minimization term under ΞΌ β‘ ( π | π¬ ) \mu(\mathbf{a}|\mathbf{s}) , yielding the following expression: π CQL 1 β ( B , Ο ) = πΌ π¬ βΌ B , π βΌ ΞΌ β‘ ( π | π¬ ) β [ Q Ο β ( π¬ , π ) ] β πΌ ( π¬ , π ) βΌ B β [ Q Ο β ( π¬ , π ) ] . \mathcal{C}_{\text{CQL}_{1}}(B,\phi)=\mathbb{E}_{\mathbf{s}\sim B,\mathbf{a}\sim\mu(\mathbf{a}|\mathbf{s})}[Q_{\phi}(\mathbf{s},\mathbf{a})]-\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim B}[Q_{\phi}(\mathbf{s},\mathbf{a})]. This conservative penalty minimizes Q-values under the adversarially chosen ΞΌ β‘ ( π | π¬ ) \mu(\mathbf{a}|\mathbf{s}) distribution, and maximizes the values for state-action tuples in the batch. Intuitively, this acts to ensure that high Q-values are only assigned to in-distribution actions. When ΞΌ β‘ ( π | π¬ ) \mu(\mathbf{a}|\mathbf{s}) is equal to the behavior policy, the penalty is zero on average. While this penalty does not produce a Q-function that is a pointwise lower bound on the true Q-function, it is a lower bound in expectation under the current policy, thereby still providing appealing conservatism guarantees, while substantially reducing underestimation in practice. As shown by Kumar et al., 2020b () , this variant produces the best performance in practice.
### 4.6 Challenges and Open Problems
As we discussed in Section 4.1 , basic approximate dynamic programming algorithms can perform very poorly in the offline setting due to distributional shift, primarily due to the distributional shift of the actions due to the discrepancy between the behavior policy Ο Ξ² β ( π | π¬ ) {\pi_{\beta}}(\mathbf{a}|\mathbf{s}) and the current learned policy Ο β‘ ( π | π¬ ) \pi(\mathbf{a}|\mathbf{s}) , which is used in the target value calculation for the Bellman backup. We discussed how policy constraints and explicit uncertainty estimation can in principle mitigate this problem, but both approaches have a number of shortcomings.