Why Should I Trust You, Bellman? Evaluating the Bellman Objective with Off-Policy Data
Authors: Scott Fujimoto
David Meger
Doina Precup
Ofir Nachum
Shixiang Shane Gu
Venue: ICLR 2022 Submitted (2022)
Keywords: reinforcement learning
off-policy reinforcement learning
off-policy evaluation
deep reinforcement learning

Abstract: In this work, we analyze the effectiveness of the Bellman equation as a proxy objective for value prediction accuracy in off-policy evaluation. While the Bellman equation is uniquely solved by the true value function over all state-action pairs, we show that in the finite data regime, the Bellman equation can be satisfied exactly by infinitely many suboptimal solutions. This eliminates any guarantees relating Bellman error to the accuracy of the value function. We find this observation extends to practical settings; when computed over an off-policy dataset, the Bellman error bears little relationship to the accuracy of the value function. Consequently, we show that the Bellman error is a poor metric for comparing value functions, and therefore, an ineffective objective for off-policy evaluation. Finally, we discuss differences between Bellman error and the non-stationary objective used by iterative methods and deep reinforcement learning, and highlight how the effectiveness of this objective relies on generalization during training. 

Under review as a conference paper at ICLR 2022
WHY SHOULD I TRUST You, BELLMAN? EVALUATING THE BELLMAN OBJECTIVE WITH OFLICY DATA
Anonymous authors Paper under double-biee blind review
ABSTRACT
In this work, we analyze the effectiveness of the Bellman equation as a proxy ob- jective for value prediction accuracy in off-policy evaluation. While the Bellman equation is uniquely solved by the true value function over state-action pairs, we show that in the finite data regime, the Bellman equation can be satisfied ex- actly by infinitely many suboptimal solutions. This means that Bellman error can be minimized without necessarily improving the accuracy of the value function. We find this observation extends to practical settings; when computed over an off- policy dataset, the Bellman error bears little relationship value prediction error. Consequently, we show that the Bellman error poor metric for comparing value functions, and therefore, ineffective objective for off-policy evaluation. Finally, we discuss differences between Bellman error and the non-stationary ob- jective used by iterative methods and deep reinforcement learning, and highlight how the effectiveness of this objective relies on generalization during training.
INTRODUCTION
In reinforcement learning (RL), value functions are measure of performance of target policy. Value functions are an important quantity in RL as they can be used to inform decision-making. Consequently, many modern reinforcement learning algorithms rely capacity (Gu et al., 2016; Schulman et al., 2017; Fujimoto et al., 2018: Badia et al., 2020).
value function in some
The Bellman equation is 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 straightforward approach for 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 prominent role in many historically significant approaches (Schweitzer & Seidmann, 1985; Baird, 1995; Bradtke & Barto, 1996; Antos et al., 2008; Sutton al., 2009), as well the more modern family of deep RL algorithms (Mnih et al., 2015; Lillicrap et al., 2015; Gu et al., 2016; Hessel et al., 2017).
In this work, we examine the relationship between the Bellman equation and the accuracy of value functions. We do so through off-policy evaluation (OPE), which presents the task of learning the value function of a target policy with data gathered from separate and possibly unknown behavior policy. OPE, which is subcomponent of virtually any off-policy RL algorithm, is an ideal setting for evaluating value functions as it provides a clear metric of performance (value prediction error) and provides consistency across trials (fixed dataset and target policy).
Our main thesis is that since the Bellman equation meant to consider the entire MDP and all possible state-action pairs, when it is instead estimated over finite dataset, there is likely to be some breakdown in its relationship to value prediction. This work aims to better understand that breakdown through theoretical analysis and empirical study. Our key discoveries are under off- policy, function approximations, and finite data assumptions:
Bellman error is poor metric for value error. We find that given two arbitrary value functions, comparing their Bellman error is insufficient to determine which value function is more accurate. This problem is highlighted by experiments which show that value functions trained to minimize

---

