# Regularized Behavior Value Estimation

Caglar Gulcehre  Sergio Gómez Colmenarejo  Ziyu Wang  Jakub Sygnowski  Thomas
Paine  Konrad Żołna  Yutian Chen  Matthew Hoffman  Razvan Pascanu  Nando de
Freitas

# Appendix

Caglar Gulcehre  Sergio Gómez Colmenarejo  Ziyu Wang  Jakub Sygnowski  Thomas
Paine  Konrad Żołna  Yutian Chen  Matthew Hoffman  Razvan Pascanu  Nando de
Freitas

###### Abstract

Offline reinforcement learning restricts the learning process to rely only on
logged-data without access to an environment. While this enables real-world
applications, it also poses unique challenges. One important challenge is
dealing with errors caused by the over-estimation of values for state-action
pairs not well-covered by the training data. Due to bootstrapping, these
errors get amplified during training and can lead to divergence, thereby
crippling learning. To overcome this challenge, we introduce Regularized
Behavior Value Estimation ($\mathtt{R}$-$\mathtt{BVE}$). Unlike most
approaches, which use policy improvement during training,
$\mathtt{R}$-$\mathtt{BVE}$ estimates the value of the behavior policy during
training and only performs policy improvement at deployment time. Further,
$\mathtt{R}$-$\mathtt{BVE}$ uses a ranking regularisation term that favours
actions in the dataset that lead to successful outcomes. We provide ample
empirical evidence of $\mathtt{R}$-$\mathtt{BVE}$’s effectiveness, including
state-of-the-art performance on the RL Unplugged ATARI dataset. We also test
$\mathtt{R}$-$\mathtt{BVE}$ on new datasets, from bsuite and a challenging
DeepMind Lab task, and show that $\mathtt{R}$-$\mathtt{BVE}$ outperforms other
state-of-the-art discrete control offline RL methods.

Machine Learning

##  1 Introduction

Deep Reinforcement Learning (deep RL) is dominated by the online paradigm,
where agents must interact with the environment repeatedly to explore and
learn. This paradigm has attained considerable success on Atari (Mnih et al.,
2015), Go (Silver et al., 2017), StarCraft II and Dota 2 (Vinyals et al.,
2019; Berner et al., 2019), and robotics (Andrychowicz et al., 2020). However,
the requirements of extensive interaction and exploration make these
algorithms unsuitable and unsafe for many real-world applications. In
contrast, in the offline setting (Fu et al., 2020; Fujimoto et al., 2018;
Gulcehre et al., 2020; Levine et al., 2020), also known as batch RL (Ernst et
al., 2005; Lange et al., 2012), agents learn from a fixed dataset previously
logged by other (possibly unknown) agents. While the offline setting would
enable the application of RL to real-world applications, current algorithms
tend to perform worse than their online counterparts.

Figure 1: In offline settings, policy improvement is risky as it relies on
extrapolating beyond the data. Nevertheless, standard approaches perform many
iterations of policy improvement during training, resulting in extrapolation
error and divergence. In contrast, behavior value estimation (Ours) estimates
the value of the behavior policy, and performs only one step of policy
improvement when the policy is deployed. Even one step of policy improvement
requires extrapolation, so to make this safer we perform ranking
regularization at training time to favour actions in the dataset that lead to
successful outcome over unobserved actions. Our approach performs as well or
better than state-of-the-art offline RL approaches across several domains.

A key difference between online and offline RL is the impact of _over-
estimating_ the value of unobserved actions (see Figure 2). In the online
case, this over-estimation incentivizes agents to explore actions of high
expected reward, thus learning by trial-and-error (Schmidhuber, 1991). After
trying a new action, the agent is able to update its values. In contrast, in
the offline case, the agent learns from a fixed dataset, and hence the agent
does not get the opportunity to interact with the environment to gather new
evidence to correct its values. As a result, the agent can become increasingly
deluded.

To minimize the harm caused by over-estimation, we propose a new offline RL
method that we refer to as _Regularized Behavior Value Estimation_
($\mathtt{R}$-$\mathtt{BVE}$). For clarity of presentation, we introduce the
ideas of _behaviour value estimation_ and _ranking regularization_ separately.
We also show in the experiments that our proposed ranking regularization may
be applied to improve deep Q-learning methods.

Behavior value estimation. Intuitively, instead of aiming to estimate the
optimal policy $Q^{\pi^{*}}$, we focus on recovering the value of the
behavioural policy $Q^{\pi_{{\cal B}}}$. This amounts to removing
$\max$-operators during training to prevent over-estimation. Subsequently, to
improve upon the behavioral policy, we conduct a single step of policy
improvement at deployment time. We found this simple method to work
surprisingly well on the offline RL tasks we tried.

Ranking regularization. Behavior value estimation is however not enough to
overcome the over-estimation problem. For this reason, we introduce a
$\max$-margin regularizer that encourages actions from rewarding episodes to
be ranked higher than any other actions. Intuitively, this regularizer pushes
down the value of all unobserved state-action pairs, thereby minimizing the
chance of a greedy policy selecting actions under-represented in the dataset.
Employing this regularizer during training minimizes the over-estimation
impact of the $\max$-operator when used in combination with Q-learning.
However, it also minimizes the impact of the $\max$-operator at deployment
time, thus making the regularizer useful for behaviour value estimation. The
ranking regularizer can further push down the value of actions that do not
appear in rewarding sequences, allowing the learned value function to improve
upon the one corresponding to the behaviour policy.

We evaluate our approach on the open-source RL Unplugged Atari dataset
(Gulcehre et al., 2020), where we show that $\mathtt{R}$-$\mathtt{BVE}$
outperforms other offline RL methods. We show that $\mathtt{R}$-$\mathtt{BVE}$
performs better on two more datasets: bsuite (Osband et al., 2019) and
partially observable DeepMind Lab environments (Beattie et al., 2016)111We
released these datasets under RL Unplugged github repo.. We provide careful
ablations and analyses that provide insights into our proposed method and
existing offline RL algorithms. Empirically, we find out that
$\mathtt{R}$-$\mathtt{BVE}$ reduces the over-estimation from extrapolation by
orders of magnitude, and improves sample-efficiency significantly (see Figures
6 and 7).

##  2 Background and Problem Statement

We consider a Markov Decision Process $(\mathcal{S},{\cal
A},P,R,{\rho_{0}},\gamma)$, where $\mathcal{S}$ is the set of all possible
states and ${\cal A}$ for all possible actions. For simplicity, we focus on
discrete actions, though our methods can be extended to continuous actions. An
agent starts in state $s_{0}\sim{\rho_{0}}(\cdot)$ where ${\rho_{0}}(\cdot)$
is a distribution over ${\cal S}$ and takes actions according to its policy
$a\sim\pi(\cdot|s)$, $a\in{\cal A}$, when in state $s$. Then it observes a new
state $s^{\prime}$ and reward $r$ according to the transition distribution
$P(s^{\prime}|s,a)$ and reward function $r(s,a)$.

The state-action value function $Q^{\pi}$ describes the expected discounted
return starting from state $s$ and action $a$ and following $\pi$ afterwards:

$\displaystyle Q^{\pi}(s,a)$
$\displaystyle=\mathbb{E}\Bigg{[}\sum_{t=0}\gamma^{t}r(s_{t},a_{t})\Bigg{]},$
(1) $\displaystyle s_{0}=s,a_{0}$ $\displaystyle=a,s_{t}\sim
P(\cdot|s_{t-1},a_{t-1}),a_{t}\sim\pi(\cdot|{\bm{s}}_{t}),$ (2)

and $V^{\pi}(s)=\mathbb{E}_{a\sim\pi(\cdot|{\bm{s}})}{[Q^{\pi}(s,a)]}$ is the
state value function. In this work, we are particularly interested in the
scenario where neural networks are used as function approximators to estimate
these functions due to their ability to scale and work on complex tasks.

The optimal policy $\pi^{*}$, which we aim to discover through RL, is one that
maximizes the expected cumulative discounted rewards, or _expected returns_
such that $Q^{\pi^{*}}(s,a)\geq Q^{\pi}(s,a)\;\forall s,a,\pi$. For notational
simplicity, we denote the policy used to generate an offline dataset as
$\pi_{{\cal B}}$. For a state $s$ in an offline dataset, we use
$\hat{V}^{\pi_{{\cal B}}}(s)$ to denote the empirical estimate of
$V^{\pi_{{\cal B}}}(s)$ computed by summing future discounted rewards over the
trajectory that $s$ is part of.

RL algorithms can be broadly categorized as either _on-policy_ or _off-
policy_. Whereas on-policy algorithms update their current policy based on
data generated by itself, off-policy approaches can take advantage of data
generated by other policies. Algorithms in the mold of fitted Q-iteration make
up many of the most popular approaches to deep off-policy RL (Mnih et al.,
2015; Lillicrap et al., 2015; Haarnoja et al., 2018). This class of algorithms
learns a $Q$ function by minimizing the Temporal Difference (TD) error. To
increase stability and sample efficiency, experience replay is typically
employed. For example, DQN (Mnih et al., 2015) minimizes the following loss
function with respect to $\theta$:

${\cal L}_{\theta^{\prime}}(\theta)=\mathbb{E}_{(s,a,r,s^{\prime})\sim{\cal
D}}[(Q_{\theta}(s,a)-r-\gamma\max_{a^{\prime}}Q_{\theta^{\prime}}(s^{\prime},a^{\prime}))^{2}],$
(3)

where $Q_{\theta^{\prime}}(s^{\prime},a^{\prime})$ is a slowly changing target
network, and ${\cal D}$ is the replay dataset generated by a behaviour policy.
Typically, for off-policy algorithms the behavior policy is periodically
updated to remain close to the policy being optimized. A deterministic policy
can be derived by defining $\pi(s)=\operatorname*{arg\,max}_{a}Q(s,a)$.
Various extensions have been proposed, including variants with continuous
actions (Lillicrap et al., 2015; Haarnoja et al., 2018), distributional
critics (Bellemare et al., 2017), prioritized replays (Schaul et al., 2015),
and n-step returns (Kapturowski et al., 2019; Barth-Maron et al., 2018; Hessel
et al., 2017).

In the offline RL setting, agents learn from fixed datasets generated via
other processes, thus rendering off-policy RL algorithms particularly
pertinent. Many existing offline RL algorithms adopt variants of Equation (3)
to learn value functions; e.g. (Agarwal et al., 2019b). Offline RL, however,
is different from off-policy learning in the online setting. The offline RL
datasets are usually finite and fixed, and does not track the policy being
learned. When a policy moves towards a part of the state space not covered by
the behavior policy(s), for example, one cannot effectively learn the value
function. We will explore this in more detail in the next subsection.

Figure 2: Over-estimation from extrapolation. $Q$ is the real value of an
action $a$ in a state $s$, and $Q_{\theta}$ is the estimated value using
function approximation. In this example $a_{1}$ is observed in the dataset
while $a_{2}$ and $a_{3}$ unobserved. Applying the max operator would cause us
to choose $a_{3}$. We refer to this phenomenon as over-estimation from
extrapolation. While in online RL it leads to optimistic exploration followed
by correction, in the offline case it results in growing value estimates and
divergence. Regularized Behavior Value Estimation is designed to avoid over-
estimation from extrapolation during training and deployment.

###  2.1 Extrapolation and over-estimation in offline RL

In the offline setting, when considering all possible actions for the next
state in Equation (3), some of the actions will be _out-of-distribution_
(OOD). This is because some actions are never picked in that state by the
behavior policy used to construct the training set. That is, the state-action
pairs are not present in the dataset. In such circumstances, we have to rely
on the current Q-network to extrapolate beyond the training data, resulting in
extrapolation errors when evaluating the loss222Neural networks trained by
gradient descent typically struggle to fit under-represented modes of the
data. Hence this argument also holds for rarely observed state-action pairs..
Importantly, this extrapolation can lead to value over-estimation, as
explained below.

Value over-estimation (see Figure 2) happens when the function approximator
predicts a larger value than the ground truth. In short, taking the max over
actions of several Q-network predictions, as in Equation (3), leads to
overconfident estimates of the true value of the state that are propagated in
the learning process.

