Paper #435

Títol:

Restless bandits, partial conservation laws and indexability

Autor:

José Niño-Mora

Data:

Desembre 1999

Resum:

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.

Paraules clau:

Stochastic scheduling, Markov decision chains, bandit problems, achievable region

Codis JEL:

C60, C61

Àrea de Recerca:

Gestió de la Producció i de les Operacions

Publicat a:

Advances in Applied Probability, 33, 1, pp. 76-98, 2001

Descarregar el paper en format PDF