Stage-wise Conservative Linear Bandits

Ahmadreza Moradipari, Christos Thrampoulidis, Mahnoosh Alizadeh

Introduction

In many real-world applications of bandit optimization, such as clinical trials or online advertising, exploration can be inherently risky. While standard bandit algorithms aim to maximize cumulative reward, they often ignore instantaneous safety constraints. This paper addresses the problem of stage-wise conservative linear stochastic bandits, where the learner must ensure that the expected reward of any chosen action never falls below a fixed fraction of a known baseline. Unlike previous work focusing on cumulative safety, this "stage-wise" approach ensures that every single decision meets a minimum safety threshold.

Proposed Algorithms: SCLTS and SCLUCB

The authors introduce two novel algorithms: Stage-wise Conservative Linear Thompson Sampling (SCLTS) and Stage-wise Conservative Linear UCB (SCLUCB). Both algorithms leverage confidence ellipsoids to maintain an estimate of the unknown reward parameter $\theta_*$.

The Core Mechanism

  1. Confidence Regions: The learner maintains a set that contains $\theta_*$ with high probability.
  2. Estimated Safe Set: At each iteration, the algorithm identifies actions guaranteed to be safe for all parameters within the confidence ellipsoid.
  3. Randomized Conservative Exploration: A key innovation is the use of a randomized conservative action—a convex combination of the baseline action and a random noise vector—when uncertainty is high. This allows for informative exploration while strictly adhering to safety constraints.

Theoretical and Numerical Results

A significant theoretical contribution is the proof that these algorithms play the sub-optimal baseline action only $O(\log T)$ times, a substantial improvement over the $O(\sqrt{T})$ required by previous methods like SEGE. Furthermore, SCLUCB achieves a regret bound of $O(d\sqrt{T} \log T)$, matching the performance of standard linear bandits that operate without safety constraints.

Regret comparison between SCLTS, SCLUCB, and the state-of-the-art SEGE algorithm.

Numerical simulations confirm these theoretical findings. As shown in the regret plots, SCLTS and SCLUCB significantly outperform the SEGE algorithm in terms of cumulative regret and convergence speed. The proposed framework is also versatile, capable of handling variations such as bandit-feedback constraints or unknown baseline reward sequences.

Expected reward over time, demonstrating that the safety constraint (red dashed line) is never violated.

Crucially, the algorithms maintain safety throughout the learning process. The expected reward consistently stays above the predefined safety threshold (indicated by the red dashed line), even during the initial exploration phase.

Conclusion and Future Directions

SCLTS and SCLUCB provide a robust framework for safe exploration in linear bandit problems. By reducing the reliance on sub-optimal baseline actions and providing tight regret bounds, they bridge the gap between theoretical safety and practical performance. Future work includes extending these principles to Generalized Linear Bandits and handling non-linear safety constraints.

Summary updated

Abstract

We study stage-wise conservative linear stochastic bandits: an instance of bandit optimization, which accounts for (unknown) safety constraints that appear in applications such as online advertising and medical trials. At each stage, the learner must choose actions that not only maximize cumulative reward across the entire time horizon but further satisfy a linear baseline constraint that takes the form of a lower bound on the instantaneous reward. For this problem, we present two novel algorithms, stage-wise conservative linear Thompson Sampling (SCLTS) and stage-wise conservative linear UCB (SCLUCB), that respect the baseline constraints and enjoy probabilistic regret bounds of order O(\sqrt{T} \log^{3/2}T) and O(\sqrt{T} \log T), respectively. Notably, the proposed algorithms can be adjusted with only minor modifications to tackle different problem variations, such as constraints with bandit-feedback, or an unknown sequence of baseline actions. We discuss these and other improvements over the state-of-the-art. For instance, compared to existing solutions, we show that SCLTS plays the (non-optimal) baseline action at most O(\log{T}) times (compared to O(\sqrt{T})). Finally, we make connections to another studied form of safety constraints that takes the form of an upper bound on the instantaneous reward. While this incurs additional complexity to the learning process as the optimal action is not guaranteed to belong to the safe set at each round, we show that SCLUCB can properly adjust in this setting via a simple modification.
BibTeX
@inproceedings{moradipari2020stage,
  author = {Ahmadreza Moradipari and Christos Thrampoulidis and Mahnoosh Alizadeh},
  title = {{Stage-wise Conservative Linear Bandits}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=yVH9KCdJWTo},
}
Figure