A new computational study reports that looking several steps ahead can substantially sharpen decisions in partially observable restless bandits, a class of problems in which each arm has a hidden state and the decision-maker must choose when to activate it. In one high-discount test, the one-step approximation put Arms 1 and 2 in the wrong order, while a two-step lookahead recovered the exact ranking of 1 > 2 > 3. That ordering remained in place at depths three and four.
The work examines a t-step extension of a one-step boundary approximation for the Whittle index. In plain terms, the method looks for the subsidy, or trial value for leaving an arm passive, at which activating an arm and leaving it passive become equally attractive, then uses the resulting threshold in arm comparisons. The model represents each arm with a belief state because its underlying state is hidden: passive operation updates the belief through the transition matrix, while activation reveals the hidden state and sets the next belief to a transition row.
A boundary that can move with the subsidy
The key difference from the one-step version is that deeper lookahead recalculates the quantities that determine the first point at which the active and passive options cross as the trial subsidy changes. At one step, the threshold is independent of the subsidy and recovers the earlier linearized threshold. Beyond one step, the threshold can shift with the subsidy and track the exact decision boundary more closely.
The computation does not require indexability as an input. Instead, it calculates a finite-depth approximate index and adds a numerical check based on whether candidate subsidy solutions agree. The accompanying theorem gives an if-and-only-if criterion: for every belief, all admissible subsidy solutions must converge to one unique subsidy as lookahead depth increases. The study therefore treats indexability as something to test numerically, rather than a condition that must be assumed before the calculation begins.
Accuracy improved as the lookahead grew
Across the reported three-state tests, the approximation moved closer to a high-depth reference as t increased. The 95th-percentile error fell from 2.18 × 10−2 at one step to 8.93 × 10−4 at eight steps. The maximum error fell from 6.27 × 10−2 to 2.79 × 10−3 over the same comparison.
The proposed numerical criterion classified all 2,715 tested three-state instances as indexable. That is a result of the specified numerical procedure, not a proof that every instance in the broader class is indexable. The verification used a subsidy grid, finite-depth searches and a prescribed tolerance, so its conclusion depends on those choices.
The mathematical result is stronger under a specific condition. If the original problem is exactly Whittle indexable, the authors prove that the t-step approximate index converges geometrically to the exact Whittle index as lookahead depth becomes large. The theorem does not remove that condition, and the randomly generated test cases did not have exact indices available for direct comparison.
Small policy tests pointed in the same direction
The study also compared policies in a six-arm problem with a budget of one active arm, a discount factor of 0.99 and a horizon extending to six steps. The optimal policy had the highest reported average reward, while finite-lookahead policies closed most of the gap to it. The improvement from one-step to two-step lookahead was especially clear later in the horizon.
On the exact-comparable finite-horizon instance, the policies using two-step and five-step thresholds produced nearly identical curves, and both performed better than the one-step Whittle-index policy. These findings come from a small, finite-horizon comparison and do not show that the lookahead policies are globally optimal or generally superior.
The trade-off was time
Greater accuracy came with a gradual increase in computation time. In the runtime experiment, each listed depth was measured with 80 samples. Median time per sample rose from 0.0509 seconds at one step to 0.2009 seconds at 15 steps, while the 90th-percentile time stayed close to the median. The result suggests a practical accuracy-cost trade-off in the tested implementation, with moderate depths potentially offering a useful compromise.
The evidence remains entirely computational. Exact Whittle indices were unavailable for the randomly generated instances, so their errors were measured against a depth-15 approximation used as the reference. The policy comparison was small and finite-horizon, and runtime was measured in one CPU-only experiment without inferential uncertainty intervals. The reported results therefore remain limited to the tested configurations.
The document is a preprint identified as arXiv:2608.24167v2 and dated 3 September 2026. The work was supported by the Leadership Talent Program (Science and Education) of SIP, grant KJQ2024202.
Paper data and sources
Original title: From Relaxed Indexability to Exact Indexability: A $t$-Step Approach for Partially Observable Restless Bandits
Authors: Qizhen Jia, Keqin Liu
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-25
DOI: Not available
Original paper · Full text