acceptodds
Under review as a conference paper at ICLR 2027

Learning Infinite-Horizon Restless Multi-Armed Bandits With Non-Stationary Dynamics

Abstract

Online restless multi-armed bandits (RMABs) typically assume that each arm evolves according to a Markov Decision Process (MDP) with stationary state transitions and rewards. However, in real-world applications such as healthcare and recommendation systems, these assumptions are often violated by non-stationary dynamics, posing significant challenges for traditional RMAB algorithms. In this work, we investigate -armed online infinite-horizon RMABs with non-stationary transitions constrained by a total variation budget . We propose NS-Whittle, a novel algorithm that integrates arm-specific sliding window reinforcement learning with an upper confidence bound mechanism to simultaneously estimate evolving transition dynamics and manage exploration-exploitation trade-offs. We establish that NS-Whittle achieves a regret bound of by leveraging a relaxed definition of regret. This work provides the first foundational theoretical framework for non-stationary RMAB problems.

Primary area:
reinforcement learning
Keywords:
reinforcement learning, restless bandits, non-stationary

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_RgEwOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies the online learning problem for infinite-horizon restless multi-armed bandits (RMABs) with non-stationary transition dynamics constrained by a total variation budget BB. To avoid the exponential blowup of the joint state space with respect to the number of arms NN, the authors propose NS-Whittle, which maintains arm-specific sliding-window confidence sets (UCB) and combines Extended Value Iteration (EVI) with a Lagrangian-relaxed Whittle index policy. The paper derives a high-probability regret upper bound of O~(N2∣S∣1/2B1/4T3/4)\tilde{\mathcal{O}}(N^2 \vert{}\mathcal{S}\vert{}^{1/2} B^{1/4} T^{3/4}) under a relaxed dynamic regret metric and evaluates the algorithm on a synthetic 10-arm, 2-state environment.

Critical strengths
  1. Studying non-stationary RMABs in an infinite-horizon setting without periodic resets is well-motivated. Maintaining arm-specific sliding windows combined with an optimistic index policy is a natural and sensible direction to avoid the exponential SN\mathcal{S}^N state-space scaling.
  2. The paper rightly notes that non-stationary dynamics can prevent the state distribution from reaching equilibrium, and attempts to avoid standard mixing-time assumptions by applying martingale concentration directly to value-function differences.
Critical weaknesses

The central issue is that the paper does not establish a valid connection between the implementable top-K Whittle policy and the stated hard-constrained RMAB objective. In addition, the key technical lemmas used to control transition-estimation error appear invalid under the paper's own estimator and support assumptions.

  1. Disconnect between policy modeling, Lagrangian relaxation, and the regret objective.

Section 3 defines the joint policy as a product of independent per-arm policies πt(at∣st)=∏iπt,i(at,i∣st,i)\pi_t(a_t \mid s_t) = \prod_i \pi_{t,i}(a_{t,i} \mid s_{t,i}), which is incompatible with strictly satisfying the per-step hard budget constraint ∑iat,i≤K\sum_i a_{t,i} \leq K almost surely; meanwhile, the executed top-KK index policy is inherently a coupled joint policy.

