# Why Should I Trust You, Bellman?
The Bellman Error is a Poor Replacement for Value Error

Scott Fujimoto  David Meger  Doina Precup  Ofir Nachum  Shixiang Shane Gu

###### Abstract

In this work, we study the use of the Bellman equation as a surrogate
objective for value prediction accuracy. While the Bellman equation is
uniquely solved by the true value function over all state-action pairs, we
find that the Bellman error (the difference between both sides of the
equation) is a poor proxy for the accuracy of the value function. In
particular, we show that (1) due to cancellations from both sides of the
Bellman equation, the magnitude of the Bellman error is only weakly related to
the distance to the true value function, even when considering all state-
action pairs, and (2) in the finite data regime, the Bellman equation can be
satisfied exactly by infinitely many suboptimal solutions. This means that the
Bellman error can be minimized without improving the accuracy of the value
function. We demonstrate these phenomena through a series of propositions,
illustrative toy examples, and empirical analysis in standard benchmark
domains.

Machine Learning, ICML, Reinforcement Learning, Bellman, Policy Evaluation,
Off-Policy

##  1 Introduction

In reinforcement learning (RL), value functions are a measure of performance
of a target policy. Value functions are an important quantity in RL as they
can be used to inform decision-making. Consequently, many modern RL algorithms
rely on a value function in some capacity (Mnih et al., 2015; Gu et al., 2016;
Schulman et al., 2017; Fujimoto et al., 2018; Badia et al., 2020).

The Bellman equation is a fundamental relationship in RL which relates the
value of a state-action pair to the state-action pair that follows and is
uniquely satisfied over all state-action pairs by the true value function. The
existence of the Bellman equation suggests a straightforward approach to
approximate value function learning, where a function is trained to minimize
the Bellman error (the difference of both sides of the equation). The Bellman
equation has played a prominent role in many historically significant
approaches (Schweitzer & Seidmann, 1985; Baird, 1995; Bradtke & Barto, 1996;
Antos et al., 2008; Sutton et al., 2009), as well as the more modern family of
deep RL algorithms (Mnih et al., 2015; Lillicrap et al., 2015; Gu et al.,
2016; Hessel et al., 2018).

This work aims to better understand the relationship between the Bellman error
and the accuracy of value functions through theoretical analysis and empirical
study. We do so by focusing on the setting of policy evaluation, which
presents the task of learning the value function of a target policy with data
gathered from a possibly separate and unknown behavior policy. Policy
evaluation, which is a subcomponent of many RL algorithms, is an ideal setting
for evaluating value functions as it provides a clear metric of performance
(value error: the distance to the true value function) and provides
consistency across trials (via a fixed dataset and policy). Our key
discoveries are as follows:

The Bellman error is a poor replacement for value error. We find that given an
arbitrary value function, low Bellman error does not indicate low value error.
This problem is highlighted by experiments which show that value functions
trained to minimize the Bellman error directly (Baird, 1995) have lower
average Bellman error, but higher average value error, than value functions
trained by iterative methods (Ernst et al., 2005). This inverse relationship
holds even when evaluated over on-policy data (Figure 2), and only worsens
further with off-policy data (Table 1). We show that this breakdown between
Bellman error and value error is due to the following two phenomena.

The magnitude of the Bellman error hides bias. The Bellman error of a value
function is the difference between the value estimates on each side of the
Bellman equation. If the value error of these estimates share the same sign
(i.e. they are biased in the same direction), then they can cancel each other
out. As a result, biased value functions will have lower Bellman error than
unbiased value functions, even if they have the same absolute value error.

Missing transitions breaks the Bellman equation. The Bellman equation is meant
to consider the entire MDP and all state-action pairs. We show that when the
Bellman equation is instead evaluated over an incomplete dataset, it can be
satisfied exactly by infinitely many suboptimal solutions. It follows that
minimizing the Bellman error over a finite dataset is not guaranteed to
improve the accuracy of a value function. In our practical experiments, we
show that when trained with off-policy data, methods which directly reduce the
Bellman error find value functions that have near zero Bellman error, but
large value error, for any state-action pair in the dataset.

We demonstrate the existence of these phenomena through theoretical analysis,
toy examples (Section 3), and experimentation in standard benchmarks (Section
4). We find that these problems extend beyond carefully designed
counterexamples, as they are consistent across domains, and can appear in a
clear, and often extreme, manner while using common algorithms with standard
hyperparameters.

Our work highlights problems with using the Bellman error as a signal or
objective, particularly in the off-policy setting. We aim to provide a better
understanding of performance gaps in RL methods: “why does directly minimizing
the Bellman error perform poorly?” and Bellman equation-based loss functions:
“why does the loss function not correspond with performance?” Our findings
point to an underappreciation of the importance of finite data in widely used
objectives and we encourage the community to place a higher emphasis on
practical settings.

##  2 Background

Reinforcement learning (RL) is an optimization framework for tasks of a
sequential nature (Sutton & Barto, 1998). Typically, tasks are defined as a
Markov decision process ($\mathcal{S}$, $\mathcal{A}$, $\mathcal{R}$, $p$,
$d_{0}$, $\gamma$), with state space $\mathcal{S}$, action space
$\mathcal{A}$, reward function $\mathcal{R}$, transition dynamics $p$, initial
state distribution $d_{0}$, and discount factor $\gamma\in[0,1)$. Actions are
selected according to a policy $\pi$ (Puterman, 1994).

The performance of a policy is measured by its discounted return
$\mathbb{E}_{\pi}[\sum_{t}^{\infty}\gamma^{t}r(s_{t},a_{t})]$. Policy
evaluation is the task of approximating the value function
$Q^{\pi}(s,a)=\mathbb{E}_{\pi}[\sum_{t}^{\infty}\gamma^{t}r(s_{t},a_{t})|s_{0}=s,a_{0}=a]$
of a target policy, given samples from an arbitrary dataset. A fundamental
relationship regarding value functions is the Bellman equation (Bellman, 1957;
Sutton & Barto, 1998):

$Q^{\pi}(s,a)=\mathbb{E}_{r,s^{\prime}\sim p,a^{\prime}\sim\pi}\left[r+\gamma
Q^{\pi}(s^{\prime},a^{\prime})\right],$ (1)

which relates the value of the current state-action pair to an expectation
over the next state-action pair. Given an approximate value function $Q$
(distinguished from the true value function $Q^{\pi}$ by dropping the $\pi$
superscript) of a target policy $\pi$, we denote the Bellman error
$\epsilon(s,a)$:

$\epsilon_{Q}(s,a):=Q(s,a)-\mathbb{E}_{r,s^{\prime}\sim
p,a^{\prime}\sim\pi}\left[r+\gamma Q(s^{\prime},a^{\prime})\right].$ (2)

In policy evaluation, the main objective of interest is a loss (such as the
MSE or L1) over the value error $\Delta_{Q}(s,a)$, the distance of an
approximate value function $Q$ to the true value function $Q^{\pi}$ of the
target policy $\pi$:

$\Delta_{Q}(s,a):=Q(s,a)-Q^{\pi}(s,a).$ (3)

Value error is often unmeasurable, as the true value function $Q^{\pi}$ is
unobtainable without the underlying MDP. While both the Bellman error and the
value error are defined with respect to $Q$, for simplicity we drop the
subscript when the error terms are not in reference to a specific value
function.

A standard result is the Bellman equation is uniquely solved by the true value
function (Bertsekas & Tsitsiklis, 1996). This can be re-framed in terms of
Bellman and value error.

######  Proposition 1.

The Bellman error $\epsilon(s,a)=0$ for all state-action pairs
$(s,a)\in\mathcal{S}\times\mathcal{A}$, if and only if the value error
$\Delta(s,a)=0$ for all state-action pairs
$(s,a)\in\mathcal{S}\times\mathcal{A}$.

The Bellman equation can be used as an operator
$\mathcal{T}Q(s,a)=\mathbb{E}_{r,s^{\prime}\sim
p,a^{\prime}\sim\pi}\left[r+\gamma Q(s^{\prime},a^{\prime})\right]$, which
when applied repeatedly to any function over all state-action pairs will
converge to the true value function (Puterman, 1994).

######  Proposition 2.

Let $Q_{1},Q_{2}$ be value functions, where $Q_{2}=\mathcal{T}Q_{1}$.
$\max_{(s,a)}|\Delta_{Q_{2}}(s,a)|\leq\gamma\cdot\max_{(s,a)}|\Delta_{Q_{1}}(s,a)|$.

In instances where we cannot compute the Bellman error exactly, we can instead
use the temporal difference (TD) error $\delta(i)$, a sample-based
approximation to the Bellman error which is computed over a transition
$i:=(s,a,r,s^{\prime})$, $\delta(i):=Q(s,a)-(r+\gamma
Q(s^{\prime},a^{\prime}))$, where $a^{\prime}\sim\pi$ (Sutton, 1988). Note
that the expected TD error is the Bellman error
$\epsilon(s,a)=\mathbb{E}_{r,s^{\prime},a^{\prime}}[\delta(i)]$, where the two
errors are identical if the environment and policy are deterministic.

A related concept is the projected Bellman error (Sutton & Barto, 1998;
Patterson et al., 2022). Since a given function approximator (particularly
linear functions) may be unable to represent value functions with low Bellman
error, the projected Bellman error is a projection into the space that is
representable by the function approximator. In our work, we consider
expressive deep neural networks which can fully represent low Bellman error
solutions (as shown by our experiments in Section 4), allowing us to consider
the true Bellman error, and avoid the need for projections.

We focus largely on two algorithms based on the Bellman equation, which update
an approximate value function $Q$, using samples from a finite dataset
$\mathcal{D}$. Bellman residual minimization (BRM) (Baird, 1995) directly
minimizes the Bellman error over samples in the dataset $\mathcal{D}$:

$\mathcal{L}_{\text{BRM}}(Q):=\frac{1}{|\mathcal{D}|}\sum_{\mathcal{D}}(Q(s,a)-(r+\gamma
Q(s^{\prime},a^{\prime})))^{2}.$ (4)

Fitted Q-Evaluation (FQE) (Ernst et al., 2005; Le et al., 2019) is an
iterative method with a similar update:

$\mathcal{L}_{\text{FQE}}(Q):=\frac{1}{|\mathcal{D}|}\sum_{\mathcal{D}}(Q(s,a)-(r+\gamma\bar{Q}(s^{\prime},a^{\prime})))^{2}.$
(5)

The key distinction between the two algorithms is that BRM updates both
$Q(s,a)$ and $Q(s^{\prime},a^{\prime})$, while FQE only updates $Q(s,a)$. This
is because FQE uses $\bar{Q}(s^{\prime},a^{\prime})$, a fixed target value
function updated by $\bar{Q}\leftarrow Q$ after a set number of time steps
(possibly including every time step).

##  3 Bellman Error as a Proxy for Value Error

In this section, we analyze the relationship between the Bellman error and
value error. Recall the key idea behind the Bellman equation is that it is
uniquely satisfied by the true value function over all state-action pairs. In
policy evaluation, the Bellman error of an approximate value function,
computed over a set of state-action pairs, is used as a measurable proxy
objective to the value error, the typically unmeasurable, true objective.

While the Bellman error of the true value function is zero for all state-
action pairs, in this section we show that the magnitude of the Bellman error
of an approximate value function is only loosely related to the value error,
even when considering the entire MDP. We show this breakdown by highlighting
two fundamental problems with using the Bellman error as a surrogate for value
error.

###  3.1 (Infinite Data Analysis) Problem 1: The Magnitude of the Bellman
Error Hides Bias

The first problem is that the magnitude of the Bellman error is not guaranteed
to correspond with the magnitude of the value error. This is because the
Bellman error of a state-action pair is the difference between two values,
which means there can exist cancellations in error terms, resulting in
deceptively low Bellman error.

To see this cancellation, consider the following:

######  Observation 1.

(Bellman error as a function of value error). For any state-action pair
$(s,a)\in\mathcal{S}\times\mathcal{A}$, the Bellman error $\epsilon(s,a)$ can
be defined as a function of the value error $\Delta$

