Restless bandits, linear programming relaxations, and a primal-dual index heuristic
成果类型：
Article
署名作者：
Bertsimas, D; Niño-Mora, J
署名单位：
Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Pompeu Fabra University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.48.1.80.12444
发表日期：
2000
页码：
80-90
关键词：
摘要：
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.