CS Paper Radar

Whittle Index Policy for Three State Collapsing Bandits

Rahul Meshram, Anu Krishna, Kesav Ram Kaza

eess.SY ·submitted 2026-10-27 06:52 UTC · v2

Abstract

Partially observable restless multi-armed bandit models have been studied for dynamic resource allocation problems under uncertainty. This paper analyzes three-state restless multi-armed bandits with partial observability. These are called collapsing bandit problems if the state of an arm (bandit) is perfectly observable when it is scheduled for allocation. The state is not observable when the arm is not scheduled. The planner has a budget constraint on the scheduling decisions in each time slot. The planner's goal is to maximize expected cumulative long term discounted reward. We study the Whittle index policy. To analyze index policy, first the $N$-armed collapsing bandit problem is decoupled into $N$ single arm problems, and convexity and monotonicity of the optimal value function in belief vector are derived using monotone likelihood ratio (MLR) ordering on state transition dynamics and monotone reward structure assumption. We next show that the optimal policy is of threshold type in belief under sufficiency conditions on the model. These sufficiency conditions depend on Lipschitz bound on the value function in the belief. We further prove the indexability for an arm using Lipschitz bound on subsidy sensitivity with minimal restrictive assumption on the transition probability model and discount factor $β.$ Our results generalize to three state and strengthen existing results on threshold policy and indexability with weaker model assumptions. We provide index computation algorithm and we present comparison of the Whittle-index, myopic policy and round-robin policies in the simulation study.

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Threshold Type Policies for Partially Observable Restless Bandits

eess.SY ·2026-09-12 ·Anu Krishna, Rahul Meshram, Kesav Ram Kaza
similarity 0.75
Abstract

We study a finite-state partially observable restless multi-armed bandit (PO-RMAB) motivated by resource-constrained wildlife monitoring. The underlying condition of each location evolves independently, while only a limited number of locations can be actively monitored at each decision epoch. Activation reveals the current state, whereas passive operation provides no observation, yielding a collapsing-bandit belief dynamics. Our main contribution is a structural characterisation of optimal policies for the multidimensional belief-state problem. We establish sufficient conditions under which an activation advantage is monotone with respect to the belief state, and hence the optimal policy has the threshold type structure over the $(M-1)$-dimensional belief simplex. The key result is obtained by bounding the variation of the value function through a model-dependent Lipschitz constant. We further specialise the result to one-step birth-death dynamics and derive explicit bounds.

0.05

From Relaxed Indexability to Exact Indexability: A $t$-Step Approach for Partially Observable Restless Bandits

cs.LG math.OC ·2026-08-25 ·Keqin Liu, Qizhen Jia
benchmarktheory similarity 0.75
Abstract · Fixed some errors in the previous version

Whittle index policies offer a scalable method for restless multi-armed bandits, but under partial observability even determining the indifference subsidy at a single belief requires solving an infinite-horizon belief-state problem with no closed-form value function. Liu [10] addresses this difficulty by linearizing the unknown decision boundary, leading to a linear system and a closed-form approximate Whittle index. However, the resulting threshold uses only a one-step active--passive comparison and does not account for longer-horizon continuation values. We extend this framework to a \emph{$t$-step lookahead threshold policy}. For each subsidy $m$, the threshold is defined by the active-minus-passive advantage under $t$-step finite-horizon value iteration. At $t=1$, the threshold is $m$-independent and recovers the linear threshold of Liu [10]; for $t>1$, it becomes subsidy-dependent through the induced first-crossing structure and tracks the exact decision boundary more closely. The proposed algorithmic framework does not require indexability as an input and includes an indexability verification. Under the original Whittle indexability, we prove that the $t$-step approximate Whittle index converges geometrically to the exact Whittle index, \[ |\widehat W_t(ω)-W(ω)|=O(β^t). \] Numerically, all 2,715 tested three-state instances are verified with computable priority index functions according to the proposed criterion. The P95 index error decreases from $2.18\times10^{-2}$ at $t=1$ to $8.93\times10^{-4}$ at $t=8$. In an exact-comparable instance with $β=0.9999$, $t=2$ already recovers the exact Whittle-index ordering. Moderate-depth threshold policies also outperform the one-step baseline and remain close to the optimal dynamic-programming benchmark, while runtime grows mildly with $t$.

