Stochastic Bandits with Delay-Dependent Payoffs
  Motivated by recommendation problems in music streaming platforms, we propose
a nonstationary stochastic bandit model in which the expected reward of an arm
depends on the number of rounds that have passed since the arm was last pulled.
After proving that finding an optimal policy is NP-hard even when all model
parameters are known, we introduce a class of ranking policies provably
approximating, to within a constant factor, the expected reward of the optimal
policy. We show an algorithm whose regret with respect to the best ranking
policy is bounded by $\widetilde{\mathcal{O}}\big(\!\sqrt{kT}\big)$, where $k$
is the number of arms and $T$ is time. Our algorithm uses only
$\mathcal{O}\big(k\ln\ln T\big)$ switches, which helps when switching between
policies is costly. As constructing the class of learning policies requires
ordering the arms according to their expectations, we also bound the number of
pulls required to do so. Finally, we run experiments to compare our algorithm
against UCB on different problem instances.
