  Restless Multi-Armed Bandits (RMABs) have been popularly used to model
limited resource allocation problems. Recently, these have been employed for
health monitoring and intervention planning problems. However, the existing
approaches fail to account for the arrival of new patients and the departure of
enrolled patients from a treatment program. To address this challenge, we
formulate a streaming bandit (S-RMAB) framework, a generalization of RMABs
where heterogeneous arms arrive and leave under possibly random streams. We
propose a new and scalable approach to computing index-based solutions. We
start by proving that index values decrease for short residual lifetimes, a
phenomenon that we call index decay. We then provide algorithms designed to
capture index decay without having to solve the costly finite horizon problem,
thereby lowering the computational complexity compared to existing methods.We
evaluate our approach via simulations run on real-world data obtained from a
tuberculosis intervention planning task as well as multiple other synthetic
domains. Our algorithms achieve an over 150x speed-up over existing methods in
these tasks without loss in performance. These findings are robust across
multiple domains.
