PESSIMISTIC BOOTSTRAPPING FOR UNCERTAINTY- DRIVEN OFFLINE REINFORCEMENT LEARNING
Year: 2022

Abstract:
Offline Reinforcement Learning (RL) aims to learn policies from previously collected datasets without exploring the environment. Directly applying off-policy algorithms to offline RL usually fails due to the extrapolation error caused by the out-of-distribution (OOD) actions. Previous methods tackle such problems by penalizing the Q-values of OOD actions or constraining the trained policy to be close to the behavior policy. Nevertheless, such methods typically prevent the generalization of value functions beyond the offline data and also lack a precise characterization of OOD data. In this paper, we propose Pessimistic Bootstrapping for offline RL (PBRL), a purely uncertainty-driven offline algorithm without explicit policy constraints. Specifically, PBRL conducts uncertainty quantification via the disagreement of bootstrapped Q-functions, and performs pessimistic updates by penalizing the value function based on the estimated uncertainty. To tackle the extrapolating error, we further propose a novel OOD sampling method. We show that such OOD sampling and pessimistic bootstrapping yields a provable uncertainty quantifier in linear MDPs, thus providing the theoretical underpinning for PBRL. Extensive experiments on D4RL benchmark show that PBRL has better performance compared to the state-of-the-art algorithms.

heading: 1 INTRODUCTION
text: Deep Reinforcement Learning (DRL) (Sutton & Barto, 2018) achieves remarkable success in a variety of tasks. However, in most successful applications, DRL requires millions of interactions with the environment. In real-world applications such as navigation (Mirowski et al., 2018) and healthcare (Yu et al., 2019), acquiring a large number of samples by following a possibly suboptimal policy can be costly and dangerous. Alternatively, practitioners seek to develop RL algorithms that learn a policy based solely on an offline dataset, where the dataset is typically available. However, directly adopting online DRL algorithms to the offline setting is problematic. On the one hand, policy evaluation becomes challenging since no interaction is allowed, which limits the usage of on-policy algorithms. On the other hand, although it is possible to slightly modify the off-policy value-based algorithms and sample solely from the offline dataset in training, such modification typically suffers from a significant performance drop compared with their online learning counterpart (Levine et al., 2020). An important reason for such performance drop is the so-called distributional shift. Specifically, the offline dataset follows the visitation distribution of the behavior policies. Thus, estimating the Q-functions of the corresponding greedy policy with the offline dataset is biased due to the difference in visitation distribution. Such bias typically leads to a significant extrapolation error for DRL algorithms since the estimated Q-function tends to overestimate the out-of-distribution (OOD) actions (Fujimoto et al., 2019).
To tackle the distributional shift issue in offline RL, previous successful approaches typically fall into two categories, namely, policy constraint (Kumar et al., 2019; Fujimoto & Gu, 2021) and conservatism (Kumar et al., 2020; Yu et al., 2020; 2021). Policy constraint aims to restrict the learned policy to be close to the behavior policy, thus reducing the extrapolation error in policy evaluation. Conservatism methods seek to penalize the Q-functions for OOD actions in policy evaluation and hinge on a gap-expanding property to regularize the OOD behavior. Nevertheless, since policy constraints explicitly confine the policy to be close to the behavior policy, it tends to be easily affected by the non-optimal behavior policy. Meanwhile, although the conservatism algorithms such as CQL (Kumar et al., 2020) do not require policy constraints, CQL equally penalizes the OOD actions and lacks a precise characterization of the OOD data, which can lead to overly conservative value functions. To obtain a more refined characterization of the OOD data, uncertainty quantification is shown to be effective when associated with the model-based approach (Yu et al., 2020; Kidambi et al., 2020), where the dynamics model can be learned in static data thus providing more stable uncertainty in policy evaluation. Nevertheless, model-based methods need additional modules and may fail when the environment becomes high-dimensional and noisy. In addition, the uncertainty quantification in model-free RL is more challenging since the Q-function and uncertainty quantifier need to be learned simultaneously (Yu et al., 2021).
To this end, we propose Pessimistic Bootstrapping for offline RL (PBRL), an uncertainty-driven model-free algorithm for offline RL. To acquire reliable Q-function estimates and their corresponding uncertainty quantification, two components of PBRL play a central role, namely, bootstrapping and OOD sampling. Specifically, we adopt bootstrapped Q-functions (Osband et al., 2016) for uncertainty quantification. We then perform pessimistic Q-updates by using such quantification as a penalization. Nevertheless, solely adopting such penalization based on uncertainty quantification is neither surprising nor effective. Training the Q-functions based solely on the offline dataset does not regularize the OOD behavior of the Q-functions and suffers from the extrapolation error. To this end, we propose a novel OOD sampling technique as a regularizer of the learned Q-functions. Specifically, we introduce additional OOD datapoints into the training buffer. The OOD datapoint consists of states sampled from the training buffer, the corresponding OOD actions sampled from the current policy, and the corresponding OOD target based on the estimated Q-function and uncertainty quantification. We highlight that having such OOD samples in the training buffer plays an important role in both the Q-function estimation and the uncertainty quantification. On the one hand, OOD sampling controls the OOD behavior in training, which guarantees the stability of the trained bootstrapped Q-functions. On the other hand, a stable estimation of the bootstrapped Qfunctions further ensures that the uncertainty quantification is reliable. We further show that PBRL is provably efficient under the linear MDP assumptions.
We highlight that PBRL exploits the OOD state-action pairs by casting a more refined penalization over OOD data points, allowing PBRL to acquire better empirical performance than the policyconstraint and conservatism baselines. As an example, if an action lies close to the support of offline data but is not contained in the offline dataset, the conservatism (Kumar et al., 2020) and policy constraint (Fujimoto et al., 2019) methods tend to avoid selecting it. In contrast, PBRL tends to assign a small Q-penalty for such an action as the underlying epistemic uncertainty is small. Hence, the agent trained with PBRL may consider such action if the corresponding value estimate is high, yielding better performance than the policy constraint and conservatism baselines. Our experiments on the D4RL benchmark (Fu et al., 2020) show that PBRL provides reasonable uncertainty quantification and yields better performance compared to the state-of-the-art algorithms.

heading: 2 PRELIMINARIES
text: We consider an episodic MDP defined by the tuple (S,A, T, r,P), where S is the state space, A is the action space, T ∈ N is the length of episodes, r is the reward function, and P is the transition distribution. The goal of RL is to find a policy π that maximizes the expected cumulative rewards E [∑T−1
i=0 γ tri], where γ ∈ [0, 1) is the discount factor in episodic settings. The corresponding
Q-function of the optimal policy satisfies the following Bellman operator, T Qθ(s, a) := r(s, a) + γEs′∼T (·|s,a) [
max a′
Qθ−(s ′, a′) ] . (1)
where θ is the parameters of Q-network. In DRL, the Q-value is updated by minimizing the TDerror, namely E(s,a,r,s′)[(Q−T Q)2]. Empirically, the target T Q is typically calculated by a separate
target-network parameterized by θ− without gradient propagation (Mnih et al., 2015). In online RL, one typically samples the transitions (s, a, r, s′) through iteratively interacting with the environment. The Q-network is then trained by sampling from the collected transitions.
In contrast, in offline RL, the agent is not allowed to interact with the environment. The experiences are sampled from an offline dataset Din = {(sit, ait, rit, sit+1)}i∈[m]. Naive off-policy methods such as Q-learning suffer from the distributional shift, which is caused by different visitation distribution of the behavior policy and the learned policy. Specifically, the greedy action a′ chosen by the target Q-network in s′ becomes OOD-action since (s′, a′) is not contained in Din. The value functions evaluated on OOD actions have significant extrapolation errors. Such errors can be further amplified through propagation and potentially diverges during training. In what follows, we introduce PBRL, which tackles such a challenge by uncertainty quantification and OOD sampling.

heading: 3 PESSIMISTIC BOOTSTRAPPING FOR OFFLINE RL

