On the optimality of the Gittins index rule for multi-armed bandits with multiple plays

We investigate the general multi-armed bandit problem with multiple servers. We determine a condition on the reward processes sufficient to guarantee the optimality of the strategy that operates at each instant of time the projects with the highest Gittins indices. We call this strategy the Gittins index rule for multi-armed bandits with multiple plays, or briefly the Gittins index rule. We show by examples that: (i) the aforementioned sufficient condition is not necessary for the optimality of the Gittins index rule; and (ii) when the sufficient condition is relaxed the Gittins index rule is not necessarily optimal. Finally, we present an application of the general results to the multiserver scheduling of parallel queues without arrivals.

Authors and Affiliations

1. ERIM International, Inc., P.O. Box 134001, Ann Arbor, MI 48113-4001, USA (e-mail: pandelis@erim-int.com), , , , , , US

   Dimitrios G. Pandelis

2. Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, MI 48109-2122, USA (e-mail:teneket@eecs.umich.edu), , , , , , US

   Demosthenis Teneketzis

Manuscript received: March 1999/final version received: July 1999

Reprints and permissions