Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reduction

Introduction

One of the primary drivers of the success of machine learning methods in open-world perception settings, such as computer vision and NLP , has been the ability of high-capacity function approximators, such as deep neural networks, to learn generalizable models from large amounts of data. Reinforcement learning (RL) has proven comparatively difficult to scale to unstructured real-world settings because most RL algorithms require active data collection. As a result, RL algorithms can learn complex behaviors in simulation, where data collection is straightforward, but real-world performance is limited by the expense of active data collection. In some domains, such as autonomous driving and recommender systems , previously collected datasets are plentiful. Algorithms that can utilize such datasets effectively would not only make real-world RL more practical, but also would enable substantially better generalization by incorporating diverse prior experience.

In principle, off-policy RL algorithms can leverage this data; however, in practice, off-policy algorithms are limited in their ability to learn entirely from off-policy data. Recent off-policy RL methods (e.g., ) have demonstrated sample-efficient performance on complex tasks in robotics and simulated environments . However, these methods can still fail to learn when presented with arbitrary off-policy data without the opportunity to collect more experience from the environment. This issue persists even when the off-policy data comes from effective expert policies, which in principle should address any exploration challenge . This sensitivity to the training data distribution is a limitation of practical off-policy RL algorithms, and one would hope that an off-policy algorithm should be able to learn reasonable policies through training on static datasets before being deployed in the real world. In this paper, we aim to develop off-policy, value-based RL methods that can learn from large, static datasets. As we show, a crucial challenge in applying value-based methods to off-policy scenarios arises in the bootstrapping process employed when Q-functions are evaluated on out of out-of-distribution action inputs for computing the backup when training from off-policy data. This may introduce errors in the Q-function and the algorithm is unable to collect new data in order to remedy those errors, making training unstable and potentially diverging. Our primary contribution is an analysis of error accumulation in the bootstrapping process due to out-of-distribution inputs and a practical way of addressing this error. First, we formalize and analyze the reasons for instability and poor performance when learning from off-policy data. We show that, through careful action selection, error propagation through the Q-function can be mitigated. We then propose a principled algorithm called bootstrapping error accumulation reduction (BEAR) to control bootstrapping error in practice, which uses the notion of support-set matching to prevent error accumulation. Through systematic experiments, we show the effectiveness of our method on continuous-control MuJoCo tasks, with a variety of off-policy datasets: generated by a random, suboptimal, or optimal policies. BEAR is consistently robust to the training dataset, matching or exceeding the state-of-the-art in all cases, whereas existing algorithms only perform well for specific datasets.

Related Work

In this work, we study off-policy reinforcement learning with static datasets. Errors arising from inadequate sampling, distributional shift, and function approximation have been rigorously studied as “error propagation” in approximate dynamic programming (ADP) . These works often study how Bellman errors accumulate and propagate to nearby states via bootstrapping. In this work, we build upon tools from this analysis to show that performing Bellman backups on static datasets leads to error accumulation due to out-of-distribution values. Our approach is motivated as reducing the rate of propagation of error propagation between states.

Our approach constrains actor updates so that the actions remain in the support of the training dataset distribution. Several works have explored similar ideas in the context of off-policy learning learning in online settings. Kakade and Langford shows that large policy updates can be destructive, and propose a conservative policy iteration scheme which constrains actor updates to be small for provably convergent learning. Grau-Moya et al. use a learned prior over actions in the maximum entropy RL framework and justify it as a regularizer based on mutual information. However, none of these methods use static datasets. Importance Sampling based distribution re-weighting has also been explored primarily in the context of off-policy policy evaluation.

Most closely related to our work is batch-constrained Q-learning (BCQ) and SPIBB , which also discuss instability arising from previously unseen actions. Fujimoto et al. show convergence properties of an action-constrained Bellman backup operator in tabular, error-free settings. We prove stronger results under approximation errors and provide a bound on the suboptimality of the solution. This is crucial as it drives the design choices for a practical algorithm. As a consequence, although we experimentally find that outperforms standard Q-learning methods when the off-policy data is collected by an expert, BEAR outperforms when the off-policy data is collected by a suboptimal policy, as is common in real-life applications. Empirically, we find BEAR achieves stronger and more consistent results than BCQ across a wide variety of datasets and environments. As we explain below, the BCQ constraint is too aggressive; BCQ generally fails to substantially improve over the behavior policy, while our method actually improves when the data collection policy is suboptimal or random. SPIBB , like BEAR, is an algorithm based on constraining the learned policy to the support of a behavior policy. However, the authors do not extend safe performance guarantees from the batch-constrained case to the relaxed support-constrained case, and do not evaluate on high-dimensional control tasks. REM is a concurrent work that uses a random convex combination of an ensemble of Q-networks to perform offline reinforcement learning from a static dataset consisting of interaction data generated while training a DQN agent.

Background