heading: 3.1 UNCERTAINTY QUANTIFICATION WITH BOOTSTRAPPING
text: In PBRL, we maintain K bootstrapped Q-functions in critic to quantify the epistemic uncertainty. Formally, we denote Qk as the k-th Q-function in the ensemble. Qk is updated by fitting the following target
T̂ Qkθ(s, a) := r(s, a) + γÊs′∼P (·|s,a),a′∼π(·|s) [ Qkθ−(s ′, a′) ] , (2)
where we denote T̂ as the empirical Bellman operator, which estimates the expectation E[Qkθ−(s
′, a′) | s, a] empirically based on the offline dataset. We adopt such an ensemble technique from Bootstrapped DQN (Osband et al., 2016), which is initially proposed for the online exploration task. Intuitively, the ensemble forms an estimation of the posterior distribution of the estimated Qfunctions, which yields similar value on areas with rich data and diversely on areas with scarce data. Indeed, the deviation among the bootstrapped Q-functions yields an epistemic uncertainty estimation, which we aim to utilize as a penalization in estimating the Q-functions. Specifically, we introduce the following uncertainty quantification U(s, a) based on the Q-functions {Qk}k∈[K],
U(s, a) := Std(Qk(s, a)) = √ 1
K ∑K k=1 ( Qk(s, a)− Q̄(s, a) )2 . (3)
Here we denote Q̄ as the mean among the ensemble of Q-functions. From the Bayesian perspective, such uncertainty quantification yields an estimation of the standard deviation of the posterior of Q-functions. To better understand the effectiveness of such uncertainty quantification, we illustrate with a simple prediction task. We use 10 neural networks with identical architecture and different initialization as the ensemble. We then train the ensemble with 60 datapoints in R2 plane, where the covariate x is generated from the standard Gaussian distribution, and the response y is obtained by feeding x into a randomly generated neural network. We plot the datapoints for training and the uncertainty quantification in Fig. 1(a). As shown in the figure, the uncertainty quantification rises smoothly from the in-distribution datapoints to the OOD datapoints.
In offline RL, we perform regression (s, a) → T̂ Qk(s, a) in Din to train the bootstrapped Qfunctions, which is similar to regress x → y in the illustrative task. The uncertainty quantification allows us to quantify the deviation of a datapoint from the offline dataset, which provides more refined conservatism compared to the previous methods (Kumar et al., 2020; Wu et al., 2019).

heading: 3.2 PESSIMISTIC LEARNING
text: We now introduce the pessimistic value iteration based on the bootstrapped uncertainty quantification. The idea is to penalize the Q-functions based on the uncertainty quantification. To this end, we propose the following target for state-action pairs sampled from Din,
T̂ inQkθ(s, a) := r(s, a) + γÊs′∼P (·|s,a),a′∼π(·|s) [ Qkθ−(s ′, a′)− βin Uθ−(s′, a′) ] , (4)
where Uθ−(s′, a′) is the uncertainty estimation at (s′, a′) based on the target network, and βin is a tuning parameter. In addition, the empirical mean Ês′∼P (·|s,a),a′∼π(·|s) is obtained by sampling the
transition (s, a, s′) fromDin and further sampling a′ ∼ π(· | s′) from the current policy π. We denote T̂ inQkθ(s, a) as the in-distribution target of Qkθ(s, a) and write T̂ in to distinguish the in-distribution target from that of the OOD target, which we introduce in the sequel.
We remark that there are two options to penalize the Q-functions through the operator T̂ in. In Eq. (4), we penalize the next-Q value Qkθ−(s
′, a′) with the corresponding uncertainty Uθ−(s′, a′). Alternatively, we can also penalize the immediate reward by
r̂(s, a) := r(s, a)− Uθ(s, a), and use r̂(s, a) in place of r(s, a) for the target. Nevertheless, since the datapoint (s, a) ∈ Din lies on rich-data areas, the penalization Uθ(s, a) on the immediate reward is usually very small thus having less effect in training. In PBRL, we penalize the uncertainty of (s′, a′) in the next-Q value.
Nevertheless, our empirical findings in §D suggest that solely penalizing the uncertainty for indistribution target is insufficient to control the OOD performance of the fitted Q-functions. To enforce direct regularization over the OOD actions, we incorporate the OOD datapoints directly in training and sample OOD data of the form (sood, aood) ∈ Dood. Specifically, we sample OOD states from the in-distribution dataset Din. Correspondingly, we sample OOD actions aood by following the current policy π(· | sood). We highlight that such OOD sampling requires only the offline dataset Din and does not require additional generative models or access to the simulator. It remains to design the target for OOD samples. Since the transition P (· | sood, aood) and reward r(sood, aood) are unknown, the true target of OOD sample is inapplicable. In PBRL, we propose a novel pseudo-target for the OOD datapoints,
T̂ oodQkθ(sood, aood) := Qkθ(sood, aood)− βood Uθ(sood, aood) , (5)
which introduces an additional uncertainty penalization Uθ(sood, aood) to enforce pessimistic Qfunction estimation, and βood is a tuning parameter. For OOD samples that are close to the indistribution data, such penalization is small and the OOD target is close to the Q-function estimation. In contrast, for OOD samples that are distant away from the in-distribution dataset, a larger penalization is incorporated into the OOD target. In our implementation, we introduce an additional truncation to stabilize the early stage training as max{0, T oodQkθ(sood, aood)}. In addition, we remark that βood is important to the empirical performance. Specifically,
• At the beginning of training, both the Q-functions and the corresponding uncertainty quantifications are inaccurate. We use a large βood to enforce a strong regularization on OOD actions.
• We then gradually decrease βood in the training process since the value estimation and uncertainty quantification becomes more accurate in training. A decreased βood makes the uncertainty more critical to decide the scale of pessimism in T̂ oodQk. The decay of βood also makes Qkθ(s ood, aood) does not diverge.
Incorporating both the in-distribution target and OOD target, we conclude the loss function for critic in PBRL as follows,
Lcritic = Ê(s,a,r,s′)∼Din [ (T̂ inQk −Qk)2 ] + Êsood∼Din,aood∼π [ (T̂ oodQk −Qk)2 ] , (6)
where we iteratively minimize the regular TD-error for the offline data and the pseudo TD-error for the OOD data. PBRL obtains a smooth and pessimistic value function by reducing the extrapolation error caused by high-uncertain state-action pairs for both (s, a) and (sood, aood).
Based on the pessimistic Q-functions, the corresponding policy is obtained by the following maximization problem,
πϕ := max ϕ
Ês∼Din,a∼π(·|s) [
min k=1,...,K
Qk(s, a) ] , (7)
where ϕ is the policy parameters. Taking the minimum among ensembleQ-functions is also adopted in previous actor-critic methods like SAC (Haarnoja et al., 2018) and TD3 (Fujimoto et al., 2018). The overall architecture of PBRL is illustrated in Fig. 1(b).

