Characterization and computation of restless bandit marginal productivity indices

e-Archivo Repository

Show simple item record Niño Mora, José
dc.contributor.editor Universidad Carlos III de Madrid. Departamento de Estadística 2007-05-14T08:17:58Z 2007-05-14T08:17:58Z 2007-05
dc.description.abstract The 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.
dc.format.extent 308088 bytes
dc.format.mimetype application/pdf
dc.language.iso eng
dc.relation.ispartofseries UC3M Working papers. Statistics and Econometrics
dc.relation.ispartofseries 07-11
dc.rights Atribución-NoComercial-SinDerivadas 3.0 España
dc.subject.other Dynamic programming
dc.subject.other Semi-Markov
dc.subject.other Finite state
dc.subject.other Stochastic scheduling
dc.subject.other Restless bandits
dc.subject.other Priority-index policy
dc.subject.other Indexability
dc.subject.other Whittle index
dc.subject.other Marginal productivity index
dc.subject.other Parametric simplex
dc.subject.other Block algorithms
dc.subject.other Computational complexity
dc.title Characterization and computation of restless bandit marginal productivity indices
dc.type workingPaper
dc.subject.eciencia Estadística
dc.rights.accessRights openAccess
dc.identifier.repec ws074311
dc.affiliation.dpto UC3M. Departamento de Estadística
 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