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

e-Archivo Repository

Show simple item record

dc.contributor.author Niño Mora, José
dc.date.accessioned 2021-07-06T07:40:07Z
dc.date.available 2021-07-06T07:40:07Z
dc.date.issued 2020-12
dc.identifier.bibliographicCitation Niño-Mora, J. (2020). A Fast-Pivoting Algorithm for Whittle’s Restless Bandit Index. Mathematics, 8(12), 2226.
dc.identifier.issn 2227-7390
dc.identifier.uri http://hdl.handle.net/10016/33001
dc.description This article belongs to the Special Issue Applied Probability
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.
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.
dc.format.extent 21
dc.language.iso eng
dc.publisher MDPI
dc.rights © 2020 by the author.
dc.rights Atribución 3.0 España
dc.rights.uri http://creativecommons.org/licenses/by/3.0/es/
dc.subject.other Restless bandits
dc.subject.other Whittle index
dc.subject.other Stochastic scheduling
dc.subject.other Index policies
dc.subject.other Indexability
dc.subject.other Index algorithm
dc.subject.other Markov decision processes
dc.title A Fast-Pivoting Algorithm for Whittle's Restless Bandit Index
dc.type article
dc.subject.eciencia Estadística
dc.identifier.doi https://doi.org/10.3390/math8122226
dc.rights.accessRights openAccess
dc.relation.projectID Gobierno de España. PID2019-109196GB-I00
dc.relation.projectID Gobierno de España. MTM2004-02334
dc.type.version publishedVersion
dc.identifier.publicationfirstpage 2226
dc.identifier.publicationissue 12
dc.identifier.publicationtitle Mathematics
dc.identifier.publicationvolume 8
dc.identifier.uxxi AR/0000026986
dc.contributor.funder Ministerio de Educación y Ciencia (España)
 Find Full text

Files in this item

*Click on file's image for preview. (Embargoed files's preview is not supported)

The following license files are associated with this item:

This item appears in the following Collection(s)

Show simple item record