For OOD actions, we depend on extrapolated values provided by the model
$Q_{\theta^{\prime}}$. We focus on neural networks as the function
approximators. While neural networks are efficient learners, they will produce
erroneous predictions on unobserved state-action pairs. Sometimes, these will
be arbitrary high. These errors will be propagated in the value of other
states via bootstrapping. Due to the smoothness of neural networks, by
increasing the value of actions in the OOD state-action’s neighborhood, the
overestimated value itself might increase, creating a vicious loop. We remark
that, in such a scenario, typical gradient descent optimization can diverge
and escape towards infinity. See Appendix A for a formal statement and proof
on this statement, though similar observations have been made before by
Fujimoto et al. (2019b) and Achiam et al. (2019). When the agent overestimates
some state-action pairs in the online setting, they will be chosen more often.
This leads to optimistic exploration, which happens both in the on-policy and
off-policy setting. The distinction is that the behavior policy trails the
learned one instead of being the same for the latter. The online agent would
then act, collect data, and correct extrapolation errors. This form of self-
correction is absent in the offline setting, and due to the over-estimation
from extrapolation, the results can be catastrophic. Additionally, OOD
actions’ impact becomes larger in the low data regime, where the chance of
observing OOD actions is greater and neural networks are more prone to
extrapolation errors.

We make a final note on the hardness of the setup we are interested in. To
solve our problems, we require powerful function approximators that make
analytical studies difficult without strong assumptions that might not hold in
practice. Additionally, the tasks are complex large-scale tasks, which can
make assumptions on the coverage of the state-action space by the training set
improbable or at least impossible to assess. Therefore we mainly rely on
empirical evidence to motivate our approach.

##  3 Regularized Behavior Value Estimation

###  3.1 Behavior Value Estimation ($\mathtt{BVE}$)

One particular starting point to deal with the vicious loop caused by over-
estimation could be simply to phrase the problem as a supervised one, where
given the data, a neural network is trained to produce for a given state the
observed action. For the discrete action setting, the one we are focusing on,
this is a well defined classification problem that will mimic the behaviour
policy used to collect the data.

However, offline RL aims to improve upon the behavior policy. To do so, many
algorithms borrow machinery from the online scenario, as for example, Equation
(3) which through the $\max$-operator tries to improve the current policy by
greedily picking the action with the largest estimated value. The repeated
application of this improvement step can cause learning to diverge in the
offline regime, as discussed earlier. Therefore, to break this cycle, we
propose to limit the number of improvement steps being done, bounding the
impact of over-estimation. In particular, given that policy iteration
algorithms typically do not require more than a few steps to converge to
optimal policy (Lagoudakis and Parr, 2003; Sutton and Barto, 2018, Chapter
4.3), we focus on the extreme scenario where we are allowed to take a single
improvement step.

We start by drawing inspiration from the SARSA update (Rummery and Niranjan,
1994; Van Seijen et al., 2009). SARSA relies on the consecutive application of
a _policy evaluation_ step, followed by a _policy improvement_ step. The
policy evaluation step is described by the update below:

${\cal
L}_{\theta^{\prime}}(\theta)=\mathbb{E}_{(s,a,r,s^{\prime},a^{\prime})\sim\pi}(Q_{\theta}(s,a)-r-\gamma
Q_{\theta^{\prime}}(s^{\prime},a^{\prime}))^{2}.$ (4)

The policy improvement step is _implicit_ by defining the policy $\pi$ used to
collect data greedily in terms of $Q_{\theta}$. Therefore we can remove the
policy improvement step by simply eliminating this dependency of $\pi$ on
$Q_{\theta}$. We propose _Behaviour Value Estimation_ as applying Equation (4)
on transitions $(s,a,r,s^{\prime},a^{\prime})$ collected by the behaviour
policy, leading to a Q-function reflecting the value of this policy.

Finally, we take a single _policy improvement_ step at deployment by acting
greedily with respect to $Q_{\theta}$, namely
$\pi(s)=\operatorname*{arg\,max}_{a}Q_{\theta}(s,a)$. A single improvement
step can not guarantee convergence to an optimal behaviour in general.
However, our approach will effectively bound the impact of extrapolation
errors and empirically provides significant improvement on the tasks
considered, see for example Figure 8. This is particularly true in the low
data regime where neural networks are less reliable and repeated policy
improvement steps are prone to lead to an amplified over-estimation of OOD
actions, as observed empirically in Figure 6. To highlight the efficiency of a
single improvement step, we provide through the lemmas in Appendix B some
sufficient conditions for a single improvement step to lead to optimal
behaviour.

###  3.2 Ranking regularization ($\mathtt{R}$-)

Behaviour Value Estimation effectively reduces over-estimation during training
by avoiding policy improvement steps but it also avoids estimating the $Q$
values of OOD actions and focuses on recovering the $Q$ values of the observed
data under the behaviour policy. In contrast to the tabular case, where all
OOD actions will have a default value of $0$, neural networks will extrapolate
based on the observed data.

We choose to learn a more conservative $Q$ function that avoids picking
actions not seen during training to mitigate the impact of the extrapolation.
To this end, here, we simply regularize the output of the Q-network to rank
the observed actions higher than the OOD ones for successful episodes.

This ranking strategy can be formulated with a hinge-loss (Chen et al., 2009;
Burges et al., 2005). We adopt the squared-hinge loss which is commonly used
for RankSVM (Chapelle and Keerthi, 2010). Given a transition from the dataset
$\left(s_{t},a_{t}\right)$ we introduce the following loss:

$\mathcal{C}(\theta)=\sum_{i=0,i\neq t}^{|{\cal
A}|}\max\left(Q_{\theta}(s_{t},a_{i})-Q_{\theta}(s_{t},a_{t})+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\nu},0\right)^{2},$
(5)

which states that if the value of any action $a_{i}$ is higher by a a certain
margin than the value of the dataset action $a_{t}$, then the value function
needs to be adjusted.

Previously, hinge losses were used for regularization in RL, but with
different goals from ours (Su et al., 2020; Pohlen et al., 2018).

Blindly applying this ranking loss on suboptimal data can have an undesirable
effect. This ranking loss mostly focuses on the frequency of an action in the
dataset, promoting frequent actions to have larger value than infrequent ones.
For suboptimal behaviour policies is likely that frequency does not correlate
with high values.

One practical answer to this problem is to filter out trajectories that are
not sufficiently rewarding, reducing the frequency of state-actions that are
not relevant for good behaviour. We adopt a soft filtering approach, which
simply re-weights each transition with the normalized value of the trajectory:

$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathtt{w}(s)}$
$\displaystyle=\exp((\hat{V}^{\pi_{{\cal B}}}(s)-\mathbb{E}_{s\sim{\cal
D}}[\hat{V}^{\pi_{{\cal
B}}}(s)])/{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}\beta})$
(6) $\displaystyle\mathcal{C}(\theta)$
$\displaystyle={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathtt{w}}(s)\sum_{i=0,i\neq
t}^{|{\cal
A}|}\max\left(Q_{\theta}(s,a_{i})-Q_{\theta}(s,a_{t})+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\nu},0\right)^{2},$

where again $\hat{V}^{\pi_{{\cal B}}}(s)$ denotes the empirical estimate of
$V^{\pi_{{\cal B}}}(s)$ computed by summing future discounted rewards over the
trajectory that $s$ is part of. The expectation $\mathbb{E}_{s\sim{\cal
D}}[\hat{V}^{\pi_{{\cal B}}}(s)]$ is estimated with an average over mini-
batches.

The weight
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathtt{w}(s)}$
can be thought of as a success filter. The formulation of this filtering
mechanism is based on the advantage based filtering mechanism used for the
policy in CRR (Wang et al., 2020). In our preliminary experiments, we tried
both binary filtering with an indicator function and advantage based
filtering, but we found that the filtering mechanism introduced above works
the best on discrete control algorithms we study here. In the online regime,
the filter amplifies the choice of actions in trajectories that fair better
than expected, behaving similarly to a policy improvement step. In particular,
our loss is closely related to Ranking Policy Gradient (Lin and Zhou, 2020).
While the same machinery of this work cannot be used to prove convergence of
our loss due to the offline character of our regime, it provides intuition of
why the filter biases the learning in the right direction. Compared with a
typical policy improvement step, this loss, however, also ensures that OOD
actions (and actions in non-rewarding sequences) rank lower in the policy.

The ranking loss can be successfully combined with Q-learning, which we will
refer as $\mathtt{R}$-$\mathtt{DQN}$ or, better with behaviour value
estimation, $\mathtt{R}$-$\mathtt{BVE}$. It is due to this reweighting that
$\mathtt{R}$-$\mathtt{BVE}$ can not only further mitigate over-estimation
compared to $\mathtt{BVE}$ but it can also improve on the behaviour policy
during training. In all our experiments, we fixed $\beta$ to be $0.5$, a
hyperparameter value borrowed from CRR (Wang et al., 2020).

##  4 Related work

Early examples of offline/batch RL include least-squares temporal difference
methods (Bradtke and Barto, 1996; Lagoudakis and Parr, 2003) and fitted Q
iteration (Ernst et al., 2005; Riedmiller, 2005). More recent offline RL
approaches fall into three broad categories: 1) policy-constraint approaches
regularize the learned policy to stay close to the behavior policy either
explicitly or implicitly (Fujimoto et al., 2019b; Kumar et al., 2019; Jaques
et al., 2019; Siegel et al., 2020; Wang et al., 2020; Ghasemipour et al.,
2020), 2) value-based approaches lower value estimates for unseen state-
actions pairs, either through regularization or uncertainty (Kumar et al.,
2020; Agarwal et al., 2019a). 3) model-based approaches similarly lower reward
estimates for unseen state-action pairs (Yu et al., 2020; Kidambi et al.,
2020).

The above methods perform policy improvement during training, and use the
methods described above to mitigate extrapolation error and divergence. Our
approach is fundamentally different. We perform no policy improvement during
training, instead estimating the value of the behavior policy. This approach
is related to policy-constraint methods but has three advantages: 1) we do not
need to estimate a behavior policy, 2) we do not constrain our policy to be
similar to the behavior policy, which may be a poor constraint when the
behavior policy is a mixture of many policies some of which are sub-optimal
and 3) we are guaranteed to avoid extrapolation errors during training.
Additionally, our method uses value-based regularization but only to mitigate
extrapolation error when we deploy our policy. Our value-based regularization
is most similar to regularization used in CQL (Kumar et al., 2020). There are
two main differences 1) our regularization is weighted by the success of the
trajectory and 2) we use a max-margin ranking loss. We find these work better
in practice.

##  5 Experiments

We investigate the performance of offline RL algorithms with discrete actions
across three domains: bsuite, Atari, and DeepMind Lab. The main question we
want to answer is: how do algorithms perform when there is low coverage of
state-action pairs? In that context, we study multiple factors that affect
coverage including dataset size (see Figure 6 and 7), noise (see Figure 3 and
9), and partial observability (Figure 8).

We compare our proposed model $\mathtt{R}$-$\mathtt{BVE}$ (Regularized
Behavior Value Estimation), its ablations $\mathtt{BVE}$ (Behavior Value
Estimation) and $\mathtt{R}$-$\mathtt{DQN}$ (Regularized Deep Q-learning), and
several offline reinforcement learning baselines. For the Atari domain we used
the RL Unplugged Atari benchmark (Gulcehre et al., 2020). We also create
additional datasets using bsuite to have fast diagnostic tests, and DeepMind
Lab to have a challenging partially observable domain. We are working to open-
source these datasets. The details of the datasets are provided in Appendix D.
In all our experiments, for our CQL baseline, we used CQL($\mathcal{H}$) with
a fixed $\alpha$ as prescribed in (Kumar et al., 2020) for Atari.

