Constrained Linear Thompson Sampling
Authors: Aditya Gangrade
Venkatesh Saligrama
Venue: NeurIPS 2025 poster ()
Keywords: Safe Bandits
Linear Bandits
Thompson Sampling
Primary area: theory
TL;DR: Methods based on Thompson Sampling for safe linear bandits that significantly improve computational costs while retaining regret and risk performance.

Abstract: We study safe linear bandits (SLBs), where an agent selects actions from a convex set to maximize an unknown linear objective subject to unknown linear constraints in each round. Existing methods for SLBs provide strong regret guarantees, but require solving expensive optimization problems (e.g., second-order cones, NP hard programs). To address this, we propose Constrained Linear Thompson Sampling (COLTS), a sampling-based framework that selects actions by solving perturbed linear programs, which significantly reduces computational costs while matching the regret and risk of prior methods. We develop two main variants: 
S-COLTS, which ensures zero risk and ${\tilde{O}(\sqrt{d^3 T})}$ regret given a safe action, and R-COLTS, which achieves ${\tilde{O}(\sqrt{d^3 T})}$ regret and risk with no instance information. In simulations, these methods match or outperform state of the art SLB approaches while substantially improving scalability. On the technical front, we introduce a novel coupled noise design that ensures frequent 'local optimism' about the true optimum, and a scaling-based analysis to handle the per-round variability of constraints.