We represent the environment as a Markov decision process (MDP) defined by a tuple $(\mathcal{S},\mathcal{A},P,R,{\rho_{0}},\gamma)$, where $\mathcal{S}$ is the state space, $\mathcal{A}$ is the action space, $P(s^{\prime}|s,a)$ is the transition distribution, ${\rho_{0}}(s)$ is the initial state distribution, $R(s,a)$ is the reward function, and $\gamma\in(0,1)$ is the discount factor. The goal in RL is to find a policy $\pi(a|s)$ that maximizes the expected cumulative discounted rewards which is also known as the return. The notation $\mu_{\pi}(s)$ denotes the discounted state marginal of a policy $\pi$, defined as the average state visited by the policy, $\sum_{t=0}^{\infty}\gamma^{t}p^{t}_{\pi}(s)$. $P^{\pi}$ is shorthand for the transition matrix from $s$ to $s^{\prime}$ following a certain policy $\pi$, $p(s^{\prime}|s)=E_{\pi}[p(s^{\prime}|s,a)]$.

Q-learning learns the optimal state-action value function $Q^{*}(s,a)$, which represents the expected cumulative discounted reward starting in $s$ taking action $a$ and then acting optimally thereafter. The optimal policy can be recovered from $Q^{*}$ by choosing the maximizing action. Q-learning algorithms are based on iterating the Bellman optimality operator $\mathcal{T}$, defined as

In large action spaces (e.g., continuous), the maximization $\max_{a^{\prime}}Q(s^{\prime},a^{\prime})$ is generally intractable. Actor-critic methods address this by additionally learning a policy $\pi_{\theta}$ that maximizes the $Q$-function. In this work, we study off-policy learning from a static dataset of transitions $\mathcal{D}=\{(s,a,s^{\prime},R(s,a))\}$, collected under an unknown behavior policy $\beta(\cdot|s)$. We denote the distribution over states and actions induced by $\beta$ as $\mu(s,a)$.

Out-of-Distribution Actions in Q-Learning

Q-learning methods often fail to learn on static, off-policy data, as shown in Figure 1. At first glance, this resembles overfitting, but increasing the size of the static dataset does not rectify the problem, suggesting the issue is more complex. We can understand the source of this instability by examining the form of the Bellman backup. Although minimizing the mean squared Bellman error corresponds to a supervised regression problem, the targets for this regression are themselves derived from the current Q-function estimate. The targets are calculated by maximizing the learned $Q$-values with respect to the action at the next state. However, the $Q$-function estimator is only reliable on inputs from the same distribution as its training set. As a result, naïvely maximizing the value may evaluate the $\hat{Q}$ estimator on actions that lie far outside of the training distribution, resulting in pathological values that incur large error. We refer to these actions as out-of-distribution (OOD) actions.

To mitigate bootstrapping error, we can restrict the policy to ensure that it output actions that lie in the support of the training distribution. This is distinct from previous work (e.g., BCQ ) which implicitly constrains the distribution of the learned policy to be close to the behavior policy, similarly to behavioral cloning . While this is sufficient to ensure that actions lie in the training set with high probability, it is overly restrictive. For example, if the behavior policy is close to uniform, the learned policy will behave randomly, resulting in poor performance, even when the data is sufficient to learn a strong policy (see Figure 2 for an illustration). Formally, this means that a learned policy $\pi(a|s)$ has positive density only where the density of the behaviour policy $\beta(a|s)$ is more than a threshold (i.e., $\forall a,\beta(a|s)\leq\varepsilon\implies\pi(a|s)=0$), instead of a closeness constraint on the value of the density $\pi(a|s)$ and $\beta(a|s)$. Our analysis instead reveals a tradeoff between staying within the data distribution and finding a suboptimal solution when the constraint is too restrictive. Our analysis motivates us to restrict the support of the learned policy, but not the probabilities of the actions lying within the support. This avoids evaluating the Q-function estimator on OOD actions, but remains flexible in order to find a performant policy. Our proposed algorithm leverages this insight.

In this section, we define and analyze a backup operator that restricts the set of policies used in the maximization of the Q-function, and we derive performance bounds which depend on the restricted set. This provides motivation for constraining policy support to the data distribution. We begin with the definition of a distribution-constrained operator:

Given a set of policies $\Pi$, the distribution-constrained backup operator is defined as:

This backup operator satisfies properties of the standard Bellman backup, such as convergence to a fixed point, as discussed in Appendix A. To analyze the (sub)optimality of performing this backup under approximation error, we first quantify two sources of error. The first is a suboptimality bias. The optimal policy may lie outside the policy constraint set, and thus a suboptimal solution will be found. The second arises from distribution shift between the training distribution and the policies used for backups. This formalizes the notion of OOD actions. To capture suboptimality in the final solution, we define a suboptimality constant, which measures how far $\pi^{*}$ is from $\Pi$.

The suboptimality constant is defined as:

Next, we define a concentrability coefficient , which quantifies how far the visitation distribution generated by policies from $\Pi$ is from the training data distribution. This constant captures the degree to which states and actions are out of distribution.

Let ${\rho_{0}}$ denote the initial state distribution, and $\mu(s,a)$ denote the distribution of the training data over $\mathcal{S}\times\mathcal{A}$, with marginal $\mu(s)$ over $\mathcal{S}$. Suppose there exist coefficients $c(k)$ such that for any $\pi_{1},...\pi_{k}\in\Pi$ and $s\in\mathcal{S}$:

