On learning Whittle index policy for restless bandits with scalable regret

Understand

Reinforcement learning is an attractive approach to learn good resource allocation and scheduling policies based on data when the system model is unknown.

• However, the cumulative regret of most RL algorithms scales as $\tilde O(\mathsf{S} \sqrt{\mathsf{A} T})$, where $\mathsf{S}$ is the size of the state space, $\mathsf{A}$ is the size of the action space, $T$ is the horizon, and the $\tilde{O}(\cdot)$ notation hides logarithmic terms.
• Due to the linear dependence on the size of the state space, these regret bounds are prohibitively large for resource allocation and scheduling problems.
• In this paper, we present a model-based RL algorithm for such problems which has scalable regret.