The dual formulation is also inconsistent across sections (switching between a scalar λt\lambda_t in Eqs. (2)/(8) and a state-dependent vector λ(s′)\lambda(s') in Assumption 5.9 and Appendix G, alongside ambiguous notation ∥π(s)∥1≤K\lVert \pi(s) \rVert_1 \leq K).

More importantly, Whittle-index thresholding is generally not an exact optimizer of the finite-NN, per-period hard-constrained RMAB (nor an exact saddle-point solution to Eq. (9)) without additional assumptions or an explicit approximation-gap analysis. The paper bounds min⁡λ1:TReg⁡dyn\min_{\lambda_{1:T}} \operatorname{Reg}_{\mathrm{dyn}} by optimizing the dual sequence in hindsight, without showing how this relaxed quantity bounds the true reward suboptimality or constraint violation of the original problem.

  1. Unjustified steps in the key technical proofs (Lemma D.1 and Lemma 5.12).
  • Zero-visit estimator error and inconsistency (Lemma D.1). Under Eq. (4), when Nt,i(s,a)=0N _ {t,i}(s,a) = 0 within the window, Nt,i+(s,a)=1N ^ + _ {t,i}(s,a) = 1 while the numerator is 00, making P~t,i(⋅∣s,a)\widetilde{P} _ {t,i}(\cdot \mid s,a) the zero vector. Thus, ∥Pt,i(⋅∣s,a)−P~t,i(⋅∣s,a)∥1=1\| P _ {t,i}(\cdot \mid s,a) - \widetilde{P} _ {t,i}(\cdot \mid s,a) \| _ 1 = 1, contradicting Eq. (55) in Appendix D, which claims this norm is 00. Meanwhile, Appendix H states that a uniform distribution is used when no data are available, creating a mismatch among the main text, proof, and implementation.

  • Likelihood-ratio support issue and joint-kernel scaling (Lemma 5.12). Equation (72) in Appendix E relies on the importance ratio P‾t(st+1∣st,at)/Pt(st+1∣st,at)\overline{P} _ t(s _ {t+1} \mid s _ t,a _ t) / P _ t(s _ {t+1} \mid s _ t,a _ t). Because EVI maximizes over an L1L _ 1 -ball confidence set, it does not automatically preserve support inclusion: Pt(s′∣s,a)=0⇒P‾t(s′∣s,a)=0P _ t(s' \mid s,a)=0 \Rightarrow \overline{P} _ t(s' \mid s,a)=0. Therefore, the ratio can be undefined due to division by zero. Assumption E.1 only lower-bounds nonzero transitions and does not resolve this issue. Moreover, PtP _ t in Eq. (72) is a joint transition kernel whereas pmin⁡p _ {\min} is defined at the per-arm level; bounding the joint ratio by pmin⁡−1p _ {\min} ^ {-1} requires a rigorous arm-wise value decomposition that is currently missing. Additionally, the high-probability expression 1−6δ′−N/δ1 - 6\delta' - N/\delta in Theorem 5.4 and Lemma 5.12 does not yield a meaningful probability lower bound for typical small δ\delta, and appears inconsistent with a standard union-bound argument.

  1. Incomplete Whittle-index computation, unverified optimistic indexability, and weak lower-bound reduction.

Line 265 defines Q~λ,i(U)(s,1)\widetilde{Q} _ {\lambda,i}^{(U)}(s,1) as the Whittle index, whereas Eq. (12) defines it as the critical subsidy inf⁡λ{λ:Q~λ,i(U)(s,1)=Q~λ,i(U)(s,0)}\inf_ {\lambda} \{\lambda : \widetilde{Q} _ {\lambda,i}^{(U)}(s,1) = \widetilde{Q} _ {\lambda,i}^{(U)}(s,0)\}. Algorithm 1 runs EVI only once per step at a single fixed λt−1\lambda _ {t-1} and immediately claims to compute Wi(st,i)\mathcal{W} _ i(s _ {t,i}) via Eq. (12), without specifying how the root-finding over λ\lambda is performed.

Furthermore, the paper does not justify why every time-varying optimistic kernel P‾t,i\overline{P} _ {t,i} remains indexable. The rejection sampling in Appendix H only enforces higher value for the active action, which is much weaker than the monotonicity of Bi(λ)B_i(\lambda).

Finally, the lower bound in Theorem 5.3 sets K=NK=N, thereby removing inter-arm budget competition entirely. This is a valid special case only in a limited sense, but it does not capture the central coupling difficulty of RMABs.

  1. Limited empirical evaluation and metric mismatch.

Experiments are restricted to a single toy setting (N=10N=10, ∣S∣=2\lvert\mathcal{S}\rvert=2, K=2K=2) against only Random and stationary Online Whittle, lacking non-stationary baselines (e.g., restart-based or discounted-history methods, or adapted episodic non-stationary RMAB baselines) and scalability tests.

The empirical metric measures immediate reward differences across separate trajectories relative to a clairvoyant Whittle policy rather than the theoretical value-function regret.

Finally, the environment description is unclear. Appendix H describes ρ\rho as a probability of transition change, but then refers to values such as ρ=500,1000,…\rho=500,1000,\ldots, which cannot be probabilities.

Questions for authors
  1. Policy class and relaxation gap: How do the authors reconcile the per-step hard budget constraint, the product-form joint policy definition, and the coupled top-KK execution policy? For finite NN, how does bounding min⁡λ1:TRegdyn\min_{\lambda_{1:T}} \text{Reg}_{\text{dyn}} provide a performance guarantee for the original hard-constrained RMAB objective?

  2. Validity of Lemma D.1 and Lemma 5.12: Please clarify the discrepancy among Eq. (4), Eq. (55), and Appendix H when Nt,i(s,a)=0N_{t,i}(s,a)=0. In Eq. (72), is the optimistic confidence set explicitly constrained to the support of the true kernel, and if not, how is the likelihood ratio defined when Pt(s′∣s,a)=0P_t(s'\mid s,a)=0? Furthermore, how is the per-arm bound pmin⁡−1p_{\min}^{-1} justified for the joint kernel PtP_t without an explicit arm-wise decomposition?

  3. Index computation and optimistic indexability: Since Algorithm 1 runs EVI only at λt−1\lambda_{t-1}, how is the root-finding in Eq. (12) over λ\lambda actually computed at each step, and what is the resulting computational complexity? What guarantees that the optimistic transition kernels remain indexable?

  4. Non-stationary schedule and baselines: Please clarify the exact transition-change schedule involving pp and ρ=500,1000,…\rho = 500, 1000, \dots in Appendix H. How does NS-Whittle perform under persistent (non-decaying) non-stationarity and against stronger non-stationary baselines when per-arm variation budgets ∑tBt,i\sum_t B_{t,i} are unknown a priori?

  5. The manuscript contains editorial oversights. For instance, Appendix H (page 22) inadvertently retains a fragment: "To ensure complete clarity, the final version will incorporate more discussion of the analyzed regret proxy."

6 comments
AuthorsOpenReview ↗

Response to Reviewer RgEw [1/4]

Thank you for identifying the gaps between the problem formulation, the proof, and the implemented policy. We address your questions below.

1. Joint policy, hard budget, and dual notation. The product-form policy in Section 3 was intended to simplify notation, but it does not represent the coupled action selection in NS-Whittle. The execution policy is a joint policy supported on AK={a∈{0,1}N:∑iai≤K}\mathcal A_K=\{a\in\{0,1\}^N:\sum_i a_i\le K\} by the top-KK Whittle rule at each step.

Thank you also for pointing out the inconsistent dual notation. The intended multiplier λt\lambda_t is a scalar shared across all states at round tt. We will revise the state-dependent notation in Assumption 5.9 and Appendix G to reflect this formulation.

2. Lagrangian relaxation and the regret objective. As discussed in our response to reviewer qM2s, the experimental policies activate exactly KK arms at each step. This guarantees hard-budget constrain and makes the Lagrangian penalty zero throughout the evaluation of each fixed policy. For any nonnegative multiplier, the Lagrangian value of any hard-feasible policy is at least its ordinary discounted value. Provided that the relaxed policy class contains all hard-feasible joint policies, weak duality and gives

Reghard,value(T)≤inf⁡λ≥0Regdyn,λ1:T(T).\mathrm{Reg}_{\mathrm{hard,value}}(T) \le \inf_{\lambda \ge 0} \mathrm{Reg}_{\mathrm{dyn},\lambda_{1:T}}(T).

Feasibility follows directly from selecting exactly KK arms. Establishing finite-NN optimality or showing that the implemented policy solves the optimistic minimax problem in Eq. (9) requires a separate argument. Top-KK Whittle-index policy has been deployed in maternal and child health programs [2]. Weber and Weiss [3] establish large-system asymptotic optimality of Top-KK Whittle in the stationary average-reward setting under a global stability condition on the fluid limit. For infinite-horizon discounted RMABs, Zhang and Frazier [4] establish a vanishing per-arm optimality gap for fluid-balance policies as the number of arms grows. Quantifying the finite-NN optimality gap of our top-KK policy under nonstationary discounted dynamics remains future work.

As detailed in our response to qM2s, we can bound two sources of UU EVI iterations. Let Qˉλ,i(U)\bar Q_{\lambda,i}^{(U)} be the iterate after UU sweeps at multiplier λ\lambda and Qˉλ′,i∗\bar Q_{\lambda',i}^{*} the EVI fixed point at a reference multiplier λ′\lambda'. Then

\le \frac{\gamma^U M_{\lambda,i}+|\lambda-\lambda'|}{1-\gamma}, \qquad M_{\lambda,i}=\max_{s,a}|R_i(s,a)-\lambda a|.$$ With $\lambda=\lambda_{t-1}$ and $\lambda'=\lambda_t^\star$, the first term bounds finite-$U$ truncation and the second bounds the effect of using the previous multiplier. Bounding their cumulative effect on the joint top-$K$ policy remains open. [2] Mate et al. (2022). Field Study in Deploying Restless Multi-Armed Bandits. [3] Weber and Weiss (1990). On an Index Policy for Restless Bandits. [4] Zhang and Frazier (2022). Near-optimality for Infinite-Horizon Restless Bandits with Many Arms.
AuthorsOpenReview ↗

Response to Reviewer RgEw [2/4]

3. Unjustified steps in Lemma D.1 and Lemma 5.12.

For the unjustified steps in Lemma D.1, we thank the reviewer for pointing out the error in Eq. (55). In Case 1 of Lemma D.1, when the window contains no visits to (s,a)(s,a), Eq. (4) gives P~t,i(⋅∣s,a)=0\widetilde P_{t,i}(\cdot\mid s,a)=0 and Nt,i+(s,a)=1N^{+}_{t,i}(s,a)=1. Since Pt,i(⋅∣s,a)P_{t,i}(\cdot\mid s,a) is a probability distribution, the correct statement is

\le \mathrm{rad}_{t,i}(s,a)+\eta_i,$$ where $\text{rad}_{t,i}(s,a) = \sqrt{2|S|\log(|S||A|T/\delta)/N^+_{t,i}(s,a)}$, this inequality will hold for a sufficient small $\delta$. Under this condition, the zero-visit confidence set contains the full probability simplex. Appendix H describes the fallback rules used in the experiments. When $(s,a)$ has no visits in the current window but was visited earlier than current window, the implementation estimates the transition distribution from all past visits to $(s,a)$. When $(s,a)$ has never been visited, the transition estimate remains uniform over next states. The reported experiments used these fallback rules without access to the true transition support. For the likelihood-ratio support, joint-kernel scaling, and probability bounds. Because $s_{t+1}$ is sampled from the true transition kernel, $P_t(s_{t+1}\mid s_t,a_t)>0$ almost surely. Let $p_{\min}^{\mathrm{joint}} \geq p_{\min}^{N}$ be the minimum positive transition probability of the true joint kernel over the evaluation horizon. The likelihood ratio at the observed transition is therefore well-defined and bounded by $1/p_{\min}^{\mathrm{joint}}$. This bound can grow exponentially with $N$ because the joint transition probability is a product of per-arm probabilities. We will revise Assumption E.1 to make the support information explicit. At each round $t$, before selecting an action, the theoretical learner knows which entries of each arm's transition kernel $P_{t,i}$ are zero. EVI uses this information by restricting each candidate transition row to assign zero probability to those entries. This adapts the known-zero assumption in Assumption 1 and Eq. (11) of [5] from a stationary MDP to our nonstationary setting. In the reported experiments, the learner had no access to this support information, and EVI was run without the support restriction. With this restriction, any joint next state with zero probability under the true kernel also has zero probability under the optimistic kernel. In Eq. (72), we will evaluate the likelihood ratio at the integration variable $s'$ and sum over the support of the true kernel. This justifies the change-of-measure identity. [5] Reward Biased Maximum Likelihood Estimation for Reinforcement Learning, 2021 Thank you for pointing out the error in Eq. (100). By Lemma A.3, the confidence event $\xi_i$ for each arm fails with probability at most $\delta/2$. A union bound gives $$\Pr\left[\left(\bigcap_{i=1}^N \xi_i\right)^c\right] =\Pr\left[\bigcup_{i=1}^N \xi_i^c\right] \le \sum_{i=1}^N \Pr(\xi_i^c) \le \frac{N\delta}{2}.$$ Thus, the arm-wise confidence events contribute at most $N\delta/2$ to the failure probability in Eq. (100). We will account for the remaining failure events separately in the revised proof. We will also restate Lemma 5.8 as a deterministic implication. Its value comparison holds on any round where the true transition kernel belongs to the confidence set and the exact optimization conditions used in Eq. (17) hold. The probability enters through the confidence event, so Lemma 5.8 does not introduce a separate failure probability.
AuthorsOpenReview ↗

Response to Reviewer RgEw [3/4]

4. Incomplete Whittle-index computation, unverified optimistic indexability, and weak lower-bound reduction..

Definition of Whittle-index Under indexability, the action-value comparison and the Whittle-index threshold rule are equivalent for each state of our two-state fixed model. The action is selected if and only if its activation charge (λ\lambda) is below the Whittle index. At the index, the active and passive action values coincide, as in Eq. (12). We will revise Line 265 to state this equivalence explicitly.

Index computation. As described in Lines 258–262 and Eq. (10), EVI will do UU updates at the fixed multiplier λt−1\lambda_{t-1} to construct an optimistic transition kernel. The implementation then used this kernel, which is fixed in the current time step, and estimates the Whittle index by bisection over the activation charge, which enters the Bellman iteractive update as a penalty on the active action. The policy will recomputes the active and passive action values on the fixed kernel and uses their difference to update the search interval. The bisection procedure is implemented in ns_whittle.py, lines 238–263.

Per-decision cost. Each round performs at most U=10U=10 EVI per arm, followed by one bisection search for the arm's current state. The search starts on [−1,1][-1,1] and halves its interval until the width is at most ε=10−3\varepsilon=10^{-3}, giving L=⌈log⁡2(2/ε)⌉=11L=\lceil\log_2(2/\varepsilon)\rceil=11 candidate evaluations. Each evaluation runs at most M=10M=10 value sweeps, for at most LM=110LM=110 value iteration per arm. With two actions and S=∣S∣S=|\mathcal S| states, the implementation's single decision planning cost is O(N(US+LMS2))O(N(US+LMS^2)).

  • USUS per arm comes from EVI. Each sweep processes 2S2S state-action pairs.
  • LMS2LMS^2 per arm comes from bisection.

Indexability of the optimistic model. The implementation does not enforce indexability of the optimistic kernel. As described above, at round tt we use the previous multiplier λt−1\lambda_{t-1} to construct an optimistic transition kernel via EVI, then hold that kernel fixed throughout the index search. For a fully observed arm with two states, two actions, and discounted rewards, any fixed pair of valid active and passive transition matrices is indexable. This result applies to the optimistic kernel frozen at each round. Under that kernel, the active-minus-passive action-value difference is strictly decreasing in λ\lambda, so we use bisection to approximate the unique charge where the two action values coincide. The indexability guarantee follows from the two-state discounted model structure, independently of the rejection-sampling rule in Appendix H.

Loose lower bound We agree that Theorem 5.3 gives a loose lower bound. The construction sets K=NK=N, so the activation budget is nonbinding and the arms do not compete for activations. A tighter lower bound that captures the difficulty of inter-arm coupling under a binding budget remains an important direction for future work.

Reviewer_C7xdOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies non-stationary restless multi-armed bandits, where each arm’s behavior can change over time, making older observations potentially misleading. The transition dynamics are also unknown and must be learned online, requiring a balance between exploration and exploitation. The main contribution is NS-Whittle, an online algorithm designed for these non-stationary settings. Instead of using the entire history, it focuses on recent data, builds optimistic estimates of how each arm may evolve to encourage exploration, computes a Whittle-index for ranking arms, and activates the highest-priority arms while respecting the resource budget. This avoids treating the entire RMAB as a single MDP, whose joint state space grows exponentially with the number of arms.

Critical strengths

The main results are both algorithmic and theoretical. Algorithmically, the method adapts Whittle index based approaches to unknown, non-stationary dynamics. Theoretically, the authors derive bounds for their regret proxy and establish a sublinear guarantee under non-stationarity. For a stationary transition model, the regret bound simplifies to the best-known bound for the stationary setting.

Critical weaknesses

Could the authors clarify the novelty of this work relative to Cheung et al. (2020) and Wang et al. (2023) in terms of algorithmic components and theoretical results? In particular, which parts of the proposed method and regret analysis are fundamentally new beyond combining the non-stationary techniques of Cheung et al. with the optimistic Whittle-index approach of Wang et al.?

In the experimental results, it would have been interesting to see an ablation of the optimistic transition probabilities, i.e., how the algorithm performs when non-optimistic transition estimates are used instead.

Questions for authors

See above.

1 comment
AuthorsOpenReview ↗

Response to Reviewer C7xd

We thank the reviewer for highlighting the strengths of our work and for suggesting an ablation of optimistic transition selection.

Novelty relative to Cheung et al. (2020) and Wang et al. (2023). Our contribution concerns the learning setting and its analysis. We study discounted RMABs with non-stationary transition and a shared activation budget, evaluated along a single continuing trajectory. To analyze dynamic Lagrangian value regret in this setting, we use a snapshot proxy that freezes the transition kernels at the current round. Lemma 5.1 relates the minimized dynamic regret to this proxy, accounting for transition drift and the time horizon.

Cheung et al. (2020) develop sliding-window estimation and confidence widening for a single nonstationary, undiscounted MDP. We adapt these tools to arm-specific windows and variation budgets. The confidence analysis must therefore account for rounds in which the true transition kernel of any arm falls outside its confidence set. This is the step addressed in Appendix D. Wang et al. (2023) study optimistic Whittle learning for stationary RMABs in an episodic setting, with the joint state reset at the start of each episode. Our analysis instead evaluates time-varying policies along a continuing trajectory.

Ablation of optimistic transition selection. We compare the original NS-Whittle (UCB) with NS-Whittle-LCB. In each EVI update, UCB chooses the transition distribution that maximizes the expected next-state value within the confidence set, while LCB chooses the distribution that minimizes it within the same set. Both variants use the same window and widening settings, Whittle-index solver, and top-KK action rule.

The table reports the cumulative realized reward gap relative to true-model Whittle (mean ± SE over 50 seeds). UCB has a lower mean gap than LCB at all six reported checkpoints. At T=300000T=300000, the mean gap is 25884 for UCB and 28299 for LCB, which also enjoys sub-linear regret performance.

StepNS-WhittleOnline WhittleRandom-KKNS-Whittle-LCB
50,0006,397.31 ± 323.795,236.62 ± 353.6110,672.08 ± 471.7510,178.43 ± 702.12
100,00011,137.95 ± 534.8510,524.37 ± 662.6821,482.64 ± 890.8217,318.47 ± 1,236.82
150,00015,287.92 ± 744.1215,368.70 ± 1,082.8432,209.64 ± 1,293.6622,048.20 ± 1,576.94
200,00019,208.47 ± 936.5519,927.87 ± 1,419.5342,710.63 ± 1,661.7424,404.31 ± 1,788.17
250,00022,903.98 ± 1,141.1124,891.61 ± 1,682.8453,094.90 ± 2,086.8126,695.83 ± 2,091.96
300,00025,884.87 ± 1,312.8229,784.16 ± 1,940.8862,177.96 ± 2,475.0728,299.73 ± 2,291.56
Reviewer_qM2sOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies infinite horizon online restless multi armed bandits with nonstationary transition kernels under a total variation budget. It proposes NS Whittle, which combines arm specific sliding window estimation, optimistic reinforcement learning, and Whittle index scheduling. The paper establishes a sublinear regret upper bound with polynomial dependence on the number of arms, provides a lower bound, and recovers a square root rate in the stationary case. Experiments on a synthetic ten arm environment show improvements over Online Whittle and random selection, with additional studies on window size and budget misspecification.

Critical strengths

1.The paper addresses nonstationary infinite horizon RMABs without episodic resets. This setting is relevant to applications such as healthcare and recommendation systems, and a rigorous solution would constitute a valuable theoretical contribution.

2.Maintaining separate estimates for each arm avoids the exponential growth of the joint state space. Combining this design with optimistic learning and Whittle scheduling provides a coherent approach whose polynomial dependence on the number of arms is consequential for both theory and practice.

Critical weaknesses

1.The analysis assumes an idealized algorithm that exactly solves the optimistic minimax problem. Algorithm 1 instead uses a previous Lagrange multiplier, truncated value iteration, and approximate Whittle scheduling. These approximation errors are not included in the regret analysis, leaving a central gap between the main theorem and the evaluated method.

2.The theory analyzes a relaxed dynamic regret defined through Lagrangian value functions, while the experiments measure immediate reward differences from an oracle Whittle policy. The relationship between these measures and the original cumulative reward objective is not established, so the experiments do not directly validate the main theoretical claims.

3.The window sizes and exploration parameters depend on the variation budget of each arm, which may be unavailable in practice. The misspecification experiments still construct these parameters from the true budgets and therefore do not demonstrate robustness when this prior information is entirely absent. This limitation weakens the practical relevance of the proposed method.

Questions for authors

Please address the concerns raised in the Weaknesses section. I am willing to reconsider and increase my score.

2 comments
AuthorsOpenReview ↗

Response to Reviewer qM2s [1/2]

Thank you for identifying the distinctions between the analyzed optimization problem, the practical algorithm, and the empirical metric. We address these separately.

We agree that the current analysis does not establish a regret guarantee for the evaluated finite-iteration implementation. At a fixed multiplier, the following bound isolates the error due to truncating the extended value iteration in Eq. (10).

Approximation error after UU EVI iterations. Fix round tt, arm ii, and multiplier λ\lambda (set λ=λt−1\lambda=\lambda_{t-1} in Algorithm 1). As in Eq. (10), initialize Qˉλ,i(0)=0\bar Q_{\lambda,i}^{(0)}=0 and let Vˉλ,i(u)(s)=max⁡a∈AQˉλ,i(u)(s,a)\bar V_{\lambda,i}^{(u)}(s)=\max_{a\in\mathcal A}\bar Q_{\lambda,i}^{(u)}(s,a). Write Mλ,i=max⁡s,a∣Ri(s,a)−λa∣M_{\lambda,i}=\max_{s,a}|R_i(s,a)-\lambda a|. For each local pair (s,a)(s,a), let Pˇt,i(U)(⋅∣s,a)\check P_{t,i}^{(U)}(\cdot\mid s,a) be a distribution in Ht,i(s,a,ηi)H_{t,i}(s,a,\eta_i) attaining the maximum in the UU-th update, which uses Vˉλ,i(U−1)\bar V_{\lambda,i}^{(U-1)}. Then

\le \gamma^U M_{\lambda,i}.$$ **Proof.** For fixed $t,i,\lambda$, the update in Eq. (10) is a $\gamma$-contraction in the sup norm. Each probability distribution maps a value difference to an average whose absolute value is bounded by its sup norm. Taking the maximum over feasible distribution preserves this Lipschitz bound. Zero initialization gives $\bar Q_{\lambda,i}^{(1)}(s,a)=R_i(s,a)-\lambda a$, so $$\lVert Q_{\lambda,i}^{(U)}-\bar Q_{\lambda,i}^{(U-1)}\rVert_\infty \le \gamma^{U-1}M_{\lambda,i}.$$ The next-state distribution selected in the $U$-th update satisfies $$\check P_{t,i}^{(U)}(\cdot\mid s,a) \in \arg\max_{p\in H_{t,i}(s,a,\eta_i)} \sum_{s'\in\mathcal S}p(s')\bar V_{\lambda,i}^{(U-1)}(s').$$ Adding and subtracting the continuation term with $\bar V_{\lambda,i}^{(U)}$ gives $$\begin{align} \bar Q_{\lambda,i}^{(U)}(s,a) &= R_i(s,a)-\lambda a +\gamma\sum_{s'\in\mathcal S}\check P_{t,i}^{(U)}(s'\mid s,a)\bar V_{\lambda,i}^{(U-1)}(s')\\\\ &= R_i(s,a)-\lambda a +\gamma\sum_{s'\in\mathcal S}\check P_{t,i}^{(U)}(s'\mid s,a)\bar V_{\lambda,i}^{(U)}(s')+\gamma\sum_{s'\in\mathcal S}\check P_{t,i}^{(U)}(s'\mid s,a) \bigl(\bar V_{\lambda,i}^{(U-1)}(s')-\bar V_{\lambda,i}^{(U)}(s')\bigr). \end{align}$$ The absolute value of the last term is bounded by $\gamma\lVert\bar V_{\lambda,i}^{(U-1)}-\bar V_{\lambda,i}^{(U)}\rVert_\infty\le\gamma^U M_{\lambda,i}$. The contraction also gives $\lVert\bar Q_{\lambda,i}^{(U)}-\bar Q_{\lambda,i}^{*}\rVert_\infty\le \gamma^U M_{\lambda,i}/(1-\gamma)$, where $\bar Q_{\lambda,i}^{*}$ is the fixed point of Eq. (10) for these confidence sets and multiplier. In the experiments, $\lambda_0=0$ and each multiplier update takes a computed index from the search interval $[-1,1]$, so $M_{\lambda_{t-1},i}\le 2$ uniformly over rounds and arms by $R_i(s,a)\in[0,1]$ and $a\in\{0,1\}$. **Effect of using the previous multiplier.** Iterative multiplier updates have been used in [1], which establish the convergence for a primal-dual method with projected sub-gradient descent. Algorithm 1 instead sets the multiplier to the $K$-th largest Whittle index. Extending the regret analysis to Algorithm 1 requires bounding the cumulative discrepancy between the multiplier used by EVI and the optimal multiplier for the current round, $\sum_{t=1}^T |\lambda_{t-1}-\lambda_t^\star|$. Fix round $t$ and arm $i$, and keep $H_{t,i}(s,a,\eta_i)$ fixed for every $(s,a)$. Since $a\in\{0,1\}$, and applying the fixed-point equations and contraction, we have $$\lVert\bar Q_{\lambda,i}^{*}-\bar Q_{\lambda',i}^{*}\rVert_\infty \le \gamma\lVert\bar Q_{\lambda,i}^{*}-\bar Q_{\lambda',i}^{*}\rVert_\infty +|\lambda-\lambda'|.$$ Taking $\lambda=\lambda_{t-1}$ and $\lambda'=\lambda_t^\star$, the scalar multiplier of the round-$t$ idealized comparator, and combining with the finite-$U$ bound gives $$\lVert\bar Q_{\lambda_{t-1},i}^{(U)}-\bar Q_{\lambda_t^\star,i}^{*}\rVert_\infty \le \frac{\gamma^U M_{\lambda_{t-1},i}+|\lambda_{t-1}-\lambda_t^\star|}{1-\gamma}.$$ The bound separates finite-$U$ truncation from the effect of using the previous multiplier. With fixed $U$, summing the truncation bound over $T$ rounds gives an upper bound of $2TN\gamma^U/(1-\gamma)$ in the experimental setting. We leave for future work the control of cumulative truncation and multiplier errors, including whether the Whittle-threshold update yields $\sum_{t=1}^{T}|\lambda_{t-1}-\lambda_t^\star|=o(T)$, and how these per-arm errors translate into a bound for the joint top-$K$ policy. [1] Natural Policy Gradient Primal-Dual Method for Constrained Markov Decision Processes, NeurIPS 2020
AuthorsOpenReview ↗

Response to Reviewer qM2s [2/2]

Theoretical and empirical metrics. Lemma 5.1 bounds the dynamic Lagrangian value regret, minimized over nonnegative multipliers. The minimized Lagrangian regret provides a conservative upper bound on the hard-constrained regret. For any nonnegative multiplier schedule, a hard-feasible Lagrangian value function is at least its ordinary discounted value. For a policy that activates exactly KK arms at every step throughout value evaluation, the Lagrangian penalty will be zero. Thus, we have:

Reghard,value(T)≤inf⁡λ≥0Regdyn,λ1:T(T).\mathrm{Reg}_{\mathrm{hard,value}}(T) \le \inf_{\lambda \ge 0} \mathrm{Reg}_{\mathrm{dyn},\lambda_{1:T}}(T).

In our experiments, Whittle, Online Whittle, and NS-Whittle all use top-KK whittle index policy and exhaust the activation budget at every step. Once these policies are fixed, the induced value gaps are independent of the multiplier update.

The top-KK Whittle policy can be feasible by showing that the algorithm's top-KK policy solves the optimistic minimax problem. Whittle-index scheduling has been deployed in practice, including for allocating outreach calls in maternal and child health programs [2]. For stationary average-reward RMABs, [3] establish large-system asymptotic optimality of Whittle scheduling under a global stability condition on the fluid limit. For infinite-horizon discounted RMABs, [4] establish a vanishing per-arm optimality gap for fluid-balance policies as the number of arms grows. Quantifying the finite-NN optimality gap of our top-KK policy under nonstationary discounted dynamics remains future work.

[2] Field Study in Deploying Restless Multi-Armed Bandits, Mate et al. (2022)

[3] On an Index Policy for Restless Bandits, Weber and Weiss (1990)

[4] Near-optimality for Infinite-Horizon Restless Bandits with Many Arms, Zhang and Frazier (2022)

Cheung et al. (2020)

Unknown variation budgets. Figure 3 has shown the sensitivity to misspecified variation budgets. To further evaluate performance without knowing these budgets, we adapt BORL [5] to NS-Whittle. At the start of each 1000-step block, an EXP3.P master selects a shared window length W∈{100,300,1000}W\in\{100,300,1000\} and confidence-widening parameter η∈{0,0.01,0.05}\eta\in\{0,0.01,0.05\} from the nine candidate pairs.

The following table reports the cumulative regret across the same 50 seeds. At T=300000T=300000, NS-Whittle + BORL achieves a mean gap of 11496 against true-model Whittle, compared with 25884 for the original NS-Whittle.

[5] Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism, Cheung, Simchi-Levi, and Zhu, 2020.

StepNS-Whittle + BORLNS-WhittleOnline WhittleRandom-KK
50,0002,371.05 ± 119.416,397.31 ± 323.795,236.62 ± 353.6110,672.08 ± 471.75
100,0004,252.38 ± 200.5111,137.95 ± 534.8510,524.37 ± 662.6821,482.64 ± 890.82
150,0006,089.47 ± 279.9615,287.92 ± 744.1215,368.70 ± 1,082.8432,209.64 ± 1,293.66
200,0008,037.99 ± 385.5619,208.47 ± 936.5519,927.87 ± 1,419.5342,710.63 ± 1,661.74
250,0009,963.67 ± 478.7722,903.98 ± 1,141.1124,891.61 ± 1,682.8453,094.90 ± 2,086.81
300,00011,496.95 ± 555.6725,884.87 ± 1,312.8229,784.16 ± 1,940.8862,177.96 ± 2,475.07

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.