0.13

Load Balancing with Partial Queue Information - Threshold Optimality and Indexability

cs.NI ·2026-09-23 ·Sathwik Chadaga, Eytan Modiano
theory similarity 0.73
Abstract

We consider the problem of load balancing in a system with one dispatcher and $N$ parallel servers. The dispatcher must select one server to dispatch new jobs at every time-step and each server buffers incoming jobs in a queue. However, the dispatcher does not know the servers' backlogs and must make dispatching decisions based on previous observations. The dispatcher's objective is to dispatch jobs to the shortest queue. This problem can be formulated as a restless multi-arm bandit (RMAB) problem where each arm's state is its corresponding belief vector. Our goal is to verify Whittle indexability for this problem and derive a low complexity Whittle index policy. Previous Whittle indexability results cannot be directly applied due to the multi-dimensional nature of the belief vector. To overcome this issue, we define the RMAB state as the tuple of the most recent backlog observation and the time since this observation. We consider two model variations, a standard finite queue model and a blocking queue model. We show that the single-arm decoupled problems of both these models have threshold optimal solutions under some assumptions. For the standard finite queue model, we prove indexability and derive the Whittle index policy in closed form. For the blocking queue model, we derive a sufficient condition for indexability under threshold optimality and use it to show indexability for some special cases.

0.14

Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping

cs.LG math.OCstat.ML ·2026-09-19 ·Huikang Liu, Zhengchao Wang, Daniel Kuhn, Wolfram Wiesemann
benchmark similarity 0.71
Abstract · This work is a preprint and has not been submitted to any conference or journal yet

We develop an index policy for finite-horizon Bernoulli multi-armed bandits from minimax solutions to single-arm bandit (SAB) problems. Each SAB problem involves choosing between an unknown Bernoulli arm and a known reward. We show that minimizing worst-case regret of SAB problems over all non-anticipative policies admits an exact semi-infinite linear programming formulation. The resulting stopping policies offer a natural way to compare arms: the higher the known reward against which a policy continues sampling, the more promising the unknown arm. We turn this intuition into indices based on cumulative continuation probabilities, with a monotone adjustment and a reward-shortfall cap. By relating index errors to the regret of single-arm stopping policies, we establish a distribution-free regret bound of $4.45\sqrt{KT}+10.75K$ for $K$ arms and horizon $T$. This bound matches the minimax-optimal regret order established in the literature. The guarantee extends to rewards supported on $[0,1]$ through Bernoulli randomization. We also provide a finite-grid implementation with quantified approximation loss. In numerical experiments, the SAB-based index policy achieves lower worst-case regret than every tested benchmark policy across all evaluated numbers of arms and horizons, while closely matching the grid-based MAB minimax policy in the two-arm setting.

0.21

Achieving an $O(1/N)$ Optimality Gap in Average-Reward Weakly-Coupled MDPs

cs.LG math.OCmath.PR ·2026-09-29 ·Yige Hong, Xiangcheng Zhang, Qiaomin Xie, Yudong Chen, Weina Wang
similarity 0.71
Abstract · 18 pages

We study average-reward weakly-coupled Markov decision processes (WCMDPs), where a WCMDP consists of $N$ smaller MDPs, called arms, that share multiple per-step budget constraints. We consider the setting where the arms have identical model parameters, multiple actions, and state- and action-dependent costs. For restless bandits (RBs), a well-studied special case of WCMDPs, prior work has developed policies that achieve an $O(1/\sqrt{N})$ optimality gap under general conditions, and has further identified conditions under which policies can achieve a better-than-$1/\sqrt{N}$ optimality gap. However, for general WCMDPs, no prior result achieves an optimality gap better than $1/\sqrt{N}$. In this paper, we identify conditions analogous to those for RBs under which a better-than-$1/\sqrt{N}$ optimality gap is achievable, and design a policy that attains an $O(1/N)$ optimality gap. Notably, unlike prior approaches based on generalizing priority orderings, our policy is not priority-based but rather is designed to induce locally linear mean-field dynamics.

0.25

Budgeted Bayesian Bandits for Future Utilization

cs.LG cs.DS ·2026-10-16 ·Sudipto Guha
similarity 0.70
Abstract

