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

Overview

• Thompson sampling (TS) is a robust technique for contextual bandit problems, but requires complex posterior inference and optimization, making it difficult to deploy in real-world systems.
• The researchers propose a novel imitation-learning-based algorithm that distills a TS policy into an explicit policy representation, enabling fast decision-making and easy deployment.
• The algorithm learns a new explicit policy by iteratively updating and imitating the TS policy using batched data.
• The imitation policy achieves comparable performance to batch TS while reducing decision-time latency by over an order of magnitude.
• The algorithm has been successfully deployed in multiple video upload systems at Meta, resulting in significant improvements in video quality and watch time.

Plain English Explanation

The paper describes a new way to use Thompson sampling, a powerful technique for making decisions in contextual bandit problems. Thompson sampling is good at finding the best actions to take, but it requires complex mathematical calculations that can slow down decision-making.

To make Thompson sampling easier to use, the researchers developed a new algorithm that takes the complicated Thompson sampling policy and distills it into a simpler, explicit policy. This explicit policy can make decisions much faster, without needing to do all the complex math. The algorithm does this by repeatedly learning from batches of data collected under the imitation policy, gradually improving the imitation to better match the original Thompson sampling policy.

The result is a decision-making system that performs about as well as the original Thompson sampling, but runs over 10 times faster. This allows the algorithm to be easily deployed in real-world systems like video upload platforms, where fast response times are crucial.

The researchers tested their algorithm at Meta (the company that owns Facebook) and found that it significantly improved video quality and watch time, showing that it can have a real-world impact. The combination of strong performance and fast, simple deployment makes this a promising approach for applying advanced decision-making techniques in practical applications.

Technical Explanation

The key technical innovation in this paper is the development of an imitation learning-based algorithm that distills a Thompson sampling (TS) policy into an explicit policy representation. This allows for fast decision-making and easy deployment in real-world systems.

The core of the approach is an iterative process of collecting batched data under the imitation policy, and then using that data to update the TS policy and learn a new imitation policy that better matches it. This cycle continues, with the imitation policy gradually improving to closely mimic the TS policy.

Empirically, the researchers show that the final imitation policy achieves performance comparable to batch TS, while providing over an order of magnitude reduction in decision-time latency. This enables the algorithm to be successfully deployed in video upload systems at Meta, where low latency and ease of implementation are critical.

Through a randomized controlled trial, the researchers demonstrate that the deployed system resulted in significant improvements in video quality and watch time, highlighting the real-world impact of their approach.

Critical Analysis

The researchers acknowledge several limitations and areas for future work. First, the imitation learning approach relies on being able to collect high-quality batched data under the imitation policy, which may be challenging in some real-world settings. Additionally, the iterative updates to the TS policy and imitation policy could potentially lead to instability or divergence, which the paper does not fully explore.

Another potential issue is that the researchers do not provide a theoretical analysis of the convergence or regret bounds of their algorithm, instead relying on empirical performance. Providing such theoretical guarantees could strengthen the foundations of the approach.

Furthermore, the paper focuses on the deployment in video upload systems at Meta, but it is unclear how well the algorithm would generalize to other types of contextual bandit problems or deployment environments. Evaluating the algorithm's performance in a wider range of scenarios could help assess its broader applicability.

Despite these limitations, the paper presents a novel and practical solution to the challenge of deploying Thompson sampling in real-world systems. The significant performance improvements and successful deployment at Meta suggest that this approach could have a meaningful impact in the field of contextual bandits and decision-making under uncertainty.

Conclusion

This paper introduces an imitation-learning-based algorithm that distills a Thompson sampling policy into an explicit policy representation, enabling fast decision-making and easy deployment in real-world systems. By iteratively updating the TS policy and learning a new imitation policy, the researchers achieve comparable performance to batch TS while dramatically reducing decision-time latency.

The successful deployment of this algorithm in multiple video upload systems at Meta, resulting in improved video quality and watch time, demonstrates the practical significance of this work. While the paper acknowledges some limitations, it provides a promising approach for applying advanced decision-making techniques, like Thompson sampling, in latency-sensitive and easily-deployable applications.