Characterization and computation of restless bandit marginal productivity indices

dc.affiliation.dptoUC3M. Departamento de Estadísticaes
dc.contributor.authorNiño Mora, José
dc.contributor.editorUniversidad Carlos III de Madrid. Departamento de Estadísticaen
dc.description.abstractThe Whittle index [P. Whittle (1988). Restless bandits: Activity allocation in a changing world. J. Appl. Probab. 25A, 287-298] yields a practical scheduling rule for the versatile yet intractable multi-armed restless bandit problem, involving the optimal dynamic priority allocation to multiple stochastic projects, modeled as restless bandits, i.e., binary-action (active/passive) (semi-) Markov decision processes. A growing body of evidence shows that such a rule is nearly optimal in a wide variety of applications, which raises the need to efficiently compute the Whittle index and more general marginal productivity index (MPI) extensions in large-scale models. For such a purpose, this paper extends to restless bandits the parametric linear programming (LP) approach deployed in [J. Niño-Mora. A (2/3)n^3 fast-pivoting algorithm for the Gittins index and optimal stopping of a Markov chain, INFORMS J. Comp., in press], which yielded a fast Gittins-index algorithm. Yet the extension is not straightforward, as the MPI is only defined for the limited range of socalled indexable bandits, which motivates the quest for methods to establish indexability. This paper furnishes algorithmic and analytical tools to realize the potential of MPI policies in largescale applications, presenting the following contributions: (i) a complete algorithmic characterization of indexability, for which two block implementations are given; and (ii) more importantly, new analytical conditions for indexability — termed LP-indexability — that leverage knowledge on the structure of optimal policies in particular models, under which the MPI is computed faster by the adaptive-greedy algorithm previously introduced by the author under the more stringent PCL-indexability conditions, for which a new fast-pivoting block implementation is given. The paper further reports on a computational study, measuring the runtime performance of the algorithms, and assessing by a simulation study the high prevalence of indexability and PCL-indexability.en
dc.format.extent308088 bytes
dc.relation.ispartofseriesUC3M Working papers. Statistics and Econometricsen
dc.rightsAtribución-NoComercial-SinDerivadas 3.0 España
dc.rights.accessRightsopen access
dc.subject.otherDynamic programmingen
dc.subject.otherFinite stateen
dc.subject.otherStochastic schedulingen
dc.subject.otherRestless banditsen
dc.subject.otherPriority-index policyen
dc.subject.otherWhittle indexen
dc.subject.otherMarginal productivity indexen
dc.subject.otherParametric simplexen
dc.subject.otherBlock algorithmsen
dc.subject.otherComputational complexityen
dc.titleCharacterization and computation of restless bandit marginal productivity indicesen
dc.typeworking paper*
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
300.87 KB
Adobe Portable Document Format