Search papers, labs, and topics across Lattice.
This paper extends the Whittle index policy framework for restless multi-armed bandits under partial observability by introducing a $t$-step lookahead threshold policy that accounts for longer-horizon continuation values. The authors prove that the $t$-step approximate Whittle index converges geometrically to the exact Whittle index, with numerical experiments demonstrating a significant reduction in index error as $t$ increases. Notably, the proposed method does not require prior indexability and includes a verification process, making it a robust advancement in the field.
The $t$-step lookahead policy reduces index error from $2.18\times10^{-2}$ to $8.93\times10^{-4}$, demonstrating that longer lookahead significantly improves decision-making in restless bandits.
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$.