Constrained Linear Thompson Sampling
Adiyya Gangrade Boston University gangrade@bu.ert edu
Venkatesh Saligrama Boston University srv@bu. edu
Abstract
We study safe linear bandits (SLBs), where agent selects actions from convex set to maximize an unknown linear objective subject to unknown linear constraints in each round. Existing methods for SLBs provide strong regret guarantees, but require solving expensive optimization problems. To address this, we propose Constrained Linear Thompson Sampling (COLTS), sampling-baset framework that selects actions by solving perturbed linear programs, which significantly reduces computational costs while matching the regret and risk of prior methods. We develop two main variants: S-COLTS, which ensures zero risk and O(vFT) regret given a safe action, and R-COLTS, which achieves O(vdTT) regret and risk with no instance information. In simulations, these methods match outperform state of the art SLB approaches while substantially improving scalability. On the technical front, we introduce novel coupled noise design that ensures frequent 'local optimism' about the true optimum, and a scaling-bare based analysis to handle the per-round variability of constraints.
Introduction
Stochastic bandit problems are a fundamental model for optimising unknown objectives through repeated trials. While single-objective bandit theory is well-developed, real-world learners must also deal with unknown constraints at every round of interaction. For instance, in dose-finding [AKR21], micro-grid control [FLZY22], and fair recommendation [Cho+24], learner must choose actions that maximise reward while never crossing unknown toxicity, voltage, or exposure limits (see ŞB).
The safe linear bandit (SLB) problem models these scenarios in linear programming (LP) setting: a learner selects actions { from a convex domain AA to optimize an unknown objective vector 0, Rd subject to unknown constraints of the form Φ.a S a, where Φ. Rmxd After each action, the learner observes noisy feedback of the objective 0_ a + noise and the constraints a a + noise, thus acquiring information to guide future actions. Performance in SLBs is measured via the
Σ (0. (a. (a.--:))) and risk, ST Σ max (b.a. - (aaa)-a)))).
regret, R
(I)
ETT
where as is the optimal action under the true (but unknown) constraints, and (-) == max(,, 0).
There are two main notions of safety in SLBs:
Hard constraint enforcement, which requires that with high probability, Sy = for all T. This only achievable if the learner has prior access to known safe action Qsafe-
Soft constraint enforcement, which requires S = oTT) with high probability (whp). This is a weaker requirement, but does not need prior information.
series of recent work [e.g. GCS24; PGB24; AAT19; MAAT21] offers OFUL-style algorithms for SLBs with strong theoretical guarantees. However, these often require the solution of nontrivial optimisation problems (second-order conic programs, and sometimes NP-hard problems) in each round. Our motivation lies in improving this computational cost.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: COMPARISON OF SLB METHODS. 'Known Osate" means that the method requires an action known a priori to be safe. A(a) == 0_ (a. a) is the reward gap of an action a, and I(a) = min, 2.a)4 is its safety margin. R(a)= == + (A())/((a)) if I()))) > O, and oo otherwise. LP is the computation needed to optimize a linear objective with m. linear constraints over A to constant approximation. SOCP is the same with m second-order conic constraints. We write 'NP-hard' if implementing the method needs a solver for an NP-hard problem. UPT-PESS refers to most frequentist hard enforcement methods discussed in $1.1, which have similar costs and bounds; SAFE-LTS is due to [MAAT2I]; DOSS and the lower bound are due to [GCS24].
Algorithm
Assumptions
Regret
Risk
Compute at t
OPT-PESS
Known Osafe
R (asate)
Ö(VPPT)
NP-hard d SOCP log(t) SOCP log(t) LP log(t))
Relaxed OPT-PESS
Known asafe
R (asate)
((VdTT)
SAFE-LTS
Known Osafe
R (asate)
((vdST)
0
S-COLIS
Known Osafe
R ((sate))
-((vBTT)
0
DOSS
Feasibility
(VdTT)
Ö(VPT)
NP-hard
R-COLTS
Feasibility
((VTT)
Ö(v (
LP log (1)
BOUND
Feasibility
max (Ry max(R,, Sr) ((VT), no matter the instance;
Contributions. We introduce a sampling-based approach, COnstrained Linear Thompson Sampling (COLTS), which adds carefully chosen noise to estimates of both the objective and constraint parame- ters, and selects actions according to this perturbed program. This allows us to maintain the same order of regret and risk bounds as prior methods, while substantially reducing the complexity of cach round. However, just perturbing the program as above does not directly yield good actions, since the perturbed program may be infeasible, or its optimum may be unsafe. We therefore develop two augmentations of COLTS, which address the SLB problem under distinct regimes:
S-COLTS assumes a given safe action Osafe- Actions are picked by first solving a perturbed LP (while ensuring that asafe is feasible), and then scaling its optimum towards Osafe to ensure safety. This yields zero risk, and regret (aastte) O(VPT) (see $2, or Table 1 for definition of R(a)).
R-COLTS requires only feasibility of the true problem, and operates by sampling (log T)) perturbed programs, and setting ag to be the optimiser of the one with largest value. This resampling directly yields optimism, leading instance-indepenndnt d(v regret and risk bounds. We additionally argue that under Slater's condition, and with extra exploration, a similar regret and risk guarantee follows without resampling, and so solving only one optimisation per round.
Table summarizes our results in comparison to prior work. We highlight that our results match previously attainable regret and risk bounds with only O(LP) computation per round. This yields the first efficient method for soft enforcement, and significantly speeds up hard constraint enforcement. A simulation study ($6,$J) further validates these claims. Contextual extensions
discussed in $E. Technical Innovations. The random perturbations in our approach cause two challenges that break existing analyses of linear TS: (i) the feasible region fluctuates at each round; and (ii) the true optimum a, can become infeasible under perturbed constraints. We address these via two key innovations:
A) Coupled Noise Design. Independent perturbations of objectives and constraints are difficult to analyze and yield undesirable exponential factors (e)(m)). We instead couple the perturbations by adding a single random vector y to the objective estimate and - to each row of the constraint estimate. This coupling ensures a high local optimism rate: with constant probability, the perturbed program is feasible at the true optimum a., achieving regret bounds scaling only with log(m). Empirical studies ($6.J) confirm the advantages of coupled noise.
B) Scaling and Resampling. The fluctuating constraints disable both existing analysis frameworks for linear TS: the 'unsaturation' approach of [AG13] and the 'optimism' approach of [AL17]. To analyze S-COLTS, we adapt the unsaturation framework with a new acaling-based trick allowing comparisons across distinct feasible regions. For R-COLTS, we instead use resampling to directly generate optimistic and feasible actions, bypassing these analytic barriers entirely.
1.1 Related Work
Safe Bandits. Safe bandits have been studied under two main notions of constraint enforcement: seft [CGS22; GCS24] and hard [AAT19; MAAT21; PGBJ21; PGB24; HTA23; HTA24]. Soft enforcement achieves regret and risk bounds of Õ D(VdT)) with improved instance-specifi guarantees for polytopal domains. Hard enforcement achieves zero risk, and regret bounds of (Rs(attee) /dT but given safe action dsafe- Efficient variants of these methods instead achieve weaker regret bounds
2

---

of ((((aaat)) (asate) VT.). In contrast to safe bandits, bandits with knapsacks [BKS13; AD16] control aggregate constraints, which is unsuitable for roundwise safety enforcement (see $C).
Computational Complexity. Existing efficient hard-enforcement methods rely on frequentists confidence sets for constraints, which induce m expensive second-order conic (SOC) constraints during action selection [PGBJ21; PGB24; AAT19; MAAT21]. Most variants require solving 2d such problems per round. Our approach, S-COLTS, instead only optimises over linear constraints while maintaining near-optimal guarantees. The scaling approach inherent to S-COLTS is related to the prior ROFUL method [HTA24], although this uses the inefficient method DOSS as a subroutine.
Notably, no computationally efficient methods have previously been proposed for soft enforcement. The main point of comparison, DOSS need to solve (2d)m+ LPs each round [GCS24]. R-COLTS resolves this gap by sampling ([log(t) perturbed programs each round. Under mild conditions (Slater's condition), one can further reduce to single I.P per round. See &C for more details.
Thompson Sampling (TS), Frequentist bounds for linear TS were first established by Agrawal & Goyal [AG13] through an 'unsaturation' approach, while Abeille & Lazaric [AL17] developed related 'global optimism' approach. Neither approach extends to SLBs due the per-round fluctuation of the perturbed constraints, and the ensuing variability of the 'feasible regions' for each round (see &C for more details). We overcome these challenges through our coupled noise design, ensuring frequent optimism, and a novel scaling trick to compare solutions across distinct feasible regions.
The only existing sampling-based treatment of unknown constraints is due to Chen et al. [CGS22] for multi-armed settings, who use posterior quantiles to enforce constraints. Although their method does not scale to continuous action sets, our resampling approach can be interpreted as an efficient, scalable analogue for simultancously enforcing constraints and optimizing reward indices.
2 Problem Definition and Background
Notation. For a vector u. [|i|| denotes its fg-norm. For a PSD matrix M, ||ollax = ||M s" is the unit sphere in Rd For a matrix M, M is the ith row of M. Im is the all ones vector in R". Also see $A for an extensive glossary of notation used in the paper.
Setup. An instance of a SLB problem is defined by an objective 0, E Rdd, a constraint matrix $. E Rrxdd constraint levels a E RT a compact conver domain A C Idd and 8 E (0, 1). A, a, 6 are known to the learner, but 0, and 4. are not. The program of interest is max 0__ a s.t. 4,a S a, a A, assumed to be feasible. a., denotes a(ny) maximiser of this program. The reward gap of a E A is A(a) ;= 0_ (o.. a), and its safety margin is I'(a)= = min; (a - L,a)4. For infeasible a, [(a)= = 0, and A may be negative. We set R(aa = 1 + ((r)/T(a) [(a) > 0, and oo otherwise. Play. We index rounds by t. At each f, the learner picks a, E A, and receives the feedback RG = 0. a, + w:", and St = 2.a; + wy, where w²" R and wy E R" are noise processes. C2 denotes algorithmic randomness at round t. The historical filtration is 5t-1 == o ((((a, , R., S.. Cx))sst), and G, = 05 U ((oi, G.)).. The action a, must be adapted to a (5 U ((Ci))))
The Soft Enforcement SLB problem demands algorithms that ensure, with high probability, that both the metries R, and Sy (see (1) grow sublinearly with T.
The Hard Enforcement SLB problem demands algorithms that ensure, with high probability, that Sy = 0 and R = (T). This is enabled by a safe starting point Osafe such that I(asafe) > 0.
Standard Assumptions. We assume the following standard conditions [e-g. APS11] on the instance
(0., A,, and noise. All subsequent results only hold under these assumptions.
Boundedness: ||0_|| I 1, for each row i, | l| < 1, and AA C {a ||a|| 1}.
$) T)² is centred and 1-subGaussian given G,, i.e.. E[wy/[5,] = O, and A\ E m=* E[exp(A )o..] S exp(()>²1//2).
SubGaussian noise: We := (wf, (w,)
To simplify the form of our bounds, we also assume that log (lg(m//) o(d) when stating theorems.
Background. The (1-)RLS estimates for 0z, 4. given the history 5i-1 are
0. = arg min
Σ(OTa, a, R2)² + 1101, and a = arg min Σ | - S2 + Σ 11$5112.
6 s<t
The standard confidence sets [APSII] for (0.. T.) are
C (5) = (0: 0 l.l.v. S (b)}. and (6) (8) = 15 V rows i, 1 -0/llv. S ww(())}
where Vn I Σ Aci a and wy := + 1/22 (m + 1)/5) 1/4 (det Vi). A key standard result states that these confidence sets are consistent [APS11].
3

---

Lemma 1. Let the consistency event at time t be (ōn := {0- E (6). 9, E (8)), and let Con(o) N2z1 (8), Under the standard assumptions. for all & (0, 1), P(Con(6) 6.
3 The Constrained Linear Thompson Sampling Approach
We begin by describing the COLTS framework. In the frequentist viewpoint, TS randomised method for bandits that, at each i, perturbs an estimate of the unknown objective, in a manner sensitive to the historical information Di-1, and then picks actions by optimising this perturbed objective.
Naturally, then, will perturb the estimates 0,, t,, for which (n, H) ~ μ4, independent of -,,1, we define the perturbed parameters
a law μ on R lxd Rmxd For
((,, = 0, + wo(0m and (H, &. + W,
1/2 The Notice that these perturbations are aligned with 5h-1 only via the scaling by wi (o)V, underlying thesis of the COLTS approach is that for well-chosen μ4, the action
a(n, H,t) t) = arg maax(((n,) t) a o t)a S a, a.,aEA. A),
(3)
if it exists, is good choice to play, in that it is either underexplored, we treat arg max as a point function that picks any one optimal solution). Two major issues arise with this view. Firstly, the set A n ( t)a at) may be empty for certain H, meaning a(1, H, t) need not exist, Secondly, hard enforcement, a(1) H, t) need not actually be safe, and so cannot directly be used. Thus, the main questions are 1) what a we should use, 2) how we should augment the COLTS principle to design effective algorithms, and 3) how we can analyse these algorithms to prove effectiveness. These questions occupy the of this paper.
nearly safe and optimal (N.B.
B-Concentration. Before proceeding, we note that very large 1), H. can wash out all of the signal in i, and é, We introduce the following definition to quantifiably limit their size.
Definition 2. Let B (0, 1] + Rz0 be nonincreasing map. A law μ on I 1xd x Rm is said to satisfy B-concentration Vf E (0, 1 μ (fmax([|v]]- max:e[1.m] | ID) 2 B(x))) S.
As an example, each 7), H' were normal, then B{g) = v log((m + 1)/E). Henceforth, we will assume that μ satisfies B-connentratioon for some map B, and define quantities in terms of this B. This condition has the following useful consequence ($F)).
Lemma 3. Let ö, == 6/t(t+1), 1), and for B (0, R2 let B, = 1 max(1,,(6.)) Let
My(a) == (,w)
Let Umn HO} be sequence of perturbation noise such that at each I, (m,, H₂) ~ p independently of 5t-1- If satisfies B-concentration, then with probability at least 1 - 25,
Vt a, max (ICO. Ö(n. t)) al. max (( t))
- }.)aa) s Ma).)
Further, Eier Me(a)) S. BTWT(() (6) O O(V S BTÖ(V
4 Hard Constraint Enforcement via Scaling-COLTS
We turn to the problem of hard constraint en- forcement of minimising Ryr while ensuring that w.h.p., Sy = O, using a safe action asae such that I((asate) > We will extend COLTS with 'scal- ing heuristic,' that was first proposed in the context of SLBs by Hutchinson et al. [HTA24], who used it to design (inefficent) method ROFUL.
Algorithm 1 Scaling- (S-COLTS(H4,)) 8))
1: Input: asate, To E [T (a (((sst)))
2: for t= 1, 2... do
3: Draw (m), H.) μ
4:
if Me(asaee) > To/3 OR a(m, H.,
does not exist then
5:
Q: & asafe-
To begin, our method, S-COLTS, draws noise (n, H,) μ4, and computes the preliminary ac- tion := a(T;; Hr, l). assuming for now that this exists. As argued in $3. this action by either has lew-regret, is informative. Of course, this b,
6:
else
7:
b a(n, H,,
8:
Compute a, as (4).
9:
Play at, observe RG, St, update f4.-
need not be safe-we only know via Lemma that b. S Mc(b.) -nd so cannot be used

---

for hard enforcement. However, the action asafe is safe, with a large slack of at least ((aaae)) ) in each constraint. Via linearity, and the convexity of A, this means we can scale back b, towards asae to find a safe action, i.e., play a, of the form (1 Mt Pt.)0sate + peb, for some Pt [0. 1]. If pt is not too small, this maintains fidelity with respect to the informative direction by, while retaining safety.
Ensuring that 1 Pt is small relies on the margin ((asafe) of Osafe Indeed, notice that
(pbz + (1 - p)aste S ar + (pMa(bi) - (1 p))
and so there a safe P satisfying 1 - 2 M,(b:))/T(aata Of course, we do not know [( ). and cannot directly set Pt this way. However, by repeatedly playing Asafe (and using adaptive bounds), we can find a value Ty such that Tn E (T(ssefe) )/2. (asaee) ) using only ((T(aa)))) rounds. We give account of this method in $H.1, and henceforth just assume that we know such To-
Define 0. (m]..) and de t), We observe that if Mclassfe) S To/3, then, whp.
Pc S Uuaafe Me(Asafe)lm a (T'(asate) 1o/3)1m S 20(00m)/331
Thus, the constraints induced by Te are feasible (since asafe meets them), and so, critically for S-COLTS, the action by = a(m, He. t) exists. To play safe action, we set
a₁ ae(p)), where (p)) (1 p)a pbe, and
(4)
Pt = max [0, 1| (,) + ( S sa..
Importantly, Mt (Oaate) S To/3 yields 1 - Pt. S (be (T (asate) (SH), giving similar fidelity to b as if we knew T (( If (a(Ssate) To/3, we simply play Asafe-
The only design variable left undetermined is the perturbation law μ.. In 1, we first describe an unsaturation condition on f that induces low regret. Then, in $4.2, we give general construction of unsaturated laws. This operationalises the S-COLTS design, with regret bounds described in $4.3.
4.1 Analysis of S-COLTS
Since safety of S-COLTT directly follows from (4), we main challenge is controlling regret. In this section, we show that js satisfies an unsaturation condition, then S-COLTS incurs ((VT) regret. We will being by describing this unsaturation condition, and show how this is operationalised via novel look-back analysis of TS, which first presented without unknown constraints for the sake of clarity. Next we will discuss how this is augmented via scaling strategy to handle the shifting constraints in S-COLTS.
Unsaturation. Following [AG13], say that an action is unsaturated time if ((a) Mc(a). The core idea is that playing unsaturated actions either informative (large (a)). or low-regret (small (a)). Thus, with large Pt, every time the proposed is unsaturated, the learning process should make progress. Of course, this by will not always be unsaturated due to the perturbations in O,, pr. but it suffices for by to be unsaturated often enough. This motivates the following definition.
Definition 4. Let μ be B-concentrated law. Define the unsaturation event at time t as Ur(6)= {(n, H) a(n, H, 1) exists, and A(a(n, H,)) I Me(a(n, H,))). For E (0, 1J, we say that y-satisfies x-unsaturation for all t such that 8/(t(t + 1)) S x/2. () Con, (5) 2 (x/2)_ccon()))
In words, x-unsaturation means that at all i, given the past, b, is unsaturated with chance at least x/2.
4.1.1 Using Unsaturation: The Look-Back method without Unknown Constraints
For the sake of clarity, let us first consider how we can analyze ts without unknown constraints using this unsaturation definition. We shall do so via novel bbckk technique, which operationalises commonly supplied intuition for how TS works [e.g.AL17) AL17], and thus offers a more intuitive argument than the prior approach based upon studying the minimum-now norm unsaturated action [AG13].
Without unknown constraints, S-COLTS collapses to standard TS by setting a, b, (and will only use de below). Now, suppose o, were always unsaturated. Then observe that we get the bound
Rr Σ A(ar) < Σ M((a.) = o dTT).
5

---

However, in reality, a is often not unsaturated. To handle this, we will 'look back' at the last time < that a, was unsaturated. Specifically, define
T(t) == isf < t: A(a.) S M,(a,),, 1
This r(t) is the last with an unsaturated ag. and so, per the unsaturation heuristic, the last time the learner made progress. The main idea of looking back is to control A(a;) in terms of the information available at rtt) to exploit the 'steady' learning at such time steps. To this end, we will bound ((a)) in terms of (r(1)- To lower density of notation, we will write r instead of r(t) unless necessary.
Introducing a., Notice that since A(a) = 0_ (a= a), we can introduce into the control thus: (ar) = (a,) + 0_ (a, - 02) S M, + 0, (a, - at), where we used the unsaturation of a,- Bounding this requires us control the second term. For this, we use the resource that or optimises 0., and so 0r (a, at) S 0. Thus,
(aa)) S Ma+a+) + (0_ - 0e) T (a, a.) + 02 (at aa)).
where the third term can be dropped. Further note that the second term decomposes as two terms of the form (0. 0.) a, which precisely the object controlled in Lemma 3. Using this gives (ax)) I (M((ar) + (aaa)) + Me(a)).
(5)
Now, the final term accumulates to Σ (ax)). which by Lemma is Ö(VT). Thus, to control regret, we only need bound the accumulation of these look back terms E, M,(o) (o)()) + Mc(ar(().
Controlling Look-Back Accumulation. Our main resource for controlling this is x-unsaturation. Consider just the first term De M-(o) (a-(1)) (the second follows similarly), and let Ti S T2 S ... denote the (stopping) times at which ag was unsaturated. Then notice that
Σ (r(o)(ar()) Σ Macol(ar1)) EST
Σ Mr(o((rro) + +... E(T, - -T. (on, T=
+
121
where we set To = 0 and Mo(.) = 1 for consistency. But notice that due to the frequency of unsaturation, each T, T;-1
1 is only O(log(T)/x) with high probability. This suggests the bound
E Mrco)(arco) < 01x Mr, s Ō(x=))
Mi(aa) = Ō(x (inn))==OxBBBBe--- BIV all
Σ
where in the second inequality, we used the nonnegativity of M, Using a more refined martingale analysis described in $H.3, this yields the following key structural tool for the look-back method.
Lemma 5. If μ. satisffes x-unsaturation, then with probability at least 1 - 5, for all T 2 /2/x.
Σ Mr(o(arto) + M,((r())) S 110Bywr (8r) x² -logg(18) + Σ Iadlly
Since (Lemma 3) WT Σ |oalll.-- = (dd (T), this results in a proof that TS with x xunsatuurtedd perturbation law admits the bound R = - with no unknown constraints.
4.1.2 Looking Back with Unknown Constraints: The Analysis of S-COLTS
In the above analysis, we critically used the optimality of the action for the perturbed program, and the frequency of unsaturation. Coming back to S-COLTS, let us recall that our action the convex combination pab. + (1 - Px) Paaae j b, and that unsaturation means that A(b:) S (b.).
Handling the Scaling, Our first course of action, then, is to observe via linearity that
Aaa)) = (b.) + (1 Pt) Px)A((C (assate;
and regret control requires to bound the of these across t. Notice that even if by were always unsaturated, we would only get the bound > (b.) + x1 Pt) ( ((aste)) and nominally, neither term is controlled by Σ Me(a.). We handle this by the following, which relies on the largeness of pt- Lemma 6. At any such that M Mc(Ossfe) S To/3, holds that
(1 pt) pt) (Usste) (a.) and (b.) S (a.)..).
This follows from more detailed result, Lemma 20 in $H.2. Observe consequence that (1 At) I ((A(aaate)
(a()a) is cell-controlled (and, of course, A ( (a((at)t)) = (asste)) 1). So, the main object of study Σ p.b..)).

---

Looking-Back with Unknown Constraints. We slightly adjust the look-back time so that (b,,(6,) & (a,((ar) holds:
br(()
T(t) := {n (s < t (asie))e I To/3. 3, (b,)) S (ba))
Following $4.1.1 directly suggests that we should proceed via pr)(b:) S (b+))))) (0. - 0,) (b, - b,) + 0. (b, be)). However, major issue emerges here; notice that b, optimises the constrained program max (0, : Φ,a S ax. However, the look-back action b, only satisfies the constraint { S a), and so b, may not be feasible for the perturbed constraints time t. This prevents us from simply dropping the final term above, and breaks the analysis.
S+(0)
Figure 1; A schematic of the analysis. S, := {#.0 S at} are the perturbed (red box) is mix-
feasible regions. ture be and agate (black box). b-(0) is infeasibe for S., and we instead mix it with asaee to produce b. E Se (blue box).
We address this by using essentially the same idea as that under- lying s- S-COLTS itself: move by towards Osafe to find a point that is feasible for 2, but has regret similar to by. Concretely, we set
by == or + (1 - where r-+t := Too(To + 3,, 3.,
Importantly, notice that σ- essentially acts the same way as pz! Indeed, part of our analysis in $H.2 essentially shows that Lemma 6 holds with o, (6,) and (1 0+ instead of pr.
In any case, the main point is thus: by two applications of Lemma 3, L,b, S a = D,b,.1 S a.
So, instead of b,, our look-back analysis will focus on b Applying this gives
(bb( S (.) + Pe 0.) (b-- - by) + peO, (b - be),
where the final term negative, and the middle term is bounded by Mt (b + 2Ma(at). For the first term, notice by linearity and unsaturation of b, that
A(b_.) = -0.,;\(b))) + (1 - (Qaat))) S or
+ (1 o+ - (asatee)
This leaves us with bound in terms of ar-+e and (b,),, the core resource for which is the observation that Tr acts essentially as pr, which lets write, e.g., that -r (b,) S (a.). For the sake of brevity, we leave this analysis to $H.2, and only state the main resulting bound. Lemma 7. Let Mo(a) == 1. If μ is B-concentrated, then with probability least 35.
Vt (asassfe S To/3, (a.) I 6R( (M; + My + M)(t)(
Importantly notice that the bound is in terms of ar(t), instead of b-(1)- Of course, this puts us in the same situation as in (5) in 1..1.1. I. but with an extra 6R (asaee) factor in the bound. Via Lemma 5, and analysis of the number of times (a > oo can hold, this yields bound of the form Rr Ö(x (O(x-RR(asst BT Srrve VTTT).
Novelty Relative to Prior Work. As previously mentioned, our look-back approach is a novel, and more intuitive. modification of the seminal analysis of unconstrained ts by Agrawal and Goyal [AG12; AG13J. More importantly, with unknown constraints, we had to handle fluctuating constraint sets: our look-back analysis broke since b, could be infeasible for t which we addressed by scaling b,. This issue would also break an analysis based directly on the approach of [AG12]. The novelty relative to [HTA24] is similar: like by. a, may also be infeasible for 4., which breaks their analysis.
4.2 The Coupled Noise Design
$4.1 shows that X-unsaturation yields control on the regret. To operationalise this, we need to design well-concentrated laws with good unsaturation. In single-objective TS, unsaturation is enabled via
anticoncentration of the 77s, and good balance is attained by, e.g., (nif(v/ddd)) or A (0. Ia).
A natural guess with unknown constraints is to sample both 17 and each row of H from such a law. However, the unsaturation rate under such design is difficult to control well. The main issue arises from maintaining feasibility with respect to all m constraints under perturbation, since each such perturbation gets independent shot at shaving away some unsaturated actions, suggesting that x decays as e -m(m) and indeed, experimentally, increase in mn may lead to at least polynomial decay in the unsaturated rate with such independent noise (see $J..3.. We sidestep this issue by coupling the perturbations of the reward and constraints, encapsulated below.
7

---

Lemma 8. Let B E {(0, 1] + R2ot be map, and p E (0, 1]. Let v be law on Rdx such that Yu R.d p((: <3v 2 |uil) 2 ps and VE E (0, 1], (({s: II| > (5))))& Let y be the law of ( Our proof of this lemma, executed in $G, is based upon analysing the local optimism event at Og:
(
v. Then μ p-unsaturated and B-concentrated.
Lo) = (17, H) A(n, 1) a. 2 0_ a.. (H, (H.t)a. S <a).
Notice that L, demands that the perturbation such that o, remains feasible with respect to Q., and its value at Og increases beyond 0 a., in other words, the perturbed program is optimistic at a.. Our proof first directly analyses a, under the perturbations to show that i... frequent local optimism. This enables an argument due to [AG13]: since a, is unsaturated (A(a.) = 0), and, w.h.p. the perturbed reward of any saturated action is dominated by that of a, follows that (6) (o), yielding lower bounds on p(U)(6)).
(o) 2 con,
We note that the conditions of Lemma are the same those used for unconstrained linear TS in prior work [AGI3; AL17J, and so this generic result extends this unconstrained guarantee to the constrained setting. In our bounds, we will set μ to be the law induced by the coupled design with Unif (vd33d) which is 0. 1--usatturtted and B-concentrated for B{{) = /3d (SG.1).
4.3 Regret Bounds for S-COLTS
With the pieces in place, we state and discuss our main result, which is formally proved in $H. Theorem 9. Let p. be the law induced by Unif( (v3d54) under the coupled noise design. Then S-COLTS(J, 8/3) ensures that with probability at least 1 - for all T, it holds that
Sr = 0 and RT R(assfe) Ö(V d d' (olgmm//8)
Comparison Regret Bounds Prior Results. As noted $1.1, prior inefficient hard en- forcement SLB methods attain regret ((R(usaaee /dTT), while efficient methods attain regret Ö(R(asate) ) Vd Our results above recover the latter bounds. The loss of vdl relative to in- efficient methods is expected since appears in all known efficient linear bandit methods (without or without unknown constraints). The ((V)) dependence is necessary (even with instance-specific information) [GCS24] as is the additive A ((osse)/T((sat)) term [PGBJ21]. Thus, S-COLTS recovers previously known guarantees using sampling rather than frequentist bounds.
Computational Aspects. An advantage of S-COLTS is that only optimises over linear constraints (beyond those of A), instead of SOC constraints of the form (Vi E [1 m)] + ( ly, S a'} imposed by prior methods. While convex, these m SOC constraints can have palpable practical slowdown on the time needed for optimisation, especially as m grows (over A = [0. 1/vd]" with the modest m we see a 5x speedup. and with d 2, m 100, a 18x speedup. in $6). In particular, when A is polyhedron, S-COLTS can be implemented with just linear programming.
We explicitly note that S-COLTS is efficient for convex A. The dominating step is the computation of br, which can be carried out to an approximation of 1/t with no loss in Theorem 9. With, say, interior point methods, this needs ((LP (og((() computation at round t, where LP the computation needed to optimise m a &a a, a E A} to constant error [BV04].
Practical Choice of Noise. has long been understood that while existing theoretical techniques for analysing linear TS need large noise (with B({) ((vd) d)), in practice much smaller noise (e.g., USd with B(g)= (11) typically retains a large enough rate of unsaturation, and significantly improve regret (although not in the worst-case [HB20J). Our practical recommendation is to indeed use such a small noise, which we find to be effective in simulations ($6). We underscore that no matter the noise used, the risk guarantee for S-COLTS is maintained.
5 Soft Constraint Enforcement with Resampling-COLiT
Given an action Osafe with positive safety margin, S-COLTS ensures strong safety and good regret. This section studies scenarios where we do not know such an @safe. In this case, it is impossible to ensure that Sx 0, and we instead show ((VT) bounds on Sr. following prior work [GCS24]. S S-COLTS uses forced exploration of asafe to ensure the feasibility of perturbed programs. However, the local optimism underlying our proof of Lemma 8 gives different way to achieve this. Indeed, the

---

event (o) of (6) implies that a, is feasible, and so a(1, H. t) exists. Thus, (f) 2 x, then we can just resample the noise (l)g(t)) times and end up with feasibility. In fact, even more true: since 0 a, 2 0__ a, under L,, resampling (log(t)) times ensures not only feasibility, but also optimism of the 'best' perturbed optimum. The R-COLTS method is based on this observation.
Concretely, given a resampling parameter r, at time R-COLTS samples 1 + [r log 1((+ indepen- dent (1) H) from μt, optimises the perturbed program induced by each, and picks the optimum of the one with largest value as de (and sets it = a--1 if all programs were infeasible). We let 0r denote the objective of this 'winning' perturbed program: in the notation of Alg. 2, 6 = ((ni.,. t). The main idea is captured in the following simple lemma.
(o). for every t. If 2 π -1, then with probability at least 1 - 2ò, at all t, the actions or and perturbed objective O, selected by R- R-COLTS(U, r, 5) are optimistic, i.e., they satisfy that 02 a, S 02 at
Lemma 10. Let E (0, 11, and suppose μ satisfies C (8)
The 'local optimism condition" on j above is reminiscent of the global optimism condition of Abeille & Lazaric [AL17]. and indeed the
Algorithm 2 PResampling-oous
(R-COLTS(U, r, r))
1: Input: 14, 6, 'resampling order' r & N
same result holds under global optimism as-
2: Initialise: I, <- 1 [r log (((+)//5)
sumption with unknown constraints. However,
3: for == 1,2,... do
the analysis in this prior work does not extend to unknown constraints due to its reliance of convexity ($1.1), and resampling bypasses this issue. See $D for more details.
for 1, 1.2....,Je do
5:
Draw (Tr,,, Hi.e) ~ v..
if a (Th,,, Hi,,, 8) exists then
7:
K(i,t) 1) <- 0TKK, 1) Ta(na, Heg,
Lemma 10 enables the use of standard opti- mism based regret analyses [e.g. APS11]. By operationalising the condition μ via the coupled design in $4.2, we show
else
9:
K(i, f) x- -00
10:
if max K K(i,t) t) -00 then
11:
a₂ + Qt-1.
Theorem 11. If μ is the law induced by Qnis(v3ds'' under the coupled design of Lemma& 8, then with probability al least
12:
else
13:
i,,1 -- arg max, K(i, t), a, almin,, H t).
14:
R-COLTS(J,, 4, 5/2) ensures that for all T,
15:
0, + U(Tb.,, t).
max(S,, Ry, Ö(V + d2T (og(m/0))
16:
Play dts observe Re, St, update 5)
Instance- Indeeendent Regret Bound. The above result limits both regret and risk to Ö(v T).. with no restance-specifie terms, unlike R(asate) in S-COLTS. In particular, this bound holds even max, ((a) = 0, i.e., the problem is marginally feasible. This result is directly comparable to the O(V bound on both regret and risk under the DOSS method [GCS24), and loses a vd-factor relative to this, a loss that appears in all known efficient linear bandit methods.
Computational Costs. R-COLTS with μ above solves 4log(t? (t² /8) optimisations of 0, a over (Φ.a S a) 1 n A. Again, Theorem 11 is resilient to approximation of, say, 1/t, and so this takes O(LP. log t) computation per round, factor of log(t) slower than S-COLTS, but still efficient in the practical regime of log /5) = (poly(d, m)). The main point of comparison, however, is DOSS, log(t) computation per round. R-COLTS is practically much faster even for small domains with long horizons-for instance, with T = 1/8 10t0, 4 log((²/5) < (2d)a+1 for all d 2 4, m > 2.
which instead needs to solve m such programs, and uses (2d)m+IL
Relationship to Posterior Quantile Indices and Safe MABs. The resampling approach executed in R-COLTS is closely related to the posterior-quantie approach of the BAYESUCB method [KCG12], wherein it is proposed to use a quantile of the arm posteriors as a reward index instead of frequentist upper confidence bound. Indeed, we can compute such quantile in a randomised way by taking many samples from the posterior of each arm, and then picking the largest of the samples as the reward index. Most pertinently, this approach was proposed for safe multi-armes' bandits [CGS22], wherein this posterior quantile index is used to decide on the 'plausible safety' of putative actions. The same work further argued that the usual single-sample TS cannot obtain sublinear regret in safe MABs. The R-COLTS approach can be viewed as an efficient extension of this principle to linear bandits with continuum actions, and differs by directly optimising the indices under each draw, and then picking the largest, instead of performing an untenable per-arm posterior quantile computation. R-COLTS Without Resampling. Given the lack of a safe action to play, one cannot direct establish the feasibility of the perturbed programs by contracting the confidence radius of a single action as in S-COLTS. However, if we introduce small amount of 'flat' exploration whenever V, is 'small', then
9

---

this ensures that any a with r(a)= > 0 will eventually be strictly feasible under perturbations. If such a exists, we only need single noise draw to attain feasibility, and can bootstrap the scaling analysis of S-COLTT to show bounds. We term this method Exxloratory-COOIT and analyse in $1.2. This results in the following soft-enforcement guarantee.
or F-COITS, and specify
Theorem 12. If p. is the law induced by Unif(v3ds" under the coupled noise design, then the E-COLTS 5/3) method of Algorithum 3 ensures that with probability at least 1 ó, for all T,
ST -r=Ō(V + min Ō d LI
(R(a)O(VET)) + 0 (6(dd)aa) da|all
k²)( and R a:I(a)>0
minn
(Taaaa
where K. is constant depending the geometry of A.
Relative to R-COLTS, the above guarantees are instance- instance-dependent, dependent, and are only nontrivial max, r(a) nonzero. The advantage of E-COLTS lies in its reduced computation. Comparing to S-COLTS, the above loses the strong Sy = 0 safety, but improves regret by adapting the best possible R(a).
i.e., the Slater parameter of the optimisation problem induced by 02, t., A is
6 Simulations
We give a brief summary of our simulations, leaving most details, and well as deeper investigation of our methods to $J. In all cases, we utilise the coupled noise design, driven with the (uninflated) noise Unif (0.5 Sr), in accordance with the discussion in $4. The same noise is used for SAFE-LTS.
Resampling tradeoff in R-COLTS. For d = 9, we optimise 0_ = 1a/ Vd over A = [0. 1/.1/vdd with a 9 x 9 constraint matrix (i.e., m 9). In this case, the action 0 is feasible, and so R-COLTS without any resampling is effective. Since a 0 has nontrivial safety margin, R- R-COLTS, even without resampling, is
Table 2: Ry and Sy at T 5- 10 for R-COLTS
with 1, samples per round (100 trials). Samples
RT
ST
1
658 + 170
2891 + 171
2 397 + 116
3126 + 137
3 301 + 102
3266 + 172
effective for this problem. This borne out in Table 2,
which shows regret and risk at the terminal time T'. We see that resampling slightly worsens risk, but significantly improves regret (although with diminishing returns). Further, both regret and risk are far below the v TT scale expected from our bounds. We note that while single iteration of R-COLTS takes Ims, since (2d)m+ > 10 this would take years for DOSS, and we do not implement In any case, note that the computational advantage of R- R-COLTS is extremely strong.
Significant Computational A Advantage and Regret Parity/Improvement of S-COLTS. We compare s S-COTTS with the hard enforcement method SAFE-LTS [MAAT21], which has been shown to match the performance of alternate such methods, while being faster. Both methods are 9 instance above, with Osafe = 0. As expected, both never play unsafe actions. Further (Fig. 2, left), S-COLTS achieves an improvement in regret relative SAFE-LTS, while reducing wall-clock time by a 5. To gain a deeper understanding of S-COLTS'S computational advantage, we investigate the same with growing m E {1, 10, 20..... 100} constraints for simple for the setup). In this problem, the benefit is even starker (Fig. 2, right). For m 2 10, the regret of 4x larger than that of S-COLTS, i.c., the latter has much better regret (m has wide confidence bands for the ratio, but mean 1.5) Further, the computational costs of SAFE-LTS relative to S S-COLTS grow roughly linearly, starting from 1.3x for m > 18x at m 100.
the d =
setting (see $
SAFE-LTS
SCOLTS
Regeet
SAFE-LIT
LSS relativve to COLTS (100 cum)
natio of Th- and Computational Core
Regnet, RR, over runs
20
Time.
Number
(ms)
Figure 2: COMPUTATIONAL AND REGRET COMPARISONS OF S-COLTS AND SAFE-LTS. Left. Regret traces in the d = 9 instance (dashed lines are one-sigma error bars); S-COLTS mildly improves regret, and is 5x faster. Right. Relative performance as m is varied in the d 2 instance. The speedup of s- S-COLTS grows linearly with m from 1.3x to > 18x. Further, for m 2 10, the regret of S-COLTS is 2-3x smaller than that of SAFE-LTS
10

---

Acknowledgements
The authors would like thank Aldo Pacchiano for helpful discussions. This research was supported by the Army Research Office Grant 1991211110246 AFRL Grant (A8650--2-C1039 and the National Science Foundation grants CPS-2317079, CCF-2007350, and CCF-1955981.
References
[AAT19]
Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. "Linear stochastic bandits under safety constraints". In: arXiv preprint arXiv:/908.055: 1908.05814 (2019) (cit. on pp. 1-3, 22).
[AD14]
Shipra Agrawal and Nikhil Devanur. "Bandits with concave rewards and convex knap- sacks". In: Proceedings of the fifteenth ACM conference on Economics and computation. 2014, pp. 989-1006 (cit. on p. 21).
[AD16]
Shipra Agrawal and Nikhil Devanur. "Linear contextual bandits with knapsacks". In: Advances in Neural Information Processing Systems 29 (2016), pp. 3450-3458 (cit. on p. 3).
[AG12]
Shipra Agrawal and Navin Goyal. "Thompson Sampling for Contextual Bandits with Linear Payoffs". In: arXiv preprint arXiv:/209.33 (09.3352 version (2012). Note: This version of the preprint, dated to 2014, improves upon the version of the paper published ICML 2013, showing V regret instead of V d Most of the text cites the ICML version, but attributes this stronger bound to it. This version is cited only to refer to specific details in this paper. (cit. on p. 7).
[AG13]
Shipra Agrawal and Navin Goyal. "Thompson sampling for contextual bandits with lin- car payoffs". In: International conference machine learning. PMLR. 2013, pp. 127- 135 (cit. on pp. 2, 3, 5, 7, 8, 22, 24).
[AK08]
Baruch Awerbuch and Robert Kleinberg. "Online linear optimization and adaptive routing". In: Journal of Computer and System Sciences 74.1 (2008), pp. 97-114 (cit. on p. 38).
[AKR21]
Maryam Aziz, Emilie Kaufmann, and Karelle Riviere. "On multi-armed bandit designs for dose-finding trials". In: Journal of Machine Learning Research 22. (2021), pp. 1-38 (cit. on pp. 1,)...
[AL17]
Mare Abeille and Alessandro Lazaric. "Linear Thompson sampling revisited". In: Electronic Journal of Statistics 11.2 (2017), pp. 5165-5197. DOI: 10. /214/17 EJS13411I. URL.: htttps://don org/ 10. 10t1/121411111 EJJJ1341S (cit. on pp. 2, 3, 8, 9, 22-24, 47).
[AML24]
Amirhossein Afsharrad, Ahmadreza Moradipari, and Sanjay Lall. "Convex methods for constrained linear bandits". In: 2024 European Control Conference (ECC). IEEE.
2024, pp. 2111-2118 (cit. on p. 22).
[APSII]
Yasin Abbasi- Abbasi-Yadkori, Yadkori, Dávid Pál, and Csaba Szepesvári. "Improved algorithms for linear stochastic bandits". In: Advances in neural information processing systems 24 (2011), pp. 2312-2320 (cit. on pp. 3, 25)..
[BGCG23]
Debangshu Banerjee, Avishek Ghosh, Sayak Ray Chowdhury, and Aditya Gopalan. "Exploration linear bandits with rich action sets and its implications for inference". In: International Conference on Artificial Intelligence and Statistics. PMLR. 2023, pp. 8233-8262 (cit. on p. 39).
[BKS13]
Ashwinkumar Badanidiyuru. Robert Kleinberg, and Aleksandrs Slivkins. "Bandits with knapsacks". In: 2013 IEFF 54th Annual Symposium on Foundations of Computer Science. IEFF. 2013, pp. 207-216 (cit. pp. 3, 21).
[Bot+22]
Alessandro Bottero, Carlos Luis, Julia Vinogradska, Felix Berkenkamp, and Jan R Peters. Infformation-thooreee safe exploration with Gaussian processes". In: Advances in Neural Information Processing Systems 35 (2022), pp. 30707-30719 (cit. on p. 21). Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004 (cit. on 8).
[BV04]
[Cam+22]
Romain Camilleri, Andrew Wagenmaker, Jamie Morgenstern, Lalit Jain, and Kevin Jamieson. "Active Learning with Safety Constraints". In: arXiv preprint arXiv: 11183 (2022) (cit. o.p.pn. 21).

---

[CGS22]
Tianrui Chen, Aditya Gangrade, and Venkatesh Saligrama. "Strategies for safe multi- armed bandits with logarithmic regret and risk". In: International Conference on Machine Learning. PMLR. 2022, pp. 3123-3148 (cit. on pp. 3, 3).
[Cho+24] Alex Chohlas- Woodd Madison Coots, Henry Zhu, Emma Brunskill, and Sharad Goel. "Learning to Be Fair: A Consequentialist Approach to Equitable Decision Making". In: Management Science (2024) (cit. on pp. 1, 21).
[CVA20]
Alexandra Carpentier, Claire Vernade, and Yasin Yadaki. "The elliptical poten- tial lemma revisited". In: arXiv preprint arXiv:2010.1018: (2020) (cit. on p. 25). Varsha Dani, Thomas P Hayes, and Sham M Kakade. "Stochastic linear optimization under bandit feedback", In: Conference on Learning Theory. 2008 (cit. pp. 21, 22, 38).
[DHK08]
[FLZY22]
Liang Feng, Wei Liu, Zhenyu Zhang, and Haoyang Yu.
Reinforcement Learning for Real-Time Voltage Control". In: arXiv preprint arXiv:2203. 12345 (2022). URL: https : arxiv org/ / abs / 2203. 12345 (cit.
on pp. 11).
[GCS24]
Aditya Gangrade, Tianrui Chen, and Venkatesh Saligrama. "Safe Linear Bandits over Unknown Polytopes". In: The Thirty Seventh Annual Conference on Learning Theory. PMLR. 2024, pp. 1755-1795 (cit. on pp. 1-3, 8, 9, 22, 39, 43).
[GGSS24]
Aditya Gangrade, Aditya Gopalan, Venkatesh Saligrama, and Clayton Scott. "Testing the Feasibility of Linear Programs with Bandit Feedback". In: Proceedings of the 41st International Conference on Machine Learning. 2024 (cit. on p. 23).
[GPSS25]
Aditya Gangrade. Aldo Pacchiano, Clayton Scott, and Venkatesh Saligrama. "Feasible Action Search for Bandit Linear Programs via Thompson Sampling". In: International Conference on Machine Learning. 2025 (cit. on p. 23).
[HB20]
Nima Hamidi and Mohsen Bayati. "On worst-case regret of linear thompson sampling". In: arXiv preprint arXiv:2006.06777 472 (2020) (cit. on p. 8).
[HRMS21] Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. "Time-uniform, nonparametric, nonasymptotic confidence sequences". In: The Annals of Statistics 49.2 29.2 (2021) (cit. on 28).
[HTA23] Spencer Hutchinson, Berkay Turan, and Mahnoosh Alizadeh. "The Impact of the Geometric Properties of the Constraint Set Safe Optimization with Bandit Feedback". In: Learning for Dynamics and Control Conference. PMLR. 2023, pp. 497-508 (cit. on p. 2).
[HTA24]
Spencer Hutchinson, Berkay Turan, and Mahnoosh Alizadeh. "Directional optimism for safe linear bandits". In: International Conference Artificial Intelligence and Statistics. PMLR. 2024, pp. 658-6666 666 (cit. on pp. 2-4, 7, 22).
[KCG12] Emilic Kaufmann, Olivier Cappé, and Aurélien Garivier. "On Bayesian upper confi- dence bounds for bandit problems". In: Artificial intelligence and statisties. PMLR. 2012, pp. 592-600 (cit. on p. 9).
[KS19]
Julian Katz-Samuels and Clayton Scott. "Top feasible arm identification". In: The 22nd International Conference on Artificial Intelligence and Statistics. PMLR. 2019, pp. 1593-1601 (cit. on p. 21).
[LM00]
Beatrice Laurent and Pascal Massart. "Adaptive estimation of a quadratic functional by model selection". In: Annals of statistics (2000), pp. 1302-1338 (cit. on p. 27). Ahmadreza Moradipari, Sanae Amani, Mahnoosh Alizadeh, and Christos Thram- poulidis. "Safe linear thompson sampling with side information". In: IEEE Transactions on Signal Processing (2021) (cit. on pp. 1-3, 10, 22, 43).
[MAAT21]
[PGB24]
Aldo Pacchiano, Mohammad Ghavamzadeh, and Peter Bartlett "Contextual Bandits with Stage- wise Constraints". In: arXiv preprint arXiv:2401.0800 (2024) (cit. on pp. 1-3, 22, 24. 25).
[PGBJ21]
Aldo Pacchiano. Mohammad Ghavamzadeh, Peter Bartlett, and Heinrich Jiang. "Stochastic bandits with linear constraints". In: International Conference on Artifi- cial Intelligence and Statistics. PMLR. 2021, pp. 2827-2835 (cit. on pp. 2, 3, 8, 22, 39).
[PV91]
Panos M Pardalos and Stephen A Vavasis. "Quadratic programming with one negative eigenvalue NP-hard". In: Journal of Global optimization 1.1 (1991), pp. 15-22 (cit. p. 22).
12

---

[Sah74]
Sartaj Sahni. "Computationally related problems". In: SIAM Journal on computing 3.4 (1974), pp. 262-279 (cit. on p. 22).
[SGBKI5]
Yanan Sui, Alkis Gotovos, Joel Burdick, and Andreas Krause. "Safe exploration for op- timization with Gaussian processes". In: International conference machine learning. PMLR. 2015, pp. 997-1005 (cit. on 21).
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: the abstract and introduction specify, propose and analyse algorithms for SLBs based on the COLTS framework.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Theoretical limitations of results, and their context, is extensively discussed, along with open problems specified (latter mostly in the appendix).
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
13

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Complete proofs available in the appendix. We also specify the main technical ideas in the main text.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: the algorithms and tools used, the computational resources needed, and the settings investigated, are all explicitly described in ŞJ
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
14

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: the methods implemented use standard estimates in bandits, along with library linear programming routines. We believe that this is easy implement.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/ public/gen /wwe//ggg/e///eeeeeeeeeee httg///ds//oeeuubbeeeee SorddeeubmsssioPPoo
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /nips. cctpublic// wwwc///wg////eeeeeeeeecee /ewdde//Coeeeuuiiiee wwweeessmmisiiooooooo
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: See $J
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
one-sigma eтror bars are reported throughout, except for iteration time mea- surement Fig. (which were recorded in bulk over 103 iterations for each methods), and for the event rate estimates in Fig. 3 and Fig. 7 (where we report 10th percentiles of integrated averages values (0, 1) over 100 runs, which are smaller than the mean minus one-sigma lower confidence bounds, and so better capture our focus for these values).
Justification:
15

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: ŞJ
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: stttps:/nneurppl http://uurris.ccppuplieeeeee httpppllic/hhihassiieeeeee
Answer: [Yes]
Justification: No data drawn from human subjects used in this research. The paper is theoretical, and focuses on developing algorithms for safe linear bandits. As such, societal impacts are related to downstream applications of this generic underlying method, and so are associated with work applying ours as a subroutine, rather than directly stemming from contributions.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics. If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
16

---

Question:
Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: discussed in the answer to the previous point, potential social impacts (positive or negative) would stem from downstream applications that use bandit linear programming routines that we have designed. We decline prognosticate such applications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: no such data models are released via this paper.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: the code was entirely written bythe authors. The sole data used the matrix & as specified in &J, which is accompanied by appropriate attribution in the same section.
17

---

Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: no new assets are released.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: we did not do this.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
18

---

Justification:
no research with human subjects crowdsourcing were employed.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
recognize that the procedures for this may vary significantly between institutions and locations, and ference, workshop, or preprint repository) and already published papers are allowed.
we expect authors adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs were not used in any part of the preparation of this paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: / /ttp///eerrr//eeeeee/eee/r wwt.oonfeeeeccs//222222222 for what should or should not be described.
19

---

A
Glossary
Symbol
Explanation
Expression/Comment
(0., Pa)
True objective/coostrrints
E [ Rax
Constraint level
R
A
Action domain
a.
Optimal action for (0., 4.)
arg max (0_ a : E $
sup
A, Φb $ aa)
(00,0) Φ)
Value function
-o (4a a nA
A(a)
Reward gap
0. (a. a)
[(a)
Safety margin
min. (ía b.a)')+ 1 (aaa/T((a)
R(a)
Gap-margin ratio
Estimation and Signal
9:-1
Historical filtration
See $2
8, 4
RLS-estimates of parameters
See $2
V,
Action second moment
Eeer aga See $2
wi (d)
Confidence radius
Cl C
Confidence sets for 0., +
Con Con
Consistency event time
{0. (.). 2 E (7)) M1Z1 Con
Overall consistency
COLTS in general
P (g. H)
Perturbation law Perturbation noise
Distribution on Rixd Raxd ~ j4, independently of 5t-1
((,,))
Pertrubed objective
0, + (6) 1/2 1/2
(HH.)
Perturbed constraint
4 wi (V) 1/2
B())
Tail bound on [|v]], max; ||
B,
Noise radius bound
max(1, B(6+)), where & = 611) Bauilally.- See (3)
Mi(a)
Perturbation scale at
ab, II.t)
Perturbed optimum
(,(
Unsaturation event
{(n H): Aaa(n H, H) Mi(a(n H, f]
X
Unsaturation
(,)
Local optimism event
(1. II) 01, 8) Ta a (1 a)
Local optimism rate
Coupled Noise Design
V
Baseline perturbation law Generic draw from / Tail bound for
Supported on Rdxx ~ v. independent of h
B
x|lss|| > B())) S E inf "(( u > ||]]]] 2
p
Anticoncentration parameter for v
(CT
1
Coupled noise induced hy v
i.c., draw ç, set = C and H = 1 1
S-COLTS
Ocato To
A priori given safe action Reference margin (see $H.1) for estimation) Perturbation noise at
Maasto > O. To [(aaate)/ 2 and To S T(a
mm. H.)
A, +.
Perturbed parameters at Preliminary action at time i (if exists)
0. 0(n,,)) t), 8. 5(H
b,
b, a(1): H1,,)
a(p)
p-mixture of b, and Asate Largest p with safe a(p) Look-back time
( = phi + p)asat
Pi
See (4); a: a(p()-
T(f)
$4. 1...2mm 7
E-COLTS
(Me, H.)
Perturbation noise draws at time f Goodness factor exploratory policy Number of exploration steps up to time f
(/h H.)
See $1.2
M4
2s Baay ddt
R-COLTS
r
Resampling parameter
T (na,, Ha.)
Number of resamplings at time ith draw of noise perturbation at time
T. = [r log(1/6)) 1. ~ μ independently
K(ū,t)
Value under perturbation
K ((((n.,,)) 1), D(H,,, 1)) arg max; k(i,t)
Best index time
a;
Action picked
0, = aTk... He..st)
0.
Objective for 1...
0, t).
20

---

B Examples of Real-World Domains where the Safe Linear Bandit Problem Applies
Table Mapping real domains to the bandit linear programming. all three cases the reward is linear in an unknown parameter vector 0., and the safety/fairness predicate is an unknown linear inequality P.a S a. Feedback noise in both rewards and constraints arises through environmental or individual fluctuations.
Domain (ref.)
Action E A C R
Reward 0.¹ noise
Constraints
Dose-finding
One-hot vector discrete dose levels Active/reactive power
0: = patient-level efficacy probability at dose
4 -txiicity of dose i; constraint
[AKR21]
so that P(toxic|doss S a
Voltage-constrained
4. -inearised network power-flow
6 locational marginal price vector
micro-grid
set-pon set-point [P, Q] T
imposing volta-e construints under variable demand
[FLZY22]
for each
Fair Reccommendation
$ encoding group attributes
Distribution over d items or policies
in A/B testing
61 revenue of item
and costs, constraints demand fair
[Cho+24]
exposure each group
C Further Discussion of Related Work
Distinction of Safe Bandits From BwK. BwK settings are concerned with aggregate cost metrics of the form Ar == max; (Σ a (_a,)' without the (-)+ nonlinearity in S [c.g. AD14; BKS13]. This simple change has drastic effect, in that BwK algorithms safe actions for some rounds, and then 'spend' it to gain high reward, without any net penalty in Ar- This is appropriate for modeling aggregate cost constraints (monetary/energylet c.), but is evidently inappropriate to model safety constraints where feasibility violation in any round cannot be offset by acting safely in another round. Notice that such behaviour is precluded by the ramp nonlinearity in Rr. Sy: playing too-conservatively does not decrease Sy, while any violation of constraints is accumulated, and similarly. playing suboptimally causes Ry to rise, but playing an over-aggressive action with negative (aa) does not reduce Rr.
'bank" violation by playing very
Pure Exploration in Safe Bandits. While our paper focuses controlling regret and risk, naturally the safe bandit problem can be studied in the pure-exploration sense. These are studied in both the 'soft enforcement' sense, in which case methods and return actions that are E-safe and E e-optimal [e.g., Cam+22; KS19), and the 'hard enforcement', wherein exploratory actions must be restricted to the feasible region [e.g.. SGBK15; Bot+22]
explore both within and outside the feasible region
More Details on Computational Costs of Prior Methods. Most frequentist confidence-set based hard enforcement methods pick actions by solving the program
a s.t. V0 Ct va S a.
BEC .aEA
Assuming, for simplicity, that asafe = 0, due to the structure of the confidence sets the above constraint translates to
[1 E m), aça + lal S a.
Notice that this constitutes m different second-org -odder conic constraints. In fact, as discussed in $1.2, we expect V.-1 to have condition number scaling as 1(t1/4), which adds further computational burdens to optimising under such constraints.
Of course, written, the above program is nonconvex due to the objective 0 a. Indeed, this is well-established issue in linear bandits (without unknown constraints), and was first observed in this context by Dani et al. [DHK08]. Specifically, notice that due to the ellipsoidal structure of C2, even without unknown constraints, the program
max T a: 0 E X
is equivalent to solving
max ( + + xE
21

---

and in general it is NP-hard to solve such programs [Sah74; PV91]. Indeed, one can see that if 0, = 0. this is exactly equivalent to positive definite quadratic maximisation, which is known to NP-hard even if V = 7 and X' is only allowed to range over polytopes. Note that with the aforementioned hard enforcement constraints, X' is the intersection of Á and these SOC constraints.
This hardness can be addressed via a standard "e-reelxxttion [DHK08], which reduces the problem to solving 2d optimisation problems with linear objectives and the above SOC constraints, while weakening regret to ((R((sate) vdTT) in a nutshell, one replaces the ellipsoid { Ø|lv S w) by a skewed & ball of the form
(1 0) S Vdw}.
Such a ball has only 2d extreme points in 0, and of course for any a, one of these extreme points optimises 01 a over this balbal, meaning that computing maxo,a 0 can be reduced to solving 2d programs of the form max. 0" a. The increase in regret occurs due to the Vd-blowup, which is needed to ensure that the relaxed confidence set contains the original ellipsoid.
This characterises the costs of most of these bpptiissti--pssimiisi AAT19]. Afsharrad et al. give a systematic and detailed account of these considerations [AML24]]. There are two exceptions. The SAFE-LTS method of Moradipari et al. [MAAT21] uses sampling to select the objective, but still imposes the same SOC constraints, thus needing only one optimisation each round. The ROFUL method of Hutchinson al.[HTA24] instead first picks an action according to (the NP-hard to implement method) DOSS, and then scales it towards Osafe as in S-COLTS. Of course, note that S-COLTS samples only one set of linear constraints each round, and is efficient. There are also analytical differences between ROFUL and S-COLTS, as discussed in $4.
methods [c.g. PGBJ21; PGB24;
Turning to soft enforcement, as we mentioned in the main text, no efficient method is known. The main method herein for linear bandits is DOSS [GCS24], which instead picks actions by solving
max 0 s.t. 34 E CP Da S a.
BECT .EA
This E operator renders this problem much more challenging, since now the constraint works out to the union of polytopes
U An < sa), ACC
which is highly nonconvex, and hard to condense or relax. Indeed, Gangrade et al. [GCS24] propose using a similar -elrlaxatioon as discussed above for both the objective and the constraints, but this now leads to (2d)mm--extreme extreme points of the confidence sets (accounting for both @ and the m-rows of 4). leading to (2d) LP. log (f) compute needed per round. In contrast, R-COLTS uses LP LPllog (t) compute, and E-COLTS uses only LP log(t) compute.
More Details on the Failure of Prior Thompson Sampling Analyses. $4 discusses the point where the prior cecaturaatoo-basee analysis of linear TS due [AG13] breaks down in the presence of unknown constraints in some detail. For the optimism-based analysis of [AL17], we only briefly touch upon this in $5, and give a more detailed look in $D, This section serves as a brief summary of the latter.
The analysis of Abeille and Lazaric relies the convexity of the value function J(Ø) = max (T a to both analyse the roundwise regret (A(a:)) and to establish the frequency of certain 'global optimism' event (see $D. With unknown constraints, the corresponding object of interest is the value function K +) == sup a E A, ta < o.). This map is not convex in 6 which causes both of these steps to break down. R-COLTS avoids this issue by resampling. It is also possible to give analysis of S-COLTS (and E-COLTS) within the optimism framework, although this again utilises a scaling trick to bypass the same issue. Of course, we also establish optimism in a convexity free way by analysing the local behaviour at Ox.
Finding a Feasible Point, and Soft-Enforcement with ((1) Risk. Notice that since there are plenty of polynomial time methods for hard enforcement in SLBs (even though the prior methods impose SOC constraints), in principle one can develop efficient soft-enforcement methods with regret scaling inversely in max, T(a) by first discovering an action that has ((a) 2 const. max, r(a), and then
'Of course, we could also reveal the value of 0: a the optimum, and then, irrespective of the value of 0. turn this into positive definite quadratic maximisation problem over the set X n (0, v).
22

---

plugging this into a hard enforcement method. In this case, the exploration time would be random, but a constant, so the net risk would ostensibly be (1)) T explodes, far below our v7 bounds, making the performance close to that of hard enforcement.
In parallelly conducted research, we (along with coauthors) have recently provided an efficient method for this problem [GPSS25], which extends a previous (inefficient) approach to testing the feasibility of LPs due to us [GGSS24]. This method, termed FAST, is also based on Thompson Sampling, and also utilises the coupled noise design of $4.2 in the analysis of this method: because the expression max, r(a) max, min, P,a)" can be expressed as the value of matrix game over A and the probability simplex, one can exploit the boundedness of the probability simplex in I-norm to directly analyse a Lagrangian. We leave the details to the appropriate paper. The net result is thus: let Opm be the maximiser of the margin ((a) over A, and let r == max, l(a). Then with high probability FAST finds point dEAST such that [(CFAST) 2 /
core element. However, there are significant differences
O(d3/ (T?) rounds, which incurring a net safety risk of Odd) /T.).
Nevertheless, let us note that coupling our FAST method with S-COLTS gives the first algorithm which selects actions by only optimising over linear constraints, and gives both Od /T.) risk and ((R(aEAST) dFT) S ((T-'Vd'T regret without prior knowledge of any safe action such as the Osafe assumed in this paper, as well as all prior papers on hard constraint enforcement in safe bandits. Naturally, note that if max, [(a) is small, this regret bound can be much weaker than the unconditional (VTTT) bound of R-COLTS: which method to prefer depends on the application, and the importance of attaining ((1) instead of O(VdTT) risk. We also note that in principle the regret bound can be tightened beyond this: instead of searching for maximiser of (a)). one could directly search for minimiser of R(aa= A(a)/T(a) Finding an efficient and effective way to do this is an interesting open problem.
D Local Optimism, Global Optimism, and Unsaturation
In $5, (implicitly) defined local-optimism condition on the perturbation law μ in the statement of Lemma 10, which is compared to a "global optimism' condition suggested by the prior work of Abeille & Lazaric [AL17]. To further contextualise these, let us explicitly define them.
Definition 13. Lef K(0, +) sup(OT the objective 0 under constraint matrix t over A, with the convention that sup 0 = -C. Recall that the local optimism event at 0. is
E A, ta S a denote the value function of optimising
To, 2 0_ o., ((H,))a Sa), (,(5) = (1, H): 0(g 1) 0.
where a, the constrained optimum for the true parameters (0.,4.). Further, define the global optimism event
G,( = (11 H): K(0(1, t), ((H,t) 2 0. a. K(0,, v.)).
For म E (0, 1), we say that a law μ on (1,, H) satisfies Fllocal optimism if
Vt, HtE])(L)())) 5t-1] 2 x clnc
and similarly, that μ satisfies x- z-global optimism if
Vt,
2 1 Con.
Notice that G demands perturbations such that after optimising the perturbed parameters, the value of the resulting program is larger than 0_ o., while L demands the stronger condition that a, is feasible, and its value increases. Evidently, L C G, and so -loocal optimism of ju implies n-global optimism. Naturally, the entirety of $5 follows if we have globally optimistic f instead of locally optimistic μ. We presented this section with L, instead due to limited space in the main text.
As discussed in $4.2, we will also show, in SG, Lo) n Con C Uz(6) n Con, i.e., when consistency holds, local optimism implies unsaturation. Thus, L; links the global-optimism based
"note that there a cost, though: as stated before, the regret would scale inversely in the Slater gap, and until the safe point is discovered, would grow linearly.
23

---

framework of [AL17], and the unsaturation based framework of [AG13]. Nevertheless, technically. these are distinct events.
Let us briefly note that the prior work [AG13] essentially passes through the same strategy as us when establishing good unsaturation rate, in that they argue that local-optimism holds frequently (although they do not consider unknown constraints, so their argument does not extend to our setting). On the other hand, [AL17] presents convexity- without unknown constraints, while immediately breaks in our setting because (0,, ②) is nonconvex in D. We also reiterate that our coupled noise design of $4.2 essentially takes the same conditions on perturbations used in these prior works, and extends them to produce the same bounds on unsaturation or global-optimistt rates by arguing that local-optimism holds. This means that these prior results do not capture the prevalence of these events beyond local optimism. Our simulations in ŞJ suggest that this leaves a significant amount of performance on the table, capturing which theoretically would require deeper understanding of U, \ L. and G, \ L.-
proof of frequent global optimism for linear TS
Role of These Conditions in Our Work. To analyse S-COLTS and E-COLTS, we used a look-back approach enabled by the unsaturation condition, while to analyse R-COLTS, we relied on a direct use of the optimism condition. turns out that the unsaturation condition is not effective at capturing at least our strategy for analysing the resampling-basee strategy R-COLTS. The reason is that while the resampling will ensure that at least one of the optima of attaining the various ((i, t) values will be unsaturated, we have no guarantee that the procedure we take of picking the i..e that maximises K(i,t) t) will choose an unsaturated action. On the other hand, the optimism condition can be used to analyse S-COLTT and B-COLITS directly (see $H.5), but a direct execution of the previous optimism based approach [AL17] fails due the lack of convexity of the map K(0,, +). Instead, we have to directly analyse expressions of the form K|| (0. )) K(O', K')l 1], where (0, b) and (0', お') iid draws of the perturbation tie 1. Under the assumption that there is action with positive safety margin with small Mr. this can be executed via a similar scaling- based analysis, albeit at a loss of some factors in the regret bound ($H.5). In our opinion the unsaturation based look-back analysis of A (ax) is conceptually clearer, and we chose to present it in the main instead.
Nevertheless, in terms of their explanatory power, neither condition dominates the other. Indeed, in simulations, we find both cases where unsaturation is frequent but global optimism is not, and cases where global optimism is frequent but unsaturation is not.' Of course, in our analysis, both of these are connected by local optimism as detailed above, which is rendered frequent through our coupled design. Nevertheless, the local optimism rate can be significantly smaller than the unsaturation and global optimism rates, particularly when the noise is shrunk far below the theoretically analysed setting of ( -scale noise (see $J). These observations again hint that developing a tight theory of linear Ts (both with and without unknown constraints) requires a deeper understanding of the portion of these events that do not intersect with local optimism.
E
An Informal Discussion of Contextual Safe Linear Bandits
Rather than static bandit problems, most practical scenarios are contextual, wherein the learner observes some side information 2, before choosing an action, and this side information affects the reward and constraint structure at time t. A common setting to model this [PGB24; AG13] is to assume that there is a known feature map 4p X' x A + Rd such that the reward and constraints at time are of the form
0_ p( a) and $ (p.p( a) S a.
Throughout, we assume the same feedback structure, i.e., noisy measurements of 8T pxx,, a:) and p ( az). Naturally, regret is compared to the optimal policy s X + A, where
A (z) = arg max 0, f(xx, a): 2,p(2, a) S aa A. It should be noted that the Lemma continue to hold, with Vú replaced by 7 7+ Eegt s(t,, ax){(F. as) T and a, by (((), at). No-
consistency, and the elliptical potential lemma (Lemma 14)
tationally, we extend A(a), I(a) A(z,a) = 0_ (p(z, (x)) (((x,)) and T(x,a) = (0.0x
"This is most pertinent for the setting where we drive the perturbations with independent noise, where in $J.3 we observed that the unsaturation rate decayed with m. but the global optimism rate did not. Indeed, this is what prompted write the aetimism-basse analysis of HH.5.
24

---

A key observation is that our result on the frequency of the local optimism persists in this contextual setting. Under the hood, this essentially shows that at any t, and for any vector yp:
P (17 H) (n. : 2 0_ p. कΦ S P. 51- (8) 2 π (8))
where 0.28 for the coupled noise driven by Unif( (d35)) Consequently, frequent local optimism follows in the contextual setting by using this result for (0 (x+)) at time t.
The above observation means that using the same coupled noise lets us extend the results of Theo- rem 11 on the regret of R-COLTS to the contextual case with only cosmetic changes in the analysis. This holds no matter how the sequence Te is selected, as long as the noise remains conditionally centred and subGaussian given at, Tt, the algorithmic randomness, and the history. Note, however, that the optimisation over may become harder due to the feature map yp, and efficiency requires further structural assumptions on yp
Focusing now on S-COLTS, let us first note that if we were given a safe action Qsafe that was safe no matter the context, i.c. such that inf, [xx asate) 2 I sufe > O, and jo were 'nice' in terms of E A,* then as long as we know I safe priori, no real change is required, and the guarantees of Theorem for S-COLTS extend the contextual setting. 5 since we can again guarantee the frequent choice of unsaturated actions through our persistent local optimism property. We note that previous works on safe contextual bandits [PGB24] assume exactly this existence an 'always very safe' action. Nevertheless, this structure is unrealistic: practically, safety should depend strongly on the context, and
unlikely that a single action would always be safe, let alone have a large safety margin. A more natural assumption is that instead of single safe action, we are given a safe policy Asate : X + AA Here, again, if we know that inf. F(x, ssate 2 safe > O, and we know the value of I safe. then we are good to go, although this is strong assumption. Without knowing this value, we need to be able to determine a good estimate of [( (x:e) in order to appropriately ensure feasiblity of perturbed programs, and to scale back the actions by. This can be challenging task, especially if I4 varies in an adversarial way, and structures enabling such estimation must be assumed. 6 Finally, note that even if we were given I(x, Asate as a function explicitly, the and do
easily forthcoming regret bounds rather pessimistically scale with (infz I' (mii(())) not capture how variation in this margin with x can be used to limit regret. A (at least somewhat) different analysis is needed to express this in a clear way. Resolving such limitations is an important open problem in the theory of SLBs.
This lacuna also affects the E-COLTS method of $1.2, but to a lesser extent. Sticking with 'nice' feature maps, again, if there exists an action that is always safe, i.c., if max, min, l'xx,, az) > O, then the guarantees of Theorem 12 extend with arbitrary context sequence. Without this guarantee, the main gap is the exploration policy being utilised, which must be adapted to attain good coverage over (4p(z (2. }}} even as Z, varies. Given such a policy, however, the results of Theorem 12 again extend to the contextual case with arbitrary Tt.
F Some Basic Tools For the Analysis
We begin with some standard tools that are repeatedly utilised in the analysis. The first of these, termed the elliptical potential lemma offers generic control on the accumulation of [|aelly-t.
Lemma 14. [APSII; CVA20] For any sequence of actions {at} C [[|a|] S 1}, and any t,
El S 2dloog( + +ldd), and Σ Ilaally.- S 2dt + 1/d).
Further, for all t, (6) < 1 + V1/2log((m + 1)/5) - 4/2log(1 + t/d).
We further explicitly write the following instantiation of the our setting.
inequality pertinent to
'We essentially need a way to efficiently select an action a such that u0z2, a) = pP((a,, bi) + (1 p)),(s,, dsafe), so that safety can still be attained by mixing with dsafe.
"upoo replacing (daut) by 1
'For instance, if 2t were drawn in some static randomised way, and I' were sufficiently simple, then we
could learn 1' 1'(x, Aasto()) (x)) using regression techniques.
25

---

Lemma 15. For any positive definite matrix V. For pair of tuples (6, ②) and (6, ②) lying in Rd x Raxx and any a E RR,, it holds that
max (110- 0) 8)" a', max 1 - Tb')aa) max(110 Bllv. max | bllllv) ||all--1.
Proof. Notice that ( (8- 0) v1/2V-1/2 - |I - 0)1 1|V The claim
follows by first repeating the same observation for each (Φ' TD) (adjusting for the fact that these row-vectors), and then recalling that (for column vectors) | M |||l/ by definition. O
This immediately yields a proof of the concentration statement of Lemma 3, which motivated the definition of M,(a).
Proof of Lemma 3. Notice that by a union bound
P(Et: max([| max [( > B(6))) - Σ 55 =
Now assume that max(] [I nell, max; ([fli]) - B())), and that the consistency event Cōn holds. Then, via the triangle inequality,
[[(me. t) - 0.llv. & [10 t) dellv. + |10, - 1l4.
Of course, given Con) the second term is smaller than (5). For the first, expanding the definition of (((,,)), )), we find that
[10( t) 0.llv: w,(6))lne V. lv. (lw,(5)m V; v mo)
and of course, ||m S B())) by our assumption above. Thus, given the concentration assumption on || Is and (8), for any t, it holds that
[0(m.. t) - 0-11v; S (1 B(6:))wer() S (owr(5).
Of course, entirely the same applies to [ 1)2 - ll, with 7/ replaced by Hi The claim now follows by Lemma 15 and the fact that Con(o) = n (6) has chance at least - 6.
G Analysis of the Coupled Noise Design
We will first execute the strategy described in $4.2 to show that under the conditions of Lemma 8, local optimism frequent. We will then use this to show the frequency of unsaturation. Lemma 16. Let p E (0, 1], and let v be a law on pdx1 such that
Yu Rd v(I5 : 5 1 || 2
Let I be the the pushforward of under the map S + Con, Elu((,())) 5--1] 2 pl (o), where L,(5) is the local optimism event (6).
Then, for all t, (mT,-Im5T)
Proof. Observe that under a draw from μe, for all t, we have
@ t)) 0, + wi)S V, 1/2 T = ((H,t) -. 1m (w) Vv 1/2). Further, recall that if the event Con occurs, then, for all a.
0 a 2 0__ a + V,) 1/2 1/2a|l, all, and e S Φ,a + 1 (m 1/2 1/2a/l. a/l. where we have the Cauchy-Schwarz inequality, and the fact that ||all-- = 1|V; all. Thus, assuming (8), for any action a, we find that
Ta a 2 8_ a (6) (5 1/2 -
- 1/21)
Th > :,a m6)
(5T 1/2 11, 1/2 (2(l))
1V,
26

---

Now, set u,,, and suppose that < ViV 2 11V,-1/2,,1]
a.ll. Then we can conclude that
0'a a. 2 0, and ta, S 2.a, S a,
the final inequality holding since a, is of course feasible for the program it optimises. Of course, by definition, this means that the ensuing noise 7), H lie in the event L(())
Now, it only remains to argue that VVV a. 2 lls V 1/2 a. happens with large chance given Dt-1. But notice that both 1/=1//2 and (the constant) a, are - 1 -messurable, and so are constant
given it. It follows thus that
Elu(ts: 5 VVV, 1/2
u. VVVV/... 11V, 1/2 (v,""(,,11) 1.ll)) 5c-1) 2 inf v((S" u> ||ull)) 2 p-
uER
To finish the proof of frequent unsaturation, we only need to determine that this local optimism induces unsaturation in the actions.
Proof of Lemma 8. Fix a f, and assume consistency. Suppose that max([|ng ||. max; || v B(6)). Note that given (8), this with chance least 1 6z. As consequence, for any action G, {a A(a) > Me(a)], J, by following the proof of Lemma 3 we can conclude that
t(n,t)" Ta S 0. + Me(a) = 0_. a. (a) + M((a) < < a..
Now, suppose that the drawn ( induces local optimism. We claim that then all saturated actions suboptimal. Indeed, by the above, each unsaturated action satisfies ((1, t)_ 0__ a.. But (n),t) 'a. 2 8__ a., and further T HH, t)a. I a, means that there is an action that feasible for the perturbed program with value strictly larger than that attained by any saturated action, i.e., any member of G, It thus follows that the optimum a(1), H, t) E G; {a (aa S (a)).
Now, we know from Lemma 16 that given 1 our assumptions of (5) and the norm-control on |[mell, max; | imply that local optimism occurs with chance at least p. Since these events occur with chance at least 5,, this means that unsaturation occurs with chance at least &c. Since definition 4 restricts attention & S p/2, the statement follows.
L
G.1 Bounds for Simple Reference Laws
We argue that both the standard Gaussian, and the uniform law of the sphere of radius v yield effective noise distributions for our coupled design.
For the Gaussian, recall that if Z ~ M ((,, Ia), then || is distributed as a xr-random variable. A classical subexponential concentration argument [e.g. LM00, Lemma 1] yields that for any x.
2 + 2 dz + 2x)= Se
Note that (d+ 2 de + 2x) < (Vd + 22 2 and hence taking x = looo (/E) in the above yields that B(E) < vd /2 (1g)()E)..))) Further, due to the isotropicity of 7, 7 u ///lu| thus (1) 2 0.158 ....
law Zi ~ N 1), and
Further, notice that if Z # (0, Ia), then Y == /3dZ/11Z]1 (Vnd S²), and by isotropicity, for any u, TTu u//luul law Y, As result,
P(Y MoTTu/lun |M|l 2 1) = PY 2 1)= = P(Y? 2 1)
d
1 P(Z 2 1) P Σ 2 3d 11).
P((dd-1)2 2 Σ z
2
2
3d 1) S But notice that d - 1 2/ (d 1) d/3 + 2d/3 < 3d - 1, and thus, P
cxp(-d/3) Invoking the bound on P(Z 2 1) = L > 1) above, we conclude that π 2 0.15 (1 e- d/3). Of course, ||||| 3d surely, giving the B expression.
We note that while the above only shows 0.15(1 - dd/3) bound on the anticoncentration of the uniform law vdddd it is simple matter of simulation to find that this is actually larger than
27

---

0.28 for all d for small dimensions, the bound turns out to be very loose, while as d diverges, this converges from above towards the chance that standard Gaussian exceeds 1/ 1/v3, which is 0.2818
H The Analysis of S-COLTS
We move on to the analysis of S-COLTS. Before proceeding, we recall that in our presentation of S-COLTS in Algorithm address how to obtain such a quantity by repeatedly playing O₃ = Safes and characterise how long this takes. For completenesss, the cost of this will be incorporated into our regret bound.
assumed access quantity To [ 12 We will first
Beyond this, we need to characterise the subsequent time spent playing Asafe due to Mi being large, and prove the look-back bound of Lemma along with the characterisation of Σ Mr (ar(t) offered in Lemma 5. We will analyse these results order, and finally show Theorem using these results.
H.1 Identifying To and Sampling Rate of Osafe
first discuss the determination To. There are two main points to make: how to ensure a correct value of lo and how many rounds of exploration this costs. To this end, we first recall the following nonasymptotic law of iterated logarithms [e.g. HRMS21J.
Lemma 17. Let (Bt) ) be filtration, and let {&t) be process such that each is B--measurable, and is further conditionally centred and 1-subGaussian given B:-1. Then
45 E (0, [0.11.P(2 P(E: Z,| > LIL 5)) S 8,
where Z₁ = Eost Eo and
max log()))
LIL(t, = 4t log
6
With this in hand, the determination of To proceeds thus: we repeatedly play Osafe, and maintain the running average Av, E.se (a (t... Further, we maintain the upper and lower bounds
u Av, + [I 5/ /L, = Av. (IT.
We stop the first time when Vi, E 2 w2/2, and set To = min, tg This stopping time is denoted To-
Let us first show that this procedure is correct, and bound the size of To.
Lemma 18. Under the procedure specified above, it holds with probability at least 1 that
To E [T'(asafe) 22 (asste))
and that
8 To S π( T(agafe)
(OT
Proof.
Notice that we can write
Av. = 100--..900 asaf +
Σ wg/tt
For suceinctness, us write a - asafe Now, by our assumption on the noise w we observe that each coordinate of w constitutes an adapted. centred, and 1-subGaussian process. Applying Lemma 17 along with union bound over the coordinates then tells us that with probability least 1 1-8 8,
Vt, Av, - r S (tL.(t,6mm)ft 1m
As consequence, at all f, we have
W4 2 22 l,
where is the vector with ith coordinate u/. and similarly for l, It follows thus that at the stopping time To.
Vi, C, 2 w = Cr 2 1/2.
28

---

Of course, a fortiori, it follows that To = min; 4 2 min; /2 T(agate)/2. Further, of course, To I ((sate) follows as well, since vt min; f S min,(T") ((safe))
only remains to control Tb- To this end, notice that for all
4 = Av: LIT m/6)/t 1m 2 r
(1, m/8)/t 1m.
and similarly,
Up + 2LIL m/ m/0)/t
1m.
Of course, then f /2 for all & such that
vi, - LII m/0) 2 /2 LIL m m/0)/2t = I > m/
It follows thus that
To E inf (t= : FT(astee 2 3LIL m/8)}.
By simple inversion, this can be bounded as
To S in 8/T ( log(1/8) and t (/T(asafe) log(1 log(t)));
which is bounded as
8
To S
(8g(8/(8T(aaat)
[(usate)
Number of Times Osafe is sampled after To- Given the behaviour of To above, we can further bound the number of times Osafe played after determining T'o
Lemma 19. For any To > 0, and T, the number of times S-COLTS plays asafe because Mj (agate) > To/3 / is bounded as 13
9w B
Proof. Let ny denote the total number of times asafe has been played up to time Then, of course, VL bp I + mygasfeelaate Now, recall that for symmetric positive definite matrices A, B, it holds that x A-1? Thus, we have
A x
Mc(asate S wr B a (I Meagaaeel - -
Now, by the Cioemman-Morissonn formula.
a aate )aate
|
1 71
Asate (I + Mellsafo -1aeee)aaaaa "asafo = |Asafe|] ||
+ n4 [Usafel
1 + nu [sate]
follows thus that
We My (e(ustt)
/
Thus Me(Usate) > To/3 if and only if
Ows B r
74
Of course, each time this occurs, n, is increased by one. Consequently, the number of times agafe is played by time & is most
9w B2
+1.
r
Note that since (T)BB)² OdP + dlog(m//8) with our choice of the coupled noise driven by Unif( (dddd, the bound above due to playing Asafe due to too large Mz outstrips the bound on Ty above as long as
= odd2), ), as is to be expected.
In more technical terms, inversion is monotone decreasing in the Loewner sense. A simple way see this is define C B- AB-1/2
I (really iff), since for ? x TC 2 x xx Using this for y = c-1/2x then gives x x = (C- C(C-1/22) 2 (C-1/22) (C-1/A2))) = x TT- Since C-1 A- (direct multiplication), the same trick yields x B- (B-1/2g) T 2 - 11/ x2, in other words, B-1 x A!
Then A F
v, (B-1/2x) A(B-1/2 1/)22) 2 (B 1/2 B(B ((B-1))
29

---

H.2 Proof of the Look-Back Bound
The main text provides a brief sketch of the approach. We will flesh out these details, as well fill in the omitted aspects of the bound. To this end, we first state a result lower bounding pt. Note that the second half of this result implies Lemma 6.
Lemma 20. Assume that To [T(ssato) [usaaet)) and that both Con(ô) n (o) and the event of Lemma hold true. Then for all such that Me(Osate) To/3, it holds that
T(Osafe)
Pt T(asate) +3M.((b))
and
2My
Pt 2M.(Usate) + Me(b))
A. fortiooi, each of the following bounds is true:
(1 pt) (a < Me(at),
(r S 2M, (at), and
(1 (Asatet) (aM.
Proof. Recall that Pr is the largest p in [0, 1] such that
(phr + ()aaae)) + we (b)l + (1 p) peafeellv,.111 mm S a.
So, we demonstrate a Po I that satisfies this inequality, then Pt 2 Pu.
First note that under the assumption Mc 1 To/3, we know that
Ogafe S a - [( I. + To/3 1m I a - 2T (asafe)) 1ms
and thus b, exists since the program defining it is feasible. Now,
My(asafe)
$ aaate + (o))laaaaellll.- D.
1m
Br
Sa a )(a + 2Mr 1m S aa
2T((usafe)
1
B,
3
using the consistency of the confidence sets (and the Cauchy-Schiee Schwarz inequality), along with the fact that B, max(1, B(5))) 2 2. Further,
B.
bb + w,)))/bblll I T.bb+
(b + B.
Mr(bb) S a + Me(b.)
B.
Therefore,
(pb. + (1 p)asote) + we(6))llbb + (1 (1-p)asofellv.-
$ p d.be+ + Mb(bs) 1m + (1 p1-p)
Mclasafe)
@ +
1m
Br
B₁
a (br) (1 (asattt))) 1m
is straightforward to find that the additive term above is nonpositive for Pa [(ors) (3.M((b)) and
I((aat)) thus P: 2 [(awa) (3M,
Further, since M, (Caate) ((dmate))), also have
a 20 (asafe)/3 S 2.M
Thus, we can also write
daate + Me (M B, B,1m 5a 2M, (U lm and carrying the procedure then shows that
2M, (Asafe)
Pt 2
2M, (Agafe) + Me(b))
30

---

To draw the final conclusions, first observe that
(btb
1-p: S (astfe + (b,)
(e S p.MM(bb) S
where we used the fact that prb, a₁ (1 Pi asafe and that M, is scaling of a norm. It follows that (1 - pt) pt) I Me(a)), and of course, that M, I 2M{(a:). Further, by similar calculation,
3M,(be)
(1 (1-Ph) Pt) ((aaae)) (b+)
(1 pc) (dsaat) S Mibb)(b) S (M.(
The above control on (1 - pt) is natural in light of terms of the form (1 (Qrat))) appearing in the bound as sketched in the main text. Let us now complete this argument.
Proving the Look-Back Bound.
Proof Lemma 7. We assume To [T(asafe)/2, l' ),, and that the event of Lemma holds, as well as Con(o). Together these occur with chance at least 1 - 36.
Now, we begin as in the main text, by observing that
A(a)) = (pthe + (1 Pt)) = (b)( + (1 - ((sate)) Let f be such that (a s o as well. Then we further know that hb v = F,b. a (M.(b.) + M,(b.))
As consequence, for
((Wsate)
0- T(asafe)
+3(M((ba) M,(b,))²
we have
(o (1-00 aa (.-b((M((bb)) (M,,)) 2(1 (x--s)T((aaall (Asate)
1 Sa aa
3
Define base o, + +(1 oa-te)asate- By the above observation, b is feasible for T and therefore 0, b,-st S 0g by. To use this, note that
((b,) = A(b + 0_ (b.-t b,) = A(bo-s)) + 0, (ba-s- bb) + (0, - Tbo-ss - be)
<(bb,-))) 07 (b.-st bb) Me(b.-1)) Me(b.).
where we first use Lemma and then bound M: b,) by using the fact that M, is norm. The second term above is of course nonpositive, and so can be dropped while retaining the upper bound. Further,
(b, o. o...A((b)) + (1 Tx-se) A(asaee)
This leaves us with the bound
((a)) S (1 Pt pr(1 -0-())))(
+ (bb.) + Mc(b.) M(..). + (1- ((
where we used the triangle inequality and the fact that M, is a scaling a norm to write the final two terms. We will, of course, evaluate this at 7t). In the subsequent, will just write instead of rtt) for the sake of reducing the density notation. Using the fact that A (bb))= S Mz (b,), ) we set up the basic bound
((a.) s (1 P: + P - (((o)))((sste)))
+p,M,(b)) (M, Mc(b,)) (1 (c)
Now, first observe that by Lemma 20,
< A(asate)
(1 - At
Mi (at):
[(Ogafe)
31

---

and further
PrMo(bb) S 2.M((a.).
We are left with terms scaling with d- (1 Tr- For this, first observe that
Blwe Br (bbrlll,,
Bruit
Me(br) = BBwee Bewwelbrrlly.
My (br);
Br
Brw,
where we use the fact that V, is nondecreasing (in the positive definite ordering). Let us abbreviate J+ == 1 + (B,)) Upon observing that Pr I 1, to finish the argument, we only need to control
(1 1--r=a)(A(aattt + (e((ts)e) + J, -
Now, notice that since M, (asafe) S To/3,
T(asafe)
T(asafe)
2M, (a7)
Or l'(asate) + (b,) + (b,)) S I'(asate) + 3M,(b,)
Pr
M,
where we invoke Lemma 20 for the final two inequalities. Thus, we find that
o.-:J+-rMM S J (,,,(b,) - 2J, (a,)).
This leaves us with the term (1 0- (A(asate) Mc (a To bound this, observe that
3 3(Ma(br) + M-
Tr-I) ([asae (b,) (b,))
(1 - - [ = 3e (b,) + M-(6+)) S -.
Recall from the discussion above that o, -- (b,) & p, - 2M,((a)) Using this, and the fact that (Mgatee s /3 then yields
A(asate) My(a,) + 2J (a.)).
(1 o ( (A(asae) M, (asate)) 6J++ ((asaee)
Putting everything together, then, we conclude that
A(asste) (Me(a.) + Jr-st + 22 (a)))) T(asate)
A(a, S
which course implies the bound we set out to show.
H.3
Controlling Accumulation in the Look-Back Bound
We proceed to control the accumulation of the look-back terms.
Proof of Lemma 5. Since B, and w, are nondecreasing, for any S T, we have
(B,w,(5) Blui (5) (b)) (B Let Tr = {t $ T ((sste) $ ro/3]. and Ut = {s s E Tr A(b.) & (bb))) Then notice that
(1
Σ ||- Σ Lellaollv.+ TET
sElfr
where L, - 11 - :()) s is the number of times serves as T()) () for some t. But this is the same as the time (restricted Tr) between and the next member of Urr , i.e., the length of the 'run' of the method playing saturated actions (plus one).
At this point, weaker bound of the form 2 log(T²/0) ExEu, ||asll,- is straightforward: each X
round has at least a chance x/2 of picking a saturated be, and the chance that the keth such run has length greater than 2 log(k((k + 1))8) is at most 5/k(k 1). Since there are at most T runs up to time T, union bounding over this gives maxur L, + 2 log( + 1)/5)/x.
The rest of this proof is devoted to give a more refined martingale analysis that saves upon the multiplicative log(T") term above. We encapsulate this an auxiliary Lemma below.
32

---

Lemma 21. In the setting of Lemma 5, it holds that with probability at least - 6,
L.llaslly, 1 I sElér
Σ
Σ SEUfr
||alll,, log(1/6))
This result shown below, Assuming this result, the original claim follows immediately, since due to the nonnegativity of ||
|| Exeu, I|axllv,- S Eigt |
n
To finish the argument, move showing the auxiliary lemma described above.
Proof of Lemma 21. We work with the reduction to Exeu, || established above. Let us denote Ç = it > Çi Ma(esate) S To/3, A(be) S M2 (b.) as the times that an unsaturated precisely the elements of Ur. Notice
action is picked, with Co that this { is a sequence of stopping times adapted to the history {5.}. Let us further denote L, = (G++1 (i), for i 2 0 (this corresponds L,, where = (t). The object we need control is
for 4 S T. these
E L.X
RGST
where X; = ||a 11 E [0, 1], the lower bound being since X; is norm, and the upper bound since Vg, > For notational convenience, we always set Xo = 1. Now, to control this, let us first pass to the associated sigma algebrac of the Ça past, denoted as
G, := (())..)
Notice that since Ç is nondecreasing, we know that {8.} forms a filtration. Of course, by definition, X, are adapted to G, while L; are adapted to 6 1++-- We further know that Lg is the time (including G) between ç and Çi+1- But then for each f. > G. P(G++1 t/++1 > t 1, 11)) 2 x/2. As a result, these I,8 are conditionally stochatically domainted by geometric random variable, i.e.,
F(L: > 1 k (,)) s (1 x
This in turn implies that for any A small enough,
X/2
[.,] S 1- x/2)exX,
In the subsequent, we will need to select a X that is independent all of these L,, X,. To ensure that the calculation makes sense, ensure that (1 x/2)e* < (which suffices since 0 X, 1). Let us define (A(A) == log((1 (1
(/x/2)). Then by the above calculation, we find that
the process (M.) with Mo I and
M exp (L, - ΣFOW
a nonnegative supermartingale with respect to the filtration {3.} with 8, = G,+1) } and So defined to be the trivial sigma algebra. Thus, by Ville's inequality, P(3i: M, 1/8) < d. Taking logarithms, we find that with probability at least - 5, it holds that
log (1/8)
F((A)
Vn, Σ LXX,
Σ X, 15n
X
SSa
long 0 - log([1 x/2). All we need now is convenient bound on Ft(A) and judicious choice of X. To this end, we observe the following simple result.
Lemma 22, For any constant u E (0, 1), consider the map f(x) == log l-ve" [0, - log(u)). Then for all E [0, - log(u)) we have
I-a over the domain
Vu
f(x) 5
r.
Vu
33

---

Proof. Observe that
uEe cd
et
f((x= = 1 - 1_ = 1 -
(1 c-1 u)) = 1- - 1220 0
The inequalities above arise since ef 1-u derivative, we may see that itself is an increasing function. Now, suppose g(z) satisfies
u using the fact that ex 2 1. By taking another
I-ae
g(0) = f(0) O, and Va, g'xx) = f((-1/2lo(uu) Vu
Then since g(( > (x) for all E [0, - log(u)] by the fundamental theorem of calculus it follows that for all x v log u, f(x So f' S Jo g' g(x).
Now, of course, (A) = f(AX;), with u = x/2. log(1/6)
Then setting À - log(1 x/2), we have
v 1-2/2
Vn, 1uX: ~ Σ x; log(1 x/2)/2
v 1 - X/2 Xi.
i5n
To get the form needed, we observe that
VI ---r 1 - (2+ - 5) 4 = -
-30² s 0.
vI -
and of course log(1 r2/2 2 2/2. Plugging in v= x/2 > 0, we end up
Vn, Σ L,X: < 85
Σ Xi i5n
4 log(1/6).
Note that explicit n-dependent term appears in the above. This makes sense: essen- tially have the X,s acting as 'time steps', and so L,X, should behave as (1 +1+ 2/x) Σ X; + O(VE X; 1 log(1/))) via Bernstein-type computation. In our case, the square root terms do not meaningfully help the solution," & and so we just pick a convenient À instead." Now, going back original object of study, have I, Tiqu: X₃ precisely the members of Ur, so we conclude that
||aç, llvzz? and these Gs
5 Ex.+log(1/0) X
VT, L.X. sElfy
H.4 Regret and Risk Bounds for S-COLTS
With the above pieces in place, we move to showing the final bounds on the behaviour of S-COLTS.
Proof of Theorem 9. We first argue the safety properties. Firstly, in the exploration phase, as well to explore, repeatedly play asafe- But this is, by definition, safe, and so accrues no safety cost. When not playing Osafe, the selected action oe at time / satisfies
i.a+ + (x)llellll v. 1m aa
But, given the consistency event (8),
Va, a.a I a. + wo(6)llal|,-";
and so 4.4. S a. Since Con(o) = 0 (on holds with chance at least 1 8, it follows that a is safe every and fortiori, ST 0 for every T.
Let us turn to the regret analysis. Fix any T. We break the regret analysis into four pieces: the regret accrued over the initial exploration, that accrued after this phase, but when (M > To/3, and
since there will always be additive log(1/8) and 5 ΣX., term
and in the process, avoid the subtleties of the dependence of À on the X,s if optimised it
34

---

over the time Tr := ft To Ma(asafe - To/3), and finally the regret incurred up to the time it 6, x/2).
The last of these is the most trivial handle: the number of such rounds is bounded as /28/x, X, and the regret in any round is at most 2.
For the first case, Lemma 18 ensures that with probability at least 6, this phase has length most
log(8/ (aT((t))))))))))
and further, the output To is at least ( /2 at the end. Using this to instantiate Lemma 19, we further find that the number of times Osafe is selected beyond this initial exploration is in total bounded as
36 B 1 1
[(safe) )
Together these contribute at most
44w B7 [(osafe)
A ((Gsaee)
to the regret.
This leaves us with the times at which My ( (Asate) < To/3, /3, for which we apply Lemma 7, along with the control Lemma 5 to find that the net regret accrued thus is bounded as
o o (1+ A(asata) T(asaee)
BrwT(O)-
5 X
|aelly + 1og(1/0)
To complete the book-keeping, the probabilistic events required for this are the consistency of the confidence sets, that for all L, max([|?) max; || (l) is bounded by B(,)), and course the bound on the times between unsaturated b, being constructed from Lemma 5. Together, these occur with chance at least 36, and putting the same together with the stopping time bound, we conclude that with chance at least 1 - 46, S-COLTS(H, d) satisfies the regret bound
RT < 1 A(asafe) I((safo) δ
Br
A(asafe) [(asao))
- - B2 [((ssao))
85
|aellv;"'
+
+
X
X
1ST
Now, invoking Lemma 14, we can bound wy - (v)))==((++0)((m00))) and Σ ||a li Ö(van Finally, for the law y induced via the coupled noise design by Unif(v/dS<4) we further know that Br = ((v)) and x 2 0.28. Of course, for this noise, B, = /3d with certainty, which boosts the probability above to 1 35. The claim thus follows for S-COI.TS(4.8/3)
H.5 An Optimism-Bartt Based Analysis of S-COLTS
We analyse S-COLTS under the assumption that satisfies B-concentration and t r-global optimism (Definition 13). We shall be somewhat informal in executing this.
Setting Up. We first note that regret accrued over rounds in which (,,), [(asate)/ and Mf ( < To/3 is small. Indeed,
Σ 1T
(b,) [(asate)/3] S
Σ (b.)2)
T(aeate)² )
1ETT
16
(a,)2)
=ō
d
< l'(ssafe)
p
TET
where Ta = (t: Me(asste) < To/3]. and we used the bound on My from Lemma 20, along with the fact that since by E A, My (bx) & Bas = (d),, which in turn implies that Pt 2 ((asate) ) )/2(d))
35

---

Naturally, this additive term is much weaker than that seen in Theorem 9. Nevertheless, the optimism- based framework does recover similar main term. In particular we will show regret bound of ((
The point of the above condition is that (using Lemma 20), if M+(b)) 2 / then 2 1 We 2
will repeatedly this fact in the subsequent.
Now, we begin similarly to the previous analysis by using
((a)) = (1 - p:) (gaae)) + (b)( I (1 ( ) + A(b)).
The first term is well-comtrolled,
detailed in the proof of Lemma 7. So. only need worry about Σ A (bb)). Notice that for this suffices to control Σ E A ( [5t_1]. Indeed, A (br) < 1 (and if it is I O, we can just drop it from the sum, i.e., we could study (A(b))) instead with no change in the argument), so the difference EisT (br,) - ([)(bb)) 5 is a martingale with increments lying in 1-1, 1J, and the LIL (Lemma 17) ensures that for all 7 simultaneously, the difference between these is (og()))())))) with chance at least - 5.
From the above, then, we can restrict attention to such that (e I To/3, 2 1-- Finally, recalling the notation K (0, ) m a: a E A, aa S a} from Definition 13, we observe that
(bb,) = 0__ a. - -0 + (6. - 0.)Tbr
< K(O,, 2.) K(0,, b.) + Mc,)))
$ K(O,, T.) K (ê,, T.)) + (a.),
where we used Lemma 3, and Lemma 20 along with the fact that pt 2 1/2. Now note that the final term above is summable to Ö(vd'T). Thus, it equivalently suffices analyse the behaviour of Eạ-1 (62, P.) - K(0,, [r-]) Lemma 23. Lef (0,, T.) and (0,, k.) denote two independent copies of parameter perturbations at time Let B2-11 = El. 11)) If satisfies r-globbl optimism, then
1] In order to do so, we begin with 'symmetrisation' lemma.
C (8) Be (0c, 2.) K (0,, Tc)1 S (6) (6) 1 -E--il Tb) K (0,,, Kc)l].
Proof. Let G G= (K(0,, x))) > K(0,, d.) Since (0,,, t..) is a constant, and since (0,, F.)
independent of (0,, 41) given 5 we conclude that
E,-1 K (0., 4.) K (0, क.) = E. E, P.) - K(O, (1) G].
But given G, K(O., D.) K0,,, σ.), and so
E- 2.) K(,, 2.)1 S E,- [K(0,, 2.) K(O,, Φ.) G]
S Ek-ilKK (K(0 b.) K K(Ø, T1)l G]. Finally, for any nonnegative random variable X, and any event E, holds that
R [ [1E] = R, 1 1 g] < R2 [X]
The claim follows upon taking X = K (0,, D.) (0,, 4 E G. and recognising that due to --pptimism, satisfies [1]] π Con.
The main question now becomes controlling how far the deviations in K can go. We control this using a similar scaling trick as in the proof Lemma
For the sake of clarity, we will denote the optimiser K(O,, Tb) as b, (instead of just as in the rest of the text), and similarly that of K (0,, tb)) as by. Our goal is to control (the conditional mean of)
10, bT - be).
Naturally, the core issue remains that b, and b, are optima in distinct feasible sets, and so it is hard to, e.g., compare 0, by and 0, b. To this end, we observe that
L.b. S a L.b. S Mc(b.))
L.b. 2b, 1m,
36

---

as long as consisteney and the boundedness of the noise norms holds (which occurs with high probability). Using this and the fact that D S ( we find that
[(asafe)
De + (1 Te)asate) S a, where o, T(asaee) + (b)
Thus, we may write
0 (1- o,) 6, 0, )o, + (o,b, be).
Above, the third term is nonpositive, while the second term may be bounded by 2a which can further be bounded by 8M²(a+) upon recalling that p. pb(b)) > &/ and the bound on pt (bbe) in Lemma 20. This leaves the first term. It is tempting to bound this directly via 0g be - ||@ll][bell but notice that the former can be as large as B vd. Instead, we can use the related bound
(0 b.) S
(.))) (1 -0)00 b,.
Now notice that (1 - σ1) S 1, and (c,),. < 4., controls the first term. Similarly, 0_ I (both have norm bounded by 1). so the second term is bounded by 5₁ I 3M.((5)) Putting these together, we conclude that
T(Oat)) < 12
Me(as) [(antt))
(1 1.),000, b.) & 4M.( + 12Mc(aa)
I(asate)
which in turn yields the bound
K(Be, (.) - K K(0,, कb) = (a.) + (a.) (āz)
((asafe) I(asate)
Of course, switching the roles of (0,, ).) and (0,, क.),, we have analogous bound on K (0,, T.) K ((,,, tb). Putting these together, we conclude that
[Ke. ).) K(0 Tb)1 (a( + M.(e)) I(asafe)
Finally, notice that ãe a. and the actually selected action a, all have the same distribution given He-1. We can thus conclude that
Mc(a.) [(asate)
E, E [i-[ Φb)) K K(O,, x < 48E,-
With this in hand, the issue returns to one concentration. We know that Σ Me(a;) is Ö(VTTT), and each (ax) is bounded as O(d) and so Σ Me(a.) - [M,()M((a:)) enjoys concentration the scale dIIIL. 5) Ō( ((v ol d.))). Thus, passing back to the the unconstrained sums, end with a bound of the form
Rr = Ō - + Ö(dTT(astt))*))
The main loss in the main term above is that instead of A (asate) ((tsatt)T((aaa (aasff)) we just have l'(asate) term in the bound. This can lossy, e.g., when agafe is very close to a., but in the regime A (aaafe) = 2(1), it recovers essentially the same guarantees Theorem 9, albeit with weaker additive term.
I The Analysis of Soft Constraint Enforcement Methods.
L.1 The Analysis of R-COLTS
Let us first show the optimism result for R-COLTS
Proof of Lemma 10. Fix any I, and assume (ō), For each i [t), know that K(i, K ((O(i,)) f), (i, t)) 2 0(i, t) a, 2 0_ a, whenever the event occurs, and thus this inequality holds with chance at least æ in every round. Since the draws all independent given 5i--1 the chance that max K(i, t) < 0_ a, is at most (1 - T)²x < exp( - (og(1/6,) x) I 6, 6/s(t+1). Thus, if we assume that (8n(8) : n (5) holds true, the chance that at any I, K K(,,, 1) < 0_ a, is at most E 8r 6. By Lemma 1, Con(8) holds with chance least 1 8, and we are done.
D
37

---

Of course, the above proof, and thus the statement of this Lemma, holds verbatim if we replace L by G, (Definition 13).
With the optimism result of Lemma 10, the argument underlying Theorem 11 is extremely standard.
Proof of Theorem 1I. Assume consistency, and that at every 1, 02 at 2 a_ Since we sample at most 2 + r log((1))) programs in round i, we further know that with probability at least 5,
VI, max max |ln(i, OI, max (1. I s = B(6./ + (ro:trrorr/////// rlog(1/))))
Assume that this too occurs, and define Mc(a) wi( B.llall,, Then, using consistency,
0_ az 2 02 at Me(ae), 2.a. - Bray + Me(a))) sa Me(at)lm. So, the safety risk is bounded
ST S Σ Me(as) S wTT( + +
Σ
Noell,.
1ST
Further,
0 a. 0, S 0g a. 0f at + Me(ae);
which implies that
R S (T( + Br Σ ||aelly-
1ST
and for our selected noise, the coupled design driven by Uni((v/d39)) we have B--) = v 3d independently of I, r,r, and thus 3T v /3.. The events needed to show the above were the consistency, the concentration of the sampled noise to B, each time t, and the optimism event of Lemma 10. Again, the second happens with certainty for us, and so the above bounds hold at all T with chance at least 1 - 25. Consequently, the result was stated for R-COLTS(P, r, 6/2).
as well. Now Lemma 14 controls wT Eist |lalll,-> to
1.2 The Exploratory-COLTS Method
As discussed in $5, the Exploratory COLTS, or E-COLTS method, augments COLTS with a low-rate of flat exploration, and exploits the resulting (eventual) perturbed feasibility of actions with large safety margin to bootstrap the scaling-basse based analysis of S-COLTS to soft-enforcement without resampling.
The main distinetion lies, of course, in the fact that in the soft enforcement setting, do not have access to a given safe action Qsafe To motivate the method, let us consider how S S-COLTS uses the knowledge of agate. This occurs in three ways: to ensure the existence of a(n, H,, t), to compute the action a, from this, and to enable the look-back analysis of lemma 7. The second use is easy to address: we will simply play a a(n, H,, t) if it exists. The key observation is that rather than explicit knowledge of any one particular safe action, as long as some action a exists such that Mc(a) < 1'(a)/3, the entirely of the first and third uses can be recovered, and so the machinery of $4 can be enabled.
Forced Exploration. We enable the eventual existence of such actions by introducing small rate of forced exploration in our method E-COLTS. Concretely, we demand a 'x-good' exploration policy over A, i.e., one such that after N exploratory actions c1,-.. EN, we are assured that Lee, > x| x|//4]]a Ia, where k > is a constant. This can, e.g., be done by playing the elements of a barycentric spanner of A in round-robin [AK08; DHK08). The resulting 6. is geometric property of A, and we note that i only enters the analysis, not the algorithm.
Let us call a time step i where the exploratory policy is executed an 'E-step'. In E-COLTS, we ensure tha tat any f, at least Brue v dt such E-steps have been performed, and not, we force an E-step. Note that we expect that the majority of the learning process occurs at steps other than E-steps, since this is where the informative action a(n, He, 1) is played. Consequently, we will call such steps LL "Lestes''
38

---

Algorithm 3 Exploratory-COLTS
(B-COLTS((1 (FFCCOo
Input: Jr, 6, exploration policy.
2: Initialise: un f 0, B, f- 1 B()))
3: for 1- 1, 2.... do
4: Draw (m, H.) na.
5: if u4-1 I (o) OR a(n: H4, f) does not exist then
6:
Pick ar via exploration policy.
7:
"4 - 4-1-1++
8:
else
9:
0r + u(ne; Ha, (), Ut +- Wz-1-
10: Play at, observe Re, Se, update 8r.
By our requirement of enough E-steps, at any L-step 1, the sample second moment matrix V satsifies
Ve x KBews vt/dla, and so,
Va, M(a) - (t) dBf 1/4
||a/].
R22t
This means that at such t. any a with r(a)= > 2t)(t/3 satisfies M((a) s I(a)/3, and so a(m, He, t) exists, and may use the analysis of $4 for such
Regret Bound. The above insight is the main driver of the result of Theorem 12, which we show in 1 to follow. Recall that this states that under the E-COLTS strategy, executed with μ constructed through the coupled noise design with base measure Unif(v3d55 the risk and regret satisfy, with high probability, the bounds
d3 ||l| (a)((a)
ST = Ö(VVT min Ō
and
R(a)Ō(VoTT) + 3 d d|aa|
Ry min a:((a>>0
where x is precisely the 'goodness-factor of the exploratory policy. Let us briefly discuss this result.
Risk bound. Unlike S-COLTS, E-COLTS suffers nontrivial risk, which is unavoidable due to the lack of knowledge of asafe [PGBJ21]. The ( dT) risk above above comparable to the OVdT) risk of the prior soft enforcement method DOSS [GCS24], with a vdl loss again attributable to efficiency. Note that compared to R-COLTS, the risk bound essentially the same, but now incurs an extra additive term scaling, essentially, with (max, I(a))= Thus, nontrivial risk bound is only shown this maximum strictly positive, i.e., under Slater's condition. Nevertheless, the term is additive, and scales with T only logarithmically (through dependence on (r). and so in typical scenarios is not expected to dominate as T diverges, although the fourth-power dependence on this quantity would increase the 'burn-in' time of this result.
Regret bound. As discussed in $5, the main term of the regret bound above improves over that of S-COLTS, since it minimises over Ra),,, rather than working with the arbitrary (asafe). Note that finding the minimiser of R may be challenging. but E-COLTS nevertheless adapts to this. However, the additive lower-order term is larger than in S-COLTS due to the 'flat' exploration of E-COLTS, and its practical effect is unclear. simple simulations, we observe significant regret improvement (SJ). We note that the k-good exploration condition only affects the lower order term in Rr, although again the fourth order dependence on l'(a) is nontrivial. Of course, relative to E-COLTS, the result suffers from instance-dependennc, and again, unless Slater's 's condition is satisfied, it is incffective.
Practical Role of Forced Exploration. E-COLTS uses forced exploration to ensure that V large, which leads to both feasibility of the perturbed program, and the scaling-based analysis. In practice, however, one expects that low-regret algorithms satisfy max, ||q| y E t 1-1/4||a|] directly, the idea being that actions with larger V,, -norm represent underexplored directions that would naturally be selected (recent work has made strides towards actually proving such a result, although does not quite get there [BGCG23J). Thus we believe that this forced exploration can practically be omitted except when the perturbed program is infeasible. Indeed, in simulations, we find that this strategy already has good regret ($J).
39

---

I.2.1 The Analysis of E-COLTS
We will essentially reuse our analysis of S-COLTS, with slight variations.
Proof of Theorem 12. We will first discuss the bound on the regret. Throughout, we assume con- sistency, and the noise concentration event of Lemma 3. We will further just write wi instead of (.) Recall the terminology that every in which we pick an action according to the exploratory policy is called an 'E-step', and every other step an 'L-step'. Here E and L stand for exploration and learning respectively, the idea being that the former constitute the basic exploration required to enable feasibility under perturbations, and so the main learning process occurs in L-steps.
Note that the number of E-steps up to time t is explicitly delineated to be at most [ V dt). Using the k-good assumption, then, we find that at every L-step.
Vi > BBowyt/dd =
' 1 V.
Now, fix any action dg with I(ao) O. Then notice that at any L-step.
l S Vdllaol?
= Me(ao)² Bowellaol? d/t.
kBewiVi
Thus, for all
82 to(ao) == inf {1: 3'dllool| Bl x²T((n))
S 5t}
that are L-steps, we know that long the noises nh Hy satisfy the bound of Lemma 3, 2,00 I a (Toaa)31,,, Note that since w/ S d log(t) + log(m/6)), and since under our choice of coupled noise, B. = 33d for all 4, we can conclude that
to(an) s Cd3 aoll" log Ca Cd2 lap 1 log(m/5)
log Cd&l log(m/8)) x²T((n)²
<²)((a0)T
x²T((a))
x²T(aa)
= (
d3s 1loll
where C' is some large enough constant (C' 4- 81 suffices). This implies that at all L>> (n(a)) at which the number of E-steps, U, is large enough, the perturbed program is feasible, and a, exists. Thus, after this time, no extraneous E-steps are accrued due to infeasibility of the perturbed program.
At this point we apply the proof of Lemma 7, with Pt 1. Let
rtt) supfs s S t: (aa.) I Me(as),M((ao) S {(ao)/33).
Now, or need not be feasible for क., but we know that a S a = T.a, S a + Me(a+) + M- (az). So for
I(ao)
o = T((an) + 3(M,(aa + M, (ar))'
we know that
(0 + (1 or=))ao) S a.
Let ar-xt= == Or-10 + (1 - 0r T- Then we can write
A(w:) A(ār-))) + 0,T (är->- -a))
< A (ar= ) + 0, (ā,-1 - ar) + Mi(ar) + Mi(ār-()
< Tr A (ar) + (1 -1- -r-rt) (un) + Mr(as) + -r-st + )
< (1 - ) + Mc(ar) + (M + (1 oy Mi)
where in the end we used the fact that A(a+) S M, (a+). Now,
(a+) + M,
Tr
To
40

---

and of course M, I To. We end up with a bound of the form
A(a)) S C 0
A(ao) (M,(a)) + M,(a,) M, I(ao)
which is essentially the same as that of Lemma 7. Given this, we can immediately invoke Lemma (appropritacly modifying by Osafe + ag and To I'(a))). We end up with the control that
A(a:) =ō (1+ A(ao) [(ao)
BIwT X
Σ
Σ |[aellv;*
For our choice of noise (being the coupled design executed with v Snif(v3dS% we have ((),, B O(vd), and so this can be bounded
ET Σ A(ai) = Ō (R(ao)dd)T)
Of course, the above holds true for all (a() that were not E-steps. Before to(ao), we may bound the per-round regret by 2. Finally, we are left with the E-steps after the time to (o())). Since, as argued above, no extraneous E-steps due to the infeasiblity of perturbed programs occur, we can then, for T to(a)), simply bound the total number of E-steps by + Brwr dT, and acerue roudwise regret of at most in these steps. With our chosen noise, B, = O(vd), this cost is O(vdT)) Summing these three contributions, and invoking the bound to(aa) finishes the argument upon recognizing that dg is arbitrary, and so we may minimise over it.
Turning now to the risk, first observe that for any / > To := min, (a(a), there exists at least one action
such that Ma) S /3a)/3, and so the perturbed program always feasible, i.e., a(m:: He, 1) exists. Now, consider subsequent times. Observe that in L-steps, since Pra; S a, we know by Lemma that a,a, < a - (Mt) assuming consistency and the concentration of max([Ine] ||. max; [| (). Thus, in L-steps, the risk accrued at any time is at most M, ). On the other hand, in E-steps, the risk accumulated can be bounded by just (using the boundedness of 4. and A, and to work out the total number of these. But after time To such an E-step only occurs to make sure that the net number of E-steps is at least Broi v dt, and so the total number of such steps is at most BrWTVdT.
only need
Putting these together, conclude that the net risk accrued is bounded
M.(ar) Br Ö(Vd'T min Ō dBRufllallt) x²T(aaa²
ST To + Σ 1+
Σ
TOSIST is E-step
STT. fis I-step
Invoking Lemma 14, as well as the fact that B, = B, 3dd for our noise design, the claim follows.
Finally, 1et account for the probabilistic conditions needed: need the concentration event of Lemma 5 to hold for the regret bound, and the consistency and boise-boundedness events for both. Of course, the second is not actually needed, since our noise is bounded always. Together, then, these occur with chance at least - 25 under our noise design. Of course, then, passing to E-COLTS 5/2) yields the claimed result.
41

---

J Simulation Study
We conduct simulation studies to investigate the behaviour of E-COLTS/R-COLTS and of S-COLTS. We first study the soft and hard constraint enforcement problems with our coupled noise design. After this, we investigate the behaviour of COLTS methods using independent (or decoupled) noise in $J.3. All experiments were executed on consumer- -radee laptop computer running a Ryzen-5 chip, in the MATLAB environment, and the total time of experiments ran to about hours.
J.1 Soft Constraint Enforcement
We begin with studying the behaviour of the soft constraint enforcement strategies E-COLTS and R-COLTS, Throughout, we treat E-COLTS as R-COLTS( 0, 8), with no exploration.
Setting. We set 4, to be a certain 9 x 9 directed adjacency matrix, A, obtained from https: //sparse. tamu. odu/vanneuueelun wwaikkellmmaaae haapllle///aaaa.// which is a 60% populated matrix with d The rows of t. over A 0, 0,1/vad and enforce the unkonwn constraints 2.a S 0.8 1/va. We note that the action 0 is always safe, no matter the d,. This choice is intentional, in that it lets us avoid the inconvenient fixed exploration present in E-COLTS and S-COLTS. Throughout, set ô = 0.1.
9. normalised to have norm We study the problem of optimising 0, vd
As stated above, for the bulk of this section, we will implement E-COLTS without forced exploration. Indeed, this is not required since 0 is always feasible, as discussed above. This can equivalently be interpreted R-COLTS with the resampling parameter r'
Effect of Noise Rate. As previously noted, in linear TS, small perturbation noise-of the scale 1 rather than O D(vd)-retain sufficient rates of global optimism and unsaturation to enable good regret behaviour. Note that such small noise directly reduces Br, and thus we would expect it to improve our regret behaviour by factor of about vd. In order exploit this, begin by conducting pilot experiments with our coupled noise design to determine a reasonable noise scale for us to use.
Concretely, drive coupled noise design with the laws v, Unif(n S"),, and run E-COLTS without exploration for 10 steps 100 times. In each run, we simply record whether (i) global optimism: (ii) local optimism; and (iii) unsaturation held, and estimate their rates simply as the fraction of jime over the run that this property was true. We construct these rate estimates for Y E [v3d /33,, specifically evaluating the same for 41 values of y chosen over an exponential grid (i.e., that log(?) has constant step). Figure 3 shows the resulting estimates.
The core observation is that global optimism and unsaturation rates are already at ~ for log(7) R 1,, indicating good performance with this noise. Note that while such performance with small noise has been previously observed for linear TS without unknown constraints, we are unaware an explicit observation of these
Median Rate Estinates for Coupled
E-COLTS over 100 Runs of Length 10
(iiiee Optiniion Hala
Local Optintion Take
Unasturation Raie
0.8
0.6
rates as above has been performed. Of course,
proving these properties at such small y is an open question, and also note that timates above are not quite correct, since they
0.2
integrate the events across time, while their rates
could vary with t. In any case, the main upshot for this is that in our subsequent experiments, we work with 7 0.5 instead of 3 x 5.2.
-1.0 -3.9
-32 -2.5
-18
-11
-0.1
0.3
1 1.7
los 7))
Figure 3: Behaviour of the Global and Local Optimism Rates, well as the Unsaturation Rate. The black verti- cal line lies at y = 0.5, the value selected subsequent experimentation. The largest studied value is at v3d, which has logarithm about 1.65 Observe that the global optimism and unsaturation rates are significant, and particular 1 for y 0.5, far below /3d 25 5.2.
The Behaviour of E-COLTS and R-COLTS. We now study R-COLTS and E-COLTS over the long horizon T 1 We execute R-COLTS with zero resamplings (i.c., E-COLTS with no explo- ration), and then one and finally two resamplings in each round, all driven by the coupled pertur- bation noise with Po.5-
42

---

No Soaappin
No Seamplat
Rmangh Onee
-Roengk Onst
Neangh Teizz
300
Reennak Tem
Regret, 100
Time.
Time,
No Bessngling
No Resenggiiggg ling
-Raangl Onee
RRoample Once
Rosugh: Tvis
300
Rosapl: Teas
Rink S. over 100
100
70
Figure Regret (left) and Risk (right) of R-COLTS zero, one, two resamplings per round. Top includes one-sigma crror bars, and for clarity, the bottom figures omit them. Note that the regret behaviour is an order of magnitude smaller than the scale ddT = 6600, while the risk behaviour is about a factor of half of this. We further observe that resampling improves regret signficantly, while only hurting the risks slightly, although this effect appears decelerate resampling increased.
On DOSS. We note that DOSS is not implemented. E-COLTS runs ~ 10-3s per round on our machine. (Relaxed)-DOsS is totally impractical: (2d) > 10 and so it needs >> 10 i.e., years, per round!
Observations. Figure 4 shows the observed regret and risk traces over 100 runs. The observed regret behaviour is very strong: even without resampling, the terminal median regret of 600 closer to VT T R 750 than / log() = 6600. The risk behaviour is more significant, but still half this scale. The observation of Ry suggests that stronger regret bound may hold for E-COLTS and R-COLTS, which line with the stronger instance-ste spenccfc regret behaviour of the optimism-baa baseed method DOSS [GCS24]. Proving this is an interesting open problem.
These simulations thus bear the strong performance of E-COLTS/R-COII with r 0. Further, as we add resampling, risk degrades mildly, but the regret improves significantly, although the returns diminish with more resampling. This suggests that practically, a few resamplings R-COLTS are enough to extract most of the advantage. Interestingly, resampling has palpable effect even though the optimism is nearly one!
J.2 Hard Constraint Enforcement
Next, we investigate the hehaviour of S-COLTS over the same instance, supplied with the data Asafe The natural point of comparison to S-COLTS is the SAFF-ITTS algorithm [MAAT21], which operates in O(SOCP log f) computation per round." 10
JeWe do not implement other prior methods for SI.Bs, mainly because SAFE-LTS has previously been seen have similar bchaviour, and be about 2d 18 times faster than these methods. Of course, we also did implement DOSS as comparison for the soft constriant enforcement methods since impractical to execute for = m = 9.
43

---

Concretely, we again drive this method with Mu.5 as before. For SAFE-LTS, we sample perturbed objective vector with the same noise scale, and otherwise optimise over the second order conic constraints as detailed in $4.3. In both cases, we used the library methods linprog and coneprog provided by MATLAB to implement these methods." !I Note that these methods are specifically tailored to linear and conic programming respectively. As before, we repeat runs of length 7 5-10 for a total of 100 runs.
Strong Safety Behaviour: We note that in all of our runs, we did not observe any constraint violation from either S-COLTS or SAFE-LTS, despite the fact that we executed these methods with 0.1. This suggests both that in practice. the parameter ó can be relaxed (which would yield mild improvements in regret), and in any case verifies the strong safety properties of these methods.
Comparison of Regret. We show the regret traces over the 100 runs in Figure 5. We observe that S-COLITS has slightly improved regret performance relative to SAFE-LTS, which may be attributed to the selection of stronger exploratory directions through solving the perturbed program.
1900
SCOLTS SAFE-LTS
1880
Regret, R., over 100 runs
1200
-2000
800
X00
Time,
Figure 5: Regret Behaviour of S-COLTS and SAFE-LTS on the same instance as previous figures (onc-sigma eтror curves). We note that S-COLTS offers mild improvement in regret over SAFE-LTS. However, this comes with 5x reduction
computational time per round, which is the main advantage of S-COLTS.
Computational Speedup. In wall-clock terms, each iteration of SAFE-LTS about 5.2x slower than that of S-COLTS on this 9 dimensional instance with 9 unknown constraints (over 5 10 total iterations, S-COLTS took about 0.22ms per iteration, while SAFE-LTS took about 1.16ms), significant computational advantage even in this modest parameter setup.
High Level Conclusions. The main takeaway from this set of experiments is that S-COLTS offers tangible benefits in computational time relative to SAFE-LTS (and a fortiori, to other pessimism- optimism based frequentist hard constraint enforcement methods), while even obtaining slight improvement in the regret behaviour. This demonstrates the utility of S-COLTS over these prior methodologies, and suggests that the natural approach that should be used in practice.
J.2.1 Investingating Behaviour with Increasing 772
Of course, the computational problem of optimising m SOC constraints becomes harder as m grows, and we expect that the computational advantage of S-COLTS over SAFE-LTS would grow with m.. 12 To investigate this hypothesis more closely, we turn to a slightly different setup.
Setup. We set d 0, = A = [-1/v0, 1/v For m 2 3, we impose m unknown constraints such that the feasible region forms regular m--gon with one vertex at (0.2/ 0). This allows us systematically increase m (to very high values) without incurring significant computational costs. We investigate the behaviour of S-COLTS and E-COLTS on this setup with the coupled noise design as the previous section (y 0.5) for m E {10, .0, 1000. We also
"f course, R- R-COLLS/E-COLLE
were also implemented using linprog.
Note that it may be possible to mitigate this somewhat by instead imposing the convex constraint max,($,c. - a)' + ||a| -1 v. < to exploit that the same matrix V,-1 appears in all constraints. However, the gradient computation of this map still grows with so the overall picture is unclear. Of course, imposing only linear constraints is bound to be faster.
44

---

SCHLES SAFB-11S
92111.5 SAPE-TT
Rogie By at 10" sians
Time Per enenation (In millscconds)
nvernge 5- 110 itercticons
Number Constraints.
Number of Coustraints,
curves) and computational costs (right) of S-COLTS = 2 instance as m varies. This is the same setting as Figure 2, right, but presented separately rather than as a ratio. The left plots the regrets at time ' = 10 over 50, and the right plots the wall-clock time iteration iteration, while SAFE-LTS needs 4.5 at 100. At the same time, for m 10, the regret of S-COLTS about 3x smaller.
Figure 6: Comparisons of the regret (left, one-sigma and SAFE-LTS
resources in milliseconds. S-COLTS needs 0.14 0.25 milliseconds per
execute this for m = 1, where a single constraint passing through the same vertex is enforced. In all cases, we Gsafe O, which is always feasible.
Strong Computatational Speedup. As seen in Figure 6, S-COLTS has a strong computational advatange, which further grows with m. In particular, m 1, s S-COLTS is about 1.3x faster to execute than SAFE-LTS, while for m 100, this advantage grows to 18x.
Improved Regret Performance. 13 Further, instead of the small gain seen in the previous section, in this problem S-COLTS has strong statistical advantage relative to SAFE-LTS for even moderate m. Indeed, while at m = 1, its regret is about 10% larger than that SAFE-LTS, for larger m, its regret is many times smaller. In particular, for m 2 10, we found that the regret of S-COLTS is roughly 3x smaller (ranging between 2.7 x and 3.4x.).
Takeaways. This investigation further bolsters the strong advantage of S-COLTS over SAFE-LTS. Note that alternative confidence-set based hard enforcement methods are at least 2d times slowed than SAFE-LTS, meaning that the computational ad advantage of S-COLTS is even stronger relative these methods. For large m, this appears to be accompanied by large statistical advantage, making this the natural method in applications of SLBs.
J.3 Simulation Study on the Behaviour of the Decoupled Noise
Finally, we investigate the behaviour the COLTS framework under the decoupled noise design, wherein, instead of setting H = -1m7, draw 1). and each row of H, independently from V/-- The main impetus behind this, of course, is that this decoupled design is a natural choice to execute COLTS, although it is contraindicated by the analysis tools available to
Behaviour of Event Rates with 7. To begin with, Figure 7 shows the global optimism, local optimism, and unsaturation rates with this decoupled noise for the same instance as previously studied. Observe first that the decoupled noise design does experience a slight decrease in each of these rates compared to those seen in Figure 3. However, this effect is relatively mild, and in particular, we can see that the unsaturation rate is already up to nearly one at our previously selected value of y = 0.5. This suggests that the decoupled noise would do nearly as well as the coupled noise in this case.
Behaviour of Regret and Risk. To further investigate the above claim, we execute E-COLTS without exploration (or equivalently, R-COLTS with = 0) driven with this decoupled noise over the longer horizon T 10 The resulting regret and risks are plotted in Figure 8, along with the same for E-COLTS with coupled noise. Observe that the decoupled noise sees significant loss of about 3x in regret, but sees gain of about 1.5x in risk. Heuristically, we may think of the decoupled noise as
13 Note: for the regret ratio in Figure 2, we perform 100 separate runs with both methods, and compute the ratio of regret for the two methods in each. That figure reports the mean over this data in this case, the expected mean is 1.5
1, but with wide confidence intervals (CIs). For m > 10, the lower confidence bounds all exceed At 1, the mean regret of SAFE-LTS is about 0.91x that of S-COLTS, with strongly overlapping Cls.
45

---

Median Emimates Decoupled
E-COUTS over 100 Ruse of Leogghh 10"
Loca Oycasam
Conelcaatoon Bate
0.0
0.2
-4.6
-3.9
-3.2
-2.5
-1.8
-1.1
-0.4
0.3
1.7
log(?)
Figure 7: Behaviour of the Global Optimism, Local Optimism, and Unsaturation Rates with for the Decoupled Noise the setting Figure 3. Observe that while these rates decay somewhat with respect to coupled noise, they are still strong, and especially for large are nearly as good as with the coupled noise.
Couplel Norso
Creple Decorpted
Dewopped Nolee
Rogeet, R. over 100 ruLa
130
Riak: S: SICE
60
Tame.
Time
Figure 8: Behaviour of regret (left) and risk (right) for E-COLTS executed with the decoupled noise compared with E-COLTS executed with the coupled noise (one-sigma error bars). Observe that the regret behaviour sharply deteriorates, while risk behaviour slightly improves the decoupled noise design. Heuristically, this suggests that the decoupled noise behaves 'like" the coupled noise, but with smaller value of 7.
behaving as if the noise is coupled but "shrunk", so that the behaviour of the risk is improved, but the behaviour the regret worsens.
Practically speaking, our recommendation remains to use the coupled noise design, that attains higher rates of explanatory events, and carries theoretical guarantees. Nevertheless, establishing that Ry and Sy do scale sublinearly with the decoupled noise design, as evident from Figure 8, is an interesting open problem.
J.3.1 Investigation of Rates with Increasing m
Of course, the main obstruction with the use the decoupled noise in $4.2 was to do with many constraints. Indeed, it should be clear that under this decoupled noise, the local optimism rate must decay exponentially with m, since any row of क is perturbed so that a. violates its constraints, local optimism would fail (and this would occcur with a constant chance, no matter the estimates).
To probe whether this indeed occurs, simulate the behaviour of E-COLTS with the coupled and decoupled noise designs on a simplified setup.
Setup. We again take the d 2 polygonal constraints investigated in $1.2.1. We investigate the behaviour of E-COLTS with both the coupled and decoupled noise designs on this instance as E {10, 20, ... 100} U {200, 300, 1000}, thus letting probe extremely high number of unknown constraints.
Observations. There are two main observations of Figure 9, Firstly, note that as shown in the main text, the rates of optimism and unsaturation under the coupled noise design are stable, and do not meaningfully vary with m after it has grown at least slightly.
46

---

Coupled Nojoe
69
Local Optintion Utosiization
100 rans of lougth 102 with Decoupled Naise
Nileel Opemmbon Local Opiinion Usautoralios
100 1045 Perceatic of Event Rates over
04-
10th Porcentlic Event Rates
94-
14-
62-
81
Number of Constraints (m)
Number of Constrainte
(m)
Figure 9: Behaviour of the rates of global and local optimism, and of unsaturation, in the polygonal instances
the number of constraints is increased for the coupled (left) and decoupled (right) noise designs driven by Un). Observed that the behaviour of these stable with for the coupled design, but for the decoupled design, the local optimism and unsaturation rate decay with m. Surprisingly, the global optimism rate remains stable even for the decoupled noise design.
On the other hand, under the decoupled noise design, the local optimism rate clearly crashes ex- ponentially. The unsaturation rate has a slower but evident decay: roughly, this is as m m-1-3 for m I 100, and appears to be exponential for large m. However, surprisingly. the global optimism rate remains stable (although lower than the same with the coupled design). This shows that there are situations with low-regret where frequent global optimism would be the 'correct' explanation for good performance methods like S-COLTS or E-COLTS (indeed, this what prompted us write the optimism based analysis of these methods in $H.5). Note however that proving that global optimism frequent under the decoupled design an open problem. In fact, with unknown constraints, we do not know of any method to deal with global optimism lower bounds that does not pass through local optimism, since the approach Abeille & Lazaric [AL17] relies on convexity properties of the value function in terms of the unknown parameters, which fails in this case.
47


Reviews:
[{"review_id": "OjTsAyFfOC", "reviewer": "Reviewer_uHq6", "summary": "The paper studies constrained linear bandit and introduces the COLTS framework and its variants with algorithmic and computational merits. However, I have several substantial concerns regarding the clarity and consistency of some key definitions and derivations, which I believe deserve careful attention.", "questions": "1. $\\Gamma(a)$ is defined as $\\min_u (\\alpha - \\Phi_\\star a)_+^i$, where the variable $u$ is undefined (line 107). \n\n2. The confidence event $Cont(\\delta)$ holds with probability at least $1 - \\delta$ in Lemma~1. However, since it combines confidence intervals for both $\\theta^\\star$ and $\\Phi_\\star$ over all $T$ rounds, the union bound implies that the probability is at least $1 - 2T\\delta$, not $1 - \\delta$. \n\n3. When ensuring constraint satisfaction, the paper states the condition $1 - \\rho \\leq M_t(b_t) / \\Gamma(a_{safe})$. This inequality is inverted: to ensure the constraint is satisfied, one must have $\\rho M_t(b_t) + (1 - \\rho) \\Gamma(a_{safe}) \\leq 0$ from line 173. This misstatement could affect both the theoretical justification and the algorithm implementation. \n\n4. The legend of Figure~2 does not explain all the components, specifically the dashed lines, which may represent standard deviations or baselines. Clarifying their meaning is important for interpretability and reproducibility.\n\n5. The majority of the safe linear bandit works, and some of them cited in the paper, consider a finite action set, rather than a convex polytope as considered in the paper. While the linear constraint that is typically used in safe bandits is of the form that action in each round, x_t^\\top \\mu^* < C, which is different from the risk definition used in this paper. Can you comment and explain and provide some practical motivation for such a constraint?", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength:\n1. Constrained bandit linear is an interesting area in the online decision-making literature.\n2. The paper provides a theoretical analysis of the proposed approach, along with experimental results.\n\nWeakness/Areas of improvement:\n\n1. The presentation of the paper is hard to follow. In my humble opinion, I would suggest that the quality and the clarity of the presentation could be improved.\n\n2. Some of the claims in the paper could be more elaborated. For instance, the paper claims the contribution as existing works require solving NP hard constraints avoiding this requirement is the focus of the paper. However, it is unclear from the paper why such an NP-hard constraint arises in those works. Some of the works that are cited study a slightly different problem setting  (specifically in their constraint model), and hence, such a claim must be well-explained. \n\n3. There are multiple undefined notations, some errors, etc., identified in the paper. A careful revision will be needed.", "was_revised": true, "final_justification": "After considering the author's response and comments by other reviewers, I am raising my score. However, in my humble opinion, the paper in its current form is hard to follow and requires a major revision.", "rebuttal": "Thank you for your thorough feedback.  Below we **restated each major question** and then provided our clarifying response.  We believe this format makes our disagreements—and the reasons for them—crystal clear. We will first discuss the questions, and then the weakness comments. $\\newcommand{\\asafe}{a_{\\mathrm{safe}}}$ $\\newcommand{\\gsafe}{\\Gamma(\\asafe)}$ $\\newcommand{\\viol}{\\mathrm{viol}}$\n\n---\n## Questions\n\n### Q1. “Several undefined notations, errors, and inconsistencies in definitions” \n>“There are multiple undefined notations, some errors, etc., identified in the paper. A careful revision will be needed.”_\n\nWe have an **extensive glossary** in Appendix A defining every symbol, and a **global pass confirms no undefined symbols** (apart from the typo in Q1 of your list, which we will correct from “_u_” to “_i_”).  If you can point to exact line numbers or symbols, we will fix them immediately.\n\n---\n\n### Q2. “The confidence event Cont(δ) holds with probability 1 – δ, not 1 – 2Tδ”; \n>“Lemma 1 combines intervals for both $\\theta\\_\\*$ and $\\Phi\\_\\*$ over $T$ rounds, so the union bound implies probability ≥ $1 – 2Tδ$, not $1 – δ$.”\n\n**We disagree. The statement as written in the paper is correct.** This is an anytime result: the chance that there exists _any_ $t$ such that  $ \\theta\\_\\* \\not\\in \\mathcal{C}\\_t^\\theta(\\delta)$ or $\\Phi\\_\\* \\not\\in \\mathcal{C}\\_t^\\Phi(\\delta)$ is smaller than $\\delta$. See Theorem 2 of [APS11]; Lemma 1 is just this along with a union bound over the $m$ constraints and $1$ objective vector.\n\n---\n\n### Q3. “The inequality $1 – ρ ≤ M_t(b_t)/\\gsafe$ is inverted; it breaks safety”\n> _“To ensure the constraint is satisfied, one must have $ρ M_t(b_t)+(1–ρ)\\gsafe ≤0$ from line 173. The paper writes the inequality the other way.”_\n\n**No, this is not a condition for safety, but a property of the selected $\\rho_t$**. \n- Let us work this out.\n    - First, note the sign error in the review: it should be $-(1-\\rho)\\gsafe$ (line 173).\n    - Any $\\rho$ satisfying $\\rho M_t(b_t) - (1-\\rho)\\gsafe \\le 0$ yields a safe action. We want the **largest** such $\\rho$.\n    - Note that $\\rho\\_\\* := \\gsafe/(\\gsafe + M\\_t(b\\_t))$ satisfies this inequality. Further, $$ 1-\\rho\\_\\* \\le \\frac{M\\_t(b\\_t)}{M\\_t(b\\_t) + \\gsafe} \\le \\frac{M\\_t(b\\_t)}{\\gsafe}.$$\n     - Thus, the largest $\\rho\\_t$ would satisfy this too.\n- The above is true if $\\gsafe$ is known. But (line 174) in reality we estimate a bound on it. Then $\\rho_t$ is defined via (4) **explicitly as a maximiser**. \n    - This $\\rho_t$ satisfies a weaker inequality $1-\\rho\\_t \\le 6M\\_t(b\\_t)/\\gsafe$. See line 181 onwards, and Lemma 19 for details. \n\n---\n\n### Q4. “Legend of Figure 2 does not explain dashed lines”\n> _“The legend of Figure 2 does not explain all components, specifically the dashed lines, which may represent standard deviations.”_\n\nThe **caption mentions one-sigma error bars**. We will expand this to: \"dashed lines denote one-sigma error bars.\" The two methods SCOLTS and SafeLTS are clearly marked in the legend and discussed in the caption.\n\n---\n### Q5. “The majority of the safe linear bandit works, and some of them cited in the paper, consider a finite action set ...”\n\nFirst, we disagree with two establishing sentences in this question.\n\n> *The majority of the safe linear bandit works... consider a finite action set, rather than a convex polytope...*\n\n**We disagree** that the majority of SLB work considers finite action sets. [AAT19], [MAAT21], [PGBJ21], [PGB 24], [GCS24] all study continuous action sets.\n   - Further, continuous action bandits are a natural and well-established model. E.g., the seminal papers of [DHK08] and [APS11] study the continuum setting. This is both a natural way to formulate many practical optimization problems, and to capture the limit of large $K$. E.g., control actions in a power system or a production line are continuous. So this line of investigation is meaningful no matter what regime prior work studied!\n\n> *While the linear constraint that is typically used in safe bandits is of the form that action in each round, $x\\_t^\\top \\mu^\\* < C$, which is different from the risk definition used in this paper*\n\n**We study the same constraints** \n    \n- First, $<$ should be $\\le$ above (this is standard in all optimization, for closedness).\n- Now, map $(\\mu^\\*)^\\top$ to our $\\Phi\\_\\*, x\\_t$ to our $a\\_t$ and $C$ to our $\\alpha$. We end up with our $\\Phi\\_\\* a_t \\le \\alpha.$ \n- Only difference: we have $m > 1$ constraints. So this is a strict generalization.\n\nFinally, the reviewer asks\n> *Can you comment and explain and provide some practical motivation for such a constraint?*\n\n**Since the constraints are the same, it is unclear what is being asked.** The reviewer seems to accept linear constraints as in prior SLB works. Given that, there are two potential issues we see\n1. *Why do we study $m > 1$ linear constraints?*\n2. *How does the cumulative \"risk\" metric $\\mathbf{S}\\_T$ relate to the per-round constraint $\\forall t, \\Phi\\_\\* a\\_t \\le \\alpha$?*\n\nWe will answer these question below, but please tell us if something else is intended.\n\n1. *Why $m > 1$ constraints:* There are three reasons\n    - **Many practical problems (see Table 3 Appendix B) have $m > 1$ constraints.** For example\n        - Power systems: each node and link in the grid has a voltage/current constraint.\n        - Fairness: each group has different membership, and so imposes a different fairness constraint.\n    - The results generalize cleanly\n        - We can handle many constraints with only $\\log(m)$ dependence in regret (Thm 8, 10). Previous works also generalize this way.\n         - $m = 1$ is easily recovered as a special case.\n     - $m > 1$ is technically challenging.\n         - Handling $m > 1$ constraints is a key issue in the design of COLTS. This is why we developed the coupled noise design.\n         - Naive approaches would instead gain $\\mathrm{poly}(m)$ or even $\\exp(m)$ factors in the regret. \n\n2. *How $\\mathbf{S}\\_T$ relates*\n    - $\\mathbf{S}\\_T$ is a convenient way to capture both hard and soft enforcement together.\n    - $\\mathbf{S}\\_T = 0$ **is equivalent to safety in every round**.\n         - For succinctness, define $\\viol\\_t = \\big( \\max\\_i (\\Phi\\_\\* a_t - \\alpha)^i \\big)_+$. Notice that $\\viol\\_t \\ge 0$ always. \n         - If for any $t$, $\\Phi\\_* a_t \\not\\le \\alpha,$ then $\\viol\\_t > 0$ (strictly positive). \n         - But $\\mathbf{S}\\_T = \\sum_t \\mathrm{viol}_t$. So, $$ \\mathbf{S}\\_T = 0 \\implies \\forall t, \\viol\\_t = 0 \\implies \\forall t, \\Phi\\_* a_t \\le \\alpha.$$  \n      - Thus, the **safety guarantee of Thm. 8** is the same as prior hard-enforcement papers. \n  - In Thm. 10, we are handing the distinct soft enforcement problem.\n\n--- \n\n## Weaknesses section\n\n### NP-hardness\n> \"the paper claims the contribution as existing works require solving NP hard constraints avoiding this requirement is the focus of the paper. However, it is unclear from the paper why such an NP-hard constraint arises in those works. Some of the works that are cited study a slightly different problem setting (specifically in their constraint model), and hence, such a claim must be well-explained.\"\n\n**No, this is not the case**. We have already (see Q5 above) discussed that the previously studied constraints and our constraints are the same. However, the **hardness is already an issue even without any constraints.** This is established in the bandits literature since at least 2008. \n\n- OFUL [APS11] addresses linear bandits without any constraints. Even OFUL needs to solve an NP-hard problem to select actions. This was first identified by Dani et al [DHK08, sec. 3.4]\n    - In OFUL, to pick $a_t$, we need to solve a program of the form $\\max_{\\theta \\in \\mathcal{C}_t, a \\in \\mathcal{A}} \\theta^\\top a$, where $\\mathcal{C}_t = \\\\{ \\theta: \\\\|\\theta - \\hat\\theta\\_t\\\\|\\_{V\\_t} \\le \\omega_t\\\\}$ is an ellipsoid. **This bilinear programming problem** is NP-hard. \n        - Indeed, by optimising over $\\theta$, this is equivalent to $\\max_{a \\in \\mathcal{A}} \\hat\\theta_t^\\top a + \\\\|a\\\\|\\_{V\\_t^{-1}}$. \n        - This is worst-case harder than positive definite quadratic maximisation (set $\\hat\\theta = 0$), which is NP-hard (Sahni 1974, Pardolis \\& Vavasis 1991).\n    - All the OPT-PESS methods, as well as DOSS (and so ROFUL), extend this method by modifying $\\mathcal{A}$. See line 511 onwards for details. But in the worst case, if $\\alpha$ is large enough, then the problem they need to solve collapses to the above. Thus, all these methods also need solutions to an NP-hard problem.\n         - In reality, the extra constraints of these methods make the problems harder, not easier, since they can lead to more complex feasible sets.\n         - E.g., DOSS uses bilinear programming over a nonconvex set (line 529 onwards)!\n\n---\n\n### Missing notation and errors\n\nWe discus this in Q1 above. Again, there is an extensive glossary, and no examples are pointed out except one typo (which we will fix). To our reading, there are no significant errors in the paper.\n\n---\n\n### Writing\n\nThe review does not mention what part of the writing they found unclear. From other reviews, yes, we agree that the writing of the look-back analysis and S-COLTS can get dense, and if accepted we will use the extra space to give more high level details for this procedure. See the other rebuttals for how we intend to address this.\n\nAgain, if the reviewer sees errors in the definitions, we will very happily address them, but no example was given.\n\n---\n\nReferences \\\n\nSahni, S. N. (1974). Quadratic maximization over a polytope. SIAM Journal on Computing. \\\nPardalos, P. M. & Vavasis, S. A. (1991). Quadratic programming with one negative eigenvalue is NP-hard. Journal of Global Optimization."}, {"review_id": "aZY4j2EKXI", "reviewer": "Reviewer_aqsD", "summary": "The paper studies linear bandits with (linear) safety constraints. The paper proposes a sampling procedure akin the Thomson sampling algorithm to avoid solving expensive problems at each round.\nBy assuming the knowledge of a safe action, the authors propose a hard-constraint algorithm (zero violations) S-colts and prove that regret scales with $O(\\sqrt{d^3 T}\\cdot R(a_{safe})$ where $R(a_{safe})$ is the ratio of the gap divided by the safety margin of the safe action (1+). The algorithm needs to know the safety margin of the safe action (bounds on).\nThen the authors provide an algorithm for the soft constraints (sublinear violations) that does not require knowing $a_{safe}$ and achieves a regret and violations bound of $O(\\sqrt{d^3T})$.", "questions": "1. The formatting of Equation 1 is weird. Consider putting regrets and risk after the definitions, and not in the equations\n2. Line 33: What is an NP-hard constraint?\n3. Table 1: Are you sure that solving OPT-PESS requires solving an NP-hard problem at each round? More precisely, are you sure that you can implement *any* instance of the NP-hard problem while running OPT-PESS (or DOSS)? I strongly believe this is not the case. While I think it is true that these methods require solving a “hard” program, you cannot say that solving these problems is NP-hard. Meaning that either you show a reduction from a generic NP-hard problem to the problem that OPT-PESS requires to solve when applied to a specific constrained bandit problem, or you cannot say that running OPT-PESS requires solving an NP-hard problem. You also have issues with randomization, as the “hard” problems that need to be solved by these methods are randomized, and, as far as we know, the average case complexity of these methods might be polynomial.\n4. Line 84: same issue. Also, problems are NP-hard and not algorithms. What you can say is that the classic implementation of ROFUL requires solving a problem X for which there is no polynomial-time algorithm currently known.\n5. Line 119: Why is the L2 operator norm used? I think constraining the vector for each reward cost is what is standard in the rated literature (BwK, for instance). There, you assume that each vector of costs (column of $\\Phi$) is a vector in between $[-1,1]^d$. I think this is more natural, as normalization across different costs does not seem natural\n6. Definition 2: What are $\\eta$ and $H^i$? This is not clear from the current writing. Additionally, Lemma 3 is somewhat confusing. Consider rewriting a bit here.\n7. What prevents you from extending the results to convex non-linear constraints?\n8. What is the connection with the BwK literature and its extension of bandit with constraints? I think this is much more related than what either community realizes. I can refer here to some papers that I think should be compared, as some recent BwK works handle per-round constraints: \"Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression\" and \"Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints\".", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "The paper is interesting and relevant to the NaurIPS learning community. The writing is good, even if it becomes a bit too dense in the second half, where I think the authors could do a better job at first describing the S-Colt algorithm at a high level, highlighting what the main argument of its correctness is. I also have a minor issue with the complexity-related terms used in the paper. Sometimes, the authors claim that an algorithm is NP-hard (which is very imprecise) or that an algorithm requires solving an NP-hard problem (which is not proven anywhere and probably unprovable formally). This is a minor misuse of terminology, but I think it has to be fixed. More on this in the questions section of the review.", "was_revised": true, "final_justification": "I agree with the author's points raised during the discussion. I find the paper, even if not revolutionary, since it mainly deals with the efficiency of linear bandits, to be a good candidate for acceptance.", "rebuttal": "Thank you for the detailed comments. Below we  \n(i) correct one factual misunderstanding in the summary, and discuss the orignality score,\\\n(ii) clarify the “NP–hard” terminology _and_ show that the hardness of OFUL-type methods is relevant, and  \n(iii) answer the numbered questions; \n\n---\n## Review Summary\n\n### *\"The algorithm needs to know the safety margin of the safe action (bounds on).\"*  \n  **No**. S–COLTS does **not** assume that this margin is known. It is estimated online via an anytime confidence interval (Alg. 1, L. 175; App. H.1), and this is where the extra  $\\tilde{\\mathcal{O}}\\bigl(d^{2}\\Delta \\Gamma^{-2}\\bigr)$ term in Theorem 8 comes from. Algorithm 1 is written without this step for brevity. \n\n### *Low Originality Score*  \n\nWe respectfully ask the reviewer to reconsider the originality score. Our work introduces four key technical innovations:\n\n- **Coupled-Noise Design (Sec. 4.2):** A novel and general noise design that couples perturbations for all constraints. This critically enables the analysis of TS in SLBs, and prior ways of analysing single-objective TS do not generalize. Further, the naive way of designing the loss would lead to extra $m$-factors in the regret that this design avoids.\n\n- **Look-back Analysis (Sec. 4.1, Lemma 5,6):** A new way to structure the unsaturation-based analysis of TS that avoids extraneous concentration losses.\n\n- **Analysis-level scaling (Sec 4.1, Lemma 5):** A novel way to manage the fluctuations of feasible sets for TS methdos in SLBs. Previous analyses completely break due to this issue.\n\n- **Resampling** ↔ Posterior-Quantile Connection (Sec. 5): A new insight connecting resampling in R-COLTS to posterior quantile methods, providing an efficient, scalable analogue for linear bandits.\n\nThese innovations jointly deliver the **first** TS algorithm for SLBs with unknown constraints. These use only LP oracles while matching the best known regret, and are practically fast and good. Reviewer cvX7 explicitly notes how our analysis goes substantially beyond existing work, and how the ideas \"might be more broadly relevant,\" supporting a higher rating. \n\n---\n\n## On the Terminology and Justification of NP-Hardness (Q2, Q3, Q4)\n>“Problems are NP-hard, not algorithms” and “NP-hard constraint?” \n\nWe thank the reviewer for the detailed questions on our use of \"NP-hard.\" While we used it as shorthand, our claim is technically correct, as the prior methods in question rely on solving a worst-case NP-hard oracle. Below, we provide the justification before proposing specific revisions for clarity.\n\n**1. Justification of Worst-Case Hardness:**\n>“Are you sure every instance of the NP-hard problem occurs in OPT-PESS / DOSS?”\n\nYes, one can encode every instance of an NP-hard problem into the optimization problem these need to solve. The core of this issue is already identified in our paper (line 518, \"...nonconvex due to the objective\").\n\n1. **The Core Hard Problem:** Even the **unconstrained OFUL** has this issue. OFUL picks action by solving a type of **bilinear program**. As discussed in lines 511–521, this is equivalent to solving \n   $$\n     \\max_{a\\in\\mathcal{A}}\\hat{\\theta}^{\\top}a +\\omega \\\\|a\\\\|_{V^{-1}}.\n   $$\n\n2. **Known Hardness:** By just setting $\\hat\\theta = 0$ and $V,\\mathcal{A}$ as needed, we can clearly encode **Positive-Definite Quadratic Maximization (PDQM)** into this problem. This class of problems is known to be NP-hard even if $V = I$ and $\\mathcal{A}$ are polytopes [Sahni ’74; Pardalos & Vavasis ’91].\n\n3. **Reduction:** The prior safe methods **OPT-PESS** and **DOSS** extend OFUL, as detailed in lines 511-537. If we set $\\alpha$ very large, the extra constraints are inactive, and we get back to the hard bilinear program underlying OFUL.\n\n**2. Proposed Revisions for Clarity:**\n\nWe will revise the imprecise shorthand to be more explicit:\n\n* **Line 33 (\"NP-hard constraints\"):** We will rewrite this to clarify it refers to constraints arising from bilinear inequalities, which defines a nonconvex set where checking feasibility—the recognition instance of the problem—is NP-hard.\n* **Lines 84 & 526 (\"NP-hard method\"):** We will change this to state that **DOSS** is an \"inefficient method\" that \"relies on an oracle that is NP-hard in the worst case.\"\n\n\n\n### Randomization and Average Case\n> \"as the “hard” problems...are randomized, and,..., the average case complexity of these methods might be polynomial\"\n\nYour point does not apply to these prior methods in a way that lets them escape worst-case hardness.\n\n- **Worst-Case vs. Average-Case:** Our claim is strictly about **worst-case** complexity. We make no claims regarding the **average-case** complexity, which (due to connections to PDQM) remains a challenging open problem.\n\n- **Deterministic Nature:** The algorithms in question (OPT-PESS, DOSS, OFUL) are **deterministic** given the history. For them, “randomness” in the optimization problem comes from the data, not from internal randomization in the algorithm itself. Even with that, at $t = 1$, we have $V_1 \\propto I, \\hat\\theta_1 = 0$, so we get the worst-case hard problem of optimising $\\\\|a\\\\|$ over $\\mathcal{A}$.\n \n### Strength of our contribution\n\nThis context highlights the primary motivation for our work. Our **COLTS** framework is specifically designed to **bypass this computational hardness entirely** by using only efficient LP or convex‐programming oracles. This theoretical advantage provides significant practical benefits, making our methods up to **18× faster** with up to **3× smaller regret** in our simulations (Section 6, pg. 9, Figure 2).  **R-COLTS is the first efficient soft-enforcement algorithm**, offering a practical alternative where none previously existed.  \n\n---\n\n## Other Questions\n\n**Q5**  *\"Line 119: Why is the... as normalization across different costs does not seem natural\"*  \nFirst, $\\Phi^i$ only encodes one constraint. This is **not** mixing across different costs. \n\n- This condition is **standard in SLBs** - all papers on this subject assume something like this (explicitly see [GCS24, PGB24]). Bounds on parameter norm are needed to run Thm 2. of [APS11], and have been standard since then. The $\\le 1$ in the assumption can be relaxed to $\\\\|\\Phi^i\\\\| \\le R^i$, but this clutter without meaningfully changing our results. \n\n- BwK is often set up as a linearization of a multi-arm bandit structure (and $\\mathcal{A}$ is a probability simplex)---this is the case in both paper you mention, for instance. In MABs it is more natural to just constrain each cost of each separately, which BwK then inherits.\n\n\n\n**Q6**  *Definition 2: What are $\\eta$ and $H^i$?... here.*\n\n- Line 134 preceding Def. 2 states that $\\mu$ is law on $\\mathbb{R}^{1 \\times d} \\times \\mathbb{R}^{m \\times d},$ and $(\\eta, H) \\sim \\mu$. These symbols are used very heavily and consistently in the paper. The glossary in sec. A also lists them. Since $H$ is a matrix, $H^i$ denotes its ith row, as mentioned in the notation paragraph (line 101). \n    -Nevertheless, to help readers avoid this confusion, we will add a sentence to the notation paragraph highlighting what $\\eta, H,$ and $\\mu$ denote. \n- Lemma 3: thanks for pointing this. We will rewrite separating out the notation $M_t(a)$ into its own dedicated definition to make this easier to parse. \n\n**Q7**  *What... to convex non-linear constraints?*\n\n- For general convex bandits, TS itself is not an effective method for $d > 1$, and results for $d = 1$ are also very recent (see remark 8.iii on page 114 of Lattimore 2024). Related algorithms like IDS need to be extended to SLBs to handle convex bandits, and we think our work is the first step in making this happen.\n- Under Eluder-type assumptions, R-COLTS should extend without problem. S-COLTS needs some sort of convexity to work. Beyond these, there is no statistical issue in extending them. However, even here, careful thought is needed regarding computation: the perturbed objectives and constraints can be quite complex, so it is not clear what kind of optimization oracle one needs. \n\n**Q8**  *What is the connection with the BwK literature...*   \nWe cited some of the early papers on BwK, and discussed the basic distinction in line 496. We will discuss this further here.  \n\n - As is well-established [PGB24, PGBJ21, GCS24, CGS22], the main difference (line 496) is in the roundwise metric $\\mathbf{S}\\_T = \\sum (\\textrm{violation}(a\\_t))\\_+$ versus the aggregate metric $\\mathbf{A}\\_T = \\sum \\textrm{violation}(a\\_t).$ Control on $\\mathbf{A}\\_T$ does not directly control $\\mathbf{S}\\_T$.\n \n- Cited papers\n    - In [SZSF22], you may be referring to Thm C.1, which says that $\\mathbf{A}\\_T \\le 0$. This does not mean $\\mathbf{S}_T = 0$. Indeed, note that $\\mathbf{S}_T = 0 \\iff \\forall t, \\Phi\\_\\* a\\_t \\le \\alpha$, i.e., each played point over the trajectory is feasible. We are unaware of any BwK method with such a guarantee. \n    - [BCCF24] do give a $\\sqrt{KT}$ bound on $\\mathbf{S}_T$ in the stochastic case for finitely many arms. It is not obvious that this extends to our SLB setting (e.g., what if $\\mathcal{A}$ has $d^{10}$ vectors, or contains a ball?).\n\n- For MABs, [CGS22] point out with a simple example that safe MABs are not equivalent to BwK, and there are instances where any good BwK method gets linear violations in the SLB setting. This is because the underlying solution concepts are distinct (linearized in BwK, not in safe MABs). Similar issues should affect the nonlinear case. Given these obstructions, some nontrivial work is needed in developing the generic connections between these two models.\n\n\n---\n\n**References beyond the submission**\n\n- Sahni, S. N. (1974). *Quadratic maximization over a polytope.* SIAM Journal on Computing.  \n- Pardalos, P. M. & Vavasis, S. A. (1991). *Quadratic programming with one negative eigenvalue is NP-hard.* Journal of Global Optimization.  \n- Lattimore, T. (2024). Bandit convex optimisation. arXiv preprint arXiv:2402.06535."}, {"review_id": "IjgcNzrE4a", "reviewer": "Reviewer_z1Dm", "summary": "This paper considers the safe linear bandits problem, where the goal is to minimize the regret subject to unknown linear constraints. The paper proposes a sampling-based framework--constrained linear Thompson Sampling--that perturbs the empirical estimates and selects actions by solving a perturbed linear programs. Under the hard constraint with a known safe action, it proposes S-COLTS and achieves $\\tilde{O}(\\sqrt{d^3 T})$; under the soft constraint, it introduces R-COLTS and achieves the same upper bound. Experiments show that COLTS matches or improves upon the regret of prior methods while dramatically reducing computational cost.", "questions": "- Is it possible to derive problem-dependent bounds on the regret and risk, i.e., the bounds will include some instance-dependent parameters like the mean gaps and the feasibility gaps of the arms? \n- Is it possible to generalize the algorithm to the combinatorial semi-bandits problem, where the hard/soft constraints are required for the pulled arms?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- This paper extends the Thompson sampling to the constrained linear bandits problem. The design of the coupled noise is novel and practically important. \n- Both COLTS algorithms avoid the complex optimization problems, yielding significant speedups compared to the baselines.\n- Theoretical guarantees are provided for both the regret and risk, matching or improving over the previous works.\n\n\n**Weaknesses**\n\n- In definition 2, should $B$ be a non-increasing map?\n- While I appreciate the authors efforts in expanding the analysis, some sections (e.g., look-back scaling) are intricate and could benefit more from additional high-level intuitions.", "was_revised": true, "final_justification": "This paper adopts Thompson sampling to deal with constrained linear bandits problems under the soft/hard constraint. The proposed algorithms enjoy theoretical guarantees and are practical. It also matches or improves over the previous works. It is of interest to the community.", "rebuttal": "Thank you for your work, and for recognizing the novelty and strengths of our contributions. \n\n### Response to Issues identified as weakness:\n\n------\n**Reviewer: In Definition 2, should B be a non-increasing map?**\n\nDef. 2, yes, it should be non-increasing, thanks for your careful reading. However, we are unclear why this is listed as a weakness of the paper. We would appreciate if you could clarify this point.\n\n------\n**Reviewer: some sections (e.g., look-back scaling) are intricate and could benefit from additional intuition**\n\nLet us provide high-level intuition that is embedded in the various lemmas. We will use the extra space in the final version to elaborate on this intuition.\n\n**Take-away:** Look back to the last *under-explored* action to control regret; scale that action just enough to satisfy today’s uncertain constraints.\n\n- **Core Idea: Link Regret to Information Gain.** Instead of analyzing regret at each step in isolation, we link the regret of our current action to the last time we took a good exploratory action---one that was unsaturated.  An unsaturated action is one where uncertainty is higher than the gap $(\\Delta(a) \\le M_t(a))$, meaning we learn a lot from taking this action. If all actions were unsaturated, then $\\mathbf{R}_T = \\sum \\Delta(a_t) \\le \\sum M_t(a_t),$ and  $\\sum_t M_t(a_t) = O(\\sqrt{T})$ (Lemma 3) leads to regret control. Methods like OFUL ensure unsaturation always. In TS this does not happen at all $t$, so we need to link the regret at time $t$ to information seen at previous times. \n\n- **The Look-back without unknown constraints**\nTo make things clear, first consider look-back for vanilla TS (so, $\\rho_t = 1$ always, and $b_t = a_t$). At any time $t$, we \"look back'' to the last time, $\\tau(t)$, that we played an unsaturated action. There are two steps\n    - First, we bound $\\Delta(a_t)$ in terms of $\\Delta(a_{\\tau(t)})$ and $M_t$-terms. \n        - By linearity, $\\Delta(a_t) = \\Delta(a_{\\tau(t)} +  \\theta_*^\\top(a_{\\tau(t)} - a_t).$ To control the extra term, we can pass to $\\tilde\\theta_t^\\top(a_{\\tau(t)} - a_t)$ by paying a $M_t(a_t) + M_t(a_{\\tau(t)})$ concentration term (Lemma 3). This is like line 213.\n        - Now, by definition of $a_t$, it optimises $\\tilde\\theta_t$, so $\\tilde\\theta_t^\\top (a_{\\tau(t)} -a_t) \\le 0$. This is key.\n        - Next, using unsaturation, $\\Delta(a_{\\tau(t)}) \\le M_{\\tau(t)}(a_{\\tau(t)})$.\n        - Heuristically, $M_t \\approx M_{\\tau(t)}$. This leaves us with a bound of $\\mathbf{R}\\_T \\le 2\\sum_t M_{\\tau(t)} + \\sum_t M_t(a_t)$. **This is the equivalent of Lemma 5**. \n   - The second step is bounding the look-back sum $\\sum_t M_{\\tau(t)}(a_{\\tau(t)}).$ This relies on frequency of unsaturation, and **is the same as Lemma 6**. \n- **Handling unknown constraints via scaling** Now, we define unsaturation in terms of the $b_t$s (it is hard to show $a_t$s are unsaturated often), and scale these down. Handling these needs two extra ingredients.\n    - **Handling $b_t \\to a_t$ scaling**. We need to get from $\\Delta(a_t)$ to $\\Delta(b_t).$ Doing this efficiently requires control on $\\sum (1-\\rho_t)$ (line 201). Also, using unsaturation means that we need control on $\\sum \\rho_t M_t(b_t)$. This is discussed in line 202, and in detail in Lemma 19.\n    - **Handling fluctuating constraints** Now, we can again pick up an informative $b_{\\tau(t)}$ like above. But this point need not be feasible for the current perturbed constraints $\\tilde\\Phi\\_t$. This breaks the key inequality used for Lemma 5 before. We handle this by scaling $b_{\\tau(t)}$ again to make it feasible for $\\tilde\\Phi\\_t$. \n         - This introduces other factors that need to be managed $\\sigma_{\\tau \\to t}.$ This is done by relating them to $\\rho_\\tau$. \n    - These two together give us the effective version of Lemma 5. Then Lemma 6 works basically the same way as in the unconstrained case. \n\nIn the paper, this combined scaling and look-back argument is the core of the proof of Lemma 5 (pg. 6). The properties of the primary scaling factor, $\\rho_t$, which are crucial for this analysis, are controlled via the bounds in Lemma 19 (pg. 21). To make the exposition clearer, we will break it apart like the above, and also move a version of Lemma 19 to the main text.\n\n-------\n### Reviewer Questions\n\n**Q1:** Is it possible to derive problem-dependent bounds on the regret and risk, i.e., the bounds will include some instance-dependent parameters like the mean gaps and the feasibility gaps of the arms? \n\n- In continuum linear bandits (LBs), instance dependent bounds arise when $\\mathcal{A}$ is a polytope. Let's discuss this setting. \n  - For SLBs, surprisingly, [GCS24] showed that even if $\\mathcal{A}$ is a polytope, we cannot have both $\\mathbf{R}\\_T$ and $\\mathbf{S}\\_T$ be $o(\\sqrt{T})$ in general, and at least one of them must be $\\Omega(\\sqrt{T})$, even given instance-specific information. \n  - For hard enforcement, since $\\mathbf{S}\\_T = 0,$ regret must be $\\Omega(\\sqrt{T})$. Note that the regret bounds in hard enforcement are all actually instance-dependent, through the $\\mathcal{R}(a\\_{\\mathrm{safe}})$ term. It is possible that this can be refined, although we do not know any such results in the literature. \n  - For soft enforcement, this is a subtle question. DOSS does get polylog regret (and $\\sqrt{T})$ risk), but this strongly uses the OFUL style bilinear optimisato way to pick $a_t$. It is unclear how to show such a bound without this. If you are familiar with [GCS24], the hard case is when only optimal BISs are activated.\n      - However, in section 6, we saw that the regret of R-COLTS is closer to $\\sqrt{T}$ than $\\sqrt{d^2 T}$. This suggests that at least $O(\\sqrt{T} + \\mathrm{poly}(d) \\mathrm{gap}^{-1})$ bounds may be possible, although this is beyond the scope of the current submission. We mention this in line 1192.\n- For finite-action problems, yes, gap dependent polylog bounds should be possible for soft enforcement, but we did not work these out. For hard enforcement, one needs to linearise into line segments to get star convexity [PGB24], and then the lower bound prevents $o(\\sqrt{T})$ again.\n\n**Q2:** Is it possible to generalize the algorithm to the combinatorial semi-bandits problem, where the hard/soft constraints are required for the pulled arms?                \n\nWhile this is not something we have thought about very much, in principle, yes, nothing stops these design principles (both the OPT-PESS style and COLTS) from being applied to richer feedback settings than just bandits. Specifically with semi-bandits, it is worth exploring what kind of constraints make sense (should we constrain the full action in some aggregate way? Or should the individual choices be curtailed (e.g., some particular link is unsafe, and so should be avoided always, et c.), and the structure of the constraint may make design/analysis of good methods challenging."}, {"review_id": "NP7oXyPSsL", "reviewer": "Reviewer_cvX7", "summary": "This paper introduces algorithms for safe linear bandits that utilize Thompson sampling-like approaches. The algorithms are evaluated according to their regret (cumulative difference in total reward between optimal actions and played actions) and risk (cumulative constraint violations of played actions). They first introduce an algorithm that ensures $\\tilde{O}(d^{3/2} \\sqrt{T})$ regret and zero risk (i.e. constraint satisfaction for all rounds) under the assumption that there is a known point that is strictly feasible. They then introduce a method with $\\tilde{O}(d^{3/2} \\sqrt{T})$ regret and risk that doesn't require the aforementioned assumption. Notably, both of their methods apply a Thompson sampling to both the reward function and the constraint function. They also provide some numerical comparison of their work with some existing work.", "questions": "Some minor points:\n- In line 122, it says that \"we also assume that $m/\\delta = O(poly(d))$ when stating theorems.\" Can you provide some clarification on this? To my knowledge, it is common to take $\\delta = 1/T$ to get expected regret guarantees, which would violate that assumption.\n- I think the presentation of Table 1 (first four rows) is misleading in that it sort of hides the assumption that the known safe action $a_{safe}$ is strictly-feasible (otherwise the given regret bounds are void).\n- Slater's condition is defined in the caption of Table 1, but I don't see that it is used in the table.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Their algorithms only require an LP per a round, versus prior work that requires an SOCP in each round with the same regret. As such, one expects that there is often substantial computational benefits to their methods.\n- The algorithm design combines some existing ideas in a new way, and introduces some new ideas. For example, it combines a scaling approach similar to what is used in [HTA24] and a linear Thompson sampling-type approach [AG13]. The resampling approach (Algorithm 2) appears to be new to the literature.\n- The analysis goes substantially beyond existing work, as combining the aforementioned algorithm designs makes the analysis substantially more difficult. The analysis ideas introduced in the paper might be more broadly relevant.\n- Relevant work is thoroughly discussed.\n- The paper does a good job of presenting the key challenges that arise in the analysis and design of the algorithms.\n\nWeaknesses:\n- The paper is quite dense, which sometimes made it difficult to follow. I expect that this will be relieved somewhat with the extra page that is allowed for the final version.\n- I discuss some specific minor points in the questions section.", "was_revised": true, "final_justification": "I appreciate the authors addressing my minor concerns. I maintain my score, and am in favor of the paper being accepted.", "rebuttal": "Our thanks for your work. We are pleased that you recognise the strengths of contributions, and the novelty of our analysis techniques.\n\n\nWe agree that the paper can get dense, especially in the presentation of S-COLTS and the look-back analysis. As you mentioned, if the paper is accepted, we will use the extra space provided to address this. \n\nWe added a high-level sketch of the look-back analysis in the rebuttal to reviewer z1Dm, and following that, we currently plan to make these changes: \\\n(i) add a structured plan of how the analysis proceeds; \\\n(ii) separate out summability of $(1-\\rho_t)$ and $\\rho_t M_t(b_t)$ into a lemma; and, \\\n(iii) decouple the explanations of the look-back part of the analysis from the scaling of $b_\\tau$ to ensure that each part can be clearly explained without the other interfering. \\\nWe would appreciate it if you have suggestions about other aspects to focus on most, or comments about this plan.\n\nQuestions\n- Thanks for catching this, it should be $\\mathrm{poly}(d,T)$. The point is that we often write $\\tilde{O}(\\sqrt{d^3 T})$, but the bounds are actually $\\tilde{O}(\\sqrt{d^3 T + d^2 T \\log(m/\\delta)}),$ and we need to say why we drop the second term.\n- This is a fair point, and we will specify that $\\Gamma(a\\_{\\mathrm{safe}}) > 0$ is needed. We note that such an assumption is necessary for hard enforcement (intuitively, if $a\\_{\\mathrm{safe}}$ is on the boundary of the feasible set, then we cannot be sure of playing any other action and retaining safety; also see [PGB24]).\n- This only comes up in line 49 (and for the E-COLTS method of section I.2), but you are right that it doesn't belong in the caption."}]

Author rebuttal:

Meta-review: This paper studies constraint linear bandits and proposes, to my knowledge, the first TS based algorithm for this problem.

TS is of practical interest in linear bandits because it has favourable computational properties compared to UCB style algorithms in problems with continuous action sets e.g. general polytopes. 

Their method matches the regret of the best known, efficient method when a safe action is known and provides the first such method for unknown soft-constraints. They pay a root(d) price over the best UCB based algorithms, which is typical for TS. Such a gap exists even without constraints, but TS is still highly of interest due to the aforementioned computational benefits.

 The excitement of most reviewers is fairly lukewarm, but it is a solid accept in my opinion.
Decision: Accept (poster)