Stochastic Bandits with Delay-Dependent Payoffs
This addresses recommendation systems in platforms like music streaming, offering a novel model with practical efficiency gains, though it is incremental in bandit theory.
The paper tackles the problem of nonstationary stochastic bandits where rewards depend on delay since last pull, motivated by music streaming recommendations, and introduces a ranking policy algorithm with regret bounded by Õ(√kT) and O(k ln ln T) switches.
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.