$\epsilon(s,a)=\Delta(s,a)-\gamma\mathbb{E}_{s^{\prime},\pi}[\Delta(s^{\prime},a^{\prime})].$
(6)

Which follows directly from the Bellman equation:

$\displaystyle\epsilon$ $\displaystyle(s,a)=Q(s,a)-\mathcal{T}Q(s,a)$ (7)
$\displaystyle=Q^{\pi}(s,a)+\Delta(s,a)-\mathcal{T}(Q^{\pi}(s,a)+\Delta(s,a))$
(8)
$\displaystyle=\Delta(s,a)-\gamma\mathbb{E}_{s^{\prime},\pi}[\Delta(s^{\prime},a^{\prime})].$
(9)

While this does mean that smaller value error terms (in magnitude) does result
in smaller Bellman error, the sign of the value error terms can have a much
larger impact. Keeping this relationship in mind, we can construct examples
where the correspondence between the magnitude of the Bellman error and value
error breaks down.

Example 1. (Same value error, different Bellman error). Let $Q^{\pi}$ be the
true value function for some MDP and policy $\pi$. We define the following
approximate value functions:

$\displaystyle Q_{1}=Q^{\pi}+1$ (error is correlated), (10) $\displaystyle
Q_{2}=Q^{\pi}\pm 1$ (error is uncorrelated), (11)

where $\pm 1$ is a random variable with equal probability of being positive or
negative. In both cases, the absolute value error will be $1$ for any state-
action pair. However, following Observation 1, for all state-action pairs, the
Bellman error of $Q_{1}$ will be $1-\gamma$, while the expected absolute
Bellman error of $Q_{2}$ will be much larger at $|\pm 1-\gamma\mathbb{E}[\pm
1]|=1$.

Example 2. (Same Bellman error, different value error). Suppose instead that
we define $Q_{1}=Q^{\pi}+\frac{1}{1-\gamma}$. Then by Observation 1, the
expected absolute Bellman error of $Q_{1}$ and $Q_{2}$ will both be $1$ for
any state-action pair, but the value error of $Q_{1}$ will be
$\frac{1}{1-\gamma}$. For a common $\gamma=0.99$ and any state-action pair
this would make the value error of $Q_{1}$ be $100$, compared to the value
error of $Q_{2}$ at $1$.

In fact, we can also define $Q_{1}$ and $Q_{2}$ such that the magnitude of the
Bellman error and value error appear inversely correlated.

######  Proposition 3.

(An inverse relationship between Bellman error and value error). For any MDP,
discount factor $\gamma\in(0,1)$, and $C>0$, we can define a value function
$Q_{1}$ and a stochastic value function $Q_{2}$ such that for any state-action
pair $(s,a)\in\mathcal{S}\times\mathcal{A}$

  1. 1.

$|\Delta_{Q_{1}}(s,a)|-|\Delta_{Q_{2}}(s,a)|>C$,

  2. 2.

$\mathbb{E}_{Q_{2}}[|\epsilon_{Q_{2}}(s,a)|]-|\epsilon_{Q_{1}}(s,a)|>C$.

This means that when comparing value functions, lower absolute Bellman error
over all state-action pairs does not guarantee lower value error for any
state-action pair.

However, there does exist a relationship between the value error of a given
state-action pair, and the Bellman error of all relevant state-action pairs of
an MDP. Let $d^{\pi}(s^{\prime},a^{\prime}|s,a)$ be the conditional discounted
state-action occupancy
$(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}p^{\pi}((s,a)\rightarrow
s^{\prime},t)\pi(a^{\prime}|s^{\prime})$, where $p^{\pi}((s,a)\rightarrow
s^{\prime},t)$ is the probability of leaving the state-action pair $(s,a)$ and
visiting the state $s$ after $t$ time steps.

######  Theorem 1.

(Value error as a function of Bellman error). For any state-action pair
$(s,a)\in\mathcal{S}\times\mathcal{A}$, the value error $\Delta(s,a)$ can be
defined as a function of the Bellman error $\epsilon$

$\Delta(s,a)=\frac{1}{1-\gamma}\mathbb{E}_{(s^{\prime},a^{\prime})\sim
d^{\pi}(\cdot|s,a)}[\epsilon(s^{\prime},a^{\prime})].$ (12)

Theorem 1 provides an upper bound on the absolute value error by considering
the expected absolute Bellman error of future state-action pairs (according to
$d^{\pi}$)

$|\Delta(s,a)|\leq\frac{1}{1-\gamma}\mathbb{E}_{(s^{\prime},a^{\prime})\sim
d^{\pi}(\cdot|s,a)}[|\epsilon(s^{\prime},a^{\prime})|].$ (13)

Since the right-hand side of this bound corresponds to the on-policy Bellman
residual minimization objective with a L1 loss, this shows how the magnitude
of on-policy Bellman error can be used as an objective for policy evaluation.
However, we remark that this also highlights how the absolute Bellman error
can correspond to a wide range of possible value error terms by also
considering the lower bound. Let $d^{\pi}$ be the expected discounted state-
action occupancy $\mathbb{E}_{s_{0}}[d^{\pi}(s,a|s_{0})]$ over the initial
state distribution.

######  Proposition 4.

(Bounds on value error). Let $C_{\text{max}}=\max_{s,a}|\epsilon(s,a)|$ and
$C_{\text{avg}}=\mathbb{E}_{(s,a)\sim d^{\pi}}[|\epsilon(s,a)|]$.

  1. 1.

$\frac{C_{\text{max}}}{1+\gamma}\leq\max_{s,a}|\Delta(s,a)|\leq\frac{C_{\text{max}}}{1-\gamma}$,

  2. 2.

$\frac{C_{\text{avg}}}{1+\gamma}\leq\mathbb{E}_{(s,a)\sim
d^{\pi}}[|\Delta(s,a)|]\leq\frac{C_{\text{avg}}}{1-\gamma}$,

Furthermore, for any MDP and policy, there exists a value function such that
the upper bound is an equality, and there exists a MDP, policy, and value
function such that the lower bound is an equality.

Similarly to Example 2, Proposition 4 says that if the average absolute
Bellman error is $1$, and the discount factor $\gamma=0.99$, then the average
value error will fall somewhere between $\approx 0.5$ and $100$. Consequently,
this wide range of value error suggests that it is difficult to make
meaningful comparisons between value functions using the magnitude of the
Bellman error alone.

$s_{0}$$s_{1}$$a$$a$ Figure 1: A basic MDP. If $(s_{0},a)$ is contained in the
dataset but $(s_{1},a)$ is not, by selecting the values $Q(s_{0},a)$ and
$Q(s_{1},a)$, we can construct examples where the Bellman error over the
dataset is $0$, but the value error is arbitrarily large, and vice-versa.

###  3.2 (Finite Data Analysis) Problem 2: Missing Transitions Breaks the
Bellman Equation

A direct consequence of Theorem 1 is the uniqueness property of the Bellman
equation. That is, if the Bellman error is $0$ for all relevant state-action
pairs which may be visited by the target policy, then the value error must
also be $0$ for these state-action pairs. However, if we examine a finite
dataset instead of the entire MDP, this relationship also highlights that if
any relevant transitions are missing, the Bellman equation, evaluated over the
dataset, will no longer have a unique solution. This means that when
considering a finite dataset, there can exist infinitely many suboptimal
solutions which satisfy the Bellman equation exactly.

######  Corollary 1.

(The Bellman equation is not unique over incomplete datasets). If there exists
a state-action pair $(s^{\prime},a^{\prime})$ not contained in the dataset
$\mathcal{D}$, where the state-action occupancy
$d^{\pi}(s^{\prime},a^{\prime}|s,a)>0$ for some $(s,a)\in\mathcal{D}$, then
there exists a value function and $C>0$ such that

  1. 1.

For all $(\hat{s},\hat{a})\in\mathcal{D}$, the Bellman error
$\epsilon(\hat{s},\hat{a})=0$.

  2. 2.

There exists $(s,a)\in\mathcal{D}$, such that the value error $\Delta(s,a)=C$.

We can find examples of this phenomenon in very simple MDPs. Consider the two-
state MDP defined in Figure 1, with reward $r=0$ for all state-action pairs.
If the dataset contains the sole transition $(s_{0},a,r,s_{1})$, then we can
construct examples where for all transitions in the dataset (the sole
transition in this instance) the Bellman error is $0$ but the value error is
arbitrarily large, and conversely, where the Bellman error is arbitrarily
large but the value error is $0$.

Example 1. ($0$ Bellman error, $C$ value error). Since the reward is $0$
everywhere, the true value of any state-action pair must be $0$. However, by
choosing the value of the missing transition $Q(s_{1},a)$ to cancel with the
value of the transition in the dataset $Q(s_{0},a)$, the Bellman error of the
sole state-action pair in the dataset is $0$.

$\begin{aligned} Q(s_{0},a)&=C,\\\
Q(s_{1},a)&=\textstyle\frac{1}{\gamma}C.\end{aligned}\implies\begin{aligned}
\epsilon(s_{0},a)&=C-\gamma\textstyle\frac{1}{\gamma}C=0,\\\
\Delta(s_{0},a)&=Q(s_{0},a)=C.\end{aligned}$ (14)

Example 2. ($C$ Bellman error, $0$ value error). Similarly, we can set the
value of the state-action pair in the dataset $Q(s_{0},a)$ to be the correct
value of $0$, and instead choose the value of the missing state-action pair
$Q(s_{1},a)$ to make the Bellman error of $(s_{0},a)$ equal $C$.

$\begin{aligned} Q(s_{0},a)&=0,\\\
Q(s_{1},a)&=-\textstyle\frac{1}{\gamma}C.\end{aligned}\implies\begin{aligned}
\epsilon(s_{0},a)&=0+\gamma\textstyle\frac{1}{\gamma}C=C,\\\
\Delta(s_{0},a)&=Q(s_{0},a)=0.\end{aligned}$ (15)

Note that these examples do not involve modifying the environment in an
extreme adversarial manner, and instead occur due to the value estimate of the
missing state-action pair. As a result, methods which directly minimize the
Bellman error may influence target values to achieve low Bellman error over
the dataset without necessarily improving the value function. Even when the
target value is not directly modified, scenarios such as 3.2, where the
current and missing values are similar, can cause deceptively low Bellman
error, without an accurate value function.

BRM  FQE  MC

Figure 2: Can the on-policy Bellman error be used as a proxy for value error?
We compare the mean squared Bellman error (top row) with the normalized
absolute value error (bottom row) of learning curves of value functions
trained with a dataset of 1m on-policy transitions. While clearly the Bellman
error is lowest for  BRM (which directly minimizes Bellman error) followed by
FQE (which indirectly minimizes Bellman error) followed by  MC (which
minimizes the Monte-Carlo estimate of value error), this ordering is not
reflected in value error. This shows overfitting of the Bellman error
objective is possible even with on-policy data and that we cannot determine
value prediction accuracy by examining the magnitude of Bellman error alone.

BRM  FQE  MC

|  Mean $|\text{BE}|$ |  Mean $|\text{VE}|$ |  Ratio $(\sum|\text{VE}|/\sum|\text{BE}|)$
---|---|---|---
BRM | 0.41 | 23.39 | 56.93
FQE | 0.76 | 8.89 | 11.72
MC | 2.76 | 2.75 | 1.00

Figure 3: Does bias explain the non-correspondence between the Bellman error
and value error? We train value functions over a single on-policy trajectory
in the HalfCheetah environment (1000 transitions, with termination). As a
result, every relevant transition is contained in the dataset. We display the
Bellman error (left) and unnormalized value error (right) for every transition
in the trajectory. In the table, we record the average absolute Bellman error
(BE), value error (VE), and ratio between these terms. By Proposition 4, with
a discount $\gamma=0.99$, the ratio between mean absolute Bellman and value
error is bounded by $[0.503,100]$. Our results show that both the upper and
lower bound can be approached in practice. Visually, we can see that the
magnitude of the Bellman error is influenced more by the clusters of similar
value error (size and direction) for  BRM and  FQE than the magnitude of the
value error. This experiment is repeated with different domains in Appendix
A.3.

