  We study the recovering bandits problem, a variant of the stochastic
multi-armed bandit problem where the expected reward of each arm varies
according to some unknown function of the time since the arm was last played.
While being a natural extension of the classical bandit problem that arises in
many real-world settings, this variation is accompanied by significant
difficulties. In particular, methods need to plan ahead and estimate many more
quantities than in the classical bandit setting. In this work, we explore the
use of Gaussian processes to tackle the estimation and planing problem. We also
discuss different regret definitions that let us quantify the performance of
the methods. To improve computational efficiency of the methods, we provide an
optimistic planning approximation. We complement these discussions with regret
bounds and empirical studies.
