Restless bandits: activity allocation in a changing world

TLDR

A population of \(n\) projects evolves over time whether active or idle, following different dynamics. The study aims to select projects over time to maximize expected reward rate while limiting the expected number of active projects. An index derived from the Lagrange multiplier—reducing to the Gittins index when idle projects are static—is computed for specific projects. When \(m\) and \(n\) are large with a constant ratio, operating the \(m\) projects with the highest current index is conjectured to be nearly optimal.

Abstract

We consider a population of n projects which in general continue to evolve whether in operation or not (although by different rules). It is desired to choose the projects in operation at each instant of time so as to maximise the expected rate of reward, under a constraint upon the expected number of projects in operation. The Lagrange multiplier associated with this constraint defines an index which reduces to the Gittins index when projects not being operated are static. If one is constrained to operate m projects exactly then arguments are advanced to support the conjecture that, for m and n large in constant ratio, the policy of operating the m projects of largest current index is nearly optimal. The index is evaluated for some particular projects.