where $P^{\pi_{i}}$ is the transition operator on states induced by $\pi_{i}$. Then, define the concentrability coefficient $C(\Pi)$ as

To provide some intuition for $C(\Pi)$, if $\mu$ was generated by a single policy $\pi$, and $\Pi=\{\pi\}$ was a singleton set, then we would have $C(\Pi)=1$, which is the smallest possible value. However, if $\Pi$ contained policies far from $\pi$, the value could be large, potentially infinite if the support of $\Pi$ is not contained in $\pi$. Now, we bound the performance of approximate distribution-constrained Q-iteration:

Suppose we run approximate distribution-constrained value iteration with a set constrained backup $\mathcal{T}^{\Pi}$. Assume that $\delta(s,a)\geq\max_{k}|Q_{k}(s,a)-\mathcal{T}^{\Pi}Q_{k-1}(s,a)|$ bounds the Bellman error. Then,

This bound formalizes the tradeoff between keeping policies chosen during backups close to the data (captured by $C(\Pi)$) and keeping the set $\Pi$ large enough to capture well-performing policies (captured by $\alpha(\Pi)$). When we expand the set of policies $\Pi$, we are increasing $C(\Pi)$ but decreasing $\alpha(\Pi)$. An example of this tradeoff, and how a careful choice of $\Pi$ can yield superior results, is given in a tabular gridworld example in Fig. 2, where we visualize errors accumulated during distribution-constrained Q-iteration for different choices of $\Pi$.

Finally, we motivate the use of support sets to construct $\Pi$. We are interested in the case where $\Pi_{\epsilon}=\{\pi~{}|~{}\pi(a|s)=0\text{ whenever }\beta(a|s)<\epsilon\}$, where $\beta$ is the behavior policy (i.e., $\Pi$ is the set of policies that have support in the probable regions of the behavior policy). Defining $\Pi_{\epsilon}$ in this way allows us to bound the concentrability coefficient:

Assume the data distribution $\mu$ is generated by a behavior policy $\beta$. Let $\mu(s)$ be the marginal state distribution under the data distribution. Define ${\Pi_{\epsilon}}=\{\pi~{}|~{}\pi(a|s)=0\text{ whenever }\beta(a|s)<\epsilon\}$ and let $\mu_{\Pi_{\epsilon}}$ be the highest discounted marginal state distribution starting from the initial state distribution $\rho$ and following policies $\pi\in{\Pi_{\epsilon}}$ at each time step thereafter. Then, there exists a concentrability coefficient $C({\Pi_{\epsilon}})$ which is bounded:

where $f(\epsilon)\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny def}}}}{{=}}}\min_{s\in\mathcal{S},\mu_{\Pi_{\epsilon}}(s)>0}[\mu(s)]>0$.

Qualitatively, $f(\epsilon)$ is the minimum discounted visitation marginal of a state under the behaviour policy if only actions which are more than $\epsilon$ likely are executed in the environment. Thus, using support sets gives us a single lever, $\epsilon$, which simultaneously trades off the value of $C(\Pi)$ and $\alpha(\Pi)$. Not only can we provide theoretical guarantees, we will see in our experiments (Sec. 6) that constructing $\Pi$ in this way provides a simple and effective method for implementing distribution-constrained algorithms.

Intuitively, this means we can prevent an increase in overall error in the Q-estimate by selecting policies supported on the support of the training action distribution, which would ensure roughly bounded projection error $\delta_{k}(s,a)$ while reducing the suboptimality bias, potentially by a large amount. Bounded error $\delta_{k}(s,a)$ on the support set of the training distribution is a reasonable assumption when using highly expressive function approximators, such as deep networks, especially if we are willing to reweight the transition set . We further elaborate on this point in Appendix C.

Bootstrapping Error Accumulation Reduction (BEAR)

We now propose a practical actor-critic algorithm (built on the framework of TD3 or SAC ) that uses distribution-constrained backups to reduce accumulation of bootstrapping error. The key insight is that we can search for a policy with the same support as the training distribution, while preventing accidental error accumulation. Our algorithm has two main components. Analogous to BCQ , we use $K$ Q-functions and use the minimum Q-value for policy improvement, and design a constraint which will be used for searching over the set of policies ${\Pi_{\epsilon}}$, which share the same support as the behaviour policy. Both of these components will appear as modifications of the policy improvement step in actor-critic style algorithms. We also note that policy improvement can be performed with the mean of the K Q-functions, and we found that this scheme works as good in our experiments.

We denote the set of Q-functions as: $\hat{Q}_{1},\cdots,\hat{Q}_{K}$. Then, the policy is updated to maximize the conservative estimate of the Q-values within ${\Pi_{\epsilon}}$:

In practice, the behaviour policy $\beta$ is unknown, so we need an approximate way to constrain $\pi$ to $\Pi$. We define a differentiable constraint that approximately constrains $\pi$ to $\Pi$, and then approximately solve the constrained optimization problem via dual gradient descent. We use the sampled version of maximum mean discrepancy (MMD) between the unknown behaviour policy $\beta$ and the actor $\pi$ because it can be estimated based solely on samples from the distributions. Given samples $x_{1},\cdots,x_{n}\sim P$ and $y_{1},\cdots,y_{m}\sim Q$, the sampled MMD between $P$ and $Q$ is given by:

