Conservative Bandits

Abstract

We study a novel multi-armed bandit problem that models the challenge faced by a company wishing to explore new strategies to maximize revenue whilst simultaneously maintaining their revenue above a fixed baseline, uniformly over time. While previous work addressed the problem under the weaker requirement of maintaining the revenue constraint only at a given fixed time in the future, the algorithms previously proposed are unsuitable due to their design under the more stringent constraints. We consider both the stochastic and the adversarial settings, where we propose, natural, yet novel strategies and analyze the price for maintaining the constraints. Amongst other things, we prove both high probability and expectation bounds on the regret, while we also consider both the problem of maintaining the constraints with high probability or expectation. For the adversarial setting the price of maintaining the constraint appears to be higher, at least for the algorithm considered. A lower bound is given showing that the algorithm for the stochastic setting is almost optimal. Empirical results obtained in synthetic environments complement our theoretical findings.

9 pages, plus 4-page appendix, with 3 figures. Submitted to ICML 2016

References in corpus (5)

• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
• Adaptive Online Prediction by Following the Perturbed Leader
• Informational Confidence Bounds for Self-Normalized Averages and Applications
• Optimally Confident UCB: Improved Regret for Finite-Armed Bandits

Cited by in corpus (15)

• Stagewise Safe Bayesian Optimization with Gaussian Processes
• Linear Stochastic Bandits Under Safety Constraints
• Exploration-Exploitation in Constrained MDPs
• Conservative Policy Construction Using Variational Autoencoders for Logged Data with Missing Values
• Conservative Exploration in Reinforcement Learning
• Stochastic Bandits with Linear Constraints
• Stage-wise Conservative Linear Bandits
• Bandit Algorithms for Precision Medicine
• Learning from User Interactions with Rankings: A Unification of the Field
• Group Fairness in Bandit Arm Selection
• Conservative Contextual Combinatorial Cascading Bandit
• Improved Algorithms for Conservative Exploration in Bandits
• Robust Bandit Learning with Imperfect Context
• Multi-armed Bandits with Cost Subsidy
• Uniformly Conservative Exploration in Reinforcement Learning