Overall, our method has two hyperparameters that we tuned:
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\nu}$ for
the margin, and the regularization coefficient $\lambda$ for the ranking
regularization. Our method seems to be quite robust to those values. We tuned
$\lambda$ only on Atari, and found out that $0.005$ worked best on nine Atari
online policy selection games. We used this value for all other tasks and
games. We fixed
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\nu}=0.05$
for both Atari and bsuite without any hyperparameter tuning. In particular,
these hyperparameters fared well for the offline policy selection games. This
provides an evidence that, for a real-world application, one might be able to
tune the regularization hyperparameters in a simulated version of the
environment and deploy them in the setting of interest. However, on DeepMind
Lab, based on a coarse grid for the margin hyperparameter
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\nu}\in\\{0.5,0.05\\}$,
we found some variation for the optimal value. On our bsuite and DeepMind Lab
plots, we report median and standard error bars across different seeds. On
Atari, as accustomed in the literature, we only report median across different
Atari games.

###  5.1 bsuite Experiments

bsuite (Osband et al., 2019) is a proposed benchmark designed to highlight key
aspects of an agent’s scalability such as exploration, memory or credit
assignment. We generated low-coverage offline RL datasets for catch,
mountain_car and cartpole by recording the experiences of an online agent
during training, as described by (Agarwal et al., 2019a), and then subsampling
it (see Appendix D.1 for details.) We generated two versions of datasets for
each task: stochastic vs. deterministic. The stochastic data is obtained by
injecting noise into transitions by replacing an agent’s actions with a random
action with probability $\epsilon=0.25$.

On bsuite experiments, our goals are: firstly to have a computationally cheap
setting to compare our proposed methods against the state-of-the-art baselines
on diagnostic tasks and, secondly, verify that our method is robust against
the stochasticity in the transitions.

Figure 3: Bsuite Experiments. bsuite results on three environments without,
and with noise injected into the actions in the dataset. The proposed method,
$\mathtt{R}$-$\mathtt{BVE}$, outperforms all the baselines on cartpole.
Methods implementing a form of behavior constraining (BCQ, CQL and our methods
$\mathtt{R}$-$\mathtt{BVE}$ and $\mathtt{R}$-$\mathtt{DQN}$) excel on catch
(with noise), stressing its importance.

In Figure 3, we compare the effectiveness of $\mathtt{R}$-$\mathtt{BVE}$ and
$\mathtt{R}$-$\mathtt{DQN}$ against four baselines: DDQN (Hasselt, 2010),
CQL($\mathcal{H}$) (Kumar et al., 2020), REM (Agarwal et al., 2019a) and BCQ
(Fujimoto et al., 2018). On the harder dataset (cartpole),
$\mathtt{R}$-$\mathtt{BVE}$ and $\mathtt{R}$-$\mathtt{DQN}$, our proposed
methods, outperform all other approaches on the noisy datasets showing the
efficiency and robustness of our approach. Two other methods, REM and CQL,
also perform relatively well in the noisy setting. The results for catch are
similar, with the exception that BCQ also has better normalized score which
re-emphasises the importance of restricting behavior to stay close to the
observed data. On mountain_car, all methods almost reaches the performance of
the expert generated the dataset on the noisy dataset. However, DDQN performed
poorly when there is no noise in the transitions. We think, this might be
because the noise injected into the dataset although increases stochasticity,
it also increases the (state, action)-coverage of the dataset. Overall,
$\mathtt{R}$-$\mathtt{BVE}$ and $\mathtt{R}$-$\mathtt{DQN}$ seem to be less
effected by this noise injected.

###  5.2 Atari Experiments

Atari is an established online RL benchmark (Bellemare et al., 2013), which
has recently attracted the attention of the offline RL community (Agarwal et
al., 2019a; Fujimoto et al., 2019a). Here, we used the experimental protocol
and datasets from the RL Unplugged Atari benchmark (Gulcehre et al., 2020). We
report the median normalized score across the Atari games as prescribed by
(Gulcehre et al., 2020).

Figure 4: Atari offline policy selection games results. We compare our
proposed $\mathtt{R}$-$\mathtt{BVE}$ against other recent state-of-the-art
offline RL algorithms with hyperparameters tuned only on offline policy
selection games. Our methods prove to be the best.

In Figure 4, we show that $\mathtt{R}$-$\mathtt{BVE}$ outperforms all
baselines reported in the RL Unplugged benchmark as well as CQL($\mathcal{H}$)
(Kumar et al., 2020) on offline policy selection games. Both
$\mathtt{R}$-$\mathtt{DQN}$ and $\mathtt{R}$-$\mathtt{BVE}$ outperform other
SOTA offline RL methods. This experiment highlights an important point: on a
large benchmark suite (including 37 Atari games) a single step of policy
improvement is sufficient to outperform several offline RL algorithms
including policy contraint (BCQ), value-based regularization (CQL), and value-
based uncertainty methods (REM, IQN). Though we should note, in this setting
there is enough data for the neural networks to learn reasonable
approximations of the Q-value (exploiting the structure of the state space to
extrapolate reasonably for unobserved state-action pairs.) This figure also
highlights the robustness of ranking regularization to its hyperparameters
since we did not do any hyperparameter search on the offline policy selection
games.

Figure 5: Atari ablations (online policy selection games). We compare
$\mathtt{BVE}$, DDQN and Monte Carlo Learning, and ranking regularization in
RLU Atari dataset for online policy selection games. $\mathtt{BVE}$ and DDQN
attain similar median episodic returns, but learning with Monte Carlo returns
performs poorly. We found that the most significant improvement from the
ranking regularization term ($\mathtt{R}$-$\mathtt{DQN}$ and
$\mathtt{R}$-$\mathtt{BVE}$). Although the combination of ranking
regularization and $\mathtt{BVE}$ performs the best.

##### Ablation Experiments on Atari

We ablate two different aspects of our algorithm on nine online policy
selection games from RL Unplugged Atari suite: i) the choice of TD backup
updates (Q-learning or behavior value estimation), ii) the effect of ranking
regularization. We show the ablation of those three components in Figure 5. We
observed the largest improvement when using ranking regularization. In
general, we found that directly using Monte-Carlo estimation for the value
function (we refer this in our plot as "MC Learning") does not work on Atari.
We also provide results with behavior cloning (BC) (Pomerleau, 1989) and
filtered BC — BC that is only trained on highly rewarding episodes. These are
episodes for whom their episodic return is greater than a thereshold, where we
set this threshold to be the mean of episodic return in the whole dataset. We
showed that BC on the whole dataset works very poorly, but filtered BC works
considerably better. Nevertheless, filtered BC still performs considerably
worse than other offline RL methods such as $\mathtt{BVE}$.

Figure 6: Over-estimation of Q-values. We report median over-estimation error
over online policy selection games on Atari with sub-sampled Atari datasets (%
of dataset). As dataset size decreases DDQN is prone to severe over-
estimation. $\mathtt{R}$-$\mathtt{DQN}$ reduces this to some extent but still
over-estimates severely. Finally, $\mathtt{BVE}$ and
$\mathtt{R}$-$\mathtt{BVE}$ significantly reduce over-estimation.

##### Over-estimation Experiments

One source for over-estimation of Q-learning is the maximization bias
(Hasselt, 2010). In the offline setting, another source, as discussed in
Section 2, is due to extrapolation errors. Double DQN (DDQN by Hasselt (2010))
is supposed to address the first problem, but it is unclear whether it can
address the second. In Figure 6, we show that in the offline setting DDQN
still over-estimates severely when we evaluate the critic’s predictions in the
environment. This suggests the second source, dominates and DDQN does not
address it. In comparison, $\mathtt{R}$-$\mathtt{DQN}$ overestimates
significantly less, highlighting the efficiency of the ranking regularization,
however its performance degrades by many orders of magnitude in the low data
regime. Finally, $\mathtt{BVE}$ and $\mathtt{R}$-$\mathtt{BVE}$ drastically
reduce over-estimation in all settings. In the figure, we compute the over-
estimation error by evaluating the methods in the environment and computing
$\frac{1}{100}\sum_{i=0}^{100}(\max(Q^{\pi}(s,a)-G^{\pi}(s),0))^{2}$ over
$100$ episodes, where $G^{\pi}(s)$ corresponds to the discounted sum of
rewards from state $s$ till the end of episode by following the policy $\pi$.

Figure 7: Sample Efficiency. Normalized scores of DDQN,
$\mathtt{R}$-$\mathtt{DQN}$, $\mathtt{BVE}$ and $\mathtt{R}$-$\mathtt{BVE}$ on
subsets of data from online policy selection games. On the smaller subsets of
the dataset $\mathtt{BVE}$ and $\mathtt{R}$-$\mathtt{BVE}$ performs
comparatively better than DQN and $\mathtt{R}$-$\mathtt{DQN}$. The Q-learning
suffers more since the coverage of the dataset reduces with the subsampling
causing more severe extrapolation error.

##### Robustness Experiments

According to Figure 5, $\mathtt{BVE}$ and Q-learning both have similar
performance on the full dataset, however, in low data regimes, the behavior
value policy considerably outperforms Q-learning (see Figure 7). The poor
performance of DQN and $\mathtt{R}$-$\mathtt{DQN}$ in the lower data regime is
potentially due to the over-estimation that we showed in Figure 6.
Furthermore, in Appendix C.2 (see Figure 14), we investigate the robustness of
$\mathtt{BVE}$ and DDQN with respect to the reward distribution. We found that
the performance of $\mathtt{BVE}$ is more robust than DDQN to variations of
the reward distribution.

Figure 8: DeepMind Lab Results: We compare the performance of different
baselines on challenging DeepMind Lab datasets coming from four different
DeepMind Lab levels. Our method, $\mathtt{R}$-$\mathtt{BVE}$, consistently
performs the best.

###  5.3 DeepMind Lab Experiments

Offline RL research mainly focused on fully observable environments such as
Atari. However, in a complex partially observable environment such as Deepmind
Lab, it is very difficult to obtain good coverage in the dataset even after
collecting billions of transitions. To highlight this, we have generated
datasets by training an online R2D2 agent on DeepMind Lab levels.
Specifically, we have generated datasets for four of the levels:
$\mathtt{explore\\_object\\_rewards\\_many}$,
$\mathtt{explore\\_object\\_rewards\\_few}$, $\mathtt{rooms\\_watermaze}$, and
$\mathtt{rooms\\_select\\_nonmatching\\_object}$. The details of the datasets
are provided in the Appendix D.2.

We compare offline BC, CQL, R2D2, $\mathtt{R}$-$\mathtt{R2D2}$, $\mathtt{BVE}$
and $\mathtt{R}$-$\mathtt{BVE}$ on our DeepMind Lab datasets. We use the same
architecture, so the main difference is in the loss function. To test our
hypothesis that partially observable environments accentuate the coverage
issue we consider the large data regime, using 300M transitions stored during
the online training of R2D2. In Figure 8, we show the performance of each
algorithm on four different levels. Our proposed modifications,
$\mathtt{R}$-$\mathtt{BVE}$ and $\mathtt{BVE}$ outperform other offline RL
approaches on all DeepMind Lab levels. We argue that poor performance of R2D2
in the offline setting is due to the implicit low coverage of the dataset.
Even at 300M transitions do not seem enough, potentially due to the partially
observable nature of the environment as well as its diversity.

##### The importance of coverage in offline RL:

Here, we investigate the effect of coverage on the DeepMind Lab
$\mathtt{seekavoid\\_arena\\_01}$ level on a dataset generated by a fixed
policy. To do so, we generated two datasets. The first relies on a R2D2
snapshot, as the behaviour policy, which we refer to as _Expert Data_. The
second uses a noisy version of this policy, where $75\%$ of decisions are
taken by the R2D2 agent, and the remaining $25\%$ rely on a uniform policy
over actions, referred as _Noisy Expert Data_. Figure 9 depicts the result on
these two datasets. BC outperforms all offline RL approaches on the noiseless
expert dataset. However, introducing the noise into the actions deteriorates
BC’s performance considerably, and $\mathtt{R}$-$\mathtt{BVE}$ outperforms it.
Over all, the episodic returns obtained by offline RL methods either improve
(R2D2, $\mathtt{BVE}$, $\mathtt{R}$-$\mathtt{BVE}$) or stay unaffacted (CQL,
$\mathtt{R}$-$\mathtt{R2D2}$) on the noisy expert data compared to their
performance on the expert data. This is most likely due to the fact that the
noisy expert data provides better coverage. Given that the environment is
deterministic, the expert data follows mostly the optimal trajectory offering
a relative low coverage of the state-action space.

