A fast-pivoting algorithm for Whittle's restless bandit index

Abstract

The Whittle index for restless bandits (two-action semi-Markov decision processes) provides an intuitively appealing optimal policy for controlling a single generic project that can be active (engaged) or passive (rested) at each decision epoch, and which can change state while passive. It further provides a practical heuristic priority-index policy for the computationally intractable multi-armed restless bandit problem, which has been widely applied over the last three decades in multifarious settings, yet mostly restricted to project models with a one-dimensional state. This is due in part to the difficulty of establishing indexability (existence of the index) and of computing the index for projects with large state spaces. This paper draws on the author's prior results on sufficient indexability conditions and an adaptive-greedy algorithmic scheme for restless bandits to obtain a new fast-pivoting algorithm that computes the $n$ Whittle index values of an $n$-state restless bandit by performing, after an initialization stage, $n$ steps that entail $(2/3)n^3+O(n^2)$ arithmetic operations. This algorithm also draws on the parametric simplex method, and is based on elucidating the pattern of parametric simplex tableaux, which allows to exploit special structure to substantially simplify and reduce the complexity of simplex pivoting steps. A numerical study demonstrates substantial runtime speed-ups versus alternative algorithms.

23 pages

References in corpus (10)

• 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
• A $(2/3)n^3$ fast-pivoting algorithm for the Gittins index and optimal stopping of a Markov chain
• A faster index algorithm and a computational study for bandits with switching costs
• Resource allocation and routing in parallel multi-server queues with abandonments for cloud profit maximization
• A Verification Theorem for Threshold-Indexability of Real-State Discounted Restless Bandits
• Admission and routing of soft real-time jobs to multiclusters: Design and comparison of index policies
• Towards minimum loss job routing to parallel heterogeneous multiserver queues via index policies
• Optimal Policies for Observing Time Series and Related Restless Bandit Problems

Cited by in corpus (4)

• Markovian restless bandits and index policies: A review
• LP-based policies for restless bandits: necessary and sufficient conditions for (exponentially fast) asymptotic optimality
• Testing Indexability and Computing Whittle and Gittins Index in Subcubic Time
• Multi-gear bandits, partial conservation laws, and indexability