Smooth Sequential Optimisation with Delayed Feedback

Abstract

Stochastic delays in feedback lead to unstable sequential learning using multi-armed bandits. Recently, empirical Bayesian shrinkage has been shown to improve reward estimation in bandit learning. Here, we propose a novel adaptation to shrinkage that estimates smoothed reward estimates from windowed cumulative inputs, to deal with incomplete knowledge from delayed feedback and non-stationary rewards. Using numerical simulations, we show that this adaptation retains the benefits of shrinkage, and improves the stability of reward estimation by more than 50%. Our proposal reduces variability in treatment allocations to the best arm by up to 3.8x, and improves statistical accuracy - with up to 8% improvement in true positive rates and 37% reduction in false positive rates. Together, these advantages enable control of the trade-off between speed and stability of adaptation, and facilitate human-in-the-loop sequential optimisation.

arXiv commentWorkshop on Bayesian causal inference for real world interactive systems, 27th SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2021)

References in corpus (8)

• Analysis of Thompson Sampling for the multi-armed bandit problem
• On Upper-Confidence Bound Policies for Non-Stationary Bandit Problems
• Batched bandit problems
• Bandits with Delayed, Aggregated Anonymous Feedback
• Best arm identification in multi-armed bandits with delayed feedback
• Nonstochastic Bandits with Composite Anonymous Feedback
• Linear Bandits with Stochastic Delayed Feedback
• Stochastic Bandits with Delayed Composite Anonymous Feedback