🤖 machine learning

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

This paper proposes a $t$ -step lookahead threshold policy that extends Liu's one-step linearization approach to approximate Whittle indices for partially observable restless bandits, achieving geometric convergence to the exact index while simultaneously verifying indexability and significantly reducing approximation errors compared to the baseline.

Original authors: Qizhen Jia, Keqin Liu

Published 2026-08-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Qizhen Jia, Keqin Liu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a manager trying to decide which of many machines to run at any given moment. Each machine is in a hidden state that changes over time, and the manager only sees a blurry picture of where each one stands. The goal is to keep the most productive machines running while letting the others rest, but because the manager cannot see the true condition of every machine, they must make guesses based on past observations. This is a classic puzzle in decision science known as the restless bandit problem. It appears everywhere from managing wireless networks to scheduling hospital equipment. The difficulty lies in the fact that the machines keep changing even when they are not being watched, and the manager must balance the immediate reward of running a machine against the long-term value of waiting to see if it improves. For decades, researchers have sought a simple rule, or a "priority list," that tells them exactly which machine to pick next without having to calculate every possible future scenario.

A powerful method for solving this puzzle is called the Whittle index. Think of it as a score assigned to each machine that represents the minimum payment a manager would need to accept to leave that machine idle. If a machine has a high score, it is worth running; if it has a low score, it is better to wait. In a perfect world where the manager can see every machine clearly, calculating this score is straightforward. However, in the real world where observations are incomplete, the math becomes incredibly difficult. The manager must track a continuous range of possibilities for every machine, turning the problem into an infinite maze with no clear exit. Previous attempts to solve this involved simplifying the maze by drawing a straight line to guess where the decision should be made. While this worked well enough for some cases, it ignored the long-term consequences of waiting, leading to decisions that were good for the next step but poor for the future.

In this work, researchers Qizhen Jia and Keqin Liu from Xi'an Jiaotong-Liverpool University have developed a way to look deeper into the future without getting lost in the complexity. They took the existing method, which only looked one step ahead, and extended it to look several steps into the future. Instead of just comparing the immediate reward of running a machine versus leaving it alone, their new approach simulates what would happen if the manager waited for two, three, or even more steps before making a decision. By doing this, they create a more accurate picture of the value of waiting. This allows them to draw a much sharper line that separates the machines worth running from those worth waiting on. The result is a new scoring system that adapts as the manager's uncertainty changes, tracking the true decision boundary far more closely than the old one-step method.

The researchers proved mathematically that as they increase the number of steps they look ahead, their calculated scores get closer and closer to the perfect, exact answer. They showed that the error shrinks rapidly, meaning that even a modest increase in how far they look into the future yields a significant improvement in accuracy. To test this, they ran thousands of simulations with machines that had three possible hidden states. In every single one of the 2,715 cases they tested, their new method successfully verified that a clear priority order existed. When they compared their scores to a highly accurate reference point, they found that the error dropped dramatically as they increased the look-ahead depth. At a depth of one step, the error was noticeable, but by the time they looked eight steps ahead, the error had shrunk to a tiny fraction of its original size.

Perhaps most impressively, the researchers found that they did not need to look very far ahead to get the right answer in terms of ranking. In a difficult test case where the machines were very similar and the future was highly valued, the old one-step method got the order wrong, suggesting the second-best machine should be run first. However, their new method, looking just two steps ahead, correctly identified the best machine and maintained the proper order. This suggests that while the exact numerical score might need a deeper look to be perfect, the crucial task of deciding which machine to pick first stabilizes very quickly. The method also proved efficient; while looking further ahead took slightly more computer time, the increase was gentle and predictable, making it practical for real-world use.

The study confirms that by looking just a little further into the future, managers can make much smarter decisions without needing to solve the impossible math of the infinite future. The new approach provides a reliable way to handle uncertainty, ensuring that resources are allocated to the right machines at the right time. It bridges the gap between simple, fast rules and complex, perfect planning, offering a tool that is both theoretically sound and practically useful for managing systems where the future is uncertain and the stakes are high.

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

Problem Statement
The paper addresses the computational challenge of determining Whittle indices for Partially Observable Restless Multi-Armed Bandits (PO-RMABs) with more than two hidden states ( $K > 2$ ). In fully observable settings, Whittle indices are derived from finite-state dynamic programming. However, under partial observability, the state space becomes a continuous belief vector on a simplex, rendering the value function an infinite-horizon belief-state problem without a closed-form solution.

