Restless bandits with switching costs: Linear programming relaxations, performance bounds and limited lookahead policies

Jerome Le Ny, Eric Feron

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Scopus citations

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 primaldual heuristic of Bertsimas and Niño-Mora [1] for the classical restless bandits problem is in fact equivalent to a one-step lookahead 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 lookahead 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. © 2006 IEEE.
Original languageEnglish (US)
Title of host publicationProceedings of the American Control Conference
Pages1587-1592
Number of pages6
StatePublished - Dec 1 2006
Externally publishedYes

Fingerprint

Dive into the research topics of 'Restless bandits with switching costs: Linear programming relaxations, performance bounds and limited lookahead policies'. Together they form a unique fingerprint.

Cite this