Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-17T10:42:41.473Z Has data issue: false hasContentIssue false

On the asymptotic optimality of greedy index heuristics for multi-action restless bandits

Published online by Cambridge University Press:  21 March 2016

D. J. Hodge*
Affiliation:
The University of Nottingham
K. D. Glazebrook*
Affiliation:
Lancaster University
*
∗ Postal address: School of Mathematical Sciences, University Park, The University of Nottingham, Nottingham NG7 2RD, UK. Email address: david.hodge@nottingham.ac.uk
∗∗ Postal address: Lancaster University Management School, Bailrigg, 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.

The class of restless bandits as proposed by Whittle (1988) have long been known to be intractable. This paper presents an optimality result which extends that of Weber and Weiss (1990) for restless bandits to a more general setting in which individual bandits have multiple levels of activation but are subject to an overall resource constraint. The contribution is motivated by the recent works of Glazebrook et al. (2011a), (2011b) who discussed the performance of index heuristics for resource allocation in such systems. Hitherto, index heuristics have been shown, under a condition of full indexability, to be optimal for a natural Lagrangian relaxation of such problems in which a resource is purchased rather than constrained. We find that under key assumptions about the nature of solutions to a deterministic differential equation that the index heuristics above are asymptotically optimal in a sense described by Whittle. We then demonstrate that these assumptions always hold for three-state bandits.

Information

Type
General Applied Probability
Copyright
Copyright © Applied Probability Trust 2015