Thompson Sampling with Unrestricted Delays
This addresses the challenge of delayed feedback in online learning for applications like recommendation systems, though it is incremental as it extends existing Thompson Sampling analysis to delayed cases.
The paper tackled the stochastic multi-armed bandit problem with delayed feedback by analyzing Thompson Sampling under arbitrary delay distributions, establishing the first regret bounds for such settings and showing in simulations that it outperforms alternative methods.
We investigate properties of Thompson Sampling in the stochastic multi-armed bandit problem with delayed feedback. In a setting with i.i.d delays, we establish to our knowledge the first regret bounds for Thompson Sampling with arbitrary delay distributions, including ones with unbounded expectation. Our bounds are qualitatively comparable to the best available bounds derived via ad-hoc algorithms, and only depend on delays via selected quantiles of the delay distributions. Furthermore, in extensive simulation experiments, we find that Thompson Sampling outperforms a number of alternative proposals, including methods specifically designed for settings with delayed feedback.