Restless bandits with imperfect binary feedback: PCL-indexability analysis and computation

José Niño-Mora

cs.LGMar 27, 2026

Restless bandits with imperfect binary feedback: PCL-indexability analysis and computation

Authors: José Niño-Mora

Organizations: Departamento de Estadística Universidad Carlos III de Madrid 28903 Getafe (Madrid), Spain

Abstract

We study restless bandits with binary latent states and imperfect binary feedback, motivated by opportunistic spectrum access with sensing errors. For the associated belief-state model, we develop a partial conservation laws (PCL)-based analytical and computational framework for establishing indexability and evaluating the Whittle index, building on a verification theorem for real-state discounted restless bandits. The framework analyzes the stochastic dynamics via an associated deterministic skeleton, renewal decompositions, and combinatorics on words. It yields tractable expressions for discounted reward and resource metrics in several threshold regimes, enabling full verification of the PCL-indexability conditions there. For the remaining regime, where a complete analytic verification is not achieved in this paper, we derive efficient numerical schemes for computing the relevant marginal metrics and the marginal productivity (MP) index, which equals the Whittle index when those conditions hold. Extensive computational experiments provide strong evidence that these conditions also hold in that regime across broad parameter ranges and without the stringent parameter restrictions imposed in prior work. The experiments further show that theMP index policy typically outperforms standard benchmark policies, often by a substantial margin.

Figures & tables

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 1: Pre-ACK reward and work metrics

\widetilde{F}(x,z)

and

\widetilde{G}(x,z)

vs.

z

for fixed belief

x

Figure 2: Reward and work metrics

F(x,z)

and

G(x,z)

vs.

z

for fixed belief

x

Figure 3: Marginal metrics

\tilde{f}(x,z)

and

\tilde{g}(x,z)

vs.

z

for fixed belief

x

Figure 4: Marginal metrics

f(x,z)

and

g(x,z)

vs.

z

for fixed belief

x

Figure 5: Marginal metrics

f(x,x)

and

g(x,x)

vs.

x

Figure 6: MP index

m(x)

vs.

x

Figure 7: MP index

m(x)

versus

x

for several values of

\beta

Figure 8: MP index

m(x)

versus

x

for several values of

\kappa

Figure 9: MP index

m(x)

versus

x

for several values of

\rho

Figure 10: MP index

m(x)

versus

\rho

for a fixed belief

x

Figure 11: MP index

m(x)

versus

x

for several values of

p_{01}

Figure 12: MP index

m(x)

versus

p_{01}

for a fixed belief

x

Explore similar work

From Relaxed Indexability to Exact Indexability: A $t$ -Step Approach for Partially Observable Restless Bandits
Aug 25, 2026Keqin Liu, Qizhen JiaMulti-Armed Bandits Sequential Decision Making
Restless Bandits with Individual Penalty Constraints: Near-Optimal Indices and Deep Reinforcement Learning
Apr 5, 2026Nida Zamir, I-Hong HouMulti-Armed Bandits Sequential Decision Making
Texas A&M University, College Station, Texas, USA
A single algorithm for both restless and rested rotting bandits
Apr 23, 2026Julien Seznec, Pierre Ménard, Alessandro Lazaric +1Multi-Armed Bandits Non-Stationary Bandits
SCOOL, Inria Lille · FAIR Paris · DeepMind Paris

Aug 25, 2026J/K move · Enter open · S save

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

Keqin Liu, Qizhen Jia

Multi-Armed Bandits Sequential Decision Making Partially Observable Markov Decision Processes

Open paper AskPDF arXiv

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,

|\widehat W_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\times10^{-2}

t=1

8.93\times10^{-4}

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

Abstract

Explore similar work

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

Restless Bandits with Individual Penalty Constraints: Near-Optimal Indices and Deep Reinforcement Learning

A single algorithm for both restless and rested rotting bandits

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