Stage-wise Conservative Linear Bandits

Ahmadreza Moradipari, Christos Thrampoulidis, Mahnoosh Alizadeh

In the world of machine learning, the "Multi-Armed Bandit" problem is the classic framework for the exploration-exploitation trade-off: do you stick with the best restaurant you know (exploitation), or try a new one that might be better or much worse (exploration)?

In many real-world scenarios—like medical trials, online advertising, or power grid management—trying a "much worse" option isn't just a disappointment; it’s a disaster. The paper "Stage-wise Conservative Linear Bandits" introduces a robust framework to learn optimal actions while guaranteeing that every single decision remains "safe" relative to a trusted baseline.

The Challenge: Stage-wise Safety

Standard bandit algorithms are inherently "optimistic"—they are willing to take big risks to gain information. However, in safety-critical systems, we often have a baseline policy (like a standard medical treatment or a historical advertising strategy) that we know is "good enough."

The core challenge is: How can a learner explore new, potentially better actions without ever performing significantly worse than this baseline?

Previous research largely focused on cumulative safety, where performance averages out over time. This paper tackles the much stricter stage-wise safety. This means the learner must ensure that at every individual round, the expected reward is at least a certain fraction of the baseline's reward. This is a significantly harder problem because a single "bad" exploration step can violate the constraint immediately.

Expected reward over time, demonstrating that the algorithm strictly maintains the safety constraint (red dashed line) at every iteration.

The Solution: Conservative Exploration

The authors develop two new algorithms, SCLTS and SCLUCB, that solve linear bandit problems while satisfying this strict safety constraint at every step. They are based on the two pillars of bandit theory:

  1. SCLTS (Stage-wise Conservative Linear Thompson Sampling): Uses a Bayesian approach, sampling potential parameters and picking the best action within an "estimated safe set."
  2. SCLUCB (Stage-wise Conservative Linear UCB): Uses frequentist confidence bounds to pick the most optimistic safe action.

The Secret Sauce: * Estimated Safe Sets: The algorithms maintain a "confidence region" of where the true reward parameters likely lie. They only consider actions that are guaranteed to be safe for every parameter in that region. * Conservative Exploration: If the learner is too uncertain to find a safe action that provides good information, it plays a "conservative action"—a clever mixture of the baseline action and a small amount of random noise. This noise is carefully calibrated to be safe while still providing just enough data to "expand" the safe set for future rounds.

Key Insights

  • Randomization is an Asset: One of the most striking insights is that the randomized nature of Thompson Sampling naturally helps expand the "safe set" faster than greedy approaches. Because it explores in many directions, it gathers diverse data more quickly.
  • The "Safety Tax" is Small: The authors prove that the "regret" (the reward lost compared to an omniscient player) is $\mathcal{O}(\sqrt{T})$, which is the same order as standard, unsafe linear bandits. This means you don't have to sacrifice long-term efficiency to stay safe.
  • Logarithmic Fallbacks: Previous methods (like the greedy SEGE algorithm) might play the sub-optimal baseline action $\mathcal{O}(\sqrt{T})$ times. This paper proves their algorithms only need to play it $\mathcal{O}(\log T)$ times. Over a million rounds, that’s the difference between playing the baseline 1,000 times versus just 14 times.
  • Handling the Unknown: The framework is highly robust. The authors demonstrate it still works even if the baseline's reward is unknown or if the safety constraint depends on a completely different hidden variable (using "bandit feedback" on the constraint itself).

Key Results

  • Regret Bounds: SCLTS achieves a probabilistic regret bound of $\mathcal{O}(\sqrt{T} \log^{3/2} T)$, and SCLUCB achieves $\mathcal{O}(\sqrt{T} \log T)$.
  • Empirical Performance: In synthetic simulations featuring a 2-dimensional action set, SCLTS and SCLUCB showed significantly lower variance and faster convergence than the baseline SEGE algorithm.
Cumulative regret comparison showing SCLTS and SCLUCB outperforming the baseline SEGE algorithm with lower variance.

Limitations and Future Work

  • Linearity Assumption: The current work assumes both the rewards and the constraints are linear. While common in theoretical settings, many real-world problems feature complex non-linear dynamics.
  • Baseline Requirement: The learner must have access to a baseline policy. If no safe baseline exists, these algorithms cannot initialize.
  • Future Directions: The authors suggest extending these "conservative" principles to Generalized Linear Models (GLMs) and exploring more complex, non-linear safety boundaries, as well as adapting the framework for upper-bound safety constraints.

Full Citation: Moradipari, A., Thrampoulidis, C., & Alizadeh, M. (2020). Stage-wise Conservative Linear Bandits. 34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada.

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 $\mathcal{O}(\sqrt{T} \log^{3/2}T)$ and $\mathcal{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 rewards. 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 $\mathcal{O}(\log{T})$ times (compared to $\mathcal{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