##  4 Experiments

Everything we have discussed thus far has suggested that the Bellman error may
not be a representative surrogate for value error. We now examine if these
problems occur in practice. Recall our main observations are (1) the magnitude
of the Bellman error is smaller for biased value functions due to
cancellations caused from both sides of the Bellman equation (Section 3.1) and
(2) the relationship between Bellman error and value error is broken if the
dataset is missing relevant transitions (Section 3.2). We find that both of
these concerns exist clearly in standard benchmark environments.

Our experiments also demonstrate the effectiveness of Fitted Q-Evaluation
(FQE) (Ernst et al., 2005; Le et al., 2019) as a policy evaluation method,
irrespective of its tendency to find value functions with high Bellman error.
While FQE is also based on the Bellman equation, we argue that its objective
is not to directly minimize the Bellman error, but rather to imitate the
Bellman operator, meaning that low error to an accurate target can be a more
important factor than the Bellman error (Section 4.4).

###  4.1 Experimental Design

We first outline the experimental choices used in our empirical evaluation.
Our experiments consider the setting of policy evaluation. Comprehensive
details can be found in Appendix E. The task can be broken down as follows:

  1. 1.

The target policy is generated from an off-the-shelf RL algorithm.

  2. 2.

The behavior policy collects a training and test dataset.

  3. 3.

The value function is trained using the dataset, target policy, and policy
evaluation algorithm.

  4. 4.

Metrics of the value function are computed over the test dataset.

Policies. The target policy is an expert deterministic policy from a fully
trained TD3 agent (Fujimoto et al., 2018). The behavior policy is a noisy
version of the target policy. Each dataset is assigned a noise value
corresponding to both the probability of selecting a uniformly random action,
as well as the standard deviation of Gaussian noise added to the actions
(noting that actions are normalized to be in the range $[-1,1]$). We use
uniformly random actions to ensure that not all actions in the dataset are
centered around the target policy, and Gaussian noise to ensure that every
action is distinct from actions selected by the target policy. The on-policy
behavior is generated without noise.

Algorithms. We use Bellman residual minimization (BRM) (Baird, 1995), Fitted
Q-Evaluation (FQE) (Ernst et al., 2005; Le et al., 2019), and Monte Carlo
estimates (MC) (Sutton & Barto, 1998). We use these algorithms due to their
prevalence in the literature, and to highlight differences between methods
which minimize the Bellman error, directly (BRM) or indirectly (FQE), and
methods which minimize value error (MC).

Metrics. We compare the mean squared Bellman error, due to its common use
(Baird, 1995; Sutton & Barto, 1998), with the absolute value error. For better
interpretability across tasks, we normalize the value error by dividing by a
constant term equal to the average true value function sampled on-policy. The
true value function is estimated with on-policy rollouts from the target
policy. In Appendix D.1 we report results with variations of these metrics.

Environments. Our experiments consider standard benchmark continuous-action
tasks through the MuJoCo simulator (Todorov et al., 2012; Brockman et al.,
2016), as it is deterministic and high-dimensional. Determinism in the
dynamics is desirable as it, alongside a deterministic policy, makes the TD
error identical to the Bellman error. This means we can compute the Bellman
error exactly and ignore the double sampling issue (Baird, 1995).

###  4.2 The On-Policy Bellman Error is a Poor Metric

In Section 3.1, we showed that it is possible for a biased value function to
have lower Bellman error over all possible state-action pairs, while having
higher value error, than an unbiased value function. In this section we show
that this problem exists in practical settings. This means that the magnitude
of Bellman error is a poor metric for comparing value functions, even when
working with on-policy data.

We begin by comparing the Bellman error and the value error of value functions
trained, and evaluated, with on-policy data. The results are displayed in
Figure 2.

Methods which minimize the Bellman error have lower Bellman error. BRM
directly minimizes the Bellman error, FQE uses an iterative approach based on
the Bellman equation, and MC does not use the Bellman equation in its
objective. Therefore it is unsurprising that in Figure 2, the value functions
trained by BRM have the lowest average Bellman error, followed by FQE, and
then MC.

Lower Bellman error does not mean lower value error. Although the value
functions trained by FQE and MC have much higher average absolute Bellman
error over the on-policy dataset (especially in Ant and Humanoid) than BRM,
the value functions trained by BRM typically have the highest average value
error. The learning curves in Figure 2 demonstrate that it is possible to find
value functions where the relative ordering in Bellman error is not respected
by the relative ordering in value error, even when working with large (1M) on-
policy datasets.

Methods which minimize the Bellman error have correlated error (and thereby
have a higher ratio of value error to Bellman error). To better understand the
importance of bias in minimizing the Bellman error, we train value functions
over a single trajectory. This allows us to consider a dataset without missing
transitions and examine the error terms of every transition in the trajectory.
We display the results in Figure 3. As the Bellman error is determined by the
difference between the value error of the current and succeeding state
(Observation 1), Figure 3 shows the magnitude of the Bellman error is
influenced more by correlated bias than the magnitude the value error.

Algorithm | Dataset | HalfCheetah | Hopper | Walker2d | Ant | Humanoid
---|---|---|---|---|---|---
|  | BE | VE |  | BE | VE |  | BE | VE |  | BE | VE |  | BE | VE |
BRM | On-Policy | 0.96 | 0.03 | ✓ | 0.17 | 0.08 | ✓ |  < 0.01 |  < 0.01 | ✓ | 2.54 | 0.16 | ✓ | 1.11 | 0.06 | ✓
0.1 | 2.02 | 0.36 |  | 3.50 | 0.47 |  | 2.10 | 0.37 |  | 5.36 | 0.81 |  | 0.53 | 0.69 |
0.2 | 0.70 | 0.47 |  | 1.86 | 0.61 |  | 1.07 | 0.45 |  | 1.27 | 0.68 |  | 0.28 | 0.80 |
0.3 | 0.34 | 0.49 |  | 1.11 | 0.62 |  | 0.55 | 0.43 |  | 0.63 | 0.62 |  | 0.16 | 0.70 |
0.4 | 0.18 | 0.48 |  | 1.08 | 0.60 |  | 0.33 | 0.41 |  | 0.38 | 0.62 |  | 0.13 | 0.63 |
0.5 | 0.09 | 0.50 |  | 0.23 | 0.63 |  | 0.26 | 0.43 |  | 0.35 | 0.56 |  | 0.07 | 0.63 |
FQE | On-Policy | 38.96 | 0.03 | ✓ | 0.09 | 0.01 | ✓ | 0.05 |  < 0.01 | ✓ | 37.95 | 0.11 | ✓ | 45.58 | 0.02 | ✓
0.1 | 1375.71 | 0.13 | ✓ | 17.56 | 0.03 | ✓ | 88.75 | 0.04 | ✓ | 838.39 | 0.11 | ✓ | 137.83 | 0.03 | ✓
0.2 | 2441.75 | 0.12 | ✓ | 57.24 | 0.05 | ✓ | 147.77 | 0.07 | ✓ | 984.95 | 0.14 | ✓ | 342.16 | 0.06 | ✓
0.3 | 1219.08 | 0.18 |  | 95.72 | 0.07 | ✓ | 113.13 | 0.11 |  | 708.50 | 0.19 | ✓ | 633.68 | 0.09 | ✓
0.4 | 244.47 | 0.21 |  | 214.92 | 0.40 |  | 139.46 | 0.12 |  | 522.05 | 0.26 |  | 575.56 | 0.09 | ✓
0.5 | 144.04 | 0.25 |  | 169.78 | 0.22 |  | 35.38 | 0.21 |  | 343.37 | 0.30 |  | 483.69 | 0.10 | ✓
Table 1: Is the Bellman error an effective off-policy objective? We display
the final mean squared Bellman error (BE) and the final normalized absolute
value error (VE) of functions trained with datasets gathered by increasingly
noisy versions of the target policy. The value of the dataset refers to the
noise level. ✓ is used to mark if performance is within $0.1$ normalized value
error of the on-policy value error. FQE consistently outperforms BRM while
having significantly higher Bellman error, particularly when off-policy.
Additionally, while the value error of BRM increases substantially from on-
policy to off-policy datasets, the Bellman error remains low for all datasets,
showing that it is possible to train a function with low Bellman error,
regardless of its accuracy with respect to the true value function.

The Bellman error is a valid on-policy objective. In Appendix A.1 we display
the correlation coefficient between the average absolute Bellman error and
value error, when isolating functions by the algorithm which trained them. We
find that when the error terms are evaluated on-policy, there is a strong
correlation between the error terms for a fixed algorithm. This corroborates
with Equation 13 which shows that the expected absolute Bellman error of on-
policy samples upper bounds value error, and suggests that when we isolate by
algorithm, value functions are biased similarly. This means that even if the
Bellman error is a poor metric for comparison, the Bellman error can be a
usable objective for on-policy evaluation and explains the decent value
prediction accuracy of BRM in Figure 2.

Variations of the Bellman error as a metric. In Section 3.1, we showed the
magnitude of the Bellman error hides bias and is therefore a poor metric for
comparing value functions. Conceivably, one could incorporate a measure of
bias into the Bellman error. For example, following Theorem 1, the exact value
error can be computed from on-policy data. However, when working with
incomplete datasets we can always find functions which have zero Bellman error
and arbitrarily high value error for any state-action pair in the dataset
(Corollary 1). Consequently, there cannot exist a metric without failure cases
for finite off-policy datasets.

###  4.3 The Off-Policy Bellman Error is a Poor Objective

In the previous section, we showed that the Bellman error cannot be used to
rank arbitrary value functions according to their accuracy. Regardless, the
on-policy accuracy of BRM is competitive (albeit weaker) with FQE and MC. This
suggests the possibility that the Bellman error could be used as an objective
for off-policy evaluation as well, irrespective of its shortcomings as a
metric. In this section we show that this is not the case: the Bellman error
makes for a poor off-policy objective.

Recall in Section 3.2 we showed that if there are missing transitions in the
dataset, the Bellman equation can be satisfied exactly by infinitely many
suboptimal solutions. This is largely a problem for finite datasets generated
off-policy, as they are guaranteed to be missing relevant transitions.
Consequently, the Bellman error, evaluated over an off-policy dataset, should
not be a meaningful objective for policy evaluation. In Table 1 we confirm
this observation, by repeating the policy evaluation experiment from the
previous section with various off-policy datasets.

The Bellman error is an ineffective off-policy objective. Table 1 shows the
performance of BRM suffers a clear drop when moving to the off-policy
datasets. Furthermore, despite this performance drop, the average Bellman
error of value functions trained by BRM remains low for all datasets, which
shows that the empirical Bellman error, evaluated over an off-policy dataset,
can be optimized independently of value error. Moreover, we remark that our
experiments are in deterministic domains, and as such, this problem is
independent from the double sampling problem with BRM (Baird, 1995). These
results support our theoretical analysis (Corollary 1) which showed that with
missing transitions, the Bellman error is no longer guaranteed to relate to
value error.

We also include results of the FQE algorithm on these datasets. While FQE also
suffers in performance with additional noise added to the behavior policy,
this performance drop is much less drastic. On every off-policy dataset, FQE
outperforms BRM, and in some instances, even outperforms BRM trained with the
on-policy dataset. The success of FQE shows that the failure of BRM is due to
its objective (of Bellman error), rather than the difficulty of the task.

###  4.4 Additional Insights about FQE

The success of FQE for policy evaluation is supported by many examples in the
literature (Voloshin et al., 2021; Fu et al., 2021; Fujimoto et al., 2021), as
well as control (Mnih et al., 2015; Lillicrap et al., 2015; Hessel et al.,
2018). The results in the previous sections may raise new questions
surrounding the performance, and behavior, of FQE.

