Thompson Sampling for Contextual Bandit Problems with Auxiliary Safety Constraints

Samuel Daulton, Shaun Singh, Vashist Avadhanula, Drew Dimmery, Eytan BakshyarXiv 2019 · OpenReview

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:

  1. 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.
  2. 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.
  3. Optimization: From that feasible set, it selects the action that maximizes the sampled reward.
  4. Update: It observes the actual outcome and updates its models.
Constraint outcome values over time, showing how TS-ASC maintains safety relative to the baseline threshold (red line).

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.
Comparison of TS-ASC against baselines in terms of per-time-step regret (top) and percentage of violated constraints (bottom) across different safety slack values (α).

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

Abstract

Recent advances in contextual bandit optimization and reinforcement learning have garnered interest in applying these methods to real-world sequential decision making problems. Real-world applications frequently have constraints with respect to a currently deployed policy. Many of the existing constraint-aware algorithms consider problems with a single objective (the reward) and a constraint on the reward with respect to a baseline policy. However, many important applications involve multiple competing objectives and auxiliary constraints. In this paper, we propose a novel Thompson sampling algorithm for multi-outcome contextual bandit problems with auxiliary constraints. We empirically evaluate our algorithm on a synthetic problem. Lastly, we apply our method to a real world video transcoding problem and provide a practical way for navigating the trade-off between safety and performance using Bayesian optimization.
BibTeX
@misc{daulton2019thompson,
  author = {Samuel Daulton and Shaun Singh and Vashist Avadhanula and Drew Dimmery and Eytan Bakshy},
  title = {{Thompson Sampling for Contextual Bandit Problems with Auxiliary Safety Constraints}},
  year = {2019},
  eprint = {1911.00638},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1911.00638},
}
Figure