Source-linked AI summary
From Relaxed Indexability to Exact Indexability: A $t$-Step Approach for Partially Observable Restless Bandits
Qizhen Jia, Keqin Liu
TL;DR
Partial observability makes Whittle-index computation an infinite-horizon belief-state problem without a closed-form value function. The paper introduces a subsidy-dependent t-step lookahead threshold and approximate index, proving geometric convergence under exact indexability and reporting improved numerical accuracy with mild runtime growth.
Problem
Partial observability turns Whittle-index computation into an infinite-horizon belief-state POMDP problem without a closed-form value function.
Method
The paper defines a t-step finite-horizon active-passive threshold, computes its approximate index through first-crossing linear systems, and includes indexability verification.
Results
Under original Whittle indexability, the approximate index converges geometrically; P95 error falls from 2.18 × 10−2 at t=1 to 8.93 × 10−4 at t=8.
Takeaways & Limitations
Moderate-depth threshold-index policies outperform one-step and myopic baselines while remaining close to the optimal dynamic-programming benchmark, with mildly increasing runtime.
Takeaways & Limitations
For t>1, the threshold and induced first-crossing quantities depend on subsidy, so the indifference equation is solved locally on affine pieces rather than globally in closed form.
Abstract
from arXiv · showhide
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(ω)-W(ω)|=O(β^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 $β=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$.
1 Introduction
Partial observability turns the single-arm problem into a continuous-belief POMDP, making exact Whittle-index computation difficult. The paper extends Liu’s one-step boundary approximation with subsidy-dependent t-step lookahead and proves convergence to the exact index under indexability.
- Partial observability replaces the finite state with a continuous belief vector, so indifference requires an infinite-horizon belief-state POMDP value function.
- Liu’s method linearizes the unknown decision boundary and uses first-crossing times to obtain a finite linear system and closed-form approximate index.Its threshold uses only the immediate active-passive comparison and omits longer-horizon continuation values.
- The paper defines a t-step lookahead threshold from the active-minus-passive advantage under t-step finite-horizon value iteration.At t=1 it recovers Liu’s threshold; for t>1 it depends on the subsidy and tracks the exact boundary more closely.
- The algorithm computes the finite-t approximate index without indexability as an input and numerically verifies indexability when multiple subsidy solutions arise.
- Under original Whittle indexability, the approximate index converges geometrically to the exact Whittle index.
- 2.18 × 10−2 to 8.93 × 10−4: P95 index error decreases from t=1 to t=8 across the reported numerical experiments.All 2,715 tested three-state instances are verified as indexable; t=2 recovers exact ordering in an instance with β=0.9999.
2 Related Work
Prior work develops indexability and priority-index frameworks, while partially observable models often require restrictive structure for tractable exact indices. Liu’s one-step linearization leaves t-step construction and convergence open; this paper addresses both gaps.
- Classical restless-bandit work characterizes indexability through relaxations, structured policy families, conservation laws, and marginal reward-resource measures.
- PCL and marginal-productivity methods compute priority indices from discounted reward and resource measures associated with structured single-arm policies.
- Partially observable restless-bandit studies commonly restrict hidden states or impose threshold, observation, or restart structure to make exact indices tractable.
- Liu linearizes the unknown boundary, computes passive first crossings, and obtains a closed-form approximate index from linear equations.
- The paper closes the open t-step construction and convergence problem by deriving a subsidy-dependent threshold, indexability test, index formula, and geometric convergence result.
- Recent RMAB work also studies learning, regret, scalable computation, belief deduplication, factorization reuse, and vectorization.
3 Model and indexability
The model is a discounted, partially observable single-arm restless bandit whose state is represented by a belief over hidden states. Exact indexability is defined through a unique subsidy separating activation from passivity at every belief.
- The model uses hidden states {0,1,…,K−1}, transition matrix P, discount factor β∈(0,1), and ordered rewards 0=B0≤B1≤···≤BK−1≤1.
- A belief state is a row vector on the simplex; passive evolution follows ωP^k, while activation reveals the hidden state and resets belief to a transition row.
- The exact value is the infinite-horizon single-arm value under passivity subsidy m, and the active-passive gap determines the optimal action.
- The exact active set contains beliefs with positive gap, while the indifference boundary contains beliefs with zero gap.
- Exact indexability requires every belief to have a unique subsidy W(ω) such that activation is optimal below W(ω) and passivity above it.
4 t-step lookahead threshold policy and approximate Whittle index
The t-step policy compares finite-horizon active-passive advantages against a target belief, then uses induced first crossings and a regenerative linear system to compute an approximate index. At t=1 it reduces to Liu’s subsidy-independent threshold, whereas deeper lookahead can change the crossing structure with the subsidy.
- Finite-horizon threshold: Passive belief updates follow P^k(ω), and finite-horizon value iteration defines the t-step active-minus-passive advantage.
- Finite-horizon threshold: At t=1, the comparison reduces to xB⊤>ωB⊤, which is independent of m and recovers Liu’s linearized threshold.
- Threshold policy: The policy activates when the current advantage exceeds its value at the target belief ω and remains passive otherwise.
- First-crossing construction: First-crossing time records when passive belief evolution first crosses the threshold; for t>1, the crossing structure may change with m.
- First-crossing construction: The passive sojourn summaries record discounted subsidy accumulation and the discounted belief vector at first activation.
- Approximate index: Stacking reset-belief values yields a regenerative linear system with a closed-form solution whose inverse exists because Gt is substochastic and β<1.
5 Geometric convergence of the approximate Whittle index
Under exact Whittle indexability, the t-step approximate Whittle index converges geometrically to the exact index. The proof transfers finite-lookahead value and action-value gaps through convergent threshold-induced linear systems.
- At the exact Whittle subsidy m⋆, finite-lookahead value and action-value discrepancies are bounded through the performance difference argument.
- Exact indexability assumes a unique Whittle index and is used to establish convergence rather than to implement the algorithm.
- The t-step lookahead gap evaluates active-passive comparisons using continuation values under the t-step threshold policy πt.
- The finite-t threshold and its first-crossing linear system converge to the exact decision-boundary system, whose unique solution is m⋆ = W(ω).
- The algorithm defines approximate indices as admissible roots of the relaxed indifference gap and performs indexability verification without requiring indexability as an input.
- For t = 1, the indifference equation is globally closed-form in m; for t > 1, subsidy-dependent first-crossing structures require local solution on affine pieces.
6 Numerical experiments
Numerical experiments assess indexability, index accuracy, ranking stability, policy performance, and computational cost for the finite-lookahead approximation. Increasing lookahead improves accuracy and policy performance, while moderate depths provide a practical accuracy-cost tradeoff.
- Indexability: 2,715 tested three-state instances were numerically verified as indexable under the proposed criterion.
- Index convergence: P95 error decreases from 2.18 × 10^-2 at t = 1 to 8.93 × 10^-4 at t = 8, while maximum error decreases from 6.27 × 10^-2 to 2.79 × 10^-3.
- Ranking stability: At β = 0.9999, the one-step approximation reverses Arms 1 and 2, whereas t = 2 recovers the exact ordering 1 > 2 > 3.The ordering remains unchanged at t = 3 and t = 4.
- Policy performance: Finite-lookahead policies close most of the reward gap from myopic allocation to the optimal benchmark, with t = 2 and t = 5 nearly identical on this instance.The improvement from t = 1 to t = 2 is especially clear in later slots.
- Computational cost: Median runtime rises from 0.0509 seconds at t = 1 to 0.2009 seconds at t = 15, while P90 runtime remains close to the median.Moderate depths such as t = 5 or t = 8 offer a reasonable accuracy-cost tradeoff in this experiment.
7 Conclusion
The paper extends Liu’s one-step threshold to a subsidy-dependent t-step family, derives an indexability verification, and establishes geometric convergence to the exact Whittle index. Numerical results show broad indexability verification, improved accuracy, and near-optimal policy performance at moderate lookahead depths.
- The finite-t approximate Whittle index is derived through a first-crossing linear system and does not require indexability as an algorithmic input.
- The algorithm provides an indexability verification when multiple candidate subsidy solutions arise.
- Under original Whittle indexability, the finite-t approximate index converges geometrically to the exact Whittle index.
- All 2,715 tested three-state instances were numerically verified as indexable, while deeper lookahead improved accuracy and moderate depths remained close to the dynamic-programming benchmark.
A Notation
This section defines the belief-state model, subsidy-dependent active and passive sets, Whittle indifference quantities, and the notation for t-step threshold constructions.
- The belief space is the simplex over K hidden states, with passive belief update P1(ω)=ωP and transition rows denoted by p_i.
- For subsidy m, Δβ,m(ω) is the exact active-minus-passive value gap, defining passive, active, and indifference sets.
- The Whittle index W(ω), or m⋆, denotes the exact indifference subsidy at belief ω.
- The notation includes h-horizon action values, the t-lookahead action-value difference, first-crossing time, continuation value, relaxed indifference gap, and approximate index.
B Proofs for Lemma 1
The proofs establish finite-horizon approximation error through the discounted Bellman operator, whose contraction property controls value-function and action-value deviations.
- Starting from the zero function, iterating the contraction yields a geometrically shrinking finite-horizon value-function error.
- The Bellman operator has a unique fixed point and is a β-contraction under the sup norm.
- The active and passive action-value errors are compared separately before being combined through the triangle inequality.
- The immediate reward cancels when subtracting active and passive expressions, isolating discounted continuation-value error.
- The resulting t-step threshold can repair a one-step threshold loss while remaining close to the optimal policy in a finite-horizon comparison.
C Additional experiments
The additional-experiment implementation used CPU-only computation on a MacBook M4 Pro with 24GB RAM and no external cluster.
- All reported experiments ran on a MacBook M4 Pro with 24GB RAM using CPU only.No GPU or external cluster was used.
C.1 Additional small-scale experiments
Additional experiments show that deeper threshold-index policies outperform myopic allocation and remain close to the optimal policy.
- About ten percent: t = 2 and t = 5 threshold-index policies outperform myopic allocation while remaining close to optimal policy.
- Deeper threshold-index policies remain close to optimal policy and exceed the one-step threshold at the final horizon.