Here, $k(\cdot,\cdot)$ is any universal kernel. In our experiments, we find both Laplacian and Gaussian kernels work well. The expression for MMD does not involve the density of either distribution and it can be optimized directly through samples. Empirically we find that, in the low-intermediate sample regime, the sampled MMD between $P$ and $Q$ is similar to the MMD between a uniform distribution over $P$’s support and $Q$, which makes MMD roughly suited for constraining distributions to a given support set. (See Appendix C.3 for numerical simulations justifying this approach).

Putting everything together, the optimization problem in the policy improvement step is

where $\varepsilon$ is an approximately chosen threshold. We choose a threshold of $\varepsilon=0.05$ in our experiments. The algorithm is summarized in Algorithm 1.

How does BEAR connect with distribution-constrained backups described in Section 4.1? Step 5 of the algorithm restricts $\pi_{\phi}$ to lie in the support of $\beta$. This insight is formally justified in Theorems 4.1 & 4.2 ($C(\Pi_{\varepsilon})$ is bounded). Computing distribution-constrained backup exactly by maximizing over $\pi\in\Pi_{\varepsilon}$ is intractable in practice. As an approximation, we sample Dirac policies in the support of $\beta$ (Alg 1, Line 5) and perform empirical maximization to compute the backup. As the maximization is performed over a narrower set of Dirac policies ($\{\delta_{a_{i}}\}\subseteq\Pi_{\varepsilon}$), the bound in Theorem 4.1 still holds. Empirically, we show in Section 6 that this approximation is sufficient to outperform previous methods. This connection is briefly discussed in Appendix C.2.

In summary, the actor is updated towards maximizing the Q-function while still being constrained to remain in the valid search space defined by ${\Pi_{\epsilon}}$. The Q-function uses actions sampled from the actor to then perform distribution-constrained Q-learning, over a reduced set of policies. At test time, we sample $p$ actions from $\pi_{\phi}(s)$ and the Q-value maximizing action out of these is executed in the environment. Implementation and other details are present in Appendix D.

Experiments

In our experiments, we study how BEAR performs when learning from static off-policy data on a variety of continuous control benchmark tasks. We evaluate our algorithm in three settings: when the dataset $\mathcal{D}$ is generated by (1) a completely random behaviour policy, (2) a partially trained, medium scoring policy, and (3) an optimal policy. Condition (2) is of particular interest, as it captures many common use-cases in practice, such as learning from imperfect demonstration data (e.g., of the sort that are commonly available for autonomous driving ), or reusing previously collected experience during off-policy RL. We compare our method to several prior methods: a baseline actor-critic algorithm (TD3), the BCQ algorithm , which aims to address a similar problem, as discussed in Section 4, KL-control (which solves a KL-penalized RL problem similarly to maximum entropy RL), a static version of DQfD (where a constraint to upweight Q-values of state-action pairs observed in the dataset is added as an auxiliary loss on top a regular actor-critic algorithm), and a behaviour cloning (BC) baseline, which simply imitates the data distribution. This serves to measure whether each method actually performs effective RL, or simply copies the data. We report the average evaluation return over 5 seeds of the policy given by the learned algorithm, in the form of a learning curve as a function of number of gradient steps taken by the algorithm. These samples are only collected for evaluation, and are not used for training.

We first discuss the evaluation of condition with “mediocre” data (2), as this condition resembles the settings where we expect training on offline data to be most useful. We collected one million transitions from a partially trained policy, so as to simulate imperfect demonstration data or data from a mediocre prior policy. In this scenario, we found that BEAR-QL consistently outperforms both BCQ and a naïve off-policy RL baseline (TD3) by large margins, as shown in Figure 3. This scenario is the most relevant from an application point of view, as access to optimal data may not be feasible, and random data might have inadequate exploration to efficient learn a good policy. We also evaluate the accuracy with which the learned Q-functions predict actual policy returns. These trends are provided in Appendix E. Note that the performance of BCQ often tracks the performance of the BC baseline, suggesting that BCQ primarily imitates the data. Our KL-control baseline uses automatic temperature tuning . We find that KL-control usually performs similar or worse to BC, whereas DQfD tends to diverge often due to cumulative error due to OOD actions and often exhibits a huge variance across different runs (for example, HalfCheetah-v2 environment).

2 Performance on Random and Optimal Datasets

In Figure 5, we show the performance of each method when trained on data from a random policy (top) and a near-optimal policy (bottom). In both cases, our method BEAR achieves good results, consistently exceeding the average dataset return on random data, and matching the optimal policy return on optimal data. Naïve RL also often does well on random data. For a random data policy, all actions are in-distribution, since they all have equal probability. This is consistent with our hypothesis that OOD actions are one of the main sources of error in off-policy learning on static datasets. The prior BCQ method performs well on optimal data but performs poorly on random data, where the constraint is too strict. These results show that BEAR-QL is robust to the dataset composition, and can learn consistently in a variety of settings. We find that KL-control and DQfD can be unstable in these settings.

