Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-15T15:15:45.625Z Has data issue: false hasContentIssue false

Some indexable families of restless bandit problems

Published online by Cambridge University Press:  01 July 2016

K. D. Glazebrook*
Affiliation:
Lancaster University
D. Ruiz-Hernandez*
Affiliation:
Universitat Pompeu Fabra
C. Kirkbride*
Affiliation:
Lancaster University
*
∗ Postal address: Department of Mathematics and Statistics, Lancaster University, Lancaster, LA1 4YF, UK. Email address: k.glazebrook@lancaster.ac.uk
∗∗ Postal address: Department of Economics and Business, Universitat Pompeu Fabra, E-08005 Barcelona, Spain.
∗∗∗ Postal address: Department of Management Science, Lancaster University, Lancaster, LA1 4YX, UK.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In 1988 Whittle introduced an important but intractable class of restless bandit problems which generalise the multiarmed bandit problems of Gittins by allowing state evolution for passive projects. Whittle's account deployed a Lagrangian relaxation of the optimisation problem to develop an index heuristic. Despite a developing body of evidence (both theoretical and empirical) which underscores the strong performance of Whittle's index policy, a continuing challenge to implementation is the need to establish that the competing projects all pass an indexability test. In this paper we employ Gittins' index theory to establish the indexability of (inter alia) general families of restless bandits which arise in problems of machine maintenance and stochastic scheduling problems with switching penalties. We also give formulae for the resulting Whittle indices. Numerical investigations testify to the outstandingly strong performance of the index heuristics concerned.

Information

Type
General Applied Probability
Copyright
Copyright © Applied Probability Trust 2006