heading: 3.3 THEORETICAL CONNECTIONS TO LCB-PENALTY
text: In this section, we show the pessimistic target in PBRL aligns with the recent theoretical investigation on offline RL (Jin et al., 2021; Xie et al., 2021a). From the theoretical perspective, an appropriate uncertainty quantification is essential to the provable efficiency in offline RL. Specifically, the ξ-uncertainty quantifier plays a central role in the analysis of both online and offline RL (Jaksch et al., 2010; Azar et al., 2017; Wang et al., 2020a; Jin et al., 2020; 2021; Xie et al., 2021a;b).
Definition 1 (ξ-Uncertainty Quantifier (Jin et al., 2021)). The set of penalization {Γt}t∈[T ] forms a ξ-Uncertainty Quantifier if it holds with probability at least 1− ξ that
|T̂ Vt+1(s, a)− T Vt+1(s, a)| ≤ Γt(s, a)
for all (s, a) ∈ S × A, where T is the Bellman equation and T̂ is the empirical Bellman equation that estimates T based on the offline data.
In linear MDPs (Jin et al., 2020; Wang et al., 2020a; Jin et al., 2021) where the transition kernel and reward function are assumed to be linear to the state-action representation φ : S × A → Rd, The following LCB-penalty (Abbasi-Yadkori et al., 2011; Jin et al., 2020) is known to be a ξ-uncertainty quantifier for appropriately selected {βt}t∈[T ],
Γlcb(st, at) = βt · [ φ(st, at) >Λ−1t φ(st, at) ]1/2 , (8)
where Λt = ∑m i=1 φ(s i t, a i t)φ(s i t, a i t) > + λ · I accumulates the features of state-action pairs in Din and plays the role of a pseudo-count intuitively. We remark that under such linear MDP assumptions, the penalty proposed in PBRL and Γlcb(st, at) in linear MDPs is equivalent under a Bayesian perspective. Specifically, we make the following claim.
Claim 1. In linear MDPs, the proposed bootstrapped uncertainty βt · U(st, at) is an estimation to the LCB-penalty Γlcb(st, at) in Eq. (8) for an appropriately selected tuning parameter βt.
We refer to §A for a detailed explanation and proof. Intuitively, the bootstrapped Q-functions estimates a non-parametric Q-posterior (Osband et al., 2016; 2018a). Correspondingly, the uncertainty quantifier U(st, at) estimates the standard deviation of the Q-posterior, which scales with the LCBpenalty in linear MDPs. As an example, we show that under the tabular setting, Γlcb(st, at) is approximately proportional to the reciprocal pseudo-count of the corresponding state-action pair in the dataset (See Lemma 2 in §A). In offline RL, such uncertainty quantification measures how trustworthy the value estimations on state-action pairs are. A low LCB-penalty (or high pseudo-count) indicates that the corresponding state-action pair aligns with the support of offline data.
Under the linear MDP or Bellman-consistent assumptions, penalizing the estimated value function based on the uncertainty quantification is known to yield an efficient offline RL algorithm (Jin et al., 2021; Xie et al., 2021a;b). However, due to the large extrapolation error of neural networks, we find that solely penalizing the value function of the in-distribution samples is insufficient to regularize the fitted value functions of OOD state-action pairs.
A key to the success of linear MDP algorithms (Jin et al., 2020; Wang et al., 2020a; Jin et al., 2021) is the extrapolation ability through L2-regularization in the least-squares value iteration (LSVI), which guarantees that the linear parameterized value functions behave reasonably on OOD stateaction pairs. From a Bayesian perspective, such L2-regularization enforces a Gaussian prior on the estimated parameter of linear approximations, which regularizes the value function estimation on OOD state-action pairs with limited data available. Nevertheless, our empirical study in §D shows that L2-regularization is not sufficient to regularize the OOD behavior of neural networks.
To this end, PBRL introduces a direct regularization over an OOD dataset. From the theoretical perspective, we observe that adding OOD datapoint (sood, aood, y) into the offline dataset leads to an equivalent regularization to the L2-regularization under the linear MDP assumption. Specifically, in linear MDPs, such additional OOD sampling yields a covariate matrix of the following form,
Λ̃ = ∑m
i=1 φ(sit, a i t)φ(s i t, a i t) > + ∑ (sood,aood,y)∈Dood φ(sood, aood)φ(sood, aood)>, (9)
where the matrix Λood = ∑
(sood,aood,y)∈Dood φ(s ood, aood)φ(sood, aood)> plays the role of the λ·I prior
in LSVI. It remains to design a proper target y in the OOD datapoint (sood, aood, y). The following theorem show that setting y = T Vh+1(sood, aood) leads to a valid ξ-uncertainty quantifier under the linear MDP assumption. Theorem 1. Let Λood λ · I . Under the linear MDP assumption, for all the OOD datapoint (sood, aood, y) ∈ Dood, if we set y = T Vt+1(sood, aood), it then holds for βt = O ( T · √ d · log(T/ξ)
) that Γlcbt (st, at) = βt [ φ(st, at) >Λ−1t φ(st, at) ]1/2 forms a valid ξ-uncertainty quantifier.
We refer to §A for a detailed discussion and proof. Theorem 1 shows that if we set y = T Vt+1(sood, aood), the bootstrapped uncertainty based on disagreement among ensembles is a valid ξ-uncertainty quantifier. However, such an OOD target is impossible to obtain in practice as it requires knowing the transition at the OOD datapoint (sood, aood). In practice, if TD error is sufficiently minimized, then Q(sood, aood) should well estimate the target T Vt+1. Thus, in PBRL, we utilize
y = Q(sood, aood)− Γlcb(sood, aood) (10) as the OOD target, where we introduce an additional penalization Γlcb(sood, aood) to enforce pessimism. In addition, we remark that in theory, we require that the embeddings of the OOD sample are isotropic, in the sense that the eigenvalues of the corresponding covariate matrix Λood are lower bounded. Such isotropic property can be guaranteed by randomly generating states and actions. In practice, we find that randomly generating states is more expensive than randomly generating actions. Meanwhile, we observe that randomly generating actions alone are sufficient to guarantee reasonable empirical performance since the generated OOD embeddings are sufficiently isotropic. Thus, in our experiments, we randomly generate OOD actions according to our current policy and sample OOD states from the in-distribution dataset.

heading: 4 RELATED WORKS
text: Previous model-free offline RL algorithms typically rely on policy constraints to restrict the learned policy from producing the OOD actions. In particular, previous works add behavior cloning (BC) loss in policy training (Fujimoto et al., 2019; Fujimoto & Gu, 2021; Ghasemipour et al., 2021), measure the divergence between the behavior policy and the learned policy (Kumar et al., 2019; Wu et al., 2019; Kostrikov et al., 2021), apply advantage-weighted constraints to balance BC and advantages (Siegel et al., 2020; Wang et al., 2020b), penalize the prediction-error of a variational auto-encoder (Rezaeifar et al., 2021), and learn latent actions (or primitives) from the offline data (Zhou et al., 2020; Ajay et al., 2021). Nevertheless, these methods may cause overly conservative value functions and are easily affected by the behavior policy (Nair et al., 2020; Lee et al., 2021b). We remark that the OOD actions that align closely with the support of offline data could also be trustworthy. CQL (Kumar et al., 2020) directly minimizes the Q-values of OOD samples and thus casts an implicit policy constraint. Our method is related to CQL since both PBRL and CQL enforce conservatism in Q-learning. In contrast, we conduct explicit uncertainty quantification for OOD actions in pessimistic Q-learning, while CQL penalizes the Q-values of all OOD samples equally.
In contrast with model-free algorithms, model-based algorithms learn the dynamics model directly with supervised learning. Similar to our work, MOPO (Yu et al., 2020) and MOReL (Kidambi et al.,
2020) incorporate ensemble dynamics-model for uncertainty quantification, and penalize the value function through pessimistic updates. Other than the uncertainty quantification, previous modelbased methods also attempt to constrain the learned policy through BC loss (Matsushima et al., 2020), advantage-weighted prior (Cang et al., 2021), CQL-style penalty (Yu et al., 2021), and Riemannian submanifold (Tennenholtz et al., 2021). Decision Transformer (Chen et al., 2021) builds a transformer-style dynamic model and casts the problem of offline RL as conditional sequence modeling. The model-based methods suffer from additional computation costs and perform suboptimally in high-dimensional and stochastic environments (Chua et al., 2018; Janner et al., 2019). In contrast, PBRL conducts model-free learning and is less affected by such challenges.
Our method is related to the previous online RL exploration algorithms based on uncertainty quantification, including bootstrapped Q-networks (Bai et al., 2021; Lee et al., 2021a), ensemble dynamics (Sekar et al., 2020), Bayesian neural network (O’Donoghue et al., 2018; Azizzadenesheli et al., 2018), and distributional value functions (Mavrin et al., 2019; Nikolov et al., 2019). Uncertainty quantification is more challenging in offline RL than its online counterpart due to the limited coverage of offline data and the distribution shift of the learned policy. In model-based offline RL, framework, MOPO (Yu et al., 2020) and MOReL (Kidambi et al., 2020) incorporate ensemble dynamics-model for uncertainty quantification. BOPAH (Lee et al., 2020) combines uncertainty penalization and behavior-policy constraints, and adopts a gradient-based optimization for hyperparameters. In model-free offline RL, UWAC (Wu et al., 2021) adopts dropout-based uncertainty (Gal & Ghahramani, 2016) while relying on policy constraints in learning value functions. In contrast, PBRL does not require additional policy constraints. In addition, according to the previous study in image prediction with data shift (Ovadia et al., 2019), the bootstrapped uncertainty is more robust to data shift than the dropout-based approach. EDAC (An et al., 2021) is a concurrent work that uses the ensemble Q-network to ensure pessimism. Specifically, EDAC calculates the gradients of each Q-function and diversifies such gradients to ensure sufficient penalization for OOD actions. In contrast, PBRL penalizes the OOD actions through direct OOD sampling and the associated uncertainty quantification. Empirically, EDAC typically requires more Q-networks than PBRL.
Our algorithm is inspired by the recent advances in the theory of both online RL and offline RL. Previous works propose provably efficient RL algorithms under the linear MDP assumption for both the online setting (Jin et al., 2020) and offline setting (Jin et al., 2021), which we follow for our analysis. In addition, previous works also study the offline RL under the Bellman completeness assumptions (Modi et al., 2021; Uehara et al., 2021; Xie et al., 2021a; Zanette et al., 2021). Previous works also study the model-based RL under the kernelized nonlinear regulator (KNR) setting (Kakade et al., 2020; Mania et al., 2020; Chang et al., 2021). In contrast, our paper focus on model-free RL.

