Safe Linear Bandits with Unknown Safety Gaps

We study stochastic linear bandits with a linear safety constraint that depends on an unknown parameter, requiring every chosen action to be safe at every round with high probability, even though the safe decision set is initially unknown. Prior work achieves $\widetilde{O}(\sqrt{T})$ regret when the safety gap, i.e., the constraint slack at the optimal action, is strictly positive and known to the learner. However, only $\widetilde{O}(T^{2/3})$ regret is established in two distinct cases: when the gap is zero, and when the gap is positive but unknown. This raises two natural questions: is the $\widetilde{O}(T^{2/3})$ bound tight in the zero-gap case, and is knowledge of the gap necessary for $\widetilde{O}(\sqrt{T})$ regret when the gap is positive? We answer both. First, we establish an $\Omega(T^{2/3})$ lower bound for zero-gap instances, showing that the existing upper bound is tight in its dependence on the horizon. Second, we propose Epoch-SLUCB, an algorithm that attains $\widetilde{O}(\sqrt{T})$ regret whenever the safety gap is positive, without requiring its value to be known. We also provide numerical simulations to demonstrate the performance of our algorithm.