Distilled Thompson Sampling: Practical and Efficient Thompson Sampling via Imitation Learning

Abstract

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.

References in corpus (17)

• Weight Uncertainty in Neural Networks
• Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design
• Analysis of Thompson Sampling for the multi-armed bandit problem
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Stochastic Gradient Hamiltonian Monte Carlo
• Unbiased Offline Evaluation of Contextual-bandit-based News Article Recommendation Algorithms
• Further Optimal Regret Bounds for Thompson Sampling
• Kernel Interpolation for Scalable Structured Gaussian Processes (KISS-GP)
• A Simple Baseline for Bayesian Uncertainty in Deep Learning
• An Efficient Bandit Algorithm for Realtime Multivariate Optimization
• Horizon: Facebook's Open Source Applied Reinforcement Learning Platform
• Thoughts on Massively Scalable Gaussian Processes
• Ensemble Sampling
• Real-world Video Adaptation with Reinforcement Learning
• Optimality of Thompson Sampling for Gaussian Bandits Depends on Priors
• Thompson sampling with the online bootstrap
• Online Learning to Estimate Warfarin Dose with Contextual Linear Bandits

Cited by in corpus (1)

• Parallel Bayesian Optimization of Multiple Noisy Objectives with Expected Hypervolume Improvement