heading: 5 EXPERIMENTS
text: In experiments, we further include an algorithm named PBRL-prior, a slight modification to PBRL by using random prior functions (Osband et al., 2018b) that are originally proposed for Bootstrapped DQN (Osband et al., 2016). Specifically, each Q-function in PBRL-Prior contains a trainable network Qkθ and a prior network pk, where pk is randomly initialized and keeps fixed in training. The prediction of each Q-function is the sum of the trainable network and the fixed prior as Qkp = Q k θ + pk, where Q k θ and pk have the same network architecture. The random prior function increases the diversity among ensemble members and improves the generalization of bootstrapped functions (Osband et al., 2018b). We adopt SAC (Haarnoja et al., 2018) as the basic actor-critic architecture for both PBRL and PBRL-prior. We refer to §B for the implementation details. The code is available at https://github.com/Baichenjia/PBRL.
In D4RL benchmark (Fu et al., 2020) with various continuous-control tasks and datasets, we compare the baseline algorithms on the Gym and Adroit domains, which are more extensively studied in the previous research. We compare PBRL and PBRL-Prior to several state-of-the-art algorithms, including (i) BEAR (Kumar et al., 2019) that enforces policy constraints through the MMD distance, (ii) UWAC (Wu et al., 2021) that improves BEAR through dropout uncertainty-weighted update, (iii) CQL (Kumar et al., 2020) that learns conservative value functions by minimizing Q-values of OOD actions, (iv) MOPO (Yu et al., 2020) that quantifies the uncertainty through ensemble dynamics in a model-based setting, and (v) TD3-BC (Fujimoto & Gu, 2021), which adopts adaptive BC constraint to regularize the policy in training.
Results in Gym domain. The Gym domain includes three environments (HalfCheetah, Hopper, and Walker2d) with five dataset types (random, medium, medium-replay, medium-expert, and expert), leading to a total of 15 problem setups. We train all the baseline algorithms in the latest released ‘v2’ version dataset, which is also used in TD3-BC (Fujimoto & Gu, 2021) for evaluation. For methods that are originally evaluated on the ‘v0’ dataset, we retrain these methods with their official implementations. We refer to §B for the training details. We train each method for one million time steps and report the final evaluation performance through online interaction. Table 1 reports the normalized score for each task and the corresponding average performance. We find CQL and TD3-BC perform the best among all baselines, and PBRL outperforms the baselines in most of the tasks. In addition, PBRL-Prior slightly outperforms PBRL and is more stable in training with a reduced variance among different seeds.
Compared to the baseline algorithms, PBRL has strong advantages in the non-optimal datasets, including medium, medium-replay, and mediumexpert. Compared to the policy-constraint baselines, PBRL exploits the optimal trajectory covered in the dataset in a theoretically grounded way and is less affected by the behavior policy. We give the average training curves in Fig. 2. The training speeds of PBRL and PBRL-Prior are slower than TD3-BC and CQL in the early stage, indicating that the uncertainty quantification is inaccurate initially. Nevertheless, PBRL and PBRL-Prior converge to better policies that outperform the baselines in the learning of uncertainty quantifiers.
Results in Adroit domain. The adroit tasks are more challenging than the Gym domain in task complexity. In addition, the use of human demonstration in the dataset also makes the task more challenging. We refer the results in §E. We observe that CQL and BC have the best average performance in all baselines, and PBRL outperforms baselines in most of the tasks.
Uncertainty quantification. To verify the effectiveness of the bootstrapped uncertainty quantification, we record the uncertainty quantification for different sets of state-action pairs in training. In
our experiments, we consider sets that have the same states from the offline dataset but with different types of actions, including (i) aoffline, which is drawn from the offline in-distribution transition; (ii) apolicy, which is selected by the training policy; (iii) arand, which is uniformly sampled from the action space of the corresponding task; (iv) anoise1 = aoffline + N (0, 0.1), which adds a small Gaussian noise onto the offline action to represent state-action pair that is close to in-distribution data; and (v) anoise2 = aoffline +N (0, 0.5), which adds a large noise to represent the OOD action. We compute the uncertainty and Q-value in ‘Walker2d’ task with two datasets (‘medium-replay’ and ‘medium’). The results are shown in Fig. 3. We observe that (i) PBRL yields large uncertainties for (s, anoise2) and (s, arandom), showing that the uncertainty quantification is high on OOD samples. (ii) The (s, aoffline) pair has the smallest uncertainty in both settings as it is an in-distribution sample. (iii) The (s, anoise1) pair has slightly higher uncertainty compared to (s, aoffline), showing that the uncertainty quantification rises smoothly from the in-distribution actions to the OOD actions. (iv) The Q-function of the learned policy (s, apolicy) is reasonable and does not deviate much from the in-distribution actions, which shows that the learned policy does not take actions with high uncertainty due to the penalty with uncertainty quantification. In addition, we observe that by incorporating the uncertainty quantification and OOD sampling, the Q-functions obtained by PBRL does not suffer from the extrapolation error issue caused by distributional shift.
Ablation study. In the following, we briefly report the result of the ablation study. We refer to §C and §D for the details. (i) Number of bootstrapped-Q. We attempt different numbers K of bootstrapped-Q in PBRL, and find the performance to be reasonable for K ≥ 6. (ii) Penalization in T̂ in. We conduct experiments with the penalized reward discussed in §3.2 and find the penalized reward does not improve the performance. (iii) Factor βin in T̂ in. We conduct experiments with different βin from {0.1, 0.01, 0.001, 0.0001} to study the sensitiveness. Our experiments show that PBRL performs the best for βin ∈ [0.0001, 0.01]. (iv) Factor βood. We use a large βood at the initial training stage to enforce strong regularization over the OOD actions, and gradually decrease βood in training. We conduct experiments by setting βood to different constants, and find our decaying strategy generalizes better among tasks. (v) The learning target of OOD actions. We change the learning target of OOD actions to the most pessimistic zero target y = 0 and find such a setting leads to overly pessimistic value functions with suboptimal performance. (vi) Regularization types. We conduct experiments with different regularization types, including our proposed OOD sampling, L2-regularization, spectral normalization, pessimistic initialization, and no regularization. We find OOD sampling the only reasonable regularization strategy and defer the complete report to §D.

heading: 6 CONCLUSION
text: In this paper, we propose PBRL, an uncertainty-based model-free offline RL algorithm. We propose bootstrapped uncertainty to guide the provably efficient pessimism, and a novel OOD sampling technique to regularize the OOD actions. PBRL is closely related to the provable efficient offline RL algorithm under the linear MDP assumption (Jin et al., 2021). Our experiments show that PBRL outperforms several strong offline RL baselines in the D4RL environments, especially for suboptimal datasets. PBRL exploits the optimal trajectories contained in the suboptimal dataset and is less affected by the behavior policy. Our illustrations suggest that incorporated with OOD sampling, PBRL produces reliable uncertainty quantifications and does not suffer from the extrapolation error.
REPRODUCIBILITY STATEMENT
The code of our work is available at https://github.com/Baichenjia/PBRL. The environments, datasets, and hyper-parameters of our experiments are are given in the appendix. All settings, assumptions, lemmas, and theorems are proved and are discussed in detail in our appendix.

heading: ACKNOWLEDGEMENTS
text: This work was supported in part by the National Natural Science Foundation of China under Grant 51935005, in part by the Fundamental Research Program under Grant JCKY20200603C010. The authors thank the anonymous reviewers, whose invaluable comments and suggestions have helped us to improve the paper.