Does FQE provide a better metric? In Appendix A.2 we examine the relationship
of the FQE loss function to value error. This loss bears no closer
relationship to value error than the Bellman error does. This is not
contradictory to the success of FQE because the objective is iterative and
evolves during training. We can interpret the objective of FQE as an
application of the Bellman operator, where the Bellman equation is used to
construct a regression target, rathar than a minimization of the Bellman
error. This means that FQE does not provide a better metric than the Bellman
error, only a better optimization process.

How does FQE handle missing data? The success of FQE is best understood as the
repeated application of the Bellman operator. Recall the Bellman operator,
applied globally to every state-action pair, ensures a reduction in the max
value error (Proposition 2). We can instead consider the Bellman operator
applied over a finite dataset $\mathcal{D}$.

######  Proposition 5.

(FQE improvement condition). Let $Q_{1},Q_{2}$ be value functions, where
$Q_{2}=\mathcal{T}Q_{1}$. If
$\gamma\cdot\max_{(s,a)\in\mathcal{D}}|\mathbb{E}_{(s^{\prime},a^{\prime})\sim
p(\cdot|s,a),\pi}[\Delta_{Q_{1}}(s^{\prime},a^{\prime})]|<\max_{(s,a)\in\mathcal{D}}|\Delta_{Q_{1}}(s,a)|$
then
$\max_{(s,a)\in\mathcal{D}}|\Delta_{Q_{2}}(s,a)|<\max_{(s,a)\in\mathcal{D}}|\Delta_{Q_{1}}(s,a)|$.

Informally, Proposition 5 says that if the target used by FQE is sufficiently
accurate relative to the accuracy of the value function over state-action
pairs in the dataset, then an iteration of FQE will improve the value estimate
over the dataset. This means that FQE can overcome missing data through
generalization and explains the strong performance of FQE in some of the off-
policy settings in Table 1. BRM on the other hand, inhibits generalization in
the target, as the target can be directly modified to reduce Bellman error,
which can result in overfitting.

FQE relies on generalization during training. While the importance of
generalization to FQE is a simple observation, it has significant
implications. Firstly, this means the Bellman equation requires generalization
during training. This is distinct from typical machine learning settings,
where generalization is an exercise which occurs after training. This is
problematic because if it is difficult to ensure good generalization after
training, it is only more difficult to ensure good generalization during
training. This highlights the importance of feature learning (Jaderberg et
al., 2016; Yang & Nachum, 2021), as neural network features are unlikely to be
relevant early in training.

Another implication is hyperparameter sensitivity. It is a well known problem
that RL algorithms are sensitive to small adjustments (Henderson et al., 2017;
Engstrom et al., 2019). A necessity of generalization at training time causes
the significance of correct hyperparameters to be amplified.

##  5 Related Work

The role of the Bellman error has been considered in depth in the literature,
in the context of bounds on the performance of a greedy policy in relation to
the norm of the Bellman error (Williams & Baird, 1993; Singh & Yee, 1994;
Bertsekas & Tsitsiklis, 1996; Heger, 1996; Munos, 2003, 2007; Farahmand et
al., 2010).

In a similar vein to our work, Kolter (2011) remarks that with off-policy
sampling, the projected solution to linear TD can have arbitrarily large
Bellman error, but focuses on the approximate fixed point, rather than any
discrepancy between Bellman error and value error. Geist et al. (2017)
evaluate the Bellman error as an objective for policy optimization. Although
they examine a different setting, they arrive at a related conclusion, the
signal from the Bellman error is only meaningful if the sampling distribution
corresponds to the optimal policy.

The Bellman error has additional concerns that our paper does not discuss. The
double sampling problem (Baird, 1995) is that the gradient of the Bellman
error is biased if estimated from a single transition in a stochastic MDP. The
double sampling issue provides motivation for many recent BRM methods (Feng et
al., 2019; Zhu & Ying, 2020; Zhang et al., 2020; Bas-Serrano et al., 2021). We
avoid this issue in our analysis by focusing on deterministic environments,
but remark that BRM is likely to perform worse with stochasticity. Sutton &
Barto (1998) show that in scenarios where the representation of states is not
uniquely defined, there exist examples where the Bellman error is not
learnable, as the structure of the MDP can not be determined from data alone,
and thus the true Bellman error cannot be computed.

The success of FQE is supported by many examples in the literature for off-
policy evaluation tasks (Voloshin et al., 2021; Fu et al., 2021; Fujimoto et
al., 2021), as well as control applications with deep RL (Mnih et al., 2015;
Lillicrap et al., 2015; Hessel et al., 2018). Our results help explain the
effectiveness of FQE, but also highlights challenge of the importance of
generalization during training.

Our observations connect strongly to offline RL (Lange et al., 2012; Levine et
al., 2020), where offline policy evaluation is used in conjunction with policy
learning. Previous work has observed that the value function of FQE methods
can diverge when computed offline due to poor estimates in the target
(Fujimoto et al., 2019b, a). Similar to our work, empirical properties of deep
value functions which induce instability or divergence have been studied (Fu
et al., 2019; Achiam et al., 2019) but have not considered the role of the
objective itself. Several recent papers examined the sample complexity of
offline RL, noting that without access to on-policy data, the number of
necessary transitions is exponential with respect to the horizon (Wang et al.,
2020; Zanette, 2021; Chen et al., 2021; Xiao et al., 2021).

In the context of offline model selection, several papers have observed that
TD error is a weak baseline with poor correspondence to policy performance,
remarking that it is a measure of value function accuracy rather than quality
of the policy, but provide little analysis (Irpan et al., 2019; Paine et al.,
2020; Tang & Wiens, 2021). Our findings help explain these results by showing
that Bellman (and TD) error are not an effective measure of value accuracy,
and cannot rank models, even with on-policy data. These empirically minded
observations caution against traditional results which suggest Bellman error
as a metric for model selection (Farahmand & Szepesvári, 2011).

##  6 Conclusion

In this paper, we study the effectiveness of the Bellman error as a proxy for
value error. We focus on two problems. Firstly, the magnitude of the Bellman
error is lower for biased value functions, as there are cancellations for
temporally correlated error terms. This means that the magnitude of the
Bellman error is not viable metric for selecting functions with lower value
error, even when considering all state-action pairs. Secondly, the Bellman
equation is only uniquely solved by the true value function when computed over
the entire MDP. When working with finite or incomplete datasets, we show there
exists infinitely many suboptimal value functions which satisfy the Bellman
equation. This means the Bellman error is not a viable objective over
incomplete datasets, such as the off-policy setting.

We demonstrate these problems theoretically, with toy problems, and
empirically on standard benchmark environments. The lack of correlation
between Bellman error and value error is highlighted by an empirical
comparison between Bellman Residual Minimization (BRM) (Baird, 1995) and
Fitted Q-Evaluation (FQE) (Ernst et al., 2005; Le et al., 2019), which shows
that value functions trained with BRM consistently have much lower Bellman
error, but much higher value error than value functions trained with FQE.

While much of the modern literature surrounding Bellman error minimization
emphasizes the double sampling problem (Dai et al., 2018; Feng et al., 2019;
Saleh & Jiang, 2019; Bas-Serrano et al., 2021), our analysis shows much more
fundamental problems; Bellman error is not guaranteed to closely correspond
with value error and solving the Bellman equation over a finite dataset does
not guarantee an accurate value function. While such problems may be alluded
to in prior work (Kolter, 2011; Geist et al., 2017; Irpan et al., 2019), to
the best of our knowledge we are the first to formalize theorems and
propositions in both infinite and finite data regimes, list out illustrative
examples, and evaluate empirically on practical settings. We hope our findings
provide a better understanding of Bellman equation-based objectives to both
practitioners and theorists alike.

## Acknowledgements

Scott Fujimoto is supported by a NSERC scholarship. We would like to thank
Dale Schuurmans, Pablo Samuel Castro, Esther Ugolini, Edward Smith, and Wei-Di
Chang for helpful feedback and discussions.

