Non-Stationary Restless Multi-Armed Bandits with Provable Guarantee

Kai Wang; Ping-Chun Hsieh; Yu-Heng Hung

REVIEW 5 major objections 5 minor 29 references

Non-Stationary Restless Multi-Armed Bandits with Provable Guarantee

T0 review · 5 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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.

desk verdict First non-stationary RMAB regret analysis, but the central substitution lemma is unproven; the bound doesn't follow as written. read the letter →

arxiv 2508.10804 v1 pith:ZNKFVYHF submitted 2025-08-14 cs.LG

Yu-Heng Hung , Ping-Chun Hsieh , Kai Wang This is my paper

classification cs.LG

keywords restlessmulti-armedbanditsnon-stationaryMarkovdecisionprocessesslidingwindowupperconfidenceboundWhittleindexextendedvalueiterationregretonlinelearning

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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$.

What carries the argument

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

What would settle it

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.

Watch

Extended reading notes

Core claim

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^

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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).

The 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.

There 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.

Who 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.

My 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.

Referee Report

5 major / 5 minor

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.

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 (5)

[§5.3, Lemma 5.7, Eq. (25)(i)] 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.
[§5.3, Lemma 5.7, Eq. (25)(ii)] 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.
[§5.3, Lemma 5.7, Eq. (25)(iii)] 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.
[§5.5, Lemma 5.9, Eq. (56)] 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.
[§6, Limitations] 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).

minor comments (5)

[Algorithm 1] 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).
[Theorem 5.1] 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.
[Remark 5.2] 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.
[Notation] 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.
[Appendix C] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the regret proxy and the estimation-gap substitution form an ordinary optimism-based upper bound, not a definitional equivalence.

full rationale

The paper's derivation does not, on inspection, reduce a 'prediction' to its own inputs by construction. The regret in (7) is defined against the frozen-dynamics optimal value V^{π*_t}_{P_t,λ*_t}(s_t) − V^{π_t}_{P_t,λ*_t}(s_t). Lemma 5.7 then claims the upper bound V^{π_t}_{P̄_t,λ*_t}(s_t) ≥ V^{π*_t}_{P_t,λ*_t}(s_t), converting regret into the transition-estimation gap Reg′(T) of (26). This is an inequality whose proof is intended to come from the algorithm's internal optimality conditions; it is not an equality of definitions. The central bound then controls Reg′ via confidence radii and the variation budget B, which is a standard optimism/UCB argument rather than a tautology. The paper's own Section 6 explicitly acknowledges that the relaxed formulation 'substitutes the optimal value function with the learned one, potentially introducing an approximation gap.' That is a legitimate caveat, and the unproven assertions inside Lemma 5.7 (e.g., that λ_t is the minimizer of V^{π_t}_{P̄_t,λ}(s_t) and that π_t, P̄_t jointly maximize V^π_{P,λ_t}(s)) are correctness gaps, not circular steps: they do not make the claimed regret bound equivalent to the algorithm's inputs. The only self-citation ([7] in Remark 5.3) is a non-load-bearing comparison to a stationary RMAB bound and does not support the main theorem. Therefore no circularity is established.

Assumptions & free parameters 3 free parameters · 7 assumptions · 0 invented entities

The bound rests on two stated problem assumptions (bounded Lagrange multipliers U_λ; a uniform lower bound p_min on non-zero transitions) plus several unstated structural assumptions: that the learner restricts to product policies, that the optimistic per-arm models are indexable so the threshold rule is optimal, that the learner knows B to tune windows, and that finite EVI and the λ-loop are exact. The regret bound contains U_λ, p_min, N², and B terms, so the guarantee degrades when these constants are unfavorable.

free parameters (3)

sliding window sizes W_i (arm-specific) = |S| T^{1/2} (Σ_t B_{t,i})^{-1/2} (Remark 5.2)
Chosen to optimize the bound; requires knowing per-arm variation budgets; the bound's T^{3/4} scaling is sensitive to W.
exploration bonus η_i = sqrt(B W*_i / T) (Remark 5.2)
Ad hoc optimism parameter; balances the T N η term against the bad-event count W B / η.
EVI iterations U = under-specified input (Algorithm 1; κ is unused)
Truncation error γ^U/(1-γ) is never accounted for in the regret analysis; the algorithm's λ-while-loop is similarly left as 'until converge'.

assumptions (7)