heading: A THEORETICAL PROOF
text: A.1 BACKGROUND OF LCB-PENALTY IN LINEAR MDPS
In this section, we introduce the provably efficient LCB-penalty in linear MDPs (Abbasi-Yadkori et al., 2011; Jin et al., 2020; 2021). We consider the setting of γ = 1 in the following. In linear MDPs, the feature map of the state-action pair takes the form of φ : S ×A → Rd, and the transition kernel and reward function are assumed to be linear in φ. As a result, for any policy π, the stateaction value function is also linear in φ (Jin et al., 2020), that is,
Qπ(sit, a i t) = ŵ > t φ(s i t, a i t). (11)
The parameter wt can be solved in the closed-form by following the Least-Squares Value Iteration (LSVI) algorithm, which minimizes the following loss function,
ŵt = min w∈Rd m∑ i=1 ( φ(sit, a i t) >w − r(sit, ait)− Vt+1(sit+1) )2 + λ · ‖w‖22, (12)
where Vt+1 is the estimated value function in the (t + 1)-th step, and r(sit, a i t) + Vt+1(s i t+1) is the target of LSVI. The explicit solution to (12) takes the form of
ŵt = Λ −1 t m∑ i=1 φ(sit, a i t) ( Vt+1(s i t+1) + r(s i t, a i t) ) , Λt = m∑ i=1 φ(sit, a i t)φ(s i t, a i t) > + λ · I. (13)
Here Λt accumulate the state-action features from the training buffer. Based on the solution of wt, the action-value function can be estimated by Qt(st, at) ≈ ŵ>t φ(st, at). In addition, in offline RL with linear function assumption, the following LCB-penalty yields an uncertainty quantification,
Γlcb(st, at) = βt · [ φ(st, at) >Λ−1t φ(st, at) ]1/2 , (14)
which measures the confidence interval of the Q-functions with the given training data (AbbasiYadkori et al., 2011; Jin et al., 2020; 2021). In offline RL, the pessimistic value function Q̂t(st, at) penalizes Qt by the uncertainty quantification Γlcb(st, at) as a penalty as follows,
Q̂t(st, at) =Qt(st, at)− Γlcb(st, at) = w>t φ(st, at)− Γlcb(st, at),
(15)
where wt is defined in Eq. (12). Under the linear MDP setting, such pessimistic value iteration is known to be information-theoretically optimal (Jin et al., 2021). In addition, exploration with Γlcb(st, at) as a bonus is also provably efficient in the online RL setting (Abbasi-Yadkori et al., 2011; Jin et al., 2020).
A.2 CONNECTION BETWEEN THE BOOTSTRAPPED UNCERTAINTY AND Γlcb
In the sequel, we consider a Bayesian linear regression perspective of LSVI in Eq. (12). According to the Bellman equation, the objective of LSVI is to approximate the Bellman target bit = r(s i t, a i t)+ Vt+1(s i t+1) with theQ-functionQt, where Vt+1 is the estimated value function in the (t+1)-th step. In linear MDPs, We parameterize the Q-function by Qt(st, at) = ŵ>t φ(st, at). We further define the noise in this least-square problem as follows,
= bit − w>t φ(st, at), (16)
where wt is the underlying true parameter. In the offline dataset with Din = {(sit, ait, sit+1)}i∈[m], we denote by ŵt the Bayesian posterior of w given the dataset Din. In addition, we assume that we are given a Gaussian prior of the parameter w ∼ N (0, I/λ) as a non-informative prior. The following Lemma establishes connections between bootstrapped uncertainty and the LCB-penalty Γlcb. Lemma 1 (Formal Version of Claim 1). We assume that follows the standard Gaussian distribution N (0, 1) given the state-action pair (sit, ait). It then holds for the posterior wt given Din that
Varŵt ( Qt(s i t, a i t) ) = Varŵt ( φ(sit, a i t) >ŵt ) = φ(sit, a i t) >Λ−1t φ(s i t, a i t), ∀(sit, ait) ∈ S ×A. (17)
Proof. The proof follows the standard analysis of Bayesian linear regression. Under the assumption that ∼ N (0, 1), we obtain that
bit | (sit, ait), ŵ ∼ N ( ŵ>t φ(s i t, a i t), 1 ) . (18)
Recall that we have the prior distribution w ∼ N (0, I/λ). Our objective is to compute the posterior density ŵt = w | Din. It holds from Bayes rule that
log p(ŵ | Din) = log p(ŵ) + log p(Din | ŵ) + Const., (19) where p(·) denote the probability density function of the respective distributions. Plugging (18) and the probability density function of Gaussian distribution into (19) yields
log p(ŵ | Din) = −‖ŵ‖2/2− m∑ i=1 ‖ŵ>φ(sit, ait)− yit‖2/2 + Const.
= −(ŵ − µt)>Λ−1t (ŵ − µt)/2 + Const., where we define
µt = Λ −1 t m∑ i=1 φ(sit, a i t)y i t, Λt = m∑ i=1 φ(sit, a i t)φ(s i t, a i t) > + λ · I. (20)
Then we obtain that ŵt = w | Din ∼ N (µt,Λ−1t ). It then holds for all (st, at) ∈ S ×A that Var ( φ(sit, a i t) >ŵt ) = Var ( Qt(s i t, a i t) ) = φ(sit, a i t) >Λ−1t φ(s i t, a i t), (21)
which concludes the proof.
In Lemma 1, we show that the standard deviation of the Q-posterior is equivalent to the LCBpenalty Var ( Q(st, at) ) = φ(st, at)
>Λ−1t φ(st, at) introduced in §A.1. Recall that our proposed bootstrapped uncertainty takes the form of
U(st, at) ≈ Std ( Qk(st, at) ) , (22)
which is the standard deviation of the bootstrapped Q-functions. Such bootstrapping serves as an estimation of the posterior of Q-functions (Osband et al., 2016). Thus, our proposed uncertainty quantification can be seen as an estimation of the LCB-penalty under the linear MDP assumptions.
In addition, under the tabular setting where the states and actions are finite, the LCB-penalty takes a simpler form, which we show in the following lemma. Lemma 2. In tabular MDPs, the bootstrapped uncertainty U(s, a) is approximately proportional to the reciprocal-count of (s, a), that is,
U(s, a) ≈ Γlcb(s, a)/βt = 1√
Ns,a + λ . (23)
Proof. In tabular MDPs, we consider the joint state-action space d = |S| × |A|. Then j-th stateaction pair can be encoded as a one-hot vector as φ(s, a) ∈ Rd, where j ∈ [0, d−1], thus is a special case of the linear MDP (Yang & Wang, 2019; Jin et al., 2020). Specifically, we define
φ(sj , aj) =  0 ... 1 ... 0  ∈ Rd, φ(sj , aj)φ(sj , aj)> =  0 ··· 0 ··· 0 ... . . . ... 0 1 0 ... . . . ... 0 ··· 0 ··· 0  ∈ Rd×d, (24) where the value of φ(sj , aj) is 1 at the j-th entry and 0 elsewhere. Then the matrix Λj =∑m i=0 φ(s i j , a i j)φ(s i j , a i j) > + λ · I is the sum of φ(sj , aj)φ(sj , aj)> over (sj , aj) ∈ Din, which takes the form of
Λj =  n0+λ 0 ··· 0 0 n1+λ ··· 0 ... . . . ... 0 ··· nj+λ 0
... . . . ... 0 ··· ··· nd−1+λ
 , (25)
