Accession Number:

AD1004473

Title:

Restless Bandits with Switching Costs: Linear Programming Relaxations, Performance Bounds and Limited Lookahead Policies

Descriptive Note:

Conference Paper

Corporate Author:

Massachusetts Institute of Technology Cambridge United States

Personal Author(s):

• Ny,Jerome L.
• Feron,Eric

Report Date:

2006-06-16

Pagination or Media Count:

6.0

Abstract:

The multi-armed bandit problem and one of its most interesting extensions, the restless bandits problem, are frequently encountered in various stochastic control problems. We present a linear programming relaxation for the restless bandits problem with discounted rewards, where only one project can be activated at each period but with additional costs penalizing switching between projects. The relaxation can be efficiently computed and provides a bound on the achievable performance. We describe several heuristic policies in particular, we show that a policy adapted from the primal dual heuristic of Bertsimas and Nino-Mora 1 for the classical restless bandits problem is in fact equivalent to a one-step look ahead policy thus, the linear programming relaxation provides a means to compute an approximation of the cost-to-go. Moreover, the approximate cost-to-go is decomposable by project, and this allows the one-step look ahead policy to take the form of an index policy, which can be computed on-line very efficiently. We present numerical experiments, for which we assess the quality of the heuristics using the performance bound.

Descriptors:

• linear programming
• evolutionary algorithms

Subject Categories:

Distribution Statement:

APPROVED FOR PUBLIC RELEASE