Finally, in Figure 4, we show that BEAR outperforms other considered prior methods in the challenging Humanoid-v2 environment as well, in two cases – Medium-quality data and random data.

3 Analysis of BEAR-QL

In this section, we aim to analyze different components of our method via an ablation study. Our first ablation studies the support constraint discussed in Section 5, which uses MMD to measure support. We replace it with a more standard KL-divergence distribution constraint, which measures similarity in density. Our hypothesis is that this should provide a more conservative constraint, since matching distributions is not necessary for matching support. KL-divergence performs well in some cases, such as with optimal data, but as shown in Figure 6, it performs worse than MMD on medium-quality data. Even when KL-divergence is hand tuned fully, so as to prevent instability issues it still performs worse than a not-well tuned MMD constraint. We provide the results for this setting in the Appendix. We also vary the number of samples $n$ that are used to compute the MMD constraint. We find that smaller n ($\approx$ 4 or 5) gives better performance. Although the difference is not large, consistently better performance with 4 samples leans in favour of our hypothesis that an intermediate number of samples works well for support matching, and hence is less restrictive.

Discussion and Future Work

The goal in our work was to study off-policy reinforcement learning with static datasets. We theoretically and empirically analyze how error propagates in off-policy RL due to the use of out-of-distribution actions for computing the target values in the Bellman backup. Our experiments suggest that this source of error is one of the primary issues afflicting off-policy RL: increasing the number of samples does not appear to mitigate the degradation issue (Figure 1), and training with naïve RL on data from a random policy, where there are no out-of-distribution actions, shows much less degradation than training on data from more focused policies (Figure 5). Armed with this insight, we develop a method for mitigating the effect of out-of-distribution actions, which we call BEAR-QL. BEAR-QL constrains the backup to use actions that have non-negligible support under the data distribution, but without being overly conservative in constraining the learned policy. We observe experimentally that BEAR-QL achieves good performance across a range of tasks, and across a range of dataset compositions, learning well on random, medium-quality, and expert data.

While BEAR-QL substantially stabilizes off-policy RL, we believe that this problem merits further study. One limitation of our current method is that, although the learned policies are more performant than those acquired with naïve RL, performance sometimes still tends to degrade for long learning runs. An exciting direction for future work would be to develop an early stopping condition for RL, perhaps by generalizing the notion of validation error to reinforcement learning. A limitation of approaches that perform constrained-action selection is that they can be overly conservative when compared to methods that constrain state-distributions directly, especially with datasets collected from mixtures of policies. We leave it to future work to design algorithms that can directly constrain state distributions. A theoretically robust method for support matching efficiently in high-dimensional continuous action spaces is a question for future research. Perhaps methods from outside RL, predominantly used in domain adaptation, such as using asymmetric f-divergences can be used for support restriction. Another promising future direction is to examine how well BEAR-QL can work on large-scale off-policy learning problems, of the sort that are likely to arise in domains such as robotics, autonomous driving, operations research, and commerce. If RL algorithms can learn effectively from large-scale off-policy datasets, reinforcement learning can become a truly data-driven discipline, benefiting from the same advantage in generalization that has been seen in recent years in supervised learning fields, where large datasets have enabled rapid progress in terms of accuracy and generalization .

Acknowledgements

We thank Kristian Hartikainen for sharing implementations of RL algorithms and for help in debugging certain issues. We thank Matthew Soh for help in setting up environments. We thank Aurick Zhou, Chelsea Finn, Abhishek Gupta, Kelvin Xu and Rishabh Agarwal for informative discussions. We thank Ofir Nachum for comments on an earlier draft of this paper. We thank Google, NVIDIA, and Amazon for providing computational resources. This research was supported by Berkeley DeepDrive, JPMorgan Chase & Co., NSF IIS-1651843 and IIS-1614653, the DARPA Assured Autonomy program, and ARL DCIST CRA W911NF-17-2-0181.

References

Appendices

In this section, we analyze properties of the constrained Bellman backup operator, defined as:

Such an operator can be reduced to a standard Bellman backup in a modified MDP. We can construct an MDP $M^{\prime}$ from the original MDP $M$ as follows:

The state space, discount, and initial state distributions remain unchanged from $M$.

We define a new action set $\mathcal{A}^{\prime}=\Pi$ to be the choice of policy $\pi$ to execute.

We define the new transition distribution $p^{\prime}$ as taking one step under the chosen policy $\pi$ to execute and one step under the original dynamics $p$: $p^{\prime}(s^{\prime}|s,\pi)=E_{\pi}[p(s^{\prime}|s,a)]$.

Q-values in this new MDP, $Q^{\Pi}(s,\pi)$ would, in words, correspond to executing policy $\pi$ for one step and executing the policy which maximizes the future discounted value function in the original MDP $M$ thereafter.

Under this redefinition, the Bellman operator $\mathcal{T}^{\Pi}$ is mathematically the same operation as the Bellman operator under $M^{\prime}$. Thus, standard results from MDP theory carry over - i.e. the existence of a fixed point and convergence of repeated application of $\mathcal{T}^{\Pi}$ to said fixed point.