Figure 9: Effect of coverage in the expert demonstrations: Given access to
data from an optimal policy only, BC performs well, where as offline RL
methods struggle due to insufficient state-action coverage. Adding noise to
the policy, in a way simulating the human demonstrations, increases coverage.
In this setting BC performs worse, but R-BVE is able to match the performance
of BC from optimal data.

##  6 Discussion

In this work we investigate the deep offline RL setting with discrete actions.
In such settings, overestimation errors of the neural network approximator get
propagated in the value function through the bootstraping. This can lead to a
cycle, where the overestimation gets amplified with every policy improvement
step, in the worst case scenario leading these values to escape to infinity.
We propose behaviour value estimation $\mathtt{BVE}$ an algorithm that limits
the number of policy improvements steps to one. Empirically, we showed that
this single policy improvement step at deployment is enough for the relatively
complex tasks we have considered.

Behavior value estimation is however not enough to overcome the overestimation
problem. For this reason, we introduce a max-margin regularizer that
encourages actions from rewarding episodes to be ranked higher than any other
actions. This leads to the proposed algorithm $\mathtt{R}$-$\mathtt{BVE}$
which outperforms all the other SOTA offline RL methods we have compared
against for the discrete control on bsuite, RLU Atari and DeepMind Lab tasks.
We note that our algorithm is particularly effective for low data regimes,
where the overestimation issue discussed in this work is acute.

Finally, we have also proposed two new offline RL datasets: (i) DeepMind Lab:
large scale, partially observable environment, (ii) bsuite: small scale, low
data regime. We believe these datasets poses unique characteristics and that
they will be of interest to the community. As future work, we plan to extend
$\mathtt{R}$-$\mathtt{BVE}$ to continuous control and other real-world
applications.

## References

  * Achiam et al. (2019) Joshua Achiam, Ethan Knight, and Pieter Abbeel.  Towards characterizing divergence in deep Q-learning.  _arXiv preprint arXiv:1903.08894_ , 2019.
  * Agarwal et al. (2019a) Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi.  An optimistic perspective on offline reinforcement learning.  2019a.
  * Agarwal et al. (2019b) Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi.  Striving for simplicity in off-policy deep reinforcement learning.  _Preprint arXiv:1907.04543_ , 2019b.
  * Andrychowicz et al. (2020) OpenAI: Marcin Andrychowicz, Bowen Baker, Maciek Chociej, Rafal Jozefowicz, Bob McGrew, Jakub Pachocki, Arthur Petron, Matthias Plappert, Glenn Powell, Alex Ray, et al.  Learning dexterous in-hand manipulation.  _The International Journal of Robotics Research_ , 39(1):3–20, 2020.
  * Barth-Maron et al. (2018) Gabriel Barth-Maron, Matthew W. Hoffman, David Budden, Will Dabney, Dan Horgan, Dhruva TB, Alistair Muldal, Nicolas Heess, and Timothy Lillicrap.  Distributed distributional deterministic policy gradients.  In _International Conference on Learning Representations_ , 2018.
  * Beattie et al. (2016) Charles Beattie, Joel Z Leibo, Denis Teplyashin, Tom Ward, Marcus Wainwright, Heinrich Küttler, Andrew Lefrancq, Simon Green, Víctor Valdés, Amir Sadik, et al.  Deepmind lab.  _arXiv preprint arXiv:1612.03801_ , 2016.
  * Bellemare et al. (2013) Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling.  The arcade learning environment: An evaluation platform for general agents.  _Journal of Artificial Intelligence Research_ , 47:253–279, 2013.
  * Bellemare et al. (2017) Marc G. Bellemare, Will Dabney, and Rémi Munos.  A distributional perspective on reinforcement learning.  In _International Conference on Machine Learning_ , pages 449–458, 2017.
  * Berner et al. (2019) Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al.  DotA 2 with large scale deep reinforcement learning.  _arXiv preprint arXiv:1912.06680_ , 2019.
  * Bradtke and Barto (1996) Steven Bradtke and Andrew Barto.  Linear least-squares algorithms for temporal difference learning.  _Machine Learning_ , 22:33–57, 03 1996.
  * Burges et al. (2005) Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender.  Learning to rank using gradient descent.  In _Proceedings of the 22nd international conference on Machine learning_ , pages 89–96, 2005.
  * Chapelle and Keerthi (2010) Olivier Chapelle and S Sathiya Keerthi.  Efficient algorithms for ranking with svms.  _Information retrieval_ , 13(3):201–215, 2010\.
  * Chen et al. (2009) Wei Chen, Tie-Yan Liu, Yanyan Lan, Zhi-Ming Ma, and Hang Li.  Ranking measures and loss functions in learning to rank.  In _Advances in Neural Information Processing Systems_ , pages 315–323, 2009.
  * Ernst et al. (2005) Damien Ernst, Pierre Geurts, and Louis Wehenkel.  Tree-based batch mode reinforcement learning.  _Journal of Machine Learning Research_ , 6:503–556, 2005\.
  * Fu et al. (2020) Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine.  D4RL: Datasets for deep data-driven reinforcement learning.  _arXiv preprint arXiv:2004.07219_ , 2020.
  * Fujimoto et al. (2018) Scott Fujimoto, Herke Van Hoof, and David Meger.  Addressing function approximation error in actor-critic methods.  _arXiv preprint arXiv:1802.09477_ , 2018.
  * Fujimoto et al. (2019a) Scott Fujimoto, Edoardo Conti, Mohammad Ghavamzadeh, and Joelle Pineau.  Benchmarking batch deep reinforcement learning algorithms.  _Preprint arXiv:1910.01708_ , 2019a.
  * Fujimoto et al. (2019b) Scott Fujimoto, David Meger, and Doina Precup.  Off-policy deep reinforcement learning without exploration.  In _International Conference on Machine Learning_ , pages 2052–2062, 2019b.
  * Ghasemipour et al. (2020) Seyed Kamyar Seyed Ghasemipour, Dale Schuurmans, and Shixiang Shane Gu.  EMaQ: Expected-Max Q-Learning operator for simple yet effective offline and online RL.  _arXiv preprint arXiv:2007.11091_ , 2020.
  * Gulcehre et al. (2020) Caglar Gulcehre, Ziyu Wang, Alexander Novikov, Tom Le Paine, Sergio Gómez Colmenarejo, Konrad Zolna, Rishabh Agarwal, Josh Merel, Daniel Mankowitz, Cosmin Paduraru, et al.  RL unplugged: Benchmarks for offline reinforcement learning.  _arXiv preprint arXiv:2006.13888_ , 2020.
  * Haarnoja et al. (2018) Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  _arXiv preprint arXiv:1801.01290_ , 2018.
  * Hasselt (2010) Hado V Hasselt.  Double Q-learning.  In _Advances in neural information processing systems_ , pages 2613–2621, 2010.
  * Hessel et al. (2017) Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver.  Rainbow: Combining improvements in deep reinforcement learning.  _arXiv preprint arXiv:1710.02298_ , 2017.
  * Hoffman et al. (2020) Matt Hoffman, Bobak Shahriari, John Aslanides, Gabriel Barth-Maron, Feryal Behbahani, Tamara Norman, Abbas Abdolmaleki, Albin Cassirer, Fan Yang, Kate Baumli, Sarah Henderson, Alex Novikov, Sergio Gómez Colmenarejo, Serkan Cabi, Caglar Gulcehre, Tom Le Paine, Andrew Cowie, Ziyu Wang, Bilal Piot, and Nando de Freitas.  Acme: A research framework for distributed reinforcement learning.  _arXiv preprint arXiv:2006.00979_ , 2020.  URL https://arxiv.org/abs/2006.00979.
  * Jaques et al. (2019) Natasha Jaques, Asma Ghandeharioun, Judy Hanwen Shen, Craig Ferguson, Àgata Lapedriza, Noah Jones, Shixiang Gu, and Rosalind W. Picard.  Way off-policy batch deep reinforcement learning of implicit human preferences in dialog.  _Preprint arXiv:1907.00456_ , 2019.
  * Kapturowski et al. (2019) Steven Kapturowski, Georg Ostrovski, Will Dabney, John Quan, and Remi Munos.  Recurrent experience replay in distributed reinforcement learning.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=r1lyTjAqYX.
  * Kidambi et al. (2020) Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims.  Morel: Model-based offline reinforcement learning.  _arXiv preprint arXiv:2005.05951_ , 2020.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In _International Conference on Learning Representations_ , 2014.
  * Kumar et al. (2019) Aviral Kumar, Justin Fu, Matthew Soh, George Tucker, and Sergey Levine.  Stabilizing off-policy Q-learning via bootstrapping error reduction.  In _Conference on Neural Information Processing Systems_ , pages 11761–11771, 2019.
  * Kumar et al. (2020) Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine.  Conservative q-learning for offline reinforcement learning.  _arXiv preprint arXiv:2006.04779_ , 2020.
  * Lagoudakis and Parr (2003) Michail G. Lagoudakis and Ronald Parr.  Least-squares policy iteration.  _Journal of Machine Learning Research_ , 4:1107–1149, 2003\.
  * Lange et al. (2012) Sascha Lange, Thomas Gabel, and Martin Riedmiller.  Batch reinforcement learning.  In Marco Wiering and Martijn van Otterlo, editors, _Reinforcement Learning: State-of-the-Art_ , pages 45–73. Springer Berlin Heidelberg, 2012.
  * Levine et al. (2020) Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu.  Offline reinforcement learning: Tutorial, review, and perspectives on open problems.  _arXiv preprint arXiv:2005.01643_ , 2020.
  * Lillicrap et al. (2015) Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra.  Continuous control with deep reinforcement learning.  _Preprint arXiv:1509.02971_ , 2015.
  * Lin and Zhou (2020) Kaixiang Lin and Jiayu Zhou.  Ranking policy gradient.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net, 2020.  URL https://openreview.net/forum?id=rJld3hEYvS.
  * Mnih et al. (2015) Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis.  Human-level control through deep reinforcement learning.  _Nature_ , 518(7540):529–533, 2015.
  * Osband et al. (2019) Ian Osband, Yotam Doron, Matteo Hessel, John Aslanides, Eren Sezener, Andre Saraiva, Katrina McKinney, Tor Lattimore, Csaba Szepezvari, Satinder Singh, et al.  Behaviour suite for reinforcement learning.  _arXiv preprint arXiv:1908.03568_ , 2019.
  * Peters and Schaal (2008) Jan Peters and Stefan Schaal.  Reinforcement learning of motor skills with policy gradients.  _Neural networks_ , 21(4):682–697, 2008.
  * Pohlen et al. (2018) Tobias Pohlen, Bilal Piot, Todd Hester, Mohammad Gheshlaghi Azar, Dan Horgan, David Budden, Gabriel Barth-Maron, Hado Van Hasselt, John Quan, Mel Večerík, et al.  Observe and look further: Achieving consistent performance on Atari.  _arXiv preprint arXiv:1805.11593_ , 2018.
  * Pomerleau (1989) Dean A Pomerleau.  ALVINN: An autonomous land vehicle in a neural network.  In _Conference on Neural Information Processing Systems_ , pages 305–313, 1989.
  * Riedmiller (2005) Martin Riedmiller.  Neural fitted Q iteration – first experiences with a data efficient neural reinforcement learning method.  In João Gama, Rui Camacho, Pavel B. Brazdil, Alípio Mário Jorge, and Luís Torgo, editors, _European Conference on Machine Learning_ , pages 317–328, 2005.
  * Rummery and Niranjan (1994) Gavin A Rummery and Mahesan Niranjan.  _On-line Q-learning using connectionist systems_ , volume 37.  University of Cambridge, Department of Engineering Cambridge, UK, 1994\.
  * Schaul et al. (2015) Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver.  Prioritized experience replay.  _arXiv preprint arXiv:1511.05952_ , 2015.
  * Schmidhuber (1991) Jürgen Schmidhuber.  A possibility for implementing curiosity and boredom in model-building neural controllers.  In _Proc. of the international conference on simulation of adaptive behavior: From animals to animats_ , pages 222–227, 1991.
  * Siegel et al. (2020) Noah Siegel, Jost Tobias Springenberg, Felix Berkenkamp, Abbas Abdolmaleki, Michael Neunert, Thomas Lampe, Roland Hafner, Nicolas Heess, and Martin Riedmiller.  Keep doing what worked: Behavior modelling priors for offline reinforcement learning.  In _International Conference on Learning Representations_ , 2020.
  * Silver et al. (2017) David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al.  Mastering the game of go without human knowledge.  _nature_ , 550(7676):354–359, 2017.
  * Su et al. (2020) Andy Su, Jayden Ooi, Tyler Lu, Dale Schuurmans, and Craig Boutilier.  Conqur: Mitigating delusional bias in deep q-learning.  _arXiv preprint arXiv:2002.12399_ , 2020.
  * Sutton and Barto (2018) Richard S Sutton and Andrew G Barto.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Van Seijen et al. (2009) Harm Van Seijen, Hado Van Hasselt, Shimon Whiteson, and Marco Wiering.  A theoretical and empirical analysis of expected SARSA.  In _2009 ieee symposium on adaptive dynamic programming and reinforcement learning_ , pages 177–184. IEEE, 2009.
  * Vinyals et al. (2019) Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al.  Grandmaster level in starcraft ii using multi-agent reinforcement learning.  _Nature_ , 575(7782):350–354, 2019.
  * Wang et al. (2020) Ziyu Wang, Alexander Novikov, Konrad Żołna, Jost Tobias Springenberg, Scott Reed, Bobak Shahriari, Noah Siegel, Josh Merel, Caglar Gulcehre, Nicolas Heess, et al.  Critic regularized regression.  _arXiv preprint arXiv:2006.15134_ , 2020.
  * Williams (1992) Ronald J Williams.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine learning_ , 8(3-4):229–256, 1992.
  * Yu et al. (2020) Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma.  Mopo: Model-based offline policy optimization.  _arXiv preprint arXiv:2005.13239_ , 2020.

