Multi-Bellman operator for convergence of $Q$-learning with linear function approximation
Authors: Diogo S. Carvalho
Pedro A. Santos
Francisco S. Melo
Venue: Accepted by TMLR ()

Abstract: We investigate the convergence of $Q$-learning with linear function approximation and introduce the multi-Bellman operator, an extension of the traditional Bellman operator. By analyzing the properties of this operator, we identify conditions under which the projected multi-Bellman operator becomes a contraction, yielding stronger fixed-point guarantees compared to the original Bellman operator. Building on these insights, we propose the multi-$Q$-learning algorithm, which achieves convergence and approximates the optimal solution with arbitrary precision. This contrasts with traditional $Q$-learning, which lacks such convergence guarantees. Finally, we empirically validate our theoretical results.

Published in Transactions on Machine Learning Research (04/2025)
Multi-Bellman operator for convergence of Q-learning with linear function approximation
Diogo S. Carvalho
diogo. http:os..ccraaooooteeeooooo...e ulissoo.
INESC-ID
Instituto Superior Técnico, University of Lisbon
Pedro A. Santos
pedro. iat.lloss@tccccc.....iiiee
INESC-ID
Instituto Superior Técnico, University of Lisbon
Francisco S. Melo
fmelo Binesc-id.pl
INESC-ID
Instituto Superior Técnico, University of Lisbon
Reviewed on OpenReview: https: // openreviee. net/ forun? id- D2PyEPGXgh
Abstract
We investigate the convergence of Q-learning with linear function approximation and in- troduce the multi-Bellman operator, an extension of the traditional Bellman operator. By analyzing the propertics of this operator, we identify conditions under which the projected multi-Bellman operator becomes contraction, yielding stronger fixed-point guarantees com- pared to the original Bellman operator. Building these insights, propose the multi-Q Q- learning algorithm, which achieves convergence and approximates the optimal solution with arbitrary precision. This contrasts with traditional Q-learning, which lacks such convergence guaranlees. Finally, we empirically validate our theoretical results.
1 Introduction
Reinforcement learning aims approximale the value of performing different actions in different stales, considering the expected sum of time-discounted rewards in Markovian environment. The importance of this task cannot be overstated, by selecting the action with the highest value in given state (Puterman 2005). The value function also facilitates environment evaluation and enables comparisons between different environments. If we can store the value of performing each action on each state individually, the Q-learning algorithm converges to the correct value function (Watkins & Dayan 1992 When is not possible to store values, for example when there are too many states, Q-learning can be combined with function approximation (Melo & Ribeiro 2007
accurate value function allows agent to make optimal decisions
Unfortunately, the combination of Q-learning and function approximation is troublesome, and even when the function approximation space is linear, the algorithm diverge (Sutton & Barto 2018). In fact, the approximation problem that Q-learning addresses does not have, in general, solution (Melo al. 2008 To address this limitation, we proposc an alternative problem and algorithm that effectively solve linear function approximation in reinforcement learning, unlike Q-learning. The problem and algorithm proposed are extensions of the original. To our ends, we start by introducing the multi- Bellman operator, and identify the conditions under which its projection into the function approximation space contractive. Leveraging operator, we propose the multi Q-learning algorithm, and
the contractivity property of the demonstrate its convergence to arbitrarily good solutions, both theoretically and empirically.

---

Published in Transactions on Machine Learning Research (04/2025)
2 Background
A Markov decision problem (MDP) is a tuple (A, p,r,7), 7), where X' is discrete set of states, A is finite set of actions, P is a set of distributions over X' for each state and action, r X' x A + [0, 1] is a reward function, and y is a real (0,1) called the discount factor (Puterman, 2005). A policy is a function w : X - A (A), mapping states to distributions over A, and its value is the function fr X that
such
2x (I, a) = E Σ Y'r no x. 00 o.
(1)
where the expectation with respect to trajectories of the MDP, namely rewards ra and states 2++1 that are obtained by performing action o, on stale Wi, with actions or that selected according lo at every L. There is at least policy x² that maximizes the value 9 every state and action [Puterman 2005 and we refer to its value as q². The value qº satisfies the Bellman fixed-point equation given by
9" =- -
(2)
where H is the Bellman operator, such that
(Hq) = E r a) + y m (x', (d',a))
(3)
d'EA"
where the expectation is with respect to the next state x' obtained by performing action state
2.1 Function Approximation
Our goal is to approximate q² In other words, we want to find good parameterized representation of the value of an optimal policy for given MDP, given a function approxination space H (hw 2 - R, E R$). Let us consider that every ho E H is differentiable in random z taking values in 2, and the loss I(w) = 2 || - hwll? where we consider the μ-norm such that ||a]]2 E,, [?](= To approximate h is to find an element in the set Proj h H such that
function h Z + R, distribution over a
Proj h = arg min I(w).
(4)
hww EH
Any w parameterizing a ha Proj must be a critical point and thus verify
Vallw) O.
(5)
Linear function approximation Given features Φ : 2 - RR lincar function approximation space is given by the functions such that h=) = (=)w. In this case, the gradient of the loss function is given by
Vul(w) = E. (0()) (h(2) (z)))
(6)
Solving for Vul(w)= 0, we obtain that
w = (0(2)) (2)] E. (o(=)h(z))
(7)
Thus, if the inverted matrix above exists, the set Proj h has a single element and can refer to both wwo. The solution wf is also the equilibrium of the dynamical system
(8)
and the limit of the sequence of we obtained by performing discretized update with 2, i.i.d from
Wh+1 = Wt + au jo (zx) (h(zz) - hw, (2))),
(9)
with a small positive real called the learning rate.
2

---

Published in Transactions on Machine Learning Research (04/2025)
Stochastic approximation
Without access to h, stochastic approximation performs the update
wh+1 = wi + au (z)) (Tr - Aw, (z+))l,
(10)
with Tr possibly wy-dependent estimate h (z+) called the target. If there exists an equilibrium wf for the dynamical system
Ep (zx) (T. (=)))),,
(11)
and it globally asymptotically stable, well-cstablished conditions guarantce the stochastic approximation update converges w" [Borkar, 2008).
2.2 Q-learning with Linear Function Approximation
We focus now on the reinforcement learning sctting and consider 2 A' x A, and an approximation space of linearly parameterized functions qu A such that
I (z, a) x" (2r, a)w.
(12)
In reinforcement learning, we want to approximate the value q", by computing w' that satisfies
-u Projq".
(13)
Without knowledge of q", we are unable to perform the exact stochastic approximation update,
Wh41 wi + on j (rr, ae) (4" (It, a+) que (Ie, 0t))]-
(14)
Leveraging the fact that 6- = Hq", Q-learning performs instead the stochastic approximation update
Wi+1 = We + a 16 (Ie, as) (Te qw, (24, a:))].
(15)
where the target is sample for (Hqw,) (z), i.e.
= r2 + max Twn a') d'EA
(16)
Since the target is not differentiated, despite possibly depending on w/, Sutton & Barto (2018) calls these semi-gradient methods. An equilibrium for Q-learning with linear function approximation must. be the fixed-point for the projected Bellman operator, thus verifying the fixed-point equation
a = Proj (Hq.).
(17)
Unfortunately, since the Projected Bellman operator is not generally a contraction, the fixed-point may not exist and, even when it does, the solution may not be an equilibrium of the associated dynamical system
E (o (Ir, az) (7. (Fs,
(18)
Consequently, Q-learning with linear function approximation can diverge, failing to provide any stable so- lution. The divergence of Q-learning is evidenced in classic counter-examples where the parameters of the approximator do not approach any solution, either oscillating within window [Boyan & Moorc. 1995 Gor-
don 2001) or growing without bound (Tsitsiklis & Van Roy 1996: Baird 1995). Currently, the theorelical results that establish convergence Q-learning restrict the data or the features too much (Szepesvári &
Smart 2004 Melo al. 2008), and the proposed variants of Q-lcarning that are guarantoed to converge
under more general conditions (Carvalho et al., 2220 [Zhang et al. 2021 Lim et al. (202)) converge fundamentally biased limit solutions that do not. hold good performance guarantees (Chen al. 2023
3

---

Published in Transactions on Machine Learning Research (04/2025)
3 Multi-Bellman Operator
Let us define the multi-Bellman operator H such that
H Hq
(19)
and
H q H
(20)
Since 4- Hq" it also holds that, for every in N.
T' -H
(21)
Proposition 3.1. The operator H is a contraction in the co-norm with contraction factor y"'
Proof. See the proof of B.1oo the appendix.
While unsurprising, the result has profound implications on the use of linear function approximation. Assumption 3.2. The features and data are such that the matrix E, [0(2, a)ø² (x, a)] is invertible. Theorem 3.3. There erists N E N such that, for all n 2 N, the operator Proj H is a contraction in the Xc-nom..
Proof. See the proof of B.2 the appendix.
Corollary 3.4. There exists N N such that, for all n 2 N, there exists a unique solution W to the fued-pponnt equation
qu Proj(H"
(22)
The result states that, while the projected Bellman operator may not be contractive, the projected multi- Bellman operator is guaranteed to be contractive for sufficiently large n. Consequently, whereas the fixed- point equation the projected Bellman operator may fail to have a solution, the fixed-point equation of the projected aulti-Bellman operator is guaranteed to have a unique solution.
While the previous result establishes existence and uniqueness of solution, it says nothing about the quality of such solution in light of the reinforcement learning objective. Now, compare qan with the optimal solution.
Assumption 3.5. For all e N, (x,, a.) is ii.d from μ.. Theorem 3.6. For all 2 N, the solution W is such that
11g" qan 2ool S 1 2am l1q" qu- 1lc
(23)
where x = max
02 maxx with dmax max [, a)ll2 and T Ep alo (x,
Proof. See the proof of B.3 of the appendix.
Corollary 3.7. The sequence of (Whn is such that
lim ||l0 n
- 20 1=
(24)
The results state that the solution Ga can be made arbitrarily close to the optimal solution qur, and can therefore provide an optimal approximation q" in a given function approximation space. In the following, design stochastic approximation algorithm that aims to approximate "".

---

Published in Transactions on Machine Learning Research (04/2025)
4 Multi Q-learning
For given n E N, to approximate the solution of
Yu Proj(H"aga)
(25)
propose to perform the multi Q- Q-learning update
W++1 We + a [0(x,, az)
(T) (T: que (e)),
(26)
where the target r."." p (x,, 04) is sample for (H" qui) (xt, at) defined recursively as:
7 (Ze, at) = rz 7 max qur (2 a')
(27)
and
m (tt,,(a,, (21, = rr. + max a'
m
Ti
(1)a))
(28)
m
where "," (z) are ii.. 7"." (x/, a') and are used to build an average with m samples.
At time step t, instead of building a 1-step greody target, multi Q-lcarning builds a target that obtained by trying, on every state encountered along n-step trajectory starting z/y every action m times, and maximizing the average of the sum of the discounted rewards at each level. We assume access to fixed replay buffer D, from which state-action pairs sampled, and a simulator to sample transitions. Our algorithm is most similar to the one of Kearns et al. (2002). In our case, in addition to off-policy learning, we have function approximation and bootstrapping Our algorithm is also similar to the one of Rosenberg el al. (023), but with off-policy learning and function approximation. More generally, our n-step updates differ from the usual in that they are policy-independent,, which as we will see allows our updates to approximate the multi Bellman operator accurately. Moreover, our setting introduces additional technical challenges due to maximization at each step and each level, which does not usually appear in the related works and lead to biased updates and solution if not properly handled. We provide pseudo-code of Multi Q-learning in Algorithm 1 which calls function that builds the target for the update defined in Algorithm 2
Algorithm Multi Q-learning
Initialize weight vector we Given a fixed replay buffer D containing state-action pairs (8t, ae) Access to a simulator that returns (re, s/) given (st, a.)
For each training iteration:
Sample a random state-action pair (st, az) from D
Simulate reward r, and next state sf by calling the simulator with (st, az)
Call build target to compute the target:
n.m (st, a.) build target(n, m, st, ar wi)
Update weights:
Wi+1 wi + [o(s,, ar) (7" a.) qwo (St, a+))
4.1 Convergence
Contrary the case of Q-learning, there is solution to the dynamical system of the multi Q-learning update.
5

---

Published in Transactions on Machine Learning Research (04/2025)
Algorithm 2 build target function
Input: parameters n, m, state 8, action a, weight vector w
Output: Target
Simulate reward Ts,a and next state s' by calling the simulator with (s,
If n=
Compute the target:
Fx,a + y max qa'x
a'EA
Else:
For each i= 1...m
Recursively obtain sample: T. (s' = build target(n - 1, m. 8 a',
Compute the target:
n-1. (s (s',a'
T Tsa + y max
e'EA
Return
Proposition 4.1. There erists N E N such that, for all 2 N, there crists equilibrium wm. for the dynamical system
à E (o(x, (f (z, (c(2)))))
(29)
Proof.
See the proof of C.1 of the appendix.
We show that multi Q-lcarning converges the solution.
Assumption 4.2. The sequence of learning rates fatheN satisfies Eis ag =0 and Ei= at < co.
Theorem 4.3. There erists N E N such that, for all 2 N and m E N, the sequence of twiHIE is such that
lim 10mm
will =0
(30)
Proof. See the proof of C.2 of the appendix.
The result establishes conditions under which multi Q-learning converges to aan.m. The assumptions are commonplace (Tsitsiklis & Van Roy 1996 Carvalho et al. 2020 Melo al. 2008). Assumptions 3.2 and 4.2 are mild. Assumption 3.5 is the most restrictive of the three, as it requires the data distribution to have shift during training. Same as the other authors, we use the assumption to facilitate our technical analysis of the convergence of Q-lcarning, which still fails in this benign setting. Nevertheless, the replay buffor can slow down the data distribution shift arbitrarily much. In the limit, the case offline reinforcement learning, the distribution is indeed fixed and samples are i.i.d.. We do believe our result can be extended to the case where the data distribution converges.
4.2 Performance
Unfortunately, in general, fan.m does not equal qon. Specifically, when the environment is not deterministic, the target of multi Q-learning is biased, due to the difficulty in estimating the maximum of an expectation. In fact, it impossible to estimate the expectation of the maximum without bias (Van Hasselt 2013). We show, however, that the number m of samples per action grows, regardless of the randomness of the environment, the solution of multi Q-learning converges to the unbiased solution gan.

---

Published in Transactions on Machine Learning Research (04/2025)
1041
30
2010
2011
12
3020
20200
(a) - 2w.
(b) Star.
Figure Classic counter-examples. The y-axis shows the difference between the estimated and q- both examples, Q-learning, that multi Q-learning with n 1, diverges but, for sufficiently large n, multi Q-learning converges.
Theorem 4.4. For all 2 N and E N, have that
&
max var nmmm
119a - Jan.m 11 S 1 Arm
(31)
mm
with { V 1-7
Proof. See the proof of C.S the appendix.
The results states that, for each n, when m increases, the solution of multi Q-learning Jan. approaches the fixed-point the projected Multi Bellman operator qam. On the other hand, states that, for each m, when n increases, the distance between the two can grow, but bounded, since we also have that /var (7m-1.m) - for all and m.
Corollary 4.5. The sequence of [@m.m) Iee is such that
lim 10" a 0.
(32)
From Corollary 3.7 we also knew that, as grows, the fixed-point of the projected Multi-Bellman operator Oan approaches the optimal solution q Putting the two results together, we conclude that, increasing n and m, the solution of multi Q-learning becomes arbitrarily close to ga*.
5 Experiments
In this section, we validate our theoretical findings. We start by focusing on the convergence property of multi Q-learning. All results are averages of five runs with standard deviations. Given the linear function approximation setting and relatively small scale of the environments, experiments can performed on standard commercial CPUs, with small memory costs, and lasting less than eight hours.
5.1 Convergence
We show that, on well-known problems where Q-learning with linear function approximation fails to converge, multi Q-lcarning converges is sufficiently large, as predicted in Theorem 4.3] We start by using two classical problems that are typically used in the literature exhibit the divergence of Q-learning with linear function approximation. The first problem was introduced by Tsitsiklis & Van Roy (1996) and the second

---

Published in Transactions on Machine Learning Research (04/2025)
problem by Baird 1995 Even though both problems are relatively simple and even though the correct solution q¹ is within the function approximation space, the parameters of Q-learning diverge to infinity in some conditions. Additionally, we introduce another simple example, which we call the Bias example. This example serves as a complement to the first examples by showcasing the bias that can appear in multi Q-learning, as predicted in 4.4 and how we can minimize it.
w + 2w The w + 2w problem due to Tsitsiklis & Van Roy (1996). The MDP has two states 1/1 and 12 and only one action by Performing the action on any of the two states always takes the agent to the second state. The reward received always zero. Therefore, q" is zero. The features o X A + such that @(11, b1) and 6(22, b1) 2. We consider discount factor of 0.9, which is within the interval where Q-learning is originally reported to diverge, and a learning rale of 10-1, and uniform data distribution. Figure 2 depicts the problem.
2n
Figure 2: Transition diagram of the process in the w + 2w problem.
Star The Star problem is due to Baird 1995). The MDP has seven states y1 to and two actions b and b2. The first action always takes the agent to the last state, the second action takes the agent to any of the first five states uniformll. The reward received is always zero. Therefore, q² is zero. The features are Φ: : X' x A- + l6 such that, for between and 7, for all i between 1 and 16 dz 62) = 1(i j + 1), for between 2 and 7 (1); b1) 2 1ii j + 1), for j between 1 and 6 Φ0 (11,,1)) = 1 I 6) and Φ1 (17, b1) 2, or(y,, b1) 0 otherwise. We consider discount factor of 0.98, within the interval at which Q-learning diverges, learning rate of 10-2, and data distribution that samples the first action one seventh of the times and the second action six sevenths of the times. Figure 3 depicts the problem.
Bag
Jusy tole
Duly
Juiy
Bug
Figure 3: Transition diagram of the process in the Star problem.
recovers the original Q-learning. We use m = The experimental results in Figure [ validate theoretical finding that, whereas the projected Bellman operator may fail to have fixed-point and Q-learning may diverge, multi Q-learning converges for large enough n, as predicted by Theorem 4.3 to the correct solution g" =.
We test multi Q-learning for n (1,2,4). We note that
Bias In some non-deterministic enviromments that are not reward-free, the solution of multi-Q-learning may not equal the projected multi-Bellmann operator, resulting in a bias that increases with n. To highlight this behavior, we introduce the Bias example. The Bias example intentionally simple, consisting of only two states and two actions with uniformly random transitions. One state provides a reward of 1, while the other provides O. This example serves two key purposes. First, it serves to illustrate the potential bias in
8

---

Published in Transactions on Machine Learning Research (04/2025)
multi Q-learning when 1. As shown in prior work (Van Hasselt 2013), it is generally impossible to estimate the maximum of a set of expected values of random variables without introducing bias. In our case, for fixed n and m, multi Q-learning can converge to a biased solution of the equation q = Proj(HH"g, and this bias increases with n. This phenomenon aligns with the predictions of our theorctical results (Theorem 4.4). Second, the Bias problem serves to demonstrate how increasing the parameter m effectively reduces the bias. Our theoretical results (Corollary 4.5) suggest that increasing m-the number of samples used construct the update target reduces this bias. The example provides controlled setting to validate this claim.
W1
W2
Figure 4: Transition diagram of the process in the Bias problem.
We use tabular features, with a discount factor of 0.9 and learning rate of 0.1. Figure shows the transition diagram for the Bias problem. The results in Figure 5a confirm that, for m = 1, the bias increases n increases. In contrast, Figure 5b shows that, as m increases, the bias decreases, aliguing with the theoretical
predictions in Corollary 4.5
5.2 Performance
We also validate that, as n increases, the distance between the fixed-point of the projected Bellman operator and qu decreases, as predicted by Corollary 3.7 We use an e-greedy policy where decays linearly from 100% to 5% during the first half of interactions and remains constant afterwards. We use a replay buffer with 20% of the total number of timesteps used for the environment. We plot a moving average of the last 5% of the total number of time steps. We use classic deterministic environments, which we describe.
where joint actuates two links such that one end is fixed and the other is free. The actions of the agent are to apply negative torque to the joint, apply a positive torque to the joint or do nothing. The state space is the tuple composed of sine, cosine and angular velocity of each link. The reward is always minus one unless the free end of the links reaches a target height, after which the agent reaches a terminal state. We discretize each dimension of the state space in four and use gaussian features. We discount factor of 0.99 and a learning rate of 3 10-3
Acrobot Acrobot is classic control problem proposed by Sutton 1995
Cartpole Cartpole is classic control problem proposed by Barto et al. 1983). where a cart balances a pole. The actions of the agent are to push the cart left right. The state space is tuple with the position and velocity of the cart and the angle and angular velocity of the pole. The reward is always unless the pole falls and the agent reaches terminal state. We discretize each dimension of the state space in two and use gaussian features. We use discount factor of 0.99 and a learning rate of 3 10
The results in Figure 0 validate the finding that as n increases, the solution of multi Q-lcarning improves, as predicted by Corollary 3.7
Altogether, our experimental results confirm that, contrary to the original Q-learning, multi Q-learning converges for sufficiently large n, that the distance between the projected multi-Bellman operator and the optimal Proj q" decreases with n, and that the distance between the solution of multi Q-learning and the fixed-point of the projected multi- Bellman operator decreases with m.
6 Related Work
We analyze work related our own, both with respect to the problem of Q-learning with linear function approximation and our proposed multi Q-learning solution.
9

---

Published in Transactions on Machine Learning Research (04/2025)
2.0
-2
33
400
800
(a) The bias increases with nL
(b) The bias decreases with m.
Figure 5: Bias problem.
Acrobot-v1
CartPole-v1
-100
-20
-000
120000 200300 300000 400500 S00002 602020 750000 800200 num CheRosminnE Steaa
25000 50000 75005 200000 125000 1:0000 175000 200000 number sniiormont staps
(a) Acrobot
(b) Cartpole.
Figure 6: Classic control. The y-axis shows the average return. The performance increases with
Convergence conditions Around the time the divergence of Q-learning was established, some works aimed at reaching conditions under which Q-learning would converge. The first works proposed restrictions of the function approximation spaces themselves. They establish that with some specific choices of fea- tures, Q-learning is guaranteed lo converge (Singh et al. 1994 Ormoneit & Sen 2002 Szepesvári & Smart, 2004). The linear architectures considered across the three works are extensions of what would be the one- hot representation in the tabular case. Afterwards, another work considered again general lincar function approximation architectures. Melo et al. (2008) prove that Q-learning with linear function approximation converges if the distribution state-action pairs the agent uses learn sufficiently close to the distribution that the optimal policy induces.
Gradient-TD methods Instead of finding conditions under which Q-learning converges, a different line of works proposes to take a step back and modify the objective that Q-learning is trying to solve. Maci ett al. (010)) propose to perform full-gradient descent on a different objective, called the projected Bellman gradient- methods. Being full gradient method, Greedy-GQ provably convergent to minimum in the approximation space. However, the method can converge to local minima and there is no guarantee that the resulting greedy policy is good control policy
error. The resulting algorithm, called Greody-GQ,
[Scherrer] 2010 Gradient-TD is also less efficient than semi-gradient methods (Mahadevan et al. 2014 Du
ct al. 2017
The problem of divergence of Q-learning with function approximation was signif- icantly revived after empirical success story of Q-learning with deep neural networks (Mnih et al. 2015
Regularized methods
10

---

Published in Transactions on Machine Learning Research (04/2025)
One of the components of the renowned deep Q-network (DQN) therein is a target network that aims compensating the instability generated by the Q-learning updates. While the DQN is not provably conver- gent, its empirical success inspired theoretical results. The works of Carvalho et al. (2020). Zhang et al.
(2021) and Chen et al. (2023) provided convergence guarantces for variants with target networks. Addition- ally, another work points out that the larget network can be seen as a regularizer (Piché et al.
2021 3. As
hinted by [aaahhmand] (2011), several works prove that various forms of regularization of the Q-values or the parameters themselves can stabilize Q-learning, resulting in a convergent algorithms (Zhang et al. 2021 Lim et al. 2022 Agarwal et al. 2021 However, the introduction of the regularizers biases the solution obtained, even in deterministic environments. Contrarily, the bias of our method only appears in non-deterministic environments and can be minimized arbitrarily much.
Non-linear function approximation The behaviour of Q-lcarning with lincar function approximation has been the focus of several theoretical works. In practice, however, Q-learning is mostly used with non- linear function approximation, especially through neural networks (Miih et al.) 2015). Still, there are works that address this more general setting. A recent work suggests loss function that is decreasing over time, assuming the neural network converges to target network at each step (Wang & Ueda] 2021). However, having a loss function that is monotonically decreasing does not imply that neither the parameters of the approximator are converging nor that the Q-values are converging. Cai et al. (2019) and Xu & Gu (2020) provide finite-time analysis of Q-learning with over-parameterizen neural networks that convergence happens only as the size of the network grows to infinity, which is an impractical scenario.
Lookahead In the context of policy iteration, several works hinted at the thcoretical benefits of lookahcad in the tabular case (De Asis et al. 2018; Efroni et al. (2018a). Efroni et al. (2018b) then identified a problem with soft policy improvement for lookahead policies, which happens if function approximation is used. Specifically, contrarily to what happens with a single-step policy improvement step, a multistep policy improvement step is not necessarily monotonically increasing. However, Efroni et al. (2020) and Winnicki & Srikant (2022) respectively provide finite-time and asymplotic results for lookahead in approximate policy iteration. Rosenberg et al. (2023) proposes interesting policy- based algorithm with adaptive depth that results in convergence in the tabular case. We focus on the problem of divergence of Q-learning, a value- based algorithm, when used with linear function approximation archilectures; the projected multi-Bellman operator that we introduced differs in that it is designed for evaluating the optimal policy. [Chen et al.) (2022) also analyze an operator similar to our proposed Belli-Bellman operator in the context of off-policy prediction in an actor-critic sctting with linear function approximation, leveraging the improved fixed-point guarantees. Due to the maximization that appears on the Bellman operator for control, in our case we lose the property of linearity and, since maximization and an expectation do not, in general, commute, the Q-lcarning setting is more challenging and the algorithm we propose is significantly different.
Planning and mosel-based reinforcement learning Multi-step real time dynamic programming algo- rithms, as defined by Efroni et al. (2018b) and discussed by Moerland et al. (2020),
integrate planning and learning and have several successful practical applications (iiver al. 2017 2018 We refer to the survey Mocrland et al. (2023) for varied algorithms that include ((a) (De Asis et al. 2018 tree-backup (Precup 2000) and multi-step expected SARSA (Sutton & Barto 2018). While most such algorithms are policy-based and on-policy, with separate value and policy and behavior-dependent solutions, we have an off-policy, value- based algorithm, which plans exclusively at training time multi Q-ccarning Our fixed depth and full breadth
setting are under-explored [Moerland et al. 2023
7 Conclusion
Our work has made significant contributions to addressing the convergence challenge in Q-learning with lin- ear function approximation. By introducing the multi-Bellman operator and demonstrating its contractive nature, we have paved the way for improved convergence propertics. The proposed multi Q-learning algo- rithm effectively approximates the fixed-point solution of the projected we have shown that the algorithm converges under relatively mild conditions.
operator. Importantly,
11

---

Published in Transactions on Machine Learning Research (04/2025)
7.1 Limitations and Future Work
Even though our algorithm can be combined with models that are learned concurrently to the reinforcement learning update to simulate the environment, in our experiments, we used a given simulator of the environ- ment. It is not the case that such simulator is always available in applications. There are several tochniques for learning a model of the environment. For example, we can learn the model previously or concurrently to reinforcement learning; the model can be exact or inexact; the model can be parametric or non-parametric. Multi Q-learning can be combined with any of the mentioned model-based approaches to remove the need for simulator when it is not available.
Multi Q-learning also performs every action on every reached state while building the target. Thus, the computational complexity is exponential on the depth n. In case only some actions are performed on each state, we cannot show convergence to an optimal solution. Nevertheless, in some cases, the computational benefits of not performing every action on every state may outweigh the theoretical comfort. An analysis of this trade-off would be valuable. Future work should also analyze techniques to prune the set of actions sampled at each level of multi Q-learning and reduce the complexity of the algorithm.
It would also be interesting to analyze multi Q-learning with non-linear function approximation, both the- orctically and empirically. Specifically, under which conditions and function approximation architectures would our convergence result still hold? How would multi Q-learning with non-linear function approxima- tion compare, in practice, with relevant policy-free reinforcement learning algorithms such as the DQN (Mnih et al. 2015)? And will the target
multi-Q-learning if combined with the target network, increase the performance of the DQN? Finally, it would be interesting to see our method applied to real-world problems where the environment, namely the transitions and rewards, can be simulated, including the training of large language models (LLMs).
Acknowledgments
This work was partially supported by the Portuguese Fundação para Ciência e a Tecnologia (FCT) un- der INESC-ID multi-annual funding (LDDD//50//////// RELEvaNT /B00//CCCCOM/500////00 Ws- MART ROUTE+ 011.220481..PPD... and CRAI (C628696807-00454112 (IAPMEI/PRR). Diogo S. Car- valho acknowledges his FCT PhD grant (2020.05360.BD)
References
Naman Agarwal, Syomantak Chaudhuri, Prateek Jain, Dheeraj Nagaraj, and Praneeth Netrapalli. Online target Q-learning with reverse experience replay: Efficiently finding the optimal policy for linear MDPs, arXiv preprint arXim:2110.08444 2021.
Terje Aven. Upper (lower) bounds on the mean of the maximum (minimum) of a number of random variables.
Journal of applied probability, 22(3):723-72) 1985.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Proceedings of the 12th International Conference on Machine Learning, pp. 30-37, 1995.
Andrew G. Barto, Richard S. Sutton, and Charles W. Anderson. Neuronlike adaptive elements that can solve difficult learning control problems. IEFE Transactions on Systems, Man, and Cybernetics, SMC-13 (5):834 846, 1983. doi: 10.1109/TSMC..199 190.MM....93.1113000
Vivek Borkar Stochastic Approrimation: A Dynamicul Systems Viewpoint. Cambridge University Press, 2008.
Justin A. Boyan and Andrew W. Moore. Generalization in reinforcement learning: Safely approximating the value function. In Advances in Newral Information Processing Systems 7, pp. 369 376, 1995.
Qi Cai, Zhuoran Yang, Jason D. Lec, and Zhaoran Wang. Neural deffpral-difference learn- ing converges to global optima. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, F. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, vol-
12

---

Published in Transactions on Machine Learning Research (04/2025)
ume 32. Curran Associates, Inc., 2019. URL http:://ppoeeenng..norrs..c/ccep Paper Pa
Diogo S. Carvalho, Francisco S. Melo, and Pedro A. Santos. A new convergent variant of Q-learning with linear function approximation. Advances in Neural Information Processing Systems, 33, 2020.
Zaiwei Chen, Sajad Khodadadian, and Siva Theja Maguluri. Finite-sample analysis of off- off-policy natural actor-critic with linear function approximation. TEEE Control Systems Letters, 6:2611-2616, 2022.
Zaiwei Chen, John-Paul Clarke, and Siva Theja Maguluri. Target network and truncation overcome the deadly triad in Q-learning. SIAM Journal on Mathematics of Data Science, 5(4):1078-1101 2023.
Kristopher De Asis, J dlenanndez-Gariia G Holland, and Richard Sutton. Multi-step reinforcement learning: A unifying algorithm. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Simon S. Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. In International Conference on Machine Learning, pp. 1049-1058. PMLR, 2017.
Yonathan Efroni, Gal Dalal, Bruno Scherrer, and Shie Mannor. Beyond the one-step greedy approach in reinforcement learning. In International Conference on Machine Learning, pp. 1387-1396. PMLR, 2018a.
Yonathan Efroni, Gal Dalal, Bruno Scherrer, and Shie Mannor. Multiple-step greedy policies in approximate and online reinforcement learning. Advances in Newral Information Processing Systems, 31, 2018b.
Yonathan Efroni, Mohammad Chavamzadeh, and Shie Mannor. Online planning with lookahoad policies. Advances in Newral Information Processing Systems, 33:14024-14033, 2020.
Amir-massoud Farahmand. Regularization in reinforcement learning. PhD Thesis, 2011.
Geoffrey J. Gordon. Reinforcement learning with function approximation converges to region. In Advances in neural information processing systems, pp. 1040-1046, 2001.
Michael Kearns, Yishay Mansour, and Andrew Y. Ng. A sparse sampling algorithm for near-optimal planning in large Markov decision processes. Machine learning, 49:193-208 2002.
Han Han-Dong Dong Lim, Do Wan Kim, and Donghwan Lee. Regularized Q-learning. arc preprint arXiv:2202.0540/ 2022.
Hamid R. Maci, Csaba Szepesvári, Shalabh Bhatnagar, and Richard S. Sutton. Toward off-policy learning control with function approximation. In Proceedings of the 27th International Conference on Machine Learning, pp. 719 726, 2010.
Sridhar Mahadevan, Bo Liu, Philip Thomas, Will Dabney, Steve Giguere, Nicholas Jacek, Ian Gemp, and Ji Liu. Proximal reinforcement learning: A new theory of sequential decision making in primal-dual spaces. arXiv preprint Xrx: 105.6755. 2014.
Francisco S. Melo and M. Isabel Ribeiro. Q-learning with linear function approximation. In Learning Theory: 20th Annual Conference on Learning Theory, COLT 2007, San Diego, CA, USA; June 18-15, 2007. Proceedings 20, pp. 308 322. Springer, 2007.
Francisco S. Melo, Scan Moyn, and M. Isabel Ribciro. An analysis of reinforcement learning with function approximation. In Proceedings of the 25th International Conference on Machine learning, pp. 664 671, 2008.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei Rusu, Joel Veness, Mare G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529 -33153999933339, 2015.
13

---

Published in Transactions on Machine Learning Research (04/2025)
Thomas M. Moerland, Anna Deichler, Simone Baldi, Joost Brockens, and Catholijn M Jonker. Think neither too fast nor too slow: The computational trade-off between planning and reinforcement learning. In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), Nancy, France, pp. 16-20, 2020.
Thomas M. Mocrland, Joost Brockens, Aske Plaat, Catholiju M Jonker, et al. Model-based reinforcement learning: A survey. Foundations and Trendol in Machine Learning, 16(1):1-118, 2023.
Dirk Ormoneit and Saunak Sen. Kernel-based reinforcement learning. Machine learning, 49(2):161 178, 2002.
Alexandre Piché, Joseph Marino, Gian Maria Marconi, Christopher Pal, and Mohammad Emtiyaz Khan. Beyond target networks: Improving deep q-learning with functional regularization. arXiv preprint arXiv:2106.0260 2021.
Doina Procup.
Eligibility traces for off-policy policy evaluation. Computer Science Department Faculty Publication Series, pp. 80, 2000.
Martil L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2005.
Aviv Rosenberg, Assal Hallak, Shie Mannor, Gal Chechik, and Gal Dalal. Planning and learning with adaptive lookabead. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 9606-9613, 2023.
Bruno Scherrer. Should compute the temporal difference fix point minimize the Bellman residual? the unified oblique projection view. Xiv preprinl arXiv:1011.4302, 2010.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550((676)):355 359, 2017.
David Silver, Thomas Hubert, Julian Schrittwieser, loannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforeement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1140 1144, 2018.
Satinder Singh, Tommi Jaakkola, and Michael Jordan. Reinforcement learning with soft state aggregation. Advances in neural information processing systems, 7, 1994.
Richard Sutton and Andrew Barto. Reinforcement Learning: An Introduction. MIT Press, 2nd edition, 2018.
Richard S Sutton. Generalization in reinforcement learning: Successful examples using sparse coarse coding, Advances in neural information processing systems, 8, 1995.
Csaba Szepesvári and William D. Smart. Interpolation- based Q-learning. In Proceedings of the twenty-fiee first international conference Machine learning, pp. 100, 2004.
John N. Tsitsiklis and Benjamin Van Roy. Feature-based methods for large scale dynamic programming. Machine Learning, 22:59 94, 1996.
Hado Van Hasselt. Estimating the maximum expected value: an analysis of (nested) cross validation and the maximum sample average. arXiv preprint arXiv:1322. 7175, 2013.
Zhikang T. Wang and Masahito Uoda. A convergent and efficient deep Q-network algorithm. arXiv preprint arXiv:2106. 15,19, 2021.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3):279- 2922, 1992.
Anna Winnicki and R. Srikant. Reinforcement learning with unbiased policy evaluation and linear function approximation. In 2022 IEFE 61st Conference on Decision and Control (CDC), pp. 801-800 806. IEFF, 2022.
14

---

Published in Transactions on Machine Learning Research (04/2025)
Pan Xu and Quanquan Gu. A finite-time analysis of Q-learning with neural network function approximation. In International Conference on Machine Learning, pp. 10555-10565. PMLR, 2020.
Shanglong Zhang, Hengshuai Yao, and Shimon Whiteson. Breaking the deadly triad with largel network. In International Conference Machine Learning, pp. 12621- 12621-12631. PMLR, 2021.
A Stochastic approximation
Theorem A.1. Lel us suppose that the Jollowing hold for the slochastic approzimation selling of Sec.
1. The map g R + R such that
g(w) =l)) -ww
is Lipschitz;
2. The sequence of me such that
M++1 = =(2+) (Te+1 - ywr (zt)) g(wr);
is martingale difference sequence with respect to {(T Wa) 8 S 1} and is such that
E |mm= ((Ta) i S s cm (1 (1+ ||well
3. The o.d.e
g(w)
has a unique and globally asymptotically stable equilibrium w such that
- = = (x) (=)] E 1bb (w))
4. The map ge R + IR such that
go(w) g(aw)
is such that lim (la((w) - goo (w))l uniformly on compacts for a Doo TR. - Rek and that the origin is the unique and globally asymptotically stable equilibrium of
= (w).
Then, the sequence of stochastic approzimation updates we converges to w".
B Multi-Bellman operator
Proposition B.1. The operator H is a contraction in the co-norm with contraction factor n
Proof. We establish the result by induction. First, we show that H contracts the co-norm. We start by writing the expression |[Hq - Hpllo in simpler terms, where q and p are value functions.
Hgg Hpll max
E
ox) + + maxq (z',a')
E
a(z,a) + max (x', m
2.a
a'EA
a'EA
max
E.
max a'EAA
(x',a')
max maxp (0', (4',
2,0
15

---

Published in Transactions on Machine Learning Research (04/2025)
Next, make use of Jensen's inequality to establish that
Hg Hpll y E max a'EA
q (z',a') max (2',
2,0
We use that the absolute difference of maxima less than or equal to the maxima of absolute difference.
Hgq - Hpll Y max 2,8 a'EA
E max lg (z', -p p
Then, we use that the expectation of random function is less than equal to its maximum.
Hqq - Hpll S 7 max max la (a', a') 1p0ppp(6- (=')
ø'Ex d'E
y max 1 (x',a') (
x' x'
||g pl
Now, we make the induction step for H=#1 HHR observing that
[| (H"4)) - H (H" S ||Hn H"pplsa
>7 |1q - plo0
= /1g plloo
We conclude the proof.
Theorem B.2. There erists N E N such that, for all n 2 N, Proj H contraction in the co-norm.
Proof. We want to show that there exists a function À N - such that
Proj (H" g) Proj (H" p)ll X(n) 11q plls
and such that, for all n greater than an existing N, A(n) is strictly smaller than 1. We start by showing that Proj satisfies
[Proj Projelax S &mnax 11q plloo
To see that, we start by recalling that
(Projg) (x, = (x (x,a)) " ((((x,))g(2,0)) "1
Then, we have that
[Proj Proj max 10= (z, az) ( a (x, " ()() a)
z.a
Now, make use of Cauchy-Schwarz incquality to say that
o0 a) [0(a, a)d" (c, a)] "1 || (a,, a) (1(2, a) - a))
|Proj q Ploj < max 2,a
and we can write, using the definition of the matrix norm induced by the Euclidean norm in R
| (z, |) E a)0" (x, -1
|Projq Proj pl max 2.0
E [o a) (g(x, a) p(x,a)))]]
We obtain that
Proj Proj plloo < mmaxxTax [l a)ll la(z, a) p(x,4)]
denn max l1g pl
16

---

Published in Transactions on Machine Learning Research (04/2025)
To conclude the proof, start by combining the inequality just established and Proposition B.1 [rooj (11*q) Proj (11" F || 1l
m 2" || pll
We finish the proof by using A(n) = d max It true that X(n) < 1 for all n 2 when we consider
= - log, (o mmxx)
Theorem B.3. For all 2 N, where identified in Theorem 3.9 W such that
1
11g" qa 10 1- -- 111" Iw loo
(33)
Proof. Let us use the triangle incquality with vertex qw-
l| - q0n a0 S 119" - qw 1loo + 11a - q0t Il
Now we focus on the second term of the right-hand side above. We have that
1 - -a- 20 = Prroj (H" q²) Proj (H" gan ol
From Proposition 3.3
have that
11 q 11 m max? 7" 11" qun 11x0
We can conclude the result taking algebraic operations, using o max Maax
C Multi Q-learning
Theorem C.1. There crists N N such that, for all N, there crists equilibrium nmm for the dynamical system
w = -E =o(o, (w) qu (2, a))]
Proof. We want to solve
or, cquivalently,
E [0(2, a) (n)) (w)) qu (2, a))l = O.
Taking linear operations, we have equivalently
w = E [ø(a, (x. a)) [dbar, (1 (r")"(w)))
We show existence and uniqueness of solution to the fixed-point equation by showing that the right-hand hand side is contractive. For starters, we have that
E [o a) (s, ax) "1 = =
Then, for any 8 E R using Jensen's and Cauchy- Schwarz incquality, we have that
[d(x, a)o (2, (z) E [o(x, a) (r" -. (w + +))]
O IIlØ(x, a)ll, IE (n" (w) mm + 8)][]
maxe Omaxx 119 qw++llss aloo
S m 2 ||01|,
Thus, if n large enough, the operator is contractive and the fixed-point equation has a unique solution.
1. R N is the ceiling function, giving the smallest natural that larger or equal argument.
17

---

Published in Transactions on Machine Learning Research (04/2025)
C.1 Convergence
Theorem C.2. There erists N E N such that, for all n 2 N and E N, the sequence of (WitLE is such that
lim 1 well2 = O.
Proof. To establish the result, we verify that we are in the conditions where Theorem A.1 which gives conditions for the convergence stochastic approximation algorithms, holds. We do so by proving the following lemmas, one for each of the assumptions of the theorem.
Lemma C.3. The may g R + R& such thal
g(w) I. (0( a) (Tn.0(()) (x)
is Lipschitz.
Proof. We start by writing
(wr(w) - 2(0)ll2 ||E (0( a) (7 (w) (1, a))] E (0(x a) (T" (0 a)]l(l
< |IE (0(x, a) (7 (w) -0))( IIB (0(2, a) (go(z, a) ( a))]ll
We take care of the second term by making of Jensen's and Cauchy-Schware inequality.
[[[ (go(a, a) - (x, a))lll I [[|d(r, a)lla (0,(x, a) gw (z,
S @max 11 qwlloo
s Tuax ||w - 0 1
Finally, by considering the sum of the coefficients from the first (obtained in the proof of C.1 and second terms, we have
([ g(0)l12 I &anxx (1 + 71)) 1|w 0012-
that is Lipschitz continuous.
Lemma C.4. The sequence of m, such that
m++1 6(F,, az) (T Im, (It, g(we)
is martingale difference sequence with respect to {(r..mm w.) S t) and is such that
[[mmitl {(7 w.) & $ t3] cm (1 + ||well))
Proof. A martingale difference sequence has zero expectation conditioned on the past. Such condition is evident once we consider Assumption 3.3 Then, a martingale difference sequence also has finite first moment. That bocomes evident when we observe that every term on the definition is bounded. Finally, since, again, every term on the definition is also bounded, the second moment is bounded.
Lemma C.5. The o.d.e
has unique and globolly asymptotically stable equilibrium is such that 3 ggw(w)
E [ [1, (x,a) a) of (sr,)] E. (bb (x. a) (.))
18

---

Published in Transactions on Machine Learning Research (04/2025)
Proof. We already know from Theorem C.1 that the equilibrium @ exists and is unique. Let us consider Lyapunov function 1: IR* - IR such that I(w) = 2 || w|l?. Existence of w is guaranteed from Banach's
fixed-point theorem and Proposition 3.3 It is clear that ((w) = 0 if w = S and that ((w) > 0 if w # w. Now,
we show that ((W) < if w + C.
We start by noticing that [(w) VI(w) w. Since VI(w) (w w) and i g(w), we have that
i(w) - (0 w) g(w).
Since g( 0, is also true that
((w) (ū w) (g (w) 9 (i))
For now, let focus on the second term of the right hand side and write
((او g( E [0(x, a) (r" (w) ". (a)) E [0(x, a) (1=(2, (xr
Let us make two assertions, one for each of the terms on the right-hand hand side of the equation. First,
| [E[ (T (i) F n (w)) ||l [0(z, a) (r (a) (w))]ll2-
Using Jensen's s and
inequality just in the previous proof, we get that
E [0(x, a) (w) - "")"(" S m y" ||e - wll
Second, we have that
E [0(x, a) (1, - 9 (x, a))l = E [0(z, a)o² (z, a)] (w - w).
Having established the two assertions mentioned, we make use of them in the following.
[(w) = - (ā - w) [d(x, a) (7 (w) (a))
(w w)|L [ō(z, a) [z) (w w) < ( w) E (Ø(z, a) (r (w) - -". (+))lll
(et w)B [d(z, o) (z. a)] (o w)
S 2m 7" || - wll2 Amin | 1--w)l wl12
(o m Amin) ) ||0 w
where Amin is the smallest eigenvalue of the auto-correlation matrix E [ō(z, (z, The expression is negative large enough. That concludes the proof.
Lemma C.6. The map 9. : R > TR. such that
gc(w) g((w)
is such that lime-+o (l 9oc (w)ll uniformly on compacts for some hoo RR. - Re and that the origin is the unique and globally asymptolically slable equiläbrium of
is = (w)).
Proof. Let us expand the definition and obtain
E [0(z, a) (7 gew (x, a))
(w)
IE [0(z, nm
E [0(x, a) (x,
19

---

Published in Transactions on Machine Learning Research (04/2025)
As co, we have that ge(w) - 920 (w) uniformly, using Ix (w) -E -((((, We then have that the ordinary differential equation
ع (w)(w)
- (T,,
-E [o(z,a)0² (z. (z.a))
is linear and time-invariant. Since the matrix above is invertible, we have that the origin its unique and globally asymptotically stable equilibrium. We conclude the result.
C.2
Performance
We establish the following lemma, quantifying the bias between the multi Q-learning target and the target from the multi-Bellman operator. We will use the lemma in the subsequent theorem, which will include function approximation.
Lemma C.7. We have that
s E (I, (I (H²g) (x, S VIA
vm
where 8 max / var (mm) and 01 0
Proof. We prove by induction. The basis is true because the bias of the 1-step update zero. We move on to the step.
From the definition and then taking algebraic operations, we have,
T m.m (a', ad) .21))
E B (x, a) g)) (x,, a)] = E (((,,a) +7 max
(((x,)) a) + max ((H () (I
max
n,m (2', a') - max ((H 9) (a', aa))))
Now, we use a result from Aven 1985
that says that, for given set of random variables (Sihier
I -
max S I max E [sil +
Σ var (Gi).
and have, after Jensen's 's inequality exchanges the order of the max and the expectation, that
E (
(x, a) (1=+11) 4) (x, a)] s 7E max E n, (x', a')) max (H" g) (x', a')
AA 1
m var
%
mm (x', aa))
A
m
Then, we add the absolute value and see that
E 1,m (x,a) - (H 4) (I, a)) S 7E
max E n. (x',a')) - max (H"g) (x', a')
I -1
m
+ ?
Σ
var
T mmm (x', ,a)
|A
m
t=1
20

---

Published in Transactions on Machine Learning Research (04/2025)
S yiB
max [rum
( (x',a') - (H (o', a')]
a'
IAI
m22
nam (xc,, at)
v [A
var
m
'E max E [r (a',
(H" q)
(a' a')l]
a"
LA
1 Σ
|A]
max var
70.m (x', ,
[AI
m
Now, we use that for a given random variable S,
5 var (5)
and proceed to see that
E [ 1 I. (I, a) (Ha+2g) (z. [2) $ yB 17 (x', a²) -(H" 9) (x', ,a)]
+ 7 (IA) - 1) max var (r (x', a²))
m
Next, we use that
mmax(-) max V-
and the hypothesis to conclude
n- 1
g
E T Im (x, - (H (x, S SyVAA -
A
m
vm
a+1
0
S -
7 -+1-
m
Theorem C.8. For all n 2 N and m E N, we have that
E g
l1aan Yo || 5 1 - X7 mm
8" = max var (7n-1,m) & = d Taax VAA -1.
Proof.
11 qamm/lo 1000 < Proj H qmm H"
Proj H" 9mm. 1o0 + Proj H qpmm qpmm 1000
Ay "lgann qsm.m loo + Proj H" qen.o Tan.m 10
Proj H
gan.m go
mm 1lo0 Da (o (I, a) - (r"qom))))) (2,
21

---

73000 300000 225003 275030 Published in Transactions on Machine Learning Research (04/2025)
Ca CartPolevv
CartPole
400
200
50000
73000 200000 123000 130002 steps
(a) Cartpole, with each dimension of the state space discretized in two.
(b) Cartpole, with each dimension of the state space discretized in four.
Figure 7: Cartpole results. The y-axis shows the average return. The performance increases with
Using the previous lemma,
E [H" (an.m) ) (x, a) (o"m))) (I, = E [(7"[[ gma.m) (I, a)
(H" qan.m (x, a)
v (1A1 1)
1=1
V|AI| 1) 8
V(A - 1) g
1 1-7 mm
where we used that, for all i S n
0 0
and
- 7-1
1 7 1 1-7
1
We conclude the result.
D Additional experiments
In this appendix we provide additional results regarding the Carpole environment. We show results for features resulting from a finer discretization of the state space in Figure 7 Specifically, each dimension of the state space is discretized in four, whereas in the results the main text each dimension discretized in two. We recall the results from the main text. for comparison. We see that the performance of Q-learning (n = 1) improved the most. The performance of multi Q-learning (n and 4) also improves. Overall the performance of multi Q-learning is superior to Q-learning.
22


Reviews:
[{"review_id": "FW1qjnQJK9", "reviewer": "Reviewer_ScuR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n* The experiments, while limited, are convincing.\n* The limitations are explicitly discussed in 7.1.\n* The multi-Q-learning algorithm is novel and theoretically supported.\n* Convergence of Q learning is of interest to the machine learning community.\n\n## Weaknesses\n* Very limited discussion of the \"Bias\" example.\n* The paper lacks context around examples. Why are these examples used?\n* The usefulness of this algorithm in real world scenario is limited. (but correctly highlighted in the limitations)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper addresses the convergence issues of Q-learning with linear function approximation. The authors introduce a multi-Bellman operator and the multi-Q-learning algorithm. The algorithm is novel and theoretically well-motivated. Finally, the authors show the effectiveness of their algorithm empirically.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Move Figure 3 to the top of the page to make the paper easier to read.\n* Add a graphical representation of the toy environments.\n* Motivate the \"Bias\" example. Why is this example necessary? \n* Move the \"Bias\" example into 5.1 since it is about convergence and not performance.\n* Equation at the top of page 5. \"i\" is not used inside of the sum.\n* Why are so many discount factors are used in the experiments? I see that 0.9, 0.98 and 0.99 are used without justification.\n* Mention semi-gradient methods in the background, since they are mentioned in the related work.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "2omGZiUO4p", "reviewer": "Reviewer_o6SM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Proposal of updating Q-values multiple times in a single step is novel and interesting. \n2. The proposed use of multi-Bellman operator and its application to obtain a contraction of the Projection of Bellman operator is interesting.\n\n\nWeaknesses:\n1. For learning Q-value function given the complete MDP, Bellman equation is applied multiple times which essentially is the multi-Bellman operator. Essentially, the proposed algorithm solves for Q-value function with unknown dynamics as if were completely known. This needs to be discussed in the paper if and how the multi-Bellman operator is different from this.\n\n2. Multi step $Q$-learning equation (above section 4.1) is not clear. Which variable contains $i$ in the update equation for $\\tau_t^{n+1,m}$.\n\n3. This statement, \"At time step $t$, instead of building a 1-step greedy target, multi Q-learning builds a target that is obtained\nby trying, on every state encountered along $n$-step trajectory starting at $x'_t$, every action $m$ times, and maximizing the average of the sum of the discounted rewards at each level.\". How does this not result an $m^n$ exponential complexity. This is not clear.\n\n4. \"We assume access to a fixed replay buffer of 1-step transitions and a simulator to sample transitions\" If you have access to simulator, why the simulator alone cannot be used for learning is not clear?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a multi-step bellman operator based $Q$-learning algorithm with linear function approximation. Instead of applying 1-step greedy $Q$-value updates using Bellman Equation, this paper proposes to updates the $Q$-value function iteratively $n$ times over every step. Further, the paper proves that the proposed method allows for projection of the Bellman operator to contract for sufficiently large values of $n$. Additionally, the paper implements the algorithm on standard RL benchmarking environments (acrobat and cartpole) to empirically show the performance of the algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Please conduct an the empirical study by updating the policy after every $m$ steps to update $Q$-values using $m$ iid data points. It will be a impactful if the algorithm convergence can be improved by reducing the variance of multi-q learning.\n\n2. Please correct the update equations for $\\tau_t^{n+1, m}$\n\n3. Please add the proposed algorithm explicitly.\n\n4. Please use equation number so that the equations can be easily referred.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8O3ZSk06Zh", "reviewer": "Reviewer_j3Jj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength:**\n\n1. The authors tackle an important problem, the divergence of Q-learning under linear function approximation, and using a multi-step method provides a new perspective on this problem.\n\n2. The theoretical analysis is solid.\n\n\n**Weakness:**\n\n\n1. The rollout of $n$-step method has been well-studied (as noted in the related works) and its contraction rate being $\\gamma^n$ has been well-known in the literature as noted in the related works.\n\n2. The practical implementation is somewhat difficult. The algorithm converges to a biased solution, and to reduce this bias, we need a large number of $n$-step sequence each state pair. Furthermore, we need the knowledge of reward function because we need to take a maximum over reward function to compute $\\tau^{n,m}$.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of convergence of Q-learning with linear function approximation. The authors suggest that using a so-called multi-Bellman operator method resolve the divergence issue. The key idea is that if we use a $n$-step roll of Bellman operator, the contraction factor can be controlled by $\\gamma^n$ where $n$ is the number of steps and $\\gamma$ is the discount factor. A sufficiently large $n$ will ensure the contraction property of the suggested operator.\n\n\nFurthermore, the convergence of the proposed stochastic algorithm is established from the ODE argument by Borkar-Meyn Theorem. The proposed stochastic algorithm uses a biased estimate of multi Bellman operator $H^nq_{w}$, which requires knowledge of the reward function.\n\nLastly, the authors study the bias of the solution of multi-Bellman equation (Theorem 3.7); bias of the multi Q-learning algorithm which is due to using a biased estimator of multi-Bellman operator.\n\n\nMoreover, the experimental results are provided.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Can the authors comment more about the bound in Theorem 3.6? For example, when $n\\to 1$, do we recover the function approximation error $\\frac{1}{1-\\gamma}||q^*-\\mathrm{Proj}(q^*)||$?\n\n2. As for the Cartpole environment, Can the authors also provide comparison under the case when Q-learning performs well?\n\n3. It would be helpful to understand the algorithm if the authors can add a pseudo-code.\n\n4. I think there is typo in the proof of Lemma C.7. In the second line of the first equation: $Hq$ should be $H^{n}q$.\n\n5. There is slight mistake in proof of Lemma C.5. $\\phi^2 \\gamma^n-\\lambda_{\\max}$ should be $\\phi^2 \\gamma^n-\\lambda_{\\min}$.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers unanimously agree to accept the paper. They find the perspective of viewing the divergence of Q-learning from n-step method to be new and expect that this will be helpful to the community. The theoretical results including bias and variance analysis is also appreciated and is expected to be helpful to understand the limits of the n-step method of Q-learning. 

A small comment is regarding the focus on linear function approximation and the concern that it may not align with ICLR's emphasis on deep (reinforcement) learning algorithms. I do not believe this to be a big issue. Another concern is regarding the exponential complexity of the algorithm, which authors may want to comment on in the camera-ready version (perhaps in the discussion). A reviewer also points that this work might be useful in training LLMs using a reward setup at each token which can act as a simulator.
Decision: Accept (poster)