A Verification Theorem for Threshold-Indexability of Real-State Discounted Restless Bandits

Abstract

The Whittle index, which characterizes optimal policies for controlling certain single restless bandit projects (a Markov decision process with two actions: active and passive) is the basis for a widely used heuristic index policy for the intractable restless multiarmed bandit problem. Yet two roadblocks need to be overcome to apply such a policy: the individual projects in the model at hand must be shown to be indexable, so that they possess a Whittle index; and the index must be evaluated. Such roadblocks can be especially vexing when project state spaces are real intervals, as in recent sensor scheduling applications. This paper presents sufficient conditions for indexability (relative to a generalized Whittle index) of general real-state discrete-time restless bandits under the discounted criterion, which are not based on elucidating properties of the optimal value function and do not require proving beforehand optimality of threshold policies as in prevailing approaches. The main contribution is a verification theorem establishing that, if project performance metrics under threshold policies and an explicitly defined marginal productivity (MP) index satisfy three conditions, then the project is indexable with its generalized Whittle index being given by the MP index, and threshold policies are optimal for dynamic project control.

This replacement to arXiv:1512.04403 is the author accepted manuscript of this paper, which is already published

References in corpus (5)

• Dynamic priority allocation via restless bandit marginal productivity indices
• Dynamic allocation indices for restless projects and queueing admission control: a polyhedral approach
• Asymptotically optimal priority policies for indexable and nonindexable restless bandits
• Resource allocation and routing in parallel multi-server queues with abandonments for cloud profit maximization
• Admission and routing of soft real-time jobs to multiclusters: Design and comparison of index policies

Cited by in corpus (6)

• Markovian restless bandits and index policies: A review
• A fast-pivoting algorithm for Whittle's restless bandit index
• Tabular and Deep Learning for the Whittle Index
• Planning to Fairly Allocate: Probabilistic Fairness in the Restless Bandit Setting
• Multi-gear bandits, partial conservation laws, and indexability
• Age of information cost minimization with no buffers, random arrivals and unreliable channels: A PCL-indexability analysis