Paper #301
- Title:
- Restless bandits, linear programming relaxations and a primal-dual index heuristic
- Authors:
- Dimitris Bertsimas and José Niño-Mora
- Date:
- August 1994 (Revised: October 1997)
- Abstract:
- We develop a mathematical programming approach for the classical PSPACE - hard restless bandit problem in stochastic optimization. We introduce a hierarchy of n (where n is the number of bandits) increasingly stronger linear programming relaxations, the last of which is exact and corresponds to the (exponential size) formulation of the problem as a Markov decision chain, while the other relaxations provide bounds and are efficiently computed. We also propose a priority-index heuristic scheduling policy from the solution to the first-order relaxation, where the indices are defined in terms of optimal dual variables. In this way we propose a policy and a suboptimality guarantee. We report results of computational experiments that suggest that the proposed heuristic policy is nearly optimal. Moreover, the second-order relaxation is found to provide strong bounds on the optimal value.
- Keywords:
- Stochastic scheduling, bandit problems, resource allocation, dynamic programming
- JEL codes:
- C60, C61
- Area of Research:
- Microeconomics
- Published in:
- Operations Research, 48, 1, (2000), pp. 80-90
Download the paper in PDF format