Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximation
Authors: GUOJUN XIONG
Jian Li
Venue: NeurIPS 2023 poster (2023)
Keywords: Restless bandits
Whittle index policy
Q-learning
Two-timescale stochastic approximation
Neural network function approximation

Abstract: Whittle index policy is a heuristic to the intractable restless multi-armed bandits (RMAB) problem. Although it is provably asymptotically optimal, finding Whittle indices remains difficult.  In this paper, we present Neural-Q-Whittle, a Whittle index based Q-learning algorithm for RMAB with neural network function approximation, which is an example of  nonlinear two-timescale stochastic approximation with Q-function values updated on a faster timescale and Whittle indices on a slower timescale.  Despite the empirical success of deep Q-learning, the non-asymptotic convergence rate of Neural-Q-Whittle, which couples neural networks with two-timescale Q-learning largely remains unclear.  This paper provides a finite-time analysis of Neural-Q-Whittle, where data are generated from a Markov chain, and Q-function is approximated by a ReLU neural network. Our analysis leverages a Lyapunov drift approach to capture the evolution of two coupled parameters, and the nonlinearity in value function approximation further requires us to characterize the approximation error.  Combing these provide Neural-Q-Whittle  with $\mathcal{O}(1/k^{2/3})$ convergence rate, where $k$ is the number of iterations.

Finite-Time Analysis of Whittle Index based Q- Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximation
Guojun Xiong, Jian Li Stony Brook University
[guojun. xiong, jian. 1i. (1..)@sttonybbook edu
Abstract
Whittle index policy is heuristic the intractable restless multi-armed bandits (RMAB) problem. Although is provably asymptotically optimal, finding Whittle indices remains difficult. In this paper, present index based Q-learning algorithm for RMAB with neural network function approx- imation, which is example of nonlinear woottimescale stochastic approximation with Q-function values updated on a faster timescale and Whittle indices on a slower timescale. Despite the empirical success of deep Q-learning, the non-asymptotic convergence rate of Neural-Q-Whitel
Whittle
which couples neural networks with two-timescale Q-learning largely remains unclear. This paper provides finite-time where data are generated from a Markov chain,
analysis of and Q-function is approximated by ReLU neural network. Our analysis leverages a Lyapunov drift approach to capture the evolution of two coupled parameters, and the nonlinearity value function approximation further requires to charac- terize the approximation error. Combing these provide Neural-Q- Boural-Q-Whis Whittle with O 011/k2/33 convergence rate, where & is the number of iterations.
Introduction
We consider the restless multi-armed bandits (RMAB) problem [56). where the decision maker (DM) repeatedly activates K out of N arms at each decision epoch. Each arm is described by Markov decision process (MDP) [5). and evolves stochastically according to two different transition
kernels, depending on whether the arm is activated or not. Rewards are generated with each transition.
Although RMAB has been widely used to study constrained sequential decision making problems
5
38
64
36 35 25 is notoriously intractable due to the explosion of state space [44]. A
celebrated heuristic is the Whittle index policy (56), which computes the Whittle index for each arm given its current state as the cost to pull the arm. Whittle index policy then activates the K highest indexed arms at each decision epoch, and is provably asymptotically optimal [54].
However, the computation Whittle index requires full knowledge of the underlying MDP associated with each arm, which is often unavailable in practice. To this end, many recent efforts have focused on learning Whittle indices for making decisions an online manner. First, model-free reinforcement learning (RL) solutions have been proposed IIO
23 53
28
57
59 61 58 31 among which
B developed a Whittle index based Q-learning algorithm, which we call Q Whittle for ease of exposition, and provided the first-ever rigorous asymptotic analysis. However, Q-Whittle suffers from slow convergence since only updates the Whittle index of a specific state when that state is visited. In addition, q-Whittle needs to store the Q-function values for all state-action pairs, which limits its applicability only to problems with small state space. Second, deep RL. methods have been leveraged to predict Whittle indices via training neural networks 40 41). Though
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

