A Fast-Pivoting Algorithm for Whittle's Restless Bandit Index

Niño Mora, José

Publication:
A Fast-Pivoting Algorithm for Whittle's Restless Bandit Index

dc.affiliation.dpto	UC3M. Departamento de Estadística	es
dc.contributor.author	Niño Mora, José
dc.contributor.funder	Ministerio de Educación y Ciencia (España)	es
dc.date.accessioned	2021-07-06T07:40:07Z
dc.date.available	2021-07-06T07:40:07Z
dc.date.issued	2020-12
dc.description	This article belongs to the Special Issue Applied Probability	en
dc.description.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)n3+O(n2) 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.	en
dc.description.sponsorship	This research has been developed over a number of years, and has been funded by the Spanish Government under grants MEC MTM2004-02334 and PID2019-109196GB-I00/AEI/10.13039/501100011033. This research was also funded in part by the Comunidad de Madrid in the setting of the multi-year agreement with Universidad Carlos III de Madrid within the line of activity "Excelencia para el Profesorado Universitario", in the framework of the V Regional Plan of Scientific Research and Technological Innovation 2016-2020.	en
dc.format.extent	21
dc.identifier.bibliographicCitation	Niño-Mora, J. (2020). A Fast-Pivoting Algorithm for Whittle’s Restless Bandit Index. Mathematics, 8(12), 2226.	en
dc.identifier.doi	https://doi.org/10.3390/math8122226
dc.identifier.issn	2227-7390
dc.identifier.publicationfirstpage	2226
dc.identifier.publicationissue	12
dc.identifier.publicationtitle	Mathematics	en
dc.identifier.publicationvolume	8
dc.identifier.uri	https://hdl.handle.net/10016/33001
dc.identifier.uxxi	AR/0000026986
dc.language.iso	eng
dc.publisher	MDPI
dc.relation.projectID	Gobierno de España. PID2019-109196GB-I00	es
dc.relation.projectID	Gobierno de España. MTM2004-02334	es
dc.rights	© 2020 by the author.	en
dc.rights	Atribución 3.0 España	*
dc.rights.accessRights	open access	en
dc.rights.uri	http://creativecommons.org/licenses/by/3.0/es/	*
dc.subject.eciencia	Estadística	es
dc.subject.other	Restless bandits	en
dc.subject.other	Whittle index	en
dc.subject.other	Stochastic scheduling	en
dc.subject.other	Index policies	en
dc.subject.other	Indexability	en
dc.subject.other	Index algorithm	en
dc.subject.other	Markov decision processes	en
dc.title	A Fast-Pivoting Algorithm for Whittle's Restless Bandit Index	en
dc.type	research article	*
dc.type.hasVersion	VoR	*
dspace.entity.type	Publication