Dynamic Control of Birth-and-Death Restless Bandits: Application to Resource-Allocation Problems

Abstract

We develop a unifying framework to obtain efficient index policies for restless multi-armed bandit problems with birth-and-death state evolution. This is a broad class of stochastic resource allocation problems whose objective is to determine efficient policies to share resources among competing projects. In a seminal work, Whittle developed a methodology to derive well-performing Whittle’s index policies that are obtained by solving a relaxed version of the original problem. Our first main contribution is the derivation of a closed-form expression for Whittle’s index as a function of the steady-state probabilities. In some particular cases, qualitative insights can be obtained from its expression; nevertheless, it requires several technical conditions to be verified. We, therefore, formulate a fluid version of the relaxed optimization problem, and in our second main contribution, we develop a fluid index policy. The latter does provide qualitative insights and it is equivalent to Whittle’s index policy in the light-traffic regime. The applicability of our approach is illustrated by two important problems: optimal class selection and optimal load balancing. Allowing state-dependent capacities, we can model important phenomena, e.g., power-aware server-farms and opportunistic scheduling in wireless systems. Whittle’s index and our fluid index policy show remarkably good performance in numerical simulations.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 37 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.