Previous work by Liu [10] attempted to solve this by linearizing the unknown decision boundary between active and passive actions, resulting in a one-step ( $t=1$ ) threshold policy. While computationally efficient, this approach relies on a one-step active-passive comparison that ignores longer-horizon continuation values, leading to suboptimal approximations of the true decision boundary and the exact Whittle index.

Methodology
The authors propose a $t$ -step lookahead threshold policy framework that generalizes the linearized approach of Liu [10].

$t$ -Step Advantage Function: For a given subsidy $m$ and lookahead depth $t$ , the method defines an active-minus-passive advantage function, $r_{t,m}(\omega) = Q^A_{\beta,m,t}(\omega) - Q^P_{\beta,m,t}(\omega)$ , based on finite-horizon value iteration.
- At $t=1$ , this reduces to the linear threshold $r_{1,m}(\omega) = \omega B^\top - m$ , independent of $m$ .
- For $t > 1$ , the threshold becomes subsidy-dependent ( $m$ -dependent) because the advantage function incorporates future rewards over $t$ steps, allowing the threshold to track the exact decision boundary more closely.
First-Crossing Structure: The policy activates an arm at belief $x$ if $r_{t,m}(x) > r_{t,m}(\omega)$ , where $\omega$ is the threshold belief. The method calculates the "first-crossing time" $L_t(x, \omega; m)$ under passive belief updates until the threshold is crossed.
Linear System Construction: Using the first-crossing times, the authors construct a linear system to estimate the value function at reset beliefs. This yields a closed-form (or locally closed-form) expression for the approximate Whittle index $\hat{W}_t(\omega)$ by solving the relaxed indifference equation $\Phi_t(\omega, m) = 0$ .
Algorithm and Verification: The proposed algorithm (Algorithm 1) computes the index directly without requiring indexability as a pre-condition. If multiple subsidy solutions exist for a belief state, the algorithm performs a numerical verification by checking if the maximum pairwise difference between candidates is within a prescribed tolerance $\epsilon_{ind}$ .

Key Contributions

Generalization of Threshold Policies: The paper extends the one-step linear threshold to a $t$ -step family, where the threshold shifts with the subsidy $m$ for $t > 1$ , providing a tighter approximation of the unknown decision boundary.
Theoretical Convergence: Under the assumption of original Whittle indexability, the authors prove that the approximate index $\hat{W}_t(\omega)$ converges geometrically to the exact Whittle index $W(\omega)$ as $t \to \infty$ :
$|\hat{W}_t(\omega) - W(\omega)| = O(\beta^t)$
Crucially, the indexability assumption is used to guarantee convergence, not to implement the algorithm.
Indexability Verification: A practical numerical criterion is introduced to verify indexability for specific instances, handling cases where multiple candidate subsidies arise.

Experimental Results
The authors evaluated the method on 2,715 randomly generated three-state instances and specific high-discount scenarios:

Index Accuracy: The P95 error of the approximate index decreased significantly as $t$ increased, dropping from $2.18 \times 10^{-2}$ at $t=1$ to $8.93 \times 10^{-4}$ at $t=8$ .
Ranking Stability: In a three-arm instance with a high discount factor ( $\beta = 0.9999$ ), the one-step approximation ( $t=1$ ) failed to recover the correct arm ordering. However, a modest lookahead of $t=2$ successfully recovered the exact Whittle index ordering ( $1 > 2 > 3$ ).
Policy Performance: In a six-arm finite-horizon instance ( $T=6$ ), the $t=2$ and $t=5$ policies outperformed both the one-step baseline and the myopic policy, achieving rewards close to the optimal dynamic programming benchmark.
Computational Cost: Runtime increased mildly with $t$ (e.g., median time rising from 0.05s at $t=1$ to 0.20s at $t=15$ ), suggesting that moderate depths offer a favorable accuracy-cost tradeoff.

Significance and Claims
The paper claims to close the gap left by Liu [10] by constructing the subsidy-dependent $t$ -step threshold and establishing its geometric convergence to the exact index. The authors emphasize that their approach:

Does not require indexability as an input, making it applicable to problems where this property is unknown.
Provides a computable approximation of the unknown decision boundary in high-dimensional partially observable models.
Lays a theoretical foundation for future applications of Partial Conservation Law (PCL) methods to high-dimensional belief models by defining a tractable threshold structure.

The work demonstrates that even moderate lookahead depths ( $t=2$ to $t=8$ ) are sufficient to achieve high accuracy and correct ranking, offering a practical alternative to solving the full infinite-horizon belief-state POMDP.

More like this