Appendix B Error Propagation

In this section, we provide proofs for Theorem 4.1 and Theorem 4.2.

Suppose we run approximate distribution-constrained value iteration with a set constrained backup $\mathcal{T}^{\Pi}$. Assume that $\delta(s,a)\geq\max_{k}|Q_{k}(s,a)-\mathcal{T}^{\Pi}Q_{k-1}(s,a)|$ bounds the Bellman error. Then,

We first begin by introducing $V^{\Pi}$, the fixed point of $\mathcal{T}^{\Pi}$. By the triangle inequality, we have:

by direct modification of the proof of Theorem 3 of Farahmand et al. or Theorem 1 of Munos with $k=1$ ($p=1$), but replacing $V^{*}$ with $V^{\Pi}$ and $\mathcal{T}$ with $\mathcal{T}^{\Pi}$, as $\mathcal{T}^{\Pi}$ is a contraction and $V^{\Pi}$ is its fixed point. An alternative proof involves viewing $\mathcal{T}^{\Pi}$ as a backup under a modified MDP (see Appendix A), and directly apply Theorem 1 of Munos under this modified MDP. A similar bound also holds true for value iteration with the $\mathcal{T}^{\Pi}$ operator which can be analysed on similar lines as the above proof and Munos .

Adding $L_{1}$ and $L_{2}$ completes the proof. ∎

Assume the data distribution $\mu$ is generated by a behavior policy $\beta$, such that $\mu(s,a)=\mu_{\beta}(s,a)$. Let $\mu(s)$ be the marginal state distribution under the data distribution. Let us define ${\Pi_{\epsilon}}=\{\pi~{}|~{}\pi(a|s)=0\text{ whenever }\beta(a|s)<\epsilon\}$. Then, there exists a concentrability coefficient $C({\Pi_{\epsilon}})$ is bounded as:

where $f(\epsilon)\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny def}}}}{{=}}}\min_{s\in\mathcal{S},\mu_{\Pi}(s)>0}[\mu(s)]$.

For notational clarity, we refer to $\Pi_{\epsilon}$ as $\Pi$ in this proof. The term $\mu_{\Pi}$ is the highest discounted marginal state distribution starting from the initial state distribution $\rho$ and following policies $\pi\in\Pi$. Formally, it is defined as:

Now, we begin the proof of the theorem. We first note, from the definition of $\Pi$, $\forall~{}s\in\mathcal{S}~{}\forall~{}\pi\in\Pi,\pi(a|s)>0\implies\beta(a|s)>\epsilon$. This suggests a bound on the total variation distance between $\beta$ and any $\pi\in\Pi$ for all $s\in\mathcal{S}$, $D_{TV}(\beta(\cdot|s)||\pi(\cdot|s))\leq 1-\epsilon$. This means that the marginal state distributions of $\beta$ and $\Pi$, are bounded in total variation distance by: $D_{TV}(\mu_{\beta}||\mu_{\Pi})\leq\frac{\gamma}{1-\gamma}(1-\epsilon)$, where $\mu_{\Pi}$ is the marginal state distribution as defined above. This can be derived from Schulman et al. , Appendix B, which bounds the difference in returns of two policies by showing the state marginals between two policies are bounded if their total variation distance is bounded.

Further, the definition of the set of policies $\Pi$ implies that $\forall~{}s\in\mathcal{S},\mu_{\Pi}(s)>0\implies\mu_{\beta}(s)\geq f(\epsilon)$, where $f(\epsilon)>0$ is a constant that depends on $\epsilon$ and captures the minimum visitation probability of a state $s\in\mathcal{S}$ when rollouts are executed from the initial state distribution $\rho$ while executing the behaviour policy $\beta(a|s)$, under the constraint that only actions with $\beta(a|s)\geq\epsilon$ are selected for execution in the environment. Combining it with the total variation divergence bound, $\max_{s}||\mu_{\beta}(s)-\mu_{\Pi}(s)||\leq\frac{\gamma}{1-\gamma}(1-\epsilon)$, we get that

We know that, $C(\Pi)\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny def}}}}{{=}}}(1-\gamma)^{2}\sum_{k=1}^{\infty}k\gamma^{k-1}c(k)$ is the ratio of the marginal state visitation distribution under the policy iterates when performing backups using the distribution-constrained operator and the data distribution $\mu=\mu_{\beta}$. Therefore,

Appendix C Additional Details Regarding BEAR-QL

In this appendix, we address several remaining points regarding the support matching formulation of BEAR-QL, and further discuss its connections to prior work.

Another justification is that, a different version of the Bellman error objective renormalizes the action-distributions to the uniform distribution by applying an inverse behavior policy density weighting. For example, use this variant of Bellman error:

This implies that this form of Bellman error mainly depends upon the support of the behaviour policy $\beta$ (i.e. the set of action samples sampled from $\beta$ with a high-enough probability which we formally refer to as $\beta(a|s)\geq\epsilon$ in the main text). In a scenario when this form of Bellman error is being minimized, $\delta_{k}(s,a)$ is defined as