domain assumption The optimal Lagrange multipliers are uniformly bounded: λ*_t ≤ U_λ for all t (Assumption 5.4).
Needed for Lemma 5.5's value bound N(1+U_λ)/(1-γ); the paper notes unbounded multipliers would make sublinear regret intractable.
domain assumption All non-zero transition probabilities are at least p_min > 0 (Assumption 5.6).
Controls the importance-sampling ratio P̄/P in Lemma 5.9's proof (eq. 51); p_min appears in the denominator of the regret bound.
domain assumption The learner restricts to product policies, and the benchmark (6) is over the same restricted class.
Makes the Lagrangian value decompose across arms, enabling per-arm EVI; restricts the optimality benchmark relative to coordinated joint policies.
ad hoc to paper The per-arm optimistic models are Whittle-indexable, so the threshold policy (19) is the per-arm Lagrangian maximizer.
Never stated nor proved; required for Lemma 5.7 step (ii).
ad hoc to paper The learner knows the total variation budget B (to set W_i and η_i optimally).
Unflagged; Remark 5.2 tunes W_i, η_i with B; no doubling scheme is provided.
ad hoc to paper The EVI iterates and the λ-loop converge exactly (or U is effectively infinite).
Algorithm 1 line 6 'until converge' with U-step EVI; the analysis treats Q̄ as the exact fixed point.
standard math Standard concentration inequalities (Azuma-Hoeffding, Lemma A.1) and the sliding-window lemmas of [8] (Lemmas A.2, A.3).
Imported background used for the confidence sets and martingale bounds; accepted as standard.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Non-Stationary Restless Multi-Armed Bandits with Provable Guarantee." pith.science (2026). https://pith.science/paper/ZNKFVYHF

@misc{pith2026250810804,
  author       = {Pith},
  title        = {Pith review of: Non-Stationary Restless Multi-Armed Bandits with Provable Guarantee},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZNKFVYHF}},
  note         = {Machine review of arXiv:2508.10804}
}

abstract

Online restless multi-armed bandits (RMABs) typically assume that each arm follows a stationary Markov Decision Process (MDP) with fixed state transitions and rewards. However, in real-world applications like healthcare and recommendation systems, these assumptions often break due to non-stationary dynamics, posing significant challenges for traditional RMAB algorithms. In this work, we specifically consider $N$-armd RMAB with non-stationary transition constrained by bounded variation budgets $B$. Our proposed \rmab\; algorithm integrates sliding window reinforcement learning (RL) with an upper confidence bound (UCB) mechanism to simultaneously learn transition dynamics and their variations. We further establish that \rmab\; achieves $\widetilde{\mathcal{O}}(N^2 B^{\frac{1}{4}} T^{\frac{3}{4}})$ regret bound by leveraging a relaxed definition of regret, providing a foundational theoretical framework for non-stationary RMAB problems for the first time.

Figures

Figures reproduced from arXiv: 2508.10804 by the authors.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

29 extracted references · 23 canonical work pages

[1]

Whittle’s index policy for a multi-class queueing system with convex holding costs

PS Ansell, Kevin D Glazebrook, José Nino-Mora, and M O’Keeffe. Whittle’s index policy for a multi-class queueing system with convex holding costs. Mathematical Methods of Operations Research, 57:21–39, 2003

work page 2003
[2]

Dynamic allocation indices for restless projects and queueing admission control: a polyhedral approach

José Nino-Mora. Dynamic allocation indices for restless projects and queueing admission control: a polyhedral approach. Mathematical programming, 93(3):361–413, 2002

work page 2002
[3]

Field study in deploying restless multi- armed bandits: Assisting non-profits in improving maternal and child health

Aditya Mate, Lovish Madaan, Aparna Taneja, Neha Madhiwalla, Shresth Verma, Gargi Singh, Aparna Hegde, Pradeep Varakantham, and Milind Tambe. Field study in deploying restless multi- armed bandits: Assisting non-profits in improving maternal and child health. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 12017–12025, 2022

work page 2022
[4]

Collapsing bandits and their application to public health intervention

Aditya Mate, Jackson 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

work page 2020
[5]

Distributed optimal relay selection in wireless cooperative networks with finite-state markov channels

Yifei Wei, F Richard Yu, and Mei Song. Distributed optimal relay selection in wireless cooperative networks with finite-state markov channels. IEEE Transactions on Vehicular Technology, 59(5):2149–2158, 2010

work page 2010
[6]

