# Dealing with the Unknown:
Pessimistic Offline Reinforcement Learning

Jinning Li, Chen Tang, Masayoshi Tomizuka, Wei Zhan
Department of Mechanical Engineering
University of California, Berkeley
United States
<EMAIL_ADDRESS>

###### Abstract

Reinforcement Learning (RL) has been shown effective in domains where the
agent can learn policies by actively interacting with its operating
environment. However, if we change the RL scheme to offline setting where the
agent can only update its policy via static datasets, one of the major issues
in offline reinforcement learning emerges, i.e. distributional shift. We
propose a Pessimistic Offline Reinforcement Learning (PessORL) algorithm to
actively lead the agent back to the area where it is familiar by manipulating
the value function. We focus on problems caused by out-of-distribution (OOD)
states, and deliberately penalize high values at states that are absent in the
training dataset, so that the learned pessimistic value function lower bounds
the true value anywhere within the state space. We evaluate the PessORL
algorithm on various benchmark tasks, where we show that our method gains
better performance by explicitly handling OOD states, when compared to those
methods merely considering OOD actions.

> Keywords: Offline Reinforcement Learning, Out-of-Distribution States

##  1 Introduction

Reinforcement learning (RL), especially with high-capacity models such as deep
nets, has shown its power in many domains, e.g., gaming, healthcare, and
robotics. However, typical training schemes of RL algorithms rely on active
interaction with the environments. It limits their applications in domains
where active data collection is expensive or dangerous (e.g., autonomous
driving). Recently, offline reinforcement learning (offline RL) has emerged as
a promising candidate to overcome this barrier. Different from traditional RL
methods, offline-RL learns the policy from a static offline dataset collected
without iterative interaction with the environment. Recent works have shown
its ability in solving various policy learning tasks [1, 2, 3]. However,
offline RL methods suffer from several major problems. One of them is
distributional shift. Unlike online RL algorithms, the state and action
distributions are different during training and testing. As a result, RL
agents may fail dramatically after deployed online. For example, in safety-
critical applications such as autonomous driving, overconfident and
catastrophic extrapolations may occur in out-of-distribution (OOD) scenes [4].

Many prior works [5, 6, 7, 8, 9, 10] try to mitigate this problem by handling
OOD actions. They discourage the policies to visit OOD actions by designing
conservative value functions, or estimating the uncertainty of Q-functions.
Although constraining the policy can implicitly mitigate the problem of state
distributional shift, few works have adopted measures to explicitly handle OOD
states during the training stage. In this work, we propose the Pessimistic
Offline Reinforcement Learning (PessORL) framework to explicitly limit the
policy from visiting both unseen states and actions. We refer to the states or
the actions that are not included in the training data as the unseen states or
the unseen actions.

Our PessORL framework is inspired by the concept of pessimistic MDP in [11],
where the reward is significantly small for unseen state-action pairs. We aim
to limit the magnitude of the value function at unseen states, so that the
agent can avoid or recover from unseen states. It is then crucial to precisely
detect OOD states and shape the value function at those states. Since prior
methods on OOD actions are derived from a similar concept, we can adapt their
approaches to handle OOD states. There are mainly two approaches in the
literature. One is to estimate the epistemic uncertainty of Q-function and
subtract it from the original Q-function to get a conservative Q-function [6,
7, 8, 9, 10]. The other is to regularize the Q-function during the learning
process [5]. The first method is highly sensitive to the trade-off between the
uncertainty estimation and the original Q-function [12, 13] and the quality of
uncertainty estimation [14].

Therefore, we follow the second approach, and add a conservative
regularization term to the policy evaluation step of PessORL to shape the
value function. We prove that PessORL learns a pessimistic value function that
lower bounds the true value function, and forces the policy to avoid or
recover from out-of-distribution states and actions. We evaluate the PessORL
algorithm on various benchmark tasks. The performance of our method matches
the state-of-the-art offline RL methods. In particular, we show that, by
explicitly handling OOD states, we can further improve the policy performance
compared to those methods merely considering OOD actions.

##  2 Related Works

A big challenge for offline reinforcement learning methods is to deal with the
problems caused by unvisited states or actions in training data, which is also
known as distributional shift. In model-free offline reinforcement learning,
some works used importance sampling to fill the gap between the learned policy
and the behavior policy in the training dataset [15, 16, 17, 18, 19]. There
are also many works constrained the learned policy to be similar to the
behavior policy by explicit constraints in the training dataset [6, 20, 21,
22, 23], so that the agent can avoid out-of-distribution actions during test
time. The work in [13] proposed a latent space to constrain the policy to
avoid deviating from the training data support. One further step to make the
agent avoid actions that may cause itself deviate from the training data
support is to get a conservative value function and thus a conservative
policy. The works in [7, 8, 6, 9, 10] estimate the uncertainty of the learned
Q-function, and then directly subtract it from the Q-function to get a
conservative Q-function. Another way to get a conservative Q-function is to
regularize the Q-function in the optimization problem during the learning
process [5]. In model-based reinforcement learning (MBRL), there are also many
algorithms that constrain the exploitation in the environment with effective
uncertainty estimation methods [24, 25, 26, 27, 28, 11]. It is considered to
be mature and reliable to detect OOD actions and states by methods from MBRL.
Most of the aforementioned methods focus on OOD actions but not have explicit
mechanism to deal with OOD states. In this paper, we focus on OOD states and
propose a method to learn a pessimistic value function by adding
regularization terms when updating Q-functions, and follow the works in the
MBRL domain to establish the module to detect OOD states in our algorithm.

##  3 Background

###  3.1 Offline Reinforcement Learning

Given a Markov decision process (MDP), an RL agent aims to maximize the
expectation of cumulative rewards. The MDP is represented by a tuple
$\mathcal{M}=(\mathcal{S},\mathcal{A},\mathcal{P},r,\gamma)$, where
$\mathcal{S}$ is the state space, $\mathcal{A}$ is the action space,
$\mathcal{P}:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow[0,1]$ is
the transition function, $r:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$
is the reward function, and $\gamma$ is the discount factor. Typical RL
algorithms optimize the policy using experience collected when interacting
with the environment. Unlike those online learning paradigms, offline-RL
algorithms rely solely on a static offline dataset, denoted by
$\mathcal{D}=\left\\{\left(\mathbf{s}_{t}^{i},\mathbf{a}_{t}^{i},\mathbf{s}_{t+1}^{i},r^{i}_{t}\right)\right\\}$.

In this work, we focus on dynamic-programming-based RL algorithms under the
offline setting, where we extract a policy from a learned value function for
the underlying MDP in the training data. Standard Q-learning method estimates
an approximate Q-function parametrized by $\theta$, i.e.
$\hat{Q}_{\theta}(\mathbf{s}_{t},\mathbf{a}_{t})$. In each iteration, the
Q-function is updated as follows:

$\displaystyle\hat{Q}^{k+1}_{\theta}\leftarrow\arg\min_{Q}\dfrac{1}{2}\mathbb{E}_{\mathbf{s},\mathbf{a},\mathbf{s}^{\prime}\sim\mathcal{D}}\left[\left(Q(\mathbf{s},\mathbf{a})-\hat{\mathcal{B}}^{\pi}\hat{Q}^{k}_{\theta}(\mathbf{s},\mathbf{a})\right)^{2}\right]\text{
(policy evaluation)},$ (1)

where $\hat{\mathcal{B}}^{\pi}$ is the empirical Bellman update operator
defined as:

$\hat{\mathcal{B}}^{\pi}\hat{Q}^{k}_{\theta}(\mathbf{s},\mathbf{a})=r(\mathbf{s},\mathbf{a})+\gamma\mathbb{E}_{\mathbf{a}^{\prime}\sim\hat{\pi}^{k}(\mathbf{a}^{\prime}|\mathbf{s}^{\prime})}\left[\hat{Q}^{k}_{\theta}(\mathbf{s}^{\prime},\mathbf{a}^{\prime})\right].$
(2)

For discrete action space, we define $\hat{\pi}^{k}$ as the optimal policy
induced by the learned Q-function, i.e.
$\hat{\pi}^{k}(\mathbf{a}|\mathbf{s})=\delta\left[\mathbf{a}=\arg\max_{\mathbf{a}}\hat{Q}^{k}_{\theta}(\mathbf{s},\mathbf{a})\right]$.
In this case, $\hat{\mathcal{B}}^{\pi}$ collides into the Bellman optimality
operator. When the action space is continuous, we follow actor-critic
algorithms to approximate the optimal policy by executing a policy improvement
step after policy evaluation in each iteration:

$\displaystyle\hat{\pi}^{k+1}\leftarrow\arg\max_{\pi}\mathbb{E}_{\mathbf{s}\sim\mathcal{D},\mathbf{a}\sim\pi(\mathbf{a}|\mathbf{s})}\left[\hat{Q}^{k+1}_{\theta}(\mathbf{s},\mathbf{a})\right]\text{
(policy improvement)}.$ (3)

In the rest of the paper, we denote
$\mathcal{E}(Q,\hat{\mathcal{B}}^{\pi}\hat{Q}_{\theta}^{k})=\dfrac{1}{2}\mathbb{E}_{\mathbf{s},\mathbf{a},\mathbf{s}^{\prime}\sim\mathcal{D}}\left[\left(Q(\mathbf{s},\mathbf{a})-\hat{\mathcal{B}}^{\pi}\hat{Q}^{k}_{\theta}(\mathbf{s},\mathbf{a})\right)^{2}\right]$
as the Bellman update error for simplicity.

###  3.2 Uncertainty-Based Methods and Pessimistic Value Functions

By observing Eqn. 1, it is obvious that the Q-function $\hat{Q}_{\theta}$ is
never evaluated or updated at states or actions that never appear in the
dataset. The agent may behave unexpectedly or unpredictably at those unseen
states or actions during test time. For dynamic-programming-based approaches,
one way to address the issue of unseen actions is to estimate the epistemic
uncertainty of Q-function and subtract it from the original Q-function [6, 7,
8, 9, 10]. The uncertainty is estimated based on an ensemble of learned
Q-functions, and the final conservative Q-function becomes
$Q_{\text{c}}(\mathbf{s},\mathbf{a})=\mathbb{E}_{Q\sim\mathcal{P}_{\mathcal{D}}(Q)}[Q(\mathbf{s},\mathbf{a})-\alpha\text{Unc}(\mathcal{P}_{\mathcal{D}}(Q))]$,
where Unc is defined to be some uncertainty estimation metric, and
$\mathcal{P}_{\mathcal{D}}(Q)$ is the distribution over possible Q-functions.
Because the uncertainty metric is directly subtracted, uncertainty-based
methods is highly sensitive to the quality of uncertainty estimation.
Meanwhile, it is difficult to find an ideal $\alpha$ to balance the original
Q-function and Unc.

