Stochastic and fluid index policies for resource allocation problems

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. It can be efficiently calculated, however, it requires several technical conditions to be verified, and in addition, it does not provide qualitative insights into Whittle´s index. 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 is close to Whittle´s index. 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. Numerical simulations show that Whittle´s index and our fluid index policy are both nearly optimal.