Cell association with user behavior awareness in heterogeneous cellular networks

Yao Sun, Gang Feng, Shuang Qin, and Sanshan Sun. Cell association with user behavior awareness in heterogeneous cellular networks. IEEE Transactions on Vehicular Technology, 67(5):4589–4601, 2018

work page 2018
[7]

Optimistic whittle index policy: Online learning for restless bandits

Kai Wang, Lily Xu, Aparna Taneja, and Milind Tambe. Optimistic whittle index policy: Online learning for restless bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 10131–10139, 2023

work page 2023
[8]

Reinforcement learning for non- stationary markov decision processes: The blessing of (more) optimism

Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Reinforcement learning for non- stationary markov decision processes: The blessing of (more) optimism. In International conference on machine learning, pages 1843–1854. PMLR, 2020

work page 2020

Show all 29 references

[9]

Regret bounds for thompson sampling in episodic restless bandit problems

Young Hun Jung and Ambuj Tewari. Regret bounds for thompson sampling in episodic restless bandit problems. Advances in Neural Information Processing Systems, 32, 2019

2019
[10]

Thompson sampling in non-episodic restless bandits

Young Hun Jung, Marc Abeille, and Ambuj Tewari. Thompson sampling in non-episodic restless bandits. arXiv preprint arXiv:1910.05654, 2019

1910 arXiv
[11]

Restless bandits: Activity allocation in a changing world

Peter Whittle. Restless bandits: Activity allocation in a changing world. Journal of applied probability, 25(A):287–298, 1988

1988
[12]

Introduction to multi-armed bandits

Aleksandrs Slivkins et al. Introduction to multi-armed bandits. Foundations and Trends® in Machine Learning, 12(1-2):1–286, 2019

2019
[13]

Algorithms for multi-armed bandit problems.arXiv preprint arXiv:1402.6028, 2014

V olodymyr Kuleshov and Doina Precup. Algorithms for multi-armed bandit problems.arXiv preprint arXiv:1402.6028, 2014

2014 arXiv
[14]

The complexity of optimal queuing network control

Christos H Papadimitriou and John N Tsitsiklis. The complexity of optimal queuing network control. Mathematics of Operations Research, 24(2):293–305, 1999

1999
[15]

On an index policy for restless bandits

Richard R Weber and Gideon Weiss. On an index policy for restless bandits. Journal of applied probability, 27(3):637–648, 1990. 10

1990
[16]

A restless bandit formulation of opportunistic access: Indexablity and index policy

Keqin Liu and Qing Zhao. A restless bandit formulation of opportunistic access: Indexablity and index policy. In 2008 5th IEEE Annual Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks Workshops, pages 1–5. IEEE, 2008

2008
[17]

Indexability of restless bandit problems and optimality of whittle index for dynamic multichannel access.IEEE Transactions on Information Theory, 56(11):5547– 5567, 2010

Keqin Liu and Qing Zhao. Indexability of restless bandit problems and optimality of whittle index for dynamic multichannel access.IEEE Transactions on Information Theory, 56(11):5547– 5567, 2010

2010
[18]

Qwi: Q-learning with whittle index

Francisco Robledo, Vivek Borkar, Urtzi Ayesta, and Konstantin Avrachenkov. Qwi: Q-learning with whittle index. ACM SIGMETRICS Performance Evaluation Review, 49(2):47–50, 2022

2022
[19]

Learn to intervene: An adaptive learning policy for restless bandits in application to preventive healthcare

Arpita Biswas, Gaurav Aggarwal, Pradeep Varakantham, and Milind Tambe. Learn to intervene: An adaptive learning policy for restless bandits in application to preventive healthcare. arXiv preprint arXiv:2105.07965, 2021

2021 arXiv
[20]

Towards q-learning the whittle index for restless bandits

Jing Fu, Yoni Nazarathy, Sarat Moka, and Peter G Taylor. Towards q-learning the whittle index for restless bandits. In 2019 Australian & New Zealand Control Conference (ANZCC), pages 249–254. IEEE, 2019

2019
[21]

Near-optimal regret bounds for reinforcement learning

Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008

2008
[22]

Logarithmic online regret bounds for undiscounted reinforcement learning

Peter Auer and Ronald Ortner. Logarithmic online regret bounds for undiscounted reinforcement learning. Advances in neural information processing systems, 19, 2006

2006
[23]

Regal: A regularization based algorithm for reinforcement learning in weakly communicating mdps

