Achieving $\tilde{\mathcal{O}}(1/N)$ Optimality Gap in Restless Bandits through Gaussian Approximation
Authors: Chen YAN
Weina Wang
Lei Ying
Venue: NeurIPS 2025 spotlight ()
Keywords: Markov Decision Processes
Restless Bandits
Gaussian Approximation
Stochastic Optimization
Primary area: reinforcement_learning
TL;DR: We propose a Stochastic-Programming-based (SP-based) policy for finite-horizon RMABs that achieves an optimality gap of $\tilde{\mathcal{O}}(1/N)$, addressing the limitations of Linear-Programming-based (LP-based) policies in degenerate settings.

Abstract: We study the finite-horizon Restless Multi-Armed Bandit (RMAB) problem with $N$ homogeneous arms. Prior work has shown that when an RMAB satisfies a non-degeneracy condition, Linear-Programming-based (LP-based) policies derived from the fluid approximation, which captures the mean dynamics of the system, achieve an exponentially small optimality gap. However, it is common for RMABs to be degenerate, in which case LP-based policies can result in a $\Theta(1/\sqrt{N})$ optimality gap per arm. In this paper, we propose a novel Stochastic-Programming-based (SP-based) policy that, under a uniqueness assumption, achieves an $\tilde{\mathcal{O}}(1/N)$ optimality gap for degenerate RMABs. Our approach is based on the construction of a Gaussian stochastic system that captures not only the mean but also the variance of the RMAB dynamics, resulting in a more accurate approximation than the fluid approximation. We then solve a stochastic program for this system to obtain our policy. This is the first result to establish an $\tilde{\mathcal{O}}(1/N)$ optimality gap for degenerate RMABs.

