mlsanityData to 14 Oct 2026

Price of Safety in Linear Best Arm Identification

arXiv 2309.08709 ↗First posted 15 Sep 2023stat.ML cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

We introduce the safe best-arm identification framework with linear feedback, where the agent is subject to some stage-wise safety constraint that linearly depends on an unknown parameter vector. The agent must take actions in a conservative way so as to ensure that the safety constraint is not violated with high probability at each round. Ways of leveraging the linear structure for ensuring safety has been studied for regret minimization, but not for best-arm identification to the best our knowledge. We propose a gap-based algorithm that achieves meaningful sample complexity while ensuring the stage-wise safety. We show that we pay an extra term in the sample complexity due to the forced exploration phase incurred by the additional safety constraint. Experimental illustrations are provided to justify the design of our algorithm.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 33 of its 48 references that are in the map. First posted on arXiv 15 Sep 2023.

Builds on

33 of 48 references.

References · 33

  1. 2021Safe Learning in Robotics: From Learning-Based Control to Safe Reinforcement Learningcited by 371
  2. 2018Safe Exploration in Continuous Action Spacescited by 247
  3. 2016Optimal Best Arm Identification with Fixed Confidencecited by 239
  4. 2013Bandits with Knapsackscited by 164
  5. 2013lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Banditscited by 149
  6. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 134
  7. 2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 134
  8. 2014Best-Arm Identification in Linear Banditscited by 100
  9. 2019Sequential Experimental Design for Transductive Linear Banditscited by 91
  10. 2019Linear Stochastic Bandits Under Safety Constraintscited by 90
  11. 2015Linear Contextual Bandits with Knapsackscited by 82
  12. 2016Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problemcited by 79
21 more
  1. 2018Stagewise Safe Bayesian Optimization with Gaussian Processescited by 79
  2. 2020Optimal Best-arm Identification in Linear Banditscited by 71
  3. 2019Non-Asymptotic Pure Exploration by Solving Gamescited by 63
  4. 2020Gamification of Pure Exploration for Linear Banditscited by 63
  5. 2016Conservative Banditscited by 59
  6. 2016Conservative Contextual Linear Banditscited by 57
  7. 2017Improving the Expected Improvement Algorithmcited by 54
  8. 2014Resourceful Contextual Banditscited by 45
  9. 2020An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Banditscited by 45
  10. 2017Fully adaptive algorithm for pure exploration in linear banditscited by 43
  11. 2019Fixed-Confidence Guarantees for Bayesian Best-Arm Identificationcited by 38
  12. 2015Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Banditscited by 29
  13. 2019Safe Linear Stochastic Banditscited by 27
  14. 2021Best Arm Identification with Safety Constraintscited by 25
  15. 2019Best Arm Identification in Generalized Linear Banditscited by 18
  16. 2019Safe Convex Learning under Uncertain Constraintscited by 17
  17. 2019Gradient Ascent for Active Exploration in Bandit Problemscited by 15
  18. 2020Explicit Best Arm Identification in Linear Bandits Using No-Regret Learnerscited by 6
  19. 2020Decentralized Multi-Agent Linear Bandits with Safety Constraintscited by 6
  20. 2019Towards Optimal and Efficient Best Arm Identification in Linear Banditscited by 3
  21. 2020Refined bounds for randomized experimental designcited by 2

Built on by

Cited by year

Citing papers per year: 2024: 2; 2025: 2.

4 papers.

  1. 2024Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budgetcited by 2
  2. 2025Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budgetcited by 1
  3. 2025Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validationcited by 1
  4. 2024Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraintscited by 0