Price of Safety in Linear Best Arm Identification

Abstract

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.

arXiv comment20 pages, 1 figures

References in corpus (18)

• Safe Exploration in Continuous Action Spaces
• Bandits with Knapsacks
• Optimal Best Arm Identification with Fixed Confidence
• Best-Arm Identification in Linear Bandits
• Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits
• Linear Stochastic Bandits Under Safety Constraints
• Improving the Expected Improvement Algorithm
• Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem
• Resourceful Contextual Bandits
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization
• Gamification of Pure Exploration for Linear Bandits
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits
• Fully adaptive algorithm for pure exploration in linear bandits
• Optimal Best-arm Identification in Linear Bandits
• Gradient Ascent for Active Exploration in Bandit Problems
• Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners
• Fixed-Confidence Guarantees for Bayesian Best-Arm Identification
• Best Arm Identification with Safety Constraints