License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-644
URL: http://drops.dagstuhl.de/opus/volltexte/2005/64/
Niño-Mora, José

Marginal productivity index policies for scheduling restless bandits with switching penalties

pdf-format:
Dokument 1.pdf (181 KB)

Abstract

We address the problem of designing a tractable, well-grounded policy for the dynamic allocation of effort to a collection of restless bandit projects, i.e. binary-action (active/passive) Markov decision processes, in which sequence-independent switching penalties (costs or delays) are incurred when switching from one project to another. We deploy the framework of partial conservation laws, introduced by Niño-Mora (2001, 2002), to establish the existence of and calculate a marginal productivity index (MPI), under certain conditions. The MPI, which extends earlier indices proposed by Gittins (1979) and Whittle (1988), yields a corresponding MPI policy, which prescribes to dynamically engage the project with larger index.

BibTeX - Entry

@InProceedings{niomora:DSP:2005:64,
  author =	{Jos{\'e} Niño-Mora},
  title =	{Marginal productivity index policies for scheduling restless bandits with switching penalties},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  year =	{2005},
  editor =	{Susanne Albers and Rolf H. M{\"o}hring and Georg Ch. Pflug and R{\"u}diger Schultz},
  number =	{05031},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2005/64},
  annote =	{Keywords: stochastic scheduling , restless bandits , index policies , switching penalties}
}

Keywords: stochastic scheduling , restless bandits , index policies , switching penalties
Seminar: 05031 - Algorithms for Optimization with Incomplete Information
Issue date: 2005
Date of publication: 30.05.2005

DROPS-Home | Fulltext Search | Imprint Published by LZI