where the j-th diagonal element of Λj is the corresponding counts for state-action (sj , aj), i.e.,
nj = Nsj ,aj .
It thus holds that [ φ(sj , aj) >Λ−1j φ(sj , aj) ]1/2 = 1√
Nsj ,aj + λ , (26)
which concludes the proof.
A.3 REGULARIZATION WITH OOD SAMPLING
In this section, we discuss how OOD sampling plays the role of regularization in RL, which regularizes the extrapolation behavior of the estimated Q-functions on OOD samples.
Similar to §A.2, we consider the setup of LSVI-UCB (Jin et al., 2020) under linear MDPs. Specifically, we assume that the transition dynamics and reward function takes the form of
Pt(st+1 | st, at) = 〈ψ(st+1), φ(st, at)〉, r(st, at) = θ>φ(st, at), ∀(st+1, at, st) ∈ S ×A×S, (27) where the feature embedding φ : S×A 7→ Rd is known. We further assume that the reward function r : S×A 7→ [0, 1] is bounded and the feature is bounded by ‖φ‖2 ≤ 1. Given the datasetDin, LSVI iteratively minimizes the least-square loss in Eq. (12). Recall that the explicit solution to Eq. (12) takes the form of
ŵt = Λ −1 t m∑ i=1 φ(sit, a i t) ( Vt+1(s i t+1) + r(s i t, a i t) ) , Λt = m∑ i=1 φ(sit, a i t)φ(s i t, a i t) > + λ · I. (28)
We remark that for the regression problem in Eq. (12), the L2-regularizer λ · ‖w‖22 enforces a Gaussian prior under the notion of Bayesian regression. Such regularization ensures that the linear function approximation φ>wit extrapolates well outside the region covered by the dataset Din. However, as shown in §D, we observe that such L2-regularization is ineffective for offline DRL. To this end, we propose OOD sampling in our proposed PBRL. To demonstrate the effectiveness of OOD sampling as a regularizer, we consider the following least-squares loss with OOD sampling and without the L2-regularizer,
w̃it = min w∈Rd m∑ i=1 ( φ(sit, a i t) >w − r(sit, ait)− Vt+1(sit+1) )2 + ∑ (sood,aood,y)∈Dood ( φ(sood, aood)>w − y )2 . (29) The explicit solution of Eq. (29) takes the form of
w̃it = Λ̃ −1 t ( m∑ i=1 φ(sit, a i t) ( r(sit, a i t) + Vt+1(s i t+1) ) + ∑ (sood,aood,y)∈Dood φ(sood, aood)y ) , (30)
where
Λ̃t = m∑ i=1 φ(sit, a i t)φ(s i t, a i t) > + ∑ (sood,aood,y)∈Dood φ(sood, aood)φ(sood, aood)>. (31)
Hence, if we further set y = 0 for all (sood, aood, y) ∈ Dood, then (29) enforces a Gaussian prior with the covariance matrix Λ−1ood, where we define
Λood = ∑
(sood,aood,y)∈Dood
φ(sood, aood)φ(sood, aood)>. (32)
Specifically, if we further enforce Dood = {(sj , aj , 0)}j∈[d] with φ(sj , aj) = λ · ej , where ej ∈ Rd is the unit vector with the j-th entry equals one, it further holds that Λood = λ · I and Eq. (29) is equivalent to Eq. (12). In addition, under the tabular setting, by following the same proof as in Lemma 2, having such OOD samples in the training is equivalent to setting the count in Eq. (26) to be
Ñsj ,aj = Nsj ,aj +N ood sj ,aj ,
where Nsj ,aj is the occurrence of (sj , aj) in the dataset and N ood sj ,aj is the occurrence of (sj , aj) in the OOD dataset.
However, to enforce such a regularizer without affecting the estimation of value functions, we need to set the target y of the OOD samples to zero. In practice, we find such a setup to be overly pessimistic. Since the Q-network is smooth, such a strong regularizer enforces the Q-functions to be zero for state-action pairs from both the offline data and OOD data, as show in Fig. 12 and Fig. 13 of §C. We remark that adopting a nonzero OOD target y does not hinder the effect of regularization as it still imposes the same prior in the covariate matrix Λ̃t. However, adopting nonzero OOD target may introduce additional bias in the value function estimation and the corresponding uncertainty quantification. To maintain a consistent and pessimistic estimation of value functions, one needs to carefully design the nonzero OOD target y.
To this end, we recall the definition of a ξ-uncertainty quantifier in Definition 1 as follows. Definition 2 (ξ-Uncertainty Quantifier (Jin et al., 2021)). The set of penalization {Γt}t∈[T ] forms a ξ-Uncertainty Quantifier if it holds with probability at least 1− ξ that
|T̂ Vt+1(s, a)− T Vt+1(s, a)| ≤ Γt(s, a)
for all (s, a) ∈ S × A, where T is the Bellman operator and T̂ is the empirical Bellman operator that estimates T based on the data.
We remark that here we slightly abuse the notation T of Bellman operator and write T V (s, a) = E[r(s, a)+V (s′) | s, a]. Under the linear MDP setup, the empirical estimation T̂ Vt+1 is obtained via fitting the least-squares loss in Eq. (29). Thus, the empirical estimation T̂ Vt+1 takes the following explicit form, T̂ Vt+1(st, at) = φ(st, at)>w̃t, where w̃t is the solution to the least-squares problem defined in Eq. (30). We remark that such ξuncertainty quantifier plays an important role in the theoretical analysis of RL algorithms, both for online RL and offline RL (Abbasi-Yadkori et al., 2011; Azar et al., 2017; Wang et al., 2020a; Jin et al., 2020; 2021; Xie et al., 2021a;b). Our goal is therefore to design a proper OOD target y such that we can obtain ξ-uncertainty quantifier based on the bootstrapped value functions. Our design is motivated by the following theorem. Theorem 2. Let Λood λ · I. For all the OOD datapoint (sood, aood, y) ∈ Dood, if we set y = T Vt+1(sood, aood), it then holds for βt = O ( T · √ d · log(T/ξ) ) that
Γlcbt (st, at) = βt [ φ(st, at) >Λ−1t φ(st, at) ]1/2
forms a valid ξ-uncertainty quantifier.
Proof. Recall that we define the empirical Bellman operator T̂ as follows,
T̂ Vt+1(st, at) = φ(st, at)>w̃t, It suffices to upper bound the following difference between the empirical Bellman operator and Bellman operator T Vt+1(s, a)− T̂ Vt+1(s, a) = φ(s, a)>(wt − w̃t). Here we define wt as follows
wt = θ + ∫ S Vt+1(st+1)ψ(st+1)dst+1, (33)
where θ and ψ are defined in Eq. (27). It then holds that
T Vt+1(s, a)− T̂ Vt+1(s, a) = φ(s, a)>(wt − w̃t)
= φ(s, a)>wt − φ(s, a)>Λ̃−1t m∑ i=1 φ(sit, a i t) ( r(sit, a i t) + V i t+1(s i t+1) ) − φ(s, a)>Λ̃−1t
∑ (sood,aood,y)∈Dood φ(sood, aood)y. (34)
where we plug the solution of w̃t in Eq. (30). Meanwhile, by the definitions of Λ̃t and wt in Eq. (31) and Eq. (33), respectively, we have
φ(s, a)>wt = φ(s, a) >Λ̃−1t Λ̃twt
= φ(s, a)>Λ̃−1t ( m∑ i=1 φ(sit, a i t)T Vt+1(st, at) + ∑ (sood,aood,y)∈Dood φ(sood, aood)T Vt+1(sood, aood) ) .
(35) Plugging (35) into (34) yields
T Vt+1(s, a)− T̂ Vt+1(s, a) = (i) + (ii), (36)
where we define
(i) = φ(s, a)>Λ̃−1t m∑ i=1 φ(sit, a i t) ( T Vt+1(sit, ait)− r(sit, ait)− V it+1(sit+1) ) ,
(ii) = φ(s, a)>Λ̃−1t ∑
(sood,aood,y)∈Dood
φ(sood, aood) ( T Vt+1(sood, aood)− y ) .
Following the standard analysis based on the concentration of self-normalized process (AbbasiYadkori et al., 2011; Azar et al., 2017; Wang et al., 2020a; Jin et al., 2020; 2021) and the fact that Λood λ · I , it holds that
|(i)| ≤ βt · [ φ(st, at) >Λ−1t φ(st, at) ]1/2 , (37)
with probability at least 1 − ξ, where βt = O ( T · √ d · log(T/ξ) ) . Meanwhile, by setting y = T Vt+1(sood, aood), it holds that (ii) = 0. Thus, we obtain from (36) that
|T Vt+1(s, a)− T̂ Vt+1(s, a)| ≤ βt · [ φ(st, at) >Λ−1t φ(st, at) ]1/2
(38)
for all (s, a) ∈ S ×A with probability at least 1− ξ.
Theorem 2 allows us to further characterize the optimality gap of the pessimistic value iteration. In particular, the following corollary holds. Corollary 1 (Jin et al. (2021)). Under the same conditions as Theorem 2, it holds that
V ∗(s1)− V π1(s1) ≤ T∑ t=1 Eπ∗ [ Γlcbt (st, at) | s1 ] Proof. See e.g., Jin et al. (2021) for a detailed proof.
We remark that the optimality gap in Corollary 1 is information-theoretically optimal under the linear MDP setup with finite horizon (Jin et al., 2021). Intuitively, for an offline dataset with sufficiently good coverage on the optimal trajectories such as the experience from experts, such gap is small. For a dataset collected from random policy, such a gap can be large. Our experiments also support such intuition empirically, where the score obtained by training with the expert dataset is higher than that with the random dataset.
Theorem 2 shows that if we set y = T Vt+1(sood, aood), then our estimation based on disagreement among ensembles is a valid ξ-uncertainty quantifier. However, such OOD target is impossible to obtain in practice as it requires knowing the transition at the OOD datapoint (sood, aood). In practice, if TD error is sufficiently minimized, then Qt+1(s, a) should well estimate the target T Vt+1. Thus, in practice, we utilize
y = Qt+1(s ood, aood)− Γt+1(sood, aood)
as the OOD target, where we introduce an additional penalization Γt+1(sood, aood) to enforce the pessimistic value estimation.
In addition, we remark that in theory, we require that the embeddings of the OOD sample are isotropic, in the sense that the eigenvalues of the corresponding covariate matrix Λood are lower
bounded. Such isotropic property can be guaranteed by randomly generating states and actions. In practice, we find that randomly generating states is more expensive than randomly generating actions. Meanwhile, we observe that randomly generating actions alone are sufficient to guarantee reasonable empirical performance since the generated OOD embeddings are sufficiently isotropic. Thus, in our experiments, we randomly generate OOD actions according to our current policy and sample OOD states from the in-distribution dataset.
B IMPLEMENTATION DETAIL
B.1 ALGORITHMIC DESCRIPTION
Algorithm 1 PBRL algorithm 1: Initialize: K bootstrapped Q-networks and target Q-networks with parameter θ and θ−, policy π with parameter ϕ, and hyper-parameters βin, βood
2: Initialize: total training steps H , current frame h = 0 3: while h < H do 4: Sample mini-batch transitions (s, a, r, s′) from the offline dataset Din 5: # Critic Training for offline data. 6: Calculate the bootstrapped uncertainty Uθ−(s′, a′) through the target-networks. 7: Calculate the Q-target in Eq. (4) and the resulting TD-loss |Qkθ(s, a)− T̂ inQk(s, a)|2. 8: # Critic Training for OOD data 9: Perform OOD sampling and obtains Nood OOD actions aood for each s.
10: Calculate the bootstrapped uncertainty Uθ(s, aood) for OOD actions through Q-networks. 11: Calculate theQ-target in Eq. (5) and the pseudo TD-loss |Qkθ(s, aood)−T̂ oodQk(s, aood)|2. 12: Minimize |Qkθ(s, a)−T̂ inQk(s, a)|2+|Qkθ(s, aood)−T̂ oodQk(s, aood)|2 to train θ by SGD. 13: # Actor Training 14: Improve πϕ by maximizing minkQk(s, aπ)− log πϕ(aπ|s) with entropy regularization. 15: Update the target Q-network via θ− ← (1− τ)θ− + τθ. 16: end while
B.2 HYPER-PARAMETERS
Most hyper-parameters of PBRL follow the SAC implementations in https://github.com/ rail-berkeley/rlkit. We use the hyper-parameter settings in Table 2 for all the Gym domain tasks. We use different settings of βin and βood for the experiment for Adroit domain and fix the other hyper-parameters the same as Table 2. See §E for the setup of Adroit. In addition, we use the same settings for discount factor, target network smoothing factor, learning rate, and optimizers as CQL (Kumar et al., 2020).
Baselines. We conduct experiments on D4RL with the latest ‘v2’ datasets. The dataset is released at http://rail.eecs.berkeley.edu/datasets/offline_rl/gym_mujoco_v2_ old/. We now introduce the implementations of baselines. (i) The implementation of CQL (Kumar et al., 2020) is adopted from the official implementation at https://github.com/ aviralkumar2907/CQL. In our experiment, we remove the BC warm-up stage since we find CQL performs better without warm-up for ‘v2’ dataset. (ii) For BEAR (Kumar et al., 2019), UWAC (Wu et al., 2021) and MOPO (Yu et al., 2020), we adopt their official implementations at https://github.com/aviralkumar2907/BEAR, https://github.com/ apple/ml-uwac, and https://github.com/tianheyu927/mopo, respectively. We adopt their default hyper-parameters in training. (iii) Since the original paper of TD3-BC (Fujimoto & Gu, 2021) reports the performance of Gym in ‘v2’ dataset in the appendix section, we directly cite the reported scores in Table 1. The learning curve reported in Fig. 2 is trained by implementation released at https://github.com/sfujim/TD3_BC.
Computational cost comparison. In the sequel, we compare the computational cost of PBRL against CQL. We conduct such a comparison based on the Halfcheetah-medium-v2 task. We measure the number of parameters, GPU memory, and runtime per epoch (1K gradient steps) for both PBRL and CQL in the training. We run experiments on a single A100 GPU. We summarize the result in Table 3. We observe that, similar to the other ensemble-based methods such as Bootstrapped DQN (Osband et al., 2016), IDS (Nikolov et al., 2019), and Sunrize (Lee et al., 2021a), our method requires extra computation to handle the ensemble of Q-networks. In addition, we remark that a large proportion of computation for CQL is due to the costs of logsumexp over multiple sampled actions (Fujimoto & Gu, 2021), which we do not require.
B.3 REMARKS ON FORMULATIONS OF PESSIMISM IN ACTOR AND CRITIC
We use different formulations to enforce pessimism in actor and critic. In the critic training, we use the penalized Q-function as in Eq. (4) and Eq. (5). While in the actor training, we use the minimum of ensemble Q-function as in Eq. (7). According to the analysis in EDAC [6], using the minimum of ensemble Q-function minj=1,...,K Qj as the target is approximately equivalent to using Q̄ − β0 · Std(Qj) with a fixed β0 as the target. In contrast, in the critic training of PBRL, we tune different factors (i.e., βin and βood) for the in-distribution target and the OOD target, which yields better performance for the critic estimation.
In the actor training, since we already have pessimistic Q-functions learned by the critic, it is not necessary to enforce large penalties in the actor. To see such a fact, we refer to the ablation study in Fig. 9, where utilizing the mean as the target achieves reasonable performances. We remark that taking the minimum as the target avoids possible large values at certain state-action pairs, which may arise due to the numerical computation in fitting neural networks. As suggested by our ablation study, taking the minimum among the ensemble of Q-functions as the target achieves the best performance. Thus, we use the minimum among the ensemble of Q-functions as the target in PBRL.