The overall error, hence, incurred due to error propagation is expected to be insensitive to distribution change, provided the support of the distribution doesn’t change. Therefore, all policies $\pi\in{\Pi_{\epsilon}}$ incur the same amount of propagated error ($|V_{k}-V_{\Pi}|$) whereas different amount of suoptimality biases – suggesting the existence of a different policy in ${\Pi_{\epsilon}}$ which propagates the same amount of error while having a lower suboptimality bias. However, in practice, it has been observed that using the inverse density weighting under the behaviour policy doesn’t lead to substantially better performance for vanilla RL (not in the setting with purely off-policy, static datasets), so we use the unmodified Bellman error objective.

Both of these justifications indicate that bounded $\delta_{k}(s,a)$ is reasonable to expect under in-support action distributions.

C.2 Details on connection between BEAR-QL and distribution-constrained backups

Distribution-constrained backups perform maximization over a set of policies ${\Pi_{\epsilon}}$ which is defined as the set of policies that share the support with the behaviour policy. In the BEAR-QL algorithm, $\pi_{\phi}$ is maximized towards maximizing the expected Q-value for each state under the action distribution defined by it, while staying in-support (through the MMD constraint). The maximization step biases $\pi_{\phi}$ towards the in-support actions which maximize the current Q-value. By sampling multiple Dirac-delta action distributions - $\delta_{a_{i}}$ - and then performing an explicit maximum over them for computing the target is a stochastic approximation to the distribution-constrained operator. What is the importance of training the actor to maximize the expected Q-value? We found empirically that this step is important as without this maximization step and high-dimensional action spaces, it is likely to require many more samples (exponentially more, due to curse of dimensionality) to get the correct action that maximizes the target value while being in-support. This is hard and unlikely, and in some experiments we tried with this variant, we found it to lead to suboptimal solutions. At evaluation time, we use the Q-function as the actor. The same process is followed. Dirac-delta action distribution candidates $\delta_{a_{i}}$ are sampled, and then the action $a_{i}$ that is gives the empirical maximum over the Q-function values is the action that is executed in the environment.

C.3 How effective is the MMDMMD\operatorname{MMD} constraint in constraining supports of distributions?

In Section 5, we argued in favour of the usage of the sampled $\operatorname{MMD}$ distance between distributions to search for a policy that is supported on the same support as the train distribution. Revisiting the argument, in this section, we argue, via numerical simulations, the effectiveness of the $\operatorname{MMD}$ distance between two probability distributions in constraining the support of the distribution being learned, without constraining the distribution density function too much. While, MMD distance computed exactly between two distribution functions will match distributions exactly and that explains its applicability in 2-sample tests, however, with a limited number of samples, we empirically find that the values of the $\operatorname{MMD}$ distance computed using samples from two $d$-dimensional Gaussian distributions with diagonal covariance matrices: $P\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny def}}}}{{=}}}\mathcal{N}(\mu_{P},\Sigma_{P})$ and $Q\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny def}}}}{{=}}}\mathcal{N}(\mu_{Q},\Sigma_{Q})$ is roughly equal to the $\operatorname{MMD}$ distance computed using samples from $\mathcal{U}_{\alpha}(P)\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny def}}}}{{=}}}[\text{~{}Uniform}(\mu_{P}^{1}\pm\alpha\Sigma_{P}^{1,1})]\times\cdots\times[\text{~{}Uniform}(\mu_{P}^{d}\pm\alpha\Sigma_{P}^{d,d})]$ and $Q$. This means that when minimizing the $\operatorname{MMD}$ distance to train distribution $Q$, the gradient signal would push $Q$ towards a uniform distribution supported on $P$’s support as this solution exhibits a lower MMD value – which is the objective we are optimizing.

Figure 7 shows an empirical comparison of $\operatorname{MMD}(P,Q)$ when $Q=P$, computed by sampling $n$-samples from $P$, and $\operatorname{MMD}(\mathcal{U}_{\alpha}(P),Q)$ (also when $Q$ = $P$) computed by sampling $n$-samples from $\mathcal{U}_{\alpha}(P)$. We observe that $\operatorname{MMD}$ distance computed using limited samples can, in fact, be higher between a distribution and itself as compared to a uniform distribution over a distribution’s support and itself. In Figure 7, note that for smaller values of $n$ and appropriately chosen $\alpha$ (mentioned against each figure, the support of the uniform distribution), the estimator for $\operatorname{MMD}(\mathcal{U}_{\alpha}(P),P)$ can provide lower estimates than the value of the estimator for $\operatorname{MMD}(P,P)$. This observation suggests that when the number of samples is not enough to sample infer the distribution shape, density-agnostic distances like MMD can be used as optimization objectives to push distributions to match supports. Subfigures (c) and (d) shows the increase in MMD distance as the support of the uniform distribution is expanded.

Appendix D Additional Experimental Details

We trained behaviour policies using the Soft Actor-Critic algorithm . In all cases, random data was generated by running a uniform at random policy in the environment. Optimal data was generated by training SAC agents in all 4 domains until convergence to the returns mentioned in Figure 5. Mediocre data was generated by training a policy until the return value marked in each of the plots in Figure 3. Each of our datasets contained 1e6 samples. We used the same datasets for evaluating different algorithms to maintain uniformity across results.