Another way is to regularize the Q-function at the step of policy evaluation.
A representative example is Conservative Q-Learning (CQL) [5]. Assuming that
the dataset $\mathcal{D}$ is collected with a behavior policy
$\pi_{\beta}(\mathbf{a}|\mathbf{s})$, and
$\hat{\pi}^{k}(\mathbf{a}|\mathbf{s})$ is the learned policy at iteration $k$,
the policy evaluation step in CQL becomes:

$\hat{Q}^{k+1}\leftarrow\arg\min_{Q}\alpha\left(\mathbb{E}_{\mathbf{s}\sim\mathcal{D},\mathbf{a}\sim\hat{\pi}^{k}(\mathbf{a}|\mathbf{s})}[Q(\mathbf{s},\mathbf{a})]-\mathbb{E}_{\mathbf{s}\sim\mathcal{D},\mathbf{a}\sim\pi_{\beta}(\mathbf{a}|\mathbf{s})}[Q(\mathbf{s},\mathbf{a})]\right)+\mathcal{E}(Q,\hat{\mathcal{B}}^{\pi}\hat{Q}_{\theta}^{k}).$
(4)

In the rest of the paper, we denote $\mathcal{C}(Q)$ as the cost term adopted
from the CQL, i.e.,
$\mathcal{C}(Q)=\alpha\left(\mathbb{E}_{\mathbf{s}\sim\mathcal{D},\mathbf{a}\sim\hat{\pi}^{k}(\mathbf{a}|\mathbf{s})}[Q(\mathbf{s},\mathbf{a})]-\mathbb{E}_{\mathbf{s}\sim\mathcal{D},\mathbf{a}\sim\pi_{\beta}(\mathbf{a}|\mathbf{s})}[Q(\mathbf{s},\mathbf{a})]\right).$
It is worth noting that the aforementioned methods all focus on OOD actions,
but they do not have an explicit mechanism to deal with OOD states, which
motivates us to develop the PessORL framework in this work.

##  4 Pessimistic Offline Reinforcement Learning Framework

In this section, we introduce the PessORL framework to mitigate the issue of
state distributional shift. In particular, we propose a novel conservative
regularization term in the policy evaluation step. It can then be integrated
into Q-learning or actor-critic algorithm, which will be described in Sec. 5.

###  4.1 How To Deal With OOD States

Assuming the dataset $\mathcal{D}$ is collected with a behavior policy
$\pi_{\beta}(\mathbf{a}|\mathbf{s})$, and the states $\mathbf{s}$ are
distributed according to a distribution $d^{\pi_{\beta}}(\mathbf{s})$ in the
dataset, we propose to solve the problem caused by state distributional shift
by augmenting the policy evaluation step in CQL [5] with a regularization term
scaled by a trade-off factor $\varepsilon$:

$\min_{Q}\varepsilon\left(\mathbb{E}_{\mathbf{s}\sim
d^{\phi}(\mathbf{s}),\mathbf{a}\sim\hat{\pi}^{k}(\mathbf{a}|\mathbf{s})}\left[Q(\mathbf{s},\mathbf{a})\right]-\mathbb{E}_{\mathbf{s}\sim
d^{\pi_{\beta}}(\mathbf{s}),\mathbf{a}\sim\hat{\pi}^{k}(\mathbf{a}|\mathbf{s})}[Q(\mathbf{s},\mathbf{a})]\right)+\mathcal{E}(Q,\hat{\mathcal{B}}^{\pi}\hat{Q}_{\theta}^{k})+\mathcal{C}(Q),$
(5)

where $d^{\phi}(\mathbf{s})$ is a particular state distribution of our choice.

The idea is to use the minimization term
$\varepsilon\left(\mathbb{E}_{\mathbf{s}\sim
d^{\phi}(\mathbf{s}),\mathbf{a}\sim\hat{\pi}^{k}(\mathbf{a}|\mathbf{s})}\left[Q(\mathbf{s},\mathbf{a})\right]\right)$
to penalize high values at unseen states in the dataset, and the maximization
term $\varepsilon\left(\mathbb{E}_{\mathbf{s}\sim
d^{\pi_{\beta}}(\mathbf{s}),\mathbf{a}\sim\hat{\pi}^{k}(\mathbf{a}|\mathbf{s})}[Q(\mathbf{s},\mathbf{a})]\right)$
to cancel the penalization at in-distribution states. The regularized
Q-function could then push the agent towards regions close to the states from
the dataset, where the values are higher. To achieve it, we need to find a
distribution $d^{\phi}(\mathbf{s})$ that assigns high probabilities to states
far away from the dataset, and low probabilities to states near the training
dataset. We will instantiate a practical design of $d^{\phi}(\mathbf{s})$ in
Sec. 5. For now, we just assume $d^{\phi}(\mathbf{s})$ assigns high
probabilities to OOD states.

###  4.2 Theoretical Analysis

In this section, we analyze the theoretical properties of the proposed policy
evaluation step. The proof and more details can be found in Appendix A.

We define $k\in\mathbb{N}$ as the iteration of policy evaluation, i.e.
$\hat{Q}^{k}$ denotes the optimized Q-function in the $k-$th iteration
obtained by PessORL. $Q^{\pi}$ is defined to be the true Q-function under a
policy $\pi(\mathbf{a}|\mathbf{s})$ in the underlying MDP without any
regularization. The true Q-function can be written in a recursive form via the
exact Bellman operator, $\mathcal{B}^{\pi}$, as
$Q^{\pi}=\mathcal{B}^{\pi}Q^{\pi}$. We define $\hat{V}^{k}$ as the value
function under a policy $\pi(\mathbf{a}|\mathbf{s})$,
$\hat{V}^{k}(\mathbf{s})=\mathbb{E}_{\mathbf{a}\sim\pi(\mathbf{a}|\mathbf{s})}[\hat{Q}^{k}(\mathbf{s},\mathbf{a})]$.
For the true value function $V^{\pi}$ in the underlying MDP, we also have
$V^{\pi}=\mathcal{B}^{\pi}V^{\pi}$.

We first introduce the theorem that the learned value function is a lower
bound of the true one without considering the sampling error defined in the
Lemma A.1.

###### Theorem 4.1

Assume we can obtain the exact reward function $r(\mathbf{s},\mathbf{a})$ and
the transition function $T(\mathbf{s}^{\prime}|\mathbf{s},\mathbf{a})$ of the
underlying MDP. Let
$\hat{V}^{\pi}(\mathbf{s})=\lim_{k\rightarrow\infty}\hat{V}^{k}(\mathbf{s})$.
Then $\forall\mathbf{s}\in\mathcal{S}$, the learned value function via Eqn. 5
is a lower bound of the true one, i.e., $\hat{V}^{\pi}(\mathbf{s})\leq
V^{\pi}(\mathbf{s})$, if the ratio $\dfrac{\varepsilon}{\alpha}$ satisfies