these methods are capable of dealing with large state space. there is no asymptotic or finite-time performance guarantee. Furthermore, training neural networks requires tuning typer-parameters. This introduces an additional layer of complexity to predict Whittle indices. Third, to address aforementioned deficiencies, [60] proposed Q-Whittle-LFA by coupling Q-Whittle with linear function approximation and provided a finite-time convergence analysis. One key limitation of q-Whittle-Läe is the unrealistic assumption that all data used in Q-Whittle- are sampled i.i.d.
from fixed stationary distribution.
To tackle the aforementioned limitations and inspired by the empirical success of deep Q-learning in numerous applications, we develop Neural- ---attt--ettteee Whittle index based Q-learning algorithm with neural network function approximation under Markovian observations. Like [ 60), the updates of Q-function values and Whittle indices form a two-timescale stochastic approximation (2TSA) with the former operating on a faster timescale and the later on slower timescale. Unlike A 60 our uses deep neural network with the ReI.U activation function to approximate the Q-function. However, Q-learning with neural network function approximation can in general diverge (2). and the theoretical convergence of Q-learning with neural network function approximation has been limited to special cases such as fitted Q-iteration with i.i.d. observations [22], which fails to capture the practical setting of Q-learning with neural network function approximation.
In this paper, we study the non-asympiotic convergence of Neural-Q -Whitttle with data generated from a Markov decision process. Compared with recent theoretical works for Q-learming with neural network function approximation [
62]. our Neural-Q-Whittle Whittle involves a two-timescale update between two coupled parameters, i.e., Q-function values and Whittle indices. This renders existing finite-time analysis
22
due to the fact that [13 22 62) only contains a single-timescale update on Q-function values. Furthermore,
[13
22 not applicable to our Neural-Q-Whithe
[3 12 62 required an additional projection step for the update parameters of neural network function as guarantee the boundedness between the unknown parameter any time step with the initialization. This in some cases is impractical. Hence, a natural question that arises is
Is it possible to provide a non-asympiotic convergence rate analysis of Neural- Sooral---Whiteee W-Whittle with two coupled parameters updated in two timescales under Markovian observations without the extra projection step?
The theoretical convergence guarantee of two-timescale Q-learning with neural network function approximation under Markovian observations remains largely an open problem, and in this paper, we provide an affirmative answer to this question. Our main contributions are summarized as follows:
We propose Neural-Q -Whittle,, a novel Whittle index based Q-learning algorithm with neural network function approximation for RMAB. Inspired by recent work on TD learning (48] and Q- learning [15] with linear function approximation, our Neural-q-Whitte removes the additional impractical projection step in the neural network function parameter update.
We establish the first finite-time analysis of Neural Neural-Q-Whitt.. under Markovian observations. Due to the two-timescale nature for the updates of two coupled parameters (i.e., Q-function values and Whittle indices) in Neural-Q-Wi: ttle, we focus on the convergence rate of these parameters rather than the convergence rate of approximated Q-functions in [1] 22 62). Our key technique is to view Neural-Q Quttt----itteee as a 2TSA for finding the solution of suitable nonlinear equations. Different from recent works on finite-time analysis of a general 2TSA 20 with linear function approximation [60]. the nonlinear parameterization of Q-function in Beural-Q-Whin Markovian observations imposes significant difficulty in finding the global optimum of the corre- sponding nonlinear equations. To mitigate this, we first approximate the original neural network function with collection of local linearization and focus on finding surrogate Q-function in the neural network function class that well approximates the optimum. Our finite-time analysis then requires to consider two Lyapunov functions that carefully characterize the coupling between iterates of Q-function values and Whittle indices, with one Lyapunov function defined with respect to the true neural network function, and the other defined with respect to the locally linearized neural network function. We then characterize the errors between these two Lyapunov functions. Putting them together, we prove that SourallQ-Whicee (1 /2/2233), where & is the number of iterations.
under
achieves a convergence in expectation at a rate
Finally, we conduct experiments to validate the convergence performance of Neural Neural-Q-Whittle, and verify the sufficiency of our proposed condition for the stability of Shural-Q-Whittll.

---

2 Preliminaries
RMAB. We consider an infinite-horizon average-reward RMAB with each arm E W described by a unichain MDP [45) M, == (S,A, Pa, rn), where S is the state space with cardinality S < co, A the action space with cardinality A. Pr. (n(s"|s, a) is the transition probability reaching state s' by taking action a in state 8, and (s, a) is the reward associated with state-action pair (s, a). At each time slot the DM activates K out of N arms. Arm n is "active" at time when it is activated, i.e., An (t) 1; otherwise, arm n. is "passive", A,, = 0. Let II be the set of all possible policies for RMAB, and is feasible policy, satisfying π : Fr H AN, where F, the agma-algebre generated by random variables (h), (n))) Vn E NN, h < t). The objective of the DM is to maximize the expected long-term average reward subject to an instantaneous constraint that only K arms can be activated at each time slot, i.e.
1 T
RMAB:
max FEll
lim T-x0
Ex
(2(())
S.L. Σ Ax) K, Vt.
(1)
(=0 n=
Whittle Index Policy. It is well known that RMAB ① suffers from the curse of dimensionality 44 To address this challenge, Whittle [56] proposed an index policy through decomposition. Specifically, Whittle relaxed the constraint in (T) be satisfied on average and obtained a unconstrained prob-
lem: max lim inf Er Ei Ex (t) + X(1 A, (t)),. where the Lagrangian multiplier associated with the constraint. The key observation of Whittle is that this problem can be decomposed and its solution is obtained by combining solutions of N independent problems via solving the associated dynamic programming (DP): (8) (0.1 Qn a), Vn E N, where
(n(o,a)+3=a(rnll0) 1onddd (ra(s.a)+ + > P. Pn
Pn
(2)
where 3 is unique and equals to the maximal long-term average reward of the unichain MDP, and
V,, is unique up to additive constant, both of which depend the Lagrangian multiplier X. The optimal decision a" in state s then is the one which maximizes the right hand side of the above DP. The Whittle index associated with state s defined as the value X₃ (s) E R such that actions 0 and 1
are equally favorable in state s for arm n B 23], satisfying
(s) = r.,ss, + Σ Pn (s (s), (s(s, -p
(3)
Whittle index policy then activates K arms with the largest Whittle indices at each time slot. Addi- tional discussions are provided in Section Bi supplementary materials.
Q-Learning for Whittle Index. Since the underlying MDPs are often unknown, 3 proposed Q-Whittle, a tabular Whittle index based Q-learning algorithm, where the updates of Q-function values and Whittle indices form a 2TSA, with the former operating on a faster timescale for a given An and the later on slower timescale. Specifically, the Q-function values for Vn A/ are updated as
Qu.+1 a) = Qn,k(s, a) + an,k 1 (Sm.=s,A,,A=a) (rn(s.a) + +(1 a))nn.
+ max (S (Qk)) - Qn)()))))
where (n((u)= E term average MDP setting M. which differs significantly from the discounted reward setting 45
Eses(Qu.kt
Qn,K(s, (8, 1)) is standard in the relative Q-learning for long-
{ar,,k } is step-size sequence satisfying En On, co and Σx oz n k oc.
Accordingly, the Whittle index is updated as
(s) = (s) + Tn. Tm. ( 1) (s,
(5)
with the step-size sequence } satisfying Σσ Mn.k 00, Σx V/ and 7h. k()
The coupled iterates (4) and (5) form 2TSA, and 3 provided an asymptotic convergence analysis.
3 Neural Q-Learning for Whittle Index
closer look at (5) reveals that Q- Q-Whittle only updates the Whittle index of specific state when that state is visited. This makes g-Whittle suffers from slow convergence. In addition, Q-Whittle
3

---

Algorithm I Neural-Q-Whitt-e Neural Q-Learning for Whittle Index
1: Input: (s),a) for Vs E, A, and learning rates (a J.......T fnEJE-1.....?
2: Initialization: b, Unif( -1,, 1)), Wr.0 ~ N (0, Ia/d), Vr E [1, and 1(8) = 0, V/ E
3: for E do
4: for == ,...., , do
5: Sample (Sk, As, S4+1) according to the e-greedy policy;
6: Ax=r(S Ax) + +(1 (s))) + max, f(0:: ((0: -(0))
As)):
7: 0x+1 = 02 + a fo o (Sk, At));
8: Ak+1(s) (s) = (s) + m ( ( 1)) 0(0x:0(s.00
9: end for
10:
end for
11: Return: Vss)
needs to store the Q-function values for all state-action pairs, which limits its applicability only to problems with small state space. To address this challenge and inspired by the empirical success of deep Q-learning, we develop Neural-q-Whittil network function approximation by using low-dimensional feature mapping and leveraging the strong representation power of neural networks. For ease of presentation, we drop the subscript in (4) and (5), and discussions in the rest of the paper apply to any arm n N.
through coupling Q-Whittle with neural
Specifically, given set of basis functions de S A + R = I, dd with d < SA the approximation of Q-function Qo a) parameterized by a unknown weight vector 0 E Rnd is given by Qo a) f(0; ((s,))) a)), Vs E S,a E A, where f is nonlinear neural network function parameterized by 0 and ((s, a). with ((s, = (01 a). (d)(s,))) The feature vectors are assumed to be linearly independent and are normalized that ( a)ll s 1, Ys S, E A. In
particular, we parameterize the Q-function by using a two-layer neural network 13 62
[(0:0(s;a))
(6)
Vm
where 0 = (bi....,lue bm, wT w...... WT m with by E TR and w, E Rdx1 Vr E [1,m]. by Vr are uniformly initialized in 11 and wr, Vr initialized according to ( La/d). During training process, only w,, Yr are updated while b,, vr are fixed as the random initialization. Hence, use and w,, Vr interchangeably throughout this paper. a (x) = max(0, x) is the rectified linear unit (ReLU) activation functior
zero Gaussian distribution
Given 6 can rewrite the Q-function value updates in
0 02. + aa. Vos ((L,, Ax)),
with A. being the temporal difference (TD) error defined as A == r(S,, Ag) + +1 (1-4,)Ax6
I(Ox) + max, [(0x; 1 a)) - (0 (Sx,, Ax)), where 1(Ox) 25 Eves E.ess
f(0,: ((s 1))]. Similarly, the Whittle index update (5) can be rewritten
(++1(s) = (s) + Ty (f((:: ((s 1)) f0x: ((s)0))).
(8)
The coupled iterates in 7 and K form
as summarized in Algorithm T which aims learn the coupled parameters (0", (0", (s)) such that f(0 6(s, 1)) f(0", 0(s 0)), Vs E S.
Remark 1. Unlike recent works for Q-learning with linear 16 37 67 neural network function approximations (13) 222 662V. we do not assume an additional projection step of the updates of unknown parameters 02 in to confine Oz. Yk into bounded set. This projection step is often used to stabilize the iterates related to the unknown stationary distribution of the underlying Markov chain, which in some cases is impractical. More recently, [48] removed the extra projection step and established the fimite-time convergence of TD learning. which is treated as a linear stochastic approximation algorithm. [15] extended it to the Q-learning with linear function approximation.
and references therein focuses on the ReLU activation function, as it has certain properties that make the analysis tractable. ReLU is piecewise linear and non saturating, which can simplify the mathematical analysis. Applying the same analysis to other activation functions like the hyperbolic tangent (tanh) could be more complex, which is out of the scope of this work.
'The finite- siite-time analysis of Deep Q-Networks (DQN) 13

---

Table 1: Comparison of settings in related works.
Algorithm
Noise
Approximation
Timescale
Whittle index
Q q-Whittle
L... Lid.
two-timescale
q-Whittle-La
60
linear
two-timescale
/
(-Learning-LFa
6
37
67
Markovian
lincar neural network
single-timeseat
X
O-Leerning-NNA
[33
15
22
62
Markovian
single-timescale
X
ID-Learning-_FA
48
Markovian Li.d
linear
single-timescale
2TSA-IID
[9
21
two-timescale
2TSA- Markkvian
20
Markovian
two-timescale
Neural-Q-Whitte (this work)
Markovian
neural network
two-timescale
However, these state-of-the-ar works only contained a single-timescale update on Q-function values, ie., with the only unknown parameter while our Neural -Q- Whit th involves two-timescale update between two coupled unknown parameters 0 and X in 7 and [ Our goal in this paper is to expand the frontier by providing a finite-time bound for Neural Q- &h ittee under Markovian noise without requiring additional projection step. We summarize the differences between our work and existing literature in Table
Finite-Time Analysis of Neural-q-Whittl.
In this section, we present the finite-time analysis of Boural-Q-Whitee for learning Whittle index X(s) any state 8 when data are generated from a MDP. To simplify notation, we abbreviate
((s) as À in the rest of the paper. We start by first rewriting the updates of Booural-QWhitter in (7)
and (8) as a nonlinear two-timescale stochastic approximation (2TSA) in Section 4.1
4.1 A Nonlinear 2TSA Formulation with Neural Network Function
We first show that Neural --hiittteee can be rewritten variant of the nonlinear 2TSA. For any fixed policy since the state of each arm {Sx} evolves according to a Markov chain, we can construct new variable X (Sk, Ag, Sk+1), which also forms Markov chain with state space
X' = {(s, a, [s Is E S, sa)ss) 2 O, p(s'|s [s. a) >> 0}. Therefore, the coupled updates and of Neural -----QQ-hhht Whittle can be rewritten in the form of a nonlinear 2TSA (0):
p = 0x + anh Xx. Ox, AR),
AR+1 d + nag X1. K 0R, A&),
(9)
where Og and A being arbitrarily initialized in mgd and R. respectively; and h(-) and g(-) satisfy
h(X2, Os. Ax) Vof(0u: Ax)) g O(xx Ax) = (0x: ((s 1)) - 0((:: 0)),
Ox E R A E R,
(10)
Og E Rmdd
(11)
Since тi Okk the dynamics of 0 evolves much faster than those of X. We aim establish the finite-time performance of the nonlinear 2TSA in g where f(-) is the neural network function
defined in (6). This is equivalent find the rool X²) of a system with two coupled nonlinear equations X x Rond x R Rend and X
R md R IR such that
H E, [ 0, A) O, G A) = Ex = 0,
(12)
where is random variable in finite state space X with unknown distribution μ.. For a fixed 0, to study the stability of X, assume the condition on the existence of a mapping such that y(0) is the unique solution of G(0, 0. In particular, y(0 is given as
(0) r(,,1)+ Σ (1)1ss,1) max /(0: a)) ((,00) - Ep(s'(s,0) max f(0; (0: a)). (13)
"The root (0" ) of the nonlinear 2TSA
can be established by using the ODE method following the
solution of suitably defined differential equations 9 49 19 20 i.e., è H A), = G)(,,)), where fixed stepsize is assumed for ease of expression at this moment.
5

---

4.2 Main Results
As inspired by (20). the finite-time analysis of such nonlinear 2TSA boils down to the choice of two step sizes {ak. 77k, vk} and Lyapunov function that couples the two iterates in (9). To this end, we first define the following two error terms:
0₂ = 02 0- A - ~v(O)))
(14)
which characterize the coupling between 0% and λs. If 0x and ds go to zero simultancously, the convergence of (0s, )x) to (0", X*) can be established. Thus, to prove the convergence of (0x, As) of the nonlinear 2TSA in (9) to its true value (0", X*), can equivalently study the convergence of
(0s, Xx) by providing the finite-time analysis for the mean squared error generated by (9). To couple
the fast and slow iterates, we define the following weighted Lyapunov function
M(Ox, Axe) = 1/k 0 2 + 1| aak
Ti 00 11 + |A - v(0x))l
(15)
where -|- stands for the the Euclidean norm for vectors throughout the paper. It is clear that the Lyapunov function M (0k: Ax) combines the updates of f and with respect to the true neural network function [(0 (0,, a)) in 6
To this end, our goal turns characterize finite-time convergence of (0, >x)]. However, it is challenging to directly finding the global optimum of the corresponding nonlinear equations due to the nonlinear parameterization of O-function in Boural-Q-Whiteee
In addition, the operators h()))g()) and y--) in (10). (1I) and (13) directly relate with the convoluted neural network function f00: a)) in 66. which hinders us characterize the smoothness properties of theses operators.
Such properties are often required for the analysis of stochastic approximation [TS] 19 21).
To mitigate this, (Step 1) we instead approximate the true neural network function f(0, (s,, a)) with collection of local linearization fo(0; (s,, a)) at the initial point 0n. Based on the surrogate stationary point 0g of f a)), we correspondingly define a modified Lyapunov function M (0x, 10g.AA) A&) combining updates of f and À with respect to such local linearization. Specifically, we have
i (0 Av) =
Te
100 0/1l + | yo (0
(16)
O
where yo(-) is in the same expression as (-) in 13 by replacing (-) with fo(.), and we will describe this in details below. (Step 2) We then study the convergence rate of the nonlinear 2TSA using this modified I. Lyapunov function under general conditions. (Step 3) Finally, since the two coupled parameters 0 and À in (9) are updated with respect to the true neural network function f(0 ((s, a)) while we characterize their convergence using the approximated
in (6) in Heural-Q-Whitt.l neural network function in Step 2. Hence, this further requires us to characterize the approximation errors. We visualize the above three steps in Figure [ and provide proof sketch in Section 4.3 Combing them together gives rise our main theoretical results on the finite-time performance of Neural- Q- Whittle, which is formally stated in the following theorem.
Theorem 1. Consider iterates { and {)k} generated by Neural Whetttee in and ( 70 (k+1)173, we have for vk 2
Given 0g- (k+1) 17
2 2+2R[N X+)1
1200gg (C1 + [0611) + (2C1 + 1|Aol1)2
E[M (0 +1, FF
(I: (1++1)² 1)2
nu
(A: + 1)2/3
2
2
11ol+113 (|0ol++|ao|+1))
(1)0
+ 01 - x2) (==
+ (k: + 1)2/8 +2
o
(17)
m²/2
where C1 := c1 (10o|l + | 1)) with e1 being a proper chosen constant, Co is a constant defined in Assumption ] T is the mixing time defined in (22). span denotes for the span semi-norm (47) and
II represents the projection to the set of F contianing all possible fo(0: ((s, a)) 18)
The first term on the right hand side 17 corresponds to the bias compared to the Lyapunov function at the mixing time r. which goes to zero at a rate (1)k22). The second term corresponds to the accumulated estimation error of the nonlinear 2TSA due to Markovian noise, which vanishes at the rate O(1 /1.233. Hence it dominates the overall convergence rate in (7). The third term captures the distance between the optimal solution (0", X²) to the true neural network function f(0;; ((s, a)) in

---

Equivvlent to 2TSA in 69)
Lyapenox if Asi in (15) war. true neural function (()
0ul2 81 Kg Av.
Neurak-0 Q- bittle Update in (7)-10) true neural function [(]
Aze1 de + noat No. Pe.
Theoran Cunvergence rale of M.
Gap Ri) fu6e)
Surrogate y in Detinittion
Local Innourization of AG [ fof-)
Lyapumov func. Kri6.. Asi in (16) w.rl local limouriee tzed neural function
Throrem 2: E Convergence rale of XriBg.hul Ak)
Auf-..00 - 90(-)
Step
Step 2
Step
Figure 1: Neural-O-Whittll operates w.r.t. true neural function f'() with its finite-time perfor- mance given in Theorem [
(indicated in dashed lines). Our proofs operate in three steps: (i) Step I: Obtain local linearization f-) and define Lyapunov function (-) w.r.t fo(-). (ii) Step 2: Character- ize the finite-time performance w.r.t. (-) using Lyapunov drift method. Since Houral---Whit.le is updated w.r.t. f(.), we need to characterize the gap between f(.) and fo(-). (iii) Step 3: Similarly, we characterize the approximation errors between (.) and (.).
(6) and the optimal one (0): Yo (0j)) with local linearization fu (5s, a)) in 18 which quantifies the error when f(0)) does not fall into the function class F. The last term characterizes the distance between f0:;; Ø(s, a)) and fo(O;; Φ(s, a)) with any 0,. Both terms diminish as m - oc. Theorem I Timplies the convergence to the optimal value (0* " is bounded by the approximation error, which will diminish to zero as representation power of fo ((s, a)) increases when
oc. Finally, we note that the right hand side (1) ends up in O01 (1/) + ((1/k2/3) + c, where e is a constant and its value goes to as m - co. This indicates the error bounds of linearization with the original neural network functions are controlled by the overparameterriattoo value of m. Need to mention that a constant step size will result in a non-vanishing accumulated error as in [15.
Remark 2. A finite-time analysis of nonlinear 2TSA was presented in [39]. However, (39] required
a stability condition that lim (0k, Ax) = (0*,) )²), and both h and are locally approximated
as linear functions. [79 60] relaxed these conditions and provided a finite-time analysis under i.i.d.
noise. These results were later extended to Markovian noise (20) under the assumption that H function is strongly monotone in I and G function is strongly monotone in X. Since (20) leveraged the techniques in [19], needed to explicitly characterize the covariance between the error caused by Markovian noise and the paramelers' residual error in (T4), leading to the convergence analysis much more intrinsic. (15) exploited the mixing time to avoid the covariance between the error caused by Markovian noise and the parameters' residual error, however, it only considered the single timescale Q-learning with linear function approximation. Though our Neural Q- Whitts tle can be rewritten as nonlinear 2TSA, the nonlinear parameterization of Q-function caused by the neural network function approximation makes the aforementioned analysis not directly applicable to ours and requires additional characterization as highlighted in Figure 7 The explicit characterization of approximation errors further disting gussi our work.
4.3
Proof Sketch
In this section, we sketch the proofs of the three steps shown in Figure | as required for Theorem I
4.3.1 Step 1: Approximated Solution of Veural-Q-Whitee
We first approximate the optimal solution by projecting the Q-function in (6) to some function classes parameterized by 0. The common choice of the projected function classes is the local linearization of
((0 a)) at the initial point 0 [3 62 i... = [fol ((,0) vo e θ}. where
1 m
fo (() a))
b, (w. (w a) > 0] (w. Σ r=1
(18)
Vm
Then, we define the approximate stationary point 0 with respect to so(O: Φ(s, a)) as follows.
Definition 1. /13 62)1 I A point 0; E 2 is said to be the approximate stationary point of Algorithm
for all feusible O E θ it holds that Ey,, [[ (A Vofo(0; ((x ((, 0% > 0, v0 E O with An = (r(s.)) a) + (1 a)X² (0) maxx' fo(0:((s' a)) 00 &s a))} where (0) =
28 Σ E.essfo00:00 0)) + fo 0 1))]
7

---

