Distilled Thompson Sampling: Practical and Efficient Thompson Sampling via Imitation Learning
This work addresses the practical deployment challenges of Thompson Sampling for online platforms, particularly for Meta's video upload systems, by reducing latency and simplifying implementation.
The authors propose a novel imitation-learning-based algorithm to distill a Thompson Sampling (TS) policy into an explicit policy representation. This approach allows for fast decision-making and easy deployment, achieving performance comparable to batch TS while reducing decision-time latency by more than an order of magnitude.
Thompson sampling (TS) has emerged as a robust technique for contextual bandit problems. However, TS requires posterior inference and optimization for action generation, prohibiting its use in many online platforms where latency and ease of deployment are of concern. We operationalize TS by proposing a novel imitation-learning-based algorithm that distills a TS policy into an explicit policy representation, allowing fast decision-making and easy deployment in mobile and server-based environments. Using batched data collected under the imitation policy, our algorithm iteratively performs offline updates to the TS policy, and learns a new explicit policy representation to imitate it. Empirically, our imitation policy achieves performance comparable to batch TS while allowing more than an order of magnitude reduction in decision-time latency. Buoyed by low latency and simplicity of implementation, our algorithm has been successfully deployed in multiple video upload systems for Meta. Using a randomized controlled trial, we show our algorithm resulted in significant improvements in video quality and watch time.