##  Appendix A Q-learning can escape to infinity in the offline case

######  Remark 1.

Q-learning, using neural networks as a function approximator, can diverge in
the offline RL setting given that the collected dataset does not include all
possible state-actions pairs, even if it contains all transitions along
optimal paths. Furthermore, the parameters (and hence the Q-values themselves)
can diverge towards infinity under gradient descent dynamics.

###### Proof.

The proof relies on providing a particular instance where Q-learning diverges
towards infinity. This is _sufficient_ to show that divergence can happen.
Note that the remark does not make any statement of how likely is for this to
happen, nor is providing sufficient conditions under which such divergence has
to happen.

Let us consider a simple deterministic MDP depicted in the figure below
(left).

$\mathcal{S}=\\{s_{1},s_{2},s_{3},s_{4}\\}$ is the set of all states, where
$S_{1}$ is deterministically the starting state and $S_{4}$ is the terminal
state of the MDP. Let ${\cal A}=\\{a_{0},a_{1},a_{2}\\}$ be the set of all
possible actions. Let the reward function $r(s,a)$ be $0$ for all action-state
pair except $r(s_{1},a_{0})$ which is 1. Let the transition probabilities
$P(s^{\prime}|s,a)$ be deterministic as defined by the depicted arrows. I.e.
for any state action pair only transitioning to one state has probability $1$,
while the rest has probability $0$. For example, only
$P(s_{4}|s_{1},a_{0})=1$, while
$P(s_{3}|s_{1},a_{0})=0,P(s_{2}|s_{1},a_{0})=0.P(s_{2}|s_{1},a_{0})=0$. For
$s_{1},a_{1}$ only $P(s_{2}|s_{1},a_{1})=1$ and so on and so forth.

_First observation_ is that the optimal behavior is to pick action $a_{0}$ (as
it is the only rewarding transition in the entire MDP).

The features describing each state are given by a single real number, where
$s_{1}=0,s_{2}=1,s_{3}=\beta$, with $\beta>\frac{1}{\gamma}>0$, where $\gamma$
is the discount factor. Assume actions are provided to the neural network as
one-hot vectors, i.e.
$a_{0}=[0,0,1]^{T},a_{1}=[0,1,0]^{T},a_{2}=[1,0,0]^{T}$333one-hot
representation is the typical representation for action in discrete spaces,
where we will refer to $a[i]$ as the $i$-th element of the vector that
represents the action $a$. For example $a_{0}[2]=1$ and $a_{0}[0]=0$.

Let us consider the Q-function parametrized as a simple MLP (depicted in the
figure above left). The MLP uses rectifier activations, and gets as input both
the state and action, returning a single scalar value which is the Q-value for
that particular state action combination. Rewriting the diagram in analytical
form we have that for $s\in\mathcal{R}$ and $a\in\mathcal{R}^{3}$:

$Q_{\theta}(s,a)=w\cdot
relu(s)+u_{1}relu(a[0]-2s)+u_{2}relu(a[1]-2s)+u_{3}relu(-2s-a[2])$ (7)

_A note on initialization._ The weights of the first layer are given as
constants. The process would work if we leave them to be learnable as well,
but the analysis would become considerably harder. The exact value used,
$-2,1,-1$, are not important. In principle we care for the negative weights
connecting $s$ to $h_{2},h_{3},h_{4}$ be larger in magnitude than those from
$a[i]$ to $h_{i}$, and we care for the weight between $a[2]$ and $h_{2}$ to be
negative. They can be scaled arbitrarily small and do not need to be
identical.

What we will rely in the rest of the analysis is that the preactivation of
$h_{2},h_{3},h_{4}$ to be negative for state $s_{2}$ and $s_{3}$. This will be
in the zero region of the rectifier, meaning no gradient will flow through
those units. Since $s_{3}>s_{2}\geq 1$ and $a[i]\in\\{0,1\\}$, it is
sufficient for the weight from $s$ to $h_{2},h_{3},h_{4}$ to be larger in
magnitude than the weight from $a[i]$ to $h_{2},h_{3},h_{4}$. This ensures
that for $s>1$, the Q-function is not a function of $u_{i}$ as $u_{i}$ will
get multiplied by $0$.444The fact that no gradient gets propagated in the
first layer is only important if we attempt to consider the case when the
first layer weights are learnable. Also we want the function to never depend
on $u_{3}$ to simplify our analysis, which is easily achievable if the weight
going from $a[2]$ to $h_{4}$ is negative.

Given the observations above, if we plug in the formula the different values
of $s_{i}$ and $a_{i}$ we get that:

$\begin{array}[]{lll}&Q_{\theta}(s_{1},a_{0})&=u_{1}\\\
&Q_{\theta}(s,1,a_{1})&=u_{2}\\\ &Q_{\theta}(s_{1},a_{2})&=0\\\ \forall
a\in\mathcal{A},&Q_{\theta}(s_{2},a)&=w\\\ \forall
a\in\mathcal{A},&Q_{\theta}(s_{3},a)&=\beta w\end{array}$ (8)

Note that this implies that

$\begin{array}[]{l}\max_{a}Q_{\theta}(s_{2},a)=w\\\
\max_{a}Q_{\theta}(s_{3},a)=\beta w\end{array}$ (9)

Assume $w>0$. And let the dataset collected by the behavior policy to contain
the following 3 transitions:

$\mathcal{D}=\\{(s_{1},a_{0},1,s_{4}),(s_{1},a_{1},0,s_{2}),(s_{2},a_{2},0,s_{3})\\}$

We can now construct the Q-learning loss that we will use to learn the
function $Q$ in the offline case which will be

$\begin{array}[]{ll}\mathcal{L}&=\sum_{(s,a,r,s^{\prime})\in\mathcal{D}}\left(Q_{\theta}(s,a)-r-\gamma
max_{a}Q_{\theta}^{\prime}(s^{\prime},a)\right)^{2}\\\
&=(Q_{\theta}(s_{1},s_{0})-1)^{2}+(Q_{\theta}(s_{1},a_{1})-\gamma\max_{a}Q_{\theta}^{\prime}(s_{2},a))^{2}+(Q_{\theta}(s_{2},a_{2})-\gamma\max_{a}Q_{\theta}^{\prime}(s_{3},a))^{2}\\\
&=(u_{1}-1)^{2}+(u_{2}-\gamma w^{\prime})^{2}+(w-\gamma\beta
w^{\prime})^{2}\end{array}$ (10)

Note that we relied on Equation (9) to evaluate the $\max$ operator and
$\theta^{\prime}$ is a copy of $\theta$, that is used for bootstrapping. This
is the standard definition of Q-learning see Equation (3). In particular in
this toy example $\theta^{\prime}$ is numerically always identical to $\theta$
(in general it can be a trailing copy of $\theta$ from k steps back) and is
used more to indicate that when we take a derivative of the loss with respect
to $\theta$ we do not differentiate through $Q_{\theta}^{\prime}$. From
Equation (10) we notice that only the first transition in dataset contributes
to the gradient of $u_{1}$, only the second transition contributes to the
gradient of $u_{2}$ and only the third transition contributes to the gradient
of $w$. We can not evaluate the gradient with respect to $\theta$ of the loss
$\mathcal{L}$ over the entire dataset:

$\begin{array}[]{lll}\nabla_{u_{1}}&=u_{1}-1&\\\
\nabla_{u_{2}}&=u_{2}-(0+\gamma w)&\\\ \nabla_{u_{3}}&=w-(0+\gamma\beta
w)&=(1-\gamma\beta)w\\\ \nabla_{w}&=w-(0+\gamma\beta w)&=(1-\gamma\beta)w\\\
\end{array}$ (11)

Note that we assumed $w>0$ and for simplicity we exploited that $w^{\prime}=w$
numerically, to be able to better understand the dynamics of the update. Given
that $\beta>\frac{1}{\gamma}$, $\nabla_{w}$ will always be negative as long as
$w$ (and implicitly $w^{\prime}$) stays positive. Given that
$w_{t}=w_{t-1}-\alpha\nabla_{w}$ for some learning rate $\alpha>0$, the update
creates a vicious loop that will increase the norm of $w$ at every iterations,
such that $\lim_{t\to\infty}w_{t}=\infty$. Given that the gradient on $u_{2}$
tracks $w$, it means that the path that takes action $a_{2}$ in the initial
state $s_{1}$ will have $+\infty$ as value. _Note that all transitions along
the optimal path of this deterministic MDP are part of the dataset._

Also that given our example, the same will happen if we rely on SGD rather
than batch GD (as the different examples affect different parameters of the
model independently and there is no effect from averaging). Preconditioning
the updates (as for e.g. is done by Adam or rmsprop) will also not change the
result as they will not affect the sign of the gradient (the preconditioning
matrix needs to be positive definite). Neither momentum will not affect the
divergence of learning, as it will not affect the sign of the update.

This means that the provided MDP will diverge towards infinity under the
updates on most commonly used gradient based algorithms.

∎

##  Appendix B The surprising efficiency of 1-step of policy improvement

In this section, we show examples where 1-step of policy improvement is
surprisingly effective. We first start by going over some theoretical results.

######  Lemma 1.

Assume a Markov Decision Process that satisfies the following conditions: (1)
the transition distribution $P$ is deterministic, (2) any trajectory has a
finite length (3) we are interested in the episodic return, i.e., the discount
factor $\gamma=1$, (4) the reward function $r(s,a)=0$ for any non-terminating
state and $r(s,a)\in\left\\{L,H\right\\}$ for any terminating state with
constants $L<H$. Denote by ${\cal S}$ the set of states from which there
exists a trajectory with a reward of $H$. If a behavior policy $\pi_{{\cal
B}}$ can generate a trajectory with a reward of $H$ with a non-zero
probability for any initial state $s\in{\cal S}$, then one step of policy
improvement on the exact behavior value function will give an optimal policy
$\pi^{*}$.

