# Conservative Contextual Linear Bandits

arXiv: https://arxiv.org/abs/1611.06426 · HTML: https://mlsanity.com/paper/1611.06426/

## Key facts

- Cited by 57 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Nov 2016.

## Built on by (most cited first, 30 of 57)

- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [Regret Minimization with Performative Feedback](https://mlsanity.com/paper/2202.00628/) (2022)
- [An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints](https://mlsanity.com/paper/2102.05295/) (2021)
- [Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints](https://mlsanity.com/paper/2202.00150/) (2022)
- [Best Arm Identification with Safety Constraints](https://mlsanity.com/paper/2111.12151/) (2021)
- [On Kernelized Multi-Armed Bandits with Constraints](https://mlsanity.com/paper/2203.15589/) (2022)
- [Truly No-Regret Learning in Constrained MDPs](https://mlsanity.com/paper/2402.15776/) (2024)
- [Policy Optimization with Linear Temporal Logic Constraints](https://mlsanity.com/paper/2206.09546/) (2022)
- [Active Learning with Safety Constraints](https://mlsanity.com/paper/2206.11183/) (2022)
- [Safe Exploration for Efficient Policy Evaluation and Comparison](https://mlsanity.com/paper/2202.13234/) (2022)
- [Bandit Algorithms for Precision Medicine](https://mlsanity.com/paper/2108.04782/) (2021)
- [Interactively Learning Preference Constraints in Linear Bandits](https://mlsanity.com/paper/2206.05255/) (2022)
- [A Reduction-Based Framework for Conservative Bandits and Reinforcement Learning](https://mlsanity.com/paper/2106.11692/) (2021)
- [Directional Optimism for Safe Linear Bandits](https://mlsanity.com/paper/2308.15006/) (2023)
- [Leveraging Initial Hints for Free in Stochastic Linear Bandits](https://mlsanity.com/paper/2203.04274/) (2022)
- [Stochastic Conservative Contextual Linear Bandits](https://mlsanity.com/paper/2203.15629/) (2022)
- [ESCADA: Efficient Safety and Context Aware Dose Allocation for Precision Medicine](https://mlsanity.com/paper/2111.13415/) (2021)
- [Learning for Edge-Weighted Online Bipartite Matching with Robustness Guarantees](https://mlsanity.com/paper/2306.00172/) (2023)
- [Near-optimal Conservative Exploration in Reinforcement Learning under Episode-wise Constraints](https://mlsanity.com/paper/2306.06265/) (2023)
- [Convex Methods for Constrained Linear Bandits](https://mlsanity.com/paper/2311.04338/) (2023)
- [Safe Data Collection for Offline and Online Policy Learning](https://mlsanity.com/paper/2111.04835/) (2021)
- [Adaptive Multi-Goal Exploration](https://mlsanity.com/paper/2111.12045/) (2021)
- [Price of Safety in Linear Best Arm Identification](https://mlsanity.com/paper/2309.08709/) (2023)
- [Conservative Contextual Combinatorial Cascading Bandit](https://mlsanity.com/paper/2104.08615/) (2021)
- [The Impact of the Geometric Properties of the Constraint Set in Safe Optimization with Bandit Feedback](https://mlsanity.com/paper/2305.00889/) (2023)
- [SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDP](https://mlsanity.com/paper/2406.02165/) (2024)
- [KL-regularization Itself is Differentially Private in Bandits and RLHF](https://mlsanity.com/paper/2505.18407/) (2025)
- [Continuous Mean-Covariance Bandits](https://mlsanity.com/paper/2102.12090/) (2021)
- [Safety Aware Changepoint Detection for Piecewise i.i.d. Bandits](https://mlsanity.com/paper/2205.13689/) (2022)
- [Distributed Stochastic Bandit Learning with Delayed Context Observation](https://mlsanity.com/paper/2207.14391/) (2022)

## Abstract (arXiv)

Safety is a desirable property that can immensely increase the applicability of learning algorithms in real-world decision-making problems. It is much easier for a company to deploy an algorithm that is safe, i.e., guaranteed to perform at least as well as a baseline. In this paper, we study the issue of safety in contextual linear bandits that have application in many different fields including personalized ad recommendation in online marketing. We formulate a notion of safety for this class of algorithms. We develop a safe contextual linear bandit algorithm, called conservative linear UCB (CLUCB), that simultaneously minimizes its regret and satisfies the safety constraint, i.e., maintains its performance above a fixed percentage of the performance of a baseline strategy, uniformly over time. We prove an upper-bound on the regret of CLUCB and show that it can be decomposed into two terms: 1) an upper-bound for the regret of the standard linear UCB algorithm that grows with the time horizon and 2) a constant (does not grow with the time horizon) term that accounts for the loss of being conservative in order to satisfy the safety constraint. We empirically show that our algorithm is safe and validate our theoretical analysis.