This paper, presented at NeurIPS 2019, introduces a practical framework for deploying contextual bandits in real-world systems where "safety" is just as important as "reward." Developed by researchers at Facebook, the work focuses on a common engineering dilemma: how do you optimize a new feature (like video quality) without accidentally breaking a critical baseline metric (like upload reliability)?
The Problem: Instance-Level vs. Cumulative Constraints
In a standard contextual bandit setting, an algorithm learns to pick the best action (e.g., which ad to show) to maximize a reward (e.g., clicks). However, in complex systems, actions often have side effects. For example, a video platform could choose to upload every video at 1080p to maximize quality, but for users on slow 2G connections, this would lead to constant timeouts and failed uploads, severely impacting reliability.
Existing "constrained" bandit algorithms often focus on cumulative constraints, meaning they care about the average performance over time. The authors argue this is "unfair" because the algorithm might choose to provide a terrible experience for one sub-population (e.g., rural users with slow internet) to "subsidize" better performance for another. This paper tackles instance-level constraints: ensuring that for every single decision, the chosen action is expected to be safe relative to a "status quo" baseline policy.
Methods: TS-ASC
The core contribution is TS-ASC (Thompson Sampling with Auxiliary Safety Constraints). This algorithm elegantly tames the exploration of standard Thompson Sampling by using it as a safety filter. At each time step $t$, the algorithm follows these steps:
- Posterior Sampling: The algorithm maintains a distribution over possible models for both the reward and the constraint. It draws a random sample ($\tilde{f}_t$) from this posterior.
- Feasibility Check: It identifies a "feasible set" of actions. An action is considered feasible if, according to the sampled model, its predicted safety metric is at least $(1 - \alpha)$ times the performance of the current baseline policy. Here, $\alpha$ is a "safety slack" parameter that controls the tolerance for safety violations.
- Optimization: From that feasible set, it selects the action that maximizes the sampled reward.
- Update: It observes the actual outcome and updates its models.
For the real-world video application, the authors used a Deep Kernel Learning approach: a neural network acts as a feature extractor, which then feeds into a Gaussian Process (GP) with a Bernoulli likelihood to model the probability of a successful upload. This allows the model to handle high-dimensional context vectors effectively.
Key Results and Insights
The paper evaluates the algorithm on a synthetic 100-arm linear bandit problem and a massive real-world video transcoding dataset from Facebook. The context vector ($x \in \mathbb{R}^{39}$) includes features like device model, OS, and network type, while the actions are four possible upload qualities: {360p, 480p, 720p, 1080p}.
- Superior Regret Management: In synthetic tests, TS-ASC achieved significantly lower regret than baseline policies and outperformed UCB-based constrained algorithms (CLUCB2) in navigating the trade-off.
- Real-World Gains: In the video transcoding task, vanilla Thompson Sampling (without constraints) frequently tanked reliability. TS-ASC, however, found parameterizations that increased both quality and reliability simultaneously compared to the production baseline.
- Constraint Satisfaction: The algorithm quickly converged to a policy that satisfied instance-level constraints. In contrast, cumulative-constraint methods often continued to violate safety for large portions of the population—up to 40% of the time as the safety slack $\alpha$ increased.
Limitations and Future Work
While the empirical results are strong, the paper does not provide formal regret bounds for TS-ASC. The authors note that proving these would likely require defining a specific "notion of correlation" between the reward and constraint metrics. Additionally, the safety of the algorithm relies heavily on the accuracy of the posterior distribution; if the model is overconfident and wrong, it might flag an unsafe action as feasible. Finally, while the method generalizes to multiple constraints, the computational complexity of checking feasibility across many metrics in real-time remains a challenge for future research.
Summary updated