The multi-armed bandit problem models the trade-off between exploration and exploitation. In this paper, we study the variant where exploration has a hard budget and precedes exploitation. Prior guarantees include a 1/3 approximation by Guha and Munagala using Lagrangian duality, and a 4/27 approximation by Ma against a primal linear programming relaxation for a more general model. We show that the analyses of both algorithms are tight, even when their relaxations are asymptotically exact. We provide a different efficient algorithm that achieves a 0.43 approximation. We then provide an efficient algorithm whose guarantee approaches 1-e^{-1} approx 0.63 for bounded exchangeable reward observations in a non-vanishing regime, which is asymptotically tight against natural linear programming relaxations. The technique also gives certificates for stopping sequential model evaluation.

0.14

Planned Restlessness: Delayed Meta Bandits with Budgets

cs.LG cs.DS ·2026-10-28 ·Sudipto Guha
theory similarity 0.68
Abstract

We study episodic finite-horizon Bayesian bandits, or meta-bandits, with independent arms. Each episode draws fresh arm qualities from unknown recurring priors. Observations arrive after known delays, and plays obey hard per-episode caps and total budgets. A play earns reward and informs both the current quality and the recurring prior: the learner must explore, use, and generalize. We formulate a common planning optimization over learning trajectories. Its LP relaxation values experiments through current reward, resource consumption and continuation: the value of future decisions from the learning state produced. Dual prices separate the arms into local programs and certify every admissible policy, including hierarchical Thompson sampling. Execution enforces the hard constraints while preserving the promised learning transitions or accounting for their loss. The framework also represents risk-sensitive objectives and prices purchased observations and buyout options. Delayed reports create planned restlessness: an arm's information changes while it is not played, through reports of its own earlier plays arriving on a known calendar. For stationary priors, finite reward alphabets, bounded report lag and nonbinding budgets, posterior sampling over the recurring priors bounds the price of not knowing them by $O(\sqrt{N})$ over $N$ episodes, with other parameters fixed. For one undelayed $T$-step episode with arms capped at $T/X$ plays each, we obtain the LP-relative approximation factor $1+(2πX)^{-1/2}+O(X^{-1})$, improving previous factors, with a matching lower bound for the leading term.

0.13

Beyond Monotonicity: Stochastic Online Optimization under Semi-Bandit Feedback

cs.LG ·2026-11-02 ·Tsubasa Harada, Yasushi Kawase, Hanna Sumita
theory similarity 0.67
Abstract · 44 pages, 1 figure

We study stochastic online optimization (SOO) under semi-bandit feedback: in each of $T$ rounds, a policy adaptively observes $n$ independent random variables with unknown distributions, learning only from observed values. First-order stochastic dominance (FSD) monotonicity enables general reductions for learning SOO, but can fail when observations change future feasibility, resource use, or reference points. Our algorithm runs the dynamic program for the optimal policy, replacing each expectation by its most optimistic value over a confidence set of distributions. Its regret depends on the level-set complexity $s_i$ of the computed values as functions of the $i$th variable: the number of intervals needed to describe their superlevel sets. For rewards in $[0,1]$, the regret is $\tilde{O}(\sqrt{ST})$ without this monotonicity, where $S=\sum_{i=1}^n\min\{s_i,k_i\}$ and $k_i$ is the support size of the $i$th distribution, which may be infinite when $s_i$ is finite. For constant level-set complexities, regret is $\tilde{O}(\sqrt{nT})$, even for continuous distributions. The algorithm requires no knowledge of $s_i$, $k_i$, or the supports, and it also achieves regret $\tilde{O}(\sqrt{nkT})$ for supports of size at most $k$ without any level-set condition, which improves the previous bound $\tilde{O}(n(\sqrt{kT}+k))$ for FSD-monotone problems. We also prove a lower bound of $Ω(\min\{T,\sqrt{ST}\})$ for all positive integers $s_1,\ldots,s_n$ with $k_i=2s_i+1$, which holds even under full feedback and matches the upper bound up to logarithmic factors. We obtain $\tilde{O}(\sqrt{nT})$ regret for these problems, all nonmonotone under FSD: stochastic Boolean function evaluation, the full-information secretary problem, optimal stopping with loss aversion, scheduling with deadlines and correlated stochastic knapsack with unimodal rewards, and overbooking with group reservations.

0.16