Conservative Contextual Linear Bandits

Abstract

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.

Cited by in corpus (23)

• Linear Stochastic Bandits Under Safety Constraints
• Exploration-Exploitation in Constrained MDPs
• An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints
• BubbleRank: Safe Online Learning to Re-Rank via Implicit Click Feedback
• Warm-starting Contextual Bandits: Robustly Combining Supervised and Bandit Feedback
• Towards Safe Policy Improvement for Non-Stationary MDPs
• Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model
• No-Regret Exploration in Goal-Oriented Reinforcement Learning
• Conservative Exploration in Reinforcement Learning
• Stochastic Bandits with Linear Constraints
• Stage-wise Conservative Linear Bandits
• Learning for Dose Allocation in Adaptive Clinical Trials with Safety Constraints
• Learning from User Interactions with Rankings: A Unification of the Field
• Thompson Sampling for Contextual Bandit Problems with Auxiliary Safety Constraints
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning
• Conservative Exploration using Interleaving
• Best Arm Identification with Safety Constraints
• Continuous Mean-Covariance Bandits
• Stochastic Linear Bandits with Protected Subspace
• Rarely-switching linear bandits: optimization of causal effects for the real world
• Adaptive Multi-Goal Exploration
• Improved Algorithms for Conservative Exploration in Bandits
• Multi-armed Bandits with Cost Subsidy