In our experiments, we found that the choice of the kernel is an important design decision that needs to be made. In general, we found that a Laplacian kernel $k(x,y)=\exp(\frac{-||x-y||}{\sigma})$ worked well in all cases. Gaussian kernel $k(x,y)=\exp(\frac{-||x-y||^{2}}{2\sigma^{2}})$ worked quite well in the case of optimal dataset. For the Laplacian kernel, we chose $\sigma=10.0$ for Cheetah, Ant and Hopper, and $\sigma=20.0$ for Walker. However, we found that $\sigma=20.0$ worked well for all environments in all settings. For the Gaussian kernel, we chose $\sigma=20.0$ for all settings. Kernels often tend to not provide relevant measurements of distance especially in high-dimensional spaces, so one direction for future work is to design right kernels. We further experimented with a mixture of Laplacian kernel with different bandwidth parameters $\sigma$ ($1.0,10.0,50.0$) on Hopper-v2 and Walker2d-v2 where we found that it performs comparably and sometimes is better than a simple Laplacian kernel, probably because it is able to track supports upto different levels of thresholds due to multiple kernels.

At evaluation time, we find that using the greedy maximum of the Q-function over the support set of the behaviour policy (which can be approximated by sampling multiple Dirac-delta policies $\delta_{a_{i}}$ from the policy $\pi_{\phi}$ and performing a greedy maximization of the Q-values over these Dirac-delta policies) works best, better than unrolling the learned actor $\pi_{\phi}$ in the environment. This was also found useful in . Another detail about the algorithm is deciding which samples to use for computing the $\operatorname{MMD}$ objective. We train a parameteric model $\pi_{data}$ which fits a tanh-Gaussian distribution to $a$ given the states $s$, $\pi_{data}(\cdot|s)=\tanh{\mathcal{N}(\mu(\cdot|s),\sigma(\cdot|s))}$ and then use this to sample a candidate $n$ actions for computing the MMD-distance, meaning that MMD is computed between $a_{1},\cdots,a_{N}\sim\pi_{data}$ and $\pi_{\phi}$. We find the latter to work better in practice. Also, computing the $\operatorname{MMD}$ distance between actions before applying the tanh transformation work better, and leads to a constraint, that perhaps provides stronger gradient signal – because tanh saturates very quickly, after which gradients almost vanish.

Other hyperparameters include the following – (1) The variance of the Gaussian $\sigma^{2}$ /(standard deviation of) Laplacian kernel $\sigma$: We tried a variance of 10, 20, and 40. We found that 10 and 20 worked well across Cheetah, Hopper and Ant, and 20 worked well for Walker2d; (2) The learning rate for the Lagrange multiplier was chosen to be 1e-3, and the $\log$ of the Lagrange multiplier was clipped between $$ to prevent instabilities; (3) For the policy improvement step, we found using average Q works better than min Q for Walker2d. For the baselines, we used BCQ code from the official implementation accompanying , TD3 code from the official implementation accompanying and the BC baseline was the VAE-based behaviour cloning baseline also used in . We evaluated on 10 evaluation episodes (which were separate from the train distribution) after every 1000 iterations and used the average score and the variance for the plots.

Appendix E Additional Experimental Results

In this section, we provide some extra plots for some extra experiments. In Figure 8 we provide the difference between learned Q-values and Monte carlo returns of the policy in the environment. In Figure 9 we provide the trends of comparisons of Q-values learned by BEAR-QL and BCQ in three environments. In Figure 10 we compare the performance when using the MMD constraint vs using the KL constraint in the case of three environments. In order to be fair at comparing to MMD, we train a model for the behaviour policy and constrain the KL-divergence to this behaviour policy. (For MMD, we compute MMD using samples from the model of the behaviour policy.) Note that in the case of Half Cheetah with medium-quality data, KL divergence constraint works pretty well, but it fails drastically in the case of Hopper and Walker2d and the Q-values tend to diverge. Figure 10 summarizes the trends for 3 environments.

We further study the performance of the KL-divergence in the setting when the KL-divergence is stable. In this setting we needed to perform extensive hyperparameter tuning to find the optimal Lagrange multiplier for the KL-constraint and plain and simple dual descent always gave us an unstable solution with the KL-constraint. Even in this case tuned hyperparameter case, we find that using a KL-constraint is worse than using a MMD-constraint. Trends are summarized in Figure 11.

As described in Section C, we can achieve a reduced overall error $||V_{k}(s)-V^{*}(s)||$, if we use the MMD support-matching constraint alongside importance sampling, i.e. when we multiply the Bellman error with the inverse of the behaviour policy density. Empirically, we tried reweighting the Bellman error by inverse of the fitted behavior policy density, alongside the BEAR-QL algorithm. The trends for two environments and medium-quality data are summarized in Figure 12. We found that reweighting the Bellman error wasn’t that useful, although in theory, it provides an absolute error reduction as described by Theorem 4.1. We hypothesize that this could be due to the possible reason that when optimizing neural nets using stochastic gradient procedures, importance sampling isn’t that beneficial .