Parameterized projected Bellman operator
Authors: Théo Vincent
Alberto Maria Metelli
Jan Peters
Marcello Restelli
Carlo D'Eramo
Venue: Submitted to ICLR 2023 (2023)
Keywords: reinforcement learning
bellman operator
operator learning
approximate value iteration

Abstract: The Bellman operator is a cornerstone of reinforcement learning, widely used in a plethora of works, from value-based methods to modern actor-critic approaches. In problems with unknown models, the Bellman operator requires transition samples that strongly determine its behavior, as uninformative samples can result in negligible updates or long detours before reaching the fixed point. In this work, we introduce the novel idea of obtaining an approximation of the Bellman operator, which we call projected Bellman operator (PBO). Our PBO is a parametric operator on the parameter space of a given value function. Given the parameters of a value function, PBO outputs the parameters of a new value function and converges to a fixed point in the limit, as a standard Bellman operator. Notably, our PBO can approximate repeated applications of the true Bellman operator at once, as opposed to the sequential nature of the standard Bellman operator. We prove the important consequences of this finding for different classes of problems by analyzing PBO in terms of stability, convergence, and approximation error. Eventually, we propose an approximate value-iteration algorithm to show how PBO can overcome the limitations of classical methods, opening up multiple research directions as a novel paradigm in reinforcement learning.

Under review as a conference paper at ICLR 2023
PARAMETERIZED PROJECTED BELLMAN OPERATOR
Anonymous authors
Paper under double-blind review
ABSTRACT
The Bellman operator cornerstone of reinforcement learning, widely used in a plethora of works, from value-based methods to modern actor-critic approaches. In problems with unknown models, the Bellman operator requires transition sam- ples that strongly determine its behavior, as uninformative samples can result in negligible updates or long detours before reaching the fixed point. In this work, we introduce the novel idea of obtaining approximation of the Bellman opera- tor, which we call projected Bellman operator (PBO). Our PBO is an operator on the parameter space of given value function. Given the parameters of a value function, PBO outputs the parameters of a new value function and converges to fixed point in the limit, as standard Bellman operator. Notably, our PBO obtain approximated repeated applications of the true Bellman operator, as op- posed the sequential nature of the standard Bellman operator. We show how obtain PBOs for representative classes of RL problems, and how to approximate it resorting to neural network regression. Eventually, we propose an approximate algorithm to learn PBOs and empirically evince how it can over- come the limitations of classical methods, opening up multiple research directions as novel paradigm in reinforcement learning.
INTRODUCTION
Value-based reinforcement learning (RL) is a popular class of algorithms for solving sequential decision-making problems with unknown dynamics (Sutton & Barto, 2018). For a given prob- lem, value-based algorithms aim at obtaining the most accurate estimate of the expected return from each state, i.e., value function. For instance, the well-known value-iteration algorithm com- putes value functions by iterated applications of the Bellman operator (Bellman, 1966), of which the true value function is the fixed point. Although the Bellman operator can be applied ex- actly in dynamic programming, it needs to be estimated from samples at each application when dealing with unknown models of RL problems, i.e., empirical Bellman operator (Watkins, 1989; Bertsekas, 2019). Intuitively, the dependence of value iteration the samples has impact on the efficiency of the algorithms and on the quality of the obtained estimated value function, which becomes accentuated when solving continuous problems that require value-based methods with function approximation. c.g.. approximate value itcration (AVI) (Munos, 2005; Munos & Szepesvári, 2008). Moreover, in AVI approaches, costly function approximation steps needed to project the output of the Bellman operator back to the considered action-value functional space. In this paper, we tackle these limitations by introducing the novel ap- proach of using samples to obtain a new operator, which we call pro- jected Bellman operator (PBO). Our PBO is function A Ω + Ω defined on parameters w E Ω of the value function. Contrarily to the standard (empirical) Bellman operator, which uses action-value func- tions Qwa to compute targets that are then projected to obtain Qweer. our PBO uses the parameters of the action-value function to compute updated parameters Wh+1 A(wa) directly (Figure 1). The crucial advantages of our approach are twofold: (i) the output PBO al- ways belongs to the considered action-value functional space, avoid- ing, therefore, the costly projection step typical when using the Bell- man operator, and (ii) once learned, PBO is applicable for an arbitrary number of iterations without using further samples, as visualized in Figure 2. Starting from initial parameters Wo, AVI approaches obtain consecutive approximations of the value function Qu,, by
Bellman Operator
Qwe
r
Q
PBO (ours)
Wx
A
Wi++
Figure I: PBO operates on value function parameters.

---

