Publication: Characterization and computation of restless bandit marginal productivity indices
Loading...
Identifiers
Publication date
2007-05
Defense date
Authors
Advisors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Impact
Export
Abstract
The Whittle index [P. Whittle (1988). Restless bandits: Activity allocation in a changing world. J. Appl. Probab. 25A, 287-298] yields a practical scheduling rule for the versatile yet intractable
multi-armed restless bandit problem, involving the optimal dynamic priority allocation to multiple stochastic projects, modeled as restless bandits, i.e., binary-action (active/passive) (semi-)
Markov decision processes. A growing body of evidence shows that such a rule is nearly optimal in a wide variety of applications, which raises the need to efficiently compute the Whittle index and more general marginal productivity index (MPI) extensions in large-scale models. For such a purpose, this paper extends to restless bandits the parametric linear programming (LP) approach
deployed in [J. Niño-Mora. A (2/3)n^3 fast-pivoting algorithm for the Gittins index and optimal stopping of a Markov chain, INFORMS J. Comp., in press], which yielded a fast Gittins-index algorithm. Yet the extension is not straightforward, as the MPI is only defined for the limited range of socalled indexable bandits,
which motivates the quest for methods to establish indexability. This paper furnishes algorithmic and analytical tools to realize the potential of MPI policies in largescale applications, presenting the following contributions: (i) a complete algorithmic characterization of indexability, for which two block implementations are given; and
(ii) more importantly, new analytical conditions for indexability — termed LP-indexability — that leverage knowledge on the structure of
optimal policies in particular models, under which the MPI is computed faster by the adaptive-greedy algorithm previously introduced by the author under the more stringent PCL-indexability
conditions, for which a new fast-pivoting block implementation is given. The paper further reports on a computational study, measuring the runtime performance of the algorithms, and assessing by a
simulation study the high prevalence of indexability and PCL-indexability.
Description
Keywords
Dynamic programming, Semi-Markov, Finite state, Stochastic scheduling, Restless bandits, Priority-index policy, Indexability, Whittle index, Marginal productivity index, Parametric simplex, Block algorithms, Computational complexity