# Conservative Bandits

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

## Key facts

- Cited by 59 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2016.

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

- [Recent Advances in Reinforcement Learning in Finance](https://mlsanity.com/paper/2112.04553/) (2021)
- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [Performative Prediction: Past and Future](https://mlsanity.com/paper/2310.16608/) (2023)
- [Regret Minimization with Performative Feedback](https://mlsanity.com/paper/2202.00628/) (2022)
- [Sharp Analysis for KL-Regularized Contextual Bandits and RLHF](https://mlsanity.com/paper/2411.04625/) (2024)
- [Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints](https://mlsanity.com/paper/2202.00150/) (2022)
- [On Kernelized Multi-Armed Bandits with Constraints](https://mlsanity.com/paper/2203.15589/) (2022)
- [Online certification of preference-based fairness for personalized recommender systems](https://mlsanity.com/paper/2104.14527/) (2021)
- [A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints](https://mlsanity.com/paper/2302.04375/) (2023)
- [Almost Optimal Variance-Constrained Best Arm Identification](https://mlsanity.com/paper/2201.10142/) (2022)
- [Safe Exploration for Efficient Policy Evaluation and Comparison](https://mlsanity.com/paper/2202.13234/) (2022)
- [Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Risk](https://mlsanity.com/paper/2204.00706/) (2022)
- [On Safety in Safe Bayesian Optimization](https://mlsanity.com/paper/2403.12948/) (2024)
- [Safe Linear Bandits over Unknown Polytopes](https://mlsanity.com/paper/2209.13694/) (2022)
- [Bandit Algorithms for Precision Medicine](https://mlsanity.com/paper/2108.04782/) (2021)
- [A Reduction-Based Framework for Conservative Bandits and Reinforcement Learning](https://mlsanity.com/paper/2106.11692/) (2021)
- [Robust Bandit Learning with Imperfect Context](https://mlsanity.com/paper/2102.05018/) (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)
- [Robust Generalization and Safe Query-Specialization in Counterfactual Learning to Rank](https://mlsanity.com/paper/2102.05990/) (2021)
- [Stochastic Conservative Contextual Linear Bandits](https://mlsanity.com/paper/2203.15629/) (2022)
- [Balancing optimism and pessimism in offline-to-online learning](https://mlsanity.com/paper/2502.08259/) (2025)
- [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)
- [Safe Data Collection for Offline and Online Policy Learning](https://mlsanity.com/paper/2111.04835/) (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)
- [SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDP](https://mlsanity.com/paper/2406.02165/) (2024)
- [Safety Aware Changepoint Detection for Piecewise i.i.d. Bandits](https://mlsanity.com/paper/2205.13689/) (2022)

## Abstract (arXiv)

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.