- 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 . To avoid the exponential blowup of the joint state space with respect to the number of arms , 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 under a relaxed dynamic regret metric and evaluates the algorithm on a synthetic 10-arm, 2-state environment.
Critical strengths
- 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 state-space scaling.
- 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.
- Disconnect between policy modeling, Lagrangian relaxation, and the regret objective.
Section 3 defines the joint policy as a product of independent per-arm policies , which is incompatible with strictly satisfying the per-step hard budget constraint almost surely; meanwhile, the executed top- index policy is inherently a coupled joint policy.
The dual formulation is also inconsistent across sections (switching between a scalar in Eqs. (2)/(8) and a state-dependent vector in Assumption 5.9 and Appendix G, alongside ambiguous notation ).
More importantly, Whittle-index thresholding is generally not an exact optimizer of the finite-, 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 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.
- 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 within the window, while the numerator is , making the zero vector. Thus, , contradicting Eq. (55) in Appendix D, which claims this norm is . 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 . Because EVI maximizes over an -ball confidence set, it does not automatically preserve support inclusion: . 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, in Eq. (72) is a joint transition kernel whereas is defined at the per-arm level; bounding the joint ratio by requires a rigorous arm-wise value decomposition that is currently missing. Additionally, the high-probability expression in Theorem 5.4 and Lemma 5.12 does not yield a meaningful probability lower bound for typical small , and appears inconsistent with a standard union-bound argument.
- Incomplete Whittle-index computation, unverified optimistic indexability, and weak lower-bound reduction.
Line 265 defines as the Whittle index, whereas Eq. (12) defines it as the critical subsidy . Algorithm 1 runs EVI only once per step at a single fixed and immediately claims to compute via Eq. (12), without specifying how the root-finding over is performed.
Furthermore, the paper does not justify why every time-varying optimistic kernel remains indexable. The rejection sampling in Appendix H only enforces higher value for the active action, which is much weaker than the monotonicity of .
Finally, the lower bound in Theorem 5.3 sets , 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.
- Limited empirical evaluation and metric mismatch.
Experiments are restricted to a single toy setting (, , ) 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 as a probability of transition change, but then refers to values such as , which cannot be probabilities.
Questions for authors
-
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- execution policy? For finite , how does bounding provide a performance guarantee for the original hard-constrained RMAB objective?
-
Validity of Lemma D.1 and Lemma 5.12: Please clarify the discrepancy among Eq. (4), Eq. (55), and Appendix H when . 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 ? Furthermore, how is the per-arm bound justified for the joint kernel without an explicit arm-wise decomposition?
-
Index computation and optimistic indexability: Since Algorithm 1 runs EVI only at , how is the root-finding in Eq. (12) over actually computed at each step, and what is the resulting computational complexity? What guarantees that the optimistic transition kernels remain indexable?
-
Non-stationary schedule and baselines: Please clarify the exact transition-change schedule involving and 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 are unknown a priori?
-
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
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 , Eq. (4) gives and . Since 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.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 () 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 updates at the fixed multiplier 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 EVI per arm, followed by one bisection search for the arm's current state. The search starts on and halves its interval until the width is at most , giving candidate evaluations. Each evaluation runs at most value sweeps, for at most value iteration per arm. With two actions and states, the implementation's single decision planning cost is .
- per arm comes from EVI. Each sweep processes state-action pairs.
- 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 we use the previous multiplier 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 , 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 , 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.
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} by the top-K Whittle rule at each step.
Thank you also for pointing out the inconsistent dual notation. The intended multiplier λt is a scalar shared across all states at round t. 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 K 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).
Feasibility follows directly from selecting exactly K arms. Establishing finite-N optimality or showing that the implemented policy solves the optimistic minimax problem in Eq. (9) requires a separate argument. Top-K Whittle-index policy has been deployed in maternal and child health programs [2]. Weber and Weiss [3] establish large-system asymptotic optimality of Top-K 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-N optimality gap of our top-K policy under nonstationary discounted dynamics remains future work.
As detailed in our response to qM2s, we can bound two sources of U EVI iterations. Let Qˉλ,i(U) be the iterate after U sweeps at multiplier λ and Qˉλ′,i∗ the EVI fixed point at a reference multiplier λ′. 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.