## References

  * Achiam et al. (2019) Achiam, J., Knight, E., and Abbeel, P.  Towards characterizing divergence in deep q-learning.  _arXiv preprint arXiv:1903.08894_ , 2019.
  * Antos et al. (2008) Antos, A., Szepesvári, C., and Munos, R.  Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path.  _Machine Learning_ , 71(1):89–129, 2008.
  * Badia et al. (2020) Badia, A. P., Piot, B., Kapturowski, S., Sprechmann, P., Vitvitskyi, A., Guo, Z. D., and Blundell, C.  Agent57: Outperforming the atari human benchmark.  In _International Conference on Machine Learning_ , pp. 507–517. PMLR, 2020.
  * Baird (1995) Baird, L.  Residual algorithms: Reinforcement learning with function approximation.  In _Machine Learning Proceedings 1995_ , pp. 30–37. Elsevier, 1995\.
  * Bas-Serrano et al. (2021) Bas-Serrano, J., Curi, S., Krause, A., and Neu, G.  Logistic q-learning.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 3610–3618. PMLR, 2021.
  * Bellman (1957) Bellman, R.  _Dynamic Programming_.  Princeton University Press, 1957.
  * Bertsekas & Tsitsiklis (1996) Bertsekas, D. P. and Tsitsiklis, J. N.  _Neuro-Dynamic Programming_.  Athena scientific Belmont, MA, 1996.
  * Bradtke & Barto (1996) Bradtke, S. J. and Barto, A. G.  Linear least-squares algorithms for temporal difference learning.  _Machine learning_ , 22(1):33–57, 1996.
  * Brockman et al. (2016) Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W.  Openai gym, 2016.
  * Chen et al. (2021) Chen, L., Scherrer, B., and Bartlett, P. L.  Infinite-horizon offline reinforcement learning with linear function approximation: Curse of dimensionality and algorithm.  _arXiv preprint arXiv:2103.09847_ , 2021.
  * Dai et al. (2018) Dai, B., Shaw, A., Li, L., Xiao, L., He, N., Liu, Z., Chen, J., and Song, L.  Sbeed: Convergent reinforcement learning with nonlinear function approximation.  In _International Conference on Machine Learning_ , pp. 1125–1134. PMLR, 2018.
  * Engstrom et al. (2019) Engstrom, L., Ilyas, A., Santurkar, S., Tsipras, D., Janoos, F., Rudolph, L., and Madry, A.  Implementation matters in deep rl: A case study on ppo and trpo.  In _International Conference on Learning Representations_ , 2019.
  * Ernst et al. (2005) Ernst, D., Geurts, P., and Wehenkel, L.  Tree-based batch mode reinforcement learning.  _Journal of Machine Learning Research_ , 6(Apr):503–556, 2005.
  * Farahmand & Szepesvári (2011) Farahmand, A.-m. and Szepesvári, C.  Model selection in reinforcement learning.  _Machine learning_ , 85(3):299–332, 2011.
  * Farahmand et al. (2010) Farahmand, A. M., Munos, R., and Szepesvári, C.  Error propagation for approximate policy and value iteration.  In _Advances in Neural Information Processing Systems_ , 2010.
  * Feng et al. (2019) Feng, Y., Li, L., and Liu, Q.  A kernel loss for solving the bellman equation.  _Advances in Neural Information Processing Systems_ , 32:15456–15467, 2019.
  * Fu et al. (2019) Fu, J., Kumar, A., Soh, M., and Levine, S.  Diagnosing bottlenecks in deep q-learning algorithms.  In _International Conference on Machine Learning_ , pp. 2021–2030. PMLR, 2019.
  * Fu et al. (2021) Fu, J., Norouzi, M., Nachum, O., Tucker, G., Wang, Z., Novikov, A., Yang, M., Zhang, M. R., Chen, Y., Kumar, A., Paduraru, C., Levine, S., and Paine, T.  Benchmarks for deep off-policy evaluation.  In _International Conference on Learning Representations_ , 2021.
  * Fujimoto et al. (2018) Fujimoto, S., van Hoof, H., and Meger, D.  Addressing function approximation error in actor-critic methods.  In _International Conference on Machine Learning_ , volume 80, pp. 1587–1596. PMLR, 2018.
  * Fujimoto et al. (2019a) Fujimoto, S., Conti, E., Ghavamzadeh, M., and Pineau, J.  Benchmarking batch deep reinforcement learning algorithms.  _arXiv preprint arXiv:1910.01708_ , 2019a.
  * Fujimoto et al. (2019b) Fujimoto, S., Meger, D., and Precup, D.  Off-policy deep reinforcement learning without exploration.  In _International Conference on Machine Learning_ , pp. 2052–2062, 2019b.
  * Fujimoto et al. (2021) Fujimoto, S., Meger, D., and Precup, D.  A deep reinforcement learning approach to marginalized importance sampling with the successor representation.  In _Proceedings of the 38th International Conference on Machine Learning_ , volume 139, pp. 3518–3529. PMLR, 2021.
  * Geist et al. (2017) Geist, M., Piot, B., and Pietquin, O.  Is the bellman residual a bad proxy?  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , pp. 3208–3217, 2017.
  * Gu et al. (2016) Gu, S., Lillicrap, T., Sutskever, I., and Levine, S.  Continuous deep q-learning with model-based acceleration.  In _International Conference on Machine Learning_ , pp. 2829–2838, 2016.
  * Haarnoja et al. (2018a) Haarnoja, T., Zhou, A., Abbeel, P., and Levine, S.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  In _International Conference on Machine Learning_ , volume 80, pp. 1861–1870. PMLR, 2018a.
  * Haarnoja et al. (2018b) Haarnoja, T., Zhou, A., Hartikainen, K., Tucker, G., Ha, S., Tan, J., Kumar, V., Zhu, H., Gupta, A., Abbeel, P., et al.  Soft actor-critic algorithms and applications.  _arXiv preprint arXiv:1812.05905_ , 2018b.
  * Heger (1996) Heger, M.  The loss from imperfect value functions in expectation-based and minimax-based tasks.  _Machine Learning_ , 22(1):197–225, 1996.
  * Henderson et al. (2017) Henderson, P., Islam, R., Bachman, P., Pineau, J., Precup, D., and Meger, D.  Deep reinforcement learning that matters.  In _AAAI Conference on Artificial Intelligence_ , 2017.
  * Hessel et al. (2018) Hessel, M., Modayil, J., Van Hasselt, H., Schaul, T., Ostrovski, G., Dabney, W., Horgan, D., Piot, B., Azar, M., and Silver, D.  Rainbow: Combining improvements in deep reinforcement learning.  In _Thirty-second AAAI conference on artificial intelligence_ , 2018\.
  * Irpan et al. (2019) Irpan, A., Rao, K., Bousmalis, K., Harris, C., Ibarz, J., and Levine, S.  Off-policy evaluation via off-policy classification.  _Advances in Neural Information Processing Systems_ , 32:5437–5448, 2019.
  * Jaderberg et al. (2016) Jaderberg, M., Mnih, V., Czarnecki, W. M., Schaul, T., Leibo, J. Z., Silver, D., and Kavukcuoglu, K.  Reinforcement learning with unsupervised auxiliary tasks.  _arXiv preprint arXiv:1611.05397_ , 2016.
  * Kakade & Langford (2002) Kakade, S. and Langford, J.  Approximately optimal approximate reinforcement learning.  In _International Conference on Machine Learning_ , volume 2, pp. 267–274, 2002.
  * Kingma & Ba (2014) Kingma, D. and Ba, J.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Kolter (2011) Kolter, J. Z.  The fixed points of off-policy td.  In _Advances in Neural Information Processing Systems_ , 2011.
  * Lange et al. (2012) Lange, S., Gabel, T., and Riedmiller, M.  Batch reinforcement learning.  In _Reinforcement learning_ , pp. 45–73. Springer, 2012.
  * Le et al. (2019) Le, H., Voloshin, C., and Yue, Y.  Batch policy learning under constraints.  In _International Conference on Machine Learning_ , pp. 3703–3712. PMLR, 2019.
  * Levine et al. (2020) Levine, S., Kumar, A., Tucker, G., and Fu, J.  Offline reinforcement learning: Tutorial, review, and perspectives on open problems.  _arXiv preprint arXiv:2005.01643_ , 2020.
  * Lillicrap et al. (2015) Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D.  Continuous control with deep reinforcement learning.  _arXiv preprint arXiv:1509.02971_ , 2015.
  * Mnih et al. (2015) Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al.  Human-level control through deep reinforcement learning.  _Nature_ , 518(7540):529–533, 2015.
  * Munos (2003) Munos, R.  Error bounds for approximate policy iteration.  In _ICML_ , volume 3, pp. 560–567, 2003.
  * Munos (2007) Munos, R.  Performance bounds in l_p-norm for approximate value iteration.  _SIAM journal on control and optimization_ , 46(2):541–561, 2007.
  * Paine et al. (2020) Paine, T. L., Paduraru, C., Michi, A., Gulcehre, C., Zolna, K., Novikov, A., Wang, Z., and de Freitas, N.  Hyperparameter selection for offline reinforcement learning.  _arXiv preprint arXiv:2007.09055_ , 2020.
  * Paszke et al. (2019) Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al.  Pytorch: An imperative style, high-performance deep learning library.  In _Advances in Neural Information Processing Systems_ , pp. 8024–8035, 2019.
  * Patterson et al. (2022) Patterson, A., White, A., and White, M.  A generalized projected bellman error for off-policy value estimation in reinforcement learning.  _Journal of Machine Learning Research_ , 23(145):1–61, 2022.
  * Puterman (1994) Puterman, M. L.  _Markov Decision Processes: Discrete Stochastic Dynamic Programming_.  John Wiley & Sons, Inc., 1994.
  * Saleh & Jiang (2019) Saleh, E. and Jiang, N.  Deterministic bellman residual minimization.  In _Proceedings of Optimization Foundations for Reinforcement Learning Workshop at NeurIPS_ , 2019.
  * Schulman et al. (2017) Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ , 2017.
  * Schweitzer & Seidmann (1985) Schweitzer, P. J. and Seidmann, A.  Generalized polynomial approximations in markovian decision processes.  _Journal of mathematical analysis and applications_ , 110(2):568–582, 1985.
  * Singh & Yee (1994) Singh, S. P. and Yee, R. C.  An upper bound on the loss from approximate optimal-value functions.  _Machine Learning_ , 16(3):227–233, 1994.
  * Sutton (1988) Sutton, R. S.  Learning to predict by the methods of temporal differences.  _Machine learning_ , 3(1):9–44, 1988.
  * Sutton & Barto (1998) Sutton, R. S. and Barto, A. G.  _Reinforcement learning: An introduction_ , volume 1.  MIT press Cambridge, 1998.
  * Sutton et al. (2009) Sutton, R. S., Maei, H. R., Precup, D., Bhatnagar, S., Silver, D., Szepesvári, C., and Wiewiora, E.  Fast gradient-descent methods for temporal-difference learning with linear function approximation.  In _Proceedings of the 26th Annual International Conference on Machine Learning_ , pp. 993–1000, 2009.
  * Tang & Wiens (2021) Tang, S. and Wiens, J.  Model selection for offline reinforcement learning: Practical considerations for healthcare settings.  In _Machine Learning for Healthcare Conference_ , pp. 2–35. PMLR, 2021.
  * Todorov et al. (2012) Todorov, E., Erez, T., and Tassa, Y.  Mujoco: A physics engine for model-based control.  In _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pp. 5026–5033. IEEE, 2012.
  * Voloshin et al. (2021) Voloshin, C., Le, H. M., Jiang, N., and Yue, Y.  Empirical study of off-policy policy evaluation for reinforcement learning.  In _Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1)_ , 2021.
  * Wang et al. (2020) Wang, R., Foster, D., and Kakade, S. M.  What are the statistical limits of offline rl with linear function approximation?  In _International Conference on Learning Representations_ , 2020.
  * Williams & Baird (1993) Williams, R. J. and Baird, L.  Tight performance bounds on greedy policies based on imperfect value functions.  Technical report, Northeastern University, College of Computer Science, 1993.
  * Xiao et al. (2021) Xiao, C., Lee, I., Dai, B., Schuurmans, D., and Szepesvari, C.  On the sample complexity of batch reinforcement learning with policy-induced data.  _arXiv preprint arXiv:2106.09973_ , 2021.
  * Yang & Nachum (2021) Yang, M. and Nachum, O.  Representation matters: Offline pretraining for sequential decision making.  In _Self-Supervision for Reinforcement Learning Workshop-ICLR 2021_ , 2021.
  * Zanette (2021) Zanette, A.  Exponential lower bounds for batch reinforcement learning: Batch rl can be exponentially harder than online rl.  In _International Conference on Machine Learning_ , pp. 12287–12297. PMLR, 2021.
  * Zhang et al. (2020) Zhang, S., Boehmer, W., and Whiteson, S.  Deep residual reinforcement learning.  In _Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems_ , pp. 1611–1619, 2020.
  * Zhu & Ying (2020) Zhu, Y. and Ying, L.  Borrowing from the future: An attempt to address double sampling.  In _Mathematical and scientific machine learning_ , pp. 246–268. PMLR, 2020.

##  Appendix A Additional Figures

###  A.1 Is the Bellman error a valid on-policy objective?

Train Data | Test Data | Algorithm | HalfCheetah | Hopper | Walker2d | Ant | Humanoid
---|---|---|---|---|---|---|---
All | On-Policy | BRM |  -0.95 |  -0.74 |  -0.96 |  -0.99 |  -0.98
FQE |  -0.81 |  -0.76 |  -0.72 |  -0.79 |  -0.11
All | $0.1$ | BRM |  -0.46 |  -0.83 |  -0.74 |  -0.75 |  -0.65
FQE |  -0.57 |  -0.85 |  -0.90 |  -0.60 |  -0.20
$0.1$ | $0.1$ | BRM |  -0.11 |  -0.04 |  -0.47 |  -0.46 |  -0.48
FQE |  -0.92 |  -0.29 |  -0.14 |  -0.58 |  -0.05
Table 2: Is there a correlation between Bellman error and value error? We
display Pearson’s correlation coefficient of the final Bellman error and value
error of functions trained with either only BRM or only FQE. Warm colors  are
used to show positive correlation and cold colors  are used for negative
correlation. The error terms are computed over held-out rollouts. The
functions are trained using datasets of varying noise levels, where all refers
to the set ($0.1$, $0.2$, $0.3$, $0.4$, $0.5$) with 10 seeds, (6$\times$10
functions), $0.1$ refers to the subset of functions trained on the $0.1$
dataset (10 functions). While there is high correlation between the on-policy
empirical Bellman error and value error when comparing functions trained with
the same algorithm, this relationship is not strong when evaluated with an
off-policy dataset $(0.1)$.

###  A.2 Does FQE provide a better metric?

Train Data | Test Data | Metric | HalfCheetah | Hopper | Walker2d | Ant | Humanoid
---|---|---|---|---|---|---|---
All | On-Policy | BE |  -0.81 |  -0.76 |  -0.72 |  -0.79 |  -0.11
$\mathcal{L}_{\text{FQE}}$ |  -0.81 |  -0.79 |  -0.60 |  -0.81 |  -0.22
All | $0.1$ | BE |  -0.57 |  -0.85 |  -0.90 |  -0.60 |  -0.20
$\mathcal{L}_{\text{FQE}}$ |  -0.62 |  -0.84 |  -0.90 |  -0.59 |  -0.21
Table 3: Is there a correlation between the FQE loss and value error?
Pearson’s correlation coefficient of the Bellman error (BE) and the FQE
objective ($\mathcal{L}_{\text{FQE}}$) with the value error of functions
trained by FQE. Warm colors  are used to show positive correlation and cold
colors  are used for negative correlation. The error terms are computed over
held-out rollouts. The functions are trained using datasets of varying noise
levels, where all refers to the set ($0.1$, $0.2$, $0.3$, $0.4$, $0.5$) with
10 seeds, (6$\times$10 functions), $0.1$ refers to the subset of functions
trained on the $0.1$ dataset (10 functions). We can see that the difference
between BE and $\mathcal{L}_{\text{FQE}}$ is minimal. This means that the FQE
loss function is not a better metric than BE. This is logical as it is non-
stationary and dependent on the current value function.

