From Relaxed Indexability to Exact Indexability: A t-Step Approach for Partially Observable Restless Bandits
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 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, |Ŵ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×10−2 at t=1 to 8.93×10−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.
Related
- Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits
- Minimum Rate For Partially Observable Linear System with Side Information: LQG Plant and Gaussian-Markov Source
- A Decentralized Partially Observable Team Decision Methodology with Delayed Information Sharing
- Ramp Metering Control via Hybrid State Deep Reinforcement Learning in Partially Observable Connected Vehicle Environments
- Adaptive relaxed CQ algorithm with dynamic stepsizes for the split feasibility problem
BibTeX
@misc{liu2026from,
title = {{From Relaxed Indexability to Exact Indexability: A $t$-Step Approach for Partially Observable Restless Bandits}},
author = {Keqin Liu and Qizhen Jia},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.24167},
eprint = {2608.24167},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.24167},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - From Relaxed Indexability to Exact Indexability: A t-Step Approach for Partially Observable Restless Bandits
AU - Keqin Liu
AU - Qizhen Jia
PY - 2026
DA - 2026/09/06
PB - arXiv
DO - 10.48550/arxiv.2608.24167
UR - https://arxiv.org/abs/2608.24167
AB - 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, |Ŵ_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×10^−2 at t=1 to 8.93×10^−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.
ER -