Achieving ((/NN) Optimality Gap in Restless Bandits through Gaussian Approximation
Chen Yan'
Weina Wang?
Lei Ying'
Uniieesity of Michigan, Ann Arbor (chenyaa, leiying)@umi Gumich edu
Carnegie Mellon University
weinawecs. cmu. edu
Abstract
We study the finite-horizon Restless Multi-Armed Bandit (RMAB) problem with homogeneous arms. Prior work has shown that when an RMAB satisfies a non-degeneracy condition, Linear-Progrann teweear-roogrammin--baasee
(LP-based) policies derived from the fluid approximation, which captures the mean dynamics of the system, achieve an exponentially small optimality gap. However, is common for RMABS be degenerate, in which case LP-based policies can result in a 0(1/ N optimality gap per arm. In this paper, we propose a novel Stochastic- Prochastc-Proggammiing based (SP-based) policy that, under uniqueness assumption, achieves an (1/NN optimality gap for degenerate RMABs. Our approach is based on the construction of a Gaussian stochastic system that captures not only the mean but also the variance of the RMAB dynamics, resulting approximation. We then solve a stochastic program for this system to obtain our policy. This is the first result to establish an (1/NN) optimality gap for degenerate RMABs.
more accurate approximation than the fluid
Introduction
The Restless Multi-Armed Bandit (RMAB) problem is an important framework in sequential decision- making, where decision maker selects a subset of tasks (arms) to work on (pull) at each time step to maximize cumulative rewards, under known model parameters [29]. Unlike the classical (restful) bandit (TT) in the restless variant, the state of each arm evolves stochastically regardless of whether it is pulled. RMABs have been widely applied in domains such as machine maintenance [9] [2].
healthcare resource allocation (22) 223, and target tracking [19] (1). to name few, where optimal maaiingn under uncertainty is critical. A general RMAB is PSPACE-hard [25. and finding optimal policies is computationally challenging, especially as the number of arms grows. Recently, there have also been efforts to use deep learning and reinforcement learning to learn heuristic policies for RMABs, such as
18 24 30 31.
In this paper, we focus on the finite-horizon version of the RMAB problem with N homogeneous arms and horizon H. where each arm follows the same (time-dependent, known) state transition and reward function. While computing the exact optimal policy is impractical, the homogeneity of the model allows for the design of computationally efficient policies. One such class of policies is
'We adopt standard asymptotic notation throughout paper. Specifically, for functions f(N) and gVV).
we write fNN) = (gg(N) if there exist positive constants C and No such that [f[] S CCg(NN] for all N 2 Ng. Similarly, we write f(N) ([g(N)) if g(N) = O(f(N)), and f(N) = ((g(N)) if both f(N) = (g()N) and f(N) = (()(N) hold simultaneously. Additionally, we use O(.) and θ notation to indicate that logarithmic factors are omitted.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

based on fluid approximation, which transforms the original N-armed RMAB problem into Linear Program (LP), and an LP-based policy can be efficiently computed based on the solution the LP.
Optimality gap. In 15 an LP-based index policy was proposed and achieves an o(1) optimality gap. This gap was later improved to O (log N/vN) in [< and subsequently to (LL/VN) in [7]. In the numerical experiments of 7 was observed that while this O(1/VN) gap appears tight for certain problems, in others the gap converges to zero more rapidly. This empirical observation was theoretically confirmed in [36], where it was shown that under non-degenerate condition (formally
defined in Definition 3.1 the gap is at a smaller order of (1/NN)
Non-degenerate condition. This non-degenerate condition has since become a key assumption in subsequent works. [T0] shows that, under this condition, the optimality gap becomes exponentially small when the rounding eπror induced by scaling the fluid approximation by N is eliminated. Further generalizations of the degeeeeeeeete condition have been made [8. extending and conti-con RMABs (also known weakly coupled Markov decision processes). In [35] the non-degenerate condition was further extended to settings with heterogeneous arms.
multi-action
Prevalence of degenerant RMABs. Despite the central role played by the non-degenerate condition, many RMAB problems are degenerate. Notable examples, which originate from real-world appli- cations, have been discussed in g 36 Moreover, numerical study presented in Appendix [B]] revealed that significant proportion (about 50% for some cases) of randomly generated RMABs are degenerate, and almost all of them satisfy the Uniqueness Assumption This highlights the practical importance of addressing degenerate RMABs.
However, to the best our knowledge, in all previous works, when an RMAB degenerate, the best known optimality gap is O(1/VN). It is widely believed that this upper bound is also order-wise tight under LP-based policies, making it O(1/VN). We will formally prove this result in Theorem by using example.
These results led us to ask the following central question this paper:
Does there exist computationally efficient algorithm for degenerate RMABs with optimality gap order-wise smaller than Ol)/VN)?
Contributions. This paper answers the question affirmatively and includes the following results:
Reward per arm
0.76
We construct a Gaussian stochastic system (see (4) that more accurately captures the behavior of the N-system than the fluid system. Unlike the fluid system, which serves as a first-order approximation to the stochastic N-systen the Gaussian stochastic system incorporates both the mean and variance of the N N-system.
0.74
LP based
SP-based
0.72
Optimal
LP bound
N
We demonstrate that the SP-based policy obtained from the Gaussian stochastic system (see Algorithm (I) achieves Ó(1 (1 optimality gap for degenerate RMABs that satisfy the Uniqueness Assumption 4.1 (see Theorem
X optimality gap
0.0
0.4
LP-based
4.1 We fur-
SP SP-based
ther prove that for degenerate RMABs without the Unique- ness Assumption SP-based policy results in provement per arm compared with a large class of LP-based policies (see Theorem 4.3)
0.2
im-
0.0
40
50
60
70
80
Figure 1: Comparison of LP and SP-based policies.
We further compliment our main result by presenting a degenerate example in Section demonstrating in Theo- rem 4.2 that not only the LP-based policy has ((IvVN) optimality gap. but also the LP upper bound has ((I/VN) gap from the optimal value. This indicates that the LP upper bound, which is a widely used baseline, itself is not tight for degenerate RMABs.
As an illustration, consider a degenerate RMAB example with states and horizon of 2 steps (the details can be found in Section 3.3). Given the small problem size, the optimal policy can be computed exactly through brute-force methods. As shown Figure the performance of the policy obtained by solving the Gaussian stochastic system is already very close to the true optimal value.

---

Considering N Xoptimality gap (i.e. the total optimality gap of the N arms with respect to the optimal policy), it remains bounded under the SP-based policy as N increases, which confirms the (1/NN) optimality gap; while the total optimality gap for the L.P-based policy appears grow unbounded.
Related work. A comparison state-of- satte-of-the-are results in finite-horizon RMABs with this work is provided in Table
Table Optimality gap and assumptions in finite-horizon RMABs
Paper
Gap
Assumption
Brown and Smith 7
((/VVN)
General
Gast et al. [T0]
O(e
Non-degeneracy
This Work
O(1/N)
Degeneracy & Uniqueness Assumption 4.1
Gaussian approximations, rooted in the central limit theorem, are widely used to approximate stochastic processes. In heavy-traffic queueing analysis, this yields the diffusson approximation, where the centered, scaled limit a diffusion process; see early work in [4] 5 16 17]. This literature typically studies fixed policies and establishes convergence (or rates) to the diffusion limit. In contrast, we aim to design near-optimal policies for discrete-time RMABs via a second-order Gaussian approximation.
which replaces the original problem with diffusion control problem solved through the Maanitton--cobi-Bllllle (HJB) equation. Recent work (6 shows HJBs arise from second-order value-function approximations of general MDPs. However, solving HJBs is notoriously difficult, especially when diffusion coefficients are control dependent, yielding highly nonlinear PDEs. This actually motivates our alternative second-order approach, detailed in Section
Closer to our setting is approximate diffusion control (e.g..
Notational convention. Vectors are row vectors by default. Throughout the paper, we consider three systems: the N-armed RMAB system, the fluid system, and the Gaussian stochastic system. As general convention, variables and functions with are for the fluid system, while those with are for the Gaussian stochastic system. The terms "action" and "control" are used interchangeably in the context of decision-makee making.
Problem formulation
RMAB model. We consider the H-horizon Restless Multi-Armed Bandit (RMAB) problem with N homogencous arms. Each arm is modeled as a Markov Decision Process (MDP) with state space S H), the decision
= (1, S} and action space A = {0. 1). each time step maker decides which arms to take action 1, also referred to as the pulling action, subject to the budget constraint that exactly aN arms should be pulled. Here 0 < a < and we assume a.N is an integer. After the actions are applied, the N arms evolve independently. Specifically, the state transitions from N to s' S with probability (s s, II PA 8n, an), where (sn: an) denotes the state-action pair for the n-th arm, and Pa( a) is the transition kernel under action a. For convenience, we refer to this RMAB system with N arms as the N-system.
At each time step h, the decision maker collects an additive reward IN (hh(Sna,,)) where (s, a) denotes the reward for the state-action pair (8, a) at time h and is assumed to be nonnegative without loss of generality. The objective is find policy xN which maps the bandit state vector 8y = (81.h: . .8N.)) maximizes the total expected reward per arm over the horizon:
to an action vector a₃ = (01,k, (2.h....,,N. for each h, that
H
N
V = max opt
En [rn ann)]]
(I)
n
h=1
n=1
N
s.t.
Σ an = a.,
1 1 H.
(2)
mm
3

---

To reduce the computational complexity, we leverage the fact that the N arms are homogeneous and aggregate the states of individual arms, This gives us simplified representation of the bandit state, which facilitates subsequent analysis and policy design. Specifically, we represent the handit state at time as vector X = ($) E A where each (s, denotes the fraction of arms in state $ E S. Here, A is discrete subset of A the probability simplex over S, such that each A satisfies that Nx has all integer entries. Similarly, we represent the action at time vector Yn (Yn (s, a) s... E AN where each (s, a) denotes the fraction of arms in state taking action a. We treat Y as a row vector of length 2S. We also write (x(:,)) = (Yx 0)) and (= 1) = (Yi, (s, 0)) which are both row vectors of length S.
Under the new state and action representation, given an action Y, = Yn. the state evolves as
1 Evfa (yh).
X
N
where 0/ (yr) E N follows a multinomial distribution multi(Nya(s,,)) PN( |s, a)), and the U(aaa) (yn)'s for different (s, aY's s are independent.
Under the new state and action representation, policy x maps the state X to action vector Yn for each h. We also rewrite the reward function as a vector ra = (rx(s, ())(s, E R22, Suppose the initial state of the N-system is X2 Xini E A Then the objective of the RMAB problem can be reformulated as:
H Σ Y
V-N ope (Xini, 1) = max
(4)
h=1
s.t. Σ 1)= 15
(5)
Yx(+0)+ + (x(,))= = X YA Y 1sh5 H.
(6)
Here corresponds to the budget constraint, and (6) ensures that Y, a valid action for state X,,-
Fluid approximation. One classical approach to address the complexity of RMAB is to consider a fluid approximation in 10 15 34 36), where the stochastic state transition is replaced by its
expected value, leading to deterministic transition at each step:
Σ yn,s, Pa | 5,a
Xh+1
This fluid system smooths out the stochastic fluctuations in the N-system and leads to the following Linear Program (LP), which we refer as the fluid LP:
H
Vxp(Xinis 1)
max (kn.Ne)ae 2.....
rayn
(8)
s.t. Σ (n =a, 1 15hs H,
yn(. 0) + (n(,1) = xx((),
yb 20 1shsH, (s (,),,), 1 (11)
(10)
= Xini x++1(+) = = Σ
8.0
Let x" (x.))E(1.2....1) and y* = -yi))e(L,....... be an optimal solution to this fluid LP. Note that this LP can be efficiently solved. Furthermore, it has been shown that V.N (Xii 1) < (x.p(xini 1); see, for instance, [36] Lemma 1] or (32 Lemma 3]. That is, the optimal value of the LP provides an upper bound on the optimal value of the RMAB problem. Based on the solution to this I.P, L.--aaed policies can be obtained but have ((1v/N) optimality gap per arm degenerate RMABs, as we pointed out in the Introduction.

---

3 Gaussian approximation and SP-based policy
3.1 Gaussian stochastic system
The performance of LP-based policies is inherently limited by how accurately the fluid system approximates the original N-system. To design policies that outperform the LP-based policies, we construct a Gaussian stochastic system that better approximates the original N N-system by capturing not only the mean but also the variance of the system. This Gaussian stochastic system is centered around y", an optimal solution to the fluid LP. We then search for an optimal policy for the Gaussian stochastic system in neighborhood of y", which adjusts y" to account for the stochasticity. This policy is then applied to the N-system after properly handling the integer effect.
Specifically, we construct a Gaussian stochastic system with state space A and action space A 25 The system has the same initial state Xini as the N-system. Under action vector yh. the state of the Gaussian stochastic system the next time step, Xn41, is a random vector of the following form:
Xa+1 = Projas
Σ (s P) s,a) + Zn/VNN 8,0
(12)
where Zn is a Gaussian random vector with distribution N 10, and Z, 's are independent across steps. The covariance matrix I' (y%) is constant matrix independent of N, with its explicit expression given in Appendix A The projection, Projas (.), is onto the simplex A under the fz-distance. This projection will not used with a high probability. Indeed, it can be shown that E., 3n (s, P. s, s, + Zn/VN E A occurs with probability - ((1/Nlog ), see Lemma C.8 of 33 for proof.
We now explain how the Gaussian stochastic system captures the mean and variance of the N-system. Suppose the action at time h is yn- Ignoring the projection, we have X = E.,a y/ (s, P The term Es.a yh (8, a P. 8, a) is the expectation of the state X in the N-system, which is the same the state X1+11 in the fluid system under action Yи- The additional term, Zz/ C4/VN, is random, and by construction, its covariance matrix matches that of X in the N-system if yı yī. Therefore, this term captures the variance of the N-system when ya is close to the optimal solution yī, of the fluid L.P
8, s, +
We remark that key innovation of our approach is to replace the otherwise (state, dependent diffusion terms with sagte.action)-indeeedeeee ones. We construct the Gaussian system so that the covariance of the noise is on yı. This enables the use of stochasti-proorrmmming techniques that require action-independenn randomness, such as the EDDP algorithm (20) Algorithm 3] we employ in Section 5 Conceptually, this is a further "simplification" of the classical diffusion approximation: although the covariance is fixed at yj,, the resulting approximation retains the same order of error for our problem (a point established in Theorem 4.1p while remaining computationally tractable.
from the fluid-optimal solution - than depending
This simplification is justified by scale separation: in the N-system, stochastic fluctuations are O(I//N) relative to the deterministic drift (see the 1/ I/VN factor multiplying Z, in (12)). Hence the covariance induced by the fluid-optimal action serves as robust surrogate for the action-dependent covariance without changing the asymptotic accuracy, a property that typically does not hold in traditional diffusion control but is available here due to the central limit theorem scaling.
3.2 Stochastic- Stochastic-Programmiit Pwogramming- (SP-based) policy
After constructing the Gaussian stochastic system, we search for an optimal policy in the Gaussian stochastic system. However, we restrict the search to neighborhood of y", since the Gaussian stochastic system closely approximates the N-system when the state and action of the N N-system stay close to y". In particular, given a fixed parameter dN == 2log N/VN- ((1//(()))) we define the following policy class:
15y (y") == { V1 S h H, [|= hi) vullo I KZLŌN, if ||2,, - x7.100 S ZNONs
(13)
π = Tre for a predefined policy Tpres if ||xn - 11 > 2nŌN}.
5

---

Algorithm Stochastic-Programming
(SP-based) policy
1: Input: An optimal solution y" to LP (8; constants 2h. 8n and K; a predefined policy "pre
2: if y" is non-degenerate then
3: Use an LP-based policy
4: Break
5: end if'
6: Solve the Gaussian stochastic program (4) to obtain an optimal policy #N Nlx (y*)
7: for h = 1 to H do
8: Xp. f- state of the N-system at time
9:
if | x l0 S 2,,N then
10:
YA round( NW* (xh, h))
11:
else
12:
YA round (xn, (x)hh)) h))
13:
end
14: Apply action Yn
15:
end for
Here is positive constant with value x max {2 + 68, 3 + 2r max HS/a), where Tmax maxs,a,A Th (8, a); a is a constant depending on the fluid LP; 2n for S I H is a recursive sequence. The explicit expressions for these constants collected in Appendix A of [33] We note that all of them are independent of N, and can be computed or estimated solely from the fluid LP (8.
We now explain the reasoning behind the definition of the policy class 1s (y*). We restrict corrections ((L/VN) neighborhood of the fluid-optimal state-action. When the LP has unique solution, an optimal N-system policy lies within this neighborhood (see Lemma C.I of 33 for a proof); hence our restriction retains optimal policies while ensuring that the second- order approximation incurs only (11NN) error (see Lemma C.4 of [33 for a proof). Enlarging the neighborhood inflates the approximation error, whereas shrinking it risks excluding the true optimum-so so O(1vVN) is the "right" scale for method. Moreover, since the smallest gap of interest O1//N) and the process leaves this neighborhood with probability ((1 N) (Lemma C.8 of (, the contribution of out-of-neighborhood behavior is negligible. Consequently, we not distinguish between policies optimized only locally and those also optimized outside the neighborhood; whenever the state exits, we simply follow predefined policy in [13
We then formulate the following Gaussian stochastic program (SP):
H Σ
max xEllaN(y (y*)
E FA
Y
(14)
hm1
s.t. Vn(s,1) =)= SSASH,
(15)
Yx(:0) + YA(,1)= Xn, 2,20, 15hSH,
(16)
X Projae
En(s,,)) (8,0) Zn/VN) 1shSH-1.
(17)
8.0
We now present our SP-based policy, formally described in Algorithm I The core idea of this policy is to solve the Gaussian stochastic program and obtain an optimal policy N.* E 116x (y*). This policy then applied the .V-system through a simple rounding procedure. It guarantees that the action generated by the algorithm pulls an integer number of agents. Since when computing the first- and second-order approximations, we extend the state and action spaces from their original discrete sets (with granularity 1/N) to continuous-vall valued probability simplices. The action computed this continuous domain must subsequently be converted back to the discrete domain, ensuring that all values multiplied by N are integers and thus applicable to the N-agent problem. This rounding procedure is explicitly detailed Appendix which we showed alongside that the rounding error is of order (L)N).

---

We remark that we only use the policy #* when the RMAB is degenerate, When the RMAB non-degenerate, our policy defaults to LP-based policy. which prior work (see Introduction) has shown achieve an exponentially small optimality gap (in terms of N) relative to LP. The definition of non-degeneracy is given below, and it is easy for an algorithm to check whether an RMAB is non-degenerate not.
Definition 3.1 (Non-degeneracy 8 36]). An RMAB is non-degenerate if. its corresponding fluid LP (8) admits optimal solution y", such that for each h with 1 S h S H, there exists at least one state 8 E S such that yi. (s, 0) and yi (8, 1) >
3.3
Illustration of the SP-based policy degenerate example
We illustrate the SP-based policy via two-state RMAB with horizon H = 2 and pulling budget
0.5. The rewards are given by Tı (1, = (2
1, with all other (h, 8, a) at-uulee being
(s, a) 0. The transition probabilities at / = 1 are Pi (1 1,1) 0.2, P1 1, 0) 0.9,
(1 2. = 0.7, (1 2, = 0.25. Assume at = 1 there are N/2 arms in state 1, and the other N/2 arms are in state 2.
is to pull as many arms in state as possible, i.e., Y),1, min (0.5, (1)}. Therefore, we only need decide the optimal action the entries of Y, are all determined by (1, 1) as follows
N -ysystem problem. Note that time h 2, only r2( so the optimal action
1. We further notice that since (1) (2) = a 0.5,
(1, (2, 1) 0.5 (1, (2 (1,
Therefore, we only need to optimize (1, 1). The N-system optimal policy is given by the solution of the following problem
max (1.1)
(1, + [mi {0.5, X2(1)))
(18)
Fluid LP and its optimal solution. In the fluid system, we replace X2(1) with mean x2(1) =
Es, yn (8. P a, = 0.8 - 1.15 y1 (1, Then the fluid LP
LP
max (L.)).0
(1, + min {0.5, 0.8 1.15 (1,
(19)
which exchanges the expectation and the min operator in the N-system problem (8)) The optimal solution is yf (1,1) = 0.2609. One can verify that this problem is degenerate (see Definition 3.1.
SP-based policy.
Given the fluid solution y" above, the corresponding Gaussian stochastic program
VN }
max (1.1g0)
(1, +E min 0.5, 0.8 1.15 x Y (1,
(20)
where Z1 (0, 0.1624). Since we are searching for an optimal solution around yi. let Y (1,
(1, V Then the stochastic program can be written as
1 VN
vi 1..5
+05
max (c + E mmi (0, Zi 1.15c))),
which is equivalent to the following problem
max c E [min (0, 21 1.15c)]
There exists an explicit and unique solution to the problem above, and the solution can be numerically computed and is oi 0.3940 (for more details please refer Appendix D of (33).. Therefore, the SP-based policy is given by (Y]tt() (1) = policy outperforms LP-based policies, illustrated in Figure [ in the Introduction.
(/940///N) This ba-based
7

---

Some insights. We compare the fluid approximation in (99) with the Gaussian approximation in (20) when they both take an action y1 (1
vi + c/ e/vN for positive constant In the fluid system, the reward for h = 2 is min (0.5, 0.8 - 1.15 x yn (1,1)), which is capped at 0.5. One can verify that this deviates from the value [min f0.5, (2(1) in the N-system by @(/vVN,, caused by the exchange the expectation and the min operator. In contrast, in the Gaussian stochastic system,
min { 0.., 0.8 1.15 1),
Z1 VN }1
Z1 1.15c
}
0.5 0.5 E min 0.
VN
which can be verified be O(1/N) away from the value E [min {0.5, X2
|| in the N-system and thus giving a better approximation. This better approximation allows us to find a better policy near vi (1, 1). The inaccuracy of the fluid approximation is in fact fundamental reason that LP-based policies have a ((1/v/) optimality gap for some degenerate RMABs, whereas the correction in our SP-based policy reduces the (I1/vN) inaccuracy to O(/NN).
Main theoretical results
In this section, we present our main theoretical results. We will frequently use the following quantities. Let V (xx, h) and Q (x, denote the value function and Q-function of policy evaluated in the N-system; and VAN (xn, h)) and QN (X,, Vn, h) denote the value function and Q-function of policy æ evaluated in the Gaussian stochastic system. Further, we consider the following optimal policies within the policy class II (y"):
# Ni* E arg max V.N (xn, rEllay
which is referred to as the Saaaly--P-optimall policy. We sometimes say that we apply the locally- SP-optimal policy N.* to the N-system and denote its value function ViN. (Xp, h), with the understanding that we apply N.* with the rounding procedure, detailed in Appendix A
4.1 Global optimality
Assumption 4.1 (Uniqueness). The fluid LP in 8 has unique optimal solution y".
Note that once we obtain an optimal solution to the LP, verifying uniqueness is straightforward
Theorem 4.1: prove gap ō(1 Ō(/NN
3
Theorem 4.1 (Global optimality). Consider an RMAB that satisfies the Uniqueness Assump- tion
VN opt
PN N.
VV
4.1 Then the locally-St Decall-SP-opptinne SP-omiimal policy, a N.-
Lemma C.1 (P roximity of optimal policy)
when applied to the N -ssystem (with round- ing). achieves an optimality gap of OLLNN): ie.,
Ō(/N
Ōa/N)
Lemma C.2
Lemma C.3 (Evaluation
V ope (Xini, 1) V.N. g..- (Xii, 1) Ō(1NN)
(Value difference)
difference)
where V.N. is the optimal value function, and N is the value function of N.*, both in the N- N-system.
Figure 2: Proof Structure of Theorem 4.1
A detailed proof of Theorem 4. is presented in Appendix C of [33] Below, we provide an outline and highlight some novel and technically interesting components of the proof. It consists of proving the following statements, as illustrated in Figure
Prove that V.N VN opt n, (Lemma C.I of (31 where N.* is the locally optimal policy within the policy class Tay (y*). This is proved by showing that a (globally) optimal policy for the N N-system belongs to the policy class 11 (y") under Assumption 4.1
8

---

Prove that |V x, (x, h) V. RAN.- (x, h)1 = O(1/N) (Lemma C.2 of (33)) and aa. (x.h) h) V.N HN,- (x, h)] ((/NN) (Lemma C.3 of (33). These two lemmas are enabled by the fact that we restrict the policies N-\ and H to 5 (y"), ie, a ( -niighhhoooo of y", which translates into a Wasserstein distance of ((1/N) between the respective next-state distributions in the N --system and in the Gaussian stochastic system.
We next highlight two interesting components in the proofs.
Characterization of optimal policies in the N-system. Lemma C.1 of [33] establishes that under Assumption 4.1 there exists an optimal policy of the N-system whose actions are close to the optimal fluid solution y". This result is noteworthy because optimal policies of the N-system are not well-understood in the literature. Prior work often circumvents this by only studying the L.P upper bound VLP, which can be loose as shown in Theorem 4.2
Approximate Lipschitz continuity in the Gaussian stochastic system. A key step in proving Lemmas C.2 and C.3 of (33) is to establish approximate local Lipschitz property of the value function g.N.- in the Gaussian stochastic system, where restricting the policy to NN introduces technical challenges. We overcome these challenges through the careful construction of an action mapping.
4.2 The ((1/VN) optimality gap of LP-based policies
To complement Theorem 4.1
we next present a result showing that the (LIv/N) optimality gap is fundamental to large class of LP-based policies. Specifically, consider the following policy class, which includes a large class of L.-based policies such as those 7 T0 36
Iuid (y") = T [xx h) yill S x||x|, - -x, VISASH),
(21)
where (x", yx) )
is optimal solution of the fluid LP (8) It has been shown in 110 Theorem 1] that any policy in (y") has an (L1/V optimality gap. We now show that there exist RMAB
instances where this optimality gap order is tight. The result is established based on the example given in Section 3.3] and the detailed proof is presented in Appendix of 33
Theorem 4.2 (Fluid gap). There exist RMAB instances for which all LP-based policies in Iy have an ((/vVN) optimality gap; i.e., Vopt (Xmi; 1) - Valiaa (xiis,Xins, (Xini, 1) = Ø(1 0(1/VN), where V.N. is the optimal value function, and V.N fluid is the value function of the optimal policy within the policy class Iyaiid(")) Moreover, there is ((1/VN) gap between the optimal value of the N-system and the optimal value of the fluid LP (8) i.e. V (XP 1) VoN (Xii, 1) O(1/NN).
We remark that although this theorem is proved via specific example, we believe the result hold more broadly for many degenerate RMABs. The O /N) optimality gap of L.P-baeed policies stems from the O(1/VN approximation error in the fluid approximation, which arises when exchanging the expectation and the minimum operator, as shown in the example in Section 3.3 This phenomenon common degenerate RMABs.
4.3 Performance improvement
Under the Uniqueness Assumption 4.1 we have shown that our SP-based policy achieves an O(1/N) optimality gap. When this assumption does not hold, the same optimality gap may not apply. However, Theorem 4.3 below shows that the SP-based policy can still yield improvement over LP-based policies.
yet be any optimal solution to the fluid LP in (8) and let NN* be the corresponding SP-based policy. Recall that V.N.. (Xini 1) and NN.... (Xini, y1, 1) denote the value function and the Q-function of the policy * N in the Gaussian stochastic system, where in the Q-function action y1 is applied at time 1. Theorem 4.3 states that if the action given by the SP-based policy # N; time is "strictly" better than the optimal LP-based action yf in the Gaussian stochastic system, then the SP-based policy improves over any LP-based policy in (y") by ((1/VN) in the N N-system.

---

Theorem 4.3 (Performance improvement). If there exists positive constant independent of N such that V.N. nN. (Xini, 1) 2 (Xiii, vi, 2 c/vN, then for any x E Iiiiid we have v. (Xmi, 1) V (Xmi: 1) (L1/VN).
Note that key strength of this result that only need evaluate the first step action yi in the Gaussian stochastic system, and the result then holds for all policies in lyai We refer to Appendix E of (33 for detailed proof of Theorem 4.3
5 Numerical experiments
Total reward difference
50
Total reward difference
20
15-
30
20
10-
10
12
10
11
12
log2(N)
log2(N)
(a) Unique fluid LP solution
(b) Non-unique fluid L.P solution
-7.35
Reward per arm
Reward per arm
-7.40
-7.40
-7.45-
-7.45
LP-ba
LP-based
7.50
SP-based
-7.50
SP-based
11
log2(N)
Iog2(N)
(c) Unique fluid LP solution
(d) Non-unique fluid LP solution
Figure 3: Comparison LP- and SP-based policies on machine maintenance example. Top row: total reward difference (SP minus LP) with 2-sigma error bars. Bottom row: reward per arm.
We evaluated the performance of SP-based policy (Algorithm T machine maintenance problem 12). an RMAB formulation motivated by real-world trade-offs preventive maintenance and resource allocation. The resulting SP is solved using the EDDP algorithm (20) Algorithm 3]. The details of the experiments are presented in Appendix B along with an empirical study of the computational complexity of EDDP for solving the SPs arising from RMABs across varying problem
sizes.
We performed two sets of experiments where the problem instances degenerate: set where the fluid LP solution is unique (Figure and Bc) and one set where it is not unique (Figure 3b and 3d). For both sets, computing the optimal policies is intractable. In each set of experiments, the performance of our SP-based policy and the LP-based policy on a sequence of problems with increasing numbers of machines N, and compared the total reward difference. Figure demonstrates that the improvement our SP-based policy over the LP-based policy grows with in both settings.
evaluated
Conclusion
In this paper, we proposed an SP-based policy for finite-horizon RMABs, leveraging a carefully constructed Gaussian approximation. Motivated by degenerate examples where fluid approximation alone fails to break the ((1/VN) gap, we showed that our policy achieves an ((1NN) optimality gap under the uniqueness assumption, and can achieve ((VN) improvement over large class of LP-based policies.
10

---

Acknowledgments and Disclosure of Funding
The work of Chen Yan and Lei Ying supported in part by U.S. National Science Foundation (NSF) under grants 21 12471, 21340811, 2207548, 2228974, 2240981, 2331780, 2324769; AFOSR grant FA9550-24-1-00000
and Bold Challenges "Accelerate" program from the University of Michigan. The work of Weina Wang is supported in part by U.S. National Science Foundation (NSF) grants ECCS-2145713, CCF-2403194 CCF-2428569, and ECCS-2432542
References
[1] Konstantin Avrachenkov, Vivek S. Borkar, and Pratik Shah. Lagrangian index policy for restless bandits with average reward. arXiv preprint 1xXix:2412./26/// 2024.
[2] V. E. Beneš, L. A. Shepp, and H. Witsenhausen. Some solvable stochastic control problems. Stochastics, 4(1):39--)) 83, 1980.
[3] Dimitris Bertsimas and John N. Tsitsiklis. Introduction to linear optimization, volume 6. Athena Scientific Belmont, MA, 1997.
[4] A. Borovkov. Some limit theorems the theory of mass service, I. Theory of Probability and its Applications, 94))5500-565, 1964.
[5] A. Borovkov. Some limit theorems in the theory of mass service, II. Theory of Probability and its Applications, 10(3):375 400, 1965.
[6] Anton Braverman, Itai Gurvich, and Junfei Huang. On the Taylor expansion of value functions. Operations Research, 68(2):631 2020.
[7] David B. Brown and James E. Smith. Index policies and performance bounds for dynamic selection problems. Manag, Sci., 66:3029-3050, 2020.
[8] David B. Brown and Jingwei Zhang. Fluid policies, reoptimization, and performance guarantees in dynamic resource allocation. Operations Research, 2023.
[9] Ece Zeliha Demirci, Joachim Arts, and Geert-Jan van Houtum. A restless bandit approach for capacitated condition based maintenance scheduling. Flexible Services and Manufacturing Journal, pages 1-29, 2024.
[10] Nicolas Gast, Bruno Gaujal, and Chen Yan. Linear program-based policies for restless bandits: Necessary and sufficient conditions for (exponentially f'ast) asymptotic optimality. Mathematics of Operations Research, 2023.
[11] J. C. Gittins. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society, Series B, pages 148-177, 1979.
[12] Kevin D Glazebrook, HM Mitchell, and PS Ansell. Index policies for the maintenance of collection of machines by a set of repairmen. European Journal of Operational Research, 165 (1):267-284, 2005.
[13] Michael Harrison. Brownian Motion and Stochastic Flow Systems. Wiley, New York, 1985,
[14] J. Michael Harrison and Lawrence M. Wein. Scheduling networks of queues: Heavy traffic analysis of simple open network. Queueing Syst., 5(4):265-279, 1989.
[15] Weici Hu and Peter Frazier. An asymptotically optimal index policy for finite-horizon restless bandits, arXiv preprint arXiv: 170.000007..00005 2017.
[16] Donald L. Iglchart and Ward Whitt. Multiple channel queues in heavy traffic. I. Advances in Applied Probability, 150-1150 1970.
[17] Donald I.. Iglehart and Ward Whitt. Multiple channel queues in heavy traffic. II: Sequences, networks, and batches. Advances in Applied Probability, 2(2):355-66,, 1970.
11

---

[18] Jackson A. Killian, Lily Xu, Arpita Biswas, and Milind Tambe. Restless and uncertain: Robust policies for restless bandits via deep multi- agget reinforcement learning. In Uncertainty in Artificial Intelligence, pages 990-1000. PMLR, 2022.
[19] B.F. La Scala and B. Moran. Optimal target tracking with restless bandits. Digital Signal Processing. 16(5):479 4474477777777 2006.
[20] Guanghui Lan. Complexity of stochastic dual dynamic programming. Mathematical Program- ming, 19 191())717-754, 2022.
[21] Jerome Le Ny. Munther Dahleh, and Eric Feron. Multi-agent task assignment in the bandit framework. In Proceedings of the 45th IEEE Conference on Decision and Control, pages 5281-5286. IEEE, 2006.
[22] Aditya Mate, Jackson A. Killian, Haifeng Xu, Andrew Perrault, and Milind Tambe. Collapsing bandits and their application to public health intervention. Advances in Neural Information Processing Systems, 33:15639-15650, 2020.
[23] Aditya Mate, Andrew Perrault, and Milind Tambe. Risk-aware interventions in public health: Planning with restless multi-armed bandits. In AAMAS, pages 880-888, 2021.
[24] Khaled Nakhleh, Santosh Ganji, Ping-Chun Hsieh, I-Hong Hou, and Srinivas Shakkottai. NeurWIN: Neural Whittle index network for restless bandits via deep RI. Advances in Neural Information Processing Systems, 34:828-839, 2021.
[25] Christos H. Papadimitriou and John N. Tsitsiklis. The complexity of optimal queuing network control. Math. Oper. Res, pages 293-305, 1999.
[26] M.V.F. Pereira and L.M.V.G. Pinto. Multi-stage stochastic optimization applied to energy planning. Mathematical programming, 52:359-376 1991.
[27] Alexander Shapiro. Analysis of stochastic dual dynamic programming method. European Journal of Operational Research, (09()))63-22,2011
[28] Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczynski. Lectures on Stochastic Programming: Modeling and Theory, Third Edition. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2021.
[29] Whittle, Restless bandits: activity allocation in a changing world. Journal of Applied Probability, 25A:287- 298. 1988.
[30] Guojun Xiong and Jian Li. Finite-time analysis of Whittle index based Q-learning for rest- less multi-armed bandits with neural network function approximation. Advances in Neural Information Processing Systems, 36:29048-29073, 2023.
[31] Guojun Xiong, Jian Li, and Rahul Singh. Reinforcement learning augmented asymptotically optimal index policy for finite-horizon restless bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8726-8723 2022.
[32] Chen Yan. An optimal-control approach to infinite-horizon restless bandits: Achieving asymp- totic optimality with minimal assumptions. 2024 IEEE 63rd Conference on Decision and Control (CDC), pages 6665-6677 2024.
[33] Chen Yan. Weina Wang. and Lei Ying. Achieving O(1/N) optimality gap in restless bandits through Gaussian approximation. arXiv preprint 1xXi::2410.15003// 2025.
[34] Gabriel Zayas-Cabán Stefanus Jasin, and Guihua Wang, An asymptotically optimal heuristic for general non-stationary fnite-horizon restless multi-armed multi-action bandits. Ross: Technology & Operations (Topic), 2017.
[35] Jingwei Zhang. Leveraging nondegeneracy in dynamic resource allocation. Available at SSRN, 2024.
[36] Xiangyu Zhang and Peter Frazier. Restless bandits with many arms: Beating the central limit theorem. arXiv preprint 21X 2021.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our paper proposes new Algorithm [ that achieves order-wise improvements over existing algorithms in the literature on the challenging finite-horizon RMAA problem. We believe that these claims in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The Uniqueness Assumption 4.1 and the Degeneracy Definition thoroughly discussed in the main paper, along with empirical study of how likely these conditions are met in RMAB instances. When the Uniqueness Assumption does not hold, we established a performance improvement result in Theorem which is weaker than the global optimality result.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
13

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The proofs of the theoretical results for the three theorems presented in the main paper can be found in the arXiv version 33
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All parameters of our numerical experiments and the algorithm used solve our problem are provided and discussed Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility.
14

---

In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Our new Algorithm T is presented with pscudocode in the main paper and is straightforward implement. The Explorative Dual Dynamic Programming (EDDP) algorithm we employ is from [20]. with pseudocode provided in that paper. The code is included in the supplemental materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips.
http:////guidee/eeeuuuubbii htt////ooouuiissseeeeeeeeee ssionPolicy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All our experimental setting details, including the choice of the parameters, are provided in Appendix B
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
The 2-sigma error bars are included in Figure 3 and Figure 4 (in the appendix).
Guidelines:
15

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The computer resource of conducting the numerical experiments are detailed in Appendix B with computation time analysis well. All numerical experiments in this paper were conducted on personal laptop equipped with a 13th Gen Intel(R) 19-13980HH CPU. All the experiments are based on solving reasonable size linear programs, for which well-established solution packages are available.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:///wrrrp...ccpppcacc/caaaaa
Answer: [Yes]
Justification: We have reviewed and confirm that our research conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
16

---

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This paper is a theoretical paper that advances research on the topic of restless bandits, which has many practical applications in machine maintenance, healthcare, etc. None of them should be highlighted as potential negative social impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
17

---

The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
18

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does involve LLMs as any important, original, or non standardd components.
Please refer to our LLM policy for what should or should not be described.
19

---

A More details of the Gaussian stochastic system and the SP-based policy
The covariance matrix (y)). Recall that when applying an action vector ya. the state of the Gaussian stochastic system at the next time step, X is a random vector of the following form:
X h+1 Projas
a a P) 8,0) Z
8,0
where Zn is a Gaussian random vector following the distribution (00, (x())))) The covariance matrix (y%) is a constant matrix independent of N, and it is defined as follows.
Define, for (h, 8,,8,) E [1, H) x S x A, the matrix (x a) of size |S| x (S), for which the (i.j)-th
entry is:
Pa(i 8, Pn s, Pa(i 8, (1 - Pv s,0)), if
if j
(22)
Then
(w(y)) Σ
(23)
Note that (yN))) is the covariance matrix of the state X in the N-systtm if the action at time h is yi.
Rounding procedure. Throughout this paper, we represent systems and controls as "fractions" of the total population N of arms, using vectors such y. In the unnormalized-scaul system, the coordinates of Nx and Ny therefore need to be integers. If these quantities are not integers, they implicitly understood be appropriately rounded via some rounding procedure. For example, after obtaining from the SP-based policy, we need to applying rounding before using it for the N-system.
Formally, a rounding procedure to solve the following problem: Given an integer N E and X E A so that NX have integer coordinates, then, for any Y E Yx, we need to construct Y- = round(Y) Vxx for which NY have integer coordinates.
This can be accomplished as follows. Set
(s, 18 = [Y 1)1
[NY 0)]
(x)
for S -11;
(24)
N
N
8-1
S-1
(8,1)) = - Σ
Y (s, (5,0)
Σ
N (s.
(25)
is then easy to verify that, Y round(Y) defined in conditions. Furthermore, by construction, it holds true that
24 25
indeed satisfies all these required
1 N
1 N
Y rounddd
0
(26)
independently of X and Y e Vx.
B More details of numerical experiments
This appendix is a collection of more details on various numerical experiments conducted to confirm the theoretical results of this paper. is structured as follows:
Appendix B.1 studies how likely an RMAB instance is degenerate or satisfies the Uniqueness Assumption
Appendix B.2 is centered around numerically solving the SP (4). which appears in Algo- rithm
Appendix B.3 displays the parameters and implementation details of the RMAB examples used in Section
20

---

All numerical experiments in this paper were conducted on personal laptop equipped with a 13th Gen Intel(R) 19-13980HX CPU. We note that our experiments are based on solving reasonable size linear programs, for which well-established solution packages are available. We implement the solutions using the Python package PuL.P and the Gurobi I.P solver.
B.1 Degeneracy and Uniqueness Assumption 4.1 in RMAB instances
We conducted a numerical study how likely randomly generated RMAB instance is degenerate (Definition 3.I) and the corresponding LP (8) satisfies the Uniqueness Assumption 4.1
In this experiment, an RMAB instance is generated as follows: Each parameter is sampled via i..d. exp(1) and normalized properly as the initial condition Xini and in the transition kernels PA. We fix = 0.4 and H = 5. We considered two scenarios: "fully-dense" where all entries of transition kernel are positive; "half-sparse" where half of the entries of each row of transition kernel are O. We varied the number of sizes per arm S = 5, 10, 15, 20 and tested the degeneracy and the Uniqueness Assumption ovee 10, 000 such RMAB instances, and recorded the numbers in percentage. The results are presented in Table
Table 2: Proportion of RMAB instances satisfying degeneracy and Uniqueness Assumption 4.1
Transition Kernel
S
Degenerate
Satisfy Uniqueness Assumption 4.1
Fully-dense
11.2%
100%
Fully-dense
10
8.7%
100%
Fully-dense
15
6.1% %
100%
Fully-dense
20
5.1%
100%
Half-sparse
51.3%
100%
Half-sparse
33.3%
100%
Half-sparse
15
28.1%
100%
Half-sparse
20
20.3%
100%
We note that overall, degenerate RMABs are a significant proportion among all instances, especially in the half-sparse setting. In addition, all these randomly generated RMABs satisfy the Uniqueness Assumption 4.1
B.2 Numerically Solving SP
This section presents the details of the numerical method we used to solve the SP 14). To solve the SP (14), we can transform and simplify it to an N N-independent and projection-free free SP. see Stochastic Linear Program, which significantly easier to solve than the original Narreed RMAB Problem 4 because the "noise" Z₁ 's are predefined Gaussian random vectors whose distributions are independent of the state and action of the system. For such a problem, there exist computationally efficient methods. In our numerical examples, we numerically solved it using the standard Sample Average Approximation (SAA) approach [28 Chapter 5] and the Explorative Dual Dynamic Programming (EDDP) algorithm (20), which is an enhancement of the classical Stochastic Dual Dynamic Programming (SDDP) 26
Equation (29) of [33] for details.
We also evaluated the computational complexity of EDDP when varying H and S. The results are shown in Figure and include 2- sigma error bars. Each recorded computation time in the figures was averaged from running EDDP on 1,000 RMAB instances, with each instance solved for 10 independent SAA realizations. The results in Figure clearly illustrate that the computational complexity under EDDP increases linearly with respect to the problem parameters H and S.
B.3 Parameters and implementation details of the RMAB examples used in Section 5
The RMAB examples used Section model a machine maintenance problem. Each machine has five states, where a higher state represents a more deteriorated condition. The first state is pristine
21

---

Degree regression (R+ 0.9963)
Degree regression (R = 0.9829)
Time (seconds)
Data with 2 sigraa error bars
Time (seconds)
Data with 2-sigma error bars
50
150
40
100
50
20
10
25
30
10
H
5
Fix
(b) Fix
Figure 4: The computation time of EDDP.
state. Under action (performing maintenance), deteriorated machine has a high probability of returning to the pristine state. Under action 0 (not performing maintenance), the machine gradually deteriorates and has an increasing probability of breaking down the state worsens. When breakdown occurs, the machine must be replaced (returning to the pristine state) and incurs a high cost. The negative rewards (i.e., costs) reflect the nature of this model. Note that sufficiently large common constant to all rewards to offset them, making the values non-negative, as per reward convention diseussed in the main paper.
add
In these RMAB examples, we set 5 and a 0.4. We consider arms representing machines each described by 10 states MDP constructed from two distinct machine types, each having 5 states. The initial state an arm determines its machine type. Consequently, the transition kernels are structured into two block matrices of size 5. Such block-structured kernel enables the modeling of multiple machine types under the assumption of homogeneous arms. In other words, the homogeneous RMAB model can be used for heterogeneous systems with finite number of types. All numerical parameters provided below are recorded with digits of precision.
P( 1,0)
0.5415
0.4585
0
0
0
0
0.5471
0.2265
0.2265
0
0
0.7067
0.1467
0.1467
0
0
0
0
0
0.8578
0.0711
0.0711
0.9214
0
0
0
0.0786
0
0
0
0.6396
0.3604
0
0
0
0.5694
0.2153
0.2153
0
0.6453
0.1773
0.1773
0
0
0
0.7007 0
0
0
0.1496
0.1496
0.7097 0
0
0.2903
P(11-1)=
22

---

1
0
0
0
0
0.7337
0.2663
0
0
0
0.7265
0.2735
0
0
0
0
0
0.6146
0.3854
0
0.6054
0
0.3946
0
0
0
1
0
0
0
0.6037
0.3963
0
0
0.6004
0
0.3996
0
0
0
0.7263
0.2737
0
0
0.6138 0
0
0.3862
Xini
0.5
0
0.5
[o
r(.,0) 0)
-5.4707
-7.0669
-8.5784
-9.2141
5..9942
-6.4534
-7.0074
-7.097
In the first set of experiments, we use
r(:,1)
--999663
-2.085
-2.035
2.0661
-1.9581
-1.994
-1.9647
-.22478
-2.0468
-2.2821
which results a fluid I.P with a unique optimal solution. the second set of experiments, we use
r(: 1) = -2 -2 -2
2 -2
2
2
-2
which leads fluid LP with multiple optimal solutions.
The LP-based policy we compared with is the LP-update policy (also referred to as the LP policy with resolving) proposed in [0. These studies reported that LP-update is one of the best-performing LP-based policies for imite-horizon RMABs. As mentioned earlier, we used EDDP (20) to obtain the SP-based policy. The predefined policy in Line 12 of Algorithm
follows: during the execution of the algorithm, the N-system state deviates significantly from the initially selected optimal LP solution where "significant" is defined as any coordinate exceeding a threshold of 20, a new LP is resolved using the current initial state of the N-system and the remaining horizon, similar the LP-updaateresolvvin policy, and then the first action from the new LP is applied.
[ i specified
In addition, we conducted further tests on several machine maintenance instances, keeping the problem size and structure fixed while varying the reward and transition parameters. All of these instances have unique LP solutions. The observed total reward gaps, shown in Table are of the same order of magnitude the example in Figure 3a for 100.
Table Additional experiments for machine maintenace.
Instance
Total Reward Gap for N 100 Machines (mean + std)
9.35 + 1.21
2
10.13 + 1.53
12.44 + 1.97
4
7.57 + 1.35
13.52 + 1.56
23


Reviews:
[{"review_id": "lRrQi6ulUS", "reviewer": "Reviewer_5dNH", "summary": "This paper studies a finite-horizon N-armed restless bandit problem with homogenous arms (identical state space and transition kernel across arms). The authors propose a Gaussian approximation-based approach that tracks the mean as well as variance of the RMAB process, resulting in a more accurate representation of the limiting process compared to standard fluid limit-based approaches. The resulting stochastic programming-based policy is shown to improve sub-optimality gap per arm by a factor of $1/\\sqrt{N}$ over LP-based policies (resulting from fluid approximation) in the case of degenerate RMABs.", "questions": "None, please see the previous section.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Proofs were not carefully checked but the intuition provided is sound and generally easy to follow. The general strengths of this paper in my opinion are:\n\n1. Well-written and instructive to follow.\n2. That a higher order approximation leads to a significant improvement (breaking the $1/\\sqrt{N}$ barrier) is nice to see.\n\nNot a weakness, but a question/suggestion: The proposed Gaussian approximation bears resemblance to \"Diffusion Approximation\" techniques common in Operations Research and Stats literature. It would be good if the authors can comment on this and make connections to similar techniques that might have appeared under different names. I am happy to revise my score upwards pending resolution of this point. In particular, I want to be sure that this (or a very similar) problem isn't already addressed in adjacent literature under different technical nomenclature.\n\nAlso curious to hear the authors' thoughts on whether the $\\mathcal{O}\\left( 1/N \\right)$ gap can be further reduced (under the same assumptions).", "was_revised": true, "final_justification": "The contributions became clearer after the authors disambiguated their (simpler) Gaussian approximation from classical diffusion scaling. There are novel elements in their approach and analysis that I believe can benefit the wider community.", "rebuttal": "We greatly appreciate the reviewer's willingness to reevaluate the score based on our response. We next address the connection to diffusion approximation and whether the $\\mathcal{O}(1/N)$ gap can be further reduced. \n\n**Connection to diffusion approximation:**\n\nIn the current version of the paper, we only briefly mention the connection to diffusion approximation in Appendix B of the supplementary material. We agree that this connection warrants further elaboration, and we plan to expand this discussion following the outline below.\n\nFirst, there is a rich literature on diffusion approximations for continuous-time queueing systems, particularly in the heavy-traffic regime (see, e.g., seminal work [3], [4], [12], [13] in the reference list of the supplementary material).\nThis body of work typically analyzes queueing systems under a *fixed policy*, and the focus is on characterizing the convergence or the rate of convergence of the centered and scaled queueing system to the diffusion limit.\nIn contrast, our work addresses a different goal for a different application: we focus on finding a near-optimal policy for a discrete-time restless bandit problem.\n\nA more closely related line of work, which builds on the diffusion approximation literature, is on approximate diffusion control for queueing systems or stochastic control in general (see, e.g., seminal work and textbook such as Beneš et al. (1980), Harrison (1985), and Harrison and Wein (1989)). In this line of work, the problem is approximated by a diffusion control problem, which is then solved via the associated Hamilton-Jacobi-Bellman (HJB) equation.\nRecent work by Braverman et al (2020) shows that the HJB equation naturally arises under the second-order approximation of value functions of general Markov decision processes (MDPs).\n\nWhile we can apply the same diffusion control to our problem, solving the HJB equation is known to be notoriously difficult in general. This is because the diffusion coefficients often depend on the control, which makes the HJB a highly nonlinear PDE. This actually motivated us to consider a different second-order approximation. \n\nA key innovation in our work is to replace (state, action)-dependent diffusion terms with (state, action)-independent diffusion terms. We construct our Gaussian approximation system such that the covariances of the Gaussian noises (analogous to the diffusion coefficients) are independent of the actions, by leveraging the optimal fluid solution.\nThis proposed Gaussian approximation allows us to tap into stochastic programming techniques, where (state,action)-independent randomness is required for efficient algorithms like the EDDP algorithm we used in this paper. In other words, our Gaussian approximation can be viewed as a further ``approximation/simplification'' of the diffusion approximation, but it has the same order of approximation error in our problem and can be solved efficiently using existing stochastic programming methods.  \n\n\nWe note that our results are possible because in the restless bandit problem, the noise terms are on a smaller scale compared to the deterministic terms as the number of arms scales, due to the central limit theorem.\nThis is reflected in the $1/\\sqrt{N}$ factor for $\\mathbf{Z}_h$ in the SP in equations (14)-(17).\nThis scale separation makes it possible to use the (state,action)-independent covariances generated by the fluid optimal solution as a surrogate for the action-dependent covariances, and leads to a critical result (Lemma D.1) that shows that the optimal policy of the $N$-arm problem is within $\\tilde{\\mathcal{O}}(1/\\sqrt{N})$ neighborhood of the fluid solution under a uniqueness assumption. We do not usually have such a property in traditional diffusion control. \n\n\nIn summary, our approach may be viewed as a further approximation of the traditional ``diffusion approximation''. Based on the proximity result (Lemma D.1) for restless bandits, our approximation reduces the problem to simpler stochastic programming (instead of solving nonlinear PDEs) and guarantees  $\\tilde{\\mathcal{O}}(1/N)$ optimality gap. \n\nWe hope these expanded discussion addresses the reviewer's concern, and we will incorporate a detailed version of this discussion into our paper.\n\n**The $\\mathcal{O}(1/N)$ gap.**\n\nWe thank the reviewer for this question. Our conjecture is that any asymptotic methods that reduce the problem to continuous state and action spaces will have an $\\Omega(1/N)$ gap in a general setting. This is because rounding procedure (like the one detailed in Appendix C), which is necessary to map a continuous action to a discrete action in the N-arm system, will result in an $\\mathcal{O}(1/N)$ error in general, except for some special cases, such as when the optimal policy is a priority policy. \n\n\n**References:**\n\n- Beneš, V. E., Shepp, L. A., and Witsenhausen, H. S. (1980). \"Some solvable stochastic control problems.\" Stochastics, 4(1), 39–83.\n\n- Braverman, A., Gurvich, I., and Huang, J. (2020). \"On the Taylor expansion of value functions.\" Operations Research, 68(2), 631–654.\n\n- Harrison, J. M. (1985). \"Brownian Motion and Stochastic Flow Systems.\" Wiley, New York.\n\n- Harrison, J. M., and Wein, L. M. (1989). \"Scheduling networks of queues: Heavy traffic analysis of a simple open network.\" Queueing Systems, 5(4), 265–279."}, {"review_id": "E5iwABM9Qo", "reviewer": "Reviewer_yu2p", "summary": "Authors study the restless multi-armed bandit problem in the finite horizon setting. They give a new policy and improved theoretical optimality gap in the degenerate setting, based on Gaussian approximation applied to the standard fluid approximation. They support their findings with empirical results.", "questions": "Since the policy is based on the fluid approximation, it would be helpful to give some idea of how much the SG policy can deviate from the base fluid approximation and still retain optimality or feasibility of computation time – what is the factor at play there?\n\nCan the gaussian approximation technique be extended to infinite horizon settings?\n\nCan you comment on how you might relax the homogeneity assumption and still maintain the gap improvement?\n\nComment on computational complexity of the approach – how it scales with |S| and H? \n\nCan this approach be extended to the multi-action/WCMDP setting?", "limitations": "n/a", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n* Key new result in RMAB literature, improving the optimality gap while relaxing the non-degeneracy assumption\n* Achieved through a new technique based on Gaussian approximation, building on established methods based on fluid approximation\n* Detailed illustrative example effectively demonstrates the mathematical intuition\n\nWeaknesses:\n* assumes homogenous arms (i.e., all arms have the same MDP probas and rewards)\n* lacking comments on the scalability of the approach with respect to the size of the state space and the length of the horizon\n* additional motivation for the degenerate setting would improve the significance -- are there convincing real-world examples?", "was_revised": true, "final_justification": "Key result in RMAB literature of interest to a wide audience. Strong results and writing in the original submission, as well as responses to all reviewer concerns and clarifications.", "rebuttal": "We greatly appreciate the reviewer's positive comments. We next address the weaknesses and questions raised by the reviewer. \n\n- **Assumes homogeneous arms (i.e., identical transition probabilities and rewards across arms).**\n\nOur results can be directly applied to settings with limited heterogeneity. A more detailed response can be found in the answer to the reviewer's question on extending to heterogeneous cases. \n\n- **Lacking comments on scalability of the approach with respect to the state-space size and horizon length.**\n\nWe provide a detailed discussion on scalability later when answering the reviewer's question on scalability,  highlighting computational complexity and empirical runtime performance. \n\n- **Additional motivation for the degenerate setting would improve significance—are there convincing real-world examples?**\n\nAnother real-world example is the applicant screening problem studied in Brown and Smith (2020), which explicitly exhibits degeneracy by requiring non-trivial tie-breaking. We will add this example to the revision. \n\n\n- **Since the policy is based on the fluid approximation, it would be helpful to give some idea of how much the SG policy can deviate from the base fluid approximation and still retain optimality or feasibility of computation time – what is the factor at play there?**\n\nWe thank the reviewer for this insightful question. Our second-order Gaussian policy specifically seeks improvements by considering corrections within a neighborhood of size $\\tilde{\\mathcal{O}}(1/\\sqrt{N})$ around the fluid-optimal state and action. When the LP has a unique solution, we proved in the paper that the optimal policy of the $N$-arm problem is within $\\tilde{\\mathcal{O}}(1/\\sqrt{N})$ neighborhood of the LP (fluid) solution (Lemma D.1 in the supplementary material). Therefore, limiting the deviation within this   $\\tilde{\\mathcal{O}}(1/\\sqrt{N})$ neighborhood retains the optimal policy and also guarantees that our second-order approximation has $\\tilde{\\mathcal{O}}(1/N)$ approximation error (in terms of Wasserstein distance). Expanding the neighborhood would increase the second-order approximation error; while shrinking the neighborhood would exclude the optimal policy. So it turns out that $\\tilde{\\mathcal{O}}(1/\\sqrt{N})$ is the ``exact'' deviation needed for our proposed method. We will add this discussion to the revision. \n\n- **Can the gaussian approximation technique be extended to infinite horizon settings?**\n\nThe algorithm can be directly extended to the infinite horizon settings by considering a second-order approximation around the LP solution to the infinite horizon problem. However, the $\\tilde{\\mathcal{O}}(1/N)$ optimality gap would require a different proof due to the fundamental difference between finite-horizon MDPs and infinite-horizon average-reward MDPs. \n\n- **Can you comment on how you might relax the homogeneity assumption and still maintain the gap improvement?**\n\nThe heterogeneous setting is more challenging because the arms can no longer be aggregated into a single representative arm as in the homogeneous case. However, if the arms can be divided into different types, and the number of types is independent of $N$, then our result can directly apply. In fact,  our machine maintenance problem in Section 5 is such a heterogeneous setting and considers two types of machines (see details in Appendix G.3 of the supplementary materials). We will clarify this in the revision. The ``fully'' heterogeneous setting would likely require new techniques. \n\n- **Comment on computational complexity of the approach – how it scales with $|S|$ and $H$?**\n\nThe computational complexity of our approach stems primarily on solving the Gaussian SP in Line 6 of Algorithm 1. The numerical solution methods are detailed in Appendix G.2 in the supplemented material: After recentering and scaling, we obtain an $N$-independent multi-stage linear stochastic program (problem (107) in the supplementary material). The computational complexity of solving problem (107) depends on the number of states per arm, $|S|$, and the horizon length, $H$. Our numerical evaluations using Explorative Dual Dynamic Programming (EDDP, Lan (2022)) indicate that the runtime scales linearly in both $|S|$ and $H$, as illustrated in Figure 5 in the supplementary material.\n\n- **Can this approach be extended to the multi-action/WCMDP setting?**\n\nThe key is to come up with an equivalent version of the action mapping algorithm in Section D.2.3 (supplementary materials) and then prove it is locally Lipschitz. The proof in this paper utilizes some unique properties of the RMAB. If a similar result can be proven for the more general WCMDP setting, then the result should generalize.  \n\n\n$\\textbf{References:}$\n\n- Brown, D. B., and Smith, J. E. (2020). \"Index policies and performance bounds for dynamic selection problems.\" Management Science, 66, 3029–3050.\n\n- Lan, G. (2022). \"Complexity of stochastic dual dynamic programming.\" Mathematical Programming, 191(2), 717–754."}, {"review_id": "chajA501Pk", "reviewer": "Reviewer_2XWR", "summary": "In this paper, the authors have studied the finite horizon Restless Multi-armed Bandit (RMAB) problem under the homogeneous arm setting. Existing works on RMAB show that Linear-Programming (LP) based policies derived from the fluid approximation can result in an exponentially small optimality gap, however, under the assumption that the RMAB satisfies a non-degeneracy condition. However, in reality, RMABs are often degenerate, and in that case, LP-based policies can result in $\\Theta(1/\\sqrt{N})$ optimality gap per arm. The authors in this paper have proposed a new Stochastic Programming (SP) based policy that can achieve an $O(1/N)$ optimality gap for degenerate RMABs (for the first time) under the uniqueness assumption. The authors claim that the construction of a Gaussian stochastic system can capture the mean and variance of the RMAB dynamics, and it is more accurate than the fluid approximation.", "questions": "1.\tWhat is the motivation behind considering a Gaussian stochastic system as an approximation of the original system? What other kinds of distribution can be chosen to offer a good approximation? Does a Gaussian stochastic system offer the best approximation?\n2.\tWhy is there a need of a $1/\\sqrt{N}$ factor multiplying $Z_h$ in equation (12)? \n3.\tThe meaning of the policy class described in (13) is not clear. What is the physical interpretation behind this class construction?\n I wonder whether it would include a large number of feasible policies. The main result in the paper (Theorem 4.1) heavily depends on this class of policies. However, the significance of the result can be better understood if we get more insight about the class and its cardinality. \n4.      Please explain what is meant by the round operator in Algorithm 1. \n5.\tTheorem 4.1 holds with rounding. Is it possible to extend this theorem to the case without rounding too? \n6.\tTheorem 4.3 assumes the existence of a positive constant $\\epsilon$ independent of $N$. How can we guarantee the existence of such an $\\epsilon$?", "limitations": "Yes. However, in the conclusion section, limitations of the proposed approach can be explicitly mentioned for more clarity.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is well-written and technically solid. However, more intuitions need to be provided to understand the impact of the result better. More insight is needed on the construction of policy class, as the main results of the paper are based on this class construction. The simulation section can be enriched with simulations on more scenarios.", "was_revised": true, "final_justification": "Authors have addressed the concerns raised by me (such as regarding construction of policy class and rounding) and provided satisfactory response. It will be good if the authors could include the additional simulation results in the main paper.", "rebuttal": "We hope our responses to the reviewer's questions below provide clearer intuition and deeper insight into the policy class construction and related issues. We also appreciate the suggestion to enrich the simulation section with additional scenarios.\nTo address this suggestion, we have conducted additional tests on several machine maintenance instances, keeping the problem size and structure the same while varying model parameters for rewards and transition probabilities. All these instances exhibit uniqueness in their LP solutions. The observed total reward gaps in these experiments, displayed in the table below, remain within the same order of magnitude as the example presented in the left subfigure of Figure 3 (Section 5 of the paper) for $N = 100$. We plan to incorporate these additional results, along with the corresponding model parameters, in a future revision of our paper.\n\n**Table: Total reward gap across additional machine maintenance instances**\n\n| Instance | Total Reward Gap for $N=100$ Machines (mean ± std) |\n|----------|-----------------------------------------------------|\n| 1        | 9.35 ± 1.21                                          |\n| 2        | 10.13 ± 1.53                                         |\n| 3        | 12.44 ± 1.97                                         |\n| 4        | 7.57 ± 1.35                                          |\n| 5        | 13.52 ± 1.56                                         |\n\n\n- **What is the motivation behind considering a Gaussian stochastic system as an approximation of the original system? What other kinds of distribution can be chosen to offer a good approximation? Does a Gaussian stochastic system offer the best approximation?**\n\nWe consider the Gaussian distribution because by the central limit theorem, the Gaussian distribution is the limiting distribution of the normalized mean of $N$ independent random variables.  The central limit theorem also implies that other kinds of distributions can't be such a limiting distribution, so the Gaussian approximation offers the best approximation asymptotically. In particular, the Wasserstein distance bound (Lemma D.1) may not hold under other distributions. \n\n- **Why is there a need of a $1/\\sqrt{N}$ factor multiplying $\\mathbf{Z}_h$ in equation (12)?**\n\nThe factor $1/\\sqrt{N}$ again arises from the central limit theorem (CLT). \n     To see this more clearly, consider $N$ independent and identically distributed random variables $X_1,X_2,\\dots,X_N$, each with mean $\\mu$ and variance $\\sigma^2$. By the CLT, as $N$ becomes large, we have the following approximation\n     \\begin{equation*}\n         \\frac{\\sum_{i=1}^N X_i-N\\mu}{\\sigma\\sqrt{N}}\\approx Z,\n     \\end{equation*}\n     where $Z$ is a standard Gaussian random variable.\n     Rewriting this gives\n     \\begin{equation*}\n       \\frac{1}{N}\\sum_{i=1}^{N}X_i \\approx \\mu + \\frac{\\sigma}{\\sqrt{N}}Z,\n     \\end{equation*}\n     where there is a $1/\\sqrt{N}$ factor multiplying $Z$.\n     The $1/\\sqrt{N}$ factor in our equation (12) comes from the same reason, although for a more complicated setting.\n\n\n- **The meaning of the policy class described in (13) is not clear. What is the physical interpretation behind this class construction? I wonder whether it would include a large number of feasible policies. The main result in the paper (Theorem 4.1) heavily depends on this class of policies. However, the significance of the result can be better understood if we get more insight about the class and its cardinality.**\n\nRoughly speaking, the policies in (13) are policies such that when the system state $\\mathbf{x}_h$ is in an $\\tilde{\\mathcal{O}}(1/\\sqrt{N})$ neighborhood of the optimal fluid state $\\mathbf{x}^{\\star}_h$, the action taken is also within an $\\tilde{\\mathcal{O}}(1/\\sqrt{N})$ neighborhood of the optimal fluid action $\\mathbf{y}^{\\star}_h$. We would like to emphasize that this policy class includes commonly studied fluid-based policies in the literature, e.g., the policies in references Zhang and Frazier (2021), Gast et al. (2023), and Brown and Zhang (2023); and most existing policies for RMAB are fluid-based.  Moreover, it also includes the optimal policy for the $N$-armed problem when the uniqueness assumption (Assumption 4.1) is satisfied.\n\n- **Please explain what is meant by the round operator in Algorithm 1.**\n\n\nThe rounding operation guarantees that the action generated by the algorithm pulls an *integer* number of arms. It is needed due to the following reason: when computing the first- and second-order approximations, we extend the state and action spaces from their original discrete sets (with granularity $1/N$) to continuous-valued probability simplices. The action computed in this continuous domain must subsequently be converted back to the discrete domain, ensuring that all values multiplied by $N$ are integers and thus applicable to the $N$-armed problem. This rounding procedure is explicitly detailed in Appendix C of the supplementary material.\n\n\n- **Theorem 4.1 holds with rounding. Is it possible to extend this theorem to the case without rounding too?**\n\nWithout rounding, the policy may output an action that pulls a fraction of an arm, which is typically not allowed in a restless bandit problem. That said, if pulling a fraction of an arm is allowed (say 0.5 arm), e.g. by using a probabilistic method (say pull one arm with probability 0.5), then Theorem 4.1 holds without rounding.\n\n\n- **Theorem 4.3 assumes the existence of a positive constant $\\varepsilon$ independent of $N$. How can we guarantee the existence of such an $\\varepsilon$?**\n\n\nWe expect that such an $\\varepsilon$ exists when the fluid optimal action $\\mathbf{y}_1^{\\star}$ at time step $1$ is not an optimal action for the Gaussian stochastic system.\nTo see this, consider the $N$-independent stochastic program (107), which is derived from problem (14) through re-centering and scaling, as detailed in Appendix G.2 of the supplementary material. If the optimal first-stage solution of (107) differs from zero, which translates to $\\mathbf{y}_1^{\\star}$ not being an optimal solution, then $\\varepsilon$ corresponds to the gap between the optimal objective value of (107) and the objective value (or the $Q$-value) obtained by evaluating the fluid-optimal first-stage action. Equivalently, the value of $\\varepsilon$ is the difference between the largest Q-value and the Q-value under the fluid action. If the fluid action is sub-optimal, then the gap $\\varepsilon$ is strictly positive and independent of $N$. Otherwise, the fluid optimal action $\\mathbf{y}_1^{\\star}$ is optimal for the Gaussian stochastic system, and our second-order policy will take the fluid optimal action. \n\n\n**References**\n\n- Brown, D. B., and Zhang, J. (2023). \"Fluid policies, reoptimization, and performance guarantees in dynamic resource allocation.\" *Operations Research*.\n\n- Gast, N., Gaujal, B., and Yan, C. (2023). \"Linear program-based policies for restless bandits: Necessary and sufficient conditions for (exponentially fast) asymptotic optimality.\" *Mathematics of Operations Research*.\n\n- Zhang, X., and Frazier, P. I. (2021). \"Restless bandits with many arms: Beating the central limit theorem.\" arXiv preprint arXiv:2107.11911."}, {"review_id": "RZBquzjnUM", "reviewer": "Reviewer_T8Za", "summary": "This paper studies an RMAB problem with $N$ homogeneous arms. Prior results based on LP relaxation may result in a larger $\\Theta(1/\\sqrt{N})$ optimality gap when the RMAB problem is degenerate. In contrast, this paper proposes a new Gaussian approximation and stochastic-programming (SP) based policy that can achieve a smaller $\\Theta(1/N)$ optimality gap, which only requires the relaxed solution to be unique. A small 2-state problem with 2 time-steps is used to show the performance advantage of the SP-based policy.", "questions": "1. My main concern is how the SP-based policy can be solved efficiently. The example in the paper involves only 2 per-agent states and 2 time-steps, which is quite small and less practical. With only two per-agent states, the occupancy measure at each time-step can be parameterized by 1 value. Then, backward induction over 2 time-steps can be written as an (expectation) optimization problem over just one variable (in Line 207). This optimization problem still needs to be solved numerically, but is not that difficult. For a general problem with $K$ states, the occupancy measure will form a $K-1$-dimensional hyperplane. With multiple steps, the backward induction will lead to a highly-complex optimization problem in $K-1$ dimension. The paper does not seem to provide a way to solve this general backward induction under Gaussian approximation. \n\nFurther, note that one of the main advantages of LP relaxation (and other related approaches such as Whittle index) is the ability to decompose the problem, which is crucial for overcoming the curse of dimensionality. Specifically, for an $N$-arm problem, solving the whole RMAB involves a backward induction over $O(N^K)$ global states (if we again use the occupancy measure to represent a global state). In contrast, solving the decomposed problem only involves backward induction over $K$ per-agent states, which is much easier. It is unclear how the Gaussian approximation and SP-based policy can benefit from similar decomposition. If such a decomposition is not possible, then even approximating the general backward induction described above will incur complexity exponential in $K$. If that is the case, the Gaussian approximation will have little advantage over the standard backward induction for the original problem in terms of complexity reduction.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength: \n\n1. The idea of using Gaussian approximation to refine the LP-relaxation seems interesting. \n\n2. The result on the $O(1/N)$ optimality gap is a strong. \n\nWeakness:\n\n1. It is unclear how to solve the SP-based policy efficiently.", "was_revised": true, "final_justification": "The rebuttal partially addresses my earlier concerns on the solution complexity of the Gaussian approximation. Even though the complexity is still significantly higher than the fluid limit (with decomposition), at least it seems more manageable. Thus, I increase my rating to Accept. It would be useful to include this complexity discussion in the main body of the paper.", "rebuttal": "We greatly appreciate the positive comments from the reviewer. We next address the computation issue of SP versus the backward induction suggested by the reviewer. \n\nFirst, we would like to clarify that our approach applies to a general number of states, time horizon, and number of arms.\nThe stochastic program (SP) (15)-(17) is for this general setting, and a variety of existing algorithms can be used to solve this SP.\nIn our numerical experiments (Section 5), we used the EDDP algorithm Lan (2022) to solve the SP, and our experiment was for a setting with $K=10$ states per arm and a time horizon of $H=5$. In Figure 5 (Appendix G.3 in the supplementary material), we evaluated the time complexity of EDDP with RMAB size as large as $K=5, H=30$ and $K=30, H=5$.\n\nNext, we would like to discuss in detail the computational complexity.\nIndeed, directly solving the backward induction incurs a complexity of at least $\\Theta(N^K)$, which is exponential in the number of states $K$. In contrast, the SP we formulated allows for more efficient algorithms.\nAt an intuitive level, although the SP doesn't exactly decompose the problem in the same way as the LP does, it still takes advantage of state aggregation.\nMore concretely, our Gaussian approximation aggregates the randomness in state transitions into a Gaussian noise ($\\mathbf{Z}_h$).\nOne of our key ideas is to make the noises ($\\mathbf{Z}_h$'s) independent of actions.\nThis allows the SP to be solved through the Sample Average Approximation (SAA) technique, which uses random samples of the $\\mathbf{Z}_h$'s and reduces the problem into a deterministic linear program.\nThe number of random samples required is polynomial in $N$ and $K$.\nOne straightforward approach then is to solve this SAA-induced linear program using the interior point method (IPM) (see, e.g., recent results on the complexity of IPM in Cohen and Song (2021)), which can already lead to a computation complexity that is polynomial in both $N$ and $K$.\n\nThat said, directly solving the resulting SAA-induced linear program can lead to an exponential dependence on the time horizon.\nIn our paper, we chose to use the recently developed EDDP algorithm to solve the SAA.\nIn our experiments, EDDP solves the SP efficiently, and in these numerical examples, the computational complexity is linear in both the time horizon and the number of states $K$ (Figure 5 in Appendix G.2 in the supplementary material).\n\n\n**References**\n\n- Cohen, M. B., Lee, Y. T., and Song, Z. (2021). \"Solving linear programs in the current matrix multiplication time.\" *Journal of the ACM (JACM)*, 68(1), 1–39.\n\n- Lan, G. (2022). \"Complexity of stochastic dual dynamic programming.\" *Mathematical Programming*, 191(2), 717–754."}]

Author rebuttal:

Meta-review: The paper tackles the degenerate restless MAB in the finite horizon setting with $N$ homogenous arms. While it is widely accepted in prior work that the optimality gap in this setting that can be achieved with LP-based policies is $\Theta(1/\sqrt{N})$, the authors surprisingly proves that using a stochastic-programming-based policy, this optimality gap can be reduced to $\tilde{O}(1/N)$.

The reviewers agree the paper is instructional and well written and the results are novel, surprising and significant as they improve on widely accepted limit. The authors obtain this key new result by way of a novel Gaussian approximation method (see reviewer yu2p's comments). While this Gaussian approximation bears resemblance to diffusion approximation, the authors detail the contrast of their method versus diffusion approximation in their reply to reviewer 5dNH's comments.

The reviewers suggest the submission would be even stronger if it incorporated the essence of the comparison to diffusion approximation, a discussion on the scalability of the approach with respect to the size of the state space and the length of the horizon and provided convincing real-world examples of the utility of the setting.

Nonetheless, the paper represents a strong technical contribution with the potential to spur wide interest in the community, and it is my and the reviewer's opinion that this paper should be accepted.
Decision: Accept (spotlight)