Under review as a conference paper at ICLR 2022
Bellman error directly (Baird, 1995) have lower Bellman error but higher value error, than value functions trained by iterative methods (Ernst et al., 2005). We find that this con-correspondence in relative ordering over enror terms holds even when evaluated over on-policy data (Figure 2), and only worsens further with off-policy datasets (Figure 3).
Bellman error is poor objective for learning off-policy. A natural consequence of the Bellman error being a weak metric for value error, is that the Bellman error makes for a poor off-policy ob- jective. Our experiments show that value functions trained by different algorithms exhibit different behaviors. As such, Bellman error cannot be used as a metric for arbitrary value functions. However, we find that when comparing value functions trained by the same algorithm, Bellman error can be used as an accurate measure for value error, but only if the error terms are evaluated with on on-policy data (Table 1). This means that Bellman error only meaningful objective when used on-policy.
Iterative methods rely on generalization for successful training, Iterative methods, such as many deep RL. algorithms (Mnih et al.. 2015; Lillicrap et al., 2015), use slightly different objective than Bellman error, where the target is assumed to be fixed. This means the objective is non-stationary and evolves during learning. Similar to the Bellman error objective, we find that examining the FQE loss alone is insufficient to determine the accuracy of the value function. However, we remark that we can compare two functions if we take the loss with respect to the same fixed target. This means that if the frozen target is accurate, then the distance to that target is good proxy for value error. This exposes the reliance of iterative methods to generalization which occurs during training.
Our work highlights problems with using Bellman setting, and aims to provide practitioners a better understanding of Bellman equation- loss functions, the role of generalization in RL, and the learning dynamics of value functions. Our findings point to an underappreciation of the importance of finite data in widely used objectives and we encourage the community place a higher emphasis on practical settings.
as a signal, objective, in the off-policy
2 BACKGROUND
Reinforcement learning (RL) is an optimization framework for tasks of sequential nature (Sutton & Barto, 1998). Typically, tasks are defined as a Markov decision process (S, A, R, p. do. 7), with state space S, action space A, reward function R. transition dynamics p, initial state distribution do. and discount factor 7 E [o, 1). Actions are selected according to policy π.
The performance of policy measured by its discounted return E2 [E: 7"((s,, ac)]. Off- policy evaluation (OPE) is the task of approximating the value function (=(s,a) E, |E, 7'r(s,, a,) [30 = s, 40 = al of a target policy, given samples from an arbitrary dataset. A fundamental relationship regarding value functions is the Bellman equation (Bellman, 1957):
Q" a) Erp'''p,''' [r 7Q" (s',a')),
which relates the value of the current state aatien pair expectation over the next state-action pair. Given an approximate value function Q (distinguished from the true value function Q" by dropping the superscript) of target policy म, we denote the Bellman error e(x, a):
((s, a) Q(s, a) Ey.esmaa' [r + QQ(s (os((((())) d')]-
In policy evaluation, the main objective of interest is value enror of state-action pair A(s,a):
(ss, a) Q(s, (= a),
where QT, the true value function, is intractable without access the underlying MDP. A standard result is if the Bellman equation converges to the fixed point then the value function must be the true value function. We can re-frame this result in terms of Bellman errors and value errors.
Proposition 1 If the Bellman error c(s, a) for all state-action pairs (s,a) E S A. then the value error ( a) = for all state-action pairs (s, a) E S x A.
In instances where we cannot compute the Bellman error exactly, such as from samples in a non- deterministic environment, can instead use temporal difference (TD) learning, where the TD error 5(t) is sample-based approximation to Bellman error which can be computed over a transi- tion i (s,a,r,8), 5(i) == ((s,a) a) (r ~Qs'' a')), where a' is sampled from the policy m.
2

---

Under review as a conference paper at ICLR 2022
Note that the expected TD error is simply the Bellman error c(s, a) Er,,' (=((() where the two values are identical if the environment and policy are deterministic.
In this work we focus two algorithms based on the Bellman equation, which will update an approximate value function Q. using samples from a finite dataset D. Bellman residual minimiza- tion (BRM) (Baird, 1995) directly minimizes the Bellman enror samples from the dataset DD:
LBRM (Q) ==
1
Σ
(Q(s,a) (r+n)))(++((s
(4)
D
(s.am:"")"DDaa'>> a'
Fitted Q-Evaluation (FQE) (Ernst et al., 2005; Le et al., 2019) is an iterative method for minimizing Bellman error:
FFFE (Q)
E
(Q(s,a)-(r++ - (1+
(5)
[D]
(e.a..
The key distinction between the two algorithms is that BRM directly updates both Q(s, a) and Q(s',a'), a'), while FQE only considers ((s.a) This is because FQE uses Q(s',at a'), target value function which is updated Q 4- Q after a fixed number time steps (possibly including every time step), meaning that only the left side of the Bellman equation is directly updated.
EXPERIMENTAL DESIGN
Our goal to thoroughly evaluate the relationship between Bellman error (a measurable proxy) and value error (an unmeasurable true objective) in the case of off-policy evaluation with finite samples. In this section we outline the experimental choices used our empirical evaluation. Comprehensive experimental details (i.e. hyperparameters, architecture, etc.) can be found in the Appendix E.
Setting. We consider the setting of off-policy evaluation (OPE), as allows to directly compare value functions over clear metric, value error. Our experiments consider variety of 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 deterministic policy, makes the Bellman eπror and TD error identical. This allows us to compute the Bellman error exactly and ignore the double sampling issue for residual gradient methods (Baird, 1995). Value functions are trained to evaluate an expert deterministic target policy from fully trained TD3 agent (Fujimoto al., 2018), using a standard discount factor y = 0.99.
Algorithms. Our experiments are based on Bellman residual minimization (BRM) (Baird, 1995) and Fitted O-Ealuuaioon (FQE) (Ernst al., 2005; Le et al., 2019). We use these algorithms due to their popularity in the literature, and to highlight differences in methods which minimize Bellman error directly or indirectly. Network architecture and hyperparameters are the same between algo- rithms and are selected to match state-of-ther theh--rrtt deep RL methods (Fujimoto et al., 2018; Haarnoja et al., 2018a) for the MuJoCo domain. FQE is implemented using a target network updated with Polyak averaging. In every experiment, algorithms trained for I million time steps and 10 seeds.
Training Datasets. Each dataset is collected by using noisy versions of the target policy. This allows to rank the distribution shift of each dataset. Each noise level corresponds 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 in the range [-1, We uniformly random actions to ensure that not all actions are centered around the target policy, and Gaussian noise to ensure that every action is distinct from actions selected by the target policy.
Metrics. We use the mean squared Bellman error, as it is the most common objective on the Bellman error (Baird, 1995; Sutton & Barto, 1998). For better interpretability, we use the absolute value error, normalized by dividing by a constant term equal to the average true value function Q" sampled on- policy. As an example, this means that 0.1 value eтror roughly corresponds of 10%. Some experiments are repeated in Appendix D with variations of these metrics.
percent difference
4 THE BELLMAN EQUATION AS AN OBJECTIVE
In this section we discuss the role of the Bellman error as a proxy objective for value error. Our main result is that missing transitions break the fundamental relationship between Bellman error
3

---

Under review as a conference paper at ICLR 2022
and value error, meaning that one of these error terms can be minimized independently of the other. Consequently, this means that minimizing the empirical Bellman error makes for an ineffective ob- jective, as it does not guarantee corresponding reduction in value error. We show this problem theoretically and through simple examples (4.1), ), then demonstrate this phenomenon occurs in stan- dard, widely used benchmark environments (4.2). Finally, discuss the effectiveness of deep RI. methods in spite of these concerns, and highlight the role of generalization in off-policy RL (4.3).
4.1 THFORETICAL ANALYSIS
Recall the key idea behind the Bellman equation is that is uniquely satisfied by the true value func- tion over all state-action pairs. Therefore, if we are interested in off-policy evaluation, the Bellman error used as a measurable proxy objective to value error, which is typically unmeasurable, While completely minimizing the Bellman error results in the optimal solution, the Bellman error is only proxy to value error, and does not share an exact correspondence, even when considering the entire MDP. Consider the following proposition.
Proposition 2 For any constant C > 0 and discount factor 7 E (0, 1), there exists an MDP and pair of value functions (Q1, Q2) with Bellman errors (E1, and value errors (A1, A2), such that for all state-action pairs (s, a) E ES x A, the absolute Bellman error of Q2 is greater than the absolute Bellman error of Q1 by C, (e2(s,
le a)l C, but the absolute value error of Q1
is greater than the absolute value error of Q2 by C, (8, a)l - A2 a)l C.
This means that reduction in Bellman enror, even over all state-action pairs, does not guaran- tee a corresponding reduction in value error. To understand how this outcome is possible, con- sider infinitely long chain MDP, with reward r 0 for all transitions. Let lt 0. Let Q1(+) = b/(1-7) for all inputs, and let Q2(s;) = (-1)'k, in other words, i on even states and k on odd states. While Q1 clearly has higher absolute value error, when we look at the Bellman error, the distance between Q1 (s),-) and 7Q1 (s will be less than Q2(s;,)) .) and (Q((s(+1..) as Q2 swaps signs each timestep. See the Appendix B.2 for the full details.
This non non-correspondence between value error and Bellman eтror was possible as the absolute value of the Bellman error does not capture the bias the value error. We can better understand bias in the value error by simply summing the Bellman errors over relevant transitions.
GO
80
81
ao
Figure 1: A basic MDP. If (so; ao) is contained in the dataset but (81, (1) a1) is not, by carefully selecting the values Q(sp, an) and ((51, a1). we can construct ex- amples where the Bellman error of the dataset is 0 but the value error is arbitrarily large.
Theorem Let d= d''s''a'ss, r) Er ( + s' ())))((')s)), be the conditional discounted state-action occupancy, where p" ((s. a) + s,t) t) is the probability of leaving the state-action pair (s,a) and visiting
(1
the state s after I time steps. The value error A(s, a) of state-action pair (8, a) can be defined as a finccion of the Bellman error e(8', over d= (8', a))s
1 I- ((e
A a)
A direct consequence of Theorem 1 is the aforementioned uniqueness property of the Bellman equa- tion. 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 O. However, if we are instead examining a finite dataset, this relationship also exposes the concern that if any relevant transitions are missing, then the desired property of unique solution of the Bellman equation is broken.
Corollary If there exists a state-action pair (s', d') not contained in the dataset DD where the state-action occupancy d= (s', a'ls, a) 0, then for any C > O, there exists value function such that the Bellman error is 0 for all state-action pairs in the dataset D, while the value error of the state-action pair (s.a) is C.
Consider the simple two-state MDP defined in Figure/ 1. Suppose again we have reward r = 0 for all state-action pairs. If we suppose that the dataset contains the sole transition (so. ag r, 8,81) then
4

---

Under review as a conference paper at ICLR 2022
HalfCheetah
Hopper
Walker2d
Ant
Humanold
Bellman Error (MSE)
1000
1.5
0.15
100
800
100
1.0
0.10
75
600
00
0.5
50
400
200
0.0
3.8
0.0
21.5
0.0
0.5
4.1
HalfCherlah
Happer
Walker22
Ant
Humanoid
0.3
0.005
Valure Error
0.004
02
0.024
0.30
0 1.555
1000
0.000
0.000
0.1
0.050
0.000
0.15
0 0.025
0.0
0.5
Time Steps (1e6)
Time Steps (1e6)
Time Steps (1e6)
Time Steps (1e6)
Steps (1e6)
BRM
FQE
MC
Figure 2: Comparing the Bellman error (top row) with value error (bottom row) of value functions trained with a dataset of Im on-policy transitions. Error terms are evaluated over held-out test set of on-policy rollouts. The shaded area captures the standard deviation over 10 seeds. MC refers to Monte Carlo value estimation with bootstrapping to reduce bias from time-delimited episode termination. 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 MC estimate value error), this ordering not reflected value error. This shows overfitting of the Bellman error objective is possible even with on polpooic data and that we cannot determine value prediction accuracy by examining empirical Bellman error alone.
we can construct examples where the Bellman error is 0 but the value error arbitrarily large and conversely, where the Bellman error is arbitrarily large but the value error is O.
Example 1. (0 Bellman Error, C Value Error). We define the Q-values such that the Bellman error is 0 but the value error is C.
Q(50, 0n) C, If
c(so, 0n) C -
(0) 7 IC.
A(so, 0n) Q ao) - O= C.
Example 2. (C' Bellman Error, O Value Error). In this second example, we define the Q-values such that the Bellman error is C but the value error is O.
(se 0g) = 0, If Q(s1, ao) = -
c(Su, an) = =
A ( ao) = Q(50, un) - 0 0.
Note that these examples do not involve adversarially modifying the environment in some extreme manner, and instead occur due to the value estimate of the missing transition. As a result, these scenarios can still happen in practical settings where function approximation is used to estimate the values of missing transitions, as is difficult to control the behavior function approximation and guarantee avoiding these scenarios where the Bellman error is deceptively low.
4.2 KEY EXPERIMENTS
Everything we have discussed thus far has suggested that Bellman error may not be representa- tive proxy objective for value error. We now examine our ideas with empirical results. Our main observation is that the relationship between Bellman emor and value error is broken in finite data settings, particularly in the off-policy case. To so, we examine the Bellman error and the value error of value functions trained by BRM and FQE. Additionally, we remark that our experiments in deterministic domains, and as such, the problems we introduce are independent from the double sampling problem with BRM (Baird, 1995).
On-policy empirical Bellman error is insufficient to rank value functions. Figure shows the learning curves of value functions trained with on-policy data, and evaluated held-out test set of on- on-policy rollouts. Recall that while FQE uses an iterative approach based on the Bellman equation, BRM directly minimizes the Bellman error, and the Monte Carlo estimate (MC) does not use the
5

---

Under review as a conference paper at ICLR 2022
HalfChestah
Hopper
Walker2d
Ant
Humancid
Bellman Error (MSE)
100040
7500
8000
100
500
2500
50
250
03 Noise Level
01
0.6
0.0
0.2
0.5
0.0
04
Noise Level
Noise Level
Noise Level
Noise Level
HalfCheetah
Hopper
Walker2d
Ant
Humanold
0.6
0.8
0.4
Value Error
0.6
9/1
0.4
0.2
6.3
0.0
0.0
Noise Level
Noise Level
Noise Level
Noise Level
Noise Level
BRM
FQE
Figure 3: The final Bellman error and value error of functions trained with datasets gathered by increasingly noisy versions of the target policy. 0.0 is an on-policy dataset and the remainder are off-policy. Error bars capture the standard deviation over 10 seeds. Bellman error was clipped to 10k on the HalfChectah task for FQE for visual clarity, as the value estimate diverged for 0.1 and 0.2 noise levels (see the learning curves in Appendix C.2). FQE consistently outperforms BRM while having sigmificantly higher Bellman error. Additionally, while value prediction accuracy BRM drops substantially with increased distribution shift, the Bellman error term remains low throughout all settings, suggesting it possible to train function with low Bellman emor, regardless of its value accuracy.
Train Data
Test Data
Algorithm
HalfCheetah
Hopper
Walker2d
Ant
Humanoid
BRM
0.95
0.74
0.96
0.99
0.98
All
On-Policy
FQE
0.81
0.76
0.72
0.79
0.11
BRM
-0.46
-0.83
-0.74
-0.75
-0.65
All
0.1
FQE
0.57
0.85
-0.90
-0.60
0.20
BRM
0.11
0.04
-0.47
0.46
-0.48
0.1
0.1
FQE
0.92
0.29
-0.14
0.58
0.05
Table 1: Pearson's '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 computed using datasets varying noise levels, where refers the set (0.1, 0.2, 0.3, 0.4, 0.5) with 10 seeds, (6x 10 functions), 0.1 refers to the subset of functions trained on the 0.1 dataset (10 functions). While there high correlation between the on-policy empirical Bellman стrоr and value error when comparing functions trained with the same algorithm, this relationship is not strong when evaluated with off-policy dataset.
the test dataset. The functions
trained
Bellman equation its objective. Therefore, is unsurprising that the value functions trained by BRM have lower Bellman error than the value functions trained by FQE and MC. However, even when the FQE value functions have much higher Bellman error (such as Ant and Humanoid), the results in value error have inverse order, where the FQE and MC value functions have lower value error than the BRM value functions. These learning curves demonstrate that while BRM methods are capable of minimizing Bellman error more aggressively than FQE, the reduction in Bellman emoor is not reflected in value error. This means that even when working with large (1m) on-policy datasets, the empirical Bellman error should not be used rank the performance of value functions.
Although Figure 2 shows a large variation in Bellman error, for most tasks, the value functions are competitive in terms value prediction error. This means that although Bellman error is not an effective metric for selecting arbitrary value functions, it may still be effective objective. In Figure we test Bellman error as an off-policy objective. We display the final Bellman error and value error of value functions trained with off off-policy datasets, where the data is gathered by noisy version of the target policy. Next, we test Bellman error as a metric for value error across functions trained by fixed algorithm. In Table 1, we seperate the functions by algorithm, and then measure the

---

Under review as a conference paper at ICLR 2022
Train Data
Test Data
Metrie
HalfCheetah
Hopper
Walker2d
Ant
Humanoid
BE
0.81
0.76
0.72
0.79
0.11
All
On-Policy
CroE
0.81
0.79
0.60
0.81
0.22
MSE
0.78
0.95
0.96
0.98
0.77
BE
0.57
0.85
-0,90
-0.60
0.20
All
0.1
CPOE
0.62
0.84
-0,90
-0,59
0.21
MSE
0.96
0.84
0.72
0.97
0.85
Table 2: Pearson's correlation coefficient of varying metrics and the value error of functions trained with. BE: Bellman Error, Crge: the FQE objective, MSE: regression loss. This regression loss is with respect to fixed target is taken from the FQE objective from a single trial (and then kept fixed across all trials). Warm colors are used to show positive correlation and cold colors are used for negative correlation. The error terms evaluated over the test data. All functions (from Figure 3), trained with datasets of varying noise levels, included. We see that the difference between BE and Croe minimal, and that MSE with fixed target the most effective metric. This shows that we cannot compare functions using LroE because is non-stationary (and dependent on the current value function), but removing the dependency on the current value function (MSE) is strong proxy for value error.
correlation between these error terms. Train data denotes the set of training data, i.c. 'All' includes the entire set of final functions gathered from the experiments in Figure 3, and '0.1' I' includes only the functions trained on the dataset of 0.1 noise level. The test data describes which dataset the error terms are evaluated on. Our conclusions are as follows:
For a fixed algorithm, on-policy empirical Bellman error can be a good proxy for value error. Table I shows that when we separate the value functions by algorithm, and evaluate the error terms over on-policy data, there is strong correlation between the Bellman error and the value error. This means that Bellman error can be mcaningful learning objective when working with on-policy data, and explains the decent value prediction accuracy of BRM as shown in Figure 2.
Bellman error is ineffective off-policy objective. The signal between Bellman error and value error is muddied when the error terms are evaluated with off-policy data (0.1). For BRM, we find the error terms correlate negatively. This is likely due to BRM overfitting Bellman error objective. We also examine only the subset of functions which were trained with the 0.1 dataset, which means the functions compared all trained with the same algorithm and on the same dataset. While they exhibit a higher correlation than set of functions trained with different datasets, the relationship is still not clear across all tasks, In Figure 3, we note that the value prediction of BRM degrades rapidly in the presence of distribution shift. Furthermore, in spite of this performance drop, the Bellman error of BRM value functions is low for all datasets, which shows that the empirical Bellman error can be optimized independently of value error, when evaluated over an off- off-policy dataset.
BRM performs poorly because of premature convergence. Our theoretical results, such as Corol- lary 1, show there exists infinitely many suboptimal solutions where the Bellman equation is satis- fied. This means Bellman error an unreliable signal for value error, as there are infinitely many functions with low Bellman eиror but high value error. However, in practice, we have found that the behavior of BRM is predictable. In Appendix A we examine the final values estimated by BRM, trained with data collected by different behavior policies of varying noise levels, and compare them to the true value of the target policy as well as the behavior policy. We find that BRM produces final values which are (I) highly consistent across seeds, (2) highly influenced by the behavior policy, and (3) close to O. This means that BRM performs poorly as it tends to converge prematurely to the first low Bellman error solution (which is not reflected in low value error). Note that this premature convergence is not an aspect of FQE, which explains some of the performance gap between the two approaches. In the following section we will examine the success of FQE in more detail.
4.3 MEANINGFUL OFT-POLICY BELLMAN OBJECTIVE REQUIRES GENERALIZATION
We now discuss the performance of FQE. In the previous section, we saw an evident disconnect Bellman error and value error. Our results show value functions trained with FQE can have growing Bellman error (Figure 2), and yet achieve a high value prediction accuracy (Figure 3). The success of FQE is supported by many examples in the literature for OPE tasks (Voloshin al., 2019; Fu
7

---

Under review as a conference paper at ICLR 2022
et al., 2021; Fujimoto al., 2021), well control applications with deep RL (Mnih et al., 2015; Lillicrap et al., 2015; Hessel et al., 2017). In this section, we discuss how FQE can be an effective approach. in spite of the flaws of the Bellman equation. and highlight the role of generalization in making the FQE objective a meaningful proxy for value error.
Unlike Bellman error, the objective used by FQE is dependent on a target value Q:
LrQu (Q) = [D]
Σ (Q(s, - (r +((
(s,0,
As FQE is an iterative algorithm, we can view LFOE as an objective which is a function of the target Q. Therefore, analysis of FFo will require reasoning about an inconsistent target. Instead, we might consider a fixed version of FroE where we use single target across all trials. We should expect this metric to have increased relevance when comparing different value functions, as it is independent of the current value function. In similar fashion Table 1, in Table 2, we list the correlation between value error and three metries:
Bellman error (BE): : (Qo(s, a) - +r+ 1+++Q0il Qu((,aa')))
(10)
The FQE objective (Croe) (Qo(s, a) - (r "ooo"
(11)
Regression to a fixed target Q (MSE): (Qa(s, a) - -
(12)
We use the subscript to show the parameters of the value function, where 0 are the parameters of Q. 0 are the parameters of Q dependent on 0, and Q is fixed target network, independent of the 0. We determine Q by taking the final target Q3 of a single trial, and then fix it across all trials.
The results in Table show little difference between Bellman error and the FQE objective in deter- mining value error. More importantly, we see MSE to a fixed target has a strong relationship to value error. Given we have previously shown that FQE learns an accurate value function (Figure 3), then should be unsurprising that the distance to this target value function is a good proxy for value error. However, both the final Bellman error and FQE objective are also measuring the MSE to an accurate value function, but their values are dependent on the current value function, which makes them less valuable for comparing across different value functions. Ultimately, this experiment shows that the Bellman equation can be useful off off-policy objective if the target is accurate.
We can formalize the intuition "if the target is accurate, then distance to the target is a good proxy for value error" by the following proposition on proxy objectives.
Proposition 3 Given a pair value functions (Q1, Q2) with value errors (A1, A2), and targer y = r + QQs',, ,a). If sign(y - Q" (s.a)) = sign A (s, a)) = sign(A2(s, a)) and ly (s < min( A a)), [2 a)) then (Qi(s.)) - yl < (Q2(5. a) - y) implies [i (s) < a)).
This same observation could be applied equally to BRM methods. However, we remark that by optimizing both sides of the Bellman equation, BRM methods are directly modifying the target. We can understand some of the performance gap between FQE and BRM in that FQE is allowed to generalize, whereas in Figure 4, we see that BRM methods are pushed into early convergence, which favors solutions near O, and inhibits generalization in the target.
The Bellman equation needs generalization. The importance of the accuracy of the target, high- lights the reliance of the Bellman equation on generalization. With an off-policy and finite dataset, succeeding state-action pairs (s', d') are unlikely to be contained in the dataset. Consequently, Q(s',a') will only be accurate if the value function is able to generalize to this state-action pair'.
While this 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 ensure good generalization after training. it is only more difficult 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 al., 2019). A necessity of generalization at training time causes the significance of correct hyperparameters to be amplified.
A similar observation has heen made in the context of offline RI., with an emphasis on the ermos this generalization induces (Fujimoto al., 2019b).
8

---

Under review as a conference paper at ICLR 2022
5 RELATED WORK
The role of 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).
Close to our work, Maillard et al. (2010) perform finite sample analysis BRM methods with on- policy samples. Similar to our work, they conclude that the empirical Bellman error from on-policy samples is a reasonable approximation to the true Bellman error, but do not perform practical exper- iments or consider the off-policy setting. Kolter (2011) remarks that with off-policy sampling, the solution to linear TD can have arbitrarily large Bellman error but does not consider BRM methods, or finite datasets. Geist et al. (2017) evaluate the Bellman error as an objective for policy optimiza- tion. Although they examine a different setting, they arrive at a similar 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 a stochastic MDP. The double sampling issue provides motivation for most recent BRM methods (Feng et al., 2019; Zhu & Ying, 2020; Bas-Serrano et al., 2020). We avoid this particular issue in our analysis by focusing on deterministic environments, but remark that BRM is likely to perform even worse with stochasticity. Sutton & Barto (1998) show that in scenarios where the feature representation of states is not uniquely defined, there exist examples where 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.
Our observations connect strongly to offline RL (Lange al., 2012; Levine 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., 2018; 2019a; Kumar et al., 2019). 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 online 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 eπror is 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).
CONCLUSION
In this paper we examine the role of the Bellman equation as an objective. Our main observation is that the Bellman equation is only uniquely solved by the true value function when computed over the entire MDP. For given finite dataset, we show there can exist infinitely many suboptimal value functions which satisfy the Bellman equation. This exposes fundamental problem with Bellman error, in that it is not guaranteed to correspond to value error. We demonstrate this problem theo- retically, with toy problems, and empirically on standard benchmark environments. This result is highlighted by an empirical comparison between Bellman Residual Minimization (BRM) (Baird, 1995) and Fitted Q-Evaluation (FQE) (Ernst et al., 2005; Le al., 2019), which shows that value functions trained with BRM 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 min- imization emphasizes the double sampling problem (Dai et al., 2018; Feng et al., 2019; Saleh & Jiang, 2019; Ser-ano et al., 2020), our results show a much more fundamental problem; solv- ing the Bellman equation over a finite dataset does not guarantee
accurate value function. We give concrete evidence of this problem with practical experiments, and hope our findings provide practitioners, and theorists alike, better understanding of Bellman equation- based objectives.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Joshua Achiam, Ethan Knight, and Pieter Abbeel. Towards characterizing divergence in deep q- learning. arXiv preprint arXiv: 2019.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71(1):89-129 2008.
Adrià Puigdomènech Badia, Bilal Piot, Steven Kapturowski, Pablo Sprechmann, Alex Vitvitskyi, Zhaohan Daniel Guo, and Charles Blundell. Agent57: Outperforming the atari human benchmark. In International Conference on Machine Learning, pp. 507-517. PMLR, 2020.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pp. 30-37. Elsevier, 1995.
Joan Bas-Serrano, Sebastian Curi, Andreas Krause, and Gergely Neu. Logistic q-learning. arXiv preprinl arXiv:2010. 1115/,, 2020.
Richard Bellman. Dynamic Programming. Princeton University Press, 1957.
Dimitri P Bertsekas and John N. Tsitsiklis. Neuro-Dynamic Programming. Athena scientific Bel- mont, MA, 1996.
Steven J Bradtke and Andrew G Barto. Linear least-squares algorithms for temporal difference learning. Machine learning, 22(1):33-57, 1996.
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016.
Lin Chen, Bruno Scherrer, and Peter L Bartlett. Infinite-horizon offline reinforcement learning with linear function approximation: Curse of dimensionality and algorithm. arXiv preprint arXiv:2103.09847, 2021.
Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. Sheed: Convergent reinforcement learning with nonlinear function approximation. In International Con- ference Machine Learning, pp. 1125-1134. PMLR, 2018.
Logan Engstrom, Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras. Firdaus Janoos, Larry Rudolph, and Aleksander Madry. Implementation matters in deep rl: A case study on ppo and trpo. In International Conference on Learning Representations, 2019.
Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning- Journal of Machine Learning Research, 6(Apr):503-556, 2005,
Amir-massoud Farahmand and Csaba Szepesvári. Model selection in reinforcement learning. Ma-
chine learning, 85(3):299 332,, 2011.
Amir Massoud Farahmand, Rémi Munos, and Csaba Szepesvári. Error propagation for approximate policy and value iteration. Advances in Neural Information Processing Systems, 2010.
Yihao Feng, Lihong Li, and Qiang Liu. A kernel loss for solving the bellman equation. Advances in Neural Information Processing Systems, 32:15456 1455-15467. 2019.
Justin Fu, Aviral Kumar, Matthew Soh, and Sergey Levine. Diagnosing bottlenecks in deep q- learning algorithms. International Conference on Machine Learning, pp. 2021-2030. PMLR, 2019.
Justin Fu, Mohammad Norouzi, Ofir Nachum, George Tucker, Ziyu Wang, Alexander Novikov, Mengjiao Yang, Michael R Zhang, Yutian Chen, Aviral Kumar, Cosmin Paduraru, Sergey Levine, and Thomas Paine. Benchmarks for deep off off-policy evaluation. In International Conference on Learning Representations, 2021.
10

---

Under review as a conference paper at ICLR 2022
Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In International Conference on Machine Learning, volume 80, pp. 1587- 1596. PMLR. 2018.
Scott Fujimoto, Edoardo Conti, Mohammad Ghavamzadeh, and Joelle Pineau. Benchmarking batch deep reinforcement learning algorithms. arXiv preprini arXiv: 2019a.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In International Conference on Machine Learning, pp. 2052-2002 2019b.
Scott Fujimoto, David Meger, and Doina Precup. A deep reinforcement learning approach to marginalized importance sampling with the successor representation. In Proceedings of the 38th International Conference Machine Learning, volume 139, pp. 3518-3529. PMLR, 2021.
Matthieu Geist, Bilal Piot, and Olivier Pietquin. Is the bellman residual a bad proxy? In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 3208-3211 2017.
Shixiang Gu, Timothy Lillicrap, Ilya Sutskever, and Sergey Levine. Continuous deep q-learning with model-based acceleration. In International Conference on Machine Learning, pp. 2829- 2838, 2016.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International Confer- ence on Machine Learning, volume 80, pp. 1861-1870. PMLR, 2018a.
Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, et al. Soft actor-critic algorithms and appli- cations. arXiv preprint
2018b.
Matthias Heger. The loss from imperfect value functions in expectation-basee and minimax-based tasks. Machine Learning, 22(1):197-225, 1996.
Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep reinforcement learning that matters. In AAAI Conference on Artificial Intelligence, 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 reXiv:1710.022: 2017.
Alexander Irpan, Kanishka Rao, Konstantinos Bousmalis, Chris Harris, Julian Ibarz, and Sergey Levine. Off-policy evaluation via off-policy classification. Advances in Neural Information Pro- cessing Systems, 32:5437-5444 2019.
Max Jaderberg, Volodymyr Mnih, Wojeiech Marian Czarnecki, Tom Schaul, Joel Z Leibo, David Silver, and Koray Kavukcuoglu. Reinforcement learning with unsupervised auxiliary tasks. arXiv preprint arXiv:1611 1..00997 2016.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In International Conference Machine Learning, volume 2, pp. 267-274, 2002.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 14X2.6:4/2..999 2014.
Zico Kolter. The fixed points of off-policy td. In Advances Neural Information Processing Systems, 2011.
Aviral Kumar, Justin Fu, Matthew Soh, George Tucker, and Sergey Levine. Stabilizing off-policy q-learning via bootstrapping error reduction. In Advances in Neural Information Processing Sys- tems, pp. 11784-11799 1174, 2019.
Sascha Lange. Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In Reinforce- ment learning, pp. 45-73. Springer, 2012.
11

---

Under review as a conference paper at ICLR 2022
Hoang Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints, In Inter- national Conference on Machine Learning, pp. 3703-3712. PMLR, 2019.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tuto- rial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643 2020.
Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.0297 2015.
Odalric-Ambrym Maillard, Rémi Munos, Alessandro Lazaric, and Mohammad Ghavamzadeh. Finite-sample analysis of bellman residual minimization. Proceedings of 2nd Asian Conference on Machine Learning, pp. 299-314. JMLR Workshop and Conference Proceedings, 2010.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, Nature, 518(7540):529-5333 533, 2015.
Rémi Munos. Error bounds for approximate policy iteration. In ICML, volume 3, pp. 560-567, 2003.
Rémi Munos. Performance bounds in Lp-norm for approximate value iteration. SIAM journal on control and optimization, 46(2):541-561, 2007.
Tom Le Paine, Cosmin Paduraru, Andrea Michi, Caglar Gulcehre, Konrad Zolna, Alexander Novikov, Ziyu Wang, and Nando de Freitas. Hyperparameter selection for offline reinforcement learning. arXiv preprint arXiv:2007.09055 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. In Advances in Neural Information Processing Systems, pp. 8024-8035, 2019.
Ehsan Saleh and Nan Jiang. Deterministic bellman residual minimization. In Proceedings of Opti- mization Foundations for Reinforcement Learning Workshop at NeurIPS, 2019.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06:: 2017.
Paul Schweitzer and Abraham Seidmann. Generalized polynomial approximations markovian decision processes. Journal of mathematical analysis and applications, 110(2):568-582, 1985.
Satinder P Singh and Richard C Yee. An upper bound on the loss from approximate optimal-value functions. Machine Learning, 16(3):227-233, 1994.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction, volume 1. MIT press Cambridge, 1998.
Richard S Sutton, Hamid Reza Maei, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. 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.
Shengpu Tang and Jenna Wiens. Model selection for offline reinforcement learning: Practical con- siderations for healthcare settings. Machine Learning for Healthcare Conference, pp. 2-35. PMLR, 2021.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 5026-5033. IEEE, 2012.
Cameron Voloshin, Hoang M Le, Nan Jiang, and Yisong Yue. Empirical study of off off-policy policy evaluation for reinforcement learning. arXiv preprint arXiv: 106854, 2019.
12

---

Under review as a conference paper at ICLR 2022
Ruosong Wang. Dean Foster, and Sham M Kakade. What are the statistical limits of offline rl with linear function approximation? In International Conference on Learning Representations. 2020.
Ronald J. Williams and L. Baird. Tight performance bounds on greedy policies based on imperfect value functions. Technical report, Northeastern University, College of Computer Science, 1993.
Chenjun Xiao, Ilbin Lee, Bo Dai, Dale Schuurmans, and Csaba Szepesvari. On the sample complex- ity of batch reinforcement learning with policy-induced data. arXiv preprint arXiv:2 2021.
Mengjiao Yang and Ofir Nachum. Representation matters: Offline pretraining for sequential deci- sion making. In Self-Supervision for Reinforcement Learning Workshop-ICLR 2021, 2021.
Andrea Zanette. Exponential lower bounds for batch reinforcement learning: Batch rl can be ponentially harder than online rl. In International Conference on Machine Learning, pp. 12287- 12297. PMLR, 2021.
Yuhua Zhu and Lexing Ying. Borrowing from the future: attempt to address double sampling. In Mathematical and scientific machine learning, pp. 246-268. PMLR, 2020.
13

---

Under review as a conference paper at ICLR 2022
A
BRM FINAL VALUES
HalfCheetah
Hopper
Walker2d
Ant
Humanold
1250
400
500
500
1000
300
400
700
200
3800
500
200
200
100
250
100
Noise
Noise
Noise
Noise
Target Policy
Behavior Policy
BRM
BRM (Suboptimal larget policy)
Figure 4: 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 BRM when trained to evaluate suboptimal policy (corresponding TD3 trained for 300k time steps rather than 3m). Error bars capture the standard deviation 10 seeds (but visually hard see as the deviation low). We can see that BRM typically converges to value which 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 what value BRM converges reduced with increased distribution shift.
14

---

Under review as a conference paper at ICLR 2022
B PROOFS
B.I PROPOSITION
Proposition 1 If the Bellman error a) for all state-action pairs (8,d) E 8 A, then the value error (s,, a) = for all state-action pairs (8, a) E x A.
Proof. This is direct consequence of Theorem
B.2 PROPOSITION 2
Proposition 2 For any constant C > 0 and discount factor 7 E (0, 1), there exists an MDP and pair of value functions (Q1, Q2) with Bellman errors 62) and value errors (A1, A2), such that for all state-action pairs (8, a) E ES* x A, the absolute Bellman error of Q2 is greater than the absolute Bellman error of Q by C, le)(s,a)]
lei (s(s.)) a) C, but the absolute value error of Q is greater than the absolute value error of Q2 by C. [)(s - [Az(s, a)l > C.
Proof. Proof by construction. Consider infinitely long chain MDP, with reward all transitions. We will consider a more general case, where (e(s,a)² [ei(s, > C' and [A, - (5, a² C, for any b and d >
for
& Let k > 0. Let Q1( 1-y for all inputs, and let Q2(sc) (-1)'k, in other words, & on even states and k on odd states.
Since the value of all state-action pairs is 0, we have
d
Aa(() =
(13)
1a2() = kd,
(14)
and
k 7k b
(c(())
kbb
(15)
1- 1- 7/
le2(-) = + 1(k -kk)
(k + 7k)
(16)
We have
22 a)l² > C if:
d
kdd > C
(17)
1
1
7) bdd kd > c
(18)
7)d 1)bdd C
(19)
k>
(20)
(1-7)a
We have a)) ( Cf:
(k: + 7k)6 - 1/b >
(21)
- (1 + +7)²/² - kbb > C
(22)
= ((1 7/ - -1)bb 0
(23)
kン C
(24)
(1+7)b1]
(25)
15

---

Under review as a conference paper at ICLR 2022
Let max (1=S)==)
B.3 THEOREM
Theorem Let d" ('','''ss al)8,0)
be the conditional discounted state-action occupancy, where P ((,,a) + 8,1) is the probability of leaving the state- action pair (s, a) and visiting the state after time steps. The value error A(s, a) of state-action pair (s, a) can be defined as a function of the Bellman error e(s ( over d= (s', as)
-1 (1-7) (') - 8 {.)))(d'''') (()
(laaa A(s,0) = 1 -
(26)
Proof. Our proof follows similar steps to the proof of Lemma 6.1 in (Kakade & Langford, 2002) and likely others.
First by definition:
A(s, = Q(s,a) -(sss)
(27)
= (s,,a)) Q(s,a) A(s.a).
(28)
Then we can decompose value error:
(ss Q(s, a) as)
(29)
Q(s a) (r + (==,,("""s
(30)
=Qss a) (r -
(31)
=(ss -rr--(+++++-- (r+ ((ss (E a'))
(32)
= =e(s,a) + (
(33)
By treating A(s, a) value function and E(s', a') as the reward,
that:
Ass
B(rra) a')]-
(34)
Note that this theorem can also be applied finite horizon MDPs, either considering defini- tion of d= which accounts for the finite horizon, d= a a'|s,a] a) بول ΣT-1 7'p" ((s, a)
s', (a' (a'lss), s.), or by transforming the finite horizon MDP into an infinite horizon MDP by consider- ing episode termination to be terminal state which loops infinitely upon itself.
B.4 COROLLARY
Corollary If there exists state-action pair (s', a') not contained in the dataset D, where the state-action occupancy d= (s', a' a'|ss, a) > 0, then for any C > O, there exists a value function such that the Bellman error is for all state-action pairs in the dataset D, while the value error of the state-action pair (s,a) a) is C.
Proof. This is direct consequence of Theorem 1. Let D' contain the set of state-action pairs (s',a') not contained in the dataset D, where the state-action occupancy d (s', a (s a) > O. It follows that
1
A(s,a)
(35)
1 1-a
1
Σ
c(s',a')
Σ e(s'sd').
(36)
1-7 (8'.0')>')
(a
16

---

Under review as a conference paper at ICLR 2022
Recall
c(s,a) == Q(s, a) - Bnstrppa'' QQ
(37)
and there exists least one Q(s, a). such that (s,a) D'. It follows that we can choose a function Q such that T (x '('', = 0 but [
I- (as e = C.
B.5 PROPOSITION 3
Proposition 3 Given a pair value functions (Q1, Q2) with value errors A2), and target =
+ (Q(s', ,'). If sign(y (s,a)) a)) sign| A1 (s,a)) sign(Az(s, a)) and ly Q=
min( (1, (8) [2,s, a)l) then (Qi(s,)) a) - yl < [Q2(s, a) - yl implies (1 a)l < (2)
y1 2 yl
(38)
= 1Qi(s. - (= (Q y/ < [Q((s.a) Q
(39)
A1i(s a) - (y - Qu(=aa < (s)(s - (y - -=*(ss))))
(40)
A1(s,a) - 11u-Q"10 (s..a)) [))(s, 1v- Q*(,aa))
(41)
A1 a) < [)(s,))).
(42)
Where the second last line is from sign(y (s))s))) sign(A1(s,a)) sign(A2(s, a)) and ly - (s) (s,((A)(s,a)))) a)1, (s)
17

---

Under review as a conference paper at ICLR 2022
C
LEARNING CURVES
C.1
BRM
HalfCherlah
Hopper
Walker2d
Ant
Humanoid
Bellman Error (MSE)
2.0
1.5
1.0
0.5
1.0
0.0
0.0
030
0.5
1.0
0.0
HalfCheetah
Hopper
Walker2d
Humanoid
Value Error
0.0
0.4
0.4
0.
0.2
0.0
0.5
Time Steps (1c6)
Time Steps (1c6)
Time Steps (1c6)
Time Steps (1c6)
Time Steps (1c8)
(a) Evaluated with the Training Dataset
HalfCheotah
Hopper
Walker2d
Ant
Humanoid
Bellman Error (MSE)
300
100
30
30
200
100
20
20
HallCheetah
Hopper
Walker2d
Ant
Humanoid
1.0
1.0
1.0
1.0
0.0
0.0
0.0
Value
64
0.4
0.4
0.2
00
0.0
0.5
0.0
Time Steps (1e6)
Time Steps (1e6)
Time Steps (1c6)
Time Steps (1c6)
Time Steps (1c6)
(b) Evaluated On-Policy Dataset
Noise level:
0.1
0.4
Figure 5: Visualizing the learning curves of the Bellman error and value error of value functions trained by BRM. The shaded area captures the standard deviation over 10 seeds. We observe that Bellman error eval- uated with the on-policy dataset is roughly representative of the value error, while the Bellman evaluated with their training datasets is not.
18

---

Under review as a conference paper at ICLR 2022
C.2 FQE
Bellman (MSE)
HalfCheetah
Hopper
Walker2d
Ant
Humanoid
10000
1000
1800
400
7300
200
100
800
500
0.0
066 HalfCheetah
1.0
0.0
0.5 Hopper
0.0
3,5
0.0
0.5
1.0
0.0
0.5
1.0
Walker2d
Ant
Humanold
0.0
0.4
Value Error
0.0
0.3
0.3
04
0.
0.2
0.2
02
0.0
0.0
85
05
1.0
Time Steps (1e6)
Time Steps (1e6)
Time Steps (1e6)
Time Steps (1e6)
Time Sleps (1e6)
(a) Evaluated with the Training Dataset
HalfCheetah
Hopper
Walker2d
Humanoid
Bellmnn Error (MSE)
10000
1000
130
800
160
7500
100
500
200
30
200
HalfCheetah
Hopper
Walker2d
Antt
Humanold
1.0
0.0
0.0
0.20
Error
0A
0.10
0.4
0.2
02
0.2
02
0.5
Steps (1e6)
Steps (1e6)
Steps (1e6)
Steps (1e6)
Steps (1e6)
(b) Evaluated with On-Policy Dataset
Noise level:
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 FQE. The shaded area captures the standard deviation over 10 seeds. Bellman error of individual trials is clipped to 10k for visual clarity.
19

---

Under review as a conference paper at ICLR 2022
WHAT IF... D
D.1 WE COMPARE ABSOLUTE BELLMAN ERROR TO ABSOLUTE VALUE ERROR?
Figure and Table I compare the mean squared Bellman error to the absolute value error. In this section we repeat these results comparing absolute Bellman error to absolute value error (Figure 7, Table 3), and mean squared Bellman error to mean squared value error (Figure 8, Table 4). We find that our observations are consistent with the observations in the main body.
HalfCherlah
Happer
Walker2d
Ant
Humanoid
Beliman Error (Abs)
1.0
0.5
0.
0.
0.2
0.0
0.0
2.0
0.5
0.0
0.5
0.0
0155
030
0.5
1.0
0030
0.5
1.0
HallCheetah
0.5
Hopper
0.006
Walker2d
0.35
Ant
Humanoid
Value Eroor (Abs)
0.004
0.30
0 100
0.29
0.000
0.000
0.00
0.000
0.15
0.020
0.0
0.6
10
00
0.5
1.0
0.000
0.5
3,5
0.10
0.5
0.5
1.0
0.000
08
0.5
1.0
Time Steps (1e6)
Time Steps (1c6)
Time Steps (1c6)
Time Steps (1c6)
Time Steps (1c6)
BRM
FQE
MC
Figure 7: Comparing the absolute Bellman error with the absolute value error. The shaded area captures the standard deviation 10 seeds. Both algorithms trained using on-policy data collected the target policy.
HalfCherlah
Happer
Walker2d
Humanoid
Boliman Enor (MSE)
1000
1.6
100
1.0
0.10
600
50
0.5
0.00
200
HalfCheetah
Hopper
Walker2d
Ant
Humanoid
Value Error (MSE)
5.00
20
0.010
76-
4.78
0.006
4:20
0.044
50
4.00
0.002
5
3.70
0.000
0.5
Steps (1e6)
Time Steps (1e6)
Time Steps (1e6)
Time Steps (1c6)
Sleps (1e6)
BRM
FQF
Figure 8: Comparing mean squared Bellman error 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.
20

---

Under review as a conference paper at ICLR 2022
Train
Test Data
Algorithm
HalfCheetah
Hopper
Walker2d
Ant
Humanoid
BRM
1.00
0.97
1.00
1.00
1.00
All
On-Policy
FQE
0.79
0.79
0.83
BRM
0.01
0.72
-0.18
-0.61
-0.50
All
0.1
FQE
0.73
0.54
-0.58
-0.07
0.67
BRM -0.08
0.53
-0.14
0.49
-0.15
0.1
0.1
FQE
0.99
0.76
0.01
0.43
0.27
Table 3: Pearson's correlation coefficient of the final absolute Bellman error and absolute value error of func- tions trained with either only BRM only FQE. Warm colors used to show positive correlation and cold colors used for negative correlation. The are trained using datasets varying noise levels, where all refers to the set (0.1, 0.2, 0.3, 0.4, 0.5) with 10 seeds, (6x 10 functions), 0.1 refers to the subset of functions trained on the 0.1 dataset (10 functions), This is repeat of Table comparing absolute Bellman error to absolute value error (rather than MSE Bellman enror). Similar observations can be made.
terms are computed over the dataset. The functions
Train
Test Data
Algorithm
HalfCheetah
Hopper
Walker2d
Ant
Humanoid
BRM
0.97
0.79
0.99
0.99
1.00
All
On-Policy
FQE
0.63
0.63
0.55
0.15
BRM
-0.29
-0.70
-0.58
-0.77
-0.58
All
0.1
FQE
0.56
0.82
-0.91
0.20
BRM
0.95
0.32
-0.13
0.53
0.54
0.1
0.1
FQE
0.12
0.06
-0.47
0.28
-0.48
Table 4: Pearson's 's correlation coefficient of the final mean squared Bellman error and mean squared value error of functions trained with either only BRM only FQE. Warm colors used to show positive correlation and cold colors functions are trained using datasets varying noise levels, where all refers with 10 seeds, (6x 10 functions), 0.1 refers to the subset of functions trained on the (.11 dataset (10 functions). This is a repeat of Table 1. comparing mean squared Bellman error to mean squared value error (rather than absolute value error). Similar observations be made.
used for negative correlation. The
computed over the test dataset. The set (0.1, 0.2, 0.3, 0.4, 0.5)
21

---

Under review as a conference paper at ICLR 2022
D.2 ...WE USE LESS DATA?
All of our experiments use datasets of Im transitions. In Figure 9 we repeat the experiment in Figure with dataset of 50k transitions, rather 1m. We find our observations are unchanged in this setting, in that FQE and MC have much higher Bellman errors but lower value errors than BRM.
HalfCheetah
Hopper
Walker2d
Ant
Humanold
Bollman Error (MSE)
400
2.0
400
10.0
1.5
800
7.5
5.0
400
100
2.5
0.5
100
0.0
0.0
0.0
0.5
0.9400
MalfChectah
0.25
Hopper
0.025
Walker2d
0.20
Ant
0.20
Humanold
Value Eroo
0.20
0.004
0.18
0.15
0.0350
0.1b
0.000
0.10
0.0325
0.14
0.0300
0.001
0.12
0.05
0.020
40
03
10
0.00
0.5
10
0.000
0.10
010
05
1.0
0.00
0.5
Time Steps (1e6)
Time Steps (1e6)
Time Steps (1e6)
Time Steps (1e6)
Time Steps (1e6)
BRM
FQE
MC
Figure 9: Comparing the mean squared Bellman error with the absolute value error, using dataset of 50k, rather than Im as in Figure 2. The shaded area captures the standard deviation over 10 seeds. Both algorithms trained using on-policy data collected by the target policy.
22

---

Under review as a conference paper at ICLR 2022
D.3 ...WE USE TRAINING ERROR INSTEAD OF TEST ERROR?
Figure evaluates the Bellman error and the value error on a held-out test set. In section we show the results on the training set (Figure 10). We see identical figures. This shows that the dataset sufficiently large that overfitting to individual transitions does not occur.
HalfCheetah
Hopper
Walker2d
Ant
Humanold
Bellman Erro (MSE)
150
0.20
200
1.5
000
0.15
1.0
400
0.06
50
0.0
0.00
0.0
0.5
1.0
HalfChectah
Hopper
Walker2d
Ant
Humanoid
0.3
0.025
0.35
0.150
Valuue Error
0.004
0.30
0.000
0.2
0.2
0 100
0.000
0.07
0.000
0.20
0.000
0.15
30
0B
1.0
0.5
0.001
05
0.10
010
0.5
0.000
0.5
Time Steps (1e6)
Time Steps (1e6)
Time Steps (1e6)
Time Steps (1e6)
Time Steps (1e6)
(a) Training Dataset
HalfCheelah
Hopper
Walker22
Humanoid
Ballman Enrrr (MSE)
1000
100
1.0
0.10
75
600
50
0.5
0.00
200
HalfCheetah
Hopper
Walker2d
Ant
Humanoid
0.8
0.000
0.35
0.150
Valuee Error
0.094
0.004
0.30
0 0.12
6.002
02
100
0.25
0.000
8.75
0.1
0.000
0.008
0.15
0.025
0.0
0.5
Steps (1e6)
Time Steps (1e6)
Time Steps (1e6)
Time Steps (1e6)
Sleps (1e6)
(b) Test Dataset
BRM
FQE
MC
Figure 10: Comparing the Bellman with value The shaded area captures the standard deviation over 10 seeds. Both algorithms are trained using on-policy data collected hy the target policy. Figure shows Bellman error and value error, evaluated on a held-out test set (repeated in Figure 10b). In this figure we also display the emror terms over the training set (Figure 10a). We see near identical figures. This shows that the dataset is sufficiently large that overfitting to individual transitions does not occur.
23

---

Under review as a conference paper at ICLR 2022
D.4 ...WE USE TRAIN FOR LONGER?
All of our experiments train for Im timseteps. In Figure 11 we repeat the experiment in Figure while training for 10m time steps, rather mm. Interestingly, between FQE and BRM at 10m time steps, but otherwise our observations are unchanged with additional training.
more consistent relative ordering
HalfCheetah
Hopper
Walker2d
Ant
Humanold
Bellmaa Error (MSE)
1000
15
0.15
200
0.10
600
100
0.5
100
200
0.0
HaltCherlah
Hogper
0.005
Walker2d
Ant
Humanoid
0.004
0.125
Valuee Error
0.2
0.004
0,100
0.003
0.1
0.060
0.000
0.028
0.
Time Steps (1e6)
Time Steps (1e6)
Time Steps (1e6)
Time Steps (1e6)
Time Steps (1e6)
BRM
FQE
MC
Figure 11: Comparing the mean squared Bellman error with the absolute value error using dataset Im but trained for 10m time steps total, rather than m as in 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.
24

---

Under review as a conference paper at ICLR 2022
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. 1,50 (Todorov al., 2012)
mujoco-py -y 1.50.1.1
-v3 versions the MuJoCo environments were used.
Hyperparameters. FQE and BRM used the same hyperparameters and architecture, described Table These hyperparameters were chosen to match TD3 and SAC (Fujimoto et al., 2018; Haarnoja al., 201 8a), state of the art off- off-policy RL algorithms used in the MuJoCo domain. Fol- lowing these algorithms, both FQE and BRM set the discount factor y to for terminal states (and 0.99 otherwise). FQE uses Polyak averaging for the target network update. Given parameters 0 of the current network, the parameters of the target network are updated by the following after each time step:
0 + (1- + T0,
(43)
where t is the target update rate. This rule is commonly-use update rule by many off-policy RL algorithms for continuous actions (Lillicrap al., 2015; Fujimoto al., 2018; Haarnoja al., 2018b).
Hyperparameter
Value
Optimizer
Adam (Kingma & Ba, 2014)
Learning rate
3e-4
Network Hyperparameters Mini-batch size
256
Target update rate (FQE)
5e-3
Discount factor
0.99
Terminal Discount factor
0.0
Network Hidden dim
256
Architecture
Network Hidden layers
2
Activation function
ReLU
Table 5:
Hyperparameters and architecture.
OPE target. In each experiment, evaluate the discounted return of a deterministic target policy taken from TD3 (Fujimoto et al., 2018) trained for 3 million time steps. Our implementation TD3 based directly off of the author-provided Github (https: //g//titt thub. com/ sfujim//////////// TD3). For all experiments, the discounted return uses a discount factor of ? = 0.99.
Dataset and behavior policy. Datasets collected by using noisy variation of the target policy Te. For a noise level n E [0.0, 0.1, 0.2, 0.3, 0.4, 0.5), the behavior policy ny is defined as:
(s) + (0 n),
with = 70,
ny (s)
(44)
uniform random action with 1 - n.
Most experiments use dataset of 1 million transitions, matching the replay buffer size of TD3/SAC.
Metries and evaluation datasets. The main metrics used are Bellman error and value error. Given an evaluation dataset D. and value function Q, the mean- equared Bellman error is computed by:
Σ
(Q(s, a) - (r =Q(((a()))
(45)
De
Given an evaluation dataset D. and value function Q. the normalized absolute value error is com- puted by:
Σ
((s,.) - Q" (s)
(46)
D|De
LLcenne information: https: /ttp:s///wwww//// robot .ua/1 cense. html
25

---

Under review as a conference paper at ICLR 2022
(=,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. Value error is normalized by per- environment constant equal to the average true value Q" over the on-policy evaluation dataset o.o:
K
E (=,
(47)
Do.ol
(r.
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 inter- pretability 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 uniformly randomly saving 1000 of the 50k transitions. Error terms are computed over an evaluation dataset of 1000 transitions, generated in similar fashion as the training datasets. Tables (1 & 2) report Pearson's 's correlation coefficient. Since this measure is not robust outliers, for FQE we remove the 30% of data points with the highest Bellman error terms (functions trained with BRM had no obvious outliers).
26


Reviews:
[{"review_id": "qML2-Zv3TB", "reviewer": "Reviewer_ZRun", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strong Points\nSignificance: I agree with the authors that the empirical demonstration of comparing Bellman error (training loss) vs value error (testing loss) is less considered in off-policy evaluation community and should receive higher emphasis. This paper may bring potential attention to the community to rethink of how to view Bellman error into the design of the algorithm.\n\nCounterexample Construction: The paper construct several simple MDP as counterexample that the Bellman error is not with aligned with the value error.\n\nEmpirical evaluation: The empirical evaluation of this paper is extensive and provides useful insight. Reader can save their time to try BRM on TD3 (which is extensively studied in this paper and is failed)\n\n## Weak Points\nNovelty: The direct use of BRM fails to solve the off-policy evaluation has been widely known in the community. The main conclusion in this paper tries to emphasis on the fail of generalization of the Bellman error because of the finite dataset. However, I believe there are a lot of off-policy evaluation papers, especially those with high confidence interval estimation papers are trying to take the finite sample into account. Without any model assumption on either the value function, dynamics, rewards or density function, no algorithm can learn the region we have not observed and the value error can be arbitrary (like what you said in the example in Fig. 1) and therefore we need to make reasonable assumption in order to generalize the existing region's information. If we can assume the value function to be in a linear class, or smooth or with a known Lipschitz constant we can definitely be able to generalize (check theoretical papers for off-policy evaluation).\n\nQuality: I like the motivation of the paper, but when I go deep into the main body of the paper, I do not find too many new things to me and feel disappointed. I would expect a new algorithm can be provided to alleviate the difference between Bellman error and the value error by either under reasonable assumption or a new way of using the Bellman information. Another thing I would expect the explanation of the comparable success of FQE. Pro. 3 looks weak to me and only said that if the sign is the same, we can expect improvement. however, since the target network $Q_{\\bar \\theta}$ is also randomly initialized the same as $Q_\\theta$, we don't know much about the sign. Another point is that in real practice the target network can also updated in each iteration with a slower rate, so we cannot think this is similar to a fixed regression version in Eq. (13).", "summary_of_the_paper": "The paper tries to argue that the Bellman error cannot be trusted as a good metric or objective for off-policy evaluation. To support the argument, the paper provides theoretical analysis as well as extensive empirical analysis. Theoretical analysis gives a few example on the relation between the true value error and the Bellman error, which could be arbitrary especially under finite sample cases. Empirical results show that even when the Bellman residual is minimized well, the value error could be large in various of settings, in comparison, FQE consistently outperform BRM even when the Bellman error is much larger.", "summary_of_the_review": "In sum, I think this is an interesting paper and the topic worth further investigating. But so far the paper is not ready enough for the bar of the top conference like ICLR. I would vote for rejection at this moment and encourage the authors to further improve on the idea and submit to another venue.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Y7GmstBYCXU", "reviewer": "Reviewer_oTrW", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### **Strengths**\n+ Exposition is clear and easy to follow. \n+ The paper includes theoretical analyses that are simple and to the point, and makes good use of illustrative examples. \n+ Empirical experiments test various settings to support the main claims, and results are nicely summarized in figures/tables. \n\n### **Weaknesses**\n- Could you comment on the connection between the notion of “generalizability during training” and “realizability/completeness of function approximator” [1]\n- There are two ways Bellman error can be used: (i) as the loss function to optimize, and (ii) as a metric to compare two different value functions. The authors provided a good review of (i) in Sec 5, which is more on the learning aspect. More recently, researchers looking at the model selection aspect, which is more related to (ii), have made similar observations that the TD error loss does not correlate well with policy value/performance [2][3][4]. Therefore, I think adding a discussion on model selection can strengthen the work and potentially resonate with more researchers. \n\n\n### **References**\n1. Jinglin Chen, Nan Jiang. Information-Theoretic Considerations in Batch Reinforcement Learning. ICML 2019. https://arxiv.org/abs/1905.00360\n2. Tom Le Paine et al. Hyperparameter Selection for Offline Reinforcement Learning. 2020. https://arxiv.org/abs/2007.09055\n3. Shengpu Tang, Jenna Wiens. Model Selection for Offline Reinforcement Learning: Practical Considerations for Healthcare Settings. MLHC 2021. https://arxiv.org/abs/2107.11003\n4. Justin Fu et al. Benchmarks for Deep Off-Policy Evaluation. ICLR 2021. https://arxiv.org/abs/2103.16596\n", "summary_of_the_paper": "This paper examines the role of Bellman error as an objective function in offline reinforcement learning. The Bellman error measures how “closely” the estimated value function $Q$ satisfies the Bellman equation, while the value error measures how close the estimated value function $Q$ is to the true value function $Q^\\pi$. In offline RL and OPE, we’re interested in value error, but since the true value function is unknown, common practice is to look at Bellman error. \n\nThe paper provides both theoretical analysis, and empirical experiments using two algorithms related to Bellman error (BRM and FQE). The main takeaways are: (i) zero Bellman error implies zero value error, but (ii) low Bellman error doesn’t imply low value error, making it a poor objective to optimize and a poor metric to compare using, (iii) the success of practical iterative value-based methods like FQE that optimizes Bellman error-like losses relies on generalization during training to reliably predict values for unseen state-action pairs. \n", "summary_of_the_review": "This paper brings renewed attention to the role of Bellman error in offline RL, beyond the more widely known double sampling issue. In my opinion, Bellman error (or relatedly, TD error) is commonly thought of as the equivalent of *loss function* in supervised learning but for offline RL, and such analysis is much needed for the community and a good step at understanding the empirical success of deep RL and its fundamental difference compared to supervised learning. I would be strongly in favor of acceptance if the authors can aptly discuss how this contribution relates to the past work provided above. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "SYDAvMxJMOZ", "reviewer": "Reviewer_fSvY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\nThe message sent by this paper is very interesting and important. This paper challenges one broadly accepted method of using Bellman error as the objective function. It proves that minimizing empirical Bellman error can be far from minimizing the value error, especially for the off-policy evaluation problems. Their theoretical results are corroborated by experimental evidence.\n\nWeakness:\nThe theoretical results of the paper are not deep enough It basically only gives some existence result which is good but not helpful enough. It actually feels a little bit obvious.\nBesides, the case considered in the paper are limited. It only considers the discounted MDP setting, while ignoring many other important settings such as finite-horizon MDPs and goal-oriented MDP (i.e. shortest path). Therefore I wonder if similar results can hold for a broader class of models/problems.\n", "summary_of_the_paper": "This paper studies the relation between the Bellman equation and the accuracy of the value functions. This paper shows that Bellman error is not a good measure for comparing value functions and thus is an ineffective objective function for off-policy evaluation.\n", "summary_of_the_review": "Despite the weakness mentioned above, I still think this paper is good. The message is important and the results are novel and interesting.\n\nMy current recommendation is (weak) accept.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "3a1o4yse4ZP", "reviewer": "Reviewer_9cny", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n---\nThe paper is of relatively high quality. Experiments are carried out with a clear purpose and the methodology seems sound.\n\nThe paper is well-written and well-structured. Theoretical results are presented cleanly and with useful exposition. I did not carefully check through the proofs in the appendix. Experimental results are also presented well and generally easy to follow.\n\nAnd, as mentioned previously, these findings may be useful for a more complete understanding of when and why RL algorithms break down, especially in paradigms such as offline RL.\n\n\nWeaknesses\n---\nI am not an expert in this area, so I am unsure as to whether all of the results (the theoretical results in particular) are fully novel or if prior work has discovered similar or roughly the same results. Additional discussion of this in the related works section would be appreciated. In particular, it seems like results showing that Bellman error can be optimized without optimizing the true objective have probably appeared in prior work, though again, I am not sure.\n\nA potentially relevant line of recent work may be Q-learning and dynamic programming approaches to offline RL. [1] may serve as a useful survey here.\n\nSome greater analysis of the experiments would also be generally helpful. In Fig 2, are there potentially some conclusions missing due to incomplete training, e.g., some of the learning curves still exhibit a downward trend at 1 million steps? And explanations for some of the outliers, e.g., FQE HalfCheetah value error and BRM Hopper Bellman error, could prove insightful. A similar comment holds for Fig 3.\n\nMore vaguely, the tables and Fig 4 are harder to follow. Adding just a couple of sentences in the main text to more explicitly describe the tables and Fig 4 would likely fix this.\n\nEven more vaguely, but perhaps also most importantly, I still have lingering concerns regarding the significance of this work. Some examples of how this work may be significant are: the work provides insight for how to devise a better RL algorithm, or the work sheds light on why some prior RL algorithms work better than others. Currently in the text, I do not see clear arguments for either of these or other examples of what may be the immediate impact of this work. Should the authors have additional thoughts here regarding how the work may influence additional work (or provide insight into prior work), that would be appreciated.\n\n\n[1] Levine et al, \"Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems.\" arXiv 2005.01643.", "summary_of_the_paper": "This paper studies the Bellman equation commonly used in reinforcement learning (RL) algorithms. The typical motivation behind using the Bellman equation to design RL objectives is that uniformly driving the Bellman error to 0 implies that the true value function has been learned, i.e., the value error is 0. However, as this paper demonstrates both theoretically and empirically, a number of issues may arise before this point in practical regimes. For example, Bellman error and value error may not be well correlated, as shown via experiments evaluating minimizing the Bellman error directly versus fitted Q-evaluation. Furthermore, when evaluated using off-policy data, Bellman error may not even be well correlated with value error for different runs of the same algorithm. These findings may be useful for a more complete understanding of when and why RL algorithms break down, especially in paradigms such as offline RL.", "summary_of_the_review": "Primarily due to concerns about significance, I am initially recommending a weak accept of this paper. I am happy to engage in discussion with the authors and other reviewers in order to reach a more confident final recommendation.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies whether the Bellman error is a good metric to reflect the quality of value function estimation, focusing on finite-sample off-policy data sets. Both theoretical analyses and empirical experiments have been provided, showing that the Bellman error is often not the right metric to consider. However, while I appreciate the authors' theoretical attempts, the current theoretical contributions are not deep/significant enough. As the reviewers mentioned, the failure of the direct use of BRM is not surprising given the insufficiency of data (namely, no algorithm can make predictions on completely unseen regions unless further modeling structure is present). The authors might want to further strengthen their theory along this important direction.
Decision: Reject