# Best Arm Identification with Safety Constraints

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 37 references that are in the map.
- First posted on arXiv 23 Nov 2021.

## Builds on (most cited first, 13 of 13)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Linear Stochastic Bandits Under Safety Constraints](https://mlsanity.com/paper/1908.05814/) (2019)
- [Stagewise Safe Bayesian Optimization with Gaussian Processes](https://mlsanity.com/paper/1806.07555/) (2018)
- [Stochastic Bandits with Linear Constraints](https://mlsanity.com/paper/2006.10185/) (2020)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [Conservative Contextual Linear Bandits](https://mlsanity.com/paper/1611.06426/) (2016)
- [Safe Linear Thompson Sampling with Side Information](https://mlsanity.com/paper/1911.02156/) (2019)
- [On Multi-Armed Bandit Designs for Dose-Finding Clinical Trials](https://mlsanity.com/paper/1903.07082/) (2019)
- [Stage-wise Conservative Linear Bandits](https://mlsanity.com/paper/2010.00081/) (2020)
- [Thresholding Bandit for Dose-ranging: The Impact of Monotonicity](https://mlsanity.com/paper/1711.04454/) (2017)
- [The Influence of Shape Constraints on the Thresholding Bandit Problem](https://mlsanity.com/paper/2006.10006/) (2020)

## Built on by (most cited first, 25 of 25)

- [Active Learning with Safety Constraints](https://mlsanity.com/paper/2206.11183/) (2022)
- [Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Risk](https://mlsanity.com/paper/2204.00706/) (2022)
- [Safe Linear Bandits over Unknown Polytopes](https://mlsanity.com/paper/2209.13694/) (2022)
- [Cost Aware Best Arm Identification](https://mlsanity.com/paper/2402.16710/) (2024)
- [Interactively Learning Preference Constraints in Linear Bandits](https://mlsanity.com/paper/2206.05255/) (2022)
- [Pure Exploration in Bandits with Linear Constraints](https://mlsanity.com/paper/2306.12774/) (2023)
- [Best Arm Identification with Fairness Constraints on Subpopulations](https://mlsanity.com/paper/2304.04091/) (2023)
- [Directional Optimism for Safe Linear Bandits](https://mlsanity.com/paper/2308.15006/) (2023)
- [Price of Safety in Linear Best Arm Identification](https://mlsanity.com/paper/2309.08709/) (2023)
- [The Impact of the Geometric Properties of the Constraint Set in Safe Optimization with Bandit Feedback](https://mlsanity.com/paper/2305.00889/) (2023)
- [Best Arm Identification with Resource Constraints](https://mlsanity.com/paper/2402.19090/) (2024)
- [Contextual Combinatorial Multi-output GP Bandits with Group Constraints](https://mlsanity.com/paper/2111.14778/) (2021)
- [Fair Active Learning in Low-Data Regimes](https://mlsanity.com/paper/2312.08559/) (2023)
- [Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget](https://mlsanity.com/paper/2405.15090/) (2024)
- [Constrained Best Arm Identification in Grouped Bandits](https://mlsanity.com/paper/2412.08031/) (2024)
- [Benefits of Monotonicity in Safe Exploration with Gaussian Processes](https://mlsanity.com/paper/2211.01561/) (2022)
- [Constrained Online Decision-Making: A Unified Framework](https://mlsanity.com/paper/2505.07101/) (2025)
- [Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validation](https://mlsanity.com/paper/2506.03062/) (2025)
- [Deceptive Exploration in Multi-armed Bandits](https://mlsanity.com/paper/2510.08794/) (2025)
- [Constrained Best Arm Identification with Tests for Feasibility](https://mlsanity.com/paper/2511.09808/) (2025)
- [Fixed-Budget Constrained Best Arm Identification in Grouped Bandits](https://mlsanity.com/paper/2603.04007/) (2026)
- [Robust Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2311.04731/) (2023)
- [Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints](https://mlsanity.com/paper/2410.18844/) (2024)
- [Dominant Arm Identification with Mixing and Recycling Observed Samples](https://mlsanity.com/paper/2608.01545/) (2026)
- [Distinguish or Homogenize: Last-Chance Policy Identification and Risk-Budgeted Recovery under Irreversible Resource Depletion](https://mlsanity.com/paper/2609.36741/) (2026)

## Abstract (arXiv)

The best arm identification problem in the multi-armed bandit setting is an excellent model of many real-world decision-making problems, yet it fails to capture the fact that in the real-world, safety constraints often must be met while learning. In this work we study the question of best-arm identification in safety-critical settings, where the goal of the agent is to find the best safe option out of many, while exploring in a way that guarantees certain, initially unknown safety constraints are met. We first analyze this problem in the setting where the reward and safety constraint takes a linear structure, and show nearly matching upper and lower bounds. We then analyze a much more general version of the problem where we only assume the reward and safety constraint can be modeled by monotonic functions, and propose an algorithm in this setting which is guaranteed to learn safely. We conclude with experimental results demonstrating the effectiveness of our approaches in scenarios such as safely identifying the best drug out of many in order to treat an illness.