$\displaystyle\dfrac{\varepsilon}{\alpha}\leq\min_{\mathbf{s}}\left(\sum_{\mathbf{a}}\pi(\mathbf{a}|\mathbf{s})\left[\dfrac{\pi(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}-1\right]\right)\left(\dfrac{\left|d^{\phi}(\mathbf{s})-d^{\pi_{\beta}}(\mathbf{s})\right|}{d^{\pi_{\beta}}(\mathbf{s})}\sum_{\mathbf{a}}\dfrac{\pi^{2}(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}\right)^{-1}.$

It is worth noting that the learned value function still lower bounds the true
value function for any state and action in the training datasets, i.e.
$\mathbf{s},\mathbf{a}\in\mathcal{D}$, even when we consider the sampling
error defined in the Lemma A.1. Further details are shown in Corollary A.1. We
have no reward or transition pair collected at unseen states or actions
outside the training dataset, so it is impossible to bound the error outside
the training dataset when consider the sampling error introduced by the reward
function and the transition function.

We can now step further and show that the values at OOD states are lower than
those at in-distribution states based on the learned value function. The proof
can be found in Appendix A.3.

###### Theorem 4.2

For any state $\mathbf{s}\in\mathcal{S}$, if $\varepsilon>0$ is sufficiently
large, then the expectation of the learned value function via Eqn. 5 under the
state marginal $d^{\pi_{\beta}}(\mathbf{s})$ in the training data is higher
than that under $d^{\phi}(\mathbf{s})$, i.e., $\mathbb{E}_{\mathbf{s}\sim
d^{\phi}(\mathbf{s})}[\hat{V}^{\pi}(\mathbf{s})]<\mathbb{E}_{\mathbf{s}\sim
d^{\pi_{\beta}}(\mathbf{s})}[\hat{V}^{\pi}(\mathbf{s})]$.

During training time, we can at least evaluate Q-values of OOD actions based
on in-distribution states. However, there is actually no information about
immediate rewards at OOD states, thus no information about Q-values.
Intuitively, under offline settings, the best we can do to mitigate the
problem of OOD states is to suppress values at these OOD states, and raising
values at in-distribution states, so that the agent can be attracted to the
area where it is familiar near the training data. Thm. 4.2 indeed tells us
PessORL models a value function that assigns smaller values to OOD states
compared to those at in-distribution states. Optimizing a policy under such a
value function is similar to forcing the policy to avoid unknown states and
actions.

In summary, PessORL can learn a pessimistic value function that lower bounds
the true value function. Furthermore, this value function assigns smaller
values to OOD states compared to those at in-distribution states, which helps
the agent avoid or even recover from OOD states.

##  5 Implementing the Algorithm

In this section, we introduce a practical PessORL algorithm based on Eqn. 5.
This algorithm simply modifies the policy evaluation step of Deep Q-Learning
or Soft Actor-Critic algorithms, which is easy to implement.

###  5.1 Detecting OOD states

In prior to designing the algorithm, we need to choose a proper
$d^{\phi}(\mathbf{s})$, which requires a tool for OOD state detection.
Following [11, 14, 29], we use bootstrapping to detect OOD states. In
particular, we train a bag of Gaussian dynamics models [29]
$\\{\hat{P}_{1},\hat{P}_{2},\dots,\hat{P}_{n}\\}$ where each model is
$\hat{P}_{i}(\cdot|\mathbf{s},\mathbf{a})=\mathcal{N}(\mathbf{s}+\hat{f}_{\phi_{i}}(\mathbf{s},\mathbf{a}),\hat{\Sigma}_{\phi_{i}})$.
The function $\hat{f}_{\phi_{i}}$ outputs the mean difference between the next
state and the current state, and $\Sigma_{\phi_{i}}$ models the standard
deviation. OOD states are detected by estimating the uncertainty of bootstrap
models at a given state $\mathbf{s}\in\mathcal{S}$. Concretely, we define
$u_{\pi}(\mathbf{s})=\mathbb{E}_{\mathbf{a}\sim\pi(\mathbf{a}|\mathbf{s})}\left[\frac{1}{n}\sum_{i=1}^{n}\left(\hat{f}_{\phi_{i}}(\mathbf{s},\mathbf{a})-\bar{f}_{\phi}(\mathbf{s},\mathbf{a})\right)^{2}\right]$,
where
$\bar{f}_{\phi}(\mathbf{s},\mathbf{a})=\dfrac{1}{n}\sum_{i=1}^{n}\hat{f}_{\phi_{i}}(\mathbf{s},\mathbf{a})$
is the mean of outputs of all $\hat{f}_{\phi_{i}}$, and the actions are drawn
from a policy distribution $\pi$. A high $u_{\pi}(\mathbf{s})$ value indicates
the state is more likely to be an unseen state. Given a set of sampled states
$\\{s_{1},s_{2},\dots,s_{n}\\}$, we can define a discrete distribution over it
using $u_{\pi}(\mathbf{s})$:
$\zeta(\mathbf{s}_{i})=\dfrac{u(\mathbf{s}_{i})}{\sum_{j}u(\mathbf{s}_{j})},i=1,2,...,n$,
which assign high probabilities to OOD states. In the following section, we
will use it to construct the distribution $d^{\phi}(\mathbf{s})$.

###  5.2 Practical Implementation of PessORL

1 Initialize: A Q network $Q_{\theta}$ parametrized by $\theta$, A target
network $Q_{\bar{\theta}}=Q_{\theta}$ parametrized by $\bar{\theta}$, a policy
network $\pi_{\varphi}$ parametrized by $\varphi$, and a bag of dynamics
models $\\{\hat{P}_{1},\hat{P}_{2},\dots,\hat{P}_{n}\\}$ to detect OOD states;

2 // Dynamics Models Training (Models are used by
$u_{\pi_{\varphi}}(\mathbf{s})$ to detect OOD states in the policy evaluation
step)

3 for  _step $i$ in range($0$, $M$)_ do

4 Train dynamics models $\\{\hat{P}_{1},\hat{P}_{2},\dots,\hat{P}_{n}\\}$
according to the transitions in the dataset $\mathcal{D}$, so that we can
later obtain an uncertainty estimation model $u_{\pi}(\mathbf{s})$ in the
policy evaluation step;

5

6 end for

7// Policy Evaluation and Improvement

8 for  _step $t$ in range($0$, $N$)_ do

9 Update $Q_{\theta}$ according to Eqn. 7 with learning rate
$\epsilon_{\theta}$ and $u_{\pi_{\varphi}}(\mathbf{s})$:

10
$\theta_{t}\leftarrow\theta_{t-1}+\epsilon_{\theta}\nabla_{\theta}J(\theta)$ ;

11 Update $\pi_{\varphi}$ according to the soft actor critic style objective
and learning rate $\epsilon_{\varphi}$:

12
$\varphi_{t}\leftarrow\varphi_{t-1}+\epsilon_{\varphi}\mathbb{E}_{\mathbf{s}\sim
d^{\pi_{\beta}}(\mathbf{s}),\mathbf{a}\sim\pi_{\varphi}(\mathbf{a})}[Q_{\theta}(\mathbf{s},\mathbf{a})-\log\pi_{\varphi}(\mathbf{a}|\mathbf{s})]$;

13 if  _$t$ mod target_update == $0$_ then

14 Soft Update the target network
$\bar{\theta}_{t}\leftarrow(1-\tau)\bar{\theta}_{t-1}+\tau\theta_{t-1}$

15 end if

16

17 end for

Algorithm 1 Pessimistic Offline Reinforcement Learning (PessORL)

We now introduce a practical PessORL algorithm. In practice, to obtain a well-
defined distribution $d^{\phi}$, we add an additional optimization problem
over $d^{\phi}$ into the original optimization problem. The resulting
optimization problem for the policy evaluation step is:

$\min_{Q}\max_{d^{\phi}}\left[\varepsilon\left(\mathbb{E}_{\mathbf{s}\sim
d^{\phi}(\mathbf{s}),\mathbf{a}\sim\hat{\pi}^{k}(\mathbf{a}|\mathbf{s})}\left[Q(\mathbf{s},\mathbf{a})\right]-\mathbb{E}_{\mathbf{s}\sim
d^{\pi_{\beta}}(\mathbf{s}),\mathbf{a}\sim\hat{\pi}^{k}(\mathbf{a}|\mathbf{s})}[Q(\mathbf{s},\mathbf{a})]\right)+\mathcal{R}(d^{\phi})\right]\\\
+\mathcal{E}(Q,\hat{\mathcal{B}}^{\pi}\hat{Q}_{\theta}^{k})+\mathcal{C}(Q),$
(6)

where $\mathcal{R}(d^{\phi})$ is a regularization term inspired by [5] in
order to stabilize the training. If we choose
$\mathcal{R}(d^{\phi})=-D_{\text{KL}}(d^{\phi}(\mathbf{s})\>||\>\zeta(\mathbf{s}))$,
where $\zeta(\mathbf{s})$ is the distribution we obtained from uncertainty
estimations, then
$d^{\phi}(\mathbf{s})\propto\zeta(\mathbf{s})\exp\left(V^{\hat{\pi}^{k}}(\mathbf{s})\right)$,
where
$V^{\hat{\pi}^{k}}(\mathbf{s})=\mathbb{E}_{\mathbf{a}\sim\hat{\pi}^{k}(\mathbf{a}|\mathbf{s})}\left[Q(\mathbf{s},\mathbf{a})\right]$.
The resulting $d^{\phi}$ is intuitively reasonable, because it assigns high
probabilities to OOD states with high uncertainty estimations. In particular,
$d^{\phi}$ assigns higher probabilities to states with high values, because we
expect to penalize harder on them than those with low values already. With
this choice of $d^{\phi}$ in Eqn. 6, we obtain the following PessORL policy
evaluation step:

$\min_{Q}J(Q)=\min_{Q}\varepsilon\left(\log\sum_{\mathbf{s}}\zeta(\mathbf{s})\exp\left(V^{\hat{\pi}^{k}}(\mathbf{s})\right)-\mathbb{E}_{\mathbf{s}\sim
d^{\pi_{\beta}}(\mathbf{s})}[V^{\hat{\pi}^{k}}(\mathbf{s})]\right)\\\
+\mathcal{E}(Q,\hat{\mathcal{B}}^{\pi}\hat{Q}_{\theta}^{k})+\mathcal{C}(Q).$
(7)

The first term in Eqn. 7 is very similar to weighted softmax values over the
state space. It penalizes the softmax value over the state space, but also
considers the distances between sample points and the training data. The two
terms following the trade-off factor $\varepsilon$ is actually trying to
decrease the discrepancy between the softmax value over OOD states and the
average value over in-distribution states. Intuitively, it should enforce the
learned value function to output higher values at in-distribution states, and
lower values at out-of-distribution states. The logsumexp term in Eqn. 7 also
mitigates the requirement for an accurate uncertainty estimation
$\zeta(\mathbf{s})$ over the entire state space. Only those states with high
values contribute to the regularization.

The complete algorithm is shown in Algorithm 1. We include the version for
continuous action space which requires a policy network here, and note that if
the action space is discrete, then we no longer need a policy network but just
an implicit policy based on the learned Q-function. We implement PessORL on
top of CQL [5], with its default hyperparameters. We also apply Lagrangian
dual gradient descent to automatically adjust the trade-off factor
$\varepsilon$. During the training process of offline reinforcement learning
algorithms such as CQL and PessORL, we only have access to the dataset
$\mathcal{D}$ instead of $d^{\pi_{\beta}}(\mathbf{s})$ and
$\pi_{\beta}(\mathbf{a}|\mathbf{s})$. Therefore, we follow the convention in
reinforcement learning community and approximated all expectations by Monte
Carlo estimation in Eqn. 7.

##  6 Experiments

We compare our algorithm to prior offline algorithms: two state-of-the-art
offline RL algorithms BEAR [6] and CQL [5]; two baselines adapted directly
from online algorithms, actor-critic algorithm TD3 [30] and DDQN [31]; and
behavior cloning (BC). The TD3 baseline is applied when the action space is
continuous, whereas DDQN is trained when the action space is discrete. We
evaluate each algorithm on a wide range of task domains, including tasks with
both continuous and discrete state and action space. All baselines are run
with the default code and hyperparameters from the original repositories. In
particular, we are interested in the comparison between our algorithm with
CQL, because we essentially add an additional state regularization term to the
original CQL framework.

Figure 1: (a) The whole map of the environment; (b) The state density in
training dataset; (c) The visualization of uncertainty estimation; (d) The
learning curves. The top row (1) and the bottom row (2) are corresponding to
PointmassHard-v0 and PointmassSuperHard-v0, respectively. We can see that
almost all trajectories in the training datasets are located around the
optimal trajectory from the start to the goal in the yellow areas in (b),
indicating they are collected by a near-optimal policy.

###  6.1 Performance on Various Environments

Pointmass Mazes. The task for the agent in this domain is to learn from expert
demonstrations to navigate from a random start to a fixed goal. The expert
dataset, which contains around 1000 trajectories all from the same start point
to the same goal, is collected by online trained RL policy. During the test
time of offline RL algorithms, we reset the start to a random point in the
state space and the goal to the same fixed point as the dataset. In this way,
the performance of the agent at unseen states are evaluated.

Before showing the performance, we first check if the OOD states detection is
accurate, and hence, if we can successfully penalize high values at unseen
states in training datasets. We evaluate the effectiveness of the OOD states
detection method based on the accuracy of uncertainty estimation in the
environment Pointmass. Figure 1(b) and (c) are visualizations of the training
datasets and estimated uncertainty $u_{\pi}(\mathbf{s})$, both of which have
the coordinate systems the same as that in the map (figure 1(a)). We use
different colors in figure 1(b) and (c) to represent different values at each
point in the map. The uncertainty estimations tend to be high (yellow areas in
Fig. 1(c)) in area where the state density is low (blue areas in Fig 1(b)),
and vice versa. This trend empirically shows that our uncertainty estimations
are reasonable. We can trust them to detect OOD states when training offline
RL algorithms.

We include the learning curves in figure 1(d), in which we evaluate each
algorithm based on 3 random seeds, and report the average return. The shaded
area represents the standard deviation of each evaluation. As we can see in
the figures, PessORL outperforms other baselines in both hard and super hard
environments. PessORL benefits from the augmented policy evaluation step in
Eqn. 7. The learned value function produces high values at areas that have low
uncertainty estimations, and low values at highly uncertain areas (OOD
states). Therefore, the agent can be “attracted” to the high value areas from
low value and unfamiliar areas.

Table 1: Performance on Gym and Adroit Domains

Domain Task BC TD3 BEAR CQL PessORL Gym hopper-medium $29.71\pm 2.43$ $0.80\pm
1.11$ $50.08\pm 4.49$ $63.04\pm 8.64$ $\textbf{76.39}\pm 4.80$ walker2d-medium
$13.06\pm 1.74$ $4.91\pm 1.08$ $34.20\pm 8.57$ $70.67\pm 0.95$
$\textbf{75.95}\pm 2.96$ halfcheetah-medium $35.81\pm 0.96$ $24.60\pm 0.79$
$41.25\pm 2.45$ $48.66\pm 0.11$ $\textbf{49.21}\pm 0.59$ ant-medium $83.42\pm
9.63$ $-63.55\pm 0.28$ $-45.78\pm 3.18$ $51.29\pm 3.92$ $\textbf{85.31}\pm
8.56$ hopper-medium-expert $85.22\pm 1.38$ $12.12\pm 0.64$ $37.67\pm 1.84$
$105.84\pm 3.62$ $\textbf{112.80}\pm 4.30$ walker2d-medium-expert $16.12\pm
0.58$ $4.77\pm 2.06$ $17.29\pm 2.46$ $75.27\pm 13.33$ $\textbf{89.67}\pm 6.73$
halfcheetah-medium-expert $\textbf{37.04}\pm 2.77$ $-1.41\pm 0.99$ $-2.93\pm
4.54$ $19.13\pm 9.81$ $24.33\pm 12.24$ ant-medium-expert $\textbf{66.49}\pm
0.76$ $-63.54\pm 0.92$ $31.31\pm 8.72$ $34.44\pm 30.36$ $49.95\pm 16.76$
hopper-random $9.44\pm 1.41$ $8.47\pm 0.52$ $9.29\pm 2.58$ $10.36\pm 3.68$
$\textbf{10.82}\pm 4.11$ walker2d-random $2.08\pm 0.54$ $\textbf{6.04}\pm
1.08$ $0.72\pm 0.82$ $1.11\pm 5.01$ $2.66\pm 3.15$ halfcheetah-random $2.25\pm
0.45$ $27.95\pm 0.59$ $2.16\pm 0.28$ $26.62\pm 1.28$ $\textbf{28.58}\pm 0.96$
ant-random $26.00\pm 0.57$ $-37.31\pm 1.16$ $24.05\pm 2.42$ $26.65\pm 8.65$
$\textbf{27.86}\pm 4.87$ hopper-expert $109.82\pm 1.44$ $1.81\pm 1.04$
$0.78\pm 4.57$ $104.41\pm 10.26$ $\textbf{110.67}\pm 8.60$ walker2d-expert
$60.66\pm 2.26$ $-0.95\pm 0.58$ $21.37\pm 3.52$ $105.55\pm 2.91$
$\textbf{109.37}\pm 4.94$ halfcheetah-expert $\textbf{94.22}\pm 1.09$
$-1.40\pm 2.85$ $13.55\pm 7.67$ $80.19\pm 14.55$ $71.33\pm 20.16$ ant-expert
$\textbf{73.57}\pm 3.28$ $55.07\pm 1.99$ $44.65\pm 10.39$ $59.04\pm 20.66$
$60.54\pm 17.83$ Adroit pen-human $34.46\pm 0.83$ $-3.83\pm 0.43$ $35.62\pm
1.34$ $54.49\pm 7.58$ $\textbf{63.07}\pm 4.36$ door-human $1.46\pm 0.06$
$-0.19\pm 0.01$ $-0.33\pm 0.05$ $1.86\pm 0.29$ $\textbf{2.28}\pm 0.14$ hammer-
human $1.35\pm 0.09$ $0.26\pm 0.12$ $0.46\pm 0.03$ $3.91\pm 0.34$
$\textbf{4.24}\pm 0.28$ relocate-human $0.04\pm 0.02$ $-0.32\pm 0.03$
$-0.30\pm 0.10$ $0.15\pm 0.04$ $\textbf{0.33}\pm 0.12$ pen-cloned $23.58\pm
1.14$ $-3.91\pm 0.36$ $28.92\pm 9.62$ $35.23\pm 11.03$ $\textbf{39.02}\pm
9.25$ door-cloned $0.15\pm 0.08$ $-0.33\pm 0.01$ $-0.16\pm 0.04$
$\textbf{1.72}\pm 0.14$ $1.69\pm 0.35$ hammer-cloned $0.40\pm 0.07$ $0.25\pm
0.04$ $0.21\pm 0.34$ $0.53\pm 0.52$ $\textbf{0.95}\pm 0.38$ relocate-cloned
$-0.24\pm 0.11$ $\textbf{-0.14}\pm 0.08$ $-0.23\pm 0.13$ $-0.28\pm 0.57$
$-0.26\pm 0.24$

Gym Tasks. In this domain, we focus on the locomotion environments from
MuJoCo, including Walker2d-v2, Hopper-v2, Halfcheetah-v2, and Ant-v2. Unlike
Pointmass environment, we directly adopt the d4rl datasets [32] as our
training data in the gym domains. We include four different types of datasets
in our experiments, namely, “medium”, “medium-expert”, “random”, and “expert”.
The “medium”, “random”, and “expert” dataset are all collected by a single
policy, which is an either early-stopping trained, or randomly initialized, or
fully trained expert policy. The “medium-expert” dataset is generated by
mixing mediocre and expert quality data. We show the normalized scores
averaged over 4 random seeds for all methods on gym domain in table 1. We
directly ran all baselines from their original repositories with their default
parameters, and we only report the average scores we actually obtained. As we
can see in the table, PessORL outperforms all other offline RL methods on a
majority of tasks on gym domains. PessORL works especially well with mediocre
quality datasets according to the results. In fact, it is one of the
advantages of offline RL methods over behavior cloning on medium quality
datasets, because offline RL methods take advantage of the information both
from the reward and the underlying state and action distributions in training
datasets, instead of simply imitating behavior policies as behavior cloning.
Medium quality datasets are also considered to be similar to real-world
datasets. Therefore, it is important for an offline RL method to perform well
in medium quality datasets. We also note that PessORL shares some good
properties with CQL, such as satisfying performance on mixed quality datasets.
PessORL and CQL both outperform other offline methods on medium-expert
datasets with PessORL better between them. The reason is that offline RL
methods can “stitch” [32] different trajectories from different policies
together according to the information from the reward.

Adroit Tasks The adroit domain [33] provides more challenging tasks than the
Pointmass environment and the gym domain. The tasks include controlling a
24-DoF simulated Shadow Hand robot to twirl a pen, open a door, hammer a nail,
and relocate a ball. Similar to the datasets in the gym domain, we also
directly use the d4rl datasets as the training datasets in our experiments.
The performance of PessORL and all baselines is shown in table 1. The
normalized scores of all methods are average returns on 5 random seeds. We
note that PessORL has better performance than other baselines on adroit
domains. It is a great advantage for PessORL to learn useful skills from human
demonstrations on these high dimensional and highly realistic robotic
simulations.

###  6.2 Discussions and Limitations

Figure 2: (a) The learning curves in hopper-medium-v0. (b) The discrepancy
$\Delta_{k}$ as a function of gradient steps for PessORL, CQL, and BEAR.

The main contribution of this work is to explicitly limit the values at OOD
states, so that the learned policy can act conservatively at OOD states and
drives the agent back to the familiar areas near the training data. We are
interested to see if our framework can indeed induce a different behavior on
OOD states. We use
$\Delta_{k}=\max_{\mathbf{s}\in\mathcal{S}}[V(\mathbf{s})]-\mathbb{E}_{\mathbf{s}\sim\mathcal{D}}[V(\mathbf{s})]$
as a metric to evaluate it at each iteration. If $\Delta_{k}$ is close to
zero, then intuitively it indicates the values at OOD states are lower than
those at in-distribution states. In Fig. 2, we plot $\Delta_{k}$ at each
iteration in hopper-medium-v0. As is shown in the figure, PessORL successfully
limits $\Delta_{k}$ to be non-positive, which meets our goal in this work and
aligns with the statement in theorem 4.2.

On the gym domain, we notice that the performance of PessORL and CQL on
datasets containing expert trajectories is not satisfying, often not as good
as BC. We believe it is because of overly conservative value estimation. In
fact, it is widely believed that conservative methods suffer from
underestimation [14]. The conservative objective function in Eqn. 7 sometimes
assign values that are too low to OOD states and actions. Besides, the
uncertainty estimation method cannot be guaranteed to be precise on high-
dimensional spaces. It is actually a possible future work direction to solve
the underestimation and uncertainty estimation problems in conservative
methods.

##  7 Conclusion

We propose a Pessimistic Offline Reinforcement Learning framework to deal with
out-of-distribution states. In particular, we add a regularization term in
policy evaluation step to shape value function, so that we can improve its
extrapolation to OOD states. We also provide theoretical guarantees that the
learned pessimistic value function lower bounds the true one and assigns
smaller values to OOD states compared to those at in-distribution states. We
evaluate the PessORL algorithm on various benchmark tasks, where we show that
our method gains better performance by explicitly handling OOD states compared
to those methods merely considering OOD actions.

## References

  * Jaques et al. [2019] N. Jaques, A. Ghandeharioun, J. H. Shen, C. Ferguson, A. Lapedriza, N. Jones, S. Gu, and R. Picard.  Way off-policy batch deep reinforcement learning of implicit human preferences in dialog.  _arXiv preprint arXiv:1907.00456_ , 2019.
  * Kalashnikov et al. [2018] D. Kalashnikov, A. Irpan, P. Pastor, J. Ibarz, A. Herzog, E. Jang, D. Quillen, E. Holly, M. Kalakrishnan, V. Vanhoucke, et al.  Scalable deep reinforcement learning for vision-based robotic manipulation.  In _Conference on Robot Learning_ , pages 651–673. PMLR, 2018.
  * Kahn et al. [2021] G. Kahn, P. Abbeel, and S. Levine.  Badgr: An autonomous self-supervised learning-based navigation system.  _IEEE Robotics and Automation Letters_ , 6(2):1312–1319, 2021.
  * Filos et al. [2020] A. Filos, P. Tigkas, R. McAllister, N. Rhinehart, S. Levine, and Y. Gal.  Can autonomous vehicles identify, recover from, and adapt to distribution shifts?  In _International Conference on Machine Learning_ , pages 3145–3153. PMLR, 2020.
  * Kumar et al. [2020] A. Kumar, A. Zhou, G. Tucker, and S. Levine.  Conservative q-learning for offline reinforcement learning.  _arXiv preprint arXiv:2006.04779_ , 2020.
  * Kumar et al. [2019] A. Kumar, J. Fu, G. Tucker, and S. Levine.  Stabilizing off-policy q-learning via bootstrapping error reduction.  _arXiv preprint arXiv:1906.00949_ , 2019.
  * Osband et al. [2016] I. Osband, C. Blundell, A. Pritzel, and B. Van Roy.  Deep exploration via bootstrapped dqn.  _arXiv preprint arXiv:1602.04621_ , 2016.
  * Eysenbach et al. [2017] B. Eysenbach, S. Gu, J. Ibarz, and S. Levine.  Leave no trace: Learning to reset for safe and autonomous reinforcement learning.  _arXiv preprint arXiv:1711.06782_ , 2017.
  * Agarwal et al. [2020] R. Agarwal, D. Schuurmans, and M. Norouzi.  An optimistic perspective on offline reinforcement learning.  In _International Conference on Machine Learning_ , pages 104–114. PMLR, 2020.
  * O’Donoghue et al. [2018] B. O’Donoghue, I. Osband, R. Munos, and V. Mnih.  The uncertainty bellman equation and exploration.  In _International Conference on Machine Learning_ , pages 3836–3845, 2018.
  * Kidambi et al. [2020] R. Kidambi, A. Rajeswaran, P. Netrapalli, and T. Joachims.  Morel: Model-based offline reinforcement learning.  _arXiv preprint arXiv:2005.05951_ , 2020.
  * Wu et al. [2019] Y. Wu, G. Tucker, and O. Nachum.  Behavior regularized offline reinforcement learning.  _arXiv preprint arXiv:1911.11361_ , 2019.
  * Zhou et al. [2020] W. Zhou, S. Bajracharya, and D. Held.  Plas: Latent action space for offline reinforcement learning.  _arXiv preprint arXiv:2011.07213_ , 2020.
  * Levine et al. [2020] S. Levine, A. Kumar, G. Tucker, and J. Fu.  Offline reinforcement learning: Tutorial, review, and perspectives on open problems.  _arXiv preprint arXiv:2005.01643_ , 2020.
  * Precup [2000] D. Precup.  Eligibility traces for off-policy policy evaluation.  _Computer Science Department Faculty Publication Series_ , page 80, 2000.
  * Gu et al. [2017] S. Gu, E. Holly, T. Lillicrap, and S. Levine.  Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates.  In _2017 IEEE international conference on robotics and automation (ICRA)_ , pages 3389–3396. IEEE, 2017.
  * Huang and Jiang [2020] J. Huang and N. Jiang.  From importance sampling to doubly robust policy gradient.  In _International Conference on Machine Learning_ , pages 4434–4443. PMLR, 2020.
  * Pankov [2018] S. Pankov.  Reward-estimation variance elimination in sequential decision processes.  _arXiv preprint arXiv:1811.06225_ , 2018.
  * Cheng et al. [2020] C.-A. Cheng, X. Yan, and B. Boots.  Trajectory-wise control variates for variance reduction in policy gradient methods.  In _Conference on Robot Learning_ , pages 1379–1394. PMLR, 2020.
  * Fujimoto et al. [2019] S. Fujimoto, D. Meger, and D. Precup.  Off-policy deep reinforcement learning without exploration.  In _International Conference on Machine Learning_ , pages 2052–2062. PMLR, 2019.
  * Siegel et al. [2020] N. Y. Siegel, J. T. Springenberg, F. Berkenkamp, A. Abdolmaleki, M. Neunert, T. Lampe, R. Hafner, N. Heess, and M. Riedmiller.  Keep doing what worked: Behavioral modelling priors for offline reinforcement learning.  _arXiv preprint arXiv:2002.08396_ , 2020.
  * Peng et al. [2019] X. B. Peng, A. Kumar, G. Zhang, and S. Levine.  Advantage-weighted regression: Simple and scalable off-policy reinforcement learning.  _arXiv preprint arXiv:1910.00177_ , 2019.
  * Nair et al. [2020] A. Nair, M. Dalal, A. Gupta, and S. Levine.  Accelerating online reinforcement learning with offline datasets.  _arXiv preprint arXiv:2006.09359_ , 2020.
  * Sutton [1991] R. S. Sutton.  Dyna, an integrated architecture for learning, planning, and reacting.  _ACM Sigart Bulletin_ , 2(4):160–163, 1991.
  * Watter et al. [2015] M. Watter, J. T. Springenberg, J. Boedecker, and M. Riedmiller.  Embed to control: A locally linear latent dynamics model for control from raw images.  _arXiv preprint arXiv:1506.07365_ , 2015.
  * Zhang et al. [2019] M. Zhang, S. Vikram, L. Smith, P. Abbeel, M. Johnson, and S. Levine.  Solar: Deep structured representations for model-based reinforcement learning.  In _International Conference on Machine Learning_ , pages 7444–7453. PMLR, 2019.
  * Hafner et al. [2019] D. Hafner, T. Lillicrap, I. Fischer, R. Villegas, D. Ha, H. Lee, and J. Davidson.  Learning latent dynamics for planning from pixels.  In _International Conference on Machine Learning_ , pages 2555–2565. PMLR, 2019.
  * Janner et al. [2019] M. Janner, J. Fu, M. Zhang, and S. Levine.  When to trust your model: Model-based policy optimization.  _arXiv preprint arXiv:1906.08253_ , 2019.
  * Chua et al. [2018] K. Chua, R. Calandra, R. McAllister, and S. Levine.  Deep reinforcement learning in a handful of trials using probabilistic dynamics models.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.  URL https://proceedings.neurips.cc/paper/2018/file/3de568f8597b94bda53149c7d7f5958c-Paper.pdf.
  * Fujimoto et al. [2018] S. Fujimoto, H. Hoof, and D. Meger.  Addressing function approximation error in actor-critic methods.  In _International Conference on Machine Learning_ , pages 1587–1596. PMLR, 2018.
  * Van Hasselt et al. [2016] H. Van Hasselt, A. Guez, and D. Silver.  Deep reinforcement learning with double q-learning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 30, 2016.
  * Fu et al. [2020] J. Fu, A. Kumar, O. Nachum, G. Tucker, and S. Levine.  D4rl: Datasets for deep data-driven reinforcement learning, 2020.
  * Rajeswaran et al. [2017] A. Rajeswaran, V. Kumar, A. Gupta, G. Vezzani, J. Schulman, E. Todorov, and S. Levine.  Learning complex dexterous manipulation with deep reinforcement learning and demonstrations.  _arXiv preprint arXiv:1709.10087_ , 2017.

##  Appendix A Proof of Theorem

In this section, we provide the proofs of the theorems in this paper.

Remark. We provide the proofs under a tabular setting. Most continuous space
can be approximately discretized to a tabular form, although the cordiality of
the tabular form may be large. We define $P^{\pi}$ as the tabular transition
probabilities under the policy $\pi$.

###  A.1 Proof of Theorem 4.1

In Eqn. 5, The Q-function update can be computed in a tabular setting, by
setting the derivative of the augmented objective in Eqn. 5 with respect to
$Q$ to zero,

$\displaystyle\varepsilon\left(d^{\phi}\pi-d^{\pi_{\beta}}\pi\right)+\alpha\left(d^{\pi_{\beta}}\pi-d^{\pi_{\beta}}\pi_{\beta}\right)+d^{\pi_{\beta}}\pi_{\beta}\left(Q-\mathcal{B}\hat{Q}^{k}\right)=0$

Therefore, we can obtain $\hat{Q}^{k+1}$ in terms of $\hat{Q}^{k}$ by
rearranging the terms,

$\displaystyle\hat{Q}^{k+1}(\mathbf{s},\mathbf{a})=\hat{\mathcal{B}}^{\pi}\hat{Q}^{k}(\mathbf{s},\mathbf{a})-\varepsilon\dfrac{\left(d^{\phi}(\mathbf{s})-d^{\pi_{\beta}}(\mathbf{s})\right)\pi(\mathbf{a}|\mathbf{s})}{d^{\pi_{\beta}}(\mathbf{s})\pi_{\beta}(\mathbf{a}|\mathbf{s})}-\alpha\left[\dfrac{\pi(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}-1\right],$
(8)

for all $\mathbf{s}\in\mathcal{S}$, $\mathbf{a}\in\mathcal{A}$ and
$k\in[0,+\infty)$. For the state-action pair $(\mathbf{s},\mathbf{a})$ such
that $d^{\phi}(\mathbf{s})<d^{\pi_{\beta}}(\mathbf{s})$ and
$\pi(\mathbf{a}|\mathbf{s})<\pi_{\beta}(\mathbf{a}|\mathbf{s})$, the last two
terms of Eqn. 8,
$-\varepsilon\dfrac{\left(d^{\phi}(\mathbf{s})-d^{\pi_{\beta}}(\mathbf{s})\right)\pi(\mathbf{a}|\mathbf{s})}{d^{\pi_{\beta}}(\mathbf{s})\pi_{\beta}(\mathbf{a}|\mathbf{s})}-\alpha\left[\dfrac{\pi(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}-1\right]$
is positive, so that we cannot simply lower bound the true Q-function
$Q^{k+1}(\mathbf{s},\mathbf{a})$ by the estimated one
$\hat{Q}^{k+1}(\mathbf{s},\mathbf{a})$ point-wise. However, we can prove that
the value function, which is the expectation of the Q-function, can be lower
bounded. Taking the expectation of both sides of Eqn. 8 under the distribution
$\mathbf{a}\sim\pi(\mathbf{a}|\mathbf{s})$, we have

$\displaystyle\hat{V}^{k+1}(\mathbf{s})=\mathcal{B}^{\pi}\hat{V}^{k}(\mathbf{s})-\varepsilon\mathbb{E}_{\mathbf{a}\sim\pi(\mathbf{a}|\mathbf{s})}\left[\dfrac{\left(d^{\phi}(\mathbf{s})-d^{\pi_{\beta}}(\mathbf{s})\right)\pi(\mathbf{a}|\mathbf{s})}{d^{\pi_{\beta}}(\mathbf{s})\pi_{\beta}(\mathbf{a}|\mathbf{s})}\right]-\alpha\mathbb{E}_{\mathbf{a}\sim\pi(\mathbf{a}|\mathbf{s})}\left[\dfrac{\pi(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}-1\right].$
(9)

The first goal is to prove that
$\hat{V}^{k+1}\leq\mathcal{B}^{\pi}\hat{V}^{k}$ which implies that each
iteration introduces some underestimation, and $\hat{V}^{k}$ could eventually
converge to a fixed point. Therefore, we need to prove the last two terms on
the right hand side of Eqn. 9 is negative. We denote $\Delta$ to be the
opposite of the last two terms on the right hand side of Eqn. 9, then

$\displaystyle\begin{aligned}
\Delta&=\varepsilon\mathbb{E}_{\mathbf{a}\sim\pi(\mathbf{a}|\mathbf{s})}\left[\dfrac{\left(d^{\phi}(\mathbf{s})-d^{\pi_{\beta}}(\mathbf{s})\right)\pi(\mathbf{a}|\mathbf{s})}{d^{\pi_{\beta}}(\mathbf{s})\pi_{\beta}(\mathbf{a}|\mathbf{s})}\right]+\alpha\mathbb{E}_{\mathbf{a}\sim\pi(\mathbf{a}|\mathbf{s})}\left[\dfrac{\pi(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}-1\right]\\\
&=\varepsilon\dfrac{d^{\phi}(\mathbf{s})-d^{\pi_{\beta}}(\mathbf{s})}{d^{\pi_{\beta}}(\mathbf{s})}\sum_{\mathbf{a}}\dfrac{\pi^{2}(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}+\alpha\sum_{\mathbf{a}}\pi(\mathbf{a}|\mathbf{s})\left[\dfrac{\pi(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}-1\right].\end{aligned}$
(10)

From the proof in [1], we know that the second term in Eqn. 10 is non-negative
when $\alpha>0$, that is

$\displaystyle
D_{\text{CQL}}(\mathbf{s})=\sum_{\mathbf{a}}\pi(\mathbf{a}|\mathbf{s})\left[\dfrac{\pi(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}-1\right]\geq
0.$ (11)

Hence, when $d^{\phi}(\mathbf{s})-d^{\pi_{\beta}}(\mathbf{s})\geq 0$, it is
obvious that $\Delta\geq 0$ for all $\varepsilon>0$. When
$d^{\phi}(\mathbf{s})-d^{\pi_{\beta}}(\mathbf{s})<0$, if $\varepsilon$
satisfies

$\displaystyle\varepsilon\leq\alpha
D_{\text{CQL}}(\mathbf{s})\left(\dfrac{\left|d^{\phi}(\mathbf{s})-d^{\pi_{\beta}}(\mathbf{s})\right|}{d^{\pi_{\beta}}(\mathbf{s})}\sum_{\mathbf{a}}\dfrac{\pi^{2}(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}\right)^{-1},$
(12)

then we have $\Delta\geq 0$.

In summary, we have $\Delta\geq 0$ when Eqn. 12 holds. Since the exact Bellman
update operator $\mathcal{B}^{\pi}$ is a contraction [4], we have

$\displaystyle||\mathcal{B}^{\pi}\hat{V}^{k+1}-\mathcal{B}^{\pi}\hat{V}^{k}||=||(\mathcal{B}^{\pi}\hat{V}^{k+1}-\Delta)-(\mathcal{B}^{\pi}\hat{V}^{k}-\Delta)||\leq\gamma||\hat{V}^{k+1}-\hat{V}^{k}||$

which implies that each value-function update
$\hat{V}^{k+1}=\mathcal{B}^{\pi}\hat{V}^{k}-\Delta$ is a contraction.
According to the contraction mapping theorem, the recursive update in Eqn. 9
will always lead value function to converge to a fixed point $\hat{V}^{\pi}$.
Now that $V^{\pi}=\mathcal{B}^{\pi}V^{\pi}$ for the true value functions, by
subtracting them from both side of Eqn. 9 and substitute $\hat{V}^{k+1}$ and
$\hat{V}^{k}$ with the fixed point $\hat{V}^{\pi}$, we have

$\displaystyle\hat{V}^{\pi}=V^{\pi}-\underbrace{(I-\gamma
P^{\pi})^{-1}}_{\text{Positive semi-
definite}}\left[\underbrace{\alpha\mathbb{E}_{\pi}\left[\dfrac{\pi}{\pi_{\beta}}-\mathbf{1}\right]+\varepsilon\mathbb{E}_{\pi}\left[\dfrac{(d^{\phi}-d^{\pi_{\beta}})\pi}{d^{\pi_{\beta}}\pi_{\beta}}\right]}_{\text{$\geq\mathbf{0}$}}\right],$
(13)

when $\varepsilon$ satisfies

$\displaystyle\dfrac{\varepsilon}{\alpha}\leq\min_{\mathbf{s}}\left(\sum_{\mathbf{a}}\pi(\mathbf{a}|\mathbf{s})\left[\dfrac{\pi(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}-1\right]\right)\left(\dfrac{\left|d^{\phi}(\mathbf{s})-d^{\pi_{\beta}}(\mathbf{s})\right|}{d^{\pi_{\beta}}(\mathbf{s})}\sum_{\mathbf{a}}\dfrac{\pi^{2}(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}\right)^{-1}.$
(14)

In Eqn. 13, we stretch all notations to be vectors, which means
$\hat{V}^{\pi}\in\Re^{|\mathcal{S}|}$, $V^{\pi}\in\Re^{|\mathcal{S}|}$, and
$\alpha\mathbb{E}_{\pi}\left[\dfrac{\pi}{\pi_{\beta}}-\mathbf{1}\right]+\varepsilon\mathbb{E}_{\pi}\left[\dfrac{(d^{\phi}-d^{\pi_{\beta}})\pi}{d^{\pi_{\beta}}\pi_{\beta}}\right]\in\Re^{|\mathcal{S}|}$
are all vectors containing values for all states. Here, $\mathbf{1}$ denotes
the vector in which the entries are all $1$. The expectations and the
operations inside
$\alpha\mathbb{E}_{\pi}\left[\dfrac{\pi}{\pi_{\beta}}-\mathbf{1}\right]+\varepsilon\mathbb{E}_{\pi}\left[\dfrac{(d^{\phi}-d^{\pi_{\beta}})\pi}{d^{\pi_{\beta}}\pi_{\beta}}\right]$
are all computed in a point-wise manner.

Therefore, we can conclude from Eqn. 13 that the estimated value function
$\hat{V}^{\pi}(\mathbf{s})$ is a lower bound of the true value-function
$V^{\pi}(\mathbf{s})$ without considering any sampling error. Thus, we finish
the proof of Thm. 4.1.

###  A.2 Value Lower Bound in Existence of Sampling Errors

We now take sampling error into account. First, we introduce a lemma from [1]:

###### Lemma A.1

If with high probability $\delta$ the reward function
$r(\mathbf{s},\mathbf{a})$ and the transition function
$T(\mathbf{s}^{\prime}|\mathbf{s},\mathbf{a})$ can be estimated with bounded
error, then the sampling error of the empirical Bellman operator is also
bounded:

$\displaystyle\left|\hat{\mathcal{B}}^{\pi}V(\mathbf{s})-\mathcal{B}^{\pi}V(\mathbf{s})\right|\leq\dfrac{C_{r,T,\delta}R_{\max}}{(1-\gamma)\sqrt{|\mathcal{D}(\mathbf{s},\mathbf{a})|}},$
(15)

where $C_{r,T,\delta}$ is a constant related to $r$, $T$, and $\delta$, and
$R_{\max}$ is the maximum possible reward in the environment.

Note that the bound of the error
$\left|\hat{\mathcal{B}}^{\pi}V(\mathbf{s})-\mathcal{B}^{\pi}V(\mathbf{s})\right|$
in Lemma A.1 only holds for states and actions in the training datasets, i.e.
$\mathbf{s},\mathbf{a}\in\mathcal{D}$. We have no reward or transition pair
collected at unseen states or actions outside the training dataset, so it is
impossible to bound the error outside the training dataset when consider the
sampling error introduced by the reward function and the transition function.
Therefore, we can lower bound the true value function by the learned value
function at states and actions in the training datasets as in the following
corollary.

###### Corollary A.1

When the sampling error defined in Lemma A.1, for any state and any action in
the training dataset, $\mathbf{s},\mathbf{a}\in\mathcal{D}$, the learned value
function via Eqn. 5 is a lower bound of the true one, i.e.,
$\hat{V}^{\pi}(\mathbf{s})\leq V^{\pi}(\mathbf{s})$, if the trade-off factor
$\varepsilon$ and $\alpha$ satisfy the constraints

$\displaystyle\begin{aligned}
\varepsilon&\leq\alpha\min_{\mathbf{s}\in\mathcal{D}}\left(\sum_{\mathbf{a}}\pi(\mathbf{a}|\mathbf{s})\left[\dfrac{\pi(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}-1\right]\right)\left(\dfrac{\left|d^{\phi}(\mathbf{s})-d^{\pi_{\beta}}(\mathbf{s})\right|}{d^{\pi_{\beta}}(\mathbf{s})}\sum_{\mathbf{a}}\dfrac{\pi^{2}(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}\right)^{-1}\\\
\alpha&\geq\max_{\mathbf{s},\mathbf{a}\in\mathcal{D}}\dfrac{C_{r,T,\delta}R_{\max}}{(1-\gamma)\sqrt{|\mathcal{D}(\mathbf{s},\mathbf{a})|}}\cdot\max_{\mathbf{s},\mathbf{a}\in\mathcal{D}}\left(\sum_{\mathbf{a}}\pi(\mathbf{a}|\mathbf{s})\left[\dfrac{\pi(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}-1\right]\right)^{-1}.\end{aligned}$
(16)

We now show the proof of Corollary A.1. From Eqn. 13, we can directly bound
the estimated value function for any $\mathbf{s},\mathbf{a}\in\mathcal{D}$ by

$\hat{V}^{\pi}=V^{\pi}-(I-\gamma
P^{\pi})^{-1}\left[\alpha\mathbb{E}_{\pi}\left[\dfrac{\pi}{\pi_{\beta}}-\mathbf{1}\right]+\varepsilon\mathbb{E}_{\pi}\left[\dfrac{(d^{\phi}-d^{\pi_{\beta}})\pi}{d^{\pi_{\beta}}\pi_{\beta}}\right]-\dfrac{C_{r,T,\delta}R_{\max}}{(1-\gamma)\sqrt{|\mathcal{D}(\mathbf{s},\mathbf{a})|}}\right],$
(17)

when $\varepsilon$ and $\alpha$ satisfy the constraints in Eqn. 16. Note that
in Eqn. 17, we use vector notations similar to those in Eqn. 13.

Therefore, when we consider sampling error introduced by the reward function
and the transition pair, the learned value function by PessORL still lower
bounds the true one for any states and actions in the training dataset. Thus,
we finish the proof of Corollary A.1.

###  A.3 Proof of Theorem 4.2

We begin the proof from Eqn. 9. We first take the expectation of both side of
Eqn. 9 under the distribution $d^{\phi}$, then

$\mathbb{E}_{d^{\phi}(\mathbf{s})}\left[\hat{V}^{k+1}(\mathbf{s})\right]=\mathbb{E}_{d^{\phi}(\mathbf{s})}\left[\mathcal{B}^{\pi}\hat{V}^{k}(\mathbf{s})\right]\\\
-\varepsilon\sum_{\mathbf{s}}d^{\phi}(\mathbf{s})\dfrac{d^{\phi}(\mathbf{s})-d^{\pi_{\beta}}(\mathbf{s})}{d^{\pi_{\beta}}(\mathbf{s})}\sum_{\mathbf{a}}\dfrac{\pi^{2}(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}-\alpha\sum_{\mathbf{s}}d^{\phi}(\mathbf{s})\sum_{\mathbf{a}}\pi(\mathbf{a}|\mathbf{s})\left[\dfrac{\pi(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}-1\right].$
(18)

Similarly, we take the expectation of both side of Eqn. 9 under the
distribution $d^{\pi_{\beta}}$, then we have

$\mathbb{E}_{d^{\pi_{\beta}}(\mathbf{s})}\left[\hat{V}^{k+1}(\mathbf{s})\right]=\mathbb{E}_{d^{\pi_{\beta}}(\mathbf{s})}\left[\mathcal{B}^{\pi}\hat{V}^{k}(\mathbf{s})\right]\\\
-\varepsilon\sum_{\mathbf{s}}d^{\pi_{\beta}}(\mathbf{s})\dfrac{d^{\phi}(\mathbf{s})-d^{\pi_{\beta}}(\mathbf{s})}{d^{\pi_{\beta}}(\mathbf{s})}\sum_{\mathbf{a}}\dfrac{\pi^{2}(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}-\alpha\sum_{\mathbf{s}}d^{\pi_{\beta}}(\mathbf{s})\sum_{\mathbf{a}}\pi(\mathbf{a}|\mathbf{s})\left[\dfrac{\pi(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}-1\right].$
(19)

If we subtract Eqn. 19 from Eqn. 18, we get

$\mathbb{E}_{d^{\phi}}\left[\hat{V}^{k+1}(\mathbf{s})\right]-\mathbb{E}_{d^{\pi_{\beta}}}\left[\hat{V}^{k+1}(\mathbf{s})\right]=d^{\phi\top}\mathcal{B}^{\pi}\hat{V}^{k}(\mathbf{s})-d^{\pi_{\beta}\top}\mathcal{B}^{\pi}\hat{V}^{k}(\mathbf{s})\\\
-\varepsilon\sum_{\mathbf{s}}\dfrac{(d^{\pi}(\mathbf{s})-d^{\pi_{\beta}}(\mathbf{s}))^{2}}{d^{\pi_{\beta}}(\mathbf{s})}\sum_{\mathbf{a}}\dfrac{\pi^{2}(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}-\alpha\sum_{\mathbf{s}}(d^{\phi}(\mathbf{s})-d^{\pi_{\beta}}(\mathbf{s}))\sum_{\mathbf{a}}\dfrac{\left(\pi(\mathbf{a}|\mathbf{s})-\pi_{\beta}(\mathbf{a}|\mathbf{s})\right)^{2}}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}$
(20)

Therefore, we have
$\mathbb{E}_{d^{\phi}}\left[\hat{V}^{k+1}(\mathbf{s})\right]\leq\mathbb{E}_{d^{\pi_{\beta}}}\left[\hat{V}^{k+1}(\mathbf{s})\right]$,
if $\varepsilon$ satisfies

$\varepsilon\geq\left[d^{\phi\top}\mathcal{B}^{\pi}\hat{V}^{k}(\mathbf{s})-d^{\pi_{\beta}\top}\mathcal{B}^{\pi}\hat{V}^{k}(\mathbf{s})-\alpha\sum_{\mathbf{s}}(d^{\phi}(\mathbf{s})-d^{\pi_{\beta}}(\mathbf{s}))\sum_{\mathbf{a}}\dfrac{\left(\pi(\mathbf{a}|\mathbf{s})-\pi_{\beta}(\mathbf{a}|\mathbf{s})\right)^{2}}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}\right]\\\
\times\left[\sum_{\mathbf{s}}\dfrac{(d^{\pi}(\mathbf{s})-d^{\pi_{\beta}}(\mathbf{s}))^{2}}{d^{\pi_{\beta}}(\mathbf{s})}\sum_{\mathbf{a}}\dfrac{\pi^{2}(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}\right]^{-1}.$
(21)

###  A.4 Existence of Feasible Trade-off Factor

Note that both Eqn. 21 and Eqn. 16 put constraints on the trade-off factor
$\varepsilon$. We show that we can choose an appropriate value of $\alpha$ to
ensure that a feasible $\varepsilon$ that satisfies both constraints exist.
Formally, we denote

$\displaystyle\begin{aligned}
&X=d^{\phi\top}\mathcal{B}^{\pi}\hat{V}^{k}(\mathbf{s})-d^{\pi_{\beta}\top}\mathcal{B}^{\pi}\hat{V}^{k}(\mathbf{s}),\\\
&Y=\sum_{\mathbf{s}}(d^{\phi}(\mathbf{s})-d^{\pi_{\beta}}(\mathbf{s}))\sum_{\mathbf{a}}\dfrac{\left(\pi(\mathbf{a}|\mathbf{s})-\pi_{\beta}(\mathbf{a}|\mathbf{s})\right)^{2}}{\pi_{\beta}(\mathbf{a}|\mathbf{s})},\\\
&Z=\sum_{\mathbf{s}}\dfrac{(d^{\pi}(\mathbf{s})-d^{\pi_{\beta}}(\mathbf{s}))^{2}}{d^{\pi_{\beta}}(\mathbf{s})}\sum_{\mathbf{a}}\dfrac{\pi^{2}(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})},\\\
&W=\min_{\mathbf{s}\in\mathcal{D}}\left(\sum_{\mathbf{a}}\pi(\mathbf{a}|\mathbf{s})\left[\dfrac{\pi(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}-1\right]\right)\left(\dfrac{\left|d^{\phi}(\mathbf{s})-d^{\pi_{\beta}}(\mathbf{s})\right|}{d^{\pi_{\beta}}(\mathbf{s})}\sum_{\mathbf{a}}\dfrac{\pi^{2}(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}\right)^{-1}\\\
&U=\max_{\mathbf{s},\mathbf{a}\in\mathcal{D}}\dfrac{C_{r,T,\delta}R_{\max}}{(1-\gamma)\sqrt{|\mathcal{D}(\mathbf{s},\mathbf{a})|}}\cdot\max_{\mathbf{s},\mathbf{a}\in\mathcal{D}}\left(\sum_{\mathbf{a}}\pi(\mathbf{a}|\mathbf{s})\left[\dfrac{\pi(\mathbf{a}|\mathbf{s})}{\pi_{\beta}(\mathbf{a}|\mathbf{s})}-1\right]\right)^{-1}\end{aligned}$
(22)

for simplicity. From Eqn. 16 and 21, we have

$\displaystyle(X-\alpha Y)Z^{-1}\leq\varepsilon\leq\alpha W$
$\displaystyle\alpha\geq U$

Hence, there exists a feasible $\varepsilon$ when $(X-\alpha
Y)Z^{-1}\leq\alpha W$ and $\alpha\geq U$. Thus, when

$\displaystyle\alpha\geq\min\left(X(WZ+Y)^{-1},U\right),$ (23)

we can choose a feasible $\varepsilon$ from the interval $\left[\left(X-\alpha
Y\right)Z^{-1},\alpha W\right]$.

##  Appendix B Implementation Details of the Algorithm

The implementation of our algorithm is based on the original implementation of
CQL: https://github.com/aviralkumar2907/CQL. We first train a bag of dynamics
models $\\{\mathcal{P}_{1},\mathcal{P}_{2},\dots,\mathcal{P}_{n}\\}$, and then
train the Q-network and policy network. When we train the Q-network and policy
network, the uncertainty estimation model $u_{\pi}(\mathbf{s})$ is induced by
the pre-trained dynamics models. We found in the experiments that a fixed
trade-off factor $\varepsilon$ would cause the learned value function to be
too conservative and hence the learned policy to fail, so we choose to use a
varying $\varepsilon$ which is adjusted by dual gradient-descent. Following
the implementation of CQL, we introduce a “budget” parameter $\tau$ to
automatically control $\varepsilon$ as below:

$\min_{Q}\max_{\varepsilon\geq
0}\left[\varepsilon\left(\log\sum_{\mathbf{s}}\zeta(\mathbf{s})\exp\left(V^{\hat{\pi}^{k}}(\mathbf{s})\right)-\mathbb{E}_{\mathbf{s}\sim
d^{\pi_{\beta}}(\mathbf{s})}[V^{\hat{\pi}^{k}}(\mathbf{s})]\right)-\tau\right]\\\
+\mathcal{E}(Q,\hat{\mathcal{B}}^{\pi}\hat{Q}_{\theta}^{k})+\mathcal{C}(Q).$
(24)

From Eqn. 24, we can see that if the discrepancy between values is less than
$\tau$, then $\varepsilon$ will be set to zero. When the discrepancy is larger
than the threshold $\tau$, $\varepsilon$ will be increased to a large value to
penalize harder on the value function. This automatic mechanism ensures a
reasonable choice of $\varepsilon$, and reduce the tedious procedure to tune
the hyperparameter $\varepsilon$. In the Gym MuJoCo domain, we choose
$\tau=0.0$ for the Hopper environment, and $\tau=10.0$ for the Walker2d,
Halfcheetah and Ant environment. In the Adroit domain, we choose $\tau=20.0$
for all four environments.

For the dynamics models learning part, we follow the convention in model-based
reinforcement learning domain, and adopt a four layers MLP with a size of
$400$ each. We choose to train five bootstrap models and collect them in a bag
to estimate uncertainty later in the policy evaluation and improvement steps.
Each dynamic model is a Gaussian model which outputs the mean and the logstd
of the next state deviation. When we train the models, we iterate through all
training data for $10$ epochs with a learning rate of $1e-4$ and a batch size
of $256$.

For the Q-function learning part of the algorithm, we inherit the twin
Q-function trick and soft target updates from the original SAC implementation
on D4RL tasks. The Q-functions are optimized by Adam with a batch size of
$256$, and the learning rate is chosen to be $3e-4$ across the environments.
We design the Q-functions to have three layers with a size of $256$ each. When
we evaluate the logsumexp term in Eqn. 24, we need to sample states from the
state space. However, the state space is unbounded on the gym domain and
Adroit domain, so we set the sample range to be
$[\mu-10*\sigma,\mu+10*\sigma]$, where $\mu$ and $\sigma$ are the mean and the
standard deviation of the current batch sampled from the training dataset.

For the policy learning part of the algorithm, we do not need an explicit
policy network to model the policy, but just an implicit argmax policy in
discrete settings such as Pointmass environment. In continuous settings on the
Gym and the Adroit domain, we adopt a Tanh-Gaussian policy structure by the
rlkit repository: https://github.com/vitchyr/rlkit. Since the action spaces in
these domains are all bounded by $-1$ and $1$, the Tanh-Gaussian policy can
capture this constraint naturally. The policy network is designed to have
three layers with a size of $256$ each. The policy network is also optimized
by Adam with a batch size of $256$, with a learning rate of $3e-4$ for the
Pointmass and the Gym domain, and $3e-5$ for the Adroit domain.

##  Appendix C Ablation Studies

###  C.1 What if $d^{\phi}(\mathbf{s})$ is induced by a uniform distribution?

In Sec. 5, we introduced a practical method to construct
$d^{\phi}(\mathbf{s})$. Alternatively, we may simply set $\zeta(\mathbf{s})$
as a uniform distribution, which also satisfies our requirement and leads to
$d^{\phi}(\mathbf{s})\propto\exp\left(V^{\hat{\pi}^{k}}(\mathbf{s})\right)$. A
uniform distribution could be more convenient if it is time consuming to
construct $d^{\phi}(\mathbf{s})$ from data. Formally, if we choose
$d^{\phi}(\mathbf{s})\propto\exp\left(V^{\hat{\pi}^{k}}(\mathbf{s})\right)$
which is induced by a uniform distribution, then the practical PessORL policy
evaluation step becomes:

$\min_{Q}\max_{\varepsilon\geq
0}\left[\varepsilon\left(\log\sum_{\mathbf{s}}\exp\left(V^{\hat{\pi}^{k}}(\mathbf{s})\right)-\mathbb{E}_{\mathbf{s}\sim
d^{\pi_{\beta}}(\mathbf{s})}[V^{\hat{\pi}^{k}}(\mathbf{s})]\right)-\tau\right]+\mathcal{E}(Q,\hat{\mathcal{B}}^{\pi}\hat{Q}_{\theta}^{k})+\mathcal{C}(Q).$
(25)

We name this variant of PessORL as PessORL-uniform. We evaluate the variant
PessORL-uniform on two D4RL MuJoCo environments, and compare its performance
to the original PessORL algorithm, CQL, BEAR, and BC based on the average
returns over three random seeds. In Fig. 3, we show the learning curves and
the value gap $\Delta_{k}$ in hopper-medium-v0 and walker2d-medium-v0. The
value gap
$\Delta_{k}=\max_{\mathbf{s}\in\mathcal{S}}[V(\mathbf{s})]-\mathbb{E}_{\mathbf{s}\sim\mathcal{D}}[V(\mathbf{s})]$
follows the same definition in Sec. 6.2, which evaluates whether a method can
assign high values at the states in the training data and low values at the
out-of-distribution states.

In Fig. 3(a) and (c), we can see that the average return of PessORL-uniform is
lower than those of CQL and PessORL. Fig. 3(b) and (d) show that the value
function learned by PessORL-uniform is either not pessimistic enough or too
pessimistic, causing the average return to be lower than the other two rivals.
We believe the reason is that a uniform distribution in PessORL-uniform does
not discriminate between OOD states and in-distribution states, so the
objective function in Eqn. 25 works differently from the original one in
PessORL. Eqn. 25 increases the values at in-distribution states, instead of
penalizing the values at OOD states as before. This mechanism cannot guarantee
an accurate penalization on most OOD states, so we observe different gaps
$\Delta_{k}$ in different environments.

In conclusion, constructing $d^{\phi}(\mathbf{s})$ via a uniform distribution
leads to worse performance, but it could be a cheap alternative in terms of
computational cost.

Figure 3: (a) and (c): The learning curves in hopper-medium-v0 and
walker2d-medium-v0, respectively. (b) and (d): The value gap $\Delta_{k}$ in
hopper-medium-v0 and walker2d-medium-v0, respectively.

###  C.2 What if an uncertainty term is directly subtracted from the learned
Q-function?

In Sec. 1 and Sec. 3.2, we discussed two main categories of method to obtain
pessimistic value functions. Besides adding a regularization term in policy
evaluation step as in the proposed PessORL, we can also improve the policy by
a pessimistic estimate of Q-function. This pessimistic Q-function can be
obtained by directly subtracting an uncertainty term from the learned value
function, i.e.,
$\hat{Q}_{\theta}^{c}(\mathbf{s},\mathbf{a})=\hat{Q}_{\theta}^{k}(\mathbf{s},\mathbf{a})-\beta\text{Unc}(\mathbf{s},\mathbf{a})$,
where we use the superscript $c$ to denote a conservative Q-function, and
$\beta$ is a trade-off factor that makes the scale of the Q-function and the
uncertainty term comparable. In this section, we first introduce two variants
of the proposed PessORL algorithm, named PessORL-unc and PessORL-OPIQ, in
which we used the aforementioned pessimistic Q-function to improve the policy.
Then we compare the variants PessORL-unc and PessORL-OPIQ to the original
PessORL, and discuss why we choose to obtain a pessimistic Q-function via
adding a regularization term in policy evaluation step instead of directly
subtracting an uncertainty term from the original learned value function.

We first introduce a variant of our algorithm, named PessORL-unc, in which the
additional regularization term in the original PessORL policy evaluation step
is removed. The policy evaluation step in PessORL-unc then becomes as follows:

$\displaystyle\min_{Q}\mathcal{E}(Q,\hat{B}^{\pi}\hat{Q}_{\theta}^{k})+\mathcal{C}(Q).$
(26)

Actually, Eqn. 26 is the same as the policy evaluation step in CQL. In the
ablation studies, we use this optimization problem to learn a Q-function
first, and then we directly subtract an uncertainty term from the learned
Q-function to get the final Conservative Q-function to be used in the policy
improvement step:

$\displaystyle\hat{\pi}_{k+1}\leftarrow\arg\max_{\pi}\mathbb{E}_{\mathbf{s}\sim\mathcal{S},\mathbf{a}\sim\pi(\mathbf{a}|\mathbf{s})}\left[\hat{Q}_{\theta}^{k+1}(\mathbf{s},\mathbf{a})-\beta\text{Unc}(\mathbf{s},\mathbf{a})\right],$
(27)

where the uncertainty term $\text{Unc}(\mathbf{s},\mathbf{a})$ is similar to
the one in the original PessORL, but we no longer take the expectation over
the action. Therefore, it becomes
$\text{Unc}(\mathbf{s},\mathbf{a})=\frac{1}{n}\sum_{i=1}^{n}\left(\hat{f}_{\phi_{i}}(\mathbf{s},\mathbf{a})-\bar{f}_{\phi}(\mathbf{s},\mathbf{a})\right)^{2}$.
This term evaluates the uncertainty of the dynamics model about a state-action
pair. If the sampled state is not in the training dataset, the uncertainty
about it will be larger than those in the training data. Therefore, the
Q-function is constrained to be lower at out-of-distribution states in this
way.

Second, we introduce the variant PessORL-OPIQ. It is inspired by the work in
[5], which uses a pessimistic initialization and an optimistic component on
the Q-function. Since in the offline settings we need a pessimistic component
in the Q-function, we set the PessORL-OPIQ uncertainty term
$\text{Unc}(\mathbf{s},\mathbf{a})$ to be the opposite of the optimistic
component in OPIQ, i.e.,
$\text{Unc}(\mathbf{s},\mathbf{a})=-\dfrac{C_{\text{action}}}{(N(\mathbf{s},\mathbf{a})+1)^{M}}$,
where $C_{\text{action}}$ and $M$ are hyperparameters in OPIQ, and
$N(\mathbf{s},\mathbf{a})$ is the pseudo count of the state-action pair
$(\mathbf{s},\mathbf{a})$. Here, we use the continuous version of the OPIQ to
obtain state-action counts. We adopt the pessimistic initialization from the
OPIQ and update the Q function via similar policy evaluation step in Eqn. 26,
but with an PessORL-OPIQ uncertainty term.

We evaluate the variants PessORL-unc and PessORL-OPIQ on two D4RL MuJoCo
environments, and compare their performance to the original algorithm PessORL,
CQL, BEAR, and BC based on the average returns on three random seeds. From
Fig. 3(a) and (c), we can see that the variants PessORL-unc and PessORL-OPIQ
both converge to similar returns which are lower than CQL and the original
PessORL. Actually, the performance of these two variants are close to each
other. We believe the reason is that they both require a super accurate
uncertainty estimation and a stringent trade-off factor $\beta$. A rough
uncertainty estimation may sometimes be harmful to the performance. As we
discussed in Sec. 6.2, our uncertainty estimation method based on bootstrapped
dynamics models still cannot guarantee an extremely precise estimation.
Therefore, directly subtracting the uncertainty term from the learned
Q-function to obtain a conservative Q-function may cause the algorithm to
perform poorly. On the other side, the original PessORL mitigates the
requirement of an accurate uncertainty estimation method because of the
additional regularization term in Eqn. 7. We also noticed that PessORL-unc and
PessORL-OPIQ still outperform the BEAR algorithm. The reason is that we
implement PessORL-unc and PessORL-OPIQ on top of CQL, which is a strong
offline RL method, so we can attribute most of their good performance to CQL.

From Fig. 3(b) and (d), we can see that PessORL-unc maintains a value gap that
is among the highest. PessORL-OPIQ is not pessimistic enough as shown in Fig.
3(b), but is too pessimistic as shown in Fig. 3(d). This indicates that they
cannot effectively control the gap and thus cannot assign lower values to out-
of-distribution states. The original PessORL algorithm can successfully
maintain a value gap that is close to zero, indicating that it shape the value
function to be the desired shape.

##  Appendix D Generalization to Real Robots

Figure 4: Screen shots of Adroit tasks. (a) Door; (b) Relocate; (c) Pen; (d)
Hammer.

Although the Adroit environments are robotic manipulation simulations, they
are considered to be complex enough so that the performance of an offline RL
method on these tasks can be viewed as a strong evidence of how the
performance will be on real robots. There are actually prior works [2] that
use Adroit environments to demonstrate the ability of RL algorithms to adapt
to complex tasks. The Adroit environments, as shown in Fig. 4, contains four
challenging dexterous robot manipulation tasks, which include controlling a
24-DoF simulated manipulator to twirl a pen, open a door, hammer a nail, and
relocate a ball. The simulator of Adroit environments provides carefully
modeled kinematics, dynamics, and sensing details of the physical hardware to
encourage physical realism. The observations contain joint angles, position
and orientations of the hand, the object and the target. The actions include
the desired position of hand joints. These are all considered to be highly
realistic. Therefore, the performance of our proposed PessORL on the Adroit
domain compared to other offline RL methods can indicate a good evidence of
how it will behave when transferred to real robots.

Besides, our proposed method PessORL matches the simulation results of prior
methods that have been demonstrated to work on real robots. Singh et al. [3]
showed that CQL can chain behaviors from data and the learned policy can work
on a real robot WidowX. From Fig. 1, Fig. 2, and Tab. 1, we can see that
PessORL achieves similar or higher performances on all three domains.
Therefore, we believe our proposed method should not be too hard to achieve
good performance on real robots.

Furthermore, a big advantage of offline reinforcement learning methods is that
unlike online RL methods, they are designed to learn policies from pure data
and then can be deployed to real robots. Learning directly from previously
collected data can dramatically reduce the safety risk in the learning process
in safe-critical tasks, such as robotic manipulation and autonomous driving.
Actually, it can be a major block for online reinforcement learning to be
deployed on real-world scenarios, because online interaction can be
impractical in many settings. We show the performance of our proposed PessORL
algorithm learned from human demonstrations in Sec. 6. These experiments align
with the motivation of developing offline reinforcement learning methods, and
we believe they can provide a good evidence of the transfer-ability of our
method to real-robots.

## References

[1] A. Kumar, A. Zhou, G. Tucker, and S.Levine. Conservative q-learning for
offline reinforcement learning. arXiv preprint arXiv:2006.04779, 2020.

[2] A. Rajeswaran, V. Kumar, A. Gupta, G. Vezzani, J. Schulman, E. Todorov,
and S. Levine. Learning complex dexterous manipulation with deep reinforcement
learning and demonstrations. arXiv preprint arXiv:1709.10087, 2017.

[3] A. Singh, A.Yu, J. Yang, J. Zhang, A. Kumar, and S. Levine. Cog:
Connecting new skills to past experience with offline reinforcement learning.
arXiv preprint arXiv:2010.14500, 2020.

[4] Smith, Trey, and Reid Simmons. Point-based POMDP algorithms: Improved
analysis and implementation. arXiv preprint arXiv:1207.1412, 2012.

[5] Rashid, Tabish, et al. Optimistic exploration even with a pessimistic
initialisation. arXiv preprint arXiv:2002.12174, 2020.