Though there is gap between the true neural function (6) and the approximated local lincarized function (8), the gap diminishes as the width of neural network i.e., m. becomes large [3] 62
With the approximated stationary point oū we can redefine the two error terms in 14 as
0. 0 0
d Ae y
(19)
using which we correspondingly define modified Lyapunov function M M A&) in 16 where yo(0) - = Σ (( 1) maxfo(00 (ss a)) -(s,0) - p(s max ((s), a)). (20)
4.3.2 Step 2: Convergence Rate of (0,,, Ax) in (6
Since approximate the true neural network function f0: Φ(s. in with the local linearized
function fo(0; ((, a)) in 18), the operators h(-) and g in 10 turn correspondingly to be
ho kx Ax) Vefo (SK,. Ax) Ak,0, (0(0)) fo (s. 1)) fo fo(0=:((s..)) 0)), (21) A (0x) + max, fo(O:: 0 (S
with 4k. r(Sk, A&)
(( Ax)).
Before we present the unite-time error bound of the nonlinear 2TSA (9) under Markovian noise, we first discuss the mixing time of the Markov chain {Xxa] and our assumptions.
Definition 2 (Mixing time 15 ). For any ō > 0, define Ta as
TB = min {k 2 [[E 0, = x] Ho A) S 5(110 6b1l + M| (066))))) (22)
Assumption 1. The Markov chain {Xx} } is irreducible and aperiodic. Hence, there exists a unique stationary distribution μ [32g, and constants C. > O and p E (0,1) such that drv (P(x x), S Cp², vk 2 0, x E X, where (..) is the total-variation (TV) distance [32].
Remark Assumption 7 is often assumed to study the asymptotic convergence of stochastic approximation under Markovian noise 4 9 [5V.
Lemma 1. The function ho! (X, 0, A) defined in (1 is globally Lipschitz continuous w.r.l 0 and X uniformly in X, i.e., [l X, 0,, A1) ho X, 02, A2)
Ln, || 02ll Ln,all>1 >2]|, VX X,
and L = 3, hn.2 = 1 are valid Lipschitz constants.
Lemma The function (0) defined
21 is linear and thus Lipschitz continuous in i.e. (l 90 (o(2))l 1|= S Lg 01 - 0211, and Lg is valid Lipschitz constant.
Lemma 3. The function (0) defined in 20 is linear and thus Lipschitz continuous in 0 i.e.
(0))(01) yo (02) S Lg, 02l1. and Ly 2 is valid Lipschitz constant.
Remark 4. The Lipschitz continuity of ho guarantees the existence of solution 0 to the ODE 0 for a fixed X, while the Lipschitz continuity of go and yo ensures the existence of a solution X to the ODE when is fixed. These lemmas often serve as assumptions when proving the convergence rate for
both linear and nonlinear 2TSA [37 39 78 24
19
17 27/.
Lemma 4. For a fixed X, there exists constant μl > O such that ho( defined in 10 satisfies
E (X, 0, A)] < --: -1110
For fixed 0, there exists constant #12 such that go 0 A) defined in satisfies
E[)gn(X,0, A)] < 12
Remark 5. Lemma 4 guarantees the stability and uniqueness of the solution 0 the ODE for the ODE X for fixed 0. This assumption can be
fixed X, and the uniqueness of the solution viewed as relaxation of the stronger monotone property of nonlinear mappings [19 [5), since it is automatically satisfied if h and g are strong monotone as assumed in 19).
Lemma 5. Under Assumption 7 and Lemma 7
there exist constants C > 0, P (0, and
L = max (3, maxx ho(X,6 0%), (o)) such that
T8 < log(1/5) log((2.Cmmi)
(1g(1/p)
8

---

Remark 6. is equivalent to the mixing time of the undertying Markov chain satisfying lims--o dTa [15.. For simplicity, we remove the subscript and denote as T.
We now present the finite-time error bound for the Lyapunov function (0x. Ax) in 16
Theorem 2. Consider iterates
{ and {Ax} generated by Newral -Q- Whith in 7 and (
Given Lemma
14 OKk (k+1) TBs (k+ (K+1)4773 C1 == C1 (0 + | || + 1) with constant CD
- 3 EM (0,,
600g (C1 + 10o11)² 2 + (2C) + +1AAo1)2
B[M d 1+
(k: + 1)2
17u
(A: + 1)2/3
c2(110
1/2
vk T. (23)
(k: + 1)2/3
4.3.3 Step 3: Approximation Error between M0,,, Ax)) and M0 Ave)
Finally, we characterize the approximation error between Lyapunov functions M As) and dealing with long-term average MDP, assume that the total varia-
(0,, Ag). Since tion of the MDP is bounded [47]
Assumption 2. There exists < K < such that (s,a) aa) (lp(-)s,a) - p(1ss' d = 2xc.
Hence, the Bellman operator is a span-contraction operator 47), i.e,
span S fo - T ((0))) S K span(fo(0%) f(0))).
(24)
Assumption 3. 100 11 - co span (Jo(8)) f(0'))ll, with co being a positive constant.
Lemma 6. For M (0x, Ax) in 15 and (0x, Ax) in 16). with constants eı and co (Assumption
2
(1100lll || + Aol + 11)
M(,,, < (0, +x)+
ax R1-
1/2
Numerical Experiments
We numerically evaluate the performance of Neural Meural-Q-Whittin --Whittlee using an example of circulant
dynamics 23 3 8. The state space is S = {1, 3, 4J. Rewards are r(1,a) a) r1, a)
r(3, .) O, and r r(4 a) 1 for a E {0, 1}. The dynamics of states are circulant and defined as
0.5
0.5
0
0
T0.
0
0
0.57
pl_
0
0.5
0.5
0
and po
0.5
0.5
0
0
0
0.5
0.5
0.5
0.5
0.5
0
0.5
0 0
0.5
0.5
This indicates that the process either remains in its current state or increments if it is active (i.e., a 1), it either remains the current state or decrements if it is passive (i.e., a 0). The exact
value of Whittle indices (23 are X(1) = -.5,, X(2) = 0.5, X(3) = 1, and X(4) -1
In our experiments, we set the learn- ing rates as Ogk = 0.5/(k + 1) and m = 0.1 1) We use e-greedy for the exploration and exploitation tradeoff with = 0.5. We consider two-layer neural network with the number of neurons in the hidden layer as m 200. As described in Algo- rithm T by, Vr are uniformly initial- ized in 1 and wr, Yr are initial- ized as zero mean Gaussian distribu- tion according to A (00 L//d). These
4000
6000
1300
2002
(a) -hhirttl--Whhtlee vs. Q-Whittle (.
(b) Convergence of Lyapunov
function in 15
Figure 2: Convergence of Neural-Q-Whitee
results are carried out by Monte Carlo simulations with 100 independent trials.

---

Convergence to true Whittle index. First, we verify that Boural-Q-hhittle convergences to true Whittle indices, and compare Q-Whittle, the first Whittle index based Q-learning algo- rithm. As illustrated in Figure 2a Neural-Q-Whittll guarantees the convergence to true Whittle indices and outperforms Q-Whittle 3 in the convergence speed. This due to the fact that Beural-Q-Whitee updates the Whittle index of specific state even when the current visited state not that state.
Second, we further compare with other other Whittle index learning al- gorithms, i.e., D-Whittle-LPP [60]. WIQL and QWIC [23 Fig- ure As we observe from Fig-
mwy way
84
8.0
ure only Neural-Q-Whitt.l
and
Q O-Whittle-LFAi in 66) can converge to the true Whittle indices for each state, while the other two bench- marks algorithms do not guarantee the convergence of true Whittle in- dices. Interestingly, the learning Whit- tle indices converge and maintain correct relative order magnitude, which is still be able to be used in real world problems (60]. Moreover, observe that Neural-Q-Whie achieves similar convergence perfor- mance Q-Whittle-LFA in the con- sidered example, whereas the latter has been shown achieve good per- formance in real world applications in [60]. Though this work focuses on the theoretical convergence analysis Q-learning based whittle index under the neural network function approximation, it might be promising to implement it in real-world applications fully leverage the strong representation ability of neural network functions, which serves as future investigation of this work.
Barsices
Taratcos
(a) Whittle index X(1) for 8 1.(b) Whittle index A(2) for 2.
A
2000
2008
8000
(c) Whittle index X(3) 3. (d) Whittle index A(4) for 4.
Figure 3: Convergence comparison between Neural-Q-Whittle and benchmark algorithms.
Convergence of the Lyapunov function defined in 15 We
18
also evaluate the convergence of the proposed Lyapunov func- tion defined in (15). which is presented in Figure 2b It depicts vs. the number of iterations in logarithmic scale. For ease of presentation, we only take state s 4 as an illus- trative example. It is clear that M (0x. As) converges to zero as the number of iterations increases, which in alignment with our theoretical results in Theorem [[]
14
E| (0, k,, )
10
Verification of Assumption We now verify Assumption that the gap between 8% and can be bounded by the span of
Number of nourons m
Figure 4: Verification of Assump-
fo()%) and f(²) with a constant co. In Figure 4 we show co as a function of the number of neurons in the hidden layer m. clearly indicates that constant eo exists and decreases the number of neurons grows larger.
tion 3 w.r.t the constant cp.
6 Conclusion
We presented Neural- -arral---Mae Q-hatttl--htteeee a Whittle index based Q-learning algorithm for RMAB with neural network function approximation. We proved that Beural-Q-Whitee achieves an (11//2/3) convergence rate, where k the number of iterations when data are generated from a Markov chain and Q-function is approximated by ReLU neural network. By viewing Neural Boural-Q-Waal Whittle as 2TSA and leveraging the Lyapunov drift method, we removed the projection step on parameter update of Q-learning with neural network function approximation. Extending the current framework to two-timescale Q-learning (i.e., the coupled iterates between Q-function values and Whittle indices) with general deep neural network approximation is our future work.
10

---

Acknowledgements
This work was supported in part by the National Science Foundation (NSF) grant RINGS-2148300 and was supported in part by funds from OUSD R&E, NIST, and industry partners as specified in the Resilient & Intelligent NextG Systems (RINGS) program. This work was also supported in part by the U.S. Army Research Office (ARO) grant W91 1-NN--3----00-
and the U.S. Department of Energy (DOE) grant EE-00000334.. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the funding agencies.
References
[1] Jinane Abounadi, Dimitrib Bertsekas, and Vivek S Borkar. Learning algorithms for markov decision processes with average cost. SIAM Journal on Control and Optimization, 40(3):681- 698, 2001.
[2] Joshua Achiam, Ethan Knight, and Pieter Abbeel. Towards characterizing divergence in deep q-learning. arXiv preprint
2019.
[3] Konstantin E Avrachenkov and Vivek S Borkar. Whittle index based q-learning for restless bandits with average reward. Automatica, 139:1 2022.
[4] Dimitri Bertsekas and John N Tsitsiklis. Neuro-dynamic programming. Athena Scientific, 1996.
[5] Dimitris Bertsimas and José Niño-Mora. Restless Bandits, Linear Programming Relaxations, and A Primal-Dual Index Heuristic. Operations Research, 48(1):80090, 2000.
[6] Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference on learning theory. pages 1691 1692. PMLR, 2018.
[7] Shalabh Bhatnagar, Richard S Sutton, Mohammad Ghavamzadeh, and Mark Lee, Natural Actor-Critic Algorithms. Automatica, 45(1 1):2471-2222 2009.
[8] Arpita Biswas, Gaurav Aggarwal, Pradeep Varakantham, and Milind Tambe. Learn to intervene: An adaptive learning policy for restless bandits in application to preventive healthcare. In Proc. of IJCAI, 2021.
[9] Vivek Borkar. Stochastic Approximation: Dynamical Systems Viewpoint, volume 48. Springer, 2009.
[10] Vivek S Borkar and Karan Chadha. A reinforcement learning algorithm for restless bandits. In 2018 Indian Control Conference (ICC), pages 89-94, IEEE, 2018.
[11] Vivek S Borkar and Vijaymohan R Konda. The Actor-Critic Algorithm as Multi-Time-Scale Stochastic Approximation. Sadhana, 22(4):5225544 1997.
[12] Vivek Borkar, K Ravikumar, and Krishnakant Saboo. An index policy for dynamic pricing in cloud computing under price commitments. Applicationes Mathematicae, 44:215-245, 2017.
[13] Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. Neural temporal difference and learning provably converge global optima. Mathematics of Operations Research, 2023.
[14] Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam. Finite- Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes. arXiv e-prints, pages 2002, 2020.
[15] Zaiwei Chen, Sheng Zhang, Thinh T Doan, Siva Theja Maguluri, and John-Paul Clarke. Performance of Q-learning with Linear Function Approximation: Stability and Finite-Time Analysis. arXiv preprint arXiv: 1425, 2019.
[16] Wenhan Dai, Yi Gai, Bhaskar Krishnamachari, and Qing Zhao. The Non-Bayesian Restless Aumei-Armed Bandit: A Case of Near Logarithge Regret. In Proc. of IEEE ICASSP, 2011.

---

[17] Gal Dalal, Balazs Szorenyi, and Gugan Thoppe. A tale of tro-tto-tmee timescale reinforcement learning with the tightest finite-time bound. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3701-3708, 2020.
[18) Gal Dalal, Gugan Thoppe, Balázs Szörényi, and Shie Mannor. Finite sample analysis of two- timescale stochastic approximation with applications to reinforcement learning. In Conference On Learning Theory, pages 1199-1233. PMLR, 2018.
[19] Thinh T Doan. Nonlinear two-time-scale stochastic approximation: Convergence and finite-time performance. arXiv preprini arXiv:201 1.01668, 2020.
[20] Thinh T Doan. Finite-time time convergence rates of nonlinear two-time-scal scale stochastic approxima- tion under markovian noise. arXiv preprint arXiv:2104.01627, 2021.
[21] Thinh Doan and Justin Romberg. Linear Two-Time-Scale Stochastic Approximation A Finite-Time Analysis. In Proc. of Allerion, 2019.
[22] Jianqing Fan, Zhaoran Wang. Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep q-learning. In Learning for Dynamics and Control. pages 486-489, PMLR, 2020.
[23] Jing Fu, Yoni Nazarathy, Sarat Moka, and Peter G Taylor. Towards q-learning the whittle index for restless bandits. In 2019 Australian & New Zealand Control Conference (ANZCC), pages 249-254, IEEE, 2019.
[24] Harsh Gupta, Rayadurgam Srikant, and Lei Ying. Finite- performance bounds and adap- tive learning rate selection for two time-scale reinforcement learning. Advances in Neural Information Processing Systems, 32, 2019.
[25] Bowen Jiang, Bo Jiang, Jian Li, Tao Lin, Xinbing Wang, and Chenghu Zhou. Online restless bandits with unobserved states. In Proc. of ICML, 2023.
[26] Young Hun Jung and Ambuj Tewari. Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problems. Proc. of NeurlPS, 2019.
[27] Maxim Kaledin, Eric Moulines, Alexey Naumov, Vladislav Tadic, and Hoi-To Wai. Finite time analysis of linear two-timescale stochastic approximation with markovian noise. In Conference on Learning Theory, pages 1144-2003, PMLR, 2020.
[28] Jackson A Killian, Arpita Biswas, Sanket Shah, and Milind Tambe. Q-learning lagrange policies for multi-action restless bandits. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 871-881, 2021.
[29] Jackson A Killian, Andrew Perrault, and Milind Tambe. Beyond" To Act or Not to Act": Fast Lagrangian Approaches to General Multi-Action Restless Bandits. In Proc.of AAMAS, 2021.
[30] Vijay R Konda and John N Tsitsiklis. Actor-Critic Algorithms. In Proc. of NIPS, 2000.
[31] Vijay R Konda and John N Tsitsiklis. Convergence rate of linear two-time-scale stochastic approximation. The Annals of Applied Probability, 14(2):99-819, 2004.
[32] David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
[33] Haoyang Liu, Keqin Liu, and Qing Zhao. Logarithmic Weak Regret of Non-Bayesian Restless Multi-Armed Bandit. In Proc of IEEE ICASSP, 2011.
[34] Haoyang Liu, Keqin Liu, and Qing Zhao. Learning in A Changing World: Restless Armee-Armed Bandit with Unknown Dynamics. IEEE Transactions on Information Theory, 192-)199--11 2012.
[35] Aditya Mate, Jackson Killian, Haifeng Xu, Andrew Perrault, and Milind Tambe. Collapsing bandits and their application to public health intervention. Advances Neural Information Processing Systems, 33:15639-11650 2020.
12

---

[36] Aditya Mate, Andrew Perrault, and Milind Tambe. Risk-Aware Interventions in Public Health: Planning with Restless Multi-Armed Bandits. In Proc.of AAMAS, 2021.
[37] Francisco 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, pages 664-671, 2008.
[38] Rahul Meshram, Aditya Gopalan, and D Manjunath. Optimal recommendation to users that react: Online learning for a class of pomdps. In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 7210-7215. IEEE, 2016.
[39] Abdelkader Mokkadem and Mariane Pelletier. Convergence rate and averaging of nonlinear two- time-scale stochastic approximation algorithms. The Annals of Applied Probability, 16(3):1671- 1702, 2006.
[40] Khaled Nakhleh, Santosh Ganji, Ping-Chun Hsieh, Hou, Srinivas Shakkottai, et al. Neurwin: Neural whittle index network for restless bandits via deep rl. Advances in Neural Information Processing Systems, 34, 2021.
[41] Khaled Nakhleh, I Hou, et al. Deeptop: Deep threshold-optimal policy for mdps and rmabs. arXiv preprint (:Xiv:2209008646, 2022.
[42] Ronald Ortner, Daniil Ryabko, Peter Auer, and Rémi Munos. Regret Bounds for Restless Markov Bandits. In Proc. of Algorithmic Learning Theory, 2012.
[43] Tejas Pagare, Vivek Borkar, and Konstantin Avrachenkov. Full gradient deep reinforcement learning for average-reward criterion. arXiv preprint arXiv:2304.00 037799, 2023.
[44] Christos H Papadimitriou and John N Tsitsiklis. The Complexity of Optimal Queueing Network Control. In Proc. of IEEE Conference on Structure in Complexity Theory, 1994.
[45] Martin L Puterman. Markoy Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 1994.
[46] Guannan Qu and Adam Wierman. Finite-Time Analysis of Asynchronous Stochastic Approxi- mation and Q-Learning In Proc. of COLT, 2020.
[47] Hiteshi Sharma, Mchdi affania-Jahromt and Rahul Jain. Approximate relative value learning for average-reward continuous state mdps. In Uncertainty in Artificial Intelligence, pages 956-964. PMLR, 2020.
[48] Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation andtd learning. In Conference on Learning Theory, pages 2803-2830. PMLR, 2019.
[49] Wesley Suttle, Kaiqing Zhang, Zhuoran Yang, Ji Liu, and David Kraemer. Reinforcement Learning for Cost-Aware Markov Decision Processes. In Proc. of ICML, 2021.
[50] Cem Tekin and Mingyan Liu, Online Learning of Rested and Restless Bandits. IEEE Transac- tions on Information Theory, 588)):5588-661, 2012.
[51] John N Tsitsiklis and Benjamin Van Roy. Average Cost Temporal-Diifference Learning. Auto- matica, 17991911799-1888 1999.
[52] Yi Wan, Abhishek Naik, and Richard S Sutton. Learning and Planning in Average-Rewar Reward Markov Decision Processes. In Proc. of ICML, 2021.
[53] Siwei Wang, Longbo Huang, and John Lui. Restless-UCB. an Efficient and Low-complexity Algorithm for Online Restless Bandits. In Proc. of NeurlPS, 2020.
[54] Richard R Weber and Gideon Weiss. On An Index Policy for Restless Bandits. Journal of applied probability, pages 637-648, 1990.
[55] Chen- Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, Hiteshi Sharma, and Rahul Jain. Model- free Reinforcement Learning in mafiite-HHoizon Average- Reward Markoy Decision Processes. In Proc. of ICML, 2020.
13

---

[56] Peter Whittle. Restless Bandits: Activity Allocation in A Changing World. Journal of applied probability, pages 287-298, 1988.
[57] Guojun Xiong, Jian Li, and Rahul Singh. Reinforcement Learning Augmented Asymptotically Optimal Index Policies for Finite-Horizon Restless Bandits. In Proc. of AAAI, 2022.
[58] Guojun Xiong, Xudong Qin, Bin Li, Rahul Singh, and Jian Li. Index-aware Reinforcement Learning for Adaptive Video Streaming at the Wireless Edge. In Proc. ACM MobiHoc, 2022.
[59] Guojun Xiong, Shufan Wang, and Jian Li. Learning infinite-horizon average-reward restless multi-action bandits via index awareness. Proc. of NeurIPS, 2022.
[60] Guojun Xiong, Shufan Wang, Jian Li, and Rahul Singh. Whittle index based q-learning for wireless edge caching with linear function approximation. arXiv preprint a3X1v:2202.13187, 2022.
[61] Guojun Xiong, Shufan Wang, Gang Yan, and Jian Li. Reinforcement Learning for Dynamic Dimensioning of Cloud Caches: A Restless Bandit Approach. In Proc. of IEEE INFOCOM, 2022.
[62] Pan Xu and Quanquan Gu. A finite-time analysis of q-learning with neural network function approximation. In International Conference on Machine Learning, pages 10555-10565. PMLR, 2020.
[63] Zhuoran Yang, Yongxin Chen, Mingyi Hong, and Zhaoran Wang. Provably Global Convergence of Actor-Critie: A Case for Linear Quadratic Regulator with Ergodic Cost. In Proc. of NeurIPS, 2019.
[64] Zhe Yu, Yunjian Xu, and Lang Tong. Deadline Scheduling as Restless Bandits. IEEE Transac- tions on Automatic Control, 6388)22343-2388, 2018.
[65] Shangtong Zhang, Yi Wan, Richard Sutton, and Shimon Whiteson. Average-Reward Off- Policy Policy Evaluation with Function Approximation. arXiv preprint arXiv:2101.02808, 2021.
[66] Sheng Zhang, Zhe Zhang, and Siva Theja Maguluri. Finite Sample Analysis of Average-Reward TD Learning and Q-Learning. Proc. NeurlPS, 2021.
[67] Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for sarsa with linear function approximation. Advances in neural information processing systems, 32, 2019.
14

---

A Related Work
Online Restless Bandits. The online RMAB setting, where the underlying MDPs are unknown, 33
42 26]. However, these methods do not exploit the special structure available in the problem and contend directly with an extremely high dimensional state-action space yielding the algorithms to be too slow to be useful. Recently, RI. based algorithms
has been gaining attention, e.g., [16
34
50
53 8 28 57 59 61 58 3), to explore the problem structure through index policies. For instance, [23] proposed Q-learning algorithm for Whittle index under the discounted setting, which lacks of convergence guarantees. [8] approximated Whittle index using the difference of Q(s, 1) Qss, 0) for any state s, which is not guaranteed to converge to the true Whittle index in general scenarios. To our best knowledge, the Q-Whittle in ( proposed by B is the first algorithm with rigorous asymptotic analysis. Therefore, [23] 3 g 28 lacked finite- time performance analysis and slow convergence.
have been developed [T0 23
stochastic approximation algorithms usually suffer from
designed modell-bsed low-complexity policy but is constrained either a specific Markovian model or depends on a simulator for a finite-horizon setting which cannot be directly applied here. Latter on, [60] showed the finite-time convergence performance under the Q- D-Whitte Whittle setting of 3] with linear function approximation. However, the underlying assumption in [3 60) is that data samples are drawn i.i.d per iteration. This is often not the case in practice since data samples of Q-learning are drawn according to the underlying Markov decision process. Till now, the finite-time convergence rate of Q-Whit Whittle under the more challenging Markovian setting remains to be an open problem. Though 43 proposed a novel DQN method and applied it to Whittle index learning, it lacks of theoretical convergence analysis. To our best knowledge, our work is the first to study low-complexity model-free Q-learning for RMAB with neural network function approximation and provide a finite-time performance guarantee.
53
57
Two-Timescale Stochastic Approximation. The theoretical understanding of average-reward rein- forcement learning (RL) methods is limited. Most existing results focus on asymptotic convergence 52 65], or finite-time performance guarantee for discounted Q-learning [15] 46 14. How- ever, the analysis of average-reward RL algorithms is known to be more challenging than their discounted-rewant counterparts [66] (55). In particular, our Neural-Q- Boural---whitee Whittle e follows the 2TSA scheme [T] 30 77 The standard technique for analyzing 2TSA is via the ODE method to prove asymptotic convergence (9. Building off the importance of asymptotic results, recent years have witnessed a focus shifted to non-asymptotic, finite-time analysis of 2TSA 24 21
19 [
The
closest work is [19] which characterized the convergence rate for general lonelinear 2TSA with i..dd noise. We generalize this result to provide a finite-time analysis of our Neural-Q-Whise with Markovian noise. In addition, existing finite-time analysis, e.g., sample complexity [66] and regret (55) of Q-learning with average reward focus on a single-timescale SA, and hence cannot be directly applied to our HeurallQ-Whitte
Finally, existing Q-learning with linear function approximation [37 67 and neural network function approximation [13 62 requires an additional projection step onto a bounded set related to the unknown stationary distribution of the underlying
MDPs, or focuses on a single-ting timese-t SA [5].
B Review on Whittle Index Policy
Whittle index policy addresses the intractable issue of RMAB through decomposition. In each round f, it first calculates the Whittle index for each arm independently only based on its current state s,, (t), and then the Whittle index policy simply selects the K arms with the highest indices to activate. Following Whittle's approach[56] we can consider a system with only one arm due to the decomposition, and the Lagrangian is expressed as
1 E, T-000 T
Σ (r(0 (110)x(1-a(t)
L(TT, A) = lim inf
(25)
where À is the Lagrangian multiplier (or the subsidy for selecting passive action). For particular X, the optimal activation policy can be expressed by a set of states which it would activate this arm, which is denoted ((A).
15

---

Definition 3 (Indexiability). We denote ( as the set of states S for which the optimal action for the arm is to choose a passive action, i.e., A = Then the arm is said be indexable if D (()) increases with X, i.e., if X > X, then ( 2 D(X).
Following the indexability property, the Whittle index in particular state S is defined follows. Definition 4 (Whittle Index). The Whittle index in state S for the indexable arm is the smallest value of the Lagrangian multiplier À such that the optimal policy at state S is indifferent towards actions A 0 and A = 1. We denote such Whitle index X(5) satisfying X(S) inf x2o D())}- Definition 5 (Whittle index policy). Whittle index policy is a controlled policy which activates the K arms with the highest whittle index (()) at each time stot I.
C Proof of Lemmas for "Step 2: Convergence Rate of M (0,, AR) in (16) "
C.1 Proof of Lemma
Proof. Recall that
fo(0:((saa)
mm Σ b,1l (o (ss
Thus we denote Vofo(0:b(s.a)) as
b1 1 [w] I. 0)p(s,a)T,....
bm
(wI m (os a) > 0}}(s,
(26)
Since [Ø(s, alll 1, S e A and the fact that by, Vr [m] is uniformly initialized as 1 and -1, we have Vofo(00: a)) < 1.
Therefore, have the following inequality for any parameter pairs (01, A1) and (2) with X (s, as) E
| X 0 A1) ho 02, A2)1l
Vefo(00: ((5, (1-a)Ar - 10)1) max fo(O;; a1)) fo(:::
61
Vefo(02: (s. (1-
a) - (0(2)) + max fo(02; ((5 fol0)))
Vefu 01 0 (1 -2) + (0() (o + -() - fo(0:)
+ max (0(1 (000,;0(''a))) - max fo 1
- (1-a)(A) x2)1 + Ilf (s, a))
+
Σ
0002:0(83 (8,00) 0)) (0: 0)) (0::; 1)) - oo
25
SES
+
||
max (fo(01: az)) max Su 165 dj
(as)
[[11 a) A2) + (1 -0)
Vofu(0 ()) 01) + Vofo(01: 1)) 01)
+
25
EES
max d1
[fo00 an)) max (o (( ((5) 02))
ag
(a4)
[[A1 A2)1l + 2 021 +
max (o(00; a.)) - max fo (02 (((0)(((''')
a1
a2
16

---

(05)
||| max fo fu(01:0(s',a') - =0(02:
11(A1 X2)1l + 2 - 02ll +
(as)
I1(A1 - X2)11 + 3 00 0211.
Specifically, (a1) holds due to the fact that
as in (26). Since
(0x) 25 BES
So(Ox: (3, 0)) + fo(0s: (88 1))]
(a2) is due to the fact that x yl < ||> I Va, y E Rnd and
| yll < -eyll Va, E Rmd
and [s a))l - 1s, (az) holds since
fo(0 (s, a)) - fo (s, a))) = Vefo (s,, a)) 01), V.) S. (04) holds for the same reason as (az). (as) is due to the fact that
(27)
max fu(01:0(s' ,d)) fo(02: (5' a')) S max (1 [Imax (uaaxxo(0::b(ss.d
fol02: .osss.'')) d'))
a'
min -d)
(28)
(0s) holds for the same reason as (az) and (a4).
C.2 Proof of Lemma
Proof. Since go (-) is irrelevant with X and X, in the following, we write 9o 0, A) with go (A)
interchangeably. For any 0 E Rnn and 02 E Rnd we have
[1 - (02)
| 1)) -
- ())
0))1
< []fo(0);(ss, 1)) - (6(0;:)(s 1)) (()) fo ((s 0))
( 1))(02 - 0:)1 + ((s, -1)
< [(: 1)) -10, 02l + (o.6 |00 02ll
s 2||0,
02l1:
where the first inequality is due to the fact that || y/l ||س||| + || Vo, y Rnd the second inequality holds due to ||= yll s ||ق||| ||lll| Vx, y Rnd, and the last inequality holds since |[Vofo(0 ((s, a))l < 1, Vs S,a a E A.
C.3 Proof of Lemma 3
Proof. For any 0, E Iund and 02 E IR,,, we have
(0)) - (02)l
= =||r(s.1) r(,, -((s0) + Σ P(s'|s, 1) max fo(O a)) - Σ P(s'|s, 0) max (((0
(((,))) Σ P(8l(s,) 1) max 0( Σ P(dl(s, max f6
Σ P(s'|s, (s 1) max ((000:(()))) a)) Σ
P(s' (ss'|s,) 1) max fo(O2: ((s.
a
Σ P(s'ls 0) max fo(0; a)) Σ P(8'|s, 0) max fo (0 $
<
Pss' ss 1) max fo 0 ((5 a))
P(s 1) max fo (0
Σ P(s' s, 0) max fu 0 0)) + Σ P(s'ls, 0) max fo fo ((::)''s
2 02ll.
with the last inequality holds due to
27 and 28
17

---

C.4 Proof of Lemma
Proof. 1) We first show that there exists a constant
> such that OO² ()) -111012
According to the definition of 0g given in Definition |
E (X, 0ü yo (0])) O. Hence, we have
00 (ho(X,, X, A) - ho(X, 30
30 (06))
0 =O'E[ho X, 0, - (0()))
To(0) + max (o ((5' a1)) 500, 0 -Q'R (() a)
an
Vefo 1 ((. -0--0))))) 1o(0%) (1-a))0((0) max fo ( 06s (2)) folO d(. ((s.a))
o"r E
V Vejo (0: 2 a)) a)( yo (0))) + T(0)) To) fo ((.
max fo (0: (5s' a1)) max fo ( 02)) max fo (0:
81
=0
Vofo(0:((s.a))
max f0 (ss,)a)))
42
Vofo (T) - (0)) 0
V (o (s. ()..0 (f000)00))))))0
+ E Vofo a) -ao-oo (0,))
(b2)
0'E Vefo max [o d')) - fo(0%:
TT E
Vofo
10 [6))
(1 (o((:)))))
0 Vofo ( +
(ba)
(o max fo -1)) fo) 66000
-0'E
Vefo
- - - fol0%:
(b4)
0 2
(6 d5 To.ii00 1)]]
V
fo
1
Volo(0:0(s,
25
EES
|10||
where (br) holds since Ve a)) VoJo(07; ((5, a)) as (6) (b2) is due to the fact that
maxa, fo: ((s a1)) max., (0; 0(s' az)) 1 max fo(0: a(s', a')) fu(O;: (ss a'))
and (bg) holds due to the fact that 0 E fo ((s, a)) a) 3o [5)) < since larger Whittle index will choose the action 1. Notice that the in (b4) represents the action a' which maximizes fo(O; Ø(s", a')) fo; ((s', a d')). Due to the definition of Velo ((s, a)) in 26) we
show that 0 (o 0, A)] < 0.
2) Next, we show that there exists constant μ12 such that E E[ 0, A)] < -
According to the definition of go (f), i.e., (o( = fn Φ(s, 1)) fo ((s,0) Since yo ( is the solution of À such that (0; 6(s, 1)) = fo(O: (fs, the signs of = X - (0) and fo(O; ((s, 1)) fo(O; ((s, 0)) are always opposite. Hence, have E[Ago (X, 0, A)] 0, which completes the proof.
18

---

C.5
Proof of Lemma
Proof. Under Lemma
we have
l 0. A) ho 0" x>>= _ 3 8" + aÀ
X-I
(29)
Let L = max(3, maxx (X, )))) then according to 29 we have
[loo(X,0,)) = 0(1 0
|| X +
Denote hx 0, A) as the i-th element of to ( X, 0, X). Following 15 we can show that 0 E R À R-, and x E X,
BB Xx. K. 0 Xo = x] - loo X, 0, X)]l
md
B Xx 0 A) Xo x] E, M6 XI]
md
(X 0,
s 22L(110 0-1 + 11 X
E
Xo
22(11 0-
1| X- + 1)
1=1
An 0.
Eu 2 0
+
a +1]
221(11 1
+ || X 1)mdCp².
where the last inequality holds due to Assumption
To guarantee 2L(110 - -0'1 + a| -111
1) 1)mdCp s 5(110 8" + π| | 1). we have
T8 v log(1/8) + log(2LCmd)
log(1/p)
which completes the proof.
C.6 Proof of Lemma 6
Proof. Based on the definition of (0x, Ax) in 115). we have
( Ax)
7 0 0' 0
+ | y(1x)112
?e |0
0
+ 0 0" 1| + | (0x) + vo())) y(Ox))l
Okk
< 21
O1l
+ 10 00 + 2(IAA 00 + (1)0((x) (0a)
277 10
2M (0 Xx)
2 + (l v 0(22))l
27
< 20, Xx)
+
@spam(fo(00) (07) 11 + (0x) - v(Ox))l
(30)
0
where the first inequality holds based on || y < 2| +| 2 and the second inequality holds based on Assumption Next, we bound
1span (0(6) - -(())) as follows
(span(Jo(03) f(0'))]l
[spann (o((0)
-1=0000'''==00))))))0 - f(0)))
< Ispan [ppan(o(00)) [T)](("))] [T - ((0)))
= spp -1=-T((())) (L==T(000"0|+++=ooo000000001=0-) -(00))
S x||span([Fo(0)) ((-))) + (T==
(31)
where the last inequality follows (24) This indicates that
1 (1 x3)3 11pp-= -
Ispan (fo6)) f((0)))))))) 1)12
(32)
19

---

We further bound [yvo(Os) - y(0x)l2 as follows (Ox)) - y(0x))l
Σ p(s' (s,1) max ma fu(0s: a1)) - Σ p(s (s,0)
max 00 o2))
a1
"2
Σ p(1) max f(O ( as)) Σ p(s'|s,0)
max 00x
84
Σ p(s'|s,,1lse (isss(s,1)(mmn (s,1) fo (0::
a1)) - max
f 0 a3)))
83
Σn( p(s (0 fo ( a2))
max f (0x: 2 .1)) a1))|'
02
44
$ 2| max fo (00: O( f(x:
(e.0)
o (10ll 1o
s 20
(33)
1/2
where the last inequality due to Lemma results.
10 Substituting
(32) and (33) back (30) yields the final
D Proof of the Theorem 2
To prove Theorem 2 we need the following three key lemmas about the error terms defined in (99
Lemma 7. Let {0x, } be generated by (9). Then under Lemmas for any 2 т, we have
E
0 k+ 1 [ S (1 + 1500 2 + mk/ax 20g )
0x
[Fa_o] + 6a E
Ax
F
0 o (1 + +1o1 + 1)3 1)5. m 1122)
(34)
T
Proof. According to 19
we have 0x+1 : 0x+1 - 0% = 0r + (xn AR), which leads to
0 | 1| = 0x
+ 2a Chx, 0r, Ax) + ( 0x, A43
= |all" + 22 0 (1( (Xxx On, Ax) - (X 0s, Ax)) + 2a ho (Xx, Ok,
+ 1 Xx 02, A1) ho (x,, 02, Ax) + (x Ax)1
- 0x | + 20 0 (h( (Xx, 02 Ax) ho Xx 02, Ax)) 20 0 /, No XR. 0x, Ax)
+ 2a [1( 2x. Av) - ho (xx, 02. A 2| 2a ( 02. A+
(35)
The above inequality holds due to the fact that ||= + y12 < 2||2|| 2/1y/1 2 Taking expectations of 11 w.r.t Fx-r yields
E
110+t1
<
0x
[r-_]]
20 (Xx, Ox, (X [c)
20
||
110 O2. )o) [oc_r]
Term
204 ( On. Aw) - ho Oz. FF))
Torma
+ 2a2E [(Xx, 0x. 2x) - Lo 0x: )a) FF
Terma
20

---

<B <b|10:
2 [ram]]
20mh 0x / [Fa-r]] + Term + Term2 + Term3, (36)
where the last inequality is due to Lemma
4
Next, we bound each individual term. Term is bounded
as
Term: = 2 ho (xx, 0n. Av [Fa-7]
(0) B
ho (o 2x. Ax) (o 0x. (o()))) ho 0x. v0((x))
- ho(Xx (o()) ho Xxx 0ū. (o())
Ho (00)))) [Fa
(02)
ho(Xx, (xx 2x, Ax) (x 2x. yo [Fa_r]
ho (N kk yo (6 ho to vo (016)) FR--]]
+ 6
+ 6
(Xa. 0% (o))
Ho vo (0))) [Fc_7]
(c))
Ga
F Fx-+|
150
0x [
(37)
where (ci) holds due to (0. yo (0%) = O, (02) follows from the triangular inequality, and (ca) follows from the Lipschitz continuity of ho (x, 0, A) Lemma
Termy is bounded as
Terma = 20 E
0
(N( 0x, Av) ho( CxXNOO. 0x, An)))(F
(cr) 7k
E
xx
[
[
+
2 E
h(xx O2. Aa) ho(Xx. Onr 0xs) [Fa-]]
O
7/K
ox O
0x
[
c1100l
1Pool 1)33 m 11/2)
(38)
akk
where (ca) holds due to the fact that 2x S Termy is bounded as
x 2 + | and (es) is due to Lemma 10
(o02E111(6 h(Xx. Ax) - ho( Ōk. Aa) 2 [Fa-T]
Term;- = 2
(cx)
20 (c( + +1 + 1)3 m m=//)) x
(39)
where (cB) comes from Lemma the desired result in 34). which
Substituting Term, Term,, and Termy back into 36 leads to
110
112
01
F K - 204u4 0x [
+ EE
|F + 1500 0| [r
+ ?k E
||10,
- [Fx
ax o 0c(((18011 + |Aol + 1)3 m m112
+ 20 0
c2((10011 + 1oal + 1)3 m -122)
0xx [Fa_r] + 6a [|xm]]]]]] 1 FFa_)]
-1 150a +m//ax 200 E
+ (a. m + 20 0 (110 Aool + 1)3 m 112))
By neglecting higher order infinitesimal, we have the inequality in 34). This completes the proof.
21

