Continuous-time multi-armed bandits under random intervention times

Abstract

This paper examines multi-armed bandits with $J$ independent arms in which actions are taken at random discrete times. When an arm is operated, it must remain active for a renewal inter-arrival time. For arms evolving as a Lévy process, we provide an explicit characterization of the Gittins index, known to yield an optimal strategy. Furthermore, when the inter-arrival times are exponential and the arms evolve as a spectrally negative Lévy process, a reflected spectrally negative Lévy process, or a diffusion process, the Gittins index is explicitly characterized in terms of the scale function or diffusion characteristics, respectively. Convergence analysis and numerical experiments are performed to support the theoretical results.

arXiv comment31 pages, 1 figure