$Q$-learning with regularization converges with non-linear non-stationary features
Authors: Diogo S. Carvalho
Francisco S. Melo
Pedro A. Santos
Venue: Submitted to ICLR 2023 (2023)
Keywords: Q-learning
Reinforcement Learning
Stochastic Approximation

Abstract: The deep $Q$-learning architecture is a neural network composed of non-linear hidden layers that learn features of states and actions and a final linear layer that learns the $Q$-values of the features. The parameters of both components can possibly diverge. Regularization of the updates is known to solve the divergence problem of fully linear architectures, where features are stationary and known a priori. We propose a deep $Q$-learning scheme that uses regularization of the final linear layer of architecture, updating it along a faster time-scale, and stochastic full-gradient descent updates for the non-linear features at a slower time-scale. We prove the proposed scheme converges with probability 1. Finally, we provide a bound on the error introduced by regularization of the final linear layer of the architecture.

Under review as a conference paper at ICLR 2023
Q- -LEARRNNG WITH REGULARIZATION CONVERGES WITH NON-LINEAR NON-STATIONARY FEATURES
Anonymous authors Paper under double-blind review
ABSTRACT
The deep Q-learning architecture is a neural network composed of non-linear hid- den layers that learn features of states and actions and a final linear layer that learns the Q-values of the features. The parameters of both components can possibly di- verge. Regularization of the updates is known to solve the divergence problem of fully linear architectures, where features are stationary and known a priori. We propose deep Q-learning scheme that uses regularization of the final linear layer of architecture, updating it along faster time-scale, and stochastic full- full-gradient descent updates for the non non-linear features at slower time-scale. We prove the proposed scheme converges with probability 1. Finally, we provide a bound on the error introduced by regularization of the final linear layer of the architecture.
INTRODUCTION
The Q-learning algorithm, introduced in the seminal paper of Watkins & Dayan (1922), ) is stochas- semi-gradient
tic semi gradient descent algorithm that allows agents to learn to make sequential decisions towards long term goals by learning the optimal state-action value function of given problem. The rele- vance of Q-learning in reinforcement learning (RL) cannot be overstated, as Q-learning with deep neural networks sustains the biggest breakthrough the field has seen (Mnih al. (013).
We can cast a deep Q-learning architecture as a neural network that combines non-linear com- ponent hidden layers, learning features of the input, and final linear component that learns the Q-values of the learned features, depicted in Figure Despite its merits, there is no guarantee that Q-learning with function approximation architectures, even linear ones, converges to the de- sired solution. In fact, divergence happens in well known examples where the parameters of the approximator do not approach any solution, either oscillating within a window (Boyan & Moore 1995 Gordon, 2001) growing without bound (Tsitsiklis & Van Roy 1996 Baird 1995). There is also evidence for convergence to incompetent solutions van Hasselt et al. 2018).
Recently, the works of Carvalho et al. (2020), Zhang et al. (2021) and Lim et al. (022) provided insights on the role of regularizana larization of the parameters and of the Q-values for stabilizing Q-learning with linear function approximation and obtaining provably convergent scheme. Under the light of the architecture in Figure[] I their setting is one in which the features are stationary and known a priori and only the final component is learned. In this work, we investigate whether a regularized version Q-learning with linear function approximation schemes converge while features are non-stationary.
In Section 3 as first result, we assume that the features are updated along a slower time-scale than the final layer and that they converge, and prove that the final layer converges. Our setting and proof are based on two time-scale stochastic approximation ideas. We also bound the distance between the optimal Q-function, generally outside the span of the features, and the regularized solution.
Then, in Section 4 we investigate how we can learn the non-linear features along the slow time-scale with provable convergence guarantees, thus verifying the assumption of the first result. We propose three learning schemes that perform stochastic full-gradient descent on well defined loss functions and are able to recent result from Mertikopoulos et al. 22200 establish their convergence.
Putting our two results together, we obtain the first convergence result for stochastic semi semi-gradient Q-learning schemes with non-linear function approximation. Our scheme is two time-scale, where the final layer of a neural network is updated faster and learns regularized Q-values of non- non-linear features that are updated slower and with stochastic full-gradient descent updates.

---

