{"id":"4f68d853-7ef6-4ca4-b06d-e5b5926e3b2a","arxiv_id":"2508.10804","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"First claimed regret bound for non-stationary restless multi-armed bandits via per-arm sliding-window optimism, but it holds for a relaxed regret measure and the proof contains gaps.","lead":"This paper proposes NS-Whittle, an algorithm for restless multi-armed bandit problems whose dynamics drift over time, and claims the first sublinear regret bound for such problems. It is worth reading because non-stationary restless bandits arise in healthcare adherence and recommendation systems, though the guarantee applies to a relaxed performance measure and the proof has gaps.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5.7's joint optimality claim is unproven: the threshold policy from finite-U EVI and the λ update do not imply V^{π_t}_{P̄_t,λ*_t} ≥ V^{π*_t}_{P_t,λ*_t}.","rationale":"The paper's headline guarantee is a sublinear regret bound for non-stationary RMABs. The proof's only bridge between the oracle policy and the learned policy is Lemma 5.7; without it, Reg_{λ*_t}(T) cannot be replaced by Reg'(T), and the subsequent confidence-interval and variation-budget arguments (Lemmas 5.8-5.9) are irrelevant. The reader's verdict flags the same hinge, and I agree that the joint optimality claim is the most load-bearing. I disagree slightly with the framing: the deeper issue is not Whittle indexability per se (the threshold rule is optimal for a fixed λ if Q is exact), but the combination of (a) finite-U EVI with no error control, (b) an affine-in-λ value that makes the 'minimizer' step (i) undefined unless the budget is exactly met, and (c) a policy definition that ignores the K constraint. These are all checkable. The paper's own Section 6 admits the regret is relaxed; that doesn't rescue the proof, but it does mean a corrected proof might still yield a meaningful per-arm bound. Therefore I would not change the reader's REJECT verdict: as written, the central theorem is unproven.","tokens_in":16575,"tokens_out":9156,"duration_ms":97118,"concrete_test":"Build a toy RMAB with N=2, |S|=2, K=1, known piecewise-stationary transitions with one change point, and run NS-Whittle as specified in eqs. (8)-(19) with finite U. For each t, compute the exact joint optimal value V^{π*_t}_{P_t,λ*_t}(s_t) and the algorithm's value V^{π_t}_{P̄_t,λ*_t}(s_t) by brute-force value iteration over the joint state space. Check whether (24) holds at every t and whether (19) ever selects both arms. If (24) fails for any t or (19) exceeds K, Lemma 5.7 is false and Theorem 5.1 does not follow.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The decisive step in Theorem 5.1 is Lemma 5.7, which asserts V^{π_t}_{P̄_t,λ*_t}(s_t) ≥ V^{π*_t}_{P_t,λ*_t}(s_t) via the chain (25): (i) λ_t is the minimizer of V^{π_t}_{P̄_t,λ}(s_t); (ii) π_t and P̄_t maximize V^π_{P,λ_t}(s) for every joint state s. Neither step is established by the algorithm's definitions. For a fixed policy π, V^π_{P,λ}(s) is affine in λ, so the 'minimizer' assertion in (i) is only meaningful if the expected discounted budget violation is exactly zero; no such property is proved for the policy from (19). Step (ii) would require that after U EVI iterations the per-arm greedy policy is the exact optimal policy of the per-arm extended MDP and that the product policy maximizes the joint Lagrangian. The paper provides no EVI error bound in U, and λ_t from (16) is a minimizer of a sum of approximate Q-values at one state-action pair, not of the joint value function. Moreover, eq. (19) can activate more than K arms, while the budget constraint is stated as at most K; the top-K selection appears only in Figure 1, not in the algorithm pseudocode. Thus (24) does not follow and the transition-estimation gap Reg'(T) in (26) cannot be used to bound the claimed Reg_{λ*_t}(T).","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes NS-Whittle, an online restless multi-armed bandit algorithm for non-stationary transition dynamics with bounded variation. The algorithm combines per-arm sliding-window transition estimates, UCB-style confidence sets, extended value iteration (EVI) with optimistic transitions, and a Whittle-index-style threshold policy. The main claim is a frequentist regret bound of order O-tilde(N^2 |S|^{1/2} B^{1/4} T^{3/4}) against a relaxed, Lagrange-relaxed regret definition. The proof route is: Lemma 5.7 substitutes the learned policy and optimistic transition model for the optimal policy in the regret expression; Lemma 5.9 bounds the resulting transition-estimation gap; Lemma 5.8 controls bad events through the variation budget.","tokens_in":16855,"tokens_out":7172,"duration_ms":82943,"significance":"If the main result were correct, this would be the first regret bound for non-stationary RMABs and would avoid the exponential dependence on N that arises from treating the problem as a single large MDP. The per-arm sliding-window decomposition and the use of confidence sets for time-varying transitions are sensible ingredients, and the paper is explicit that the guarantee is for a relaxed regret proxy rather than the standard cumulative dynamic regret. However, the central proof hinges on Lemma 5.7, whose three inequalities are not established by the algorithm as defined. The paper also provides no experiments or concrete verification of the indexability requirements. The contribution is therefore not currently supported by the theoretical analysis.","major_comments":[{"comment":"Step (i) asserts that λ_t minimizes V^{π_t}_{P̄_t,λ}(s_t), but Algorithm 1 computes λ_t in Eq. (16) as argmin of Σ_i Q̄^{(U)}_{λ,i}(s_t,a_t) at one observed state-action pair, not the value function at the joint state. For a fixed policy the value function is affine in λ and may not have a finite minimizer unless the expected discounted budget violation is exactly zero; no such property is proved. Hence the first inequality in (25) does not follow.","section":"§5.3, Lemma 5.7, Eq. (25)(i)"},{"comment":"Step (ii) requires that π_t and P̄_t jointly maximize V^π_{P,λ_t}(s) for every s. This needs Whittle indexability for each per-arm optimistic model, exact optimality after U EVI iterations, and consistency with the at-most-K activation constraint. None of these is established: no indexability assumption appears in the paper, no EVI error bound in U is given, and Eq. (19) can activate more than K arms while the top-K correction appears only in Figure 1, not in Algorithm 1's pseudocode. Thus the joint Lagrangian maximizer claim is unjustified.","section":"§5.3, Lemma 5.7, Eq. (25)(ii)"},{"comment":"Step (iii) treats λ*_t as the minimizer of V^{π*_t}_{P_t,λ}(s_t). The definition in Eq. (6) is argmin_λ max_π V^π_{P_t,λ}, which gives a minimizer for the max over policies only under a saddle-point/minimax condition. No such duality property or indexability condition is proved, so the third inequality is also unsupported.","section":"§5.3, Lemma 5.7, Eq. (25)(iii)"},{"comment":"The proof of B5 divides by P_t(st+1 | st, at). Assumption 5.6 only lower-bounds nonzero entries of the true transition; it does not prevent the optimistic model P̄_t chosen from H_t from assigning positive mass to states that are unreachable under P_t. In that case the ratio P̄_t/P_t is undefined or infinite. A support-matching constraint is missing from H_t, so the importance-ratio argument in Eq. (56) does not hold as written.","section":"§5.5, Lemma 5.9, Eq. (56)"},{"comment":"The paper itself states that the relaxed formulation 'may not fully capture non-stationary dynamics.' That acknowledgement is directly relevant because Theorem 5.1 bounds Reg_{λ*_t}(T) after replacing the oracle term with the learned value via Lemma 5.7. Without Lemma 5.7, the bound is for Reg'(T) in Eq. (26), not for the regret definition in Eq. (7).","section":"§6, Limitations"}],"minor_comments":[{"comment":"The pseudocode does not match Figure 1: there is no top-K selection in Algorithm 1, and the inner 'while until Q̄, λ converge' loop has no termination criterion. The notation λ_{t+1} on line 8 is also inconsistent with the use of λ_t in Eqs. (18)--(19).","section":"Algorithm 1"},{"comment":"Eq. (21) and Eq. (69) state an equality where an inequality is intended, and the claimed probability '1 − 6δ' − N/δ' can be negative for small δ. Lemma 5.7 similarly states probability '1 − N/δ'. These should be corrected to meaningful probability statements.","section":"Theorem 5.1"},{"comment":"The optimal window size W*_i = |S| T^{1/2}(Σ_t B_{t,i})^{-1/2} requires per-arm total variation, but the problem description only gives a global budget B. The dependency of the final bound on per-arm budgets should be clarified.","section":"Remark 5.2"},{"comment":"The symbols P̄_t, P̄_{t,i}, λ_t, and λ*_t are used with overlapping meanings in Eqs. (17)--(19), and in Eq. (15) the reward R_{t,i}(s,a) should presumably be the stationary per-arm reward R_i(s,a). Clarifying this would improve readability.","section":"Notation"},{"comment":"The probability statement in Appendix C switches between '1 − 3δ' and '1 − 3δ′' without explanation, and the martingale bound in Eq. (49) uses 2δ' while Lemma 5.9 states 6δ'. These inconsistencies should be reconciled.","section":"Appendix C"}],"recommendation":"reject","confidential_remarks":"The central theorem depends on Lemma 5.7, and each step of its proof chain is unsupported by the algorithm as written. The missing pieces are not minor: they include Whittle indexability, exactness of EVI, handling of the K-arm budget in the policy, and the relationship between λ_t and the value-function minimizer. The relaxed-regret benchmark is also explicitly acknowledged in Section 6 as only an approximation. As a result, I do not see a local fix that would preserve the claimed contribution within the current scope. This is a reject rather than a major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is the first paper to claim a sublinear regret bound for non-stationary RMABs, and the per-arm sliding-window decomposition is a sensible way to avoid the exponential state space. But the central theorem does not follow from the proof as written. Lemma 5.7, which does all the work, asserts exactly what the algorithm is not shown to deliver.\n\nThe problem is real and the high-level approach has merit. Treating each arm separately, using sliding-window estimates with UCB-style optimism, and then doing a per-arm Whittle-index-style threshold is a plausible route; the T^{3/4} scaling and the N^2 dependence on the number of arms are the right shape. I give credit for the problem framing and for the relaxed regret definition (7)-(26), even though the relationship to the true non-stationary regret is left unquantified (the authors admit this in Section 6).\n\nThe soft spots are not minor. Lemma 5.7's chain requires λ_t to be a minimizer of the joint value function, π_t and P̄_t to jointly maximize the Lagrangian for every state, and λ*_t to be the minimizer of the oracle value. Step (ii) is asserted, not derived: the per-arm threshold policy from finite-U EVI, the λ update computed only at the observed (s,a), and the at-most-K activation constraint (the top-K step appears only in Figure 1) together do not imply joint optimality. No EVI truncation error in U is given. As written, the substitution (24) is unsupported, and the regret bound collapses.\n\nThere is also a suspicious importance-sampling step in the proof of Lemma 5.9, where the likelihood ratio uses s_{t+1} instead of the integration variable s'. And Theorem 5.1 states a random quantity as a deterministic equality; the stated success probability 1-6δ'-N/δ is negative for any reasonable δ' and δ; and the exponent of B changes from B^{3/4} in the Introduction to B^{1/4} in the Abstract and Remark 5.2. The last is probably a typo, but the first two are not.\n\nWho is this for? Researchers working on online RMABs and non-stationary MDPs. It does not give them a usable algorithm with a proven guarantee, but it does frame the problem and propose a decomposition that may be repairable. If a revision can prove the key substitution or modify the algorithm so that it holds, this could become a useful paper.\n\nMy recommendation: yes, send to peer review. The problem is open, the approach is not crazy, and the flaws are specific enough that a careful referee could either fix them or kill the paper cleanly. But I would not cite the current bound as established.","headline":"First non-stationary RMAB regret analysis, but the central substitution lemma is unproven; the bound doesn't follow as written.","tokens_in":17485,"tokens_out":4947,"would_cite":false,"duration_ms":49800,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Non-stationary restless multi-armed bandits can be learned online with sublinear regret: the NS-Whittle algorithm attains $\\widetilde{\\mathcal{O}}(N^2 |\\mathcal{S}|^{1/2} B^{1/4} T^{3/4})$ against a frozen-dynamics oracle.","keywords":["restless multi-armed bandits","non-stationary Markov decision processes","sliding window","upper confidence bound","Whittle index","extended value iteration","regret bound","online learning"],"falsifier":"On a two-arm, two-state drifting instance with known small variation budget $B$, brute-force compute $V^{\\pi_t}_{\\bar P_t,\\lambda^*_t}(s_t)$ and $V^{\\pi^*_t}_{P_t,\\lambda^*_t}(s_t)$ at each step. If the former is ever smaller, Lemma 5.7 fails and Theorem 5.1 does not follow. Alternatively, run NS-Whittle with the optimal $W^*$ and $\\eta^*$ from Remark 5.2 on synthetic drifting data and measure cumulative regret against the frozen-dynamics oracle; a growth rate clearly above $T^{3/4}$ would falsify the claimed bound.","tokens_in":16286,"feed_emoji":"🎰","tokens_out":12699,"duration_ms":111800,"temperature":0.7,"pith_summary":"This paper tries to establish the first online learning guarantee for restless multi-armed bandits in which each arm's transition probabilities drift over time, subject to a total variation budget $B$. The proposed algorithm, NS-Whittle, estimates each arm's current dynamics from its own sliding window of recent observations, builds an optimistic transition model with an upper confidence bound (UCB) radius, and then activates the arms with the largest Whittle indices computed by extended value iteration. The main result is a high-probability regret bound of $\\widetilde{\\mathcal{O}}(N^2 |\\mathcal{S}|^{1/2} B^{1/4} T^{3/4})$ against a relaxed oracle that freezes dynamics, policy, and Lagrange multiplier at their current values. A sympathetic reader should care because the paper shows that drift does not force exponential dependence on the number of arms, and because the bound matches the best known stationary RMAB rate when $B=0$.","feed_headline":"Sliding windows yield sublinear regret for drifting restless bandits","feed_subtitle":"Each arm learns its own drifting dynamics, so regret stays sublinear and never touches the exponential joint state space.","key_machinery":"The load-bearing mechanism is the pair formed by a sliding-window UCB confidence set and an optimistic Whittle-index policy. The Whittle index is a per-arm priority score derived from the Lagrangian relaxation of the activation budget. The sliding window with length $W_i$ turns non-stationary estimation into a bias-variance trade-off: shorter windows track drift, longer windows reduce sampling error, and the UCB radius $rad_{t,i}(s,a)$ keeps the confidence set optimistic. EVI solves the per-arm Bellman update with the transition matrix as an additional control variable, producing $\\bar Q^{(U)}_{\\lambda,i}$, and the threshold rule activates arm $i$ whenever $\\bar Q_{\\lambda_t,i}(s_{t,i},1) \\g","core_discovery":"On its own terms, the paper's discovery is that a non-stationary RMAB can be solved arm-by-arm, without ever forming the joint state space $\\mathcal{S}^N$. At each time $t$ and arm $i$, a sliding window of length $W_i$ gives an empirical transition estimate $\\tilde P_{t,i}$, and a UCB radius $rad_{t,i}(s,a)$ defines a confidence set $H_{t,i}$ of plausible transitions. Extended value iteration (EVI) maximizes the Lagrangian action-value $\\bar Q^{(U)}_{\\lambda,i}$ over $P \\in H_{t,i}$, and the policy activates arm $i$ when the optimistic active value exceeds the passive value. The key step, Lemma 5.7, substitutes the optimal oracle value with the learned value under optimistic transitions, $V^","pith_inferences":["If Lemma 5.7 holds, the same arm-wise sliding-window-plus-optimism recipe should extend to other index-based policies (queueing, wireless scheduling), provided each per-arm optimistic model remains indexable.","The relaxed regret proxy may understate the gap to a fully adaptive oracle; a direct comparison against an oracle that knows all future transitions in advance would reveal how much of the bound is due to the relaxation.","The dependence on $p_{\\min}^{-1}$ in Lemma 5.9 suggests the bound is loose for sparse transition matrices; a tighter concentration or importance-sampling argument might remove that factor and possibly improve the $B^{1/4}$ rate.","The paper assumes rewards are stationary and known; if rewards also drift, a windowed reward estimator would add a reward-variation term, likely giving a similar $T^{3/4}$ bound with $B$ replaced by a combined variation budget."],"forward_implications":["If Theorem 5.1 is correct, non-stationary RMABs are learnable at the same $T^{3/4}$ rate as non-stationary single-agent MDPs, with only polynomial dependence on the number of arms and the per-arm state-space size.","When $B=0$, choosing $W=T$ and $\\eta=1/T$ recovers $\\widetilde{\\mathcal{O}}(N^2|\\mathcal{S}|\\sqrt{T})$, matching the best known stationary RMAB regret, so the result extends the stationary theory rather than only proving a bound on a harder problem.","Because the algorithm optimizes each arm separately and then selects the top $K$ arms, it avoids the exponential joint state space, making it computationally plausible for large-$N$ applications such as health interventions and recommendation systems.","The guarantee is stated against a relaxed oracle that re-optimizes each time step with frozen dynamics; a bound against a fully adaptive dynamic oracle would require additional argument and is not the same result."],"supporting_citations":[{"why":"Supplies the sliding-window confidence-set machinery and the bad-event counting lemmas (Lemma A.2 and A.3) that NS-Whittle adapts to per-arm estimation.","marker":"[8]"},{"why":"Provides the stationary optimistic Whittle-index baseline, including the per-arm EVI routine and the $\\widetilde{\\mathcal{O}}(N|\\mathcal{S}|\\sqrt{T})$ regret bound that Remark 5.3 matches when $B=0$.","marker":"[7]"},{"why":"Gives extended value iteration and the visitation-counting lemma (Lemma 19 in [21]) used to bound the transition-estimation gap in Lemma 5.9.","marker":"[21]"},{"why":"Introduces the Whittle index policy for restless bandits, the decomposable per-arm priority rule on which the algorithm's threshold policy is based.","marker":"[15]"},{"why":"Establishes indexability conditions under which the Whittle index threshold is optimal per arm, a requirement for the value substitution in Lemma 5.7.","marker":"[16, 17]"},{"why":"Provides the stationary episodic Thompson-sampling regret bound used as a baseline when the variation budget is zero.","marker":"[9]"},{"why":"Provides the stationary non-episodic Thompson-sampling regret bound that Remark 5.3 also matches in the $B=0$ case.","marker":"[10]"}],"fun_headline_variants":["Sliding-window RL yields provable regret for drifting bandits","Arm-by-arm learning handles non-stationary restless bandits","Drifting transitions? Sliding-window UCB keeps regret sublinear","No joint state space: provable regret for non-stationary RMABs"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"Everything rests on the assumption that the per-arm index threshold is the true maximizer of the joint relaxed objective at every state—each optimistic model is Whittle-indexable and the computed Lagrange multiplier is the exact minimizer—because if this fails, the proof's central value substitution breaks.","fun_headline_variants_meta":{"raw":{"variants":["Sliding-window RL yields provable regret for drifting bandits","Arm-by-arm learning handles non-stationary restless bandits","Drifting transitions? Sliding-window UCB keeps regret sublinear","No joint state space: provable regret for non-stationary RMABs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000746,"raw_usage":{"total_tokens":3155,"prompt_tokens":727,"completion_tokens":2428,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":471,"completion_tokens_details":{"reasoning_tokens":2350}},"tokens_in":471,"tokens_out":2428,"duration_ms":18785,"temperature":1.0,"reasoning_tokens":2350,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T20:19:29.177888+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a two-arm, two-state drifting instance with known small variation budget $B$, brute-force compute $V^{\\pi_t}_{\\bar P_t,\\lambda^*_t}(s_t)$ and $V^{\\pi^*_t}_{P_t,\\lambda^*_t}(s_t)$ at each step. If the former is ever smaller, Lemma 5.7 fails and Theorem 5.1 does not follow. Alternatively, run NS-Whittle with the optimal $W^*$ and $\\eta^*$ from Remark 5.2 on synthetic drifting data and measure cumulative regret against the frozen-dynamics oracle; a growth rate clearly above $T^{3/4}$ would falsify the claimed bound.","supporting_citations":[{"cited_title":"Reinforcement learning for non- stationary markov decision processes: The blessing of (more) optimism","cited_arxiv_id":null,"evidence_quote":"Supplies the sliding-window confidence-set machinery and the bad-event counting lemmas (Lemma A.2 and A.3) that NS-Whittle adapts to per-arm estimation."},{"cited_title":"Optimistic whittle index policy: Online learning for restless bandits","cited_arxiv_id":null,"evidence_quote":"Provides the stationary optimistic Whittle-index baseline, including the per-arm EVI routine and the $\\widetilde{\\mathcal{O}}(N|\\mathcal{S}|\\sqrt{T})$ regret bound that Remark 5.3 matches when $B=0$."},{"cited_title":"Near-optimal regret bounds for reinforcement learning","cited_arxiv_id":null,"evidence_quote":"Gives extended value iteration and the visitation-counting lemma (Lemma 19 in [21]) used to bound the transition-estimation gap in Lemma 5.9."},{"cited_title":"On an index policy for restless bandits","cited_arxiv_id":null,"evidence_quote":"Introduces the Whittle index policy for restless bandits, the decomposable per-arm priority rule on which the algorithm's threshold policy is based."},{"cited_title":"Regret bounds for thompson sampling in episodic restless bandit problems","cited_arxiv_id":null,"evidence_quote":"Provides the stationary episodic Thompson-sampling regret bound used as a baseline when the variation budget is zero."}],"review_version":1}