Under review as a conference paper at ICLR 2023
Q'
Quo
Qui
Qra(wo)
Quy(wo)
Qru
Qw
Qp (wo)
2n
2n
(a) PBO (ours)
(b) AVI
Figure 2: Behavior of our PBO and approximate value iteration (AVI) in the space of value functions. Q* and Qw- are respectively the optimal value function and its projection on the parametric space.
applying the Bellman operator iteratively over samples (Figure 2b). Instead, our PBO makes use of the samples to learn the operator only. Then, starting from initial parameters wo. PBO can produce a chain of updated parameters of arbitrary length (blue lines in Figure 2a) without requiring further samples. In the following, after formally introducing PBO and novel algorithm for value estima- tion based on it, we analyze its advantageous properties for different classes of problems. Thus, our contribution is threefold: (i) we introduce the notion of projected Bellman operator (PBO); (ii) show how to derive different PBOs according to the class of problems at hand; (iii) we develop a novel algorithm for value estimation based PBO and show its advantages related baselines on several RL problems.
2 RELATED WORKS
Our work is, to the best of our knowledge, the first attempt to obtain variant of the Bellman opera- tor that acts on the parameters of action-value functions. Nevertheless, several works in the literature proposed variants of the standard Bellman operator to induce some desired behavior. Variants of the Bellman operator are widely studied for entropy-reeullrized MDPs (Neu et al., 2017: Geist al., 2019; Belousov & Peters, 2019). The softmax (Haarnoja et al., 2017; Song al., 2019), mellowmax (Asadi & Littman, 2017), and optimistic (Tosatto et al., 2019) operators are all examples of variants of the Bellman operator to obtain maximum-entroop exploratory policies. Besides favoring exploration, other approaches address the limitations of the standard Bellman op- erator. For instance, the consistent Bellman operator (Bellemare et al., 2016) is modified operator that addresses the problem of inconsistency of the optimal action-value functions for suboptimal ac- tions. The distributional Bellman operator (Bellemare et al., 2017) enables to operate on the whole return distribution, instead of its expectation, i.e., the value function (Bellemare et al., 2023). Fur- thermore, the logistic Bellman operator uses logistic loss to solve a convex linear programming problem to find optimal value functions (Bas-Serrano et al., 2021). Finally, the Bayesian Bellman operator is a method in Bayesian RL to infer a posterior over Bellman operators centered on the true Bellman operator (Fellows et al., 2021). We point out that our PBO can be seamlessly applied on an arbitrary variant of the standard Bellman operator with just minor adaptations.
Operator learning. Literature in operator learning is mostly focused on supervised learning, with methods for learning operators over vector spaces (Micchelli & Pontil, 2005) and parametric ap- proaches for learning non-linear operators (Chen & Chen, 1995), with resurgence of recent con- tributions in deep learning. For example, Kovachki et al. (2021) learn mappings between infinite function spaces with deep neural networks, Kissas et al. (2022) apply an attention mechanism to learn correlations in the target function for efficient operator learning. The literature about operator learning is much larger, but we consider it out of the scope of this work that, to the best of our knowledge, is the first to deal with the original problem of operator learning in RL.
3 PRELIMINARIES
We consider discounted Markov decision processes (MDPs) M (S, A, P. R. 7). where S is a measurable state space, A is a measurable action space, P S x A + A(S)' is the transition
(AY')) denotes the set of prohability measures over the set X.
2

---

Under review as a conference paper at ICLR 2023
kernel of the dynamics of the system, R S A + R is reward function and 7 [0, is discount factor (Puterman, 1990). deterministic policy т : S + A is a function mapping a state to an action, inducing a value function (=)s) & E 7 ( (S:))) = s]. i.c., expected cumulative discounted reward following policy л. Similarly, the action-valle function (= a) & 1 ( A Au a, A, ((,)] is the expected discounted cumulative reward executing action in state s, following policy thereafter. RL aims to find an optimal policy n yielding the optimal value function V*(s) _ max (*),,, Vs E S (Puterman, 1990).
The (optimal) Bellman operator I is fundamental tool RL for obtaining optimal policies, and it is defined
(s))) R(s,a) + P(ds'ls. V(s,a) EXA
It is well-known that Bellman operators are contraction mappings in Loe-norm such that iterating over an action-value function leads to the fixed point n'Q" Q" in the limit (Bertsekas, 2015). We consider the use of function approximation to represent value functions and denote Ω the space of their parameters. Additionally, we define On {Qw :S x A - R E Ω} as the set of value functions representable by parameters of Q.
4 PROJECTED BELLMAN OPERATOR
The application of the Bellman operator in RL requires transition samples (Equation 1) (Munos, 2003; 2005; Munos & Szepesvári, 2008). The impact of this requirement is twofold: (i) the be- havior of the Bellman operator strictly depends on the quality of the samples, thus poor sample selection can result in negligible updates and long detours before convergence; (ii) the direction of the update is determined exclusively by the current samples, meaning that the empirical Bellman op- erator has no memory of previously observed samples (Bellemare et al., 2016; Agarwal al., 2019; Fellows et al., 2021). Ideally, we want to obtain an operator that mirrors the behavior of the true Bellman operator while being independent of the transition samples and extrapolating from previous experience. Thus, we introduce the idea of alternative operator, which we call projected Bellman operator (PBO), defined as follows.
[} be function approximation space for the value function, induced by the parameter space Q. A projected Bellman operator (PBO) is a function A Ω > Лt such that
Definition 1. Let On {Qw S A
R/w
A arg min B(e.a)<p.ooo (I - (s, Aff--
for some stute-uction distribution p and parameter distribution
Note that the symbol I* is the regular optimal Bellman operator on Qa- Conversely, PBO is an operator A acting the space of parameters Q. All proofs of following results can be found in Appendix
4.1 FUNCTION APPROXIMATION FOR PROJECTED BELLMAN OPERATORS
In the following, we show that PBO can be expressed in closed-form for representative classes of RL problems: (i) finite MDPs, (ii) low-rank MDPs (Agarwal et al., 2020; Sekhari et al., 2021), and (iii) linear quadratic regulation problems (Bradtke, 1992; Pang & Jiang, 2021).
4.1.1 FINITE MARKOV DECISION PROCESSES
Let us consider finite state and action spaces of cardinality N and M respectively, and tabular setting with N- Intuitively, there a trivial bijection between On and Q. which allows us to write the parameters of the action-valu value function Q instead of w.
Proposition The PBO exists and is equal to the optimal Bellman operator
(²)
7P max Q(:a).
aEA
Note that, since the optimal Bellman operator a y-contraction mapping for the sup-norm, PBO for finite MDPs (Equation 3) also -ccottrcctoon mapping.

---

Under review as a conference paper at ICLR 2023
4.1.2 LOW-RANK MARKOV DECISION PROCESSES
Low-rank MDPs is a class of problems with two feature maps S A R and μ 8 R².
such that P(s a) = (a,s, a), (u(s") and R(s,, a) (a(s, a), 0), for all (s,a, 8') Ax and for R. We assume, without loss of generality, that for all (s,0) E A, (|( S and max { (s) [0 S vd. We set the space of action-value functions to be the space of linear functions in the parameters, i... Qn ((((: w)|l RR..
Proposition 2. In case of continuous state and action spaces and for w E R2, the PBO is
J m (())))
(w) 0 +
The closed-form is again a y-contraction mapping under the assumption that the MDP has latent variable representation.
4.1.3 LINEAR QUADRATIC REGULATION
Eventually, consider the continuous MDPs class of linear quadratic regulator (LQR) with = R. The transition model a(s,a) = As + Ba deterministic and the reward func- tion R(s.u)- Qs² + 2Ssa + Ru is quadratic, where A, B Q. S and R, are constants inherent to the MDP. As commonly done for LQR, we consider an undiscounted setting, thus we do not an- alyze the contraction property of PBO. We choose parameterize the action-value -aluee functions with a 3-dimensional parameter vector Qa = {(8 + Gs² + 2Tsa + Ma (G, M) E RR,, for visualization purposes.
Proposition 3. The PBO exists and for any E RR2 RT its closed form is
++ AR 12 M
G
A w =
I
+
S AB(G 1
M7
(5)
M
R+ B² M)
A geometrical interpretation of the behavior of this PBO is available in Appendix A.
4.2 APPROXIMATING PROJECTED BELLMAN OPERATORS
For generic RL problems that do not fall into the previously described categories, the true PBO is unknown and has be estimated from samples. We propose approximate the unknown PBO with parameierized PBO As differentiable w.r.t. its parameters & E 6 enabling the use of gradient descent on a loss function. A first idea would be learn an operator that minimizes the loss in the definition of PBO (Equation 2). While this approach has the benefit of allowing to sample as many parameters as needed from Ω2 it does not leverage the crucial fact that approximating an operator allows to iterate over it as many times desired. Thus, our key insight is to include multiple iterations of the operator to the loss. The function to minimize becomes
(PBO(O) = =E ("Q (.00..(0))))0 Qx)co)(s,a))
(6)
for all w 22 E and a E A, and where K is an arbitrary number of optimal Bellman operator iterations. An additional idea is to add term that corresponds to an infinite number of iterations, i.e. the fixed point, when possible. Now, the loss becomes
Lpso+ = LLBO(Φ) + (r
Qsg(s,a)
Fixed point term
for all w E Ω2 E S, and E A, where Agg is the fixed point of the parameterized PBO. Note that the addition of the fixed point term is only possible for classes of parameterized PBOs where the fixed point can be computed and the computation is differentiable in the parameters Φb
IIf w R {0) (0), the formula still holds with the convention % 0.
4

---

Under review as a conference paper at ICLR 2023
I Quo wo
r"Q mp
Qr
I Q a (w))
Q
Q
Q wru
Q upo
Qr (wo))
Qr w
Q wr
Q Qw
Qry (wo) (wo)
2n
(a) PQI
(b) FQI
Figure 3: Behavior of PQI and FQI in the space of all value functions for one iteration. The dashed
lines represent the projections in Qn.
Algorithm Projected Q-Iteration (PQI)
1: Inputs:
samples D = {($}, a, r, s parameters W {wit
#Bellman iterations K, #training steps I, #fitting steps H, operator Aş to learn with initial parameters Φ Φo. learning rate
2: for 1.....16
3:
Compute the target T for 1...K do (3)) Ti, E W. X D do
4:
5:
for (Wi, (sy,
6:
(8), rj max Q A- (wi) (s)
AEA
optimal Bellman iteration
A (we)
7:
end for end for
8:
9:
Minimize the loss starting from the previous parameters
10:
Φ Φi-1
11:
E f
12:
for j E J do
13:
Φ - Φ
(T))))) - -u (()
14: end for
15: end for
16:
end for
17: return Parameters Φ of operator A
4.3 APPROXIMATE VALUE ITERATION FOR PROJECTED BELLMAN OPERATORS
We devise an approximate value iteration algorithm to learn parameterized PBOs by solving the optimization problems (6) and (7). The general structure of the algorithm closely resembles the one of Fitted Q-Iteration (Ernst et al., 2005), alternating one phase in which we compute the targets, and another one where we apply gradient descent fit parameters w.r.t. the targets (Algorithm 1). For this reason, we call our algorithm Projected Q-Iteration (PQI). When possible, the fixed point of the parameterized PBO added to the loss. interesting property of our method that it enables to build rich loss by including multiple optimal Bellman iterations at the same time, opposed to FQI that learns each Bellman iteration sequentially: Q E arg inf qu I' - Q|. Figure illustrates this advantage by comparing the way PQI and FQI behave in the space of all possible action-value functions. The ability of iterating for an arbitrary number of times enables us to derive theoretical advantages of PQI by leveraging established results in approximation error for AVI.
Theorem 1. (Theorem 3.4 of Farahmand (2011)) Let K E N P, U two distribution probabilities over S A. For any sequence (Qu)k C B (S A, R.) where R., depends the reward function

---

Under review as a conference paper at ICLR 2023
and the discount factor, we have
PQT
1
K Σ
l1Q" - Q= inf F(r; p,n))
2r Ok
ITQR-1-QA Qu11
+
(8)
re(o,1]
FQI
where as and CK,Y,R do not depend on the sequence (Q&) k=y trability coefficients of the greedy policies w.r.t the value functions.
K
F(r; K, p. 7) relies on the concen-
This theorem shows that the distance between the value function and the optimal value function depends on the approximation errors for all the iterations. The loss of FQI contains only one term of the sum, while the loss of PQI contains the entire sum. In PQI, the terms are summed up with equal weights, which is not the case for the error propagation. Future works could investigate how to weight those terms for increased performance.
EXPERIMENTS
We empirically analyze our PQI algorithm with different classes of parameterized PBOs w.rt. FQI (Ernst al., 2005) and, when possible, the additional baseline least-squares policy itera- tion (LSPI) (Lagoudakis & Parr, 2003). The fixed point is always added to the loss for the linear PBO, unless stated otherwise. The pseudocodes of FQI and LSPI are provided in Appendix B. Experimental details. Each algorithm receives a fixed dataset of samples 'D and has access to the same number of optimal Bellman iterations K. We define the initial parameters for both FQI and LSPI such that they result in a zero-function. We store the parameters after each iteration of the algorithms; then, we compute the action-value function for each iteration and the value function sociated with the greedy policy computed from the vation-value function at each iteration. PQI can access the same functions by iterating over the initial parameters for more than K' iterations, thanks to our parameterized PBO. When possible, we include the parameters corresponding to an infinite number of iterations, i.e., the fixed point of the parameterized PBO. We learn parameterized PBOs both with linear function approximators (linear PBO) and neural networks (neural PBO). We also report the performance of the fixed point the linear PBO (linear PBO fixed point). For problems when PBO is known in closed-form, we include it in the analysis as a reference (PBO in the figures). Additional details on the experiments are in Appendix C.
5.1 CHAIN-WALK
We initially consider the chain-walk environment Figure 4, with chain of length N = 20. We parameterize value functions as tables to leverage our theoretical results on finite MDPs (Section 1.). We plot the fg-norm between the iter- ated value functions and the optimal ones in Figure 5a. For all methods, the Bellman operator is iterated for K 5 times during training. The vertical black dotted line denotes the split between the iterations that are learnt and the iteration that can be only reached by parameterized PBO. Notably, we can it- erate the learnt PBO for an arbitrary number of times. This property is crucial to nullify the distance between the value function computed with the parameterized PBOs and the optimal value function. The superior per- formance of PQI comes from the fact that both classes of operators are close to the class of the PBO. Since in this setting the PBO perfectly replicates the behavior of the optimal Bellman operator, we can foresee that any algorithm minimizing the approximation error by learning parameters of value functions would perform in the best case as good as the PBO, meaning that their performance would coincide with the one of PBO at iteration 5. For this reason, any algorithm designed such would perform worse than or equal to FQI in this setting. Note that LSPI is not aiming at reducing the approximation error, this is why the reasoning does not apply this baseline.
0,1
2
0.9
0.1
The chain-walk from Munos (2003). Reward is always but 1 in green states.
Figure 4:
Analysis of the size of the dataset of parameters. Ideally, the dataset of parameters should con- tain parameters close the initial ones (the parameters with only zeros), others close to optimal

---

Under review as a conference paper at ICLR 2023
IIV Vnll2
I|V V*Il2
linear PBO
linear PBO; 20 weights
linear PBO fixed point
linear PBO: 50 weights
neural PBO
linear PBO; weights
FQI
P8O
PBO
5
10
15
20
25
10
15
20
25
#lteratioon
ltterations
(a) Approximation error.
(b) Ablation on parameters dataset.
Figure 5: f2-norm of the optimal value function and the value function induced by the Iearned greedy policy on chain-walk. Results averaged over 20 seeds with 95% confidence interval.
V*I|>
1|V
Ve
PBO
linear P&O fixed point
neural
FQI
LSPI
PDO
22
15
4tterations
#bterstions
(a)
(b) K 15.
Figure 6: Analysis on the number of Bellman iterations K on chain-walk.
parameters, and others in between. Since we only assume to know the initial parameters, we take parameters close to them, in the sense that the truncated normal distribution used for data collection is centered, Figure shows the distance to the optimal value function for different number of pa- rameters. Reasonably, the more parameters are given to the algorithm, the better the performance. Analysis on the number of Bellman iterations K. We additionally analyze the behavior of PBOs for different number of Bellman iterations than K 5. We consider K 2 and K 15, observing that the PBOs still behave well as shown in Figure 6.
5.2 LINEAR QUADRATIC REGULATOR
We consider the LQR setting in Section 4.1.3, leveraging our theoretical analysis by parameterizing value functions accordingly. Again, we consider a neural PBO and linear PBO. Figure 7a shows a metric proportional to the distance between the optimal value function and the value functions obtained at each iteration. For all methods, chosen class of operators is close to the class of the optimal PBO. We see that, at iteration 2, the performance of FQI and the PQI on par, while afterward, PQI keeps improving until the fixed point is reached. Again, we can state that any algorithm that learns parameters of value functions trying to minimize the approximation error, would perform worse than FQI. FQI follows the curve of the PBO, meaning that the training cannot be improved. LSPI performs badly because the first policy for the evaluation step a uniform policy, and the value function associated with the uniform policy is not a quadratic function.
set K 2. As in the previous experiment, the
Analysis on the number Bellman iterations K. Since the convergence of all the algorithms is fast in term of iterations, we additionally show the performance with 4 Bellman iterations instead of 2. Figures 7b confirms that PBOs perform well for a larger number of Bellman iterations.
Analysis on the size of the dataset of samples. We focus neural PBO. Figure 8a shows the distance to the optimal value function for trainings with a varying number of samples. When the grid becomes thinner, the distances are decreasing. However this decrease is not strong. This is why

---

Under review as a conference paper at ICLR 2023
j0
Pl| x |[V"
V=ll2
-P-Pl| IIV
10
linear PBO
10
linear PBO fixed point
neural
10a4
FQI
10
PBO
10-6
4
#iterations
#lterations
(a) K =
(b) K = 4.
Figure 7: fz-norm of the optimal value function and the value function induced by the learned greedy policy on LQR. Results averaged over 20 seeds with 95% confidence interval.
|p WIV"
Villa
10-1
0.0
linear PBO
neural PBO Fqi
10
optimal parameters
10-4
10a4
neural PDO: x samples
PBO: samples
neural PBO; 11 x 11 samples
16-1
PBO
0.0
0.1
#ttorations
0.0
-02
(a) Performance for different grid sizes.
(b) Iterated parameters the space Ω.
Figure 8: Analysis on number of Bellman iterations and visualization of iterated weights on LQR.
the size of the dataset is not crucial parameter for learning PBO. Visualization. This setting allow us to plot the parameters of the action-value functions space. The parameters corresponding to the iterations of PQI and FQI shown in Figure 8b. The training is done with = The first parameters for the three algorithms are on (0, 0, 0) and then, the iterations goes towards the optimal parameters being able to iterate after the training clearly makes the difference, as it clear that PQI is able to get closer to the optimal parameters after the second iteration.
the bottom right of the figure. In this case,
3,0
1.0
3.0
1.0
2.2
1.5
0.5
1.5
0.5
0.8
0.8
0.0
0.0
0.0
0.8
0.8
1.5
0.5
-1.5
0.5
2.2
-.2
3.0
-1.0
-3,0
-1.0
-0.5
-0.2
0.0
0.2
0.5
0.8
1.0
-0.8
.0.5
.0.2
0.0
0.2
0.5
0.8
1.0
(a) PQI's policy.
(b) FQI's policy.
Figure 9; Policies at iteration 9 on car-on-hill.
8

---

Under review as a conference paper at ICLR 2023
VVV
ynll2
11 Vella
linear PBO
linear PBO fixed point
neural
FO1
10 elterations
15
10
15
25
lteraaions
(a) K = 9.
(b) K = 15.
Figure 10: Weighted l2- norm for the value function on car-on-hill (see Appendix C.3). Results averaged over 20 seeds with 95% confidence interval.
Performance
Balancing time in seconds ds
500
400
300
N
800
200
1000
linear PBO fixed point
100
linear P60 fixed point
-1200
FOI
FO1
-1400
2
10 Ittrrtions
8
12
10
12
14
16
18
*
Alterations
(a) Bicyle performance.
(b) Bicycle balancing time.
Figure 11: Analysis for the Bicycle environment.
5.3 NON-LINEAR PROJECTED BELLMAN OPERATORS
We consider more advanced setting where the value function is approximated by neural network, thus the space value functions is not stable by the optimal Bellman operator. We focus on the car- on-hill MDP (Ernst et al., 2005), implemented in MushroomRL (D' ID'Ermmo et al., 2021), and the bicycle MDP in Randlov & Alstrøm (1998). We parameterize value functions with one hidden layer of 30 neurons, and we compare PQI only to FQI, since L.SP is not suitable for this setting. We train a linear PBO and neural PBO. We set K = 9 for car-on-hill and K = 8 for bicycle. Figure 9 shows the policies on car-on-hill for FQI and PQI trained with the neural PBO, where PQI is able obtain a significantly more accurate policy than FQI. Figures 10 and lla show that PBOs outperform FQI in terms of performance too. Interestingly, iterating further produces drop in performance for linear PBO, indicating that the class of linear operator is too simple. Remarkably, neural PBO either shows no deterioration (Figure 10a), or a slight deterioration due to opposite performance in different seeds (Figure lla and Appendix C.4), Further tuning should substantially reduce the number of failing seeds. This experiment evinces the limits of FQI where errors made at any iteration propagates until the last iteration (Theorem 1). Conversely, PQI can change the path to the optimal parameters at each optimization step.
CONCLUSION
We introduced the original idea of obtaining an approximation of the true Bellman operator, which we call projected Bellman operator (PBO). We defined PBO for different classes of problems, stud- ied their theoretical properties of stability and convergence, and devised novel approximate value iteration algorithm that provably reduces the error propagation over Bellman iterations. Finally, we have empirically shown the benefit of PBO over related baselines sider this work a seminal study of PBO as a novel paradigm of RL, that can lead to multiple research directions, among which investigating its use in online settings is first foreseeable avenue.
variety of problems. We con-

---

Under review as a conference paper at ICLR 2023
7 REPRODUCIBILITY STATEMENT
We aim to guarantee the reproducibility of our work by providing the proofs of our theoretical results and additional details of the conducted experiments in the appendix. Further, we provide the code for reproducing our results in the supplementary material, and we will make it public upon acceptance.
REFERENCES
Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seatlle Seattle, WA, USA, Tech. Rep, pp. 10-4, 2019.
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural com- plexity and representation learning low rank mdps. Advances neural information processing systems, 33:20095-20107,, 2020.
Kavosh Asadi and Michael L Littman. An altermative softmax operator for reinforcement learning. In International Conference on Machine Learning, pp. 243-24422222 252. PMLR, 2017.
Joan Bas-Serrano, Sebastian Curi, Andreas Krause, and Gergely Neu. Logistic q-learning. In Inter- national Conference Artificial Intelligence and Statistics, pp. 3610-3613 PMLR, 2021.
Mare G Bellemare, Georg Ostrovski, Arthur Guez, Philip Thomas, and Rémi Munos. Increasing action gap: New operators for reinforcement learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 30, 2016.
Mare G Bellemare, Will Dabney, and Rémi Munos. A distributional perspective reinforcement learning. International Conference on Machine Learning, pp. 449-458. PMLR, 2017.
Mare G. Bellemare, Will Dabney, and Mark Rowland. Distributional Reinforcement Learning. MIT
Press, 2023, http: /twp://wwww/////////////////to
st wtt.tiitttttttiiii.o.i.oo
Richard Bellman. Dynamic programming. Science, 153(3731):34-37, 1966.
Boris Belousov and Jan Peters. Entropic regularization of markov decision processes. Entropy, 21 (7):674, 2019.
Dimitri Bertsekas. Reinforcement learning and optimal control. Athena Scientific, 2019.
Dimitri P. Bertsekas. Dynamic Programming and Optimal Control 4 th Edition, Volume II. Athena Scientific, 2015.
Steven Bradtke.
Reinforcement learning applied to linear quadratic regulation. Advances in neural information processing systems, 5, 1992.
Tianping Chen and Hong Chen. Universal approximation to nonlinear operators by neural networks with arbitrary activation functions and its application to dynamical systems. IEEE Transactions on Neural Networks, 6(4):911-917, 1995.
Carlo D' D'Framo, Davide Tateo, Andrea Bonarini, Marcello Restelli, and Jan Peters. Mushroomrl: Simplifying reinforcement learning research. Journal of Machine Learning Research, 22(131): 1-5, 2021.
Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning- JMLR, 6:503-556, dec 2005. ISSN 1532-4435.
Amir-massoud Farahmand. Regularization reinforcement learning. 2011.
Mattie Fellows, Kristian Hartikainen, and Shimon Whiteson. Bayesian bellman operators. Advances in Neural Information Processing Systems, 34:13641-13633 2021.
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. theory of regularized markov decision processes. In International Conference Machine Learning, pp. 2160-2169, PMLR, 2019.
10

---

Under review as a conference paper at ICLR 2023
Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. In International conference on machine learning, pp. 1352-1361. PMLR. 2017.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In International Conference on Learning Representations, 2015.
Georgios Kissas, Jacob H Seidman, Leonardo Ferreira Guilhoto, Victor M Preciado, George J Pap- pas, and Paris Perdikaris. Learning operators with coupled attention. Journal of Machine Learning Research, 23(215): 2022.
Nikola Kovachki, Zongyi Li, Burigede Liu, Kamyar Arizzadenesheli, Kaushik Bhattacharya, An- drew Stuart, and Anima Anandkumar. Neural operator: Learning maps between function spaces. arXiv preprint arXiv:2108
wtt::2208.088000 08.888 2021.
Michail Lagoudakis and Ronald Parr. Least-squares policy iteration. The Journal of Machine Learning Research, 4: 107--1444 2003.
Charles A Micchelli and Massimiliano Pontil. On learning vector-valued functions. Neural compu- lation, 17(1):177-204, 2005.
Rémi Munos. Error bounds for approximate policy iteration. In ICML, volume 3, pp. 560-567, 2003.
Rémi Munos. Error bounds for approximate value iteration. In Proceedings of the National Confer- ence on Artificial Intelligence, volume 20, pp. 1006. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2005.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008.
Gergely Neu, Anders Jonsson, and Vicenç Gómez. A unified view of entropy-regularized markov decision processes. arXiv preprint arXiv: 2017.
Bo Pang and Zhong-Ping Jiang. Robust reinforcement learning: A case study in linear quadratic regulation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 9303-9311, 2021.
Martin L Puterman. Markov decision processes. Handbooks in operations research and management science, 2:331-434, 1990.
Jette Randlov and Preben Alstrøm. Learning to drive a bicycle using reinforcement learning and shaping. In Proceedings of the 15th International Conference Machine Learning, pp. 463- 471, 01 1998.
Ayush Sekhari, Christoph Dann, Mehryar Mohri, Yishay Mansour, and Karthik Sridharan. Agnostic reinforcement learning with low-rank mdps and rich observations. Advances in Neural Informa- tion Processing Systems, 34:19033-19044 19045, 2021.
Zhao Song, Ron Parr, and Lawrence Carin. Revisiting the softmax bellman operator: New benefits and new perspective. In International conference on machine learning, pp. 5916-5925. PMLR, 2019.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Samuele Tosatto, Carlo D'Eramo, Joni Pajarinen, Marcello Restelli, and Jan Peters. Exploration driven by an optimistic bellman equation. In 2019 International Joint Conference on Neural Networks (IJCN),, pp. 1-8. IEEE, 2019.
Christopher John Cornish Hellaby Watkins. Learning from delayed rewards. 1989.
11

---

Under review as a conference paper at ICLR 2023
A PROOFS
Proof of the closed-form of the PBO for a finite MDP. over table Q E R N.M
compute the optimal Bellman iteration
(*Q(s,0) = r((,,)) + +yyyg
max max a'EA
=r(8,a) +7 Σ p(s'lss, ())
maay(((s c'Ed
=(R+ R + Pmx o(( (s,
max
(9)
d'EA
where PE R-N-MXN is the transition probability matrix of the environment. From these equations, the operator Q R+ y A Q(:,a') evaluated the objective function from the definition of PBO 2, yields zero error. This means that we have found the PBO in closed-form.
Proof of the closed-form of the PBO for a low-rank MDP. The proof considers continuous un- bounded state action spaces. For Qu Qn, w the vector representing Qw maxae (w, a) well defined (here max might not be attained, it should be interpreted as supremum). We have (s. a)] = (or [w) s (s a)ll ||w||| S ||ll| thus m Qw, a) < cc. Then, we write the optimal Bellman iteration on the function Qw
(s, a(s,a) + +7 +7B max Qw ('
o'EA
ar( + max (p) a)ds
-o(ss,))00) + max(o (a (s)))sss))) from the definition of the transition
probabilities.
(o((s, +7
á ((d) from the linear of the scalar product.
This derivation shows that the operator w ~ 0 +0+ 7 fg. maxa (ar us minimizes the objective function presented in the definition of PBO 2 since its yields zero error. This operator is the PBO for low-rank MDP.
Intuition on the architecture of the parameterized PBO for a low-rank MDP. In the finite case, the PBO is
[7(w) 0 + Σ
max(o (''x(osssd')))))uu d'))w))((s)
s
0
+
max
Σ
(s mess)
x²
(E(......d))
We can see that the most suitable architecture is composition of a linear layer followed by max- pooling and finally last linear layer.
Proof that the PBO is a "ycoontacction-mape mappiin for a low-rank MDP. We now assume that the MDP has latent variable representation. This proof inspired by the proof of the contraction
12

---

Under review as a conference paper at ICLR 2023
property of the Bellman Operator in Bertsekas (2015). Considering w/ E IR we have
([))()) (p(w')ll> - = /. max d')l(w ('))) "do's
1/8 max [')l( ('))
7 max (E
Sy max
max (ar d') w')) (us'), dsss' since sa(-) is positive.
iE (L,,...,,)
Σ Y max
:E(),..,d)
J o'
max
a's'''')sll ,')s w'), (allulss) (ds'' since a(.-) are positive.
jE(I....d)
< max
max
E jE(!....))
ols' (aa))uuss'))sa w| w'lloo
iE( iE()...))
/ ((s'),dd' -|ا - w'llo since (+:.) are probability distributions.
Sy max
jE(
S ,||W - 1100 since p(-)) is probability distribution for all i.
Proof the the closed-form of the PBO for LQR MDP. Let (G, R R the optimal Bellman iteration over Qw is I In (s. a) r(s,a) + max, (u', a'). Before moving forward, we have to make sure this quantity properly defined. The function + Qw(s',
G.G. 8 + 27 . s'a' + M a² is a polynomial of degree 2 in d'. By choosing M < O, we ensure that this function has a unique maximum of equation -1/M s'. This is why the PBO only defined on I² x RT UU R {0} {0). This makes
1 max Qw Qw M
12 M
1
1 (G
GG
12
8
M 82.
M
By putting it in the Bellman equation, we get
12 M
I* = r(s, (G
I
=2 22-$+25
222 sa + R. a² + (G
M - )
-(Q+A'C A I
2 +2
5 AB
)
I2
sa.
12
R+ (R+BaGG- M
aa2
Then, the following operator is the PBO
Q + A2 12
Aa
34
AB
S
+ A(w)
AB
B+ M
R
B
with A(w) G - R/M.
Remarks The PBO can also be understood a geometrical way. It projects the parameters along
line of direction vector [A² AB B²T with an offset IQ S RJ"" The iterations correspond to non-linear transformation of the coefficient in front of the direction vector. This also means that the fixed-point, i.e. the optimal parameters are also this line.
Iff R (0) (0), the result still holds with the convention %/-
13

---

Under review as a conference paper at ICLR 2023
B
DETAILS OF THE BASELINES
Algorithm FQI
Inputs:
Dataset of samples D #Bellman iterations K
#fitting-ster steps H
learning rate
2: Initialize:
wg # weight that give the null Q function
3: for in 1..... K do
4: Compute the target
5: for ($ 0g. 8/) E D do
6: a5) Tj + y max, ( a)
7: end for
8:
9: Minimize the loss starting from the previous weights
Wi W:-1
11:
for in 1
do for batch do
13:
wi - w; A
V (T(s), Qw, (z))
j jEbatch
14: end for
15:
end for
16:
end for
17:
return Wk
Algorithm LSPI
1: Inputs:
Dataset of samples D
#Bellman iterations K
features σ
2: Initialize:
Weights wp that give the null Q function
3: for in 1... K do
4: Critic step: policy improvement
5: for (5) D do
6:
T(/)) = arg max, (s'), w/
7:
end for
8:
9:
Actor step: policy evaluation
10:
A A
b+0
b
12:
for
(s,, (). E D do
13:
A - A A a.) - b + r ( az)
-o((s,
14:
15: end for
Wi - b
17: end for
return Wk
14

---

Under review as a conference paper at ICLR 2023
Table Summary of all parameters used in the experiments.
Chain-walk
LQR
Car-on-hill
Bicycle
horizon
+ +00
+00
100
50.000
0.9
1
0.95
0.99
#D
400(*)
121(+)
5.000
70.000
batch size on D
20
121
500
1.000
K
5(+)
2(*)
9(*)
8
fitting step
400
800
1.200
1 1.200
patience
FQI
starting learning rate
10-2
10-2
10-
10
ending learning rate
10-5
10 10-5
10
10
#W
100
batch size on W
100
training step
400
3.200
4.000
500
fitting step
4
1
15
PBOs
starting learning rate
5 x 10-3
10
10 10-3
10
ending learning rate
10 10-5
10
x 10 6
10
initial weight std
5 x 10
5 x 10 4(a)
x 10
5 x 10
(+) Experimental analysis available for these parameters.
no
To
Q
Wo
Q
22
Behavior of LSPI in the space of all action-value functions for one iteration. The dotted lines are representing projections in the space of action-value functions.
Figure 12:
C ADDITIONAL RESULTS AND DETAILS OF THE EMPIRICAL ANALYSIS
We provide details of the experimental setting. Table summarizes the values of all parameters appearing the experiments. For the additional empirical analysis, only the parameter stake is changed, all the others remain the ones shown in Table 1. FQI and PQI use an Adam opti- mizer (Kingma & Ba, 2015) with a linear annealing learning rate. For FQI, the optimizer reset at each iteration.
C.1 CHAIN-WALK
We consider all the possible state-action pairs 10 times as the initial dataset of samples D. These 10 repetitions help the algorithms to grasp the randomness of the environment. The set of parameters W is generated by taking truncated normal distribution for different seeds. The initial parameters use for the figures is table composed of zeros. The architecture the neural PBO is max- max-pooling layer followed by linear layer. This choice has been made that perfectly tuned parameterized PBO can be mathematically equal to the PBO.
15

---

Under review as a conference paper at ICLR 2023
C.2 LINEAR QUADRATIC REGULATOR
The dynamics of the system is P(s, a) = 0.72s - 0.53a and the reward func- tion is R(s,a)
-0.13s2 + 0.26sa 0.80a². The set D is collected on
mesh of size 11 by 11 on the state-action space going from -4 to 4 in both directions, which means that samples belong to [-4,4] 4]
444 C s A.
The set W is composed of only the initial parameters, i.c., (0, 0, 0). This choice is made because during the optimiza- tion, the optimal Bellman operator might project the param- eters in an area where the coefficients M are positive which would lead the next optimal Bellman iterations to diverge. For PQI and FQI. we use the optimal Bellman operator, meaning that we should compute the maximum over value function. We choose to parameterize the value functions in a quadratic way, thus allowing
PP-Pi= IIV -
10a
10
10-1
Inear P6O; std=l
compute the maximum in closed- form. However, we assume that the algorithms do not have this knowledge since it not the case in more general settings. For this reason, we discretize the action space in a set of 200 actions going from -8 8. The architecture of the neural PBO starts with function + W1 S and is followed by linear layer. Once again, this choice has been made to ensure that the neural PBO can reproduce the behavior of the PBO it is well trained.
Inear PBO; std-5 x
10-
Inear PBO; std=5 10-
PS0
iiteraaions
Figure 13: Performance for initial parameters with different standard deviations.
In the following, we explain how to obtain the metric used in Figure 7a. Then, we demonstrate that lowering the standard deviation of the initial parameters of PBO is important.
Metric. In this setting, the value functions associated to a greedy policy can be computed in closed form. For weight = (G, I, M) E RR2 R UR (0} x {0} such that A BI/M * 1, the value function associated to the greedy policy Tu computed from the value function Qu has the following form, for any 8 E S:
VT~ (s) = Pw s?.
where Pa Q- 287
1-(A 3 Note that G does not influence the result, which is normal since the greedy policy is only influenced by the term linked with the actions.
Proof. Let w (G, M) E R x XR UR x {0} x {0} such that BI/M * 1, the greedy policy of the value function parameterized by w is x² = -1/ar- . where we take the convention %/ = 0. To show the result, we show that the function s + Po s² satisfies the optimal Bellman
Q- 281 R12
equation". We set Pw 1-(A- of j2 and we have
322
vs SsES Pw. $2 - Pw. (s) optimal Bellman equation for the function x r Pw x².
+ Vs Pw 52 = r(s, ग (s)) + Pw "
S, .2 rr(s, M 5) + Pa - B
3)
M 5)2
1
5² + R T2
S, 8 =0Q - 25
+
Pu - B M
M
M2
P. =0 - 25 1 π2
T
R M (A B
M }2
M
P Q 281 + R12
M
(A BI
M
Note that if we multiply s to both side of the assumption A BT/M * 1, we get s' * s where s' is the next state if the greedy policy is followed. This means that we cannot compute the value function of greedy policies that leads to steady states. This is normal since this value function is not defined for all states because the sum of accumulated rewards diverges except in 0 where it is O. O
"This only shows the result up to additive constant, but since ne (0) = 0 then VT~ (0) 0, so this constant is O.
16

---

Under review as a conference paper at ICLR 2023
3.0
200
3.0
2.2
2.2
1.5
150
1.5
0.8
0.8
0.0
100
0.0
-5
0.8
-0.8
1.5
-50
-1.5
-10
2.2
-2.2
3.0
3.0
-0.8
-0.5
-0.2
x 0.0
02
0.3
0.8
1.0
-0.8
-0.5
-0.2
x 0.0
0.2
0.5
0.8
1.0
(a) Sample distribution.
(b) Reward distribution.
Figure 14: Composition of the dataset of samples D on car-on-hill.
We leverage this result state that the distance between the Pw of set of parameters and the solution of the Riccati equation is proportional to the distance between the value function of the greedy policy and the optimal value function.
Proof. Let b E R. We consider the norm-2 over the functions going from[-ba b] For R2 x Ri UR (0) x {0), we have
V
1|2
(V* - Vnu (s)
eEl-b.b)
PP Pully
s4ds
-el-bbbl
b5
P Pol
V
2
The norm of the difference of the value functions proportional the difference P coefficients.
Analysis on the standard deviation of parameterized PBO's initial parameters. Figure 13 shows the distance to the optimal value function for linear PBOs that have been initialized with different standard deviations. The linear PBO initialized with smaller standard deviation shows better perfor- mance. This behavior can be explained by the following two reasons. First, a linear PBO very limited in terms of freedom, meaning that if it is initialized in such way that it goes to the wrong direction, it is very likely that it will stay in the wrong direction during the training; second, by ini- tializing the parameters the parameterized PBO with low value, the operator is already contractive at the beginning of the training. This helps the parameterized PBO to have a stable behavior when evaluating on iterations that were not seen during training.
C.3 CAR-ON-HILL
The goal is to bring a car up a hill. The agent chooses between 2 actions: left or right. The state space is 2-dimensional: position in [-1, and velocity [-3,3], the agent succeeds bring the car the hill at position greater than and velocity in between -3 and 3 - then the reward is 1, if the agent exceeds the state space, the reward 11; otherwise, the reward is O.
As our PQI is an offline algorithm, we need to make sure that all the necessary exploration has been done the dataset of samples. For that reason, we first consider a uniform sampling policy to collect episodes starting from the lowest point in the map ((-0.5, 0)) with an horizon of 100. This sampling process is stopped when 4.500 samples are gathered. To get more samples with positive reward, we sample new episodes starting from a state located between 10.1. 1.3) and [0.5, 0.38) with uniform policy as well. In total, 5.000 samples are collected. The sample and reward distributions over the state space is shown in Figure 14. Inspired by the most suitable architecture for parameterized
17

---

Under review as a conference paper at ICLR 2023
-ill
11 V9
2.2
4-
2.0
3
1.8
1.6
2-
PBO linear
14
P8O deep
12
FQI
10
15
20
25
#lterations
#iterations
(a) Weighted distance between the optimal action- value function and the learned action-value function for every iteration.
(b) Weighted distance between the optimal value function and the learned value functions for every iteration.
Figure 15: Performance with K = 15 on car-on-hill.
PBO, see Appendix A, we set the architecture of the neural PBO with a first block composed of a linear layer followed by rectified linear unit (ReLU) and another linear layer. Then, the first block followed by max- max--oooling before adding a second block that is identical to the first one. The set of parameters W is composed of only the initial parameters, because the complexity of the classes of PBOs used in the experiment is not high. The initial parameters are random except for the last layer that is set zero, ensuring that the associated value function only outputs zeros. To help the training, the value functions are taking actions in { {-1, }} instead of the usual (0, 1}. We also use a low standard deviation for the initial parameters of the PBOs as described in Appendix C.2.
Metric. Ernst et al. (2005) measure the performance of the agents by performing roll-outs starting from different states on a grid of size 17 17. Since the policies, the reward, and the dynamics are deterministic, the discounted reward obtained at the end of the roll-outs corresponds to the value function associated with the policy used during the roll-outs. To compute the optimal value function, they run brute force algorithm that tries every possible sequence of actions until it finds the shortest way to go up hill. our case, the agents do not have all the transitions D corresponding to every starting states of the grid they are using, as shown in Figure 14a. This is why apply mask on the grid to weight the starting states by the number of time a state has been visited in the dataset. Analysis the number of Bellman iterations K. Figure 15 shows that PQI outperforms FQI iteration 15, for K = 15. Similarly to the case K = 9, the linear PBO is too simple to behave well after the training iterations. Once again, the way the loss is shaped allows PQI to outperform FQI.
C.4 BICYCLE
We consider the bicycle problem, as described in Randlov & Alstrøm (1998). The state space is composed of dimensions: (w, ú 0, 0) where is the angle between the floor and the bike, and 0 is the angle between the handle bar and the perpendicular axis to the bike. The goal is to ride bicycle for 500 seconds (50.000 steps). The agent can apply a torque T E 2-2,0 0, 2} to the handle bar to make it rotate. The agent can also move its center of gravity in the direction E {-0.02, 0, 0.02) perpendicular to the bike. As in Lagoudakis & Parr (2003), the agent chooses between applying torque or moving its center of gravity, resulting in 5 actions instead of 9. Usually, a uniform noise in the interval [-0.02, 0.02] is added to d. For the purpose of this work, reduce the number of samples by making the magnitude of the noise 10 times smaller. A reward of -1 is given when the bike falls down, i.e., |w|| > 12". We also use reward shaping have more informative samples, and we add a reward proportional to the change in w, i.c., 10 (1wxl [w)+l)), as in Lagoudakis & Parr (2003). The dataset of samples is composed of 3.500 episodes starting from position close to (0, 0, 0) and cut after 20 steps (Lagoudakis & Parr, 2003). The architecture of the neural PBO the same as the one used in the Car-On-Hill experiment. To evaluate the value functions, we simulate 10 trajectories. We observed only two kinds of outcomes in our experiments: either the policies deteriorate the performance quickly, or they keep it stable, as shown Figure 1lb. This also explains the big confidence interval for deep PBO in Figure la.
18


Reviews:
[{"review_id": "ykepugwhpp", "reviewer": "Reviewer_3oQg", "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": "", "summary_of_the_paper": "This paper proposes to obtain an approximation of the standard Bellman operator, called projected Bellman operator (PBO). Specifically, PBO is a parametric operator on the parameter space of a given value function. Based on the idea of PBO, the authors develop a novel algorithm for value estimation. Experiments demonstrate the effectiveness of the proposed method. ", "summary_of_the_review": "To the best of my knowledge, the idea of obtaining a parametric operator on the parameter space of a given value function is novel. The paper is well organized and easy to follow. However, the experiments can be improved (please see above for details). ", "strength_and_weaknesses": "Strengths:\n\n1.\tTo the best of my knowledge, the idea of obtaining a parametric operator on the parameter space of a given value function is novel. \n\n2.\tThe proposed method is theoretically sound. The authors show how to derive different PBOs according to the class of problems at hand.\n\n3.\tThe paper is well organized and easy to follow.\n\nWeaknesses:\n\n1.\tThe experiments can be improved. It would be more convincing if the authors could evaluate PBO on more challenging continuous control tasks, such as Mujoco [1].\n\n2.\tThe authors may want to provide a detailed discussion on advantages of PBO over the standard Bellman operator. \n\n[1] Todorov et.al \"Mujoco: A physics engine for model-based control.\" international conference on intelligent robots and systems. IEEE, 2012.", "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": "iOc33cAy-m", "reviewer": "Reviewer_emHW", "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": "", "summary_of_the_paper": "The paper proposes learning a parametric model of the Bellman operator, and using this Projected Bellman Operator (PBO) in place of the true Bellman operator to optimize a learned value function. The paper gives examples of PBOs for several settings, and derives an approximate value iteration algorithm based on PBOs. Experiments on several environments are conducted.", "summary_of_the_review": "~~My initial recommendation is to reject the paper due to some of the weaknesses mentioned above. However, I actually quite like the paper and the idea of projected Bellman operators, and feel that the paper is not far from clearing the bar for acceptance; if the authors respond satisfactorily to my concerns, I would recommend acceptance.~~\n\nThe authors have responded satisfactorily to most of my concerns, although I would still like to see a discussion of the weaknesses/limitations of the proposed algorithm. For that reason I'm comfortable recommending the paper be accepted.", "strength_and_weaknesses": "**Strengths:**\n1. Very clearly written. Thank you!\n1. Examples are given when explaining concepts, which is very helpful.\n1. Plots are well-done, large enough to read, and include 95% confidence intervals.\n\n**Potential Weaknesses/Questions:**\n1. The main advantage of learning a PBO as stated in the introduction is that it can be applied an arbitrary number of times without using samples. Applying it repeatedly in this way would require the PBO to be extremely accurate, as any error would be propagated and magnified with each application. However, parametric models are usually biased by the initial values of the model parameters, and therefore are likely to be inaccurate while the parameters are optimized. In addition, asymptotic accuracy is limited by how well the chosen function class can represent the true Bellman operator. For these reasons, it seems like it would be difficult to actually take advantage of the main strength of a PBO in practice, especially on larger/harder problems where the function approximator is not powerful enough, where it's unclear what parameterization is appropriate, or whenever a huge batch of data is not available (such as the usual online setting).\n1. When the PBO parameterization is not suitable, the algorithm can fail completely. This seems like a problem, because knowledge of which parameterization is sufficient for a given environment is not available in general.\n1. ~~How is learning a PBO different from learning a parametric model of the transition and reward functions in model-based RL (e.g. Dyna)? This connection with model-based RL should definitely be discussed in the Related Works section.~~ The authors' comments and the updated version of the paper made it clearer to me that there is no actual model of the environment being used to generate samples in the update.\n1. Experiments are on simple problems with powerful function approximation. How does the method perform on harder problems with weaker function approximation?\n1. The paper does not sufficiently discuss weaknesses of the proposed method.\n1. The paper only presents the parameter settings used in the experiments, but does not mention how these parameters were chosen, what other values were tried, or how different values of parameters change the resulting performance of each method (although this is done for a subset of the parameters). Hence, the experiments seem more like demonstrations than rigorous comparisons between algorithms.\n1. PBO seems to only be specified for the offline batch setting, which is at odds with the usual online sequential RL setting. How could it be used in the online setting?\n1. Learning a PBO requires transition samples, so why would using transition samples to learn a PBO and then using the PBO to learn a parametric value function be better than using the transition samples to learn a value function directly?\n1. ~~What is the vertical dashed black line in the plots?~~ The authors addressed this in their response.\n1. Consider using a colour scheme for the plots that is more friendly to people with colourblindness. Alternatively, the legend could be replaced with labels that point to each line, so that the ability to discern colour is not actually necessary to tell which algorithm corresponds to which line.\n1. The name \"projected Bellman operator\" is very similar to the \"projected Bellman error\" (i.e., the Bellman error with a projection operator) used in gradient TD algorithms, which was a bit confusing. This is an extremely minor point, but it might be good to explicitly clarify the difference.\n\n**References:**\n- Sutton, R. S., Szepesvári, C., Geramifard, A., & Bowling, M. (2008, July). Dyna-style planning with linear function approximation and prioritized sweeping. In Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (pp. 528-536).", "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": "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": "YFuV_XMsjAX", "reviewer": "Reviewer_Kjbj", "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": "", "summary_of_the_paper": "This paper proposes the projected Bellman operator (PBO), an operator on the parameter space of the value function, for value-based reinforcement learning. The paper argues that PBO can approximate repeated applications of Bellman operator at once. To show the advantage of this, the paper considers three example of applying PBO, including tabular MDP, low-rank MDP and LQR, where the convergence and approximation error of PBO are provided. Finally, the paper also provides empirical studies in simple synthetic environments. \n", "summary_of_the_review": "I recommend rejecting this paper as the contribution of the proposed method is not clear to me. \n", "strength_and_weaknesses": "Strength \n\nThe paper considers a new paradigm for value-based RL, which could be potentially interesting for both theoretical and practical applications. Other than some notational ambiguity, the paper is well written. I also like that the authors give some specific examples of the proposed general operator. \n\nWeakness \n\nThe major weakness of this paper is that the significance of the contributions is not clear to me. \n\nSince the main contribution is PBO, the key to decide if the contribution is significant enough is to understand if this new operator can bring some new findings from either empirical or theoretical perspective. However this is not clear to me as explained in details below. Please correct me if I missed anything important in the rebuttal. \n\n \n1. The so called PBO, defined in Equations 3 and 4, is defined as the solution of solving a single step of fitted value iteration for a general parameterized function class. But I believe this operator has already been considered in the literature. For example, [1] defines it in a similar way, and analyze FVI with this operator in a batch setting. \n\n2. The authors claim that “our PBO can approximate repeated applications of the true Bellman operator at once, as opposed to the sequential nature of the standard Bellman operator”. This is what motivates the learning objective 13. However, to avoid a sequential implementation when computing $T_\\phi^k$, doesn’t it need the assumption that the operator is linear, or at least can be written as a closed form? I believe this is definitely not true for general non-linear function approximation. \n\n3. The authors consider three cases as examples of PBO and gives convergence analysis for all three examples. However, it seems that all these results are already known? For example, a more general case of tabular MDP (Section 4.2) is under the assumption of linear function approximation (as one-hot feature is linear), in which case similar results have been provided in [2]. \n\n4. Some notations might not be well defined. For example, What is F in Theorem 1? What is $\\Pi$ in Equation 6? Equation 13: there is no (s,a). \n\n\n\n[1] Chen, J. and Jiang, N., 2019, May. Information-theoretic considerations in batch reinforcement learning. In International Conference on Machine Learning (pp. 1042-1051). PMLR. \n\n[2] Parr, R., Li, L., Taylor, G., Painter-Wakefield, C. and Littman, M.L., 2008, July. An analysis of linear models, linear value-function approximation, and feature selection for reinforcement learning. In Proceedings of the 25th international conference on Machine learning (pp. 752-759).\n", "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": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "TtuI03odUo", "reviewer": "Reviewer_bapX", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The author has discussed the problem of transition samples in the bellman operator, which determine the operator's behavior. The author has proposed a novel idea of approximation of the Bellman operator known as the Projected Bellman Operator (PBO). Given the value function's parameter, PBO outputs the new value function's parameter. PBO is a parametric operator on the parameter space of the given value function. Finally, the author has analyzed PBO in terms of stability, convergence, and approximation error on different problems. The author claims that the PBO method overcomes the classical methods' limitations.", "summary_of_the_review": "The overall writing quality is ok, and the proposed method is simple and beneficial. However, the experiment comparison lacks justification, and the technical contribution is plain.", "strength_and_weaknesses": "Strength:\n\n  The paper discusses an essential problem in the literature.\n\n  Also, the author provides a nice solution to tackle the problem, but the analysis and intuition part is very poorly represented in this paper.\n\nWeaknesses:\n\n\" first to deal with the original problem of operator learning in RL.\"\nI don't think this statement is correct. Please refer [R1] and BBO(Fellows et al., 2021) from the paper.\n\nThe author should compare the results of other Bellman operators like the Bayesian Bellman operation. It would be nice to observe the performance of the PBO with other Bellman operators' methods.\n\nIt is not clear in the paper how the parameter approximation is formulated in function space (Operator learning space). Which function approximation method is used in PBO? How does it work in the operation space? The author should add a paragraph on function approximation in the literature.\n\nThe author should show the parameter distribution of V before the approximation and after the approximation. \n\nHow does the quality of the sample improve in PBO techniques? The author should show results both qualitatively and quantitatively. \n\nHow about the direction of the update by the current sample? The decision is taken by a single instance or batch of samples.\n\nThe author should report ablation analysis on various parameter approximation methods.\n\nThe experiment section is not represented properly. The author should report stability results to compare with another method. Also should report the approximation error results.\n\nReference:\nR1. Song, Zhao, Ron Parr, and Lawrence Carin. \"Revisiting the softmax bellman operator: New benefits and new perspective.\" In International conference on machine learning, pp. 5916-5925. PMLR, 2019.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject