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

arXiv cs.LG Papers
restless-bandits whittle-index partial-observability indexability t-step-approximation convergence-theory

Summary

This paper proposes a t-step lookahead threshold policy for Whittle index in partially observable restless bandits, proving geometric convergence to the exact index and enhancing numerical accuracy.

arXiv:2608.24167v1 Announce Type: new Abstract: 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 algorithm 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(\omega)-W(\omega)|=O(\beta^t). \] Numerically, all 2,715 tested three-state instances are verified as indexable 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 $\beta=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$.
Original Article
View Cached Full Text

Cached at: 08/26/26, 09:35 AM 

# From Relaxed Indexability to Exact Indexability: A $t$-Step Approach for Partially Observable Restless Bandits
Source: [https://arxiv.org/abs/2608.24167](https://arxiv.org/abs/2608.24167)
[View PDF](https://arxiv.org/pdf/2608.24167)

> Abstract: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 algorithm 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\(\\omega\)\-W\(\\omega\)\|=O\(\\beta^t\)\. \\\] Numerically, all 2,715 tested three\-state instances are verified as indexable 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 $\\beta=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$\.

## Submission history

From: Keqin Liu Prof\. \[[view email](https://arxiv.org/show-email/abfbb4af/2608.24167)\] **\[v1\]**Tue, 25 Aug 2026 07:31:30 UTC \(511 KB\)

Similar Articles

Stochastic Linear Bandits with Partially Observed Actions

arXiv cs.LG

This paper studies stochastic linear bandits where the agent only observes a random subset of action coordinates, proving that sublinear regret is possible when actions have low intrinsic dimension, and proposes the TOFU-POV algorithm with theoretical guarantees.

Randomized Exploration for Linear Bandits via Absolute Perturbations

arXiv cs.LG

This paper proposes Absolute Thompson Sampling (ATS), a modification of Thompson Sampling that ensures optimism in expectation by using absolute exploration noise, enabling a simpler UCB-style regret analysis while maintaining computational efficiency. It achieves regret matching existing TS bounds, and introduces an ensemble variant that converges to UCB behavior.

Discrepancy-Rounded Fair Bandits with Static and Time-Varying Exposure Floors

arXiv cs.LG

This paper introduces a discrepancy-rounding framework for stochastic bandits with exact minimum-exposure constraints, achieving fair regret governed by the nonmandatory budget rather than horizon. It proposes algorithms with minimax and instance-dependent optimality guarantees, handles time-varying and overlapping group floors, and validates through experiments.

When Determinants Are Not Enough: Private Rare Switching

arXiv cs.LG

This note presents a research moment where Codex helped find a new rare-switching rule for private linear bandits, using the generalized Rayleigh quotient to overcome the failure of determinant-based monotonicity due to Gaussian noise.