###  A.3 Additional Single Trajectory Experiments

(a)

(b)

(c)

(d)

(e)

BRM  FQE  MC

Figure 4: Does bias explain the non-correspondence between the Bellman error and value error? We train value functions over a single on-policy trajectory (1000 transitions, with termination). As a result, every relevant transition is contained in each dataset. We display the Bellman error (left) and unnormalized value error (right) for every transition in the trajectory. Visually, we can see that the clusters of similar value error (size and direction) can cause lower magnitude Bellman error for  BRM and  FQE. | BRM | FQE | MC
---|---|---|---
| BE | VE | Ratio | BE | VE | Ratio | BE | VE | Ratio
HalfCheetah | 0.41 | 23.39 | 56.93 | 0.76 | 8.89 | 11.72 | 2.76 | 2.75 | 1.00
Hopper | 0.07 | 5.54 | 77.43 | 0.12 | 1.13 | 9.33 | 0.36 | 0.50 | 1.39
Walker2d | 0.16 | 8.87 | 56.56 | 0.16 | 1.92 | 11.79 | 0.19 | 0.29 | 1.50
Ant | 0.42 | 16.02 | 38.17 | 0.20 | 0.33 | 1.68 | 0.14 | 0.15 | 1.09
Humanoid | 0.12 | 4.50 | 37.64 | 0.33 | 0.30 | 0.93 | 0.09 | 0.06 | 0.72
Table 4: Does bias explain the non-correspondence between the Bellman error
and value error? We train value functions over a single on-policy trajectory
(1000 transitions, with termination). As a result, every relevant transition
is contained in each dataset. We report the average absolute Bellman error
(BE) and value error (VE), and ratio between these terms. By Proposition 4,
with a discount $\gamma=0.99$, the ratio between mean absolute Bellman and
value error is bounded by $(0.5,100)$. The tabular results show that both the
upper and lower bound can be approached in practice.

###  A.4 BRM Behaves Predictably

Target Policy  Behavior Policy  BRM  BRM (Suboptimal target policy)

Figure 5: Visualizing the final value estimated by BRM after training on
different datasets corresponding to varying noise levels. The true value of
the target policy and the behavior policy are displayed to provide reference,
as well as BRM when trained to evaluate a suboptimal policy (corresponding to
TD3 trained for 300k time steps rather than 3m). Error bars capture the
standard deviation over 10 seeds (but are visually hard to see as the
deviation is low). We can see that  BRM typically converges to a value which
is closer to the  behavior policy rather than the  target policy, and
typically prefers values which are close to 0. Interestingly, the BRM trained
to evaluate the suboptimal target policy  converges to the same value on the
noisiest datasets, suggesting that the influence of the target policy on what
value BRM converges to is reduced with increased distribution shift.

##  Appendix B Proofs

###  B.1 Proposition 1

######  Proposition 1.

The Bellman error $\epsilon(s,a)=0$ for all state-action pairs
$(s,a)\in\mathcal{S}\times\mathcal{A}$, if and only if the value error
$\Delta(s,a)=0$ for all state-action pairs
$(s,a)\in\mathcal{S}\times\mathcal{A}$.

Proof.

$\Rightarrow$: This is a direct consequence of Theorem 1.

$\Leftarrow$: If for all $(s,a)\in\mathcal{S}\times\mathcal{A}$,
$\Delta(s,a)=Q(s,a)-Q^{\pi}(s,a)=0$ then $Q(s,a)=Q^{\pi}(s,a)$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$. From the Bellman equation it follows
that

$\displaystyle Q(s,a)$ $\displaystyle=Q^{\pi}(s,a)$ (16)
$\displaystyle=\mathcal{T}Q^{\pi}(s,a)$ (17)
$\displaystyle=\mathcal{T}Q(s,a).$ (18)

$\blacksquare$

###  B.2 Proposition 2

######  Proposition 2.

Let $Q_{1},Q_{2}$ be value functions, where $Q_{2}=\mathcal{T}Q_{1}$.
$\max_{(s,a)}|\Delta_{Q_{2}}(s,a)|\leq\gamma\cdot\max_{(s,a)}|\Delta_{Q_{1}}(s,a)|$.

Proof.

For all $(s,a)\in\mathcal{S}\times\mathcal{A}$:

$\displaystyle\Delta_{2}(s,a)$
$\displaystyle=\mathcal{T}Q_{1}(s,a)-Q^{\pi}(s,a)$ (19)
$\displaystyle=\mathcal{T}Q_{1}(s,a)-\mathcal{T}Q^{\pi}(s,a)$ (20)
$\displaystyle=\mathbb{E}_{s^{\prime},a^{\prime}}[\gamma(Q_{1}(s^{\prime},a^{\prime})-Q^{\pi}(s^{\prime},a^{\prime}))]$
(21)
$\displaystyle=\mathbb{E}_{s^{\prime},a^{\prime}}[\gamma\Delta_{1}(s^{\prime},a^{\prime})].$
(22)

It follows that for all $(s,a)\in\mathcal{S}\times\mathcal{A}$:

$\displaystyle|\Delta_{2}(s,a)|$
$\displaystyle\leq\max_{(s,a)}\gamma|\Delta_{1}(s,a)|$ (23)
$\displaystyle\Rightarrow\max_{(s,a)}|\Delta_{2}(s,a)|$
$\displaystyle\leq\max_{(s,a)}\gamma|\Delta_{1}(s,a)|.$ (24)

$\blacksquare$

###  B.3 Proposition 3

######  Proposition 3.

(An inverse relationship between Bellman error and value error). For any MDP,
discount factor $\gamma\in(0,1)$, and $C>0$, we can define a value function
$Q_{1}$ and a stochastic value function $Q_{2}$ such that for any state-action
pair $(s,a)\in\mathcal{S}\times\mathcal{A}$

  1. 1.

$|\Delta_{Q_{1}}(s,a)|-|\Delta_{Q_{2}}(s,a)|>C$,

  2. 2.

$\mathbb{E}_{Q_{2}}[|\epsilon_{Q_{2}}(s,a)|]-|\epsilon_{Q_{1}}(s,a)|>C$.

Proof.

Let

$\displaystyle Q_{1}(s,a)$ $\displaystyle=Q^{\pi}(s,a)+\frac{k}{1-\gamma},$
(25) $\displaystyle Q_{2}(s,a)$ $\displaystyle=Q^{\pi}(s,a)\pm k(1+\gamma).$
(26)

Then

$\displaystyle|\Delta_{1}(s,a)|$ $\displaystyle=\frac{k}{1-\gamma},$ (27)
$\displaystyle|\Delta_{2}(s,a)|$ $\displaystyle=k(1+\gamma),$ (28)

where $\frac{k}{1-\gamma}>k(1+\gamma)$ for all $\gamma\in(0,1)$.

And

$\displaystyle\epsilon_{1}(s,a)$
$\displaystyle=\frac{k}{1-\gamma}-\frac{\gamma k}{1-\gamma}=k,$ (29)
$\displaystyle\mathbb{E}[|\epsilon_{2}(s,a)|]$
$\displaystyle=0.5|k(1+\gamma)-\gamma k(1+\gamma)|+0.5|k(1+\gamma)+\gamma
k(1+\gamma)|$ (30) $\displaystyle=k(1+\gamma),$ (31)

where $k<k(1+\gamma)$ for all $\gamma\in(0,1)$.

Then we need

$\displaystyle\frac{k}{1-\gamma}-k(1+\gamma)$ $\displaystyle>C$ (32)
$\displaystyle\Rightarrow k\left(\frac{1}{1-\gamma}-(1+\gamma)\right)$
$\displaystyle>C$ (33) $\displaystyle\Rightarrow k$
$\displaystyle>\frac{C}{\frac{1}{1-\gamma}-(1+\gamma)}=\frac{C(1-\gamma)}{\gamma^{2}}.$
(34)

and

$\displaystyle k(1+\gamma)-k$ $\displaystyle>C$ (35) $\displaystyle\Rightarrow
k\gamma$ $\displaystyle>C$ (36) $\displaystyle\Rightarrow k$
$\displaystyle>\frac{C}{\gamma}.$ (37)

Set $k=\max\left(\frac{C(1-\gamma)}{\gamma^{2}},\frac{C}{\gamma}\right)$.

$\blacksquare$

###  B.4 Theorem 1

######  Theorem 1.

(Value error as a function of Bellman error). For any state-action pair
$(s,a)\in\mathcal{S}\times\mathcal{A}$, the value error $\Delta(s,a)$ can be
defined as a function of the Bellman error $\epsilon$

$\Delta(s,a)=\frac{1}{1-\gamma}\mathbb{E}_{(s^{\prime},a^{\prime})\sim
d^{\pi}(\cdot|s,a)}[\epsilon(s^{\prime},a^{\prime})].$ (38)

Proof. Our proof follows similar steps to the proof of Lemma 6.1 in (Kakade &
Langford, 2002) and likely others.

First by definition:

$\displaystyle\Delta(s,a)$ $\displaystyle:=Q(s,a)-Q^{\pi}(s,a)$ (39)
$\displaystyle\Rightarrow Q^{\pi}(s,a)$ $\displaystyle=Q(s,a)-\Delta(s,a).$
(40)

Then we can decompose value error:

$\displaystyle\Delta(s,a)$ $\displaystyle=Q(s,a)-Q^{\pi}(s,a)$ (41)
$\displaystyle=Q(s,a)-(r+\gamma\mathbb{E}_{\pi}[Q^{\pi}(s^{\prime},a^{\prime})])$
(42)
$\displaystyle=Q(s,a)-(r+\gamma\mathbb{E}_{\pi}[Q(s^{\prime},a^{\prime})-\Delta(s^{\prime},a^{\prime})])$
(43)
$\displaystyle=Q(s,a)-(r+\gamma\mathbb{E}_{\pi}[Q(s^{\prime},a^{\prime})])+\gamma\mathbb{E}_{\pi}[\Delta(s^{\prime},a^{\prime})]$
(44)
$\displaystyle=\epsilon(s,a)+\gamma\mathbb{E}_{\pi}[\Delta(s^{\prime},a^{\prime})].$
(45)

By treating $\Delta(s,a)$ as a value function and
$\epsilon(s^{\prime},a^{\prime})$ as the reward, we can see that:

$\Delta(s,a)=\frac{1}{1-\gamma}\mathbb{E}_{(s^{\prime},a^{\prime})\sim
d^{\pi}(\cdot|s,a)}[\epsilon(s^{\prime},a^{\prime})].$ (46)

Note that this theorem can also be applied to finite horizon MDPs, by either
considering a definition of $d^{\pi}$ which accounts for the finite horizon,
$d^{\pi}(s^{\prime},a^{\prime}|s,a)=\frac{1}{\sum_{t=0}^{T-1}\gamma^{t}}\sum_{t=0}^{T-1}\gamma^{t}p^{\pi}((s,a)\rightarrow
s^{\prime},t)\pi(a^{\prime}|s^{\prime})$, or by transforming the finite
horizon MDP into an infinite horizon MDP by considering episode termination to
be a terminal state which loops infinitely upon itself.

$\blacksquare$

###  B.5 Proposition 4

######  Proposition 4.

(Bounds on value error). Let $C_{\text{max}}=\max_{s,a}|\epsilon(s,a)|$ and
$C_{\text{avg}}=\mathbb{E}_{(s,a)\sim d^{\pi}}[|\epsilon(s,a)|]$.

  1. 1.

$\frac{C_{\text{max}}}{1+\gamma}\leq\max_{s,a}|\Delta(s,a)|\leq\frac{C_{\text{max}}}{1-\gamma}$,

  2. 2.

$\frac{C_{\text{avg}}}{1+\gamma}\leq\mathbb{E}_{(s,a)\sim
d^{\pi}}[|\Delta(s,a)|]\leq\frac{C_{\text{avg}}}{1-\gamma}$,

