PCL-Indexability and Whittle Index for Restless Bandits with General Observation Models

Keqin Liu, Chengzhong Zhang

Abstract: In this paper, we consider a general observation model for restless multi-armed bandit problems. The operation of the player needs to be based on certain feedback mechanism that is error-prone due to resource constraints or environmental or intrinsic noises. By establishing a general probabilistic model for dynamics of feedback/observation, we formulate the problem as a restless bandit with a countable belief state space starting from an arbitrary initial belief (a priori information). We apply the achievable region method with partial conservation law (PCL) to the infinite-state problem and analyze its indexability and priority index (Whittle index). Finally, we propose an approximation process to transform the problem into which the AG algorithm of Niño-Mora and Bertsimas for finite-state problems can be applied to. Numerical experiments show that our algorithm has an excellent performance.

Introduction

The Restless Multi-Armed Bandit (RMAB) problem is a fundamental framework in stochastic scheduling, where a decision-maker selects $K$ out of $N$ arms to activate at each epoch to maximize long-term rewards. Unlike traditional bandits, "restless" arms can transition between states regardless of whether they are selected.

A major practical hurdle is the presence of noisy or partial observations, common in fields like opportunistic spectrum access and cybersecurity. In these scenarios, the true state of an arm is hidden, necessitating a Partially Observable Markov Decision Process (POMDP) approach. Here, the "state" is replaced by a belief state—a probability distribution over all possible true states. As these beliefs evolve, the state space becomes infinite and high-dimensional, leading to the "curse of dimensionality." While the Whittle Index is a powerful heuristic for RMABs, proving "indexability" (the existence of the index) and computing it for infinite belief states has remained a significant theoretical and computational challenge.

Methodology

The authors bridge the gap between theoretical indexability and practical computation by combining infinite-dimensional linear programming with the Achievable Region method. Their approach centers on generalizing the Partial Conservation Law (PCL) to countable state spaces.

Table 1: Main Notations used in the RMAB formulation.

The methodology consists of four primary components:

  1. Theoretical Extension of PCL: They prove a "Decomposition Law" (Theorem 1), establishing that performance measures in infinite spaces still satisfy the structural identities required for indexability.
  2. PCL-Indexability Proof: They demonstrate that if a problem satisfies PCL under certain regularity conditions (e.g., finitely many limit points for the index sequence), it is guaranteed to be Whittle indexable.
  3. $T$-step $\epsilon$-Approximation: To manage the infinite belief tree, they introduce a pruning method. If a new belief state is within an Euclidean distance $\epsilon$ of an existing one, or if it exceeds a depth $T$ from the initial belief, it is merged or truncated.
  4. Adaptive Greedy (AG) Algorithm: They adapt the Niño-Mora AG algorithm to work with this approximate, finite state space to numerically compute Whittle indices.

A key insight is that the geometric structure of the "achievable region"—the set of all possible performance outcomes—remains a manageable polyhedron even in infinite spaces, provided the transitions follow Markovian rules.

Experimental Evaluation

The proposed framework was evaluated using simulated environments reflecting real-world RMAB applications:

  • Opportunistic Spectrum Access (OSA): 2-state and 3-state channel models where sensing is error-prone.
  • Cybersecurity Monitoring: A 4-state model where an administrator monitors network segments (attacked, malfunctional, overloaded, normal).
  • Tiny Benchmarks: Small 2-state, 4-arm instances used to compare against exact dynamic programming.

Key Results

  • Performance Gains: In simulations with 30 to 50 arms, the Whittle index policy consistently outperformed myopic policies by 4% to 13%.
  • Scalability: The Whittle index computation scales linearly with the number of arms $N$, offering a significant advantage over "Rollout" policies that scale exponentially.
  • Near-Optimality: On small-scale instances, the Whittle index policy recovered the optimal trajectory within 0.01% to 0.24%.
  • Robustness: The algorithm maintained its performance edge across various observation error structures, including symmetric and asymmetric noise matrices.

Conclusion

This research extends RMAB theory to scenarios with limited and noisy observations by generalizing PCL to infinite belief state spaces. The results suggest that while the theoretical belief space is infinite, the effective belief space often stabilizes or clusters, justifying the use of Euclidean $\epsilon$-approximations. Future work may explore broader "feasible set families" or apply "fluid analysis" to high-dimensional belief spaces to further enhance computational speed as $N \to \infty$.

Summary updated

Abstract

In this paper, we consider a general observation model for restless multi-armed bandit problems. The operation of the player needs to be based on certain feedback mechanism that is error-prone due to resource constraints or environmental or intrinsic noises. By establishing a general probabilistic model for dynamics of feedback/observation, we formulate the problem as a restless bandit with a countable belief state space starting from an arbitrary initial belief (a priori information). We apply the achievable region method with partial conservation law (PCL) to the infinite-state problem and analyze its indexability and priority index (Whittle index). Finally, we propose an approximation process to transform the problem into which the AG algorithm of Ni\~no-Mora and Bertsimas for finite-state problems can be applied to. Numerical experiments show that our algorithm has an excellent performance.
BibTeX
@misc{liu2023pcl,
  author = {Keqin Liu and Chengzhong Zhang},
  title = {{PCL-Indexability and Whittle Index for Restless Bandits with General Observation Models}},
  year = {2023},
  eprint = {2307.03034},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2307.03034},
}
Figure