Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Some families of indexable restless bandit problems.
AU - Glazebrook, Kevin
AU - Kirkbride, C.
AU - Ruiz-Hernandez, D.
N1 - RAE_import_type : Journal article RAE_uoa_type : Statistics and Operational Research
PY - 2006/9/1
Y1 - 2006/9/1
N2 - 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.
AB - 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.
KW - Bandit problem
KW - dynamic programming
KW - Gittins index
KW - machine maintenance
KW - restless bandit
KW - stochastic scheduling
KW - switching cost
U2 - 10.1239/aap/1158684996
DO - 10.1239/aap/1158684996
M3 - Journal article
VL - 38
SP - 643
EP - 672
JO - Advances in Applied Probability
JF - Advances in Applied Probability
SN - 1475-6064
IS - 3
ER -