###### Proof.

Let us note that, our proof assumes a tabular case, and by our definition any
trajectory receives an episodic return of either $L$ or $H$. A policy $\pi$ is
optimal in this environment if and only if it receives a reward of $H$ with a
probability of 1 from any state $s\in{\cal S}$. For a behavior policy
satisfying the premise, its value function is as follows,

$\displaystyle Q(s,a)$ $\displaystyle=\mathbb{E}_{\tau\sim\pi_{{\cal
B}}}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})\right]=\Big{(}p(\tau_{H}|s,a)H+(1-p(\tau_{H}|s,a))L\Big{)}\in\left[L,H\right],$
$\displaystyle V(s)$ $\displaystyle=\mathbb{E}_{a\sim\pi_{{\cal
B}}(s)}[Q(s,a)]\left\\{\begin{array}[]{ll}>L&\mbox{if $s\in{\cal S}$;}\\\
=L&\mbox{otherwise.}\end{array}\right.$ (14)

where $p(\tau_{H}|s,a)$ denotes the probability of trajectories sampled from
$(s,a)$ with a reward of $H$. The policy after one step of policy improvement
is defined as follows with a tie being broken arbitrarily.

$\pi(s)=\operatorname*{arg\,max}_{a}Q(s,a)$ (15)

From any state $s_{0}\in{\cal S}$, let $a_{0}\sim\pi(s_{0})$ be any sample
from $\pi$. Because $V(s)>L$, we know $Q(s_{0},a_{0})>L$, which infers there
exists a trajectory starting from $(s_{0},a_{0})$ with a reward of $H$. Let
$s_{1}$ be the next state following action $a_{0}$ in the deterministic
environment. Consequently we know $s_{1}\in{\cal S}$. We can apply $\pi$
repeatedly to sample a trajectory $s_{0},a_{0},s_{1},a_{1},\dots$. Because
$s_{t}\in{\cal S},\forall t\geq 0$ by induction and any trajectory is finite
according to the premise, any sampled trajectory from $s_{0}$ will eventually
reach a terminating state with a reward of $H$, and therefore, the policy
$\pi$ receives an episodic return of $H$ with a probability of 1 from any
state $s_{0}\in{\cal S}$ and is therefore an optimal policy. ∎

######  Remark 1.

The conditions of the MDP can be satisfied by a broad range of reinforcement
learning problems, such as a goal reaching task that receives a constant
positive reward only if it reaches the goal within a time limit, or an
autonomous driving task that will receive a constant penalty if it crashes in
a given time period.

######  Remark 2.

The assumption on the behavior policy assumes a sufficient exploration in the
dataset so that a good trajectory exists for any initial state, but it doesn’t
impose any restriction on the average performance.

Figure 10: Chain MDP. The initial state is the leftmost state. There are only
two rewarding transitions both of which come out of the right most state. All
other transitions have a reward of 0. The behavioral policy is uniformly
random between the two actions in each state.

######  Lemma 2.

In the chain MDP (Figure 10) of at least 2 states with discount
$\gamma\in(0,1)$, under uniformly random behavior policy, one step of policy
improvement (given the true value function) would lead to an optimal policy.

###### Proof.

We name the states in this class of environment numerically. That is the left
most state is state $1$ and the last state $n$. Denote $V_{i}$ to be the value
function of the uniform random policy at state $i$. Let
$V=[V_{0},V_{1},\cdots,V_{n}]$. It is easy to show that $(I-\gamma P)V=R$
where $P$ is the state transition matrix $R=[0,\cdots,1]^{T}$. We know

$(I-\gamma
P)=\left(\begin{array}[]{cccccc}1-\frac{1}{2}\gamma&-\frac{1}{2}\gamma&&&&0\\\
-\frac{1}{2}\gamma&1&-\frac{1}{2}\gamma&&&\\\
&-\frac{1}{2}\gamma&1&-\frac{1}{2}\gamma&&\\\ &&\ddots&\ddots&\ddots&\\\
&&&-\frac{1}{2}\gamma&1&-\frac{1}{2}\gamma\\\
0&&&&-\frac{1}{2}\gamma&1-\frac{1}{2}\gamma\\\ \end{array}\right).$

Since all rewards are positive, we know $V_{i}>0\;\forall\,i$. Since
$(1-\frac{1}{2}\gamma)V_{1}-\frac{1}{2}\gamma V_{2}=0$, $V_{1}>0\;V_{2}>0$,
and $\gamma\in(0,1)$, we know $V_{2}>V_{1}$. Assume that $V_{k}>V_{k-1}$ where
$k<n$ , then $V_{k+1}>V_{k}$ since $\frac{1}{2}\gamma(V_{k+1}+V_{k-1})=V_{k}$.
Therefore, by induction, we show that the values are monotonically increasing.

In every state, going left along the chain is therefore of lower $Q$ value
compared to going right (if going right in the rightmost states entails
staying). We know the optimal policy in this environment is to go right.
Therefore 1 step of policy improvement provides the optimal policy. ∎

######  Remark 3.

In a 2-d grid world, we can show an analogous result. We, however, omit this
as the proof follows a similar structure albeit more complicated.

One-step of policy improvement, despite the examples we have shown in this
section, does not always lead to an optimal policy. We argue, however, it is
surprisingly good in many scenarios. In this section, we present such an
example in a 2-d grid world (see Figure 11). In this example, one-step of
policy improvement from a random policy is not sufficient to derive an optimal
policy. The resulting policy, however, is very close in performance to the
optimal policy when measured by the value of the initial state. It is
reasonable to assume that many environments share the properties for which BVE
is an effective technique.

Figure 11: Grid world example. Here, the numbers in the cells represent
rewards. (The reward is 0 in the absence of numbers). The green arrows
represent the policy. The color of the cell shows the GT value function. [Top]
An uniformly random policy achieves value of $-9.518$ at the initial state
(upper left state). [Middle] With one step of policy improvement over the
random polices, we achieve $42.160$ in value. [Bottom] The optimal policy in
this environment obtains $42.359$ in value for the initial state, only $0.2$
higher than the value achieved using only 1 step of policy improvement.

##  Appendix C Additional Results and Ablations

###  C.1 On the Effects of Regularization

In this section, we study the effect of the regularization on the action gap
and the over-estimation error. In Figure 12, we show that increasing the
regularization co-efficient for the ranking regularization increases the
action gap across the Atari online policy selection games which can result to
lower estimation error and better optimization.

Figure 12: The effect of increasing the ranking regularization on the action
gap. We can see that increasing the regularization significantly increases the
action-gap which potentially can help further stabilize the learning.

In Figure 13, we investigate the effect of increasing the regularization on
the over-estimation of the Q-network when evaluated in the environment. We
visualize the mean over-estimation across the online policy selection games
for Atari.

Figure 13: The Effect of increasing the ranking regularization on the over-
estimation. Here, we see that increasing the ranking regularization reduces
the mean over-estimation error across Atari online policy selection games.

###  C.2 Atari: Robustness to Data

The robustness of the reward distribution in the dataset is an important
feature required to deploy offline RL algorithms in the real-world. We would
like to understand the robustness of behavior value estimation in the offline
RL setting. Thus, we first investigate the robustness of $\mathtt{B}$ in
contrast to Q-learning with respect to the datasets’ size and the reward
distribution. In Figure 14, we split out the dataset into two smaller
datasets: i) transitions coming from only highly rewarding ii) transitions
from only poorly performing episodes. We show that $\mathtt{B}$ outperforms
Q-learning in both settings.

Figure 14: Robustness Experiments: We compare DQN and $\mathtt{B}$ in terms of
their robustness to the reward distribution on Atari online policy selection
games. We split the datasets in two bins: the dataset that only contains
transitions that are coming from episodes that have episodic return less than
the mean episodic return in the dataset ("Episodic Reward $<$ Mean"),
transitions coming from episodes with return higher than the mean return in
the dataset ("Episodic Reward $>$ Mean"). $\mathtt{B}$ performs better than
DQN in both cases.

###  C.3 Online Policy Selection Games Results

In Figure 15, we compare the performance of DDQN, $\mathtt{BVE}$,
$\mathtt{R}$-$\mathtt{BVE}$, and $\mathtt{R}$-$\mathtt{DQN}$ with respect to
the rewards they achieve over the course of training on Atari online policy
selection games.

Figure 15: The Raw Returns obtained by each baseline on Atari online Policy
Selection Games.

###  C.4 Over-estimation on Online Policy Selection Games

In Figure 16 and 17, we report the value error of $\mathtt{BVE}$,
$\mathtt{R}$-$\mathtt{BVE}$, $\mathtt{R}$-$\mathtt{DQN}$ and DDQN’s value
error and overestimation error respectively. With respect to both metrics we
observed that DDQN has the highest value error. Using $\mathtt{BVE}$
significantly alleviates the problem with the value and overestimation errors,
but ranking regularization further reduces the problem both for DDQN and
$\mathtt{BVE}$.

Figure 16: The value error computed in the environment by evaluating the agent
and computed with respect to the ground truth discounted returns. The negative
values indicate under-estimation and positive values are for over-estimation.
Figure 17: Overestimation error: Here we show the over-estimation error
computed by evaluating the agent in the environment. We compute the over-
estimation error as we discussed in the main paper. Here we can see the clear
trend for the over-estimation error across different Atari online policy
selection games as follows: DDQN > $\mathtt{R}$-$\mathtt{DQN}$ >
$\mathtt{BVE}$ > $\mathtt{R}$-$\mathtt{BVE}$. We see that $\mathtt{BVE}$
alleviates the over-estimation problem and ranking regularization further
helps as well.

##  Appendix D Details of Datasets

###  D.1 BSuite Dataset

BSuite (Osband et al., 2019) data was collected by training DQN agents (Mnih
et al., 2015) with the default setting in Acme (Hoffman et al., 2020) from
scratch in each of the three tasks: cartpole, catch, and mountain_car. We
convert the originally deterministic environments into stochastic ones by
randomly replacing the agent action with a uniformly sampled action with a
probability of $\epsilon\in\\{0,0.1,0.2,0.3,0.4,0.5\\}$ (ie. $\epsilon=0$
corresponds to the original environment). We train agents (separately for each
randomness level and 5 seeds, i.e. 25 agents per game) for 1000, 2000, 500
episodes in cartpole, catch and mountain_car respectively. The number of
episodes is chosen so that agents in all levels can reach their best
performance. We record all the experience generated through the training
process. Then to reduce the coverage of the datasets and make them more
challenging we only used 10% of the data by subsampling it. More details of
the dataset are provided in Table 1. The results presented in the paper are
averaged over the 5 random seeds.

Environments | Number of episodes | Number of transitions | Average episode length
---|---|---|---
cartpole ($\epsilon=0.0$) | 1000 | 710K | 710
cartpole ($\epsilon=0.1$) | 1000 | 773K | 773
cartpole ($\epsilon=0.2$) | 1000 | 649K | 649
cartpole ($\epsilon=0.3$) | 1000 | 607K | 607
cartpole ($\epsilon=0.4$) | 1000 | 672K | 672
cartpole ($\epsilon=0.5$) | 1000 | 643K | 643
catch ($\epsilon=0.0$) | 200 | 1.8K | 9
catch ($\epsilon=0.1$) | 200 | 1.8K | 9
catch ($\epsilon=0.2$) | 200 | 1.8K | 9
catch ($\epsilon=0.3$) | 200 | 1.8K | 9
catch ($\epsilon=0.4$) | 200 | 1.8K | 9
catch ($\epsilon=0.5$) | 200 | 1.8K | 9
mountain_car ($\epsilon=0.0$) | 50 | 10K | 205
mountain_car ($\epsilon=0.1$) | 50 | 10K | 210
mountain_car ($\epsilon=0.2$) | 50 | 22K | 447
mountain_car ($\epsilon=0.3$) | 50 | 13K | 277
mountain_car ($\epsilon=0.4$) | 50 | 12K | 250
mountain_car ($\epsilon=0.5$) | 50 | 24K | 494
Table 1: BSuite dataset details.

