Price of Safety in Linear Best Arm Identification
arXiv:2309.08709
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.
20 pages, 1 figures
References in corpus (11)
- Safe Exploration in Continuous Action Spaces
- Best-Arm Identification in Linear Bandits
- Improving the Expected Improvement Algorithm
- Gamification of Pure Exploration for Linear Bandits
- An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits
- Optimal Best-arm Identification in Linear Bandits
- Fully adaptive algorithm for pure exploration 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