Restless bandits, partial conservation laws and indexability

We show that if performance measures in a general stochastic scheduling pro blem satisfy partial conservation laws (PCL), which extend the generalized conservation laws (GCL) introduced by Bertsimas and Nino-Mora(1996), then t he problem is solved optimally by a priority-index policy under a range of admissible linear performance objectives, with both this range and the opti mal indices being determined by a one-pass adaptive-greedy algorithm that e xtends Klimov's: we call such scheduling problems PCL-indexable. We further apply the PCL framework to investigate the indexability property of restle ss bandits (two-action finite-state Markov decision chains) introduced by W hittle, obtaining the following results: (i) we present conditions on model parameters under which a single restless bandit is PCL-indexable, and henc e indexable: membership of the class of PCL-indexable bandits is tested thr ough a single run of the adaptive-greedy algorithm, which further computes the Whittle indices when the test is positive: this provides a tractable su fficient condition for indexability: (ii) we further introduce the subclass of GCL-indexable bandits (including classical bandits), which are indexabl e under arbitrary linear rewards. Our analysis is based on the achievable r egion approach to stochastic optimization, as the results follow from deriv ing and exploiting a new linear programming reformulation for single restle ss bandits.