###  D.2 DeepMind Lab Dataset

DeepMind Lab (Beattie et al., 2016) data was collected by training distributed
R2D2 (Kapturowski et al., 2019) agents from scratch on individual tasks.
First, we tuned the hyperparameters of a distributed version of the Acme
(Hoffman et al., 2020) R2D2 agent independently for every task to achieve fast
learning in terms of actor steps. Then, we recorded the experience across all
actors during entire training runs a few times for every task. Training was
stopped after there was no further progress in learning across all runs, with
a resulting number of steps for each run between 50 million for the easiest
task ($\mathtt{seekavoid\\_arena\\_01}$) and 200 million for some of the hard
tasks. Finally we built a separate offline RL dataset for every run and every
task. See more details about these datasets in Table 2.

Additionally, for the $\mathtt{seekavoid\\_arena\\_01}$ task we ran two fully
trained snapshots of our R2D2 agents on the environment with different levels
of noise ($\epsilon=0,0.01,0.1,0.25$ for $\epsilon$-greedy action selection).
We recorded all interactions with the environment and generated a different
offline RL dataset containing 10 million actor steps for every agent and every
value of $\epsilon$.

Figure 18: DeepMind Lab Reward Distribution: We show the reward distributions for the DeepMind Lab datasets. The vertical red line indicates the average episodic return in the datasets. Table 2: DeepMind Lab dataset details. For training data, reward is measured as the maximum over training of the average reward over runs for the same task. For snapshot data, reward is just an average over all episodes recorded using the same level of noise. Task | Episode Length | Datasets | Episodes (K) | Steps (M) | Reward
---|---|---|---|---|---
$\mathtt{seekavoid\\_arena\\_01}$ | 300 | 5 | 667.1 | 200.1 | 39.0
$\mathtt{seekavoid\\_arena\\_01}$ snapshot ($\epsilon=0$) | 300 | 2 | 66.7 | 20 | 40.4
$\mathtt{seekavoid\\_arena\\_01}$ snapshot ($\epsilon=0.01$ | 300 | 2 | 66.7 | 20 | 40.1
$\mathtt{seekavoid\\_arena\\_01}$ snapshot ($\epsilon=0.1$) | 300 | 2 | 66.7 | 20 | 36.9
$\mathtt{seekavoid\\_arena\\_01}$ snapshot ($\epsilon=0.25$) | 300 | 2 | 66.7 | 20 | 29.7
$\mathtt{explore\\_object\\_rewards\\_few}$ | 1350 | 3 | 178.3 | 240.7 | 51.5
$\mathtt{explore\\_object\\_rewards\\_many}$ | 1800 | 3 | 334.1 | 601.4 | 64.5
$\mathtt{rooms\\_select\\_nonmatching\\_object}$ | 180 | 3 | 2001.1 | 360.2 | 32.5
$\mathtt{rooms\\_watermaze}$ | 1800 | 3 | 201.8 | 363.3 | 48.8

##  Appendix E Experiment Details

We used the Adam optimizer (Kingma and Ba, 2014) for all our experiments. For
details on the used hyperparameters, refer to the Table 4 for bsuite, Table 3
for Atari, and Table 5 for DeepMind Lab. Our evaluation protocol is described
below, in Section E.1. On Atari experiments, we have normalized the agents’
scores as described in (Gulcehre et al., 2020). On Atari, in all our
experiments we report the median normalized score only as accustomed in the
literature for reporting results on Atari.

##### Atari Hyperparameters:

On Atari we directly used the baselines and the hyperparameters reported in
(Gulcehre et al., 2020), to get the detailed Atari results on test set we
communicated with the authors. We have run additional CQL and our own models
with ranking regularization and reparameterization. For CQL we have finetuned
both the learning rate from the grid $\left[8e-5,\leavevmode\nobreak\
1e-4,\leavevmode\nobreak\ 3e-4\right]$. For our own proposed models we have
only tuned the learning rate from the grid $\left[8e-5,\leavevmode\nobreak\
1e-4,\leavevmode\nobreak\ 3e-4\right]$ and the ranking regularization
hyperparameter from the grid $\left[0.005,0.05,0.01,0.1,1\right]$. We have
fixed the rest of the hyperparameters. As mentioned earlier, we have only used
the online policy selection games for finetuning the hyperparameters. As a
result of our grid search, we have used learning rate of $1e-4$ for CQL and
our models. We have used $0.01$ for the $\alpha$ hyperparameter of CQL.
$0.005$ seems to be the most optimal hyperparameter choice for the ranking
regularization hyperparameter on most tasks that we have tried it on. We
provide the details of the Atari hyperparameters and compute infrastructure in
Table 3.

Table 3: Atari experiments’ hyperparameters. The top section of the table corresponds to the shared hyperparameters of the offline RL methods and the bottom section of the table contrasts the hyperparameters of Online vs Offline DQN. Hyperparameter | setting (for both variations)
---|---
Discount factor |  | 0.99
Mini-batch size |  | 256
Target network update period | every 2500 updates
Evaluation $\epsilon$ |  | $0.4^{8}$
$Q$-network: channels |  | 32, 64, 64
$Q$-network: filter size |  |  $8\times 8$, $4\times 4$, $3\times 3$
$Q$-network: stride |  | 4, 2, 1
$Q$-network: hidden units |  | 512
Training Steps |  | 2M learning steps
Hardware |  | Tesla V100 GPU
Replay Scheme |  | Uniform
Hyperparameter | Online | Offline
Min replay size for sampling | 20,000 | -
Training $\epsilon$ (for $\epsilon$-greedy exploration) | 0.01 | -
$\epsilon$-decay schedule | 250K steps | -
Fixed Replay Memory | No | Yes
Replay Memory size | 1M steps | 2M steps
Double DQN | No | Yes

##### bsuite Hyperparameters:

Our hyperparameter selection protocol for bsuite is the same as Atari. The
main difference between the Atari and bsuite experiments is the network
architecture that has been used. We provide the details of hyperparameters
used for bsuite in Table 4.

Table 4: bsuite experiments’ hyperparameters. The top section of the table corresponds to the shared hyperparameters of the offline RL methods and the bottom section of the table contrasts the hyperparameters of Online vs Offline DQN. Hyperparameter | setting (for both variations)
---|---
Discount factor |  | 0.99
Mini-batch size |  | 128
Target network update period | every 2500 updates
Evaluation $\epsilon$ |  | $0.4^{8}$
$Q$-network: |  | an MLP
$Q$-network: hidden units |  | $56,56,\text{num\\_actions}$
Training Steps |  | 2M learning steps
Hardware |  | Tesla V100 GPU
Replay Scheme |  | Uniform
Hyperparameter | Online | Offline
Min replay size for sampling | 20,000 | -
Training $\epsilon$ (for $\epsilon$-greedy exploration) | 0.01 | -
$\epsilon$-decay schedule | 250K steps | -
Fixed Replay Memory | No | Yes
Replay Memory size | 1M steps | 2M steps
Double DQN | No | Yes

##### DeepMind Lab Hyperparameters:

On DeepMind Lab experiments, we tuned the hyperparameters of each model
individually on each level separately. We have tuned the learning rate and the
method-specific hyperparameters for each model from the same grid that we have
used for Atari. For CQL, the specific hyperparameter that we tuned in addition
to the learning rate is the regularization hyperparameter $\alpha$. For our
own baselines with the ranking regularization, we fixed the ranking
regularization co-efficient to the best value we found on Atari, and only
tuned the margin hyperparameter $\nu$ from the grid $\\{0.05,0.5\\}$. All our
algorithms use n-step returns in our DeepMind Lab experiments, where $n$ is
fixed to $5$ in all our experiments. Thus both behavior value estimation and
Q-learning experiments use 5 steps of unrolls for learning. We provide the
details of the Deepmind Lab hyperparameters and details of compute
infrastructure in Table 5.

Table 5: Deepmind Lab experiments’ hyperparameters. The top section of the table corresponds to the shared hyperparameters of the offline RL methods and the bottom section of the table contrasts the hyperparameters of Online vs Offline DQN. Hyperparameter | setting (for both variations)
---|---
Discount factor |  | 0.997
Target network update period | every 400 updates
Evaluation $\epsilon$ |  | $0.4^{8}$
Importance sampling exponent |  | 0.6
Architecture |  Canonical R2D2 (Kapturowski et al., 2019)
Hyperparameter | Online | Offline
Hardware | 4x TPUv2 | 4x Tesla V100 GPU
Training Steps | 50-200M actor steps | 50K learning steps
Sequence Length | 120 (40 burn-in) | Full episode
Mini-batch size | 32 | 8
Training $\epsilon$ (for $\epsilon$-greedy exploration) | $0.4,...,0.4^{8}$ | -
Replay Scheme | Prioritized (exponent 0.9) | -
Min replay size for sampling | 600K steps | -
Replay Memory size | 12M steps | 50-200M steps

###  E.1 Evaluation protocol

To evaluate the performance of the various methods, we use the following
protocol:

  1. 1.

We sweep over a small (5-10) sets of hyperparameter values for each of the
methods.

  2. 2.

We independently train each of the models on 5 datasets generated by running
the behavior policy with 5 different seeds (ie. producing 25-50 runs per
problem setting and method).

  3. 3.

We evaluate the produced models in the original environments (without the
noise).

  4. 4.

We average the results over seeds and report the results of the best
hyperparameter for each method.

####  E.1.1 Evaluation method

To evaluate models (step 3. above), in the case of bsuite and DeepMind Lab we
ran an evaluation job in parallel to the training one. It repeatedly read the
learner’s checkpoint and produced evaluation results during training. We
report the average of the evaluation scores over the last 100 learning steps.

In the case of the Atari environments, instead of averaging performance during
the final steps of learning, we take the final snapshot produced by a given
method and evaluate it on a ‘100‘ environment steps after the training
finished.

###  E.2 Atari Offline Policy Selection Results

In Table 6, we show the performance of our baselines on different Atari
Offline Policy selection games. We show that $\mathtt{R}$-$\mathtt{BVE}$
outperforms other approaches significantly.

Table 6: Atari Offline Policy Selection Results: In this table, we list the median normalized performance of different baselines across all RLU Atari offline policy selection games. Name | Normalized Score
---|---
BC | 50.8
DDQN | 83.1
CQL | 98.9
BCQ | 102.6
IQN | 104.8
REM | 104.7
$\mathtt{R}$-$\mathtt{DQN}$ | 108.2
$\mathtt{R}$-$\mathtt{BVE}$ | 109.1

###  E.3 DeepMind Lab Detailed Results

In Table 7, we have shown the results on the Deepmind Lab datasets. It is
possible see from these numerica results that $\mathtt{R}$-$\mathtt{BVE}$
outperforms other approaches and $\mathtt{BVE}$ is still very competitive.

Table 7: Detailed Results on the DeepMind Lab: We provide the detailed results for each DeepMind levels along with the standard errors. | BC | R2D2 | CQL | $\mathtt{BVE}$ |  $\mathtt{R}$-$\mathtt{BVE}$
---|---|---|---|---|---
$\mathtt{explore\\_object\\_rewards\\_many}$ |  1.8 $\pm$ 1.0 |  19.8 $\pm$ 4.0 |  23.8 $\pm$ 5.1 |  23.7 $\pm$ 3.8 |  31.4 $\pm$ 1.7
$\mathtt{explore\\_object\\_rewards\\_few}$ |  2.9 $\pm$ 1.4 |  8.5 $\pm$ 3.4 |  9.3 $\pm$ 2.5 |  7.6 $\pm$ 2.1 |  13.4 $\pm$ 2.6
$\mathtt{rooms\\_watermaze}$ |  0.1 $\pm$ 0.1 |  2.7 $\pm$ 1.4 |  4.0 $\pm$ 3.7 |  9.9 $\pm$ 2.7 | 14.1 $\pm$ 4.2
$\mathtt{rooms\\_select\\_nonmatching\\_object}$ |  1.1 $\pm$ 4.6 |  5.4 $\pm$ 2.3 |  3.4 $\pm$ 2.4 |  9.4 $\pm$ 2.3 |  9.6 $\pm$ 3.2
$\mathtt{seekavoid\\_arena\\_01}$, $\epsilon=0$ |  28.02 $\pm$ 7.6 |  4.7 $\pm$ 3.0 |  12.8 $\pm$ 10.7 |  4.4 $\pm$ 0.9 |  17.07 $\pm$ 10.1
$\mathtt{seekavoid\\_arena\\_01}$, $\epsilon=0.01$ |  32.4 $\pm$ 1.3 |  5.5 $\pm$ 1.6 |  12.7 $\pm$ 5.4 |  4.1 $\pm$ 1.8 |  19.8 $\pm$ 4.9
$\mathtt{seekavoid\\_arena\\_01}$, $\epsilon=0.1$ |  18.9 $\pm$ 14.4 |  8.6 $\pm$ 3.0 |  16.3 $\pm$ 7.7 |  11.775 $\pm$ 4.5 |  31.8 $\pm$ 4.7
$\mathtt{seekavoid\\_arena\\_01}$, $\epsilon=0.25$ |  17.46 $\pm$ 7.5 |  13.5 $\pm$ 5.1 |  13.5 $\pm$ 5.06 |  9.0 $\pm$ 0.25 |  25.57 $\pm$ 7.0

##  Appendix F Ranking Regularization

We propose a family of methods that prevent the extrapolation error by
suppressing the values of the actions that are not in the dataset. We achieve
that by ranking the actions in the training set higher than the ones that are
not in the training set. For the learned Q-function the absolute values of
actions do not matter, we are rather interested in relative ranking of the
actions. Given $a_{t}$ is the action from the dataset. For all $j\neq t$ and
illustration purposes, the value iteration can be written as:

$\displaystyle\mathbb{E}[\max_{a}Q(s,a)]$
$\displaystyle\approx\mathbb{E}\left[P(Q(s,a_{t})>Q(s,a_{j}))Q(s,a_{t})|t\in
Max\right]+\mathbb{E}\left[P(Q(s,a_{t})\ngtr Q(s,a_{j}))Q(s,a_{j})|j\in
Max\right]$
$\displaystyle=\mathbb{E}\left[P(Q(s,a_{t})>Q(s,a_{j}))Q(s,a_{t})|t\in
Max\right]+\mathbb{E}\left[(1-P(Q(s,a_{t})>Q(s,a_{j})))Q(s,a_{j})|j\in
Max\right]$
$\displaystyle=\alpha\mathbb{E}\left[P(\hat{Q}(s,a_{t})>\hat{Q}(s,a_{j}))\hat{Q}(s,a_{t})|t\in
Max\right]+\alpha\mathbb{E}\left[(1-P(\hat{Q}(s,a_{t})>\hat{Q}(s,a_{j})))\hat{Q}(s,a_{j})|j\in
Max\right]$
$\displaystyle=\alpha\left(\mathbb{E}\left[P(\hat{Q}(s,a_{t})>\hat{Q}(s,a_{j}))\hat{Q}(s,a_{t})|t\in
Max\right]+\mathbb{E}\left[(1-P(\hat{Q}(s,a_{t})>\hat{Q}(s,a_{j})))\right]\right)\xi$

where $\xi$ is an irreducible noise, because we can not gather additional data
on $(s_{t},\leavevmode\nobreak\ a_{j})$, and we don’t know the corresponding
reward for it. This causes extrapolation error which accumulates through the
bootstrapping in the backups as noted by (Kumar et al., 2019). We implicitly
pull down the $P(Q(s,a_{t})\ngtr Q(s,a_{t}))$ by ranking the actions in the
dataset higher which pushes up $P(Q(s,a_{t})>Q(s,a_{j}))$. As a result, the
extrapolation error in Q-learning would also reduce.

###  F.1 Pairwise Ranking Loss for Q-learning

In this section, we discus the relationship between the pairwise ranking loss
for Q-learning and the list-wise pairwise ranking losses.

$\displaystyle p_{tj}$
$\displaystyle=\sigma(\hat{Q}_{\theta}(s,a_{t})-\hat{Q}_{\theta}(s,a_{j})),$
$\displaystyle\pi(a_{t}|s)$ $\displaystyle\approx\prod_{i=0,i\neq t}^{|{\cal
A}|}p_{ti}/Z,$ $\displaystyle Z$ $\displaystyle=\sum_{i=0}^{|{\cal
A}|}\prod_{j=0,j\neq i}^{|{\cal A}|}p_{ij}.$ $\displaystyle{\cal R}(\theta)$
$\displaystyle=-\sum_{i=0}^{|{\cal A}|}\log(p_{ti}),$
$\displaystyle=-\sum_{i=0,i\neq t}^{|{\cal
A}|}\log(\sigma(\hat{Q}_{\theta}(s,a_{t})-\hat{Q}_{\theta}(s,a_{i}))),$
$\displaystyle=\sum_{i=0,i\neq t}^{|{\cal
A}|}\text{softplus}(\hat{Q}_{\theta}(s,a_{i})-\hat{Q}_{\theta}(s,a_{t})).$

We use a common approximation (Chen et al., 2009; Burges et al., 2005) of the
softplus with the $\max(\cdot,0)$ function:

$\mathcal{C}(\theta)=\sum_{i=0,i\neq t}^{|{\cal
A}|}\max\left(\hat{Q}_{\theta}(s,a_{i})-\hat{Q}_{\theta}(s,a_{t})+\nu,0\right)^{2}$
(16)

Imposing the constraint in Equation equation 16 can be harmful when the
dataset has large amount of suboptimal trajectories (or when the dataset is
generated by a random policy.) Because this constraint can drive the value
function to overestimate the values of suboptimal actions in the dataset. As a
result, similar to (Wang et al., 2020), we propose a filtering function to
impose that constraints only on rewarding transitions:

$\mathcal{C}(\theta)=\exp(\hat{V}^{\pi_{{\cal B}}}(s)-\mathbb{E}_{s\sim{\cal
D}}[\hat{V}^{\pi_{{\cal B}}}(s)])\sum_{i=0,i\neq t}^{|{\cal
A}|}\max\left(\hat{Q}_{\theta}(s,a_{i})-\hat{Q}_{\theta}(s,a_{t})+\nu,0\right)^{2}$
(17)

###  F.2 Relationship to the Policy Gradients

It is possible to drive the formulation that we use for the ranking
regularizer from the policy gradient theorem to show the relationship. The
Ranking Policy Gradient Theorem formulates the optimization of long-term
reward using a ranking objective as done in (Lin and Zhou, 2020). The
equations below illustrates the formulation process. Let us note that we apply
the ranking regularization on the offline and off-policy data, such that the
formalism below only works when the behavior policy and target policy are
equivalent, when the transitions are coming from on-policy data. If the
ranking regularizer is used on the on-policy data it approximates the policy
gradients, but it will not on the off-policy data.

Our construction is based on direct policy differentiation (Peters and Schaal,
2008; Williams, 1992) where the objective function is to
$\theta^{\ast}=\operatorname*{arg\,max}_{\theta}J({\theta})$ for
$p_{ij}=\text{sigmoid}\left(Q(s,a_{i})-Q(s,a_{j})\right)$.

$\displaystyle{\nabla}_{\theta}J({\theta})=$
$\displaystyle{\nabla}_{\theta}\sum_{\tau}\nolimits
p_{\theta}(\tau)\hat{V}^{\pi_{{\cal B}}}(s)$ (18) $\displaystyle=$
$\displaystyle\sum_{\tau}\nolimits p_{\theta}(\tau){\nabla}_{\theta}\log
p_{\theta}(\tau)\hat{V}^{\pi_{{\cal B}}}(s)$ $\displaystyle=$
$\displaystyle\sum_{\tau}\nolimits
p_{\theta}(\tau){\nabla}_{\theta}\log\left(p(s_{0})\Pi_{t=1}^{T}\pi_{\theta}(a_{t}|s_{t})p(s_{t+1}|s_{t},a_{t})\right)\hat{V}^{\pi_{{\cal
B}}}(s)$ $\displaystyle=$ $\displaystyle\sum_{\tau}\nolimits
p_{\theta}(\tau)\sum_{t=1}^{T}\nolimits{\nabla}_{\theta}\log\pi_{\theta}(a_{t}|s_{t})\hat{V}^{\pi_{{\cal
B}}}(s)$ $\displaystyle=$
$\displaystyle\mathbb{E}_{\tau\sim\pi_{\theta}}\left[\sum_{t=1}^{T}\nolimits{\nabla}_{\theta}\log\pi_{\theta}(a_{t}|s_{t})\hat{V}^{\pi_{{\cal
B}}}(s)\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}_{\tau\sim\pi_{\theta}}\left[\sum_{t=1}^{T}\nolimits{\nabla}_{\theta}\log\left(\prod\nolimits_{j=1,j\neq
i}^{m}p_{ij}\right)\hat{V}^{\pi_{{\cal B}}}(s)\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}_{\tau\sim\pi_{\theta}}\left[\sum_{t=1}^{T}\nolimits{\nabla}_{\theta}\sum_{j=1,j\neq
i}^{m}\nolimits\log\left(\text{sigmoid}(p_{ij})\right)\hat{V}^{\pi_{{\cal
B}}}(s)\right]$ (19) $\displaystyle=$
$\displaystyle-\mathbb{E}_{\tau\sim\pi_{\theta}}\left[\sum_{t=1}^{T}\nolimits{\nabla}_{\theta}\sum_{j=1,j\neq
i}^{m}\nolimits\text{softplus}(p_{ji})\hat{V}^{\pi_{{\cal B}}}(s)\right]$
$\displaystyle\approx$
$\displaystyle-\mathbb{E}_{\tau\sim\pi_{\theta}}\left[\sum_{t=1}^{T}\nolimits{\nabla}_{\theta}\left(\sum_{j=1,j\neq
i}^{m}\nolimits\max\left(Q(s,a_{i})-Q(s,a_{j}),0\right)\right)\hat{V}^{\pi_{{\cal
B}}}(s)\right],$ (20)

with baseline $\mathbb{E}_{s\sim{\cal D}}[\hat{V}^{\pi_{{\cal B}}}(s)]$ it
will be,

$\displaystyle\approx$
$\displaystyle-\mathbb{E}_{\tau\sim\pi_{\theta}}\left[\sum_{t=1}^{T}\nolimits{\nabla}_{\theta}\left(\sum_{j=1,j\neq
i}^{m}\nolimits\max\left(Q(s,a_{i})-Q(s,a_{j},0)\right)\right)\left(\hat{V}^{\pi_{{\cal
B}}}(s)-\mathbb{E}_{s\sim{\cal D}}[\hat{V}^{\pi_{{\cal B}}}(s)]\right)\right]$
(21)

Then we apply the $\exp(\cdot)$ transformation on $(\hat{V}^{\pi_{{\cal
B}}}(s)-\mathbb{E}_{s\sim{\cal D}}[\hat{V}^{\pi_{{\cal B}}}(s)]$ to impose
this loss loss mostly on the rewarding trajectories, and we can turn the
maximization problem to a minimization one with a flip of sign:

$\displaystyle=$
$\displaystyle\mathbb{E}_{\tau\sim\pi_{\theta}}\left[\sum_{t=1}^{T}\nolimits{\nabla}_{\theta}\left(\sum_{j=1,j\neq
i}^{m}\nolimits\max\left(Q(s,a_{i})-Q(s,a_{j}),0\right)\right)\exp\left(\hat{V}^{\pi_{{\cal
B}}}(s)-\mathbb{E}_{s\sim{\cal D}}[\hat{V}^{\pi_{{\cal B}}}(s)]\right)\right]$
(22)

where the trajectory is a series of state-action pairs from $t=1,...,T$, i.e.
$\tau=\left(s_{1},a_{1},s_{2},a_{2},...,s_{T}\right)$. The gradients in
equation 22 would exactly be the gradients of the ranking regularization.