The Gittins index is optimal for dynamic allocation with conditionally independent filtrations

Abstract The dynamic allocation problem, also known as the ‘multi-armed bandit’ problem, simulates a situation in which an agent is faced with a tradeoff between actions that yield an immediate reward and actions whose benefits can only be perceived in the future. In this paper, we see that the non-Markovian, discrete-time problem can be solved by following a Gittins index strategy, without the assumption that the rewards processes are independent. Instead, we require the underlying multi-parameter filtration to satisfy a conditional independence property. Three representations of the maximal attainable value are provided under an optimal strategy. Furthermore, we discuss the relationship between index-type strategies and the ‘synchronization’ paradigm from operations research.