Peter L Bartlett and Ambuj Tewari. Regal: A regularization based algorithm for reinforcement learning in weakly communicating mdps. arXiv preprint arXiv:1205.2661, 2012

2012 arXiv
[24]

Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach

Chen-Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach. In Conference on learning theory, pages 4300–4354. PMLR, 2021

2021
[25]

A sliding-window algorithm for markov decision processes with arbitrarily changing rewards and transitions

Pratik Gajane, Ronald Ortner, and Peter Auer. A sliding-window algorithm for markov decision processes with arbitrarily changing rewards and transitions. arXiv preprint arXiv:1805.10066, 2018

2018 arXiv
[26]

Near-optimal model-free reinforcement learning in non-stationary episodic mdps

Weichao Mao, Kaiqing Zhang, Ruihao Zhu, David Simchi-Levi, and Tamer Basar. Near-optimal model-free reinforcement learning in non-stationary episodic mdps. In International conference on machine learning, pages 7447–7458. PMLR, 2021

2021
[27]

Learning in a changing world: Restless multiarmed bandit with unknown dynamics

Haoyang Liu, Keqin Liu, and Qing Zhao. Learning in a changing world: Restless multiarmed bandit with unknown dynamics. IEEE Transactions on Information Theory, 59(3):1902–1916, 2012

1902
[28]

Regret bounds for discounted mdps

Shuang Liu and Hao Su. Regret bounds for discounted mdps. arXiv preprint arXiv:2002.05138, 2020

2002 arXiv
[29]

X t∈N γt−1 R(st, at) − λ∗ t πt(st)⊤1 − K | s1 = s # (31) ≤ E(s,a)∼(P ,πt)

P Kumar and Woei Lin. Optimal adaptive controllers for unknown markov chains. IEEE Transactions on Automatic Control, 27(4):765–774, 1982. 11 A Useful Lemmas Lemma A.1 (Azuma-Hoeffding inequality). Let (Xi, Fi)i=1,··· ,t to be a martingale satisfying Xi < M,∀i ∈ [t], for some ...

1982

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.

[1] [1]

Whittle’s index policy for a multi-class queueing system with convex holding costs

PS Ansell, Kevin D Glazebrook, José Nino-Mora, and M O’Keeffe. Whittle’s index policy for a multi-class queueing system with convex holding costs. Mathematical Methods of Operations Research, 57:21–39, 2003

work page 2003

[2] [2]

Dynamic allocation indices for restless projects and queueing admission control: a polyhedral approach

José Nino-Mora. Dynamic allocation indices for restless projects and queueing admission control: a polyhedral approach. Mathematical programming, 93(3):361–413, 2002

work page 2002

[3] [3]

Field study in deploying restless multi- armed bandits: Assisting non-profits in improving maternal and child health

Aditya Mate, Lovish Madaan, Aparna Taneja, Neha Madhiwalla, Shresth Verma, Gargi Singh, Aparna Hegde, Pradeep Varakantham, and Milind Tambe. Field study in deploying restless multi- armed bandits: Assisting non-profits in improving maternal and child health. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 12017–12025, 2022

work page 2022

[4] [4]

Collapsing bandits and their application to public health intervention

Aditya Mate, Jackson 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

work page 2020

[5] [5]

Distributed optimal relay selection in wireless cooperative networks with finite-state markov channels

Yifei Wei, F Richard Yu, and Mei Song. Distributed optimal relay selection in wireless cooperative networks with finite-state markov channels. IEEE Transactions on Vehicular Technology, 59(5):2149–2158, 2010

work page 2010

[6] [6]

Cell association with user behavior awareness in heterogeneous cellular networks

Yao Sun, Gang Feng, Shuang Qin, and Sanshan Sun. Cell association with user behavior awareness in heterogeneous cellular networks. IEEE Transactions on Vehicular Technology, 67(5):4589–4601, 2018

work page 2018

[7] [7]

Optimistic whittle index policy: Online learning for restless bandits

Kai Wang, Lily Xu, Aparna Taneja, and Milind Tambe. Optimistic whittle index policy: Online learning for restless bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 10131–10139, 2023

work page 2023

[8] [8]

Reinforcement learning for non- stationary markov decision processes: The blessing of (more) optimism

Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Reinforcement learning for non- stationary markov decision processes: The blessing of (more) optimism. In International conference on machine learning, pages 1843–1854. PMLR, 2020

work page 2020