heading: C ABLATION STUDY
text: In this section, we present the ablation study of PBRL. In the training, we perform online interactions to evaluate the performance for every 1K gradient steps. Since we run each method for 1M gradient steps totally, each method is evaluated 1000 times in training. The experiments follow such evaluation criteria, and each curve is drawn by 1000 evaluated scores through online interaction.
Number of bootstrapped-Q. We conduct experiments with different numbers of bootstrapped Q-networks in PBRL, and present the performance comparison in Fig. 4. We observe that the performance of PBRL is improved with the increase of the bootstrapped networks. We remark that since the training of offline RL is more challenging than online RL, it is better to use sufficient bootstrapped Q-functions to obtain a reasonable estimation of the non-parametric Q-posterior. We observe from Fig. 4 that using K = 6, 8, and 10 yields similar final scores, and a larger K leads to more stable performance in the training process. We adopt K = 10 for our implementation.
Uncertainty of in-distribution target. We compare different kinds of uncertainty penalization in T̂ in for in-distribution data. (i) Penalizing the immediate reward only. (ii) Penalizing the next-Q value only, which is adopted in PBRL. (iii) Penalizing both the immediate reward and next-Q value. We present the comparison in Fig. 5. We observe that the target-Q penalization performs the best, and adopt such penalization in the proposed PBRL algorithm.
Tuning parameter βin. We conduct experiments with βin ∈ {0.1, 0.01, 0.001, 0.0001} to study the sensitivity of PBRL to the tuning parameter βin for the in-distribution target. We present the
comparison in Fig. 6. We observe that in the ‘medium’ dataset generated by a single policy, the performance of PBRL is insensitive to βin. One possible reason is that since the ‘medium’ dataset is generated by a single policy, the offline dataset tends to concentrate around a few trajectories and has low uncertainty. Thus, the magnitude of βin has a limited effect on the penalty. Nevertheless, in the ‘medium-replay’ dataset, since the data is generated by various policies, the uncertainty of offline data is larger than that of the ‘medium’ dataset (as shown in Fig. 3). Correspondingly, the performance of PBRL is affected by the magnitude of βin. Our experiment shows that PBRL performs the best for βin ∈ [0.0001, 0.01]. We adopt βin = 0.01 for our implementation.
Tuning parameter βood. We use a large βood initially to enforce strong OOD regularization in the beginning of training, and then decrease βood linearly while the training evolves. We conduct experiments with constant settings of βood ∈ {0.01, 0.1, 1.0}. We observe that in the ‘medium’ dataset, a large βood = 1.0 performs the best since the samples are generated by a fixed policy with a relatively concentrated in-distribution dataset. Thus, the OOD samples tend to have high uncertainty and are less trustworthy. In contrast, in the ‘medium-replay’ dataset, a small βood ∈ {0.1, 0.01} performs reasonably well since the mixed dataset has larger coverage of the state-action space and the uncertainty of OOD data is smaller than that of the ‘medium’ dataset. Thus, adopting a smaller βood for the ‘medium-replay’ dataset allows the agent to exploit the OOD actions and gain better performance. To match all possible situations, we propose the decaying strategy. Empirically, we find such a decaying strategy performs well in both the ‘medium’ and ‘medium-replay’ datasets.
We also record the Q-value for (s, a) ∼ Din in the training process. As shown in Fig. 8, since both the in-distribution actions and OOD actions are represented by the same Q-network, a large con-
stant βood makes the Q-value for in-distribution action overly pessimistic and leads to sub-optimal performance. It is desirable to use the decaying strategy for βood in practice.
Actor training. We evaluate different actor training schemes in Eq. (7), i.e., the actor follows the gradients of ‘min’ (in PBRL), ‘mean’ or ‘max’ value among K Q-functions. The result in Fig. 9 shows training the actor by maximizing the ‘min’ among ensemble-Q performs the best. In the ‘medium-replay’ dataset, since the uncertainty estimation is difficult in mixed data, taking ‘mean’ in the actor can be unstable in training. Taking ‘max’ in the actor performs worse in both tasks due to overestimation of Q-functions.
Number of OOD samples. The pessimism in critic training is implemented by sampling OOD actions and then performing uncertainty penalization, as shown in Eq. (6). In each training step, we perform OOD sampling and sample Nood actions from the learned policy. We perform an ablation study with Nood ∈ {0, 2, 5, 10}. According to Fig 10, the performance is poor without OOD sampling (i.e., Nood = 0). We find the performance becomes better with a small number of OOD actions (i.e., Nood = 2). Also, PBRL is robust to different settings of Nood.
OOD Target. In §A.3, we show that setting the learning target of OOD samples to zero enforces a Gaussian prior to Q-function under the linear MDP setting. However, in DRL, we find such a setup leads to overly pessimistic value function and performs poorly in practice, as shown in Fig. 11. Specifically, we observe that such a strong regularizer enforces the Q-functions to be close to zero for both in-distribution and OOD state-action pairs, as shown in Fig. 12 and Fig. 13. In contrast,
our proposed PBRL target performs well and does not yield large extrapolation errors, as shown in Fig. 12 and Fig. 13.