Furthermore, for any MDP and policy, there exists a value function such that
the upper bound is an equality, and there exists a MDP, policy, and value
function such that the lower bound is an equality.

Proof.

Upper bound on $\max_{s,a}|\Delta(s,a)|$: For all
$(s,a)\in\mathcal{S}\times\mathcal{A}$:

$\displaystyle\Delta(s,a)$
$\displaystyle=\frac{1}{1-\gamma}\mathbb{E}_{(s^{\prime},a^{\prime})\sim
d^{\pi}(\cdot|s,a)}[\epsilon(s^{\prime},a^{\prime})]$ (47)
$\displaystyle\Rightarrow|\Delta(s,a)|$
$\displaystyle=|\frac{1}{1-\gamma}\mathbb{E}_{(s^{\prime},a^{\prime})\sim
d^{\pi}(\cdot|s,a)}[\epsilon(s^{\prime},a^{\prime})]|$ (48)
$\displaystyle\leq\frac{1}{1-\gamma}\mathbb{E}_{(s^{\prime},a^{\prime})\sim
d^{\pi}(\cdot|s,a)}[|\epsilon(s^{\prime},a^{\prime})|]$ (49)
$\displaystyle\leq\frac{1}{1-\gamma}\max_{(s,a)\in\mathcal{S}\times\mathcal{A}}|\epsilon(s,a)|$
(50) $\displaystyle\Rightarrow\max_{(s,a)}|\Delta(s,a)|$
$\displaystyle\leq\frac{1}{1-\gamma}\max_{(s,a)\in\mathcal{S}\times\mathcal{A}}|\epsilon(s,a)|.$
(51)

A proof of a similar relationship can also be found in Bertsekas & Tsitsiklis
(1996), (Proposition 6.1, page 262).

Lower bound on $\max_{s,a}|\Delta(s,a)|$: For all
$(s,a)\in\mathcal{S}\times\mathcal{A}$:

$\displaystyle\epsilon(s,a)$
$\displaystyle=\Delta(s,a)-\gamma\mathbb{E}_{s^{\prime},\pi}[\Delta(s^{\prime},a^{\prime})]$
(52) $\displaystyle\Rightarrow\Delta(s,a)$
$\displaystyle=\epsilon(s,a)+\gamma\mathbb{E}[\Delta(s^{\prime},a^{\prime})]$
(53) $\displaystyle\Rightarrow|\Delta(s,a)|$
$\displaystyle=|\epsilon(s,a)+\gamma\mathbb{E}[\Delta(s^{\prime},a^{\prime})]|$
(54) $\displaystyle\Rightarrow\max_{(s,a)}|\Delta(s,a)|$
$\displaystyle=\max_{(s,a)}|\epsilon(s,a)+\gamma\mathbb{E}[\Delta(s^{\prime},a^{\prime})]|$
(55)
$\displaystyle\geq\max_{(s,a)}|\epsilon(s,a)|-\gamma|\mathbb{E}[\Delta(s^{\prime},a^{\prime})]|$
(56)
$\displaystyle\geq\max_{(s,a)}|\epsilon(s,a)|-\gamma\max_{(s,a)}|\mathbb{E}[\Delta(s^{\prime},a^{\prime})]|$
(57)
$\displaystyle\geq\max_{(s,a)}|\epsilon(s,a)|-\gamma\max_{(s,a)}|\Delta(s,a)|$
(58) $\displaystyle\Rightarrow(1+\gamma)\max_{(s,a)}|\Delta(s,a)|$
$\displaystyle\geq\max_{(s,a)}|\epsilon(s,a)|$ (59)
$\displaystyle\Rightarrow\max_{(s,a)}|\Delta(s,a)|$
$\displaystyle\geq\frac{1}{1+\gamma}\max_{(s,a)}|\epsilon(s,a)|.$ (60)

Upper bound on $\mathbb{E}_{(s,a)\sim d^{\pi}}[|\Delta(s,a)|]$: For all
$(s,a)\in\mathcal{S}\times\mathcal{A}$:

$\displaystyle\Delta(s,a)$
$\displaystyle=\frac{1}{1-\gamma}\mathbb{E}_{(s^{\prime},a^{\prime})\sim
d^{\pi}(\cdot|s,a)}[\epsilon(s^{\prime},a^{\prime})]$ (62)
$\displaystyle\Rightarrow|\Delta(s,a)|$
$\displaystyle=\frac{1}{1-\gamma}|\mathbb{E}_{(s^{\prime},a^{\prime})\sim
d^{\pi}(\cdot|s,a)}[\epsilon(s^{\prime},a^{\prime})]|$ (63)
$\displaystyle\Rightarrow\mathbb{E}_{d^{\pi}}[|\Delta(s,a)|]$
$\displaystyle=\frac{1}{1-\gamma}\mathbb{E}_{d^{\pi}}[|\mathbb{E}_{(s^{\prime},a^{\prime})\sim
d^{\pi}(\cdot|s,a)}[\epsilon(s^{\prime},a^{\prime})]|]$ (64)
$\displaystyle\leq\frac{1}{1-\gamma}\mathbb{E}_{d^{\pi}}[\mathbb{E}_{(s^{\prime},a^{\prime})\sim
d^{\pi}(\cdot|s,a)}[|\epsilon(s^{\prime},a^{\prime})|]]$ (65)
$\displaystyle=\frac{1}{1-\gamma}\mathbb{E}_{d^{\pi}}[|\epsilon(s^{\prime},a^{\prime})|].$
(66)

Lower bound on $\mathbb{E}_{(s,a)\sim d^{\pi}}[|\Delta(s,a)|]$: For all
$(s,a)\in\mathcal{S}\times\mathcal{A}$:

$\displaystyle\epsilon(s,a)$
$\displaystyle=\Delta(s,a)-\gamma\mathbb{E}_{s^{\prime},\pi}[\Delta(s^{\prime},a^{\prime})]$
(67) $\displaystyle\Rightarrow\Delta(s,a)$
$\displaystyle=\epsilon(s,a)+\gamma\mathbb{E}[\Delta(s^{\prime},a^{\prime})]$
(68) $\displaystyle\Rightarrow|\Delta(s,a)|$
$\displaystyle=|\epsilon(s,a)+\gamma\mathbb{E}[\Delta(s^{\prime},a^{\prime})]|$
(69) $\displaystyle\Rightarrow\mathbb{E}_{d^{\pi}}[|\Delta(s,a)|]$
$\displaystyle=\mathbb{E}_{d^{\pi}}[|\epsilon(s,a)+\gamma\mathbb{E}[\Delta(s^{\prime},a^{\prime})]|]$
(70)
$\displaystyle\geq\mathbb{E}_{d^{\pi}}[|\epsilon(s,a)|-\gamma|\mathbb{E}[\Delta(s^{\prime},a^{\prime})]|]$
(71)
$\displaystyle=\mathbb{E}_{d^{\pi}}[|\epsilon(s,a)|]-\gamma\mathbb{E}_{d^{\pi}}[|\mathbb{E}[\Delta(s^{\prime},a^{\prime})]|]$
(72) $\displaystyle\Rightarrow(1+\gamma)\mathbb{E}_{d^{\pi}}[|\Delta(s,a)|]$
$\displaystyle\geq\mathbb{E}_{d^{\pi}}[|\epsilon(s,a)|]$ (73)
$\displaystyle\Rightarrow\mathbb{E}_{d^{\pi}}[|\Delta(s,a)|]$
$\displaystyle\geq\frac{1}{1+\gamma}\mathbb{E}_{d^{\pi}}[|\epsilon(s,a)|].$
(74)

Equality on upper bound: For any MDP, policy $\pi$, and constant $C$, let
$Q(s,a)=Q^{\pi}+\frac{C}{1-\gamma}$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$. It follows that $\epsilon(s,a)=C$ and
$\Delta(s,a)=\frac{C}{1-\gamma}$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$.

Equality on lower bound: Consider a two-state, single action MDP
$\mathcal{S}=\\{s_{1},s_{2}\\},\mathcal{A}=\\{a\\}$ such that
$(s_{1},a)\rightarrow s_{2}$ and $(s_{2},a)\rightarrow s_{1}$. Let
$Q(s_{1},a)=Q^{\pi}+\frac{C}{1+\gamma}$ and
$Q(s_{2},a)=Q^{\pi}-\frac{C}{1+\gamma}$ for some constant $C$. It follows that
$|\epsilon(s,a)|=C$ and $|\Delta(s,a)|=\frac{C}{1+\gamma}$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$.

$\blacksquare$

###  B.6 Corollary 1

######  Corollary 1.

(The Bellman equation is not unique over incomplete datasets). If there exists
a state-action pair $(s^{\prime},a^{\prime})$ not contained in the dataset
$\mathcal{D}$, where the state-action occupancy
$d^{\pi}(s^{\prime},a^{\prime}|s,a)>0$ for some $(s,a)\in\mathcal{D}$, then
there exists a value function and $C>0$ such that

  1. 1.

For all $(\hat{s},\hat{a})\in\mathcal{D}$, the Bellman error
$\epsilon(\hat{s},\hat{a})=0$.

  2. 2.

There exists $(s,a)\in\mathcal{D}$, such that the value error $\Delta(s,a)=C$.

Proof. This is a direct consequence of Theorem 1. Let $\mathcal{D}^{\prime}$
contain the set of state-action pairs $(s^{\prime},a^{\prime})$ not contained
in the dataset $\mathcal{D}$, where the state-action occupancy
$d^{\pi}(s^{\prime},a^{\prime}|s,a)>0$. Let $\mathcal{D}_{\text{unique}}$ be
the set of unique state-action pairs in $\mathcal{D}$. It follows that

$\displaystyle\Delta(s,a)$
$\displaystyle=\frac{1}{1-\gamma}\mathbb{E}_{(s^{\prime},a^{\prime})\sim
d^{\pi}(\cdot|s,a)}[\epsilon(s^{\prime},a^{\prime})]$ (75)
$\displaystyle=\frac{1}{1-\gamma}\sum_{(s^{\prime},a^{\prime})\sim\mathcal{D}_{\text{unique}}}d^{\pi}(s^{\prime},a^{\prime}|s,a)\epsilon(s^{\prime},a^{\prime})+\frac{1}{1-\gamma}\sum_{(s^{\prime},a^{\prime})\sim\mathcal{D}^{\prime}}d^{\pi}(s^{\prime},a^{\prime}|s,a)\epsilon(s^{\prime},a^{\prime}).$
(76)

Recall

$\epsilon(s,a):=Q(s,a)-\mathbb{E}_{r,s^{\prime}\sim
p,a^{\prime}\sim\pi}\left[r+\gamma Q(s^{\prime},a^{\prime})\right],$ (77)

and there exists at least one $Q(s,a)$, such that
$(s,a)\in\mathcal{D}^{\prime}$. Since the sets $\mathcal{D}$ and
$\mathcal{D}^{\prime}$ are distinct, it follows that there exists a function
$Q$ such that $\epsilon(s,a)=0$ for all $(s,a)\in\mathcal{D}$, but
$\frac{1}{1-\gamma}\sum_{(s^{\prime},a^{\prime})\sim\mathcal{D}^{\prime}}d^{\pi}(s^{\prime},a^{\prime}|s,a)\epsilon(s^{\prime},a^{\prime})=C$.

$\blacksquare$

###  B.7 Proposition 5

######  Proposition 5.

(FQE improvement condition). Let $Q_{1},Q_{2}$ be value functions, where
$Q_{2}=\mathcal{T}Q_{1}$. If
$\gamma\cdot\max_{(s,a)\in\mathcal{D}}|\mathbb{E}_{(s^{\prime},a^{\prime})\sim
p(\cdot|s,a),\pi}[\Delta_{Q_{1}}(s^{\prime},a^{\prime})]|<\max_{(s,a)\in\mathcal{D}}|\Delta_{Q_{1}}(s,a)|$
then
$\max_{(s,a)\in\mathcal{D}}|\Delta_{Q_{2}}(s,a)|<\max_{(s,a)\in\mathcal{D}}|\Delta_{Q_{1}}(s,a)|$.

