CS Paper Radar

Optimal Threshold Type Policies for Partially Observable Restless Bandits

Anu Krishna, Rahul Meshram, Kesav Ram Kaza

eess.SY ·submitted 2026-09-12 11:21 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Whittle Index Policy for Three State Collapsing Bandits

eess.SY ·2026-10-27 ·Rahul Meshram, Anu Krishna, Kesav Ram Kaza
similarity 0.75
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.

0.20

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

Budgeted Bayesian Bandits for Future Utilization

cs.LG cs.DS ·2026-10-16 ·Sudipto Guha
similarity 0.69
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

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

Safety by Design: Realized-Cost Constraints for Contextual Bandits with Continuous Actions

cs.LG ·2026-08-27 ·Spyros Dragazis, Aldo Pacchiano
theory similarity 0.66
Abstract

Contextual bandits are a standard framework for sequential decision-making under uncertainty, with applications in clinical trials, dosage selection, recommendation systems, and autonomous systems. Safety is central in many of these applications, since a single unsafe decision in settings such as dosage selection or autonomous driving can have catastrophic consequences. A common way to model safety in bandit problems is to associate each action with both a reward signal and a cost signal, and to optimize reward subject to constraints on cost. Most existing safety-constrained bandit models enforce safety by requiring the expected cost of each action to remain below a prescribed threshold. However, this may be insufficient in heteroscedastic settings, where the chosen action affects not only the expected reward and cost, but also the variability of the observed outcomes. We study contextual bandits with one-dimensional continuous actions and stage-wise high-probability constraints on the realized cost. We propose High-Probability Constrained UCB, an optimistic-pessimistic algorithm that explores for reward while conservatively estimating the safe action set. For linear reward and cost models, we prove a tight $\tilde{\mathcal{O}}(d\sqrt{T})$ regret bound, and we extend the analysis to general function classes using the eluder dimension. Experiments show that enforcing realized-cost safety substantially reduces violations compared with expected-cost constrained baselines.

0.08

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

High-Probability Regret Bounds for Feel-Good Thompson Sampling

cs.IT stat.MLcs.LG ·2026-10-14 ·Xuheng Li, Qingyue Zhao, Quanquan Gu
similarity 0.66
Abstract · 22 pages

Feel-good Thompson sampling (FGTS) augments the posterior of vanilla Thompson sampling with an exploration term that favors reward functions with high predicted optimal values. This modification achieves minimax-optimal regret up to logarithmic factors in linear contextual bandits, but existing analyses of its two standard variants establish regret guarantees in expectation. In this paper, we derive the first high-probability regret bounds for both cumulative and current-step FGTS in contextual bandits with general realizable function approximation. Our bounds depend on the corresponding decoupling coefficients and the prior mass near the true reward function. In the $d$-dimensional linear setting, both variants satisfy $\mathrm{Regret}(T)=O\big(d\sqrt T\log(2T)+\sqrt T\log(1/δ)\big)$ with probability at least $1-δ$, where $T$ is the time horizon. This bound matches the dimension and horizon dependence of algorithms based on the upper confidence bounds, up to logarithmic factors. Relative to the expected-regret guarantees, the cost of controlling the regret with high probability is confined to additive terms with at most linear dependence on $\log(1/δ)$. The proof ideas are partially developed by GPT-6 Astra under the authors' guidance.

0.19

Minimax estimation of the pseudo-spectral gap of continuous Markov chains, with applications to empirical concentration bounds

cs.LG stat.MLmath.ST ·2026-10-14 ·Vahe Karagulyan, Mikołaj Kasprzak, Pierre Alquier
similarity 0.66
Abstract

We study the minimax estimation of the pseudo-spectral gap $γ_{ps}$ of a Markov chain from the observation of a single trajectory. Extending earlier works on finite-state space chains by Wolfer and Kontorovich (2024), we provide an estimator in the case of a compact, continuous state-space. Our estimator appears to be minimax-optimal on the class of chains with a transition operator with Lipschitz density, up to logarithmic terms. Our estimator, combined with Paulin's version of Bernstein inequality, allows to derive empirical concentration inequalities for Markov chains. This unlocks many applications, from confidence intervals, to active learning and generalization bounds. In particular, for rested bandits with Markov rewards, we provide a version of UCB with a regret bound similar to the one in the iid case, without assuming any knowledge on the pseudo-spectral gap of the chains.

0.43