Restless bandits, partial conservation laws and indexability

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Niño-Mora, Joséca
• dc.contributor.other Universitat Pompeu Fabra. Departament d'Economia i Empresa
• dc.date.accessioned 2017-07-26T12:08:02Z
• dc.date.available 2017-07-26T12:08:02Z
• dc.date.issued 1999-12-01
• dc.date.modified 2017-07-23T02:05:02Z
• dc.description.abstract We show that if performance measures in a stochastic scheduling problem satisfy a set of so-called partial conservation laws (PCL), which extend previously studied generalized conservation laws (GCL), then the problem is solved optimally by a priority-index policy for an appropriate range of linear performance objectives, where the optimal indices are computed by a one-pass adaptive-greedy algorithm, based on Klimov's. We further apply this framework to investigate the indexability property of restless bandits introduced by Whittle, obtaining the following results: (1) we identify a class of restless bandits (PCL-indexable) which are indexable; membership in this class is tested through a single run of the adaptive-greedy algorithm, which also computes the Whittle indices when the test is positive; this provides a tractable sufficient condition for indexability; (2) we further indentify the class of GCL-indexable bandits, which includes classical bandits, having the property that they are indexable under any linear reward objective. The analysis is based on the so-called achievable region method, as the results follow from new linear programming formulations for the problems investigated.
• dc.format.mimetype application/pdfca
• dc.identifier https://econ-papers.upf.edu/ca/paper.php?id=435
• dc.identifier.citation Advances in Applied Probability, 33, 1, pp. 76-98, 2001
• dc.identifier.uri http://hdl.handle.net/10230/629
• dc.language.iso eng
• dc.relation.ispartofseries Economics and Business Working Papers Series; 435
• dc.rights L'accés als continguts d'aquest document queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.rights.uri http://creativecommons.org/licenses/by-nc-nd/3.0/es/
• dc.subject.keyword stochastic scheduling
• dc.subject.keyword markov decision chains
• dc.subject.keyword bandit problems
• dc.subject.keyword achievable region
• dc.subject.keyword Operations Management
• dc.title Restless bandits, partial conservation laws and indexabilityca
• dc.type info:eu-repo/semantics/workingPaper