Proof.

For all $(s,a)\in\mathcal{D}$:

$\displaystyle\Delta_{2}(s,a)$
$\displaystyle=\mathcal{T}Q_{1}(s,a)-Q^{\pi}(s,a)$ (78)
$\displaystyle=\mathcal{T}Q_{1}(s,a)-\mathcal{T}Q^{\pi}(s,a)$ (79)
$\displaystyle=\mathbb{E}_{(s^{\prime},a^{\prime})\sim
p(\cdot|s,a),\pi}[\gamma(Q_{1}(s^{\prime},a^{\prime})-Q^{\pi}(s^{\prime},a^{\prime}))]$
(80) $\displaystyle=\mathbb{E}_{(s^{\prime},a^{\prime})\sim
p(\cdot|s,a),\pi}[\gamma\Delta_{1}(s^{\prime},a^{\prime})]$ (81)
$\displaystyle\Rightarrow|\Delta_{2}(s,a)|$
$\displaystyle=\gamma|\mathbb{E}_{(s^{\prime},a^{\prime})\sim
p(\cdot|s,a),\pi}[\Delta_{1}(s^{\prime},a^{\prime})]|.$ (82)

It follows that for all $(s,a)\in\mathcal{D}$ if

$\displaystyle\gamma\cdot\max_{(s,a)\in\mathcal{D}}|\mathbb{E}_{(s^{\prime},a^{\prime})\sim
p(\cdot|s,a),\pi}[\Delta_{1}(s^{\prime},a^{\prime})]|$
$\displaystyle<\max_{(s,a)\in\mathcal{D}}|\Delta_{1}(s,a)|$ (83)
$\displaystyle\Rightarrow\max_{(s,a)\in\mathcal{D}}|\Delta_{2}(s,a)|$
$\displaystyle<\max_{(s,a)\in\mathcal{D}}|\Delta_{1}(s,a)|.$ (84)

$\blacksquare$

##  Appendix C Learning Curves

###  C.1 BRM

(a) Evaluated with the Training Dataset

(b) Evaluated with the On-Policy Dataset

Noise level:  On-policy ($0.0$)  $0.1$ $0.2$ $0.3$ $0.4$ $0.5$

Figure 6: Visualizing the learning curves of the Bellman error and value error
of value functions trained by BRM evaluated over the training dataset (used in
Table 1) and on-policy dataset (used in Table 2). The shaded area captures the
standard deviation over 10 seeds.

###  C.2 FQE

(a) Evaluated with the Training Dataset

(b) Evaluated with the On-Policy Dataset

Noise level:  On-policy ($0.0$)  $0.1$ $0.2$ $0.3$ $0.4$ $0.5$

Figure 7: Visualizing the learning curves of the Bellman error and value error
of value functions trained by FQE evaluated over the training dataset (used in
Table 1) and on-policy dataset (used in Table 2). The shaded area captures the
standard deviation over 10 seeds. The Bellman error of individual trials is
clipped to 10k for visual clarity (only relevant for HalfCheetah).

##  Appendix D What if…

###  D.1 …we compare the absolute Bellman error to absolute value error?

Figure 2 compares the mean squared Bellman error to the absolute value error.
In Figure 8 we compare the absolute Bellman error with the absolute value
error, and in Figure 9 we compare the mean squared Bellman error with the mean
squared value error. We find that our observations regarding the relative
ordering of the Bellman error and value error are unchanged.

BRM  FQE  MC

Figure 8: Comparing the absolute Bellman error with the absolute value error.
The shaded area captures the standard deviation over 10 seeds. Both algorithms
are trained using on-policy data collected by the target policy.

BRM  FQE  MC

Figure 9: Comparing the mean squared Bellman error with the mean squared value
error. The shaded area captures the standard deviation over 10 seeds. Both
algorithms are trained using on-policy data collected by the target policy.

###  D.2 …we use less data?

Figure 2 uses datasets of 1M transitions. In Figure 10 we repeat the
experiment in Figure 2 with a dataset of 50k transitions. We find that our
observations regarding the relative ordering of the Bellman error and value
error are unchanged.

BRM  FQE  MC

Figure 10: Comparing the mean squared Bellman error with the absolute value
error, using a dataset of 50k. The shaded area captures the standard deviation
over 10 seeds. Both algorithms are trained using on-policy data collected by
the target policy.

###  D.3 …we use training error instead of test error?

Figure 2 evaluates the Bellman error and the value error on a held-out test
set. In Figure 11 we evaluate the error terms on the training dataset, rather
than the held-out test set. We find that our observations regarding the
relative ordering of the Bellman error and value error are unchanged.

BRM  FQE  MC

Figure 11: Comparing the mean squared Bellman error with the absolute value
error, evaluated on the training dataset, rather than a held-out test set. The
shaded area captures the standard deviation over 10 seeds. Both algorithms are
trained using on-policy data collected by the target policy.

###  D.4 …we use train for longer?

Figure 2 displays the learning curves for 1M time steps. In Figure 12 we train
for 10M time steps (using the same dataset). We find that our observations
regarding the relative ordering of the Bellman error and value error are
unchanged.

BRM  FQE  MC

Figure 12: Comparing the mean squared Bellman error with the absolute value
error while training for 10M time steps (the dataset of 1M is unchanged from
Figure 2). The shaded area captures the standard deviation over 10 seeds. Both
algorithms are trained using on-policy data collected by the target policy.

##  Appendix E Experiment Details

Software. Software versions used were as follows:

  * •

Python 3.6

  * •

Pytorch 1.8.0 (Paszke et al., 2019)

  * •

Gym 0.17.0 (Brockman et al., 2016)

  * •

MuJoCo 1.50111License information: https://www.roboti.us/license.html (Todorov
et al., 2012)

  * •

mujoco-py 1.50.1.1

-v3 versions of the MuJoCo environments were used.

Hyperparameters. FQE and BRM used the same hyperparameters and architecture,
as described in Table 5. These hyperparameters were chosen to match TD3 and
SAC (Fujimoto et al., 2018; Haarnoja et al., 2018a), state of the art off-
policy RL algorithms used in the MuJoCo domain. Following these algorithms,
both FQE and BRM set the discount factor $\gamma$ to $0$ for terminal states
(and use $0.99$ otherwise). FQE uses Polyak averaging for the target network
update. Given parameters $\theta$ of the current network, the parameters of
the target network $\bar{\theta}$ are updated by the following after each time
step:

$\bar{\theta}\leftarrow(1-\tau)\bar{\theta}+\tau\theta,$ (85)

where $\tau$ is the target update rate. This rule is a commonly-used update
rule by many off-policy RL algorithms for continuous actions (Lillicrap et
al., 2015; Fujimoto et al., 2018; Haarnoja et al., 2018b).

| Hyperparameter | Value
---|---|---
Network Hyperparameters | Optimizer | Adam (Kingma & Ba, 2014)
Learning rate | 3e-4
Mini-batch size | 256
Target update rate (FQE) | 5e-3
Discount factor | 0.99
| Terminal Discount factor | 0.0
Architecture | Network Hidden dim | 256
Network Hidden layers | 2
Activation function | ReLU
Table 5: Hyperparameters and architecture.

Target policy. In each experiment, we evaluate the discounted return of a
deterministic target policy taken from TD3 (Fujimoto et al., 2018) trained for
3 million time steps. Our implementation of TD3 is based directly off of the
author-provided Github (https://github.com/sfujim/TD3). For all experiments,
the discounted return uses a discount factor of $\gamma=0.99$.

Dataset and behavior policy. Datasets are collected by using a noisy variation
of the target policy $\pi_{t}$. For a noise level
$n\in[0.0,0.1,0.2,0.3,0.4,0.5]$, the behavior policy $\pi_{b}$ is defined as:

$\pi_{b}(s)=\begin{cases}\pi_{t}(s)+\mathcal{N}(0,n),&\text{with }p=1-n,\\\
\text{uniform random action}&\text{with }p=n.\end{cases}$ (86)

Unless stated otherwise, experiments use a dataset of 1 million transitions,
matching the replay buffer size of TD3/SAC.

Metrics and evaluation datasets. The main metrics used are the Bellman error
and the value error. Given an evaluation dataset $\mathcal{D}_{e}$ and value
function $Q$, the mean-squared Bellman error is computed by:

$\frac{1}{|\mathcal{D}_{e}|}\sum_{(s,a,r,s^{\prime})\sim\mathcal{D}_{e},a^{\prime}\sim\pi}\left(Q(s,a)-(r+\gamma
Q(s^{\prime},a^{\prime}))\right)^{2}.$ (87)

Given an evaluation dataset $\mathcal{D}_{e}$ and value function $Q$, the
normalized absolute value error is computed by:

$\frac{1}{K|\mathcal{D}_{e}|}\sum_{(s,a,r,s^{\prime})\sim\mathcal{D}_{e},a^{\prime}\sim\pi}|Q(s,a)-Q^{\pi}(s,a)|.$
(88)

$Q^{\pi}(s,a)$ is computed near exactly by resetting the MuJoCo environment to
the specific state-action pair $(s,a)$ and running the policy for $1000$ time
steps (the environment and policy are deterministic, so one trajectory is
sufficient to estimate the true value). Value error is normalized by a per-
environment constant equal to the average true value $Q^{\pi}$ over the on-
policy evaluation dataset $\mathcal{D}_{\text{on-policy}}$:

$K=\frac{1}{|\mathcal{D}_{\text{on-
policy}}|}\sum_{(s,a,r,s^{\prime})\sim\mathcal{D}_{\text{on-
policy}}}Q^{\pi}(s,a).$ (89)

We report the values of $K$ used in Table 6.

Environment | $K$
---|---
HalfCheetah | 1382.35
Hopper | 388.56
Walker2d | 529.12
Ant | 580.90
Humanoid | 571.29
Table 6: Values of the per-environment normalizing constant $K$, used to
normalize value error for better interpretability across tasks.

Evaluation datasets are each collected by using the same set of behavior
policies used to generate the training datasets, in other words with noise
levels $[0.0,0.1,0.2,0.3,0.4,0.5]$. Each evaluation dataset contains 1000
transitions, and is gathered by collecting 50k transitions, and then selecting
1000 of the 50k transitions with uniform probability. Error terms are computed
over an evaluation dataset of 1000 transitions, generated in similar fashion
as the training datasets.

Termination. The MuJoCo environments are time-limited at $1000$ time steps.
Since using time-limited termination (which is not represented in the state)
breaks the Markov property, we follow standard practice (Fujimoto et al.,
2018; Haarnoja et al., 2018a) and only consider a state terminal if
termination occurs before $1000$ time steps. In other words, $\gamma=0$ if a
state $s_{t}$ is both terminal and $t<1000$, and $\gamma=0.99$ otherwise.

Outliers. In the experiments for Table 1, for HalfCheetah with the $0.1$ and
$0.2$ datasets the value function trained by FQE diverged on several seeds
(see Section C.2 for visualization), these trials were removed when computing
the values in the table. Note that this does not affect the conclusions made,
as we are interested in the existence of problems with the Bellman error, not
comparing the performance of BRM and FQE.

Tables (2 & 3) report Pearson’s correlation coefficient. Since this measure is
not robust to outliers, for FQE we remove the 30% of data points with the
highest Bellman error terms (functions trained with BRM had no obvious
outliers).

Single trajectory experiments. In Figure 3 and Section A.3 experiments were
performed over a single on-policy trajectory. This trajectory was collected by
the expert target policy. Unlike the other experiments, termination was used
so that the dataset was complete (contained every relevant transition). To
reduce the importance of propagating values, we added the average reward in
the dataset, scaled by the horizon (i.e. $\frac{1}{1-\gamma}=100$), to the
terminal reward $r_{T-1}\leftarrow
r_{T-1}+\frac{\gamma}{(1-\gamma)T}\sum_{i=0}^{T-1}r_{i}$, where $T=1000$ is
the total numbers of transitions in the trajectory. Additionally, algorithms
were trained for 250k time steps rather than 1M.