heading: D REGULARIZATION FOR PBRL
text: In this section, we compare different regularization methods that are popular in other Deep Learning (DL) literature to solve the extrapolation error in offline RL. Specifically, we compare the following regularization methods.
• None. We remove the OOD-sampling regularizer in PBRL and train bootstrapped Q-functions solely based on the offline dataset through T̂ in.
• L2-regularizer. We remove the OOD-sampling regularizer and use L2 normalization instead. As we discussed in §3.3, in linear MDPs, LSVI utilizes L2 regularization to control the extrapolation behavior of Q-functions in OOD samples. In DRL, we add the L2-norm of weights in the Q-network in loss functions to conduct L2-regularization. We attempt two scale factors {1e− 2, 1e− 4} in our experiments.
• Spectral Normalization (SN). We remove the OOD-sampling regularizer and use SN instead. SN constrains the Lipschitz constant of layers, which measures the smoothness of the neural network. Recent research (Gogianu et al., 2021) shows that SN helps RL training when applied to specific layers of the Q-network. In our experiment, we follow Gogianu et al. (2021) and consider two cases, namely, applying SN in the output layer (denoted as SN[-1]) and applying SN in both the output layer and the one before it (denoted as SN[-1,-2]), respectively.
• Pessimistic Initialization (PI). Optimistic initialization is simple and efficient for RL exploration, which initializes the Q-function for all actions with a high value. In online RL, such initialization encourages the agent to explore all actions in the interaction. Motivated by this method, we attempt a pessimistic initialization to regulate the OOD behavior of theQ-network. In our implementation, we draw the initial value of weights and a bias of the Q-networks from the uniform distribution Unif(a,b). We try two settings in our experiment, namely, (i) PI-small that sets (a, b) to (−0.2, 0), and (ii) PI-large that sets (a, b) to (−1.0, 0). In both settings, we remove the OOD sampling and use PI instead.
We illustrate (i) the normalized performance in the training process, (ii) theQ-value along the trajectory of training policy and (iii) the uncertainty quantification along the trajectory of training policy. We present the results in Fig. 14, Fig. 15, and Fig. 16, respectively. In the sequel, we discuss the empirical results.
• We observe that OOD sampling is the only regularization method with reasonable performance. Though L2-regularization and SN yields reasonable performance in supervised learning, they do not perform well in offline RL.
• In the ‘medium-replay’ dataset, we observe that PI and SN can gain some score in the early stage of training. Nevertheless, the performance drops quickly along with the training process. We conjecture that both PI and SN have the potential to be effective with additional parameter tuning and algorithm design.
In conclusion, previous regularization methods for DL and RL is not sufficient to handle the distribution shift issue in offline RL. Combining such regularization techniques with the policy constraints and conservatism methods may lead to improved empirical performance, which we leave for future research.

heading: E EXPERIMENTS IN ADROIT DOMAIN
text: In Adroit, the agent controls a 24-DoF robotic hand to hammer a nail, open a door, twirl a pen, and move a ball, as shown in Fig. 17. The Adroit domain includes three dataset types, namely, demonstration data from a human (‘human’), expert data from an RL policy (‘expert’), and fifty-fifty mixed data from human demonstrations and an imitation policy (‘cloned’). The adroit tasks are more challenging than the Gym domain in task complexity. In addition, the use of human demonstration in the dataset also makes the task more challenging. We present the normalized scores in Table 4. We set βin = 0.0001 and βood = 0.01. The other hyper-parameters in Adroit follows Table 2.
In Table 4, the scores of BC, BEAR, and CQL are adopted from the D4RL benchmark (Fu et al., 2020). We do not include the scores of MOPO (Yu et al., 2020) as it is not reported and we cannot find suitable hyper-parameters to make it work in the Adroit domain. We also attempt TD3-BC (Fujimoto et al., 2018) with different BC weights and fail in getting reasonable score for most of the tasks. In addition, since UWAC (Wu et al., 2021) has a different evaluation process, we re-train UWAC with the official implementation and report the scores in Table 4.
In Table 4, we add the average score without ‘expert’ dataset since the scores of ‘expert’ dataset dominate that of the rest of the datasets. We find CQL (Kumar et al., 2020) and BC have the best average performance among all baselines. Meanwhile, we observe that PBRL slightly outperforms CQL and BC. We remark that the human demonstrations stored in ‘human’ and ‘cloned’ are inherently different from machine-generated ‘expert’ data since (i) the human trajectories do not follow the Markov property, (ii) human decision may be affected by unobserved states such as prior knowledge, distractors, and the action history, and (iii) different people demonstrate differently as their solution policies. Such characteristic makes the ‘human’ and ‘cloned’ dataset challenging for offline RL algorithms. In addition, we remark that the recent study in robot learning from human demonstration also encounter such challenges (Mandlekar et al., 2021).

heading: F RELIABLE EVALUATION FOR STATISTICAL UNCERTAINTY
text: Recent research (Agarwal et al., 2021) proposes reliable evaluation principles to address the statistical uncertainty in RL. Since the ordinary aggregate measures like mean can be easily dominated by a few outlier scores, Agarwal et al. (2021) presents several efficient and robust alternatives that are not unduly affected by outliers and have small uncertainty even with a handful of runs. In this paper, we adopt these evaluation methods for each method in Gym domain with Mtask ∗Nseed runs.
• Stratified Bootstrap Confidence Intervals. The Confidence Intervals (CIs) for a finite-sample score estimates the plausible values for the true score. Bootstrap CIs with stratified sampling can be applied to small sample sizes and is better justified than sample standard deviations.
• Performance Profiles. Performance profiles reveal performance variability through score distributions. A score distribution shows the fraction of runs above a certain score and is given by F̂ (τ) = F̂ (τ ;x1:M,1:N ) = 1 M ∑M m=1 1 N ∑N n=1 1[xm,n ≥ τ ].
• Aggregate Metrics. Based on bootstrap CIs, we can extract aggregate metrics from score distributions, including median, mean, interquartile mean (IQM), and optimality gap. IQM discards the bottom and top 25% of the runs and calculates the mean score of the remaining 50% runs. Optimality gap calculates the amount of runs that fail to meet a minimum score of η = 50.0.
The result comparisons are give in Fig. 18 and Fig. 19. Specifically, Fig. 18 shows aggregate metrics based on 95% bootstrap CIs, and Fig. 19 shows performance profiles based on score distribution. For both evaluations, our PBRL and PBRL-prior outperforms other methods with small variability.
40 60 80 BEAR
UWAC MOPO
CQL TD3-BC
PBRL PBRL-prior
Median
40 60 80
IQM
45 60 75
Mean
10 15 20
Optimality Gap
Normalized Score
Figure 18: Aggregate metrics on D4RL with 95% CIs based on 15 tasks and 5 seeds for each task. Higher mean, median and IQM scores, and lower optimality gap are better. The CIs are estimated using the percentile bootstrap with stratified sampling. Our methods perform better than baselines.
0 20 40 60 80 100 120 Normalized Score (τ)
0.00
0.25
0.50
0.75
1.00
Fr ac
tio n
of ru
ns w
ith s
co re
> τ
0 20 40 60 80 100 120 Normalized Score (τ)
0.00
0.25
0.50
0.75
1.00
Fr ac
tio n
of ta
sk s
w ith
s co
re >
τ
BEAR UWAC MOPO CQL TD3-BC PBRL PBRL-prior
Figure 19: Performance profiles on D4RL based on score distributions (left), and average score distributions (right). Shaded regions show pointwise 95% confidence bands based on percentile bootstrap with stratified sampling. The τ value where the profiles intersect y = 0.5 shows the median, and the area under the performance profile corresponds to the mean.

Review summaries:
This paper proposed an uncertainty-aware offline reinforcement learning algorithm based on a Q-network ensemble. The proposed method penalizes Q-values on OOD actions and performs pessimistic offline Q-learning. The paper interprets the method with LCB framework. The proposed method outperforms existing offline RL algorithms on D4RL Gym and Adroit tasks. 

This paper presents a model-free pessimistic bootstrapping approach for offline RL. Specifically, the paper considers an actor-critic approach with an ensemble of Q-functions and utilizing disagreements in their predictions (measured as standard deviation) for learning the Q-functions. The paper also presents a way to regularize the learning with out of distribution state-action pairs which according to the paper is a crucial part in obtaining improved results.   --- Update post author response: I have increased my score.

This paper presents Pessimistic Bootstrapping for offline RL (PBRL), a model-free offline RL algorithm that purely relies on an uncertainty-driven method. Bootstrapped Q-functions are trained, and the standard deviation of their estimates is used for the uncertainty quantification. This uncertainty quantification is then used for pessimistic bootstrapping. Also, in contrast to the existing methods that only considers in-distribution target, PBRL optimizes Q-function even for out-of-distribution actions with the pseudo-target that is penalized by the uncertainty quantifier. A theoretical analysis is provided that PBRL is provably efficient in the linear MDP setting. Experimental results demonstrate that PBRL outperforms the state-of-the-art methods. 

The paper looks at the offline RL problem and claims that existing techniques penalize out-of-distribution actions too aggressively and so perform poorly at generalization and extrapolation. To remedy this, the paper proposes an offline RL algorithm in which an ensemble of critics is trained with an objective composed of (1) a TD error based on actions seen in the dataset with target value penalized by standard deviation over the ensemble of the next Q-values, and (2) a squared error on the Q-values of OOD actions regressing to those same Q-values penalized by the standard deviation over the ensemble. The proposed algorithm is paired with a theoretical analysis connecting it to recent theoretical offline RL papers. The algorithm is evaluated on the D4RL benchmarks and shows favorable performance compared to baselines.