---

Lemma 8. Ler (0k,, ) be generated by (9)
Then under Lemmas
44 for any Ao 2 T, we have
AR+1 12 Fi-r s (1 27/x/1/ + agTT +
24a
21/
+ The + 24a )1
[Fa-r]
OEk
+ (600a + Sn + 8mp
600
[F
The o (1 |I + |ol + 1)a² m 1/2
(40)
O%k
Proof. According to the definition in (44. we have
Sx+1
xx+1 yo (0x+11))
= ' + +00((0x) + yo - (o((x
which leads to
2 =
|| Ax. + (0.)(xx) + (0 v0 )|(
Ae+1
À + (
|| (0x) yo ++++1
Term
Terma
+ 2 (Ax +mm(0ss) (yo y0 00+0++))
(41)
Terma
The second equality is due to the fact that | + yl1² = || + | F + 2x We next analyze the
conditional expectation of each term [ on FR-r. We first focus on Term
2
Term
FR
210))..(00)) kx) |
[
B
B A
2o + 2m da (0(x)) (0())) ni g(Ox)) (0x)) + :0((ss)
/ [5a_7]
s E
[F
+ 1 Au (0x) Fx
+ 1 )s(g(Or) (0x())
||| (((0s) - go 50x0))) 1|2 |
(0((x)) (O.)) [5m-T]] [|0000.)|1PFm=1
+ 2n E
2
(4:)
E
11 11
|F -
FR-
+ 27M E Ango (0x)(OOx122) (K)
+ 27k E (ex)))))= go vn(Ox)) (00)))]F
2n E
|1|00 ((Oa)) ) - go (0x))
1 -
27
||| (0(0)) 90 (n())) ((k_T]
(4))
E
|1| Am 11 12 F - 27th 2211 E || 1|
[
+ S
00x 11 [R
2m
E ()(x)
(1(((0a)) - - 1i
(dg)
E
Sx 1 [r
- 22
|1 2 F -
+ 8n
[
+ F |||م||||
[ [Fx_
(4mx/ax + 8n (20(1 + Aool + 1)3 m 1/2
where (d,) follows from go (03) 0, (dz) holds due to Lemma and the Lipschitz continuity of yo in Lemma 3 and (da) comes from Lemma 10 For Termy, we have
Terma Fx-o| = [|po(O.) - vo 20(0k+1) Frad (Fam
22

---

| 0k+1 12 1F 1
4E
2
11 [ n. 22. deel 1Fa-
4
1( 1(Xx 2x )x) - An, Ax) + hooooo. Oc, de)1 [Fk-T]
No ho( 0 Ax) 11 [ + & [((Xx 0n, )b) ho( Ons Ame [F(_T]
SagLE
(4.) B
IoooX: O2, Ax) no 2c (0x))) + ho OR. vo(O2))
no 0 yo (0)) + ho [xx 0/: yo (06) - Ho yo (0))) 15
+ & 11( (xx: OR, Ax) ho (xx: Ok. )x0) 1|2 |Fk-1
(da)
x 24
/o An) ho 0x v0(0x))
[k
1|
+ 24
110 (N Os (0.) - ho 06 vo(()))
+ 24a
/ho(Xx> 0g (0))) Ho y0 (0)))
| [Fa-
+ 80
F [Fa [[ O2. Ax) ho Ox. )w))
(dg)
S 2A
F [ 600aI | [Fx-7]
+ $
|(Xx= 2R, Ax) ho Okr Axt)
[Fk-T]
(d+)
S 24
[Ae]
F [ + 600a |10 Fx
+ No
(c/(1101)
+ 1all + 1)3 mm
m mm11))
(42)
where (d4) is due to the fact that (0 (0))) 0. (ds) holds according to | + + 2| <
3||==||² +3|y/|/ +|]==|] since ((x,, (X*) X²) = 0, (de) holds because Lipschitz continuity
of hg and yo in Lemma and Lemma 3 and (dz) comes from Lemma 10 Next, we have the
conditional expectation of Termy as
Terma Fx
2E
|| Au. + min( ||00(0)) v0(0k+1) -00(ttt)|
(dg)
Term
+
ak
Term2
ai
17k
Ue EE
2
[ [Fa_r]
22 E
Rx [Fx-
87
E
0x
[Fa_
Okk
ax
+ 1E
[Fx
Th
(4nR / + +
(1 -P1ol +1)3 11/2)
ax
24
600 E -100x [Fa-T]]
|Sxe|
E
7
8a
+
0
(c]((100)) +
|Aol + 1)3 m.mmmmm-
- -1/2)
where (da) holds because 2x < 1/ BIy v/ > 0. Summing Term,, Termy, and Termy and neglecting higher order infinitesimal yield the desired result.
D
23

---

Now we are ready to prove the results in Theorem non-increasing, we have the following inequality
Providing Lemma 8 and Lemma 7 if is
E [((k+1:: ARt1) FR = E
Ok+1
+ |
2
FR--
ak
1]
(1 20m )
10x 1 [FR_
+
600a
EE'
[Fx-
Okk
T/
Sar 0
(c>((1001l
Moo 1)8 m 1/2)
(1
2111122 )
|| [Fa-7]
600
E
(43)
7h
Since (A: + 1)2.
o2 7
1)3/3, c + +
no
multiplying both sides of (3 with (A: + 1)?, we have
(h: + 1) Ni +1,
1 A FR-r]]
600g8 (k + 1)2/3 (100.1 1| + ||aa|1
<t'B (0xx Ax) F Fx +
sad +
(k - 1) 1 c2lll + Mol + 1)3 -m- 1/2).
(44)
7/0
Summing (44) from time step 7 to time step k. we have
(ks + 1) M(
A FF
S =12
MO AT) + 600
(A: + 1)4/3 (1ee,1 + +112,1²)
8ag
(A: + 1)1/3 0 (ci(11o0l + |Aal + 1)3 m m-112)
2 M [0, 2.)] + 600gg (C, 10 2 + (2C) + |
770
(At + 1) 1//4/3
4/3
O
(cG(110011
|Aal 1)3 1/2
8a
(45)
1o
(k-1) 4/3
where the second inequality holds due to Lemma 9 Finally, dividing both sides by (k + 1)² and moving the constant term into O(-) yields the results in Theorem
E Auxiliary Lemmas
In this part, we present several key lemmas which are needed for the major proofs. We first show the parameters update in (9) is bounded in the following lemma.
Lemma' 9. The update of 0 and As in (9) is bounded with respect to the initial Og and No i.e.
0 0ol + A Aol S ci c10ol + Iool + 1),
with Ci be the constant, i.e., e = 1 + ] (T4,0 + -,,, (T) + I 1).
Proof. Without loss generality, we assume that
IA 2 max(3, max [ o, 0)1), 1/ 2 max(2, max |1 0)1). XEX
Xex
Then based on triangular inequality and Lemmas we have
[X,, 0, A)Il < (001 + | + 1), l1 0x, A) < 43 10 EX. (46)
24

---

Since we have 0x 0x + ax O2 Ato) we have the following inequality due to Lipschitz
continuity of (46)
1 k+1 0x11 (allli((a On Ax)I (10x1 + + + 1).
(47)
Similarly, have
DR+1 ARl = mel O2, Ax)1 - m + |hxl + 1).
(48)
Due to triangular inequality, adding (47) and 48 leads to
00++1l + |attl + 1 S (L), + I. + 1x + |m + 1) I (L) + n0 + () + Axx + 1),
(49)
where the second inequality holds due to the non-increasing learning rates {ax, mh Rewriting the above inequality in (49) in a recursive manner yields
|0+11 + da + 1 S (4,,00 + Lo + 1)==7(100) + 14,1 +1)
(50)
Hence, we have
10 02 0k-rll + Ae A t=k-
10++1 - 0ell + 1de+1 - del
k-1
$ (T + 11))00)
Σ
(10+1 + 11
t=
(L%,00 [1, + M + 1) Σ
(L + Li 1)--
[[T4000 + =T' + 1)" 1] x + A +1)
(ellioot1igm) 1)([10)=+) + A +1) 2(44,00 + 11) ( | 1),
where the last inequality holds when (o + 10) - 1/4. This implies when h = т, we have
|00 -ull 1A= Aol - 2 T 0g = + |oo + 1).
(51)
Similarly, we also have
||0 0. A d
0 - 0ell det1 de
k-1
Σ (L),a, + (l0ell de 1)
k-1
(110|11 + d + 1)
Euha + 1)y)))
Tha + 1y 1). (52)
Therefore, the following inequality holds
10, loll + A >xol
< 110, - 0-1 + AAx x=1 + ||0, - 0oll + [Ar Aol
< 2( + 1' 100 T 0oll + 1Aol+ + 1)
+ ||10,|| + X + 1) Σ (4 + Lyy
II
+ +
1=0
2((L/a0 + 1,700 010l + Aool +1)
25

---

k-1
+ 02 - LT T+ + 1)
Σ (1 + m))
1 + Ligh+s + 1) + 1ool + +
==0
E (Thor + Tggn) 1=7
II
(T + lightt +1) (110bl + 1ool +
2 2
==0
with the last equality holds when (4,000 + LIyTOTT S 1/4. When Ei 1g)))
+ 1or + 1) is non-increasing with h, then we can set c1 as c1 + 3 (L + 1g + li + 1). This completes the proof.
Provided Lemma 9 have the following lemma related with local lincarization of Q functions and the original Q functions.
Lemma (Lemma 5.2
There exists a constant eysuch that
[1(x 0R. Ax) ho xx 2x
| - S 0 [T((0000] + |ool+ + 1)8 m m-1/2).
Lemma 10 indicates that if the updated parameter is always bounded in ball with the initialized one as the center and fixed radius, the local linearized function fo(-) (18) and the original neural network approximated function f(-) in (6) have bounded gap, which tends to be zero as the width of hidden layer m grow large. For interested readers, please refer to [13 for detailed proofs this lemma.
26


Reviews:
[{"review_id": "41oSwYU5Ha", "reviewer": "Reviewer_bjcG", "summary": "This paper provides a finite-time analysis of Neural-Q-Whittle. The authors propose Neural-Q-Whittle, a novel Whittle index-based Q-learning algorithm with neural network function approximation for RMAB. Their analysis leverages a Lyapunov drift approach to capture the evolution of two coupled parameters, and the nonlinearity in value function approximation further requires us to characterize the approximation error. They also conduct experiments to validate the convergence performance of Neural-Q-Whittle, and verify the sufficiency of their proposed condition for the stability of Neural-Q-Whittle.", "questions": "Please refer to the Weaknesses section.", "limitations": "No", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper provides a non-asymptotic convergence rate analysis of Neural-Q-Whittle with two coupled parameters updated in two timescales under Markovian observations without the extra projection step.\n2. The authors propose Neural-Q-Whittle, a novel Whittle index-based Q-learning algorithm with neural network function approximation for RMAB.\n3. The authors establish the first finite-time analysis of Neural-Q-Whittle under Markovian observations. Their analysis leverages a Lyapunov drift approach to capture the evolution of two coupled parameters, and the nonlinearity in value function approximation further requires us to characterize the approximation error.\n4. The writing is good.", "weaknesses": "Compared with existing works [13, 22, 58] for Q-learning with neural network function approximation, the technique contribution of this paper is kind of limited. It will be better if the authors could include additional parts to clarify the technical contribution of the paper, compared with prior works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review and constructive comments, as well as giving the positive rating of our work. Here we would like to address the reviewer's concerns and hope that can help raise the rating of our paper. The detailed responses are as follows:\n\n**Weakness #1:** Compared with existing works [13, 22, 58] for Q-learning with neural network function approximation, the technique contribution of this paper is kind of limited. It will be better if the authors could include additional parts to clarify the technical contribution of the paper, compared with prior works. \n\n**Our Response:** Thank you for this insightful comment and providing us a chance to further clarify the contributions of this paper. \n\nCompared with existing works [13, 22, 58] for Q-learning with neural network function approximation, the first fundamental difference of our proposed Neural-Q-Whittle lies in the algorithm framework. Existing works [13, 22, 58] aimed to learn Q-function values with neural network function approximation, while our proposed Neural-Q-Whittle aims to learn the Whittle index for restless multi-armed bandits (RMAB) problem by leveraging Q-learning with neural network function approximation. In particular, our Neural-Q-Whittle involves a two-timescale update between two coupled parameters, i.e., Q-function values $Q(s,a), \\forall s,a$ and Whittle indices $\\lambda(s), \\forall s$ as defined in Eq. (4)-(5). **This renders existing finite-time analysis in [13, 22, 58] not applicable to our Neural-Q-Whittle** due to the fact that [13, 22, 58] only contained a single-timescale update only on Q-function values $Q(s,a), \\forall s, a.$ **Hence, it requires a fundamental different technique (i.e., two-timescale analysis) to establish the finite-time convergence of our proposed Neural-Q-Whittle with two-coupled parameters.**\n\nSecond, due to the Markovian observations of Q-learning at each iteration, conventional single-timescale update Q-learning with neural network function approximation [13, 22, 58] **required an additional projection step for the update of parameters of neural network function** so as to guarantee the boundedness between the unknown parameter at any time step with the initialization, which stabilizes the updates. However, this in some cases is impractical. **Hence, how to remove this additional projection step is an open research problem in the community.** One possible way to remove the projection step is to treat the Q-learning (or TD learning) update as one-timescale stochastic approximation (SA) as in [15, 47]. However, these results only apply to Q-learning with linear function approximation. To the best of our knowledge, the results for single-timescale Q-learning with neural network function approximation is even unknown, let alone the two-timescale Neural-Q-Whittle learning that is considered in this paper. Therefore,  a natural question that arises is: **Is it possible to provide a non-asymptotic convergence rate analysis of Neural-Q-Whittle with two coupled parameters updated in two timescales under Markovian observations without the extra projection step?** Indeed, we provide an affirmative answer to this question in this paper.\n\nWith that being said, our major contribution in this paper is to establish the first-ever finite-time analysis of Neural-Q-Whittle under Markovian observations. **Due to the two-timescale nature for the updates of two coupled parameters (i.e., Q-function values and Whittle indices) in Neural-Q-Whittle, we focus on the convergence rate of these parameters rather than the convergence rate of approximated Q-functions as in [13, 22, 58].** Our key technique is to view Neural-Q-Whittle as a two-timescale stochastic approximation (2TSA) for finding the solution of suitable nonlinear equations. Different from recent works on finite-time analysis of a general 2TSA [20] or with linear function approximation [57], the nonlinear parameterization of Q-function in Neural-Q-Whittle under Markovian observations imposes significant difficulty in finding the global optimum of the corresponding nonlinear equations. To mitigate this, we first approximate the original neural network function with a collection of local linearization and focus on finding a surrogate Q-function in the neural network function class that well approximates the optimum. Our finite-time analysis then requires us to consider two Lyapunov functions that carefully characterize the coupling between iterates of Q-function values and Whittle indices, with one Lyapunov function defined with respect to the true neural network function, and the other defined with respect to the locally linearized neural network function. We then characterize the errors between these two Lyapunov functions. Putting them together, we prove that Neural-Q-Whittle achieves a convergence in expectation at a rate\n$\\mathcal{O}(1/k^{2/3})$, where $k$ is the number of iterations.\n"}, {"review_id": "b6mq3X5tgP", "reviewer": "Reviewer_KAmk", "summary": "This paper studies Whittle index-based Q-learning with neural network function approximations restless multi-armed bandits (RMAB) problem, which is a model-free low-complexity reinforcement learning (RL) heuristics for RMABs. Since state-action space of RMABs is exponentially growing with the number of arms, common Q-learning techniques as well as tabular Q-Whittle algorithm suffer from curse of dimensionality. Instead, the authors analyze a low-complexity neural network approximation method for Whittle index-based Q-learning under non-iid Markovian state-action observations, namely Neural-Q-Whittle. The authors formulate Neural-Q-Whittle as a nonlinear two-timescale stochastic approximation (2TSA) where the parameters of the neural network Q-function and the Whittle indices  are mutually coupled and the former is updated on a faster timescale than the latter. Leveraging a Lyapunov function method, the authors provide a finite-time convergence analysis of Neural-Q-Whittle with non-iid Markovian data. The analysis involves characterizing the error between two Lyapunov functions: one for the neural network Q-function and one for the linear approximation of the neural network.", "questions": "1)I am not sure if I understand the sentence starting with \"(Step 3)\" between lines 204-207. Can you clarify what you mean exactly?\n\n2) You might include the definition of \"span\" operator in equation 17 as a footnote.\n\n3) Are h, g, y in Remark 4 supposed be h_0, g_0, y_0?\n\n4) It is not exactly clear to me why it is desirable to update neural network parameters and the indices at two different time-scales. Do these parameters only converge under this case? Or do they converge faster compared to single timescale? Could you clarify the need for and the significance of two-timescale approximation?\n\n\n\n\n\n\n", "limitations": "The limitations are addressed within the text and mentioned as a future work in the conclusion (extension to multi-layer neural network).", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "This paper is original in the sense that it removes some of the limitations in the previous theoretical works on finite-time analysis of Whittle index, Q-learning, and nonlinear 2TSA and generalizes to neural network Q-function approximation in two-timescales under non-iid ergodic state-action process.  The theoretical analysis and proofs seem technically solid and mostly clear. \n", "weaknesses": "Since this work builds upon the limitations in the related past works, it would be easier to follow and appreciate the novelty and significance if you could provide a table comparing to related works in various aspects (eg. methods, assumptions, convergence rates, computational (time or space)  and sample complexities). It could also help with presentation if you give an informal version of your main theorem beforehand or simplify Theorem 1 using asymptotic notation and state the full version in the appendix.\n\nI believe it should also be emphasized more that your convergence result relies on diminishing error bound of linear approximation of overparameterized neural networks. \n\nAlthough this is mainly a theory paper, it would be interesting to see the experimental comparison to other methods such as Q-Whittle-LFA and references 13, 22, 58.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review and constructive comments, as well as giving the positive rating of our work. Here we would like to address the reviewer's concerns and hope that can help raise the rating of our paper. The detailed responses are as follows:\n\n**Weakness #1:** ...provide a table comparing to related works...simplify Theorem 1 using asymptotic notation ... \n\n**Our Response:** Thank you for this insightful comment and suggestion. Since this paper is the first to provide a finite-time convergence rate of the complex setting that learning the Whittle index by leveraging Q-learning with neural network function approximation, it is not straightforward and fair to compare the convergence rates, computational (time or space) and sample complexities with those references listed in our paper. However, to further distinguish the difference between our papers and per the reviewer's suggestion, we can still compare those works in terms of the considered setting, such as the noise model, whether an approximation was used or not, what is the timescale of the algorithm, and whether it aims at learning Whittle index. We summarize these in a table (**Please kindly refer to the pdf in the global response** ).  As for simplifying Theorem 1, we will end up with $\\mathcal{O}(1/k^2)+\\mathcal{O}(1/k^{2/3})+c$  with c being a constant value depending on $m$ and it goes to 0 as $m\\rightarrow \\infty$. However, we believe that presenting a full version in the main paper helps to better explain each term at the r.h.s. of Eq. (17). Since we will have an additional content page, we can include these discussions in the camera-ready version of this paper.  \n\n**Weakness \\#2:** ...emphasized more ...overparameterized ...\n\n**Our Response:** Thank you for this valuable suggestion. Indeed, the error bounds of linearization with the original neural network functions are controlled by the overparamterization value $m$, which has an impact on the global convergence as clearly shown in Theorem 1. We will emphasis this more in the camera-ready version.  \n\n**Weakness \\#3:** ... experimental comparison ...\n\n**Our Response:** Thank you for this suggestion. We indeed provided the comparison with Q-Whittle-LFA [57], WIQL [8] and QWIC [23] in supplementary material F (Figure 4 on page 26 in supplementary materials). The reason that [13, 22, 58] are not compared is that our proposed Neural-Q-Whittle in this paper aims to leverage Q-learning with neural network function approximation to learn Whittle index, which involves two coupled parameters, i.e., the Q function values and the Whittle indices. However, the algorithms in [13, 22, 58] are only Q-learning (or TD learning) with neural network function approximations, which only has one single parameter, i.e., the Q function values. To this end, we can only compare with those benchmarks which aim at learning Whittle indices.  Based on the reviewer's suggestion and since we will have an additional content page, we could add/move the experimental results in Figure 4 to the main paper in the camera-ready version. \n\n**Your Question #1:** ...Step 3...\n\n**Our Response:** Sorry for the confusion. We would like to explain this with the aid of Figure 1 on page 6 in the main paper. Our goal is to characterize the finite-time convergence of the two-timescale stochastic approximation (2TSA) defined in Eq. (9) where $h$ and $g$ are related with the true neural network function $f$. To do so, we define the Lyapunov function $M(\\pmb{\\theta}_k, \\lambda_k)$ as in Eq. (15). However, it is challenging to directly finding the global optimum of the corresponding nonlinear equations due to the nonlinear neural network parameterization of Q-function in Neural-Q-Whittle. To tackle this challenge, we first provide a linearization $f\\_0$ of the original neural network function $f$ and define a new Lyapunov function $\\hat{M}(\\pmb{\\theta}\\_k, \\lambda\\_k)$ as in Eq. (16). We then can study the convergence rate of the nonlinear 2TSA using this modified Lyapunov function with smoothness properties guaranteed due to linearization. Theorem 2 provides the convergence results for the surrogate linearized function  $f\\_0$, which assumes that the 2TSA updates in Eq. (9) are based on the $f\\_0$ function.  However, two coupled parameters $\\pmb{\\theta}$ and $\\lambda$ in (9) are updated with respect to the true neural network function $f$, not $f\\_0$. Hence, this further requires us to characterize the approximation errors between $f$ and $f_0$. When adding back this error to the result in Theorem 2, we finally get the desired result in Theorem 1. \n\n**Your Questions #2 and #3:** ...\"span\"... $h\\_0, g\\_0, y\\_0$\n\n**Our Response:** Thank you for this suggestion and pointing out this typo. Yes, it is $h_0, g_0, y_0$, and we will fix them in the camera-ready version.\n\n**Your Question \\#4:** ... two different time-scales...\n\n**Our Response:** Thank you for this insightful question. First, we would like to point out that it is not necessary to be two-timescale parameters.  However, in practice, for an update with two coupled variables with different sensitivities, it is usually empirically better to make one update quicker than the other, which has been widely studied as in [3,8, 19, 20, 21, 38] and reference therein.  As in our setting, the Whittle index depends on the value of Q functions, and thus it is natural to make Q functions update quicker than the Whittle index updates. This technique has also been used in [3, 57]. Second, from the perspective of theoretical performance analysis, this has been widely and theoretically studied in two-timescale stochastic approximation (2TSA) literature, e.g., [18, 19, 20, 21, 38],  with two learning rates, i.e., $\\eta_{n,k}=o(\\alpha_{n,k})$ (see lines 121 and 119). Indeed, by controlling these parameters as in two-timescale and as defined in Theorem 1 (line 212) , we achieve the best-known convergence speed $\\mathcal{O}(1/k^{2/3})$.\n\n\n"}, {"review_id": "ISIHtIpmrr", "reviewer": "Reviewer_rZoR", "summary": "This paper investigates the finite-time analysis of the Whittle index-based Q-learning policy for the RMAB problem under neural function approximation. The authors formulate the algorithm as a nonlinear two-time-scale stochastic approximation problem and present a convergence rate of $K^{2/3}$.", "questions": "Since two-time-scale stochastic approximation has been extensively studied recently, could the authors clarify the novel main technical contributions of this paper?", "limitations": "More limitations of the approach should be added.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The Neural-Q-Whittle algorithm eliminates the projection step.\n2. The paper provides finite-time analysis.\n3. Simulation results are included to verify the convergence performance.", "weaknesses": "1. It is unclear whether the approximated Q-functions converge or not.\n2. The errors diminish as $m\\rightarrow \\infty$, indicating the need for overparameterization.\n3. The simulation setting is too simple to sufficiently demonstrate the advantages of neural approximation. Consideration of a larger state and action space is warranted.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review and constructive comments. Here we would like to address the reviewer's concerns and hope that can help raise the rating of our paper. The detailed responses are as follows:\n\n**Weakness #1:** It is unclear whether the approximated Q-functions converge or not.\n\n**Our Response:** Thank you for this question. Yes, the approximated Q-functions converge. Need to mention that due to the two-timescale nature for the updates of two coupled parameters (i.e., Q-function values and Whittle indices) in our proposed Neural-Q-Whittle, we focus on the convergence rate of these parameters rather than the convergence rate of approximated Q-functions as in [13, 22, 58]. Our key technique is to view Neural-Q-Whittle as a two-timescale stochastic approximation (2TSA) for finding the solution of suitable nonlinear equations. **Since we have theoretically shown that the parameters can converge to its unique optimal value in Theorem 2 when the neural network function $f$ is linearized as $f_0$,  the convergence of parameters in the original neural network function $f$ is established by adding the error between $f$ and $f_0$ introduced by the local linearaiztaion as in Theorem 1.  As long as $m\\rightarrow\\infty$, the learned parameters converge to the true optimal parameters with the convergence speed $\\mathcal{O}(1/k^{2/3})$.**\n\n**Weakness #2:** ...$m\\rightarrow \\infty$ ...\n\n**Our Response:** Yes, that is true. The overparameterization is important in characterizing the convergence of Q-learning with neural network function approximation as in [13, 22, 58]. For a small $m$ value, there will always be a non-diminishing error in the convergence bound. \n\n**Weakness #3:** ...larger state and action space is warranted...\n\n**Our Response:** Thank you for your suggestion.  Since we are learning the Whittle index for restless multi-armed bandits (RMAB), the action space is two, i.e., 0 and 1 in the RMAB literature. In addition, the true Whittle index for the general RMAB problem is hard to be solved and may not have a closed-form solution. Hence, we consider a special queueing scenario of the RMAB problem where the state of each arm evolves as a controlled birth and death process as [M. Larrnaaga, U. Ayesta and I. M. Verloop, Dynamic Control of Birth-and-Death Restless Bandits: Application to Resource-Allocation Problems].  Per the reviewer's suggestion, we consider a larger state space, i.e., an arm with 51 states, which range from 0 to 50, representing the queue length. We randomly select a state and compare the learned Whittle index by our Neural-Q-Whittle with all other benchmarks in this paper.  For these experimental results, **Please kindly refer to the pdf in the General Response.** Again, it is clear that we make the same observations as we have in current experiments.  Since we will have an additional content page, we will add these results and discussions in the camera-ready version.  Finally, we note that although this work focuses on the theoretical convergence analysis of Q-learning based Whittle index under the neural network function approximation, it might be promising to implement it in real-world applications to fully leverage the strong representation ability of neural network functions, which serves as future investigation of this work.\n\n**Your Question #1:** Since two-time-scale stochastic approximation has been extensively studied recently, could the authors clarify the novel main technical contributions of this paper?\n\n**Our Response:** Thank you for this question and providing us an opportunity for clarifying. Two-timescale stochastic approximation (2TSA) has indeed been extensively studied as the references cited in our work [3, 18, 19, 20, 21, 38, 57] and many others. However, most of the current works focus on either linear or nonlinear with i.i.d noise [3, 18, 19, 21, 38, 57]. This may not be the real-world cases for reinforcement learning since the noise observed in each iteration is often not i.i.d. but Markovian. To our knowledge, the only work that considered Markovian noise is [20], which leveraged the same techniques in i.i.d noise setting as [19],  to explicitly characterize the covariance between the error caused by Markovian noise and the parameters’ residual error, leading to the convergence analysis much more intrinsic. Moreover, the analysis in [20] relies the strong monotone and smoothness of the considered functions. Unfortunately, these properties do not hold for the general neural network function as considered in our paper.  **Please kindly refer to the table in the pdf in General Response.**\n\nIn this paper, we addressed two challenges that remain open in most of previous works. First, we removed the addition projection step introduced to stabilize the reinforcement learning due to Markovian noise. Second, we come up a new manner to deal with the non-linear neural network functions in a two- timescale stocahstic approximation framework, which is to deal with a local linearized neural network function first and then characterizing the error between the local linearization and the original neural network function. "}, {"review_id": "hRmtsXOSm2", "reviewer": "Reviewer_ZyEQ", "summary": "This paper presents a neural Q learning method to compute the Whittle indices in restless multi-armed bandit problems. The paper provides an algorithm using two-timescale stochastic approximation (2TSA) to update the parameters in the neural networks and the Whittle indices jointly with different learning rates. The authors also show that the 2TSA method guarantees convergence to the optimal/approximately optimal solution of Whittle indices. One of the major contributions is the breakthrough of not using projection step in the 2TSA algorithm. The algorithm proposed by the authors doesn’t require the functional class to contain the optimal functional approximator. The corresponding approximation guarantee also shows an additional term dependent on the distance of the true optimal to the span of the functional bases used in neural networks. Lastly, the authors provide experiments to show the convergence of the proposed algorithm and empirically verify the assumptions made in the paper.", "questions": "**Question 1**:\nEquation 3: the Whittle index defined by Whittle is defined as the Lagrangian multiplier such that the Q values of action 0 and 1 are identical, i.e., whittle index $\\coloneqq  \\inf_\\lambda \\{ Q_n(s,1;\\lambda) = Q_n(s,0;\\lambda) \\}$, where the Q functions are functions of lambda (Lagrangian multiplier) and thus parameterized by lambda. However, your definition in Equation 3 is defined as the difference between Q values, i.e., whittle index $\\coloneqq Q_n(s,0) – Q_n(s,1)$, where the Lagrangian multiplier for defining the Q values is also not specified. To my knowledge, this is not equivalent to the original Whittle index definition. The original Whittle index is defined based on the solution to Lagrangian relaxation, but yours doesn’t have this property. Please clarify/justify why you can define Whittle index in this way or provide any references supporting your claim. And please also clarify how this definition impacts you downstream analysis.\n\nI have also checked your references in [3,23] are also aligned with the original Whittle index definition (Whittle index defined such that Q(s,0) = Q(s,1)). Please see Equation (4) in [23] and Equation (11) in [3].\n\nEquation (13) will also be impacted by the definition of Whittle index. So does the analysis in Equation (21) and Lemma 2, which will no longer be linear.\n\n\nReferences:\n\n[3] Konstantin E Avrachenkov and Vivek S Borkar. Whittle index based q-learning for restless bandits with average reward. Automatica, 139:110186, 2022.\n\n[23] Jing Fu, Yoni Nazarathy, Sarat Moka, and Peter G Taylor. Towards q-learning the whittle index for restless bandits. In 2019 Australian & New Zealand Control Conference (ANZCC), pages 249–254. IEEE, 2019.\n\n---\n\n**Question 2**:\nDo other choices of step size sequence $\\alpha$ and $\\eta$ work as well?\n\n**Feedback 3**:\nEquation 18 is the linearized version of Equation 6 where the coefficient associated to the linear term is defined by the initial point $\\theta_0 = [w_{r,0}]$. The definition is correct but slightly unclear.", "limitations": "- Different definition of Whittle index: if this is true, then the analysis might be restricted to the definition shown in the paper.\n- Linearization: the authors need to linearize the Lyapunov function to enable the theoretical analysis. I believe this is the reason why the authors focus on 2-layer neural networks (only input and output and a ReLU activation function). This can limit the functional approximator class to such neural networks only. For more complex NN structures, the same linearization trick and analysis don't apply anymore.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I like the idea of projecting the neural networks using ReLU to linear functions to enable downstream analysis. The paper also generalizes the theoretical analysis in previous work to quantify the impact of approximation error in the functional approximator class. I didn’t go through the appendix, but the proof sketch is clear to me. Overall, the paper is nicely written with new theoretical contribution compared to the previous work. It would be great if the authors can further emphasize and summarize the contributions in the theoretical analysis that are incurred due to not using projection steps. The convergence rate also matches the previous work using projection steps.", "weaknesses": "The comparison to the previous algorithm is not clear. I didn’t fully understand why the previous algorithm requires a project step to force the parameters in a bounded set and why your algorithm doesn’t. I believe it is due to the analysis in the convergence guarantee where unbounded parameters can lead to useless bound or divergence. Could you please clarify and emphasis this in the paper more to highlight your contribution more clearly? Especially this seems to be the major contribution of the paper. It deserves a larger portion of the paper to clarify it.\n\nPlease also clarify why the definition of Whittle index is different from Whittle et al. and most of the literature. Please see below for more details. I am worried that the different definition can impact the convergence analysis (especially the linearity and Lipschitzness in the proof). Please either justify the use of your definition and any references showing this different definition is valid, or show us that the analysis is not impacted by the definition.\n\nThese two are my major concerns of the paper. Please clarify them and I am happy to update my score based on the response.\n\n[Answered by the authors during the rebuttal]", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review and constructive comments. Here we would like to address the reviewer's concerns and hope that can help raise the rating of our paper. The detailed responses are as follows:\n\n**Weakness \\#1:** ... project step...\n\n**Our Response:** Thank you for this insightful comment. The projection step in reinforcement learning originates from [6], which provided the first finite-time performance of TD learning with linear function approximation. Due to the Markovian observation noise, the dependent nature of the data introduces a substantial technical challenge: the algorithm’s updates are not only noisy, but can be severely biased.  Hence, [6] proposed a variant of TD that projects the iterated parameters onto a norm ball. This projection step imposes a uniform bound on the noise of gradient updates across time, which is needed for tractability. Later on, similar techniques have been extended to Q-leaning with linear function approximation [62, 63] and neural network function approximation [13, 22, 58]. Note that all these works **target the convergence of Q function values**, where the bounded gradient plays a key role. \n\nTo remove the projection step under the Markovian observations, [47] is the first work that treats the TD-learning with linear function approximation as a linear stochastic approximation with Markovian noise and shows **the convergence of the parameters in terms of Lyapunov stability theory for linear ODEs by designing a suitable Lyapunov function.** Since the stochastic approximation-based technique tracks the drift of parameters rather than the Q function values, there is no need to track the gradient for parameter update. Instead, we may leverage other properties such as Lipshcitz continuity of the approximate linear functions, which we proved as in Lemmas 1-3 (lines 268-274). Later on, [15] extends the result to Q-learning with linear function approximation. \n\nTill now, the finite-time performance for Q-learning with neural network function approximation is unexplored, let alone our proposed Q-learning-based Whittle index with neural network function approximation (Neural-Q-Whittle). Our goal is to provide the first-ever finite-time convergence of Neural-Q-Whittle without the additional projection step by treating it as a two-timescale stochastic approximation under Markovian observations, which tracks the drift of parameters rather than Q function values.  \n\n**Weakness #2:** ...whittle index definition...\n\n**Our Response:** We thank the reviewer for this insightful comment and sharp observation. We believe this is a misunderstanding here, mainly due to our unclear statements. We are sorry for this and will make it clear in the camera-ready version. Below, we provide some clarifications.  \n\nIn our paper, the Whittle index is still defined in the same manner as in conventional works [3, 23], which is the Lagrangian multiplier such that the Q values of action $0$ and $1$ are identical. With that being said, we have the following equation for action being $0$ and $1$, \n$$\nQ_n(s,0)+{\\beta}=r_n(s,0)+\\lambda+\\sum_{s^\\prime}p_n(s^\\prime |s,0)V_n(s^\\prime), \n$$\n$$\nQ_n(s,1)+{\\beta}=r_n(s,1)+\\sum_{s^\\prime}p_n(s^\\prime |s,1)V_n(s^\\prime). \n$$\nHence, we have\n$\nQ_n(s,0)-Q_n(s,1) =r_n(s,0)+\\lambda+\\sum_{s^\\prime}p_n(s^\\prime |s,0)V_n(s^\\prime)-r_n(s,1)-\\sum_{s^\\prime}p_n(s^\\prime |s,1)V_n(s^\\prime), $\nwhich means that $\\lambda^*\\_n(s)$ is the value to make $Q\\_n(s,0)-Q\\_n(s,1)=0$.\nThis leads to the definition of Whittle index in Equation (3), i.e.,\n$$\n\\lambda\\_n^*(s) = r\\_n(s,1)+\\sum_{s^\\prime}p_n(s^\\prime |s,1)V\\_n(s^\\prime)-r_n(s,0)-\\sum_{s^\\prime}p_n(s^\\prime |s,0)V_n(s^\\prime).\n$$\nThis is exactly the same as Equation (4) in [23] and Equation (11) in [3]. Note that in current Eq. (3), the $Q_n(s,0)-Q_n(s,1)$ is redundant and should be removed. We thank the reviewer again for this comment and we will make this part clear in the camera-ready version. \n\n**Your Question #2:** ... step size...\n\n**Our Response:** Yes. As long as the stepsize sequences $\\alpha$ and $\\beta$ satisfy the conditions in line 119 and line 121, an almost-sure convergence for learning Whittle index by Q-learning has been characterized in [3]. However, in this paper, we aim to provide the first-ever finite-time convergence rate by carefully designing the stepsize sequences as in Theorem 1 (line 212), which achieves the best-known convergence speed $\\mathcal{O}(1/k^{2/3})$ as the general linear and nonlinear 2TSA with i.i.d noise [19, 21]. \n \n**Limitation #2:** ... 2-layer NN...\n\n**Our Response:** Thank you for this insightful comment. Unfortunately, we are afraid that we cannot agree with the reviewer's argument. The local linearization is a common trick to tackle the non-convexity of the original neural network function in finite-time analysis [13, 22, 58]. The major difference is that they characterize the convergence of Q function values while we track the drift of parameters. That is the fundamental reason why they need a projection step for parameter update while we do not require it. The local linearization technique can indeed be extended to multi-layer neural network function as in [58]. \n\nThe reason why we consider a two-layer NN is that the two-layer NN serves as the basis of multi-layer NN and it has strong representation power as the size $m$ goes large [13, 22].  The theoretical results of two-layer NN provide the fundamentals to characterize the result of multi-layer NN, just as what has been done in [13, 22].  In the current manuscript, our focus is to provide a fundamental theoretical analysis of a two-timescale  Q-learning-based Whittle index with neural network function approximation, which is already an open question and quite challenging, for which we make clear contributions as we summarize in the introduction. We thank the reviewer for pointing out this question, and extending the current framework with multiple layers is our future research. "}, {"review_id": "a20eINEs2g", "reviewer": "Reviewer_PM6q", "summary": "This paper proposes a neural network approach to learning the Whittle index policy. In addition, the paper gives a finite-time analysis for the algorithm, and shows that the algorithm indeed learns the Whittle index values for restless bandits. \n", "questions": "Question: the neural network is using ReLU activation functions. Would the finite-time analysis be applicable to other activation functions such as tanh? ", "limitations": "The limitations are addressed by the authors in the paper in regards to the finite-time analysis. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "The paper’s sections are well-written and the technical claims of the paper are sound. In addition, the paper provides sufficient analysis of the two-timescale stochastic approximation used here (to learn the Whittle index values and the action-value function for each arm). Also, the paper offers finite time performance bounds in the neural network setting which is a largely unstudied area.\n", "weaknesses": "While the paper is well-written, I believe it’s better if less remarks/lemmas blocks are used and if they are written as paragraphs. Other than that, the technical details appear correct to the best of my knowledge. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review and constructive comments, as well as giving the positive rating of our work. Here we would like to address the reviewer's concerns and hope that can help raise the rating of our paper. The detailed responses are as follows:\n\n**Weakness #1:** While the paper is well-written, I believe it’s better if less remarks/lemmas blocks are used and if they are written as paragraphs. Other than that, the technical details appear correct to the best of my knowledge.\n\n**Our Response:**  We thank this reviewer for this suggestion. We will modify those remarks and lemmas in the camera-ready version per your suggestion.\n\n**Question #1:** The neural network is using ReLU activation functions. Would the finite-time analysis be applicable to other activation functions such as tanh?\n\n**Our Response:** We thank this reviewer for this insightful comment. The finite-time analysis of Deep Q-Networks (DQN) [13, 22, 58] and references therein focuses on the ReLU (Rectified Linear Unit) activation function, as it has certain properties that make the analysis tractable. ReLU is piecewise linear and non-saturating, which can simplify the mathematical analysis.\n\nApplying the same analysis to other activation functions like the hyperbolic tangent (tanh) could be more complex. The tanh function is smooth and saturating, meaning that it can squash its input into a small range. This can lead to different behaviors during training, such as vanishing gradients, which might not be captured by an analysis designed for ReLU. It is usually used in classification between two classes and rarely used in deep Q-learning. \n\nTo the best of our knowledge, the research for other activation functions on DQN is quite limited, which is an open research problem at current stage. "}]

Author rebuttal:
The attached Pdf contains a table for **Reviewer KAmk** and **Reviewer rZoR**, and a figure for **Reviewer rZoR.** The detailed response to the corresponding comments are provided below in our rebuttal to each reviewer. 

Meta-review: Reviewers unanimously agree on acceptance.
Please consider the authors comments regarding several confusing parts in the manuscript, and be sure to fix them for the camera-ready version.
Decision: Accept (poster)