Under review as a conference paper at ICLR 2023
Hidden layers
Final layer
@u(a,a) a)
0u(z,
(a,a) a)
Non-linear features
Linear activation
Quaiataa
Figure 1: A general deep Q-learning neural network architecture. The state-action pair inputs (z, a) are fed to non-linear hidden layers that output features the input du (a, a). Then linear activation layer parameterized by outputs the Q-values of (x, a) using the features. Usually, the architecture learned through performing stochastic cemi-gradient descent updates on the Bellman error.
2 BACKGROUND
A Markov decision process M is tuple (, R), where X' is a finite set of states, is a finite set of actions, P is of transition probability distributions P(x, a) E A and R is set of bounded real-valued random variables, R(x, a) E [-Tmax: Tmax). called the reward.
An agent interacts, discretely, with an environment described as a Markov decision process by ob- serving the random state of the process X,, performing a random action A, and receiving a random reward R₂ ~ R(X,, At). The state of the process changes X₃-1 and the interaction repeats. The way the agent selects actions once it observes a state is prescribed by policy ı that, for each state, a probability distribution TTx) A(A).
For given policy т, we measure the value of performing some action at some state through the function Q* : x A R. The Q-function, given state-action pair (I, a), gives the expected sum of rewards the agent receives throughout its interaction with the environment, after performing action a in state x, then continuing choosing actions according to म, and considering a discount factor [0, 1).
The Markov decision problem is the one finding a policy n² such that, for every state, maximizes the value of the best action. Such policy is known exist (Puterman [005] Section 6.2). It may, however, not be unique. While an optimal policy π is not necessarily unique, the optimal value Q" and verifies the fixed-point equation of the Bellman operator
(z, E [[[((,,)) + 7 Q" (x' a'EA
Q'(X' a').
(1)
where X' P(x,a) a) and the expectation is taken with respect to X' and R(x, a). Additionally, from Q" we can obtain an optimal policy x² by greedily choosing, for each state, the action with highest Q-value. Consequently, we can solve the Markov decision problem by solving the fixed- point equation above.
To solve equation
1
we can define loss function h RR_ R such that
hww)= = E (R(X. + m a'eAA
max (x' Qxx
where Q., : X' x A + R is function approximator, for instance neural network, and w E R its parameters. Additionally, the expectation is taken with respect to a distribution over state, action, next-state and reward transitions A, R(X,A)).
If assume the off-policy target R(I, a) + y max.'e. A Qu .a) of equation 2 is fixed obtain a stochastic semi- cemi-gradient descent scheme to minimize h. The resulting algorithm called Q-learning with function approximation and takes the form
Wi+1 w. + (r + max Qu( a') Qu ar)) V Qo at) a'EA
where state-action samples (#t, ar) n. the data distribution / A(X x A), next-states x/ P(r,, az), rewards r; ~ R(x,, a;) and a; E R+ is a learning rate.
We use (B3) to denote the set of probability distributions over a set 13
"hhe technique is usually referred bootstrapping.
2

---

Under review as a conference paper at ICLR 2023
3 LEARNING WITH NON-STATIONARY FEATURES
In our work, we consider parameterized functions as depicted in Figure | We observe that a state- action pair (2;, a) is the input, and is processed by non-linear features parameterized by u, Ou- Then, 0u (I. a) is passed on to a linear layer parameterized by u. The output is Qu,([ a). In architecture, we use Qu,a X A R such that (1, a) = du (2, Proj,(1) where Proj, : I K + B, maps v to a ball of radius p in RK that can be arbitrarily large. Proj, ensures boundedness of the Q-values without requiring boundedness of the parameters. We refer to the parameters of the final linear layer, V E IK as the final parameters, to the parameters of the non- RD, as the hidden parameters and to O.. X' x A - R K the features.
linear hidden layers,
In this section, we make the argument that learning the final parameters e at a faster sime-scale than the hidden parameters allows to decouple the convergence analysis of the two and consequently establish that a regularized version of Q-learning with convergence guarantees for the stationary features case, will also converge if the features are non-stationary but convergent. Specifically, following Borkar [2008] Chapter 6), assuming the features change slower than the final layer allows us to treat the former as being quasi-static from the point of the view of the latter, even though both learning processes evolve simultaneously. We note that, in our analysis, we do not require, necessarily, that the features learn through the same supervision signal as the final layer.
We define the Q-learning scheme of the final linear layer with the addition of ridge regularization of the parameters, merging ideas from Lim et al. (2022) and ZZhng et al. (2021).
Definition 1. In Q-learning with regularization, the final parameters are updated according to
c 0z + an (r. + y max (2 d') - 5Qu, (I2, a,)) p.. (Ie, a.) C,CU',
a'EA
where 5,e > are regularization hyper-parameters and the positive learning rates in far are such that Dr= Ot xc and Er= of oc. We observe that if & 1, e and p - oc, we recover the original Q-learning with linear function approximation algorithm, which can diverge.
For our first result, let assume the features are updated much slower than the final layer through stochastic approximation scheme with well-behaved noise. Formally, we assume the following.
Assumption 1. The hidden parameters u are updated according to
Ue41 Ue + (g(VV, u.) N2+1),
the sequence of random vectors {N.) has zero mean and finite variance; the learning rates in (20 are such that Et=o 32 = x0, E B2 < oo and B./a, O. We finally assume the sequence (1: converges, i.e. that ut- + u² for some u' E R.D
where the vector field g RK+D + RR is
In Sec we propose three feature learning schemes that satisfy Assumption [ i.e., specific choices of g and N that are provably convergent. For now, we establish that Q-learning with regularization converges with non-stationary convergent features.
Theorem 1. Suppose that Assumption holds and moreover
(i) For all 2 O, the distribution μ. A(X x A) and is such that (N,, At) ~ p and are i.i.d::
on the first argument; (iii) For all u E RR, the features &u are such that, for all (x, E X x A. [|ou( a)ll S 1;
(i) The architecture cb R.. X + K and is Lipschitz-continunn
(iv) For all u E RD, the features du and the distribution i are such that the K x K matrix is dositive-defiitee and its minimum eigenvalue is a.
Σ. = E A))
Additionally suppose that the regularization parameter E > 1 is large enough, specifically that { 2; that e > 0 is small enough, specifically that < - "; and that the radius of the ball Bp, Your E--
p > 0, is also large enough, specifically that >
Then, it holds that et-
- 0² (1²) I.p.1, with o- :R RKK such that 1 ---1 (R(X,
2² (u)
(__'E((((x,,))) A) + max d'EA
c (x-lo²(u). Qu (X))
5
{
3

---

Under review as a conference paper at ICLR 2023
Before we present the proof, we discuss Assumptions (iv of Theorem
While not necessary, Assumption ii facilitates the formal analysis of the stochastic processes, as well as its exposition in the document. Assumption (ii) allows us to use theoretical results the convergence of stochastic approximation processes, such as the ones of Borkar (2008] Chapter 6; Theorem 2) and Mertikopoulos al. (2020) Theorem 2). Assumption ( is important the for- mal analysis of the limiting ordinary differential equations, as well as to assured of technical requirements, such as Lipschitz continuity of the update. Specifically, since the Q-learnin update considered features products between and u dependent quantities, the assumption ensures the ex- pected update Lipschitz-come contbiuuss Finally, Assumption (iv) used to guarantee existence of solution to the limiting o.d.e., as well as to characterize such solution.
Proof. We present outline of the proof, referring to the supplementary material for proofs of auxiliary lemmas.
The Q-learning algorithm presented is two time-scale stochastic approximation algorithm where the fast component takes the form
+ (J ue) - Mc+1);
Vt+1
with f + RR* the expected update
f(u, u) = (R(X, + max a'EA
Qu,(X' AX) A)]
and Me E R its noise.
Borkar (2008) Chapter 6; Theorem 2) provides conditions under which the stochastic process above converges. The conditions include that is Lipschitz and M,+1 is a martingaleddiffrrence sequence, which show through Lemmas and respectively. In addition, Lemma 3 establishes that, for each u E RD, the ordinary differential equation (o.d.e.)
d1 f(v,, u)
has unique globally asymptotically stable equilibrium v* (w), using Lyapunov argument. Since we show using Lemma 4 that, additionally, the iterates remain bounded, we conclude through Lemma that they converge to the equilibrium w.p.1.
We finish this section by providing a bound on the solution obtained by the Q-learning scheme considered and the optimal solution.
Let us denote the optimal Q-function by Q", which exists and is unique and is generally outside the linear space generated by the features du-. Let define the orthogonal projection of Q" into such linear space as the operator 4.- such that (Z), a) = o (x. a)E,, 'E' (0 a)Q(z, a)). We can think of au. Q* as the best linear approximator of Q" Unfortunately, such approximator is, in general, not reachable through Q-learning.
Using wn to jointly denote the parameters of v²("", u", we have the following result for the solution Qw- otained by the regularized Q-learming scheme.
Theorem 2. Under Assumptions 7 and (i) to (iv) Theorem on Qu::
have the following error bound
Eo
Fmax (5 -11 + Sc: 12"" P.. 1 + (1 7)(Ea -7)
IIQ - Qw- <
(4)
Eo
where f.
EFaer Ee(a-9-11
Ear Eo--a
In equation we observe the bound depends on the regularization, through the hyper-parameters and c, and the features, through and u*. We make - 0 and make fa arbitrarily small. As for the second term, it disappears if g = 1 and the error then depends only on the best possible solution for the given features, Q" However, if the Q-learning scheme may diverge.
4

---

Under review as a conference paper at ICLR 2023
Proof. We have that
||Q - Qu- 20 - 1QQ - 10 + 1 Q" - -
Let us consider the second term on the right-hand side. We know that Q" = HQ" using to denote the Bellman operator, and that Q $ HQ wr + & o" (u") from the characterization of the limit solution in Theorem 1
Then, we have that
1 | Qw Iloe = Q" - t 1..Q"ll + 11 HQQ - -v fu- 1l + Eo - =1lv"(u))) (u")
5
(5)
by means of the Cauchy-Schve Scchwa- and Jensen inequalities. For the first term the right hand side of equation we can establish that
T'mx (E 1) Pu- Q~ S 11 17 S
PP Q-
EØ - 7)
For the second term the right hand side of equation 5 we have that
1 HQ" 2u- HQ 1l S Eo
10- Qw 1100
Finally, for the third term on the right hand side of equation
5 we start by noting that
(v"("")) - o (rmax + +~ll""("''*>>>""> (l=")
1
fo || (o"""u))las loo.
Equivalently, for the third term on the right hand side of equation we have
mamax fo 10 (u")ll Şσ(a - ED
Putting everything together, conclude the result.
3.1 EXPERIMENTAL RESULTS
We illustrate our proposed learning architectures under three examples with converging features. In all of them, the original Q-learning diverges while the proposed architecture does not.
LINEAR 2v EXAMPLE
In the 2u example of Tsitsiklis & Van Roy (1996) there first state always transitions to the second; the second state always transitions to itself. All rewards 0 and, consequently, so are the Q-values. We consider the features (x(x) (1(x) u, where
states and single action. The
(x:) is for the first state and for the second state and E R. We consider = (-1)' 0. We divide the features by in order to respect Assumption (iii). The desirable behavior of Q-learning the parameter diverges.
would be + 0. Figure 2a shows the results. We can see that when As increases, learning is more stable. When { = 2, v converges to the desired solution 0.
STAR EXAMPLE
The star example of Baird (1995). slightly modified by Sutton Barto (2018), has seven states and two actions. One of the actions transitions to any of the first six states uniformly, the other action transitions to the seventh state. rewards are and so are the Q-values. The behavioral policy chooses the first action with probability and the second action with probability 4. Therefore, the next state distribution is uniform. The target policy, however, always chooses the second action. For the first six states, the state-fcatures features x-th component, in the eight component and 0 otherwise. For the seventh state, the features are 1 in the seventh component and 2 in the eight component. We consider again converging hidden parameters u, (-1)*(3 respect Assumption (iii. 2bg shows the results obtained. When & 1. the parameters grow. However, see that as & increases, the final parameters do not grow, desired.
(z) v(x) + g where (xx)) are 2 in the
11:71 1.!) + O. We divide the features by v5 in order to
5

---

Under review as a conference paper at ICLR 2023
50
40
(-2
11
30
20
20
40
60
80
100
200
400
600
800
1000
Time steps
Time steps
(a) Linear 2v example.
(b) Star example.
Figure 2: Experimental results on the linear + 2v and star problems under non-stationary con- vergent features for different values of regularization parameters & and fixed c 10-8. As the regularization parameter increases, Q-learning updates stabilize and the parameters converge.
25
1.0
2=2
1.5
0.6
1.0
62
0.0
(=2
100
200
3.00
400
500
100
200
3.00
400
500
Time
Time
(a) Final parameter U.
(b) Hidden parameter u.
Figure 3: Experimental results on the non-linear v + 2v problem for different values of regular- ization parameters & and fixed = 10 8, As the regularization parameter& ç increases, Q-learning updates stabilize and the final parameters converge. The hidden parameter converges regardless of the regularization parameter ç, though the limit solutions are different for different values of &.
NON-LINEAR 20 EXAMPLE
modify the v - 2v to a non-linear learning architecture. The Markov chain remains the original from Tsitsiklis & Van Roy (199)), and so does the data distribution. We learn the linear features with sigmoid activation function (x)x) = (z)) with the final linear layer parameterized by (ő(x)u)v.
and again (x:)
0 recovers the correct Q-values. In Figure 3a we see divergence of the final parameter when = and convergence to the correct solution when { 1.5 and 2. In both cases the features converge, be seen is Figure 3b
Then, we have (x)
LEARNING NON-LINEAR FEATURES
Theorem states that the regularized Q-learnin scheme is convergent with features that chang- ing over time, throughout the learning process, as long as those features converge. We now present three learning settings for the hidden layers that we can show satisfy the assumption, i.e., three learning setting under which convergence of the features is guaranteed.
We consider D-times differentiable objective function h RD IR. We want find =* such that
min ((2).

---

Under review as a conference paper at ICLR 2023
The stochastic gradient descent scheme for solving the equation above takes the form
2(+1 = Be (V=((z)) + Y++1),
where the random variables Y, have zero-mean and bounded variance. We have the following result from Mertikopoulos al., (2020).
Theorem 3. Suppose that the function h is Lipschitz-coninnuuss Lipschitz-smooth, coercive and not asymptotically flat. Then, we have that the set of critical points Z == {z : Vzh(z) 0} is non-empty. Further suppose that the random variables Y, have zero-mean and finite variance. Then,
2t
" w.p.1,
where 4 C z is a bounded connected component over which h is constant.
Theorem provides general conditions under which the parameters of a stochastic approximation scheme that is, particularly, stochastic gradient descent of loss function h, converge to bounded region with constant value. While Q-learning is not true stochastic gradient descent and divergence of the parameters is known to happen, it is possible learn the parameters of the features through stochastic full-gra full-gradient descent and obtain convergence guarantees. In the sequel, we propose three such feature learning schemes. One of the proposed schemes based on an unupervised learning update; another is based on a semi- supervised learning update; the final is based on a reinforcement learning update. light of Theorem 3 all the proposed feature learning schemes are in accordance with Assumption and are thus guaranteed to converge. We note, however, that in order to guarantee boundedness of the features, we should post-process them with a sigmoid final layer, a R + [0, 1] such that (z) T+e x thus respecting Assumption iill of Theorem
We define the generalized Huber loss H R.L. TR such that (1)) minpe(1.2) 1 |
robust loss function in the conditions demanded by the theorem. The Huber loss considered is thus the 2-norm if its input is close to the origin and the 1-norm otherwise. Additionally, we remark that the finite linear combination and the finite composition of Lipschitz- smooth functions is also Lipscuuu and Lipschitz Finally, note that V sign(l) if arg min pE (1.2) || and (I)) = if arg (1.2) 11 |11
and Lipschitz-
4.1 UNSUPERVISED LEARNING
We can learn a linear map that reduces the input space, linearly, through principal component analy- sis. In the non-linear case, we instantiate such learning using auto-encoder (Liou et al. (0144) or variational auto-encoder (Kingma & Welling 2014) architectures. Finally, constrastive learning has also been used in feature extraction (Laskin al. 2020). All these methods have no task information but can still be powerful if dimensionality is an issue or we want to transfer learning across tasks or even domains (Higgins al. 2017). We focus here on the definition of a loss function over which the stochastic gradient descent scheme is guaranteed to converge: the auto-encoder. Formally, the auto-encoder performs stochastic gradient descent over the loss function
hu,, s) EE Kis (v A))) (X (()
where (z, a) is an euclidean representation of (x, a) in R.P. In the auto-encoder, an encoder &u Rº + R u E RRP learns to map the features into latent space and decoder Kg : RR - R. learns to reconstruct the original input. The features &n can then be normalized and inputted to the final layer of our regularized Q-learnin scheme. The auto-encoder has been applied successfully in reinforcement learning tasks (Lange et al., 2012).
In practice the stochastic gradient updates are as follows.
Ue+1 Ut 8 V. Qu. (b(2, Vra. (m.. (v(z, (b( Ko (o
3, V KK, (bu (bb a)) VΦn. (v/a a)) VH Kis ( (ox, ())
8141 5t
The process of learning the final linear layer parameterized by v evolves concurennlyy described in 3 As long as 3, is o o(a)), convergence of both sets of parameters happens with probability 1 according Theorem

---

Under review as a conference paper at ICLR 2023
4.2 SEMI-SUPERVISED LEARNING
We can also approach the feature learning problem in a semi-superviset way grounded in MDP theory (Ferns al. 2004). Specifically, instead only learning put together inputs that are close to each other in the original space, we can learn to put them together if they are close to each other the Markov decision process. Bissimulation metrics (Ferns al. (01T)) give us a way to perform such learning, by considering that state-action pairs are similar if they produce similar rewards and lead to similar states. We can thus define the loss function
((u) [ -
-R (
and perform again stochastic gradient descent. The technique has also provided positive results in practice, specifically when compared to unsupervised learning (Zhang et al. 2020).
In this semi- supersupe setting, the stochastic gradient updates take the form
Ue+1 = - 3e (ulo (2), a.) - ou, (Tt, āe)) V (ove (Ee, ac) Oue (=))
Vu (oue at) - Sne (8t, az) V Oue (2t, Due (Tt.
VH H (mu (2r, a.) Dus (Rt, ār)) H(r (r)) H H( (Per Due (izz :)):
where (āz, 0r, 2/ f Fr) are sampled independent and identically distributed. Again, learning scheme used to update the hidden parameters can happen alongside learning of the final linear layer parameterized by and convergence guaranteed by Theorem
4.3 REINFORCEMENT LEARNING
Q-learning assumes bootstrapped targets and thus makes only stochastic semi-gradient descent over the loss function. In practice, that choice may produce good results but is often unstable. We propose that we could learn the features through full stochastic gradient descent and learn the final layer through the usual regularized stochastic semi-gradient descent scheme. The loss function considered is
M(u v') = H(R max ox(,
H a'EA
Recent work from Avrachenkov et al. (202I) proves that, often, the stochastic full gradient descent over the loss function is able to perform competitively with the stochastic semi-gradient scheme. The updates take the form
u++1 ui B.V
max Su,, (2/, d') vi. om oue, ar) (e))-o)) v%)
d'EA
(Vadus (Tt, at )1) V
max Pa, (xb6,a')
d'EA
M411 of 3. (Ft + max Par (1), d'ed
Ou (xt, ai) vf)
(ou, (Ie, ax) - V max pu, (2', a' d')u))
d'EA
For the gradient of the max operator, we may consider a smooth approximation parameterized by a, max., such that max (V1, (Vi,...,
Eizt 2
As a + oc, maxo + max.
The hidden parameters that being updated can, at the same time, be used to learn the final parameters using the regular semi-gradient Q-learning update. In the regularized version of Q- learning presented in Section convergence happens (Theorem 3
In practice, our proposed approach is halfway between the full- gradiend and semi-gradient schemes for reinforcement learning and is able capture the stability of full- aall-gradient schemes and optimality of semi- aami-gradient schemes. The additional computational and training costs are minimal. More specifically, one additional linear layer of parameters E I2 is required.
8

---

Under review as a conference paper at ICLR 2023
5 RELATED WORK
There were initial efforts to provide stable Q-learning methods in the presence of function approx- imation (Singh et al. 1994 Ormoneit & Sen 2002 Szzeesvári & Smart 2004 Melo et al.] 2008 Maei et al. 2010). While meritous and insightful, the referred works were not only restricted to the linear function approximation case but also assumed the data was particularly well-aligned with specific distributions (Melo et al. 2008).
More recently. Q-learning was attributed finite-time error bounds when certain fixed behavior poli- cies are used Chen et al. (2019). Such policies are scarce or may not even exist as the number of features grows. Finite-time time error bounds for Adaptive Dynamic Programming methods Bertsekas & Tsitsiklis (1995). including Fitted Q-iteration (FQI) Ernst et al. (2005), assume not only the real- izability of the optimal Q-function but also closedness under Bellman update (Szzpesvári Munos 2005). Such conditions have been discussed in a recent work Chen & Jiang (2019).
The problem of divergence of Q-learning with function approximation was revived after a significant empirical success story of the use of Q-learning with deep neural networks (Mnih et al. 2015), where the function approximation setting is non-linear and the features are non-stationary. One of the components of the renowned deep Q-newwork (DQN) is target network that mitigates the negative impact of bootstrapping, i.e., of the stochastic semi-gradient update.
The works of Carvalho et al. (2020); [Zhang et al. (2021); Chen et al. (2022) provided theoretical in- sights and convergence guarantees for Q-learning with the target network. There is also work point- ing out that regularization of the Q-values the parameters themselves
stabilize Q-learning. resulting in a convergent algorithm (Zhang et al. 202T Carvalho et al. 2020) Lim et al., 2022 All these works applicable the linear function approximation case, merely. In the case of lin- car function approximation, the features are assumed to be stationary and known prior to learning. The practical applications of reinforcement learning, however, are moving in the opposite direc- tion, where the features are also learned. Additionally, such learning setting is, typically, non-linear. Consequently, the gap between theory and practice remains significant.
For the case of non-linear function approximation, recent work suggests loss function that is decreasing over time, assuming the neural network converges to the targets from a target network at each step (Wang & Ueda 2021). Finally, Xu & Gu (2020) provide finite-time result for Q- learning with aver-parameterized neural networks. While being an interesting result, as the size of the network grows infinity the learning architecture also grows closer to tabular representation.
6 CONCLUSION
In this work, we provided the first convergence result for a Q-learning scheme with non-linear non- stationary features without the use of target network. In our scheme, the final layer of network is updated faster than the hidden layers. We show that if the features converge, the final layer also converges. We complement our theoretical analysis with experiments showcasing our result. Finally, propose three schemes that result in guaranteed convergence of the features.
In the future, it would be relevant to compare experimentally the three learning schemes for the fea- tures considered, specifically unsupervised, semi-supervised and full-gradient reinforcement learn- ing. Additionally, it would be important to characterize the solutions obtained by each scheme.
REFERENCES
Konstantin E. Avrachenkov, Vivek S. Borkar, Hars P. Dolhare, and Kishor Patil. Full gradient dqn reinforcement learning: a provably convergent scheme. In Modern Trends in Controlled Stochastic Processes:, pp. 192-220. Springer, 2021.
Leemon Baird. Residual algorithms:
Reinforcement learning with function approximation. In Proceedings the 12th International Conference on Machine Learning, pp. 30-37, 1995.
Dimitri P Bertsekas and John N Tsitsiklis. Neuro-dynamic programming: overview. In Pro- ceedings of 1995 34th IEEE conference on decision and control, volume 1, pp. 560-564, IEEE, 1995.

---

Under review as a conference paper at ICLR 2023
Vivek Borkar. Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press, 2008.
Justin A. Boyan and Andrew W. Moore. Generalization in reinforcement learning: Safely approxi- mating the value function. In Advances in Neural Information Processing Systems 7, ppp 376, 1995.
Diogo S. Carvalho, Francisco S. Melo, and Pedro A. Santos. new convergent variant of q-learning with linear function approximation. Advances in Neural Information Processing Systems, 33: 19412-19421, 2020.
Jinglin Chen and Nan Jiang. Information-thhoreen considerations in batch reinforcement learning. In International Conference on Machine Learning, pp. 1042-1051. PMLR, 2019.
Zaiwei Chen, Sheng Zhang, Thinh T Doan, Siva Theja Maguluri, and John-Paul Clarke. Perfor- mance of q-learning with linear function approximation: Stability and finite-time analysis. arXiv preprint arXiv: /905. 1425, pp. 4, 2019.
7aiwei Chen, John Paul Clarke, and Siva Theja Maguluri. Target network and truncation overcome the deadly triad in q-leaming. arXiv preprint wxXi:2203300625 2022.
Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6, 2005.
Norm Ferns, Prakash Panangaden, and Doina Precup. Metries for finite markov decision processes. In Uncertainty in Artifial Intelligence, volume 4, pp. 162-169, 2004.
Norm Ferns, Prakash Panangaden, and Doina Precup. Bisimulation metrics for continuous markov decision processes. SIAM Journal on Computing, 1666:116 2011.
Geoffrey J. Gordon. Reinforcement learning with function approximation converges to region. In Advances in neural information processing systems, pp. 1040-1046, 2001.
Irina Higgins, Arka Pal, Andrei Rusu, Loic Matthey, Christopher Burgess, Alexander Pritzel, Matthew Botvinick, Charles Blundell, and Alexander Lerchner. Darla: Improving zero-shot trans- fer in reinforcement learning. In International Conference Machine Learning, pp. 1490-1490.
PMLR, 2017.
Diederik P. Kingma and Max Welling. Stochastic gradient vb and the variational auto-encoder. In Second International Conference on Learning Representations, ICLR, volume 19, pp. 121, 2014.
Sascha Lange, Martin Riedmiller, and Arne Voigtländer. Autonomous reinforcement learning on raw visual input data in a real world application. In The 2012 international joint conference on neural networks (IJCNN), pp. 1-8. IEEE, 2012.
Michael Laskin, Aravind Srinivas, and Pieter Abbeel. Curl: Contrastive unsupervised representa- tions for reinforcement learning. In International Conference on Machine Learning, pp. 5639- 5650. PMLR, 2020.
Han-Dong Lim, Do Wan Kim, and Donghwan Lee. arXiv:2202.05404 2022.
arXiv preprint Regularized q-learning.
Cheng-Yuan Liou, Wei-Chen Cheng, Jiun Wei-Wei Liou, and Daw-Ran Liou. Autoencoder for words. Neurocomputing, 139:84-96, 2014.
Hamid Reza Maei, Csaba Szepesvári, Shalabh Bhatnagar, and Richard S. Sutton. Toward off-policy learning control with function approximation. In International Conference Machine Learning, 2010.
Francisco S. Melo, Sean P. Meyn, and M. Isabel Ribeiro. An analysis of reinforcement learning with function approximation. In Proceedings of the 25th international conference on Machine learning, pp. 664, 2008.
10

---

Under review as a conference paper at ICLR 2023
Panayotis Mertikopoulos, Nadav Hallak, Ali Kavis, and Volkan Cevher, On the almost sure vergence stochastic gradient descent in non-convex problems. H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 1117-1122 1128. Curran Associates, Inc., 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, nature, 518(7540):529-5333 2015.
Dirk Ormoneit and Šaunak Sen. Kernel-baeed reinforcement learning. 161-178, 2002.
Machine learning, 49(2):
Martin L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2005.
Satinder Singh, Tommi Jaakkola, and Michael Jordan. Reinforcement learning with soft state ag- gregation. Advances in neural information processing systems, 1994.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Csaba Szepesvári and Rémi Munos. Finite time bounds for sampling based fitted value iteration. In Proceedings of the 22nd international conference Machine learning, pp. 880-887, 2005.
Csaba Szepesvári and William D Smart. interpolation-baseee q-learning. In Proceedings of the !wenty-first international conference on Machine learning, pp. 100, 2004.
John Tsitsiklis and Benjamin Van Roy. Analysis of temporal-diffferene learning with function approximation. Advances in neural information processing systems, 9, 1996.
John Tsitsiklis and Benjamin Van Roy. Feature-based methods for large scale dynamic program- ming. Machine Learning, 22:59-94, 1996.
Hado van Hasselt, Yotam Doron, Florian Strub, Matteo Hessel, Nicolas Sonnerat, and Joseph Mo- dayil. Deep reinforcement learning and the deadly triad. CoRR, abs/18 812.02648, 2018.
Zhikang T. Wang and Masahito Ueda. A convergent and efficient deep network algorithm. arXiv preprint arXiv:2106. 15419, 2021.
Christopher Watkins and Peter Dayan. Q-learning. Machine learning, 8(3):279 292, 1992.
Pan Xu and Quanquan Gu. A linite-time analysis q-learning with neural network function ap- proximation. In International Conference Machine Learning, pp. 10555-10565, PMLR, 2020.
Amy Zhang, Rowan McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. Learning invariant representations for reinforcement learning without reconstruction. arXiv preprint arXiv:2006.10742 2020.
Shangtong Zhang, Hengshuai Yao, and Shimon Whiteson. Breaking the deadly triad with target network. In International Conference Machine Learning, pp. 12621-12631. PMLR, 2021.


Reviews:
[{"review_id": "PA7caJLOhz5", "reviewer": "Reviewer_J62D", "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 studies Q-learning with neural network approximation and proposes a two-layer regularized Q-learning algorithm. The algorithm can be viewed as an extension of Q-learning with linear function approximation, where an additional layer is used to learn the features. The authors show asymptotic convergence of the proposed algorithm using the ODE approach. Numerical simulations were performed on a well-known divergent example of vanilla Q-learning, on which the proposed algorithm is stable.", "summary_of_the_review": "Since the designed algorithm (which can be viewed as an extension to (Zhang et al. 2021), (Lim et al. 2022)) suffers from the same limitations as in (Zhang et al. 2021), (Lim et al. 2022), and the technical contribution is incremental, I do not recommend this paper being accepted by ICLR.", "strength_and_weaknesses": "While the writing and the exposition are clear, there are many limitations of this work, as elaborated below.\n\n(1) Compared to using linear function approximation, the two-layer neural network approximation enables the agent to also update the features. Therefore, one should expect the function approximation error to be smaller than simply using linear function approximation. In my point of view, this is the main advantage of using two-layer neural network, and is the motivation of this work. However, in view of Theorem 2, this advantage is not theoretically clear. In particular, it is not clear if the function approximation error $||Q^*-\\Phi_{u^*}Q^*||$ is smaller compared to using linear function approximation where the features are fixed.\n\n(2) This paper follows the regularization framework proposed in (Zhang et al. 2021) and (Lim et al. 2022). However, it was discussed in a recent work (Chen et al. 2022) Appendix E that the regularization technique proposed in (Zhang et al. 2021) is to stabilize Q-learning by changing the problem discount factor to a smaller one. This is the reason that their algorithm does not converge to $Q^*$ even in the tabular setting. Similar issue is present in (Lim et al. 2022) too. Since this paper follows that regularization framework, it has the same issue. To see this, the second and the third term on the right-hand side of Theorem 2 Eq. (4) do not vanish even in the tabular setting, suggesting that the MDP problem is no longer the original one. While this is a limitation in previous papers, since this paper follows the same framework, the validity of the algorithm design is unclear.\n\n(3) As a follow-up concern to (2), since introducing the regularization parameter is equivalent to reducing the MDP discount factor, and it is well-known that small discount factor leads to convergence of Q-learning with linear function approximation, the numerical simulations are not surprising. Also, since DQN (Mnih et al., 2015) is known to be successful, and the authors propose a different DQN scheme, it may be a good idea to compare the empirical performance of the proposed algorithm to that of DQN (Mnih et al., 2015).\n\n(4) Both the regularization parameters $\\zeta$ and $\\epsilon$, and the projection radius $\\rho$ depend on the unknown parameter $\\sigma$. Therefore, it is unclear how to implement this algorithm in practice.\n\n(5) The technical contribution is incremental because (i) using regularization to overcome divergence is readily established in the literature, (ii) the convergence of the slower time-scale follows from existing literature on SGD, and (iii) the convergence of the faster time-scale follows from the ODE framework.\n\n\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": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "HvQ-BSOXg6", "reviewer": "Reviewer_gATf", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 studies the convergence of a regularized Q learning algorithm and the features are learned from a nonlinear approximation. The features are updated much slower than the $Q$ function parameter. The authors prove that the proposed regularized Q-learning converges as long as the feature learning scheme converges and other conditions hold. Empirical results are provided to show that the proposed algorithm can converge while Q-learning diverges in some problems.\n", "summary_of_the_review": "For Definition 1, it is unclear why there are two regularization parameters in the update. In particular, what is the role of $\\xi$? It is clear that when $\\xi=1$, the regularization disappears. But what happens with a very small or large $\\xi$? Maybe the authors should motivate this regularization in the loss function before presenting it in the update rules. \n\nWhat is $\\rho$ in Definition 1?\n\nThe result in Theorem 1 is somewhat weak since it only holds asymptotically. In practice, the convergence could be impacted heavily by the approximation of the feature learning at each step, which is now assumed to converge in Assumption 1. \n\nTherefore, the theoretical novelty is limited given that the results are also much weaker though the authors try to solve a harder problem than existing work for Q-learning with linear function approximation. \n", "strength_and_weaknesses": "I think the problem studied here is very interesting, especially the investigation of when Q learning diverges and how to remedy it. The experimental results are a good illustration of such a goal. However, the motivation for the particular regularization is not clear. There is no sufficient discussion on how the regularization is designed and what happens when the regularization deviates from 0. The theoretical analysis in this paper seems to be sloppy and does not address the convergence of the proposed algorithm as claimed.\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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "D9BM0WkYZY", "reviewer": "Reviewer_5r8F", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 proposed a new scheme of deep Q-learning by introducing final layer regularization and then updates it along faster time-scale than that of the non-linear features. Moreover, it provably converges even when the  features are non-stationary. A bound is also derived on the error introduced by regularization. ", "summary_of_the_review": "Generally this is a good and rigorous paper on evaluating the convergence of deep Q-learning with non-stationary features. A new scheme is proposed and a following proof is given to show its convergence under some assumptions. My only concern is a lack of discussions of the generalization results for other settings apart from the three considered in current paper, i.e., a discussion of limitations and useful insights are suggested.  ", "strength_and_weaknesses": "Strength:\n\n1. The paper propose a novel scheme for deep Q-learning with non-stationary features and rigorously proved that it converges. \n\n2. Three settings are considered under which the features converge. \n\n3. Numerical results support the theoretical analysis. \n\nWeakness:\n\n1. A lack of (empirical) verification of the obtained bound. \n2. Three settings with feature convergence are considered. How about other cases? It is suggested to add some discussions and/or limitations of the current results. ", "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": {}}]

Author rebuttal:

Decision: Reject