Abstract
The design and performance analysis of bandit algorithms in the presence of stage-wise safety or reliability constraints has recently garnered significant interest. In this work, we consider the linear stochastic bandit problem under additional linear safety constraints that must be satisfied at each round. We provide a new safe algorithm based on linear Thompson Sampling (TS) for this problem and show a frequentist regret of order $\mathcal{O} (d^{3/2}\log^{1/2}d \cdot T^{1/2}\log^{3/2}T)$, which remarkably matches the results provided for the standard linear TS algorithm in the absence of safety constraints. We compare the performance of our algorithm with a UCB-based safe algorithm and highlight how the inherently randomized nature of TS leads to a superior performance in expanding the set of safe actions the algorithm has access to at each round.
Introduction
In many real-world sequential decision-making problems—such as medical trials, robotics, or power grid management—an algorithm cannot simply "move fast and break things." It must ensure that its actions are safe at every single step of the learning process. This requirement introduces a fundamental tension: to find the optimal action, an agent must explore, but exploration near the boundaries of knowledge risks violating safety constraints.
This paper addresses the linear stochastic bandit problem with stage-wise linear safety constraints. In this setting, a learner chooses an action to maximize a linear reward based on an unknown parameter $\theta_\star$. Simultaneously, the action must satisfy a safety constraint defined by $x_t^\top \mu_\star \leq C$, where the safety parameter $\mu_\star$ is also unknown. The learner only receives noisy "side information" about $\mu_\star$ after taking an action. The challenge lies in balancing the conservative behavior required for safety with the optimism needed to minimize regret.
The Safe-LTS Algorithm
The authors propose Safe Linear Thompson Sampling (Safe-LTS), which adapts the classic Thompson Sampling framework to a safety-critical environment through two primary mechanisms:
1. Inner Approximation of the Safe Set
Using the side information received at each step, the algorithm constructs a high-probability confidence ellipsoid around the unknown safety parameter $\mu_\star$. It then defines a conservative "safe decision set" consisting only of actions that satisfy the safety constraint for every possible parameter within that ellipsoid. This ensures that even in the worst-case scenario within the confidence interval, the chosen action remains safe.
2. Inflated Thompson Sampling
Standard TS works by computing a least-squares estimate of the reward parameter $\theta_\star$, adding random Gaussian noise, and selecting the action that maximizes the reward for that perturbed parameter. However, because Safe-LTS restricts actions to a conservative inner set, standard TS often lacks the "optimism" required to push the boundaries and discover new safe actions.
To overcome this, the authors introduce a novel twist: variance inflation. They mathematically prove that the TS random perturbation must satisfy a stricter anti-concentration property to guarantee exploration. By injecting additional variance (specifically, an extra $\frac{2}{C}LS$ term) into the sampled reward parameter, the algorithm is forced to occasionally "reach" for actions on the edge of the known safe set, effectively expanding the safe boundaries over time.
Key Insights and Results
Matching Unconstrained Performance
One of the most significant theoretical contributions of this work is the proof that safety does not have to come at the cost of asymptotic performance. Safe-LTS achieves a frequentist regret bound of $\mathcal{O}(d^{3/2} \log^{1/2} d \cdot T^{1/2} \log^{3/2} T)$. This $\mathcal{O}(\sqrt{T})$ scaling matches the state-of-the-art bounds for standard linear Thompson Sampling without safety constraints. This suggests that with the right randomization strategy, the "safety tax" on regret can be minimized to a constant factor rather than a change in rate.
Randomization vs. Deterministic Exploration
Existing Upper Confidence Bound (UCB) algorithms for safe bandits often struggle because they are inherently deterministic. They frequently get "stuck" in their initial conservative safe sets and require an explicit, highly suboptimal "pure exploration" phase to learn the boundaries. Safe-LTS demonstrates that the inherent randomness of Thompson Sampling naturally pushes the boundaries of the safe set. In empirical tests, Safe-LTS vastly outperforms "Naive Safe-LUCB" and improves upon prior theoretical models that could only guarantee $\mathcal{O}(T^{2/3})$ regret when safety constraints were active.
Limitations and Future Work
While Safe-LTS represents a major step forward, two primary areas for improvement remain:
- Late-Stage Over-Exploration: The theoretical proof requires inflated variance at all rounds to guarantee optimism. However, once the safe set is well-understood, this extra noise causes unnecessary regret. The authors suggest a "dynamic noise" heuristic that decreases variance over time, which performs well in practice but currently lacks a formal proof.
- Linearity Constraints: The current model assumes both rewards and safety constraints are linear. Extending this TS-based safe exploration to non-linear settings, such as those modeled by Gaussian Processes, is a promising direction for future research.
Conclusion
Safe-LTS provides a robust framework for learning in environments where mistakes are costly. By leveraging the power of randomized sampling and variance inflation, it achieves optimal regret while maintaining strict stage-wise safety, proving that we do not necessarily have to sacrifice long-term performance for short-term reliability.
Summary updated