Feasible Action Search for Bandit Linear Programs via Thompson Sampling
Authors: Aditya Gangrade
Aldo Pacchiano
Clayton Scott
Venkatesh Saligrama
Venue: ICML 2025 poster (2025)
Keywords: Safe Bandits
Linear Bandits
Thompson Sampling
Primary area: theory->online_learning_and_bandits
TL;DR: An efficient method based on Thompson Sampling to find feasible actions for LPs with bandit feedback

Abstract: We study the 'feasible action search' (FAS) problem for linear bandits, wherein a learner attempts to discover a feasible point for a set of linear constraints $\Phi_* a \ge 0,$ without knowledge of the matrix $\Phi_* \in \mathbb{R}^{m \times d}$. A FAS learner selects a sequence of actions $a_t,$ and uses observations of the form $\Phi_* a_t + \mathrm{noise}$ to either find a point with nearly optimal 'safety margin', or detect that the constraints are infeasible, where the safety margin of an action measures its (signed) distance from the constraint boundary. While of interest in its own right, the FAS problem also directly addresses a key deficiency in the extant theory of 'safe linear bandits' (SLBs), by discovering a safe initialisation for low-regret SLB methods.

We propose and analyse a novel efficient FAS-learner. Our method, FAST, is based on Thompson Sampling. It applies a _coupled_ random perturbation to an estimate of $\Phi_*,$ and plays a maximin point of a game induced by this perturbed matrix. We prove that FAST stops in $\tilde{O}(d^3/\varepsilon^2 M_*^2)$ steps, and incurs $\tilde{O}(d^3/|M_*|)$ safety costs, to either correctly detect infeasibility, or output a point that is at least $(1-\varepsilon) M_*$-safe, where $M_*$ is the _optimal safety margin_ of $\Phi_*$. Further, instantiating prior SLB methods with the output of FAS yields the first SLB methods that incur $\tilde{O}(\sqrt{d^3 T/M_*^2})$ regret and $O(1)$ risk without a priori knowledge of a safe action. The main technical novelty lies in the extension of Thompson Sampling to this multiobjective setting, for which we both propose a coupled noise design, and provide an analysis that avoids convexity considerations.

Feasible Action Search for Bandit Linear Programs via Thompson Sampling
Aditya Gangrade'
Aldo Pacchiano 12
Clayton Scott 3 Venkatesh Saligrama
Abstract
unknown objective and noisy measurements of the quality of actions. The generality of this setup lends itself to many applications in, e.g., machine learning, control system, and resource allocation. However, the standard theory assumes that the constraints of these L.ss are known, which is unreal- istic in a multitude of applications in these domains, This motivates the safe linear bandit (SLB) problem, wherein the learner attempts select actions with high reward while not violating unknown (linear) constraints at any time using noisy feedback of the rewards and constraint levels.
We study the 'feasible action search' (FAS) prob- lem for linear bandits, wherein learner attempts to discover feasible point for of linear con- straints &. a 2 O, without knowledge of the ma- trix +. E T A FAS learner selects se- and uses observations of the form & a.a; + noise to either find a point with nearly optimal 'safety margin', or detect that the constraints are infeasible, where the safety mar- gin of action measures its (signed) distance from the constraint boundary. While of interest in its own right, the FAS problem also directly addresses a key deficiency in the extant theory of 'safe linear bandits' (SLBs), by discovering a safe initialisation for low-regret SLB methods.
quence of actions
The recent literature has described several methods that ad- dress this problem in a strong sense, ensuring low regret whilst never violating safety, i.e., playing an infeasible ac- tion. Such an algorithm must be initialised with safe action, Osafe- begin with, in order to 'seed' the method with an initial safe region to explore over. Moreover, the safety mar- gin of Gsafe (see below) quantitatively affects regret bounds, and so must be large to ensure good performance. However, no prior method discusses how to get hold of such a point. This not only limits the applicability of these algorithms,, but also hides their true safety costs, since the discovery of such Asafe would, with high likelihood, require playing some unsafe actions. We address this question by designing an efficient algorithm for feasible action search (FAS).
We propose a novel efficient FAS- based Thompson Sampling (TS), FAST, which ap- plies a coupled random perturbation to an es- timate of Φ., and plays a maximin point of a game induced by this perturbed matrix. We prove that FAST stops in (dd /s2 M2) steps, and incurs (dd /IM.I) safety cost, to either correctly detect infeasibility, or find a point Gout that is at least (1 ( where M. is the optimal safety margin of 4.. Further, instantiating prior SLB methods with Gout yields the first SLB methods that incur Ö D(vd/TMM3 regret and O(1) risk without priori knowledge of a safe action. The main technical novelty lies in the extension of TS to this multiobjective setting, for which we both propose a coupled noise design, and provide an analysis that avoids convexity considerations.
Concretely, consider the program max.e. 0_T a P.a 2 or where the reward parameters 8, E Rd and constraint param- eters &, E g are unknown, while AA is a known convex domain. The safety margin of an action a E A, M(a) == min A=1 A T..a, measures a 'signed distance' of from the constraint boundaries. Given E, 8 (0, 1), FAS learner selects a sequence of actions {ar} C A, and accu- mulates information by observing noisy risk measurements S = Φ.a; + noise in response. This continues until a stopping time, т, at which point the learner either
1. Introduction
declares infeasibility, i.c., that An (#,a 2 = 0, OR outputs an action Gouts and 'certificate' Maut such that
Linear bandits capture online approach to the fundamen- tal dacision-making paradigm of linear programs (LPs) with
M M( 2 Mout: and Mout 2 M).
where M. := max (a) is the optimal safery margin.
'Boston University "Broad Institute of MIT and Harvard e Unniversity of Michigan. Correspondence to: Gangrade <gan- mande@bu.edu>.
The goal is to minimise т, while ensuring correctness with probability at least - 8. Ideal methods should adapt their stopping time to the unknown M,, ineur limited 'safety costs' during exploration, and be computationally efficient.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Feasible Action Search for Bandit LPs via Thompson Sampling
Of course, the FAS problem is of interest in its own right, beyond applications to SLBSs, with applications to domains such as control, manufacturing, and resource allocation, where practitioners must balance many objectives with one solution. For instance, when designing a manufacturing process, a FAS-learner would find a set of process parame- ters that balance manifold cost, efficiency, and quality con- straints. The parameter E serves as dial between the re- silience of such parameters to process perturbations, and the cost of identifying the feasible action. In particular, we note that setting = 1 recovers safe action with minimal search costs, but offers no nontrivial safety margin.
[(] == m 0 a, execute gradient- based analysis showing that if the noise ensures that the "global optimism event' Gj :- {0, J(O.) 2 J(O.)} occurs at constant rate, then the regret is bounded. They further exploit the convexity of J(Ø) to show that for certain concrete choices of noise law, this Gj is indeed frequent enough.
In our multiobjective scenario, the role of (0) is instead played by [()) := maX min A Da. However, this K is not convex in Φ, which precludes both the gradient- based approach to showing progress in learning. as well as the convexity- beasxiit--baeed analysis for the frequency of optimism.
Our analysis of FAST is instead based on a convexity-free approach using the local optimism event
Our Contributions. We exploit the design of a recent (in- tractable) bandit feasibility test for LPs to propose novel efficient method, 'Feasible Action Search via Thompson Sampling' (FAST), to address the FAS problem for linear constraints. FAST operates by constructing regression es- timates of Φ.,, and playing a maximin point of the matrix game induced by randomly perturbing this estimate. This uses Ó(LP-time) computation per round, where LP-time the cost of optimising a linear objective under m linear constraints over A to constant error. Stoppage is driven by estimates that bound the value of Ma, and we pick the average of played actions Gout-
L == ( min A Tā 2 M.}, A
where a, denotes maximin point of the matrix game in- duced by p. In words, L is the event that after perturbation, the safety margin of a. increases. We first argue, via a di- rect analysis of the value, that as long as the chance of L, is (21), simple test statistic maintains efficient bounds on the true value M., enabling fast and reliable stoppage. Next, we provide a generic construction of a coupled noise that ensures that P(L, history) 2 0.15. Concretely, this noise design applies identical scaled spherical perturbations to each of the rows of an estimate of 2.. and we show that L is frequent under this noise by directly analysing the be- haviour of the perturbed program at a., is interesting to note that in this local analysis, the natural noise design of perturbing each row of an estimate of 4, independently is hard to control, and crude analyses only yield ineffective 2 2-0(m) bounds). This local optimism approach may be of independent interest, since it may apply to Ts-based algo- rithms in other scenarios with nonconvex value functions.
We show that FAST is reliable, and stops in a near- optimal Ö( M3) rounds if the instance is feasi- ble, or Ö(Vdd/ //M.//MM))) steps if it is infeasible. We fur- ther show that FAST accumulates a limited safety cost of S. = O MM.), where S. := E- min; 4 +)++ measures the extent of constraint violation per round. In each case, the dependence on m/5 is polylogarithnic.
Further, due to its limited safety cost, instantiating prior methods for SLBs with the output of FAST yields the first SLB algorithm that, without priori knowledge of a safe action, attains ((VdTT/M3 regret (see $2), and O(P/M.) = 0(1) safety costs in rounds. This not only removes the assumption of knowing asafe, but also improves the regret by factor of M./ /M (dsafe), which may be arbi- trarily large, but at a (T-independent) safety cost.
1.1. Related Work
Best Arm Identification (BAI). The FAS problem is in- timately related to the fixed-confidence BAI problem for linear bandits. Typically. this is formulated for a finite A, and the focus is on identifying the best arm exactly using experimental design based methods (Soare et al., 2014), Several asymptotically optimal (as the confidence parameter 8 + 0) methods have been proposed for this problem (c.g. Fiez et al., 2019; Jedra & Proutiere, 2020; Degenne et al., 2020; Wang et al., 2021). FAS, however, operates over a con- tinuum of actions, which renders the 2((A) computation incurred in these methods untenable (note that any reason- able discretisation is of size 20(4)). The problem of finding s-optimal action in continuum linear bandits has received less attention, but is usually approached by either sampling from a uniform spanner to directly estimate the parameters (Jedra & Proutiere, 2020), or by playing a low-regret algo- rithm. Our approach is along the latter lines, but with key
Technical Novelty. As with any method based on Thomp- son Sampling (TS), FAST operates by drawing noisily per- turbed estimates of the unknown parameter, .t and acting "greedily" according to program induced by this t The main challenge is to design an effective distribution on the noise, and to prove the associated bounds.
The influential approach of Abeille & Lazaric (2017) for analysing low-regret linear TS is a natural framework to adopt for this task. However, this approach is rooted in convexity, and further does not consider multiple objectives together. In detail, Abeille& & Lazaric (2017) exploit the con- vexity of the value function of an LP with given constraints,
2

---

Feasible Action Search for Bandit LPs via Thompson Sampling
differences: we need to deal with finding a near-maximin action for many objectives, our approximation guarantees are multiplicative in the optimal cost rather than additive, and we need to verify the feasibility of the instance. We note that multiplicative approximation is necessary-sinee M. is unknown, a E-safe action for a fixed e may even be unsafe. Such multiplicative guarantees have been studied for multi-armen bandits (Michel et al., 2022). but we are un- aware of a linear bandit treatment. We note the recent work of Li et al. (2024b), which proposes TS-based sampling strategy for BAI in finite A linear bandits. While we do not use this approach, adapting it to FAS over continuous A is an interesting direction.
Feasibility Testing. A closely related work ours is recent study of subset of the authors and A. Gopalan (Gangrade et al., 2024b) on feasibility testing of unknown LPs, which is a 'testing version' of our estimation problem. This work uses a frequentist low-regret method based on 'OFUL' (Abbasi-Yadkee estimate of the sign of M,, using which they proposed the 'ellipsoidal optimistic-greedy test,' EOGT. Of course, using a version of our Lemma 7, in principle EOGT can also be used for the FAS problem. However, this method is computationally intractable, requiring, in each round, the learner to solve the program
et al., 2011) to design a reliable
max max min X Da, DEC aEA AEA
Best Safe Arm ID (BSAT). Naturally, the FAS problem is intimately related to the problem of discovering a s-optimal feasible action (e.g. Katz-Samuels & Scott, 2019; Camilleri et al., 2022; Carlsson et al., 2023) for an unknown objec- tive and constraint. Again, most of the literature focuses on finite| |A], often in the multi-armed bandit setup, with additive guarantees of both the optimality and safety of ac- tions. Notice that under such an additive guarantee the latter scenario, the selected action can violate the constraints by up to e. Instead, we study a continuous A, and, with high probability, necessarily output safe action. Further, we note that the FAS and BSAI problems have distinct struc- ture. For instance, the optimal action in BSAI typically lies close to (if not at) the boundary of the fcasible set, and thus simply verifying the safety of such an action requires huge number of samples. In contrast, in FAS the output lies deep within the feasible set, and solving the FAS problem needs correspondingly fewer samples.
where is a (nonconvex) confidence set for the constraint parameters, structured as a union of polytopes (see $2.1). This problem is in fact NP-hard even if C were convex set, and standard Lı-based relaxations (Dani et al., 2008) need the learner to solve (2d) matrix games in each round. Our procedure FAST both extends the insights of this work to identify safe actions, but also does so efficiently. In the process, we obtain an efficient version of this test as well, which can be obtained by passing & = 1 to FAST. In passing, we note that this feasibility testing problem is inti- mately related to the 'minimum threshold testing problem' (Kaufmann et al., 2018), and refer the reader to Gangrade et al. (2024b) for a detailed discussion.
Low-Regret SLBs have attracted attention in the recent lit- erature, and a many low-regret methods no safety violations have been proposed (Amani et al., 2019; Moradipari et al., 2021; Pacchiano et al., 2021: 2024; Hutchinson et al., 2023). These methods fundamentally require the priori knowl- edge of a safe action asafe such that M (dsate) > O, and (under efficient relaxations) the ensuing regret bounds scale as Ö(V /ddT/M (Assie)²). (asse. Our solution to the FAS problem not only eliminates this assumption, but also replaces the arbitrary M (Mssae) in the regret bounds by the optimal safety margin M., improving the resulting regret bounds, albeit at an (unavoidable) O(1) safety cost. The only methods that do not require an assumption of knowing asafe to begin with are known to violate constraints regularly, and only yield Ö (T) bounds on safety costs (Gangrade et al., 2024a).
Minimax and Pareto Bandits. FAST operates by exploit- ing that the FAS problem is equivalent to searching for a point that is near-maximin for the matrix game induced by 2., which naturally relates it to the problem of achieving maximin values in a low-regret sense that has attracted re- cent attention (O' (O'Donoghue al., 2021; Maiti et al., 2023; Li et al., 2024a). The extant literature again focuses the multi-armed bandit setting using UCB-style approaches (with 2((14) computation per round), while we study con- tinuous A. Further, the information structure in our study is different from these prior works, reflected in the fact that our bounds scale with log(m). while theirs scale as poly(m) Instead of searching for minimax point, number of works deal with multiobjectivityy by attempting to identify the en- tire set of Pareto-optimal actions (e.g. Auer et al., 2016). In our notation, this is the set of a E A such that 2,a 1 &,a' for all a' E A. This objective is very different from our setup- we only need to identify a single action, but this must be meximmax Note, of course, that the Pareto set may contain actions that are unsafe (and in the worst case, the entire frontier can be composed of unsafe points).
In passing, we note that the above SLB problem is distinct from the 'bandits with knapsacks' problem, wherein learn- ers may violate constraints in each round, but must satisfy long-term aggregate constraints (e.g. Badanidiyuru et al., 2013). An interesting point of contact in this literature lies in the use of primal- dual methods for such problems, which too require the use of a point with nontrivial margin (re- ferred to as a Slater parameter therein). Within this context, Castiglioni et al. (2022, $8) study a related method to iden- tify (or bound) such a Slater parameter, which is related to our FAS problem. We note, however, that this method is
3

---

Feasible Action Search for Bandit LPs via Thompson Sampling
focused initialising a primal-dual algorithm, and so treats this FAS problem very erudely. In particular, the method does not adapt its stopping behaviour to the size of M., nor obtains tight FAS guarantees, unlike our work.
to the learner round L. We will denote the historical filtration 5t-1 = af{(a,, R2, Ssy C.))sst sct), and 6; o (5::1 U {a,, C.J). The actions a, must be adapted to (55:-1
Thompson Sampling (TS). We refer the reader to Russo et al. (2018) for background on TS. For parametric prob- lems, the efficiency of TS has long made this approach attractive, with frequentist regret bounds in the linear setup first demonstrated by Agrawal & Goyal (2013). Abeille & Lazaric (2017) provide simplification of this analysis that most strongly informs our approach. Of course, these analy- ses are limited to single objectives, while our focus lies in finding a maximin point of a multiobjective problem. This introduces new challenges arising from the nonconvexity of the value function, and the need for a robust noise design. We address these by developing systematic convexity-free analysis that directly exploits the saddle-point structure of the optimal noisy value, and further describe a novel coupled noise structure to ensure frequent optimism.
In the feasible action search (FAS) problem, given e, e, e (0, 1), the learner selects actions, and at some point, deter- mines a stopping time, т. Upon stopping, the learner either declares the instance to be infeasible, or outputs an action Gout A, along with certificate Mout- We call FAS learner (e, 8)-reliable if with probability at least 1 6, (a) if M, < O, the learner declares infeasibility, and (b) if M. > 0, the learner ensures that M (Cout) 2 Mout 2 (1 - e) w.p. at least 1 - 6. The goal is to select actions and the stopping rule in a way that maintains reliability, whilst min- imising T (which is the number of samples used). We note that the reward information need not be utilised by a FAS learner. In addition to the stopping time, we will control the safety cost of exploration, S,, where for t E N,
S. = - min A +,0+)++
851
2. Problem Definition and Background
with (z)+ max(2, 0). Notice that S, penalises any ex- cursion outside of the feasible set, but playing within this set does not yield a reduction in S..
Notation. For E IRd, ||a||| denotes the Euclidean 2-norm. For PSD matrix M, ||e||ar := || ||M'/= />oll. An inequality a S b is said to hold under an event E if all S bli where 1E indicates E. Standard Big-O notation is used, and Ö hides polylog factors. Sd is the unit l2 sphere in Rd, and A the simplex. For a matrix M, M denotes its ith row. Gaussians are denoted W.
In the regret-control problem, given å E (0. 1), the learner's 's goal to ensure that w.p. at least 1 8, both the safety cost and the regret well-controlled, where, with OPT being the optimal value of the program, the regret is
R [(OPT a.)+:).
Setup. We are concerned with linear programs of the form max.e 10,,a a L.a 2 0}. where A C Rd is assumed to be a known bounded domain, while 0, E R o. E R.nxd are unknown reward and constraint parameters. The safe, or feasible, set is denoted S. == A n {T 2 0}. Note that S, may be empty. We define the safety margin of an action as M (a) := minxee" AT a. This is equal to minge [1:]] ( (D.a)', and thus captures the smallest 'slack' in the constraints at a if positive, and the greatest violation of them if negative. The optimal safety margin is
When discussing regret-control, we tacitly will assume fea- sibility, i.e., that S. := An (T_ S 0} + Ø.
Standard Assumptions. Throughout, we will assume the following conditions on the instance (0, A), and noise w. All subsequent results only hold under these assumptions. Boundedness: it holds that max([10. |Im max; || < 1,
and A C {a ||a|| S 1). SubGaussian noise: w, == (w (w;)T)T is centred and 1-subGaussian with respect to G, i.e., E(w, [,] = 0, and
M, := max M (a) mmxx min A T_aa. aEA A
aEAA
At E R=+1 E[exp(A ()))] S (1)
Note that M, may be positive or negative. If negative, then S. = 0. i.e., the instance is infeasible. Throughout, we use (a., X.) to denote a(ny) saddle point of this game. Nonzero constraint levels. We note that our setup of {$.a 2 0} subsumes the general case (Φ.a 2 a), since we can
If augmenting the dimension to handle nonzero constraint levels, boundedness only applies to the unknown parts of क.
2.1. Background
augment the dimension by one, include as a column of 2,, and include d=+1 = 1 as a constraint in A.
We include repeatedly used background on online linear regression, and on laws of iterated logarithms.
Play proceeds in rounds indexed by E N. At each 1, the learner picks an action 0g E A, and gets the feedback R₂ = 0_ wwf and S, = -baa-up where wff E IR and
Confidence Ellipsoids. We estimate the parameters 4, given h.-1 by 4, = arg ming Eese jda.- - S. + Σ, || |
The standard confidence set for T. is
w e R.m are noise. Let C. denote randomness available
(6) { V rows i, 1 Tdllv S (x)),
4

---

Feasible Action Search for Bandit LPs via Thompson Sampling
where V/2 = 1 Eest aga, and : == (222)g((m//)) + 1/4 log det Va)
Algorithm I Feasible Action Search via Thompson Sam- pling (F,
I: Input: e, E (0, 1), 14, law on m and A.
The first key result states that these confidence ellipsoids are consistent at all times.
2: Initialise: 50 < 23, To - 0, - 0, 0
3: while r < 0 do
al., 2011) Define the con- sistency event at time (ō) = { E ((()),, and (ō) == nezI Con((o). Under the standard assumptions, for all 5 E (0, T), (P(Con(8)) 2 1 - 6.
Lemma 1. Albbasi-Yakkon
4: Increment t and draw H₃ ~ μ independent of 5t-1-
5: L, +- 4 + (6 V-/22
6: Compute Xe, a, via (2).
7:
Play a,, and observe S..
T. t T-1 X1 St. (a)s t Eese as/t.
The following result is termed the elliptical potential lemma (Abbasi- Yadkori et al., 2011; Carpentier et al., 2020).
Update Bi( 0) as defined in Lemma 7.
10:
Ug - (T + B,t L1 + (.H Bi)/t.
Lemma 2. For any t, and any sequence of actions } lying in the unit ball, it holds that
11:
Uf < or (L, > (1 - E)U and U, > 0) then
12:
T T t.
13:
Uf > 0 then
laolly, 15 2 2og log det V s 2dtt log( + t/d).
14: Return Gout = (a) Mout Lr
15: Return "Instance is infeasible".
We will also need the following nonasymptotic law of iter- ated logarithms (LIL) (e.g. Howard et al., 2021).
which is used to determine stoppage.
Lemma 3. For any filtration (3e), & is a process adapted to Be that is conditionally centred and I Issubaaussinn, then
There are two important questions to address: how should one select μ4, and how should one select the stopping and decision rules to ensure both efficiency and reliability.
4J 10. (3:: Z,l (t.. S6 where Z. = Σ E. & (II 5) == / log(11 11 max(log t, 1)/5).
To this end, in $3.1, we describe a generic 'concentration- optimism' condition on μ., and show that under this condi- tion, the value of T. tracks the optimal safety margin in the sense that
3. Feasible Action Search via Thompson Sampling
T. E LM, + Be(u,, ō),
As previously discussed, our algorithm is inspired by the EOGT procedure of Gangrade et al. (2024a). This method uses low-regret algorithms for linear bandits to construct an approach to estimate the sign of the value of a matrix game. Our strategy is to apply this idea to construct a com- putationally efficient method by exploiting a randomised approach based on Thompson Sampling.
where B, is an adapted computable process defined below. Using this, in $3.2 we will describe a simple reliable stop- ping rule, which either detects that M, < 0, or continues sampling until (a); == Eeer az/t is an appropriately feasi- ble action. Next, in $3.3, we provide a generic construction of jas satisfying this CO condition, operationalising this de- sign. Finally, in $3.4, we use these properties to analyse the behaviour of the stopping time and the safety costs of FAST.
Our method, FAST is parametrised by law μ on R along with 6. FAST(H, e, 6), operates by first drawing noise matrix H₁ ~ p. independently of 5t-1, and construct- ing the perturbed constraint matrix
3.1. The CO Condition and the Tracking Inequality
As in prior studies of linear TS, the core insight exploit is that progress is made in learning whenever the perturbation is 'optimistic', i.e., the optimal perturbed value dominates the true value. Thus, it is enough to design a noise that ensures frequent optimism, while limiting blowups in errors due to the scale of these perturbations. For the FAS problem, we encapsulate these two aspects in the following condition.
T = (H,,t,)) == . + (()
(1)
Observe that the perturbation is aligned with the geometry induced by the historical information via wq V. v.1/2 Given
Tt we select both an action a, E A, as well as a vector d E r by solving the game
max min A TT.a. EEA m
Definition 4. Let B [0, 1] + R>0 be a map, and π e (0,1), Define the global optimism event
The action aj is played, and the ensuing safety feedback is used along with X, to construct the main statistic
Gr(5) : {1le : K K( 2 K(4.)}
Ft :- Σ X S.
where K( := max minxesm A Da. Recall the
event Con (8) = ( E ())) from Lemma I.
5

---

Feasible Action Search for Bandit LPs via Thompson Sampling
We say that distribution j on Rmxd satisfies B- concentration condition if & [0, it holds that p({H: : max || > B(E))) c.
Blu(G,)5s,: -ll |5) G.], and noting that ,(G,) 2 ((G)) - 8, since (u(Ball 2 11-60 -1-6,. 6,.
In more detail, for the single objective value J(0) o
Further, we say that μ.. satisfies oopptmmssm condition if 2 x con:
maX 0 a, prior analysis due Abeille & Lazaric We will succinctly say that is satisfies a (B, --O condition if both these properties are true.
46, 1, 1 Con:
(2017) rely on the convexity of J to bound (( - by
V.. (0.- 0e), where 6g is the perturbed objective, and 0g is an analogue of Q, The final step is to use the fact that (O,) = ar almost surely, which concludes the argument via the Cauchy-Schward inequality.
The concentration property above limits how far the pertur- bation can move : and thus, the size of のb - 4. under consistency. The event (ō) is a "global optimism' event, in that when P.- E (o)) the value of the game induced by T dominates the value induced by t. (which equals M.). Note that Gz( dependts on d through the (6) term in 4 in (1). The remainder of this section will derive key consequences of the CO condition, and we leave a generic construction of laws meeting 'good' CO conditions to $3.3.
In our case, the map K K($) is nonconvex', and we instead approach this question by directly exploiting the saddle point structure of K. This strategy should be useful in other scenarios with unknown constraints by exploiting the saddle point property of a Lagrangian (as long as norms of dual-optimal solutions are controlled).
The above is complemented by roundwise lower bound. Lemma 6. For all t, under (āll n (o),
Roundwise Tracking. The main utility of the CO condition the following key result.
M. 2 M(ae) 2 2. 2(1 (())),
Lemma 5. Let 6,- = min(x /2, 5/1(1 + 1)), and define the event (6) := {max, ||H||| S ((,.)). If u-satisfies a (B, -O condition, then for all t, under (5),,
Proof. Under the event in question, each row of e, Φ.
has Vy-norm bounded by S = (1 - ((d))) Now, by definition, M. 2 M(a)). Further, suppose M(as) = M(a:) T T.at. Since (az, Aτ) is a saddle point for T.,
M. S AT 0.a0+ + (B(5e)wr((
Ellla llv. 10: 19:--].
π
Proof Sketch. We defer most details to $A.1, and only high- light the main difference from the prior analysis of Abeille & Lazaric (2017). Using this approach, under Ball,
Taa) 2 AT T.a.
But, since [|(at))l || 1, we further have
M. - K ( S ()) K k( G.).
Maa)) T T. + Gelleelly. 2 x a.a Gellaell....
where te is the minimiser of (4) over the set & = ($(H,t,)) : max; || S B and G, = G, n (6). At this point, prior analyses use the convexity of the value function in terms of the unknown parameters, which fails for us. Instead, we take the following direct tack.
Tracking Inequality, The above roundwise results, coupled with concentration arguments, yield the main consequence of the CO condition for the FAS problem, which relate the behaviour of the statistic T to M. This is shown in $A.1.
Let (ūe, Xe) denote saddle point of & such that X, 0. = K K(o.). By the saddle point property, X h. I K(.)). By the same coin, X, 0.a0 2 2T D.a K ((..). So.
Lemma 7. Define the boundary process
Biln, 8) = (1+ (L+) (LII lla Ellaallla) Il
min( 1/2)
SSt.
K( k( S X7 ( 5.)at.
If u satisfies a (B, -) condition, and E (0, 1), then for 8, == min(7, (x, 6/u++)), with probability at least 1 46,
But, under G, C Ball,, each row of ~. Th has V/- norm at most 2B )or()) and thus [1 - o )orlo S 2 Buw Bwslldelll (see Lemma 11 in SA.1). Since || ||
FAST 5) ensures that simultaneously for all
Je + (1, 2 tM, 2 Σ M((a)) 2 2 -- -e((,)))
by Hoelder's ' inequality, we conclude that under Balle,
eSt
M.- k(Ø,) < (8 we (6][[laell 15.-1. G.).
legg,, consider the payoff (1 (1-2
2 2 1- over A = 2
2
as varies. Via direct computation (see $A.5.1). we find that K(z) + min(0, (2z)-1 - 1), which is nonconvex over any interval containing 2 = 1/2.
The conclusion follows by using the nonegativ- ity of ||aslly,+ to see that El[la= 1|llasill,--0s0 - [1 2
6

---

Feasible Action Search for Bandit LPs via Thompson Sampling
3.2. The Design of FAST(,,,,
For Ç ~ v, let y be the law of H 1 T Then a satisfies ( [B -OO condition with p, and B(E) B(E)-
The above tracking inequality captures the main thrusts of the design of FAST. The two key processes are
The noise design above boils down to setting H 1 where is drawn from a good single-objective law. The core of the analysis shows that under such a noise design, local optimism at (a., X.) is frequent, i.e., that the event
Uy = T. + +.. and L, T Be
8
Under the tracking inequality, these bound the optimal mar- gin M, as Uz 2 M, 2 L.. This immediately suggests reliable stopping criterion: if U, < O, then M, < 0, and we can declare infeasibility. If instead L, > (1 - E)U;
L(()) = { min A A'D.a 2 M.} AEAM
p under Con Notice that in contrast to the global optimism event G,) (6) specifically requires that the value of the perturbed program increases at a maximal safety margin point og, Of course, (6) C (6), so this event ensures global optimism.
satisfies Blue (L.(O)) 5.-1]
and U2 > O, we can a fortiori conclude that M, > 0 and L > (1 - M). However, yet more is true. Notice that
A Eisrge G.
A
a.a. L
((s)
min
min A
The idea of the analysis is as follows. To begin with, con- sider just the first row of the Øs. Under the event (o), we know by Lemma 1 and the Cauchy-Schwarz inequality that
A
Thus, we also find that the ergodic average action (a), Eest az/t satisfies M M(a))) 2 Ly- Since A is convex, this point lies in it, and thus under the second stopping criterion, we fortiori conclude that (a); is at least (1 - M),, -sfe.
3/a, 2 P/a - (o)
So, if the noise H² satisfies
H'V, v2, a, 2 11V a.ll = |axllv;
1V,-1/a.
This motivates the stopping time of FAST((I, E, 5),
: it : Ue < O OR L3 > (1 - e)U, > 0}.
then
Upon stopping, we find a reliable decision by declaring infeasiblity if U, 0, and outputting (a) L, if U, > O.
T/a, =taa. + w,( Vaa 2 v.a..
But each row 5ú satisfies the same property, and so such an H would improve the value of every constraint, ergo, the coupled noise H = 1m H would ensure that
3.3. Choosing an Effective Noise Distribution
The quantitative effect of the choice of μ on FAST through the factor B6 n appearing in Be, 8). Since stoppage requires that T. dominates L,, this factor directly scales the costs of FAST, and thus good μ should control this ratio. We now turn to the problem of designing such μ..
T i.a, L.a, + 1 HV 1/2
> D.a, (, ll. 1m + (o)()ala.lly P.o.,
thus inducing local optimism. The coupled design samples (column vector) Ç ~ V, and then sets H' = < H 1m | The 'anticoncentrationn condition on r(( 2 ||ll]) in Theorem 8 then ensures that matter the value of Vi, with chance at least p. H² =a.)) > 11V, V1V,~\/a,. ||. The boundedness of Ç ~ V is of course directly inherited by H thus establishing the mentioned CO condition.
Via a convexity bbsed analysis. Abeille & Lazaric (2017) show that for single objective TS, optimism is induced the noise law is anticoncentrated (i.e., the noise vector has large projection along any direction with constant chance) This lies in tension with B B-concentration, and good balance is attained by, e.g.. (0 Ia), and Lnif(v3dd5 (S....1)
This local approach again bypasses convexity considerations of K ((), which prior proofs of frequent optimism need. We note that even though we only analyse L, C GG, the resulting optimism rate prove is the same these prior analyses, i.e., we derive r-optimism with many unknown constraints under the same conditions under which prior work derives n-optimism for single objectives.
A natural idea is to draw each row of H independently from such a law. However, this approach is hard to analyse well: each row of H, gets an independent shot at reducing the noisy feasible set {a: D.a S 0}, and thus at reducing the noisy optimal margin K( (.)) which suggests that under such noise, ग would be of the order 2 22(m), where m is the number of unknown constraints. We avoid this issue with a simple fix, coupling all pertarbations, and via convexity- free local analysis at a. prove the following result in $A.2.
3.4. Stopping Time and Safety Cost Bounds
Instantiating the tracking analysis with our design of effec- tive μ from the previous section, and controlling the growth of B, to - ((vdtt) yields our main result on the stop- ping time and safety costs of FAST, as shown in $A.3.
Theorem 8. For a map B [0, 1] + Rzo. and p E (0, 1],
let be a law on Ç Rdx1 such that
v([k|| > B(6)) S 6, and Yu E Rd, "(("T T u Z [|u|]) pp.
7

---

Feasible Action Search for Bandit LPs via Thompson Sampling
Theorem 9. Let p. be the law of ImS", where { ~ Unif( / 3d and les A be convex, and 1o = o(d). Then FAST(H, e, 9/6) is (e,8)- -'-rrbiable, and w.p. at least 1-ô, in the feasible case, the stopping time is bounded as
Relationship to EOGT. FAST can be seen as an efficient ex- tension of the feasibility test ROGT (Gangrade et al., 2024b). Indeed, if executed with E 1, FAST stops as soon as Ug < 0 or L; > 0, which yields a reliable detection of the feasibility of the constraints, capturing the testing guarantees of BOGT. Of course, by coupling EOGT with an appropriate version of our Lemma 7, we can also use this to method to solve the FAS problem. Quantitatively, EOGT would need f Od M(..M. samples (and the fe-rllxationn proposed by Gangrade et al. (2024b) to implement EOGT would need r = O ((e.M)))), with testing guarantees recovered by setting = = 1. Thus, FAST recovers the same stopping behaviour, except for the loss of the extra factor of d relative to the unrelaxed-EOGT. As previously discussed, such loss is associated with all known efficient methods for linear bandits. We note that in simulations ($B.2), FAST with appropriately selected noise (see below and (B) is both computationally and statisically faster than EOGT even for small m. In particular, in the scenario of BB.2, we have d = 6, m = 2, M. = 0.4, and the stopping time of FAST is ~ 27x smaller than that of EOGT, and each round is 100x faster as well.
d + dd 1og(m/6)) )
T T= Ō (
M2
and the excess-risk incurred is bounded as
d3
dd/2 /log(m/5)
S, Ō
M.
EM,
If instead the instance is infeasible. then the same bounds hold with all & above replaced by 1, and M,, by (M.)
On tightness. FAST yields point dont that has near-optimal safety margin in time O(d / Note that since M. is a priori unknown, this procedure adapts to its value. The de- pendence of on e and M, is optimal up to polylog factors. Indeed, for m = 1, i.e., only a single unknown constraint, the problem of reliably finding a point with safety margin e1, is equivalent to finding a point that maximises the unknown objective Φ.. to within a eM, error, and it is known that any method solving this problem for linear bandits requires (2dd /=²M3) samples in the worst case (Wagenmaker et al., 2022, Thm. 2). The main loss, then, a factor of d in the stopping time (which in turn inflates the S,). However, such a loss of a factor of d appears in all known efficient algorithms for linear bandits (Dani et al., 2008; Agrawal & Goyal, 2013). Indeed, for continuous A, we are unaware of any polytime algorithm that can identify near-optimal actions with o(d") samples.
Mild Dependence on m, 8. Notice that the dependence of on m and ó is quite weak. These terms appear logarithmi- cally, and scale with second order factors in the dimension d. Thus, in the practically relevant regime of m/5 = poly (d), the statistical effect of large m or small 8 is limited.
Mild Dependence of ST on E. Finally, we highlight that the main term of Sy depends on E only logarithmically, and the second order term is 1/ev factor smaller (and so is inactive if E ((d-'/²)) Further, the safety cost scales only inversely with M., rather than with its square (as in T). This limited safety cost can be understood through the tracking behaviour of FAST: since the optimal margin occurs deep inside S., and since the margins of the de track the optimal margin, FAST must play an a E S. in most rounds.
Computational Costs. The dominating step for FAST is finding saddle point of the game (2). By a standard re- duction (see $A.5.2, and also Boyd & Vandenberghe (2004, Ch. 5)), this can be computed by solving a lincar program with d + 1 variables and constraints over the set A. We note that some care is needed: typically such meth- ods are only efficient for approximate computation of the optima. However, our tracking analysis is robust to approxi- mation errors that are o(t-O.5 and using this approximat- plot(mecnntauuionn level, the computational cost needed at round t scales as OLP-timme log(t)) by, e.g., interior-point methods (Boyd & Vandenberghe, 2004). Of course, for convex A, this LP-time is scales polynomially in m, d, and appropriate complexity measures of A. In particular, if A is a polyhedron with k faces, then this is poly (d, m + k).
FAS v/s Optimal Margin. Nominally, the result above captures a stronger output than is strictly needed for the FAS problem, in that aout has margin 2 (1 (0==)MM, E)... i.c.. close to the optimal margin, while FAS only requires us to output a point with (arbitrarily small) positive margin. We note that our theory actually captures the latter scenario too, by setting 1. Indeed, in this case, the procedure will stop essentially in time required to test feasibility, and provide point with arbitrarily small positive margin. This arises due to the multiplicative nature of our notion of approximation in essence, M.. serves as the natural scale of the search problem, and æ simply tunes between the resilience of the solution and the costs of recovery. Note that the resulting stopping time is still tight.
We reiterate that this efficiency holds even though A is continuous. This is distinct from finite-action bandit explo- ration approaches, where the computation per round grows as ()()A)). Discretisation of A at the scale eM, would require (((cM.)-)) -d) points, making these approaches un- tenable in our scenario. Of course, M. is unknown, so such discretisation cannot be directly implemented anyway.
The Zero Optimal Margin Case. Strietly speaking, The- orem 9 only captures settings with [M]] > 0. For com-
8

---

Feasible Action Search for Bandit LPs via Thompson Sampling
pleteness, we note that for M, O. no method can have nontrivial stoppage guarantee. A simple way to this is to note that the Dedf/²2M0 bound above diverges as M. + O.
Corollary 10. For Ç ~~ Unif(v3dd") let i be the law of 1m For any feasible instance, the two phase method that runs FAST(U, 1/2, 6/5) until stoppage, and then executes LC-LUCB(5) initialised with its output ensures that with probability at least 1 - for all T,
Practical Noise Distributions. It is well-understood that while existing analyses of TS require inflation of the noise variance to demonstrate optimism, in practice the smaller perturbations of the form NO, La/ Vd) have sufficient opti- mism rate, and improve regret by factor of vd by contract- ing B (e.g. Abeille & Lazarie. 2017). In the case of FAST, this improvement would be stronger still, since the stopping time scales with (B/x)² We recommend that in practice, this method is executed with such a small noise, but without amending the value of π. Simulations supporting this design are presented in $B. Of course, proving that this algorithm is reliable is open question.
RT ŌT=Ō
(v
d
and ST =Ō
d3 M.
= (())
M
in the regime log(m/0) = o(d).
Comparison to Hard Enforcement Methods. Notice that the regret bound of the two phase method in Corollary 10 improves upon prior results by a factor of M./ which can be attributed the fact that FAST( 9/5) finds point with margin at least M./2. In the absence of pri- ori control on Myafe, this factor can be arbitrarily large. In greater detail, given that FAST ignores all reward in- formation, our analysis simply incurs a constant cost for т = Odd3/MM3) rounds. Of course, this additive over- head does not grow with T, and so is hidden in the regret bounds. However, even more is true: notice that bound of v /d safe is smaller than T only if T > d @/MM Since M. 2 Maate, this means that by the time prior results give sublinear regret, the above two phase process already recovers the same performance as prior results to within a polylog factor, without being given an initial safe action.
4. Implications for Low-Regret SLBs
Finally, we turn to the implications of the FAS problem, and specifically FAST, for regret control in safe linear bandits (SLBs). Recall that the regret control problem concerns both the reward 0g_ and the risks $_a associated with the program 4 0__ a.a 2 O. Using noisy feedback of both the rewards and risks, the 'hard enforcement' problem for SLBs demands an algorithm for which the regret Ry is small, while ensuring that the actions are always safe, i.e., with high probability, ST =
Limited Safety Costs Without A Priori Knowledge. No- tice that the bound on Sy in Cor. 10 does not grow with T, i.e., that the net excess-risk is only O(1). Since the re- gret performance of this two-stage procedure matches prior results, this is the first hard enforcement method for SLBs that ensures Ö / dTTMM) regret at an O(1) cost, without assumed knowledge of an Qsafe to begin with, and with de- pendence only on the optimal safety margin M,.
As previously discussed, algorithms for SLBs, such as LC-LUCB (Pacchiano et al., 2024) or SAFE-LTS (Moradi- pari et al., 2021) address this problem, given an initial ac- tion Gsafe: along with a bound Maata such that M (dsate) Z Mafe+ > 0. These methods proceed by constructing a se- quence of inner approximation of S., St, and ensure safety by restricting a to lie in St for each t. The data (Asate: Maate) is used to construct the initial So and Maste affects the rate of expansion of S.. as reflected in the regret bounds, for efficient meth- ods. Note that as such this Maate is an arbitrary value, and may not be close to M.. For instance, in settings such as drug design and trialling, while a 'no-dosage" solution is always safe, it may not have a nontrivial margin (since, typ- ically, active compounds must be coupled with auxiliary compounds to manage their side-effects).
No Restart Requirement. The two phase method can be ex- ecuted without resetting the information accumulated over the course of running FAST, since our argument accounts for conditions under which, c.g., LC-LUCB is low-regret. This 'reuse" of information (i.e., the data in 5)) yields 'warm start', and thus practical speed up, for regret control.
which scale as R = Ō( DDVdTT/M2
5. Conclusion
We have presented FAST, method that efficiently explores a convex action space to either detect the infeasibility of a set of linear constraints, or to find a safe point with safety margin close to optimal. The design and analysis of FAST yield new insights in the theory of TS when applied to multi- objective problems. The stoppage of FAST adapts optimally to the optimal safety margin, and limited safety costs are incurred, which allows this method to be combined with low-regret algorithms for SLBs to yield the first method that, without priori knowledge of a safe action, achieves strong regret performance at only ((1) safety cost.
Of course, without knowledge of such an asafe, these meth- ods cannot be executed. Indeed, without such agafe. it is evidently impossible to achieve guarantees such as S7 O, since just the initial action may be unsafe with constant chance. Given the development of FAST above, our pro- posal is natural: we initialise these prior methods with the output of FAST, run with & = 1/2. This results in the follow- ing guarantee ($A.4).

---

Feasible Action Search for Bandit LPs via Thompson Sampling
Impact Statement
Camilleri, R., Wagenmaker, A., Morgenstern, J., Jain, L., and Jamieson, K. Active learning with safety constraints. arXiv preprint arXiv:2206. 11183, 2022. 3
This paper develops an efficient algorithm for discovering actions meeting unknown linear constraints, and analyses its theoretical properties and applications safe bandits. The potential societal consequences of this work depend largely on how and to what domains practitioners apply such algorithms, which we decline to prognosticate. We do not see any ethical concerns with the contents of this paper.
Carlsson, E., Basu, D., Johansson, F. D., and Dubhashi, D. Pure exploration in bandits with linear constraints. arXiv preprint arXiv:2306. 12774, 2023.
Carpentier, A., Vernade, C., and Abbasi-Yadkoris Y. The elliptical potential lemma revisited. arXiv preprint WrXiv:2010.10182. 2020. 5
Acknowledgements
Castiglioni, M., Celli, A., Marchesi, A., Romano, G., and Gatti, N. A unifying framework for online optimization with long-term constraints. Advances in Neural Informa- tion Processing Systems, 15:33589-33660) 2022. 3
AG was supported by the National Science Foundation award CPS-2317079. VS was supported by the Army Research Office Grant W911NF21 AFRL Grant FA8650-22-C1039, and the National Science Foundation awards CPS-2317079, CCF-2007350, and 195-1955981. CS was supported in part by the Department Defense, Defense Threat Reduction Agency under award HDTRAI-
Dani, V., Hayes, T. P., and Kakade, S. M. Stochastic linear optimization under bandit feedback. In Conference Learning Theory, 2008. 3, 8, 21
20-2-0002.
Degenne, R., Ménard, P., Shang, X., and Valko, M. Gamifi- cation of pure exploration for linear bandits. In Interna- tional Conference on Machine Learning, pp. 2432-2442. PMLR, 2020.
References
Abbasi-Yadkoris Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24:2312-2320, 2011. 3, 20
Fiez, T., Jain, L., Jamieson, K. G., and Ratliff, L. Sequen- tial experimental design for transductive linear bandits. Advances in neural information processing systems, 32,
Abeille, M. and Lazaric, A. Linear Thompson sampling revisited. Electronic Journal of Statisties, 11(2):5165- 5197, 2017. doi: 10.1214/17-EIS134155 https: //doi. org 111.:001111111111111111111111 2, 4. 6, 9, 28
2019. 2
Gangrade, A., Chen, T., and Saligrama, V. Safe linear bandits over unknown polytopes. In The Thirty Seventh Annual Conference on Learning Theory, pp. 1755-1795. PMLR, 2024a. 3,5
Agrawal, S. and Goyal, N. Thompson sampling for contex- tual bandits with linear payoffs. In International confer- ence on machine learning, pp. 127-135. PMLR, 2013. 4,
Gangrade, A., Gopalan, A., Saligrama, V., and Scott, C. Testing the feasibility of linear programs with bandit feed- back. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F. (eds.), Proceedings of the 41st International Conference on Ma- chine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 14513-14539, PMLR, 21-27 27 Jul 2024b. 3, 8, 27
Amani, S., Alizadeh, M., and Thrampoulidis, C. Linear stochastic bandits under safety constraints. arXiv preprint arXiv:1908.0588 2019. 3
Auer, P., Chiang, C.-K., Ortner, R., and Drugan, M. Pareto front identification from stochastic bandit feedback. In Proceedings of the 19th International Conference on Ar- tificial Intelligence and Statistics, 2016.7 3
Howard, S. R., Ramdas, A., McAuliffe, J., and Sekhon, J. Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2), 2021. 5
Hutchinson, S., Turan, B., and Alizadeh, M. The impact of the geometric properties of the constraint set in safe opti- mization with bandit feedback. In Learning for Dynamics and Control Conference, pp. 497-508. PMLR, 2023. 3
Badanidiyuru, A., Kleinberg, R., and Slivkins, A. Bandits with knapsacks. In 2013 IEEE 54th Annual Symposium Foundations of Computer Science, pp. 207-216. IEEE, 2013. 3
Jedra, Y. and Proutiere, A. Optimal best-arm identifica- tion in linear bandits. Advances in Neural Information Processing Systems, 33:10007-10017, 2020.
Boyd, S. and Vandenberghe. L. Convex optimization. Cam- bridge university press, 2004.
10

---

Feasible Action Search for Bandit LPs via Thompson Sampling
Katz-Samuels, J. and Scott, C. Top feasible arm identifica- tion. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 1593-1601, PMLR, 2019.
Wagenmaker, A. Chen, Y., Simchowitz, M., Du, S., and Jamieson, K. Reward-free r1 is harder than reward- aware rl in linear markov decision processes. In Inter- national Conference on Machine Learning, pp. 22430- 22456. PMLR, 2022.
Kaufmann, E., Koolen, W. M., and Garivier, A. Sequential test for the lowest mean: From Thompson to Murphy sampling. Advances in Neural Information Processing Systems, 31, 2018.
Wang, P.-.,, Tzeng, R.-C., and Proutiere, A. Fast pure exploration via frank-wolfe Advances in Neural Infor- mation Processing Systems, 34:5810-58211 2021. 2
Laurent, В. and Massart, Adaptive estimation of quadratic functional by model selection. Annals of statis- tics, pp. 1302 1338, 2000. 15
Li, Y., Liu, L., Pi, W., Liang, H., and Luo, Z.-Q. Optimistic thompson sampling for no-regret learning unknown games. arXiv preprint arXiv:2402.09455 2024a.
Li, Z., Jamieson, K., and Jain, L. Optimal exploration is harder than thompson sampling. In International Conference Artificial Intelligence and Statistics, pp- 1684-1692. PMLR, 2024b. 3
Maiti, A., Jamieson, K., and Ratlif,, L. destance-dependent sample complexity bounds for zero-sum matrix games. In International Conference on Artificial Intelligence and Statistics, pp. 9429 9469. PMLR, 2023.
Michel, T., Hajiabolhassan, H., and Ortner, R. Regret bounds for satisficing in multi-armed bandit problems. Transactions Machine Learning Research, 2022. 3
Moradipari, A., Amani, S., Alizadeh, M., and Thram- poulidis, C. Safe linear thompson sampling with side information. IEEE Transactions on Signal Processing, 2021. 3, 9, 22
D'Doooguue, B., Lattimore, T., and Osband, I. Matrix games with bandit feedback. In Uncertainty Artificial Intelligence, pp. 279-289. PMLR, 2021.
Pacchiano, A., Ghavamzadeh, M., Bartlett, P., and Jiang, H. Stochastic bandits with linear constraints. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 2827-2835. PMLR, 2021. 3
Pacchiano, A., Ghavamzadeh, M., and Bartlett, P. Contex- tual bandits with stage-wise constraints. arXiv preprint arXiv:2401.08016, 2024. 3, 9, 21, 22
Russo, D. J., Van Roy, B., Kazerouni, A., Osband, I., Wen, 7., et al. A tutorial on thompson sampling. Foundations and T in Machine Learning, 11(1):199, 2018. 4
Soare, M., Lazaric, A., and Munos, R. Best-arm identifica- tion in linear bandits. Advances in Neural Information Processing Systems, 27, 2014.7 2

---

Feasible Action Search for Bandit LPs via Thompson Sampling
A. Analysis of FAST
We prove the results determining the reliability of, and quantitative bounds on, the behaviour of FAST. We will repeatedly exploit the following basic observation, which is consequence of the Cauchy-Schwee inequality.
Lemma 11. Lef Φ be two matrices in Rmxxd and let V be positive definite matrix Rdxd, Then any a RRd
|1 - V)allo S (max 1| V')llv][allv--
Proof. By the
inequality,
1( T/ v')aa = 1( V')V1/2V 122 S 11 1') 1 |V--
where we note that (Ø' V// row vector. Of course, ||| aT VVv-//--//// = ||a|| and similarly
for ||( v1)/1/211 This bounds the absolute value of the ith coordinate of (Φ' - Va)a, and maximising over the same bounds the 20 norm.
A.1. Proof of the Tracking Inequality
The main tool required to analyse FAST is the tracking incquality of Lemma 7. order to prove the same, we begin by completing the proof of the roundwise tracking upper bound of Lemma 5.
Proof of Lemma 5. Recall the event Ball, = {max, || I B())). In this case, we know that क; & = (*( max; || S B())). Finally, recall the event G. ( () Ball,
Now, observe that the constant M. satisfies
M. |M.M Go],
where we exploit the fact that Ball, is determined given G.. Of course, by definition, under G²(5) C G., holds that M. K( I K)),), which further yields the upper bound
M, Ball,
S B[K B[K((,) (B)) 1 G.].
On the flipside, notice that X, ".aaa = (( Now, under Ball, it holds that Th E Es, which implies that
K K( IBall. 2 K (
where
T E arg arggin K($).
DEE,
But notice that & entirely determined given the historical data (i.e., does not depend on the noise H,), and thus so is K( (())). As consequence, ((b)) independent of G, given Gt-1. We can then conclude that
K L( 2 L Ball, = ([K()))) G.] Balll
Putting these two together gets us to the point discussed main text, that
(M. Blal S <((,( -
G,) Balle:
which point we can continue that analysis. For completeness, we restate this here.
Recall that k(.)) X, e.a, Since ((..)) is similarly the value of the matrix game over A induced by the payoffs क., there exists saddle point (Xe, ūz) of db such that K (( X, d.
Note that since À is selected by the 'min' 'min'-player -player, deviating from A, while keeping a, fixed increases the value of X i beyond K (.)). Using this for À de, we find that
k( X7 Traz S X7 p.at.
12

---

Feasible Action Search for Bandit LPs via Thompson Sampling
By the same coin, deviating from 0z while leaving Xe fixed decreases the value of the payoff under t i.e.,
X a 2 X +,at-
As result,
K( K( S X (Ø: )rr
Now, under G, C (6), we further know that max; || &illv S B )un, since each lies in & Thus, applying the Cauchy-Schwarz relation of Lemma 11, and using the fact that | since it lies in the simplex A,, conclude that
E| (+,) - K( (( Bal S BB2 (6) (a)llly X 15:-1, G. 1Bal..
Since B())) is deterministic, and (6) is me-i--eeaurable, this lets us conclude that
(M. - k( Bllll I 2B( 55-1 1
The argument is concluded by observing that for any nonnegative random variable X and event E, (/X/[[/EEPPP [E]P(E) S E[X], and using the fact that under the x-optimism condition, ((G:)) 2 ((G(())) - م (Ball, (6)) 2 π - x/2.
Proving the Main Tracking Inequality. We recall the roundwise lower bound of Lemma 6, which will also be exploited in the proof of the main tracking inequality.
The proof consists of exploiting the roundwise results of Lemmas and 5 to derive basic forms of upper and lower bounds on Th. These bounds are controlled by a concentration argument to conclude.
Proof of Lemma 7.
Let Ball( = M1z (f), and recall the event Con(8) M12 Con, Note that the probability of Ball(f) least 1 1- E-E d,
8.
Lower bound on T.. Observe that
= 1 + 23 (0. 2.)a..
Under (ō n Ba)l()), holds for all that max, || ll S (())))e(()) and max, | &illv, S (.) By the Sccwwrr relation Lemma 11, and the fact that ||> 1 since it lies in the simplex A", we have under Ball(8) C8n that
Vs, A. aaa 2 Ao P,, - (1 B(5,))w,,()) (o)lla,ll,.
Now, using the upper bound of Lemma 5, we further conclude that under Ball()) Con(o);
AB(8,)w.(( D.a. 2 M, (1 (6,)),
E BIIla= [S.-1].
m
Now, let C. == A₃ w be the projection of the noise in S, onto A.. Notice that since A is measurable given 6, (since it can be determinitically determined from the history and H,), ). the process { is a centred 1-subGaussian process with respect to the filtration 6.. We let Z, = Ense So.
Now, finally, have
T ENTS.
Es. Σ XJ
L., +
85t
$5t
65t
AB(())ws,()
2 + tM, Σ
(1+ B(5,) B(5,)) (w))))),(()llloal)
Σ
TE[1 az 11v 1-.-1]
π
25t
e5t
4B 4B(5 (0)
2 tM, + 2, (1 + B( (o)
Σ |1ally.-
Ellla leoellyv-1 blv 5--1h
E
(3)
SSt
where the final line uses the fact that B(,,) and (6) are nondecreasing in s, and that [a.lly, nonnegative quantity.
13

---

Feasible Action Search for Bandit LPs via Thompson Sampling
Upper bound on T. Taking a similar approach, have
T. = Z + Σ A.
P.0g:
SSt
and applying Lemma 6, under Con(E) n Ball()), we have
T. S Ze + Σ
M(a)) + 2(1 + (()
Σ Iaollv,
(4)
151
Concentration. There are two quantities in the bounds above that need to be controlled: Ze and E.gr BalaBllllllll ll 15a-1
Now, notice that since the only randomness in given - arises from Hs, which is independent of f the fluctuations [|sslle-1 - -[]1a=Ilv,-1 [5.-1] are conditionally centred. Further, since ||a,lly,- E [0, 1J, which uses the fact that V, > and A {||a|| s 1}, we conclude that these fluctuations are also I-subGaussian. It follows thus that the process
Be = Σ ||a-lly, E[[lasllv [5c-1]
has centered I-subGaussian increments with respect {5.--). Of course, we have already argued that Z, is martingale with centred and I-subGaussian increments with respect to the filtration (G.).
We encapsulate the concentration of these two processes into one event
Walk(ō) := [Vt, |&1 < (t, 6), Zz.l S LIL(t,
Tracking Inequality. But then, applying (4), under C6) n Ball( n Walk(5), we have
T. 2 I., - 1 ( B()))) + 4B(6,)
|aslly,- - (1 (1+ 4B()))
LIL(1,
e5
and applying (3),
J. Σ ((a)) + 2(1 + ((6,))we
Σ
laallv, + LI)(t,
Now, recall that under (ō) n Ball()) n Walk(8),
8) = (1 + ((()))
Σ |lallv.. 1 LIL
min( 1/2)
But then it is evident that
Bilu, 8) 2 2(1 + ((6)))ar
Σ
||aall.- + +LIL(I,)) 8),
$5t
and
Bi 8) 2 1 B(xe)
| 1v. + (1+ 4B(6,) Σ
(x)
we (I)L
SSt.
This lets us conclude that under Con(6) n Ball()) n Walk(ō), it holds simultaneously for all that
T. + Bil,, 8) 2 tM, and J. Bo(H, < Σ M(a)).
and the tracking inequality follows from the trivial observation that Eese M (a.) < LM..
Bookkeeping the probability of violation. Finally, we note from Lemma that the chance of Con(ō) is at least 1 - 8. Via the lil, the chance of Walk(5) is at least - 25, using a union bound for the two processes B, and Z, Finally, by union Σ 8, 2 1 - Σ 1/t(t 1) = 1 1 8. By a union bound, then, these events occur
bound, the chance of Ball()) 6) at least
together with chance at least 48.
14

---

Feasible Action Search for Bandit LPs via Thompson Sampling
A.2. Analysis of the Coupled Noise Design
We move to the erucial argument that our coupled noise design leads to good FCO condition, which relies on analysing the behaviour of a, under the perturbations.
Proof of Theorem 8. Notice that the noise distribution ju couples the rows of H such that H 1 where Ç ~ V. We will suppress the dependence of wi. (ōn on ó in the following.
Let a, be any maximin point of the matrix game, and fix any t. As stated in $3.1, we will analyse the local optimism event
L = {0, min A a. 2 M, = a..)
To this end, recall that
p = t + wi H.V. 1/2
Thus, local optimism holds whenever He is such that
i.a. + will V2,, 2 2.a..
VillleViVaa.
Now, under Con(5), we know that max; || - Dillv, S wy. Thus, by the Canchy-Schwarz relation of Lemma 11, we know that
(I D.)a.llo S willaally.+ w 1/2 aall = D.0. 2 D.a. -wellV 1/2 aaa 11m
But then notice that
L.a. we HoV. uaa 2 p.a. + we
(H.V. va..l1mm))
Now, we use the fact that H, = 1 for some ( ~ v drawn independently of Ve. In this case, we find that
HeV, 1/2 a, - V 1/2 a. 11m (Suuu -1|ug 1)
where = V,- o...
It immediately follows that (S ue 2 || C Lo(6) under Cō), But since ( ~ v independently of the history, the chance of this given h is at least æ. Of course, we can further see that each row of He is just copy of Çr and so automatically inherits the concentration property v.
Let us note that in practice, we expect the optimism rate to be much larger: we only showed that optimism occurs at rate at least π at any maximin point a,, But the global optimism event G, accounts for any draw where the value the game induced by t (for which the margin at a, only a lower bound). In practice, it is known that in single objective TS, the optimism rate is large even with laws that are poorly anticoncentrated in the sense of v (e.g.. N Ia/ dd). which typically only ensures that Ç" u twll/Vd.
1. BOUNDS FOR SIMPLE REFERENCE DISTRIBUTIONS
We argue that both the standard Gaussian, and the uniform law of the sphere of radius 3 yield effective noise distributions for our coupled design.
For the Gaussian, recall that if Z ~ (0 I2), then | is distributed as a x² rrandomm variable. A classical subexponential concentration argument (e.g. Laurent & Massart, 2000, Lemma 1) yields that for any x,
2[| 2 2 d + 2/dx 2x) =
Note that (d + 2v + 2x) < (vd + 2, and hence taking x = log(1/) (/8) in the above yields that B()) s vd + / 1og((1))) Further, due to the isotropicity 7, z u ||u||| law
Z1 \O0 1), and thus +(1) 2 0.158
15

---

Feasible Action Search for Bandit LPs via Thompson Sampling
Further, notice that if Z (0, Ia), then Y == /3d2//121 Unif(y3d 33)) and by isotropicity, for any u : ||u]] Y. u/|lull law
Y1. As result,
P(YTu/Ilu)) ||||| 2 = P( 2 1) - 1 P(Y? 2 1)= 1 - -P((3 - 1) 2 Σ 2 2 P(Z 2 11 PP 2 3d 1).
P(Y //
But notice that d - 1 2+ (d - 1) d/3 + 2 and thus, P( d
2 2 -) exp( exp(-d/33 -d/3). Invoking the bound on 1Z 2 1) P[Z] 2 1) above, we conclude that _ 2 0.15 (1 e d/3). Of course, |Y] v3d surely,
giving the B expression.
We note that while the above analysis only shows 0.15(1 e 4-13) lower bound for Unif( V 3dS4), via direct simulation this can easily be seen to exceed 0.28, no matter the d. In this case, the attained ratio B/ / behaves roughly as 6vd.
A.3. Analysis of Stopping Time and Excess- Rise of Exploration
The tracking inequality, along with the development in $3.2 enables the analysis of the stopping time and excess-risk of exploration, which we provide below.
The analysis breaks into three pieces: (i) reliability analysis; (ii) control of the stopping time, and (iii) control of the safety costs. We first separately discuss these aspects through a sequence of Lemmas, throughout working under the event that the tracking inequality holds (and perhaps other auxiliary events), and then prove of Theorem 9 by accounting for the various failure rates of the events. Throughout, will repeatedly use the notation Con(8), (8)) Walk()), Ze and 3r as defined in the proof of Lemma 7.
Reliability. We demonstrate reliability under the tracking inequality.
Lemma 12. If the tracking inequality of Lemma 7 holds, then the procedure FAST(U, 6) is reliable, i.e.,
M, s 0 = Ur < 0, and
M, 2 0 min T (a), 2 Ly (1 (1- M)
Proof. Assume the tracking inequality. Then for all t,
U. 2 Ms 2 Li
where U, - + Bi(,,) 6))/t and L. -Fh B1, 8)) Further recall that the stopping time of FAST is
T == inf(t U1 < 0 or L, (1--80 U); 0.
But then, if M, 5, - L, < 0 for all t, and if U, then L, Z (1 - e,,,, and thus upon stopping it must hold that U, < O.
Further, if M, > 0, then it always holds that U. > 0, and so only the second stopping criterion, that L,- > (1 - -,, can be met, which in turn implies that L, > (1 M.. Further, as discussed in $3.2, ((a)r, Lx) form a valid output since
min M(aa))) 2 Σ M(a.)/T 2 I,, > (1 M.M.
x
Stopping Time Analysis. Again, using the tracking inequality, we control the behaviour of T. Lemma 13. (Stopping Time Analysis) Suppose that the tracking inequality holds. Then,
(0 (
T = @ d2 log(m/0)
if the instance is feasible, and T =-Ö (0x
d + dl log(m/5)
otherwise.
M²
M
Proof. We begin by bounding the boundary Bi 8). Instantiating B and π with the bounds from $A.2.1 above, we note that B/ = O(vd) for our choices of laws. Using Lemma 2 to control Σ |aalll, and w., we conclude that there is a
16

---

Feasible Action Search for Bandit LPs via Thompson Sampling
constant C' such that for 1 1 max(d,3),
B,(,, S CVdy (og Cvd. Vdlog(!) + log(m/6) v dt log
s 3CVE (10 logt d
We now turn to studying the stopping time. Firstly, notice that if the tracking inequality always true, then
U = ( Bi 6))/1 & M. + (1,
and
L, ( Bilu 8))/t 2 M. (H,
Now, in the infeasible case, i.e., when M, 50
U. S I.M. + (u, 6) < - MlM 60Vl (d//2ogg + dr (og(() log(m/8))
meaning that in this case, with probability least 1 - 48,
S [t: t.M + (1, 6) < 0}
in : M 2,,
s inf 2 max(d,3) 3) t|M.| > c' Vt. (#/2 + dv (og((t) log(m/ (0)) }
with C² 6C., This infimum can be upper bounded using the following result:
Lemma 14. For A 2 inf 2 e 2 A log } s loggA).
Proof. Notice that the map f(z)= == 2/ log is nondecreasing for = 2 since f'(2) = log=-1
log² 2 0. Now,
2.A (2A)
2A (ogg)))
f(2Alog(2A)) log(2A) log log(2A)
2 (2A) A.
where we have used that log log(2) s log(z) for all 2
To use the above, notice that r S max where
Ti inf 2 max(d, e²) Vt/log( > 4C' d/2 //M.I3.
T2 = inf 2 max e²) Vt/logt 2 2C d log(m// /8)/
By Lemma 14, if Vt >
1C' 3/2
J.I. log(d /M? and Vt > e, then > Ti, and similarly. t
40 log 18)
log(8C*2 log(m/ / MM MM. P), then 1 T2, yielding the bound that
d d 16C
log² 2 d 4C
log(m M?
2 log((m/))
< max
log
M2
M
M2
Turning now to the feasible case, where M. > 0, we instead notice that if the tracking inequality holds, U, 2 M. > 0 always, and thus
S inf(t: M, 28, (1.0)/102222 (1- e) (2 (1,,
inf Mt|M.| 2 (1,
where we used |.M|| = M. > 0 in the second line. But this the same bound as the infeasible case, except with [M,| replaced by M/2. Thus, we can immediately invoke the analysis above to conclude that in the feasible case,
< max d dd+e. 2
3d
16 log(m/0) log
16 log(m/o)
log²
E²M?
E²M²
e²M²
17

---

Feasible Action Search for Bandit LPs via Thompson Sampling
Safety Analysis. Finally, analyse the safety of the actions selected by FAST using both the tracking inequality, the behaviour of 7, well as concentration of a sum of |as [ds]ll.. on the subset of events where these have large expectation. leave the analysis of the event Walk' below to the final argument proving Theorem
Lemma 15. Recall the events Con( Ball()), and Walk(ō) from the proof of Lemma 7. Further, define the process
X
Σ [E| (a [5.-1] |aallv, :) ()[(aa 115a-1] > M./2KK3
and the event
Walk (Vt, |x,] (IL
Under Cōn n Ball(d) n Walk(ö) n Walk' (8), it holds that
S, Ō Ō ( d3
18/2 /lo(mm/0)
if the instance is feasible, and S =ō 0 d3 |Mab]
+
otherwise,
M,
eM.
where we assume that (m/g)) o(d).
Proof. As show in the proof of Lemma 7, the tracking inequality holds under the assumed events. We will exploit further detailed bounds shown in that proof. Throughout, we will suppress the dependence of ō until required. Similarly, will just write B, instead of (())).
Recall that the safety cost at any time t is
S
Σ SSt
-
min ATD.as) AEA"
= ( (-M())))+
Under the roundwise tracking inequality, which holds under Con(d) n Ball(o), we know that
M(a)) 2 A P.a. 2(1 + B, )e.) aaallyy
M(aa) -1 TT.a + 2(1 B)wellasllv=
Of course, under Con n Ba)l()), further know by application of the Caucy-Sehwarz relation that T.a A T aaa (1 + B.)wellasllv. 1.
Further under the roundwise tracking upper bound, we have
4B,ws Σ E
A. A. < M, +
Putting these together, we conclude that
4B,wg
(M,) 5 3 + B.).sllaolly
BIlaa
E
alaalll;; 115,1155-111 - Mr
For convenience we define
k. (3(1 (..)) (B.())))))(( o log(t) + dllo(mm8)).
where the O only suppresses universal constant factor, and the bound arises from choice of fa 1 ST for ( Unif( (adf())dd)).... We further recall the notation 3t E.st ||a.lly, Billo,lly, [).
Since both ||a, loo=ll,;+ and EE [[/laallv.. [hist--1] are nonnegative, with this notation, we can write
-M,))) s N. (laslly. + [lllaally-- (5e-1l) M.
(5)
18

---

Feasible Action Search for Bandit LPs via Thompson Sampling
Infeasible case. In this case, notice that M,, -Ma&l 2 bound that under Con(o) n Ball()),
Since the remaining terms are nonnegative, end with the
S, t + Ke
Σ e5
||a.llv. + N
where we have used recall that is nondecreasing as 8 increases. But, under Walk(8), we further know that |&e| - LIL((, ,)), which tells us that for all 4,
S. S M +
(.))() +x. 2d0 t/d) + LIT((t,)).
Recall further that in the infeasible case, under Con(6) Ball()) (all()))) Walk())) holds that T = -OM,, & log(m//))), as discussed in Lemma 13. Using this, we find that
d + d dolommm/))
V==Ō
J.M.
Upon accounting for the fact that (II((t,)) = = but tedious accounting) that
log t + t (og((/)) and the bound on Ki,, this induces (by simple
S, = d (0
+ dl log(m/0) + 8 (og(mm0))//og)))) log (og(m//))/////
[..
Naturally, in the regime log(m//) ((d), , the leading term is / MM).
Feasible case. Note that in the feasible case, we could always get an upper bound by dropping the M, < 0 term in (5) and repeating the same analysis the above. However, this would give extra 1/- factor blowup in the main term of the safety costs due to the increase in the bound on т. To show the stated bound thus requires to exploit this M, term as resource. To this end, we note using the subadditivity of (-)+ that for any u, v, it holds that
(u + w)+ S (u- w/2)+ + (e - w/2)+ = (u w/ ( > w/2) + (v w/2)1{u> w/2}.
Using this with a = Ko Kallaolly--,, v= = K.BBllabll,= [5.- w M.. we find upon summing that
St SKI Σ
(1 | M./2ks}
>
(aa-i)-MM/22-00 (Billa 15-1] - M2/2 1 [B[[/alllv.> 15.-1] > Ma/26sa:
Krt
where we again used that K; 2 Kg for all S I.
We will first reduce the analysis of the second sum above to the first using the event Walk' in the statement of the lemma. For the sake of suceinctness, define t, M,/2ti, ///2i,,, ns I|aslly- l. ms Bllla=lly,- [5-1l Lg. Notice that ||s llvlly- > la n. > 0 and similarly for m,,
Now,
Σ mal > >0 = En.lmm > -0 + Σ (m, n2 1m,, > 0}
556
=:X;
=X,+ + Σ
n n.l(n > 0} + Σ
n4 (1,m, > 0} - 1( > 0})
SSt
$5t
=:Yi
= = + Y + Σ
n nn > 0}.
19

---

Feasible Action Search for Bandit LPs via Thompson Sampling
To analyse y, notice that
1 > 1 > 00
[m,, n, _0] [(m, S 0, > 0}.
But then, we have
Y = Σ n. n,m > 0,n, _0} - Σ n.lfm, 0, > >0}
Σ n,, 0,n, 50) Σ (-n,)1 (-n() < <0)
50
50
2 0.
Further, moving notation back terms of ||o lolllv.. instead of n,y M,, the process X, is precisely
X1 = Σ [B[ [B[laellv--1 (5.-1
1 > Me/2neh.
and thus under Walk' (8), [X,] < (t, (t, 8). Let us note that this concentration event is likely; indeed, since M. and Ki are deterministic quantities, and E|I|a,l| -- 15 is 1b---rmeasuralle we find that the conditional expectation of
C2 = (Eilla, llv. 1 - ||a. llv (B[la_lly, -85-1]] > M./2Ke}
given 5.-1 is zero. Further, of course, since < Ilallly, S 1, the random variable is 1-subGaussian given 8 meaning that the I.I. applies and Walk'(8) (8) has chance at least - 8.
Now, moving back, we conclude that
Vl, S S Kip
+ 2kz
- (I/22n)) >
85t
To address the second term, we note that
Σ (1a.llv,- Bepellyi-MM//1ree M Ma/2ne)
|aallv, Alllaaall,, 1> Ma/2Kia
28s
||a=|l?
M.
2k
<
||aal
M.
.5t
where we use the fact that 1fu > Potential Lemma (Abbasi-Yadkorii Yadkori al., 2011, Lemma 11), which states that for any sequence of actions in the unit ball, and any f,
v} S u/v for nonnegative u, v. At this point, we use a refinement of Elliptical
la, 12 S 2 log det V, s lo + t/d).
Indeed, the statement in Lemma 2 is derived from the above via an application of the Cauchy-Schwarz inequality to write Evsr |a=llv,- < v Exs1 Enss ||
In any case, incorporating all of the above, we find under the event Con(d) n Ball()) n Walk(8) Walk'()), that
(6)2 S < M. (odlog(1 + +/d)) + (8)LL 6).
20

---

Feasible Action Search for Bandit LPs via Thompson Sampling
Further, under this event, know by Lemma 13 that
7 ==ō d8 [ (1²² de looogo/)))))))
M²M
Since n log(t) + (l))(m/))); and since (T, [T] 0
log (1/6)) Ō(VF), conclude that
d3 d log(m/0) ( (
+ d Vlog(1/6) + df (ocl/)))d//lllmm//// log d log(m/ /0g/
S =
M
eM,
or, dropping all lower order terms under the regime log(m/6) = o(d),
- d3 d /lo(mm/))
s, =
+
M.
eM.
Conclusion: proof of the main theorem. With all the pieces in place, the proof of the main reliability and stopping analysis of EAST is simple matter of putting the arguments together, and arguing the frequency of Walk'.
Proof of Theorem 9, We will first show that the probability of the event Walk'(ō/5) defined in the statement of Lemma 15 least 1 8/5. Recall that the process under consideration
x, = Σ (llasllv. --lllallla 55, 1)) [B| agll vl 1 M.)2ks,0))
But notice that since B[[|a, |lv. [ is 5t-1 measurable, and M./Ka (0..()) 6) is not random, B(c,|5.-11 = 0 for all 8. Further, since 0 < ||a.lly, < 1, we immediately conclude that E [-1, 1] surely. Thus, the process X, is a martingale with [-1, 1b-ounded,,, and thus, conditionally 1-subGaussian increments, meaning the LII (Lemma 3) applies, and so for all 6, with probability at least 8/5, X. S LIL(I, 8/5), as required.
Now, by a union bound, the probability of the event Con(o/5) ()) Ba5l( Walk(8/5) Walk' (8/5), as defined in the proof of Lemma and the statement of Lemma 15, is at least and further, detailed in the proof of Lemma 7, the tracking inequality holds under this event.
Then invoking Lemma 12, we conclude that the probability that the output of FAST(E, 8/5) is valid is at least 1 - 8. Further, under the same event, Lemma 13 and Lemma 15 yield the stated bounds on the stopping time and safety costs.
A.4. Proof of Regret Bounds for Safe Linear Bandits
Proof of Corollary 10. As discussed in the main text, we execute FAST with = 1/2, and ó as specified. We recall that FAST produces a reliable output under the event = (5n(5/5) n Ball()/5) n Walk(5/5) Walk' (6/5) defined the previous sections. This results in an Gout Mout such that M (aout) 2 Mout 2 M2/
Now, we instantiate the LC-LUCB method of Pacchiano al. (2024) with (aout: Mout). We note that since we do not exactly know M (Aout), we must run this method without the projection onto the subspace orthogonal douts as detailed in their remark 11. Further, to ensure efficiency, we carry the reward optimisation via an Le-relxxtion, which incurs extra vd factor relative to their regret bounds (Dani et al., 2008). Invoking Theorem 18 of Pacchiano et al. (2024) with these corrections, and observing that 0_ (a, - ot) S 2, we find
(V |P T)+ (M./2)²
Rr < 2 2 (T,7) (T,)((
and ST S,. Of course, using the bounds in Theorem 9, under E, Ō (M/MM)), and Rr δ ( + VdT/MM3 and further Sy = Õ /M.). Finally, note that v Td < T + d /M2 < T.
which allows to absorb the first term above into just a Ō d+T/M2 bound.
21

---

Feasible Action Search for Bandit LPs via Thompson Sampling
In further detail, we the only probabilistic condition needed for Theorem 18 of Pacchiano et al. (2024) is precisely the event (ōn E, along with similar condition for confidence estimate of the parameter 0, which only causes the change that m + m + 1 in (o). Thus, one can 'warm start' LC-LUCB with the information accrued up to time and retain these guarantees. An entirely analogous argument holds for any other hard enforcement method, including, e.g., SAFE-LTS (Moradipari et al., 2021).
A.5. Auxiliary Material on Matrix Games
A.5.1. NONCONVEXITY OF THE VALUE OF A MATRIX GAME IN ITS PAYOFF MATRIX
We explicitly calculate the value of the parametric game presented in the footnote in $3.1.
2 = and the game was defined over Recall that the payoff, as a function of a variable = E R was ((2) == 2
2
A Thus, we have
K(z) = K({())
max min (A 1 1- oE(0.1] XE
(1-2
1 1-2
2 - 1 (1-a)
2
(
By an explicit computation, the objective above works out
U2(a, A) - (A 1 1- { ( (-1+a+2 = --I+a+z+ À 2ad2,
24.
and we wish to work out (a minxe(o.11 (2(a,
Now, the coefficient of À is (1 2az). There are two cases: if 2az 2 1, then the coefficient of is negative, making the Thus, we are left with resolving max Va(a), where
optimal À and if 2az < I, the optimal À
a+ 2- 2a 20 2
Vi(a)=
a
2az
Now, if 2 S 0, then the branch 2a 2 1 is never attained over E [0, 1). In this case, the optimal a is just 1, since the constraint 2az < 1 is never active. We conclude that K(=) = z if = < O.
If instedd = 2 0, there are many cases:
If S 1, then the 2az 2 branch is infeasible. Again the value just 2.
2f 1, then both branches are possible. In the 1/2z branch, the coefficient of is 1 22 S 0, and the constraint a 2 1 1/2z saturates. For 1/22 S the objective increases with a, and this constraint saturates in the second branch. In either case, the optimal value is attained at a = 1/2z, and equals + 1/2z
Thus, the value is
0
1/2
K(:) +
1122 -
2 >> 1/2
which can be succinctly written as 2 + min (2z)-1 - -1). To see the nonconvexity, explicitly observe that K(0) = 0, (1) = 1.4 but K (1122) = 1/2 > 1/4.
A.5.2. REDUCTION OF SOLVING MATRIX GAME TO LINEAR OPTIMISATION
We wish compute the value of a game of the form
max min X Aa. aEA XEAM
Notice that for any a, and m. A (Taa)= 2 min; L'a, and this value is attained over m by placing all of the mass on the coordinate corresponding to arg min, 4'a. Thus, the value of the game is equal to max, (min, 4'a) max,,vER V min; &'a 2 v,a A. But of course, min, Φ'a a 2 > Ta > ulm, m. and further, for any (a, v) that optimise the same, it holds that min, A th v. Thus, it suffices to solve the program
max S.I. vlm Da 50 0,2
22

---

Feasible Action Search for Bandit LPs via Thompson Sampling
which is an convex program over d+1 variables, with m linear constraints along with those defining A, and the corresponding A can be computed directly by computing Pa, and then choosing its smallest coordinate. Since LP-time is polynomial in d. increasing d by leaves the time to solve this LP O(LP-time), and of course, computing À after the fact only costs (()) time. For nonzero constraint level a, the margin is modified to mIn A A ( -a). Carrying out the same analysis, we just need to replace ta by ta - a, which makes the constraint wlmm - pa + a S O.
Let us note further that since M. is directly defined as m mina A V. the algorithm only ever solves maX.eA miny X L.a. Thus, we do not need to invoke the minimax theorem in the above, and the same analysis persists even if A were not convex (of course, without the efficiency guarantees). The main thing that breaks in this scenario for FAST is that the cumulative action Ees: az/t is not necessarily element of A, and the design of appropriate rounding rule would be required along with the stopping condition to yield a feasible action in this situation.
B. Simulation Study
Our main simulations focus on constructing a practical methodology out of the theoretical study of FAST. These are presented in $B.1 below. Additionally, we do auxiliary simulations that compare the behaviour of FAST and EOGT, which are presented in $B.2.
B.1. Main Simulations: The Behaviour of FAST and A Practical Choice of Noise and Boundary.
We investigate the behaviour of FAST, with the focus being to derive practical recommendations for how to set μ4, t in this procedure. Throughout, we set b, to be a certain 9 x directed adjacency matrix, A, obtained from https: // sparse. tamu. rows of this matrix were normalised to have norm 1. Throughout, we work over A = {x: : Vi, 0 S x; S 1/ 1/v9), i.e., we impose known box constraints that lie within the unit ball.
cage4, which has 49 nonzero entries out of 81. This sets up d = = 9. The
To generate a variety of M, in structured way, we work by varying the constraint level. Specifically, we study the safe sets (0) == A n ( ($_a a 2 -619}, where @ is scalar parameter. This has the optimal margin M. (o)) = 0.4849 + o. and is feasible so long as Φ > 004484.. In all cases, the optimal margin is attained by the action a. 19/v9.
Plan of Simulations, and brief summary of results. We study three aspects of the behaviour of FAST in three experiments. The results of each experiment raise further open problems pertinent to the practical use of FAST, which we also discuss.
1. In the first case, we attempt to discover what scales of noise are required for a practically efficient version of FAST. The main impetus is that while theoretical analyses of TS require a large noise of typical standard deviation vd, in practice, smaller noise of scale 1 is sufficient to retain good optimism rates, and thus such methods in practice tend to deliver an improvement of Q ((vd) in the regret achieved. Such low-regret TS methods do not use the optimism rate in any way (other than in the analysis), so these prior experiments could just simply be executed with this smaller noise. In FAST, we do not need to know the optimism rate in order to select actions, but we do need it in the boundary design. Note that an overly pessimistic bound on π would thus hit us with double whammy: an increased stopping time due to both overestimating 1/T, ,, and also due to choosing a very large B.
To address this, we execute the action selection procedure of FAST 0.1) where ny is the law of 1m with (~ Unif( ) without enforcing stopping for 10y steps. The theoretical analyses were performed with 7 = 3. In this case, we investigate 7 E 31-7:11, which yields a wide gamut of these scales, but keep M. = fixed in order to gain a sense of the relative optimism in these problems. Note that large M, means that the probability of optimism is lowered, so this gives us reasonably reliable bound on use in further simulations.
The main results here that optimism is frequent even with moderate noise 7 = 1/27. Since FAST is most effective when B is small, but is large, the main implication is that y 1/27 would yield the most effective noise for FAST. Much smaller 7 leads to a significant drop in the optimism rate, particularly in occasional runs, while much larger y leads to little increase in π, but a linear in y increase in the stopping time. Of course, proving that in general such a 7, which essentially corresponds to the noise Unif( 1133- - sd), does retain such good optimism is an open problem (although from the observations of prior TS studies, we do expect this to be true).
2. In the second case, we attempt to understand the behaviour of FAST in response to changing M,, and e. For this, we select 7 = 3-3 from above as a noise with a good balance of B/π < 0.8. We use this value of B/T, along with a refinement of the boundary process (see the proof of the tracking inequality in $A.1 for these expressions) to investigate
23

---

Feasible Action Search for Bandit LPs via Thompson Sampling
the behaviour of FAST as we vary M, and e. Throughout, we will focus on relatively large values of e, since this is the main regime in which we intend apply FAST the SLB problem.
The main results in this case bear out the broad scaling structures in our results in terms of dependence on E, M, of the stopping time and safety costs. We also find that the boundary process still tends to be too pessimistic, and thus describe the open problem of designing refinements for the same.
3. Finally, in the third case, we investigate the behaviour of the natural decoupled noise, ie., μl such that each row of H, is drawn independently from the same distribution. In more detail, we revisit the first experiment with this noise, and attempt to understand the optimism rates and reliability of FAST executed with such noise. We find that such decoupled noise is also effective for FAST, but requires a higher y than the coupled noise (and thus leads increase in stopping time). We again note that showing that this decoupled noise attains good performance is open problem.
B.I.I. INVESTIGATING OPTIMISM RATES
Estimatte of Optimien Rotes Under Coupled
Design (medians over 100 runs lougth 10")
Gooaal
We execute FAST on the described instance with E = 0.9, and chosen so that M. = 1. As mentioned above, the noise laws for
69
Lond
investigated are the coupled design, with Ç ~ Unif(v
8.7
y E {3 i [-4, 1]]. Note that since d = 9, the parameter 7 3- boils down to choosing the uniform law on $4
Since the action selection in FAST is independent of the boundary process, and thus of the value of x. we estimate π by simply execut- ing FAST for 10 steps, and averaging the counts of the number of times that the selected action was positive. This experiment run with a & such that the optimal margin is M. 1. Note that since
63
this M, is large, this lowers the probability of optimism (given that
the signal structure is identical in all of these runs, and the margin is adjusted simply by adjusting the constraint threshold). As such, we expect that the resulting values of ग are underestimates for sit- uations with smaller margin. Throughout, we let the feedback noise have variance 1. We also record the probability of 'lccal optimism' in the same way, i.e., the probability of the event L. from $3.3. In each case, the experiment is executed 100 times.
-6
log())/log(()
Figure 1. Estimates of the Optimism Rates under the Cou- pled Design Drawn According to Unif( varied. Top. Medians over 100 runs. Note that the X Xaxxis is lcale, We observe that global optimism rates sig- nificant for y = 3 = 1/3d, significantly smaller than the theoretically analysed scale of 3. Similarly, while considerably smaller, local optimism holds for 7 2 3-
as ry is
Figure/ shows medians of these optimism rates as we vary The main observation is that the probability of optimism is large even for surprisingly small values of 7, and that this probability is considerably larger than the probability of local optimism (although this too remains nontrivial for large y). Demonstrating this fact to be true (which is indeed expected from observations regarding TS in single objective low-regret bandits) is a fascinating open problem.
B. 1.1. THE BEHAVIOUR OF FAST WITH RESPECT TO M. AND
Using the information drawn in the previous section, we now turn to our main simulations on the behaviour of FAST. In order to do so, run FAST with the noise (oy with y = 3-3 which, seen in Figure 1 above provides regular large probability of optimism. We instantiate the boundary process for FAST with the value of the median global optimism rate estimated above. Note that this has a significant effect: the resulting B/T is roughly 0.8, which makes the boundary process behave as roughly 3w Σ | + (1 + LII. If we instead ran with the theoretical values of B/T = v3d/0.28 x 18, the boundary process (or refinements of the same, as detailed in 1A.1) would instead have a coefficient of ~ 30 for the first term, leading to two orders of magnitude increase in 7 in the worst case. Of course, in practice such a ı cannot be estimated simply- - resolving this is an important open question for the applicability of methods such as FAST. Our practical recommendation is to simply use noise of the form Unif( (e8d) for e a not-too-smal constant, and set π ~ 0.5.
We first describe two experimental details before discussing our results.
A Refinement of the Stopping Criterion. In addition to the certificate L,, on the value of M., note that our setup yields a rumning estimate of a potentially feasible action, (a): = =E.g az/t, and using Lemma along with the
inequality, we can further conclude that with high probability, (a), 2 &.(a), + well wall(a)lllv 1m which yields further lower bound on the value of the margin, min A (2) - a) > L. == min X ((.((a), - a) - wr wrll(a))lly, 1. In our
24

---

Feasible Action Search for Bandit LPs via Thompson Sampling
Value of Certificate L. normalised by M.
True Margin of a normalised by M.
0.95
0.6
0.8
0.5
0.75
0.4
0.50
H-8
0.50
0.7
0.70
0.3
0.70
c
0.90
+-8 0.90
0.65
0.2
0.16
0.2
0.25
0.3
0.35
0.4
0.45
0.5
0.16
0.2
0.25
0.3
0.55
0.4
0.45
0.5
Optimal Margin M,
Optimal Margin M.
Figure True safety margin of the oulput of FAST with different (left), and the certificate Mout L,, output by it (right), a fraction of the true margin. Means over 100 runs with mee-stndarrdddeviatoo enror bars presented. Notice that the certified value is typically much larger than 1 - E, and the actual realised value larger still (always > 0.8), indicating that while reliable, the procedure is too conservative.
experiment, we replace the T, the stopping criterion by == max(Tx; T.).. Note that this retains the reliability guarantee. While theoretically this does not improve the behaviour of the stopping time beyond a constant factor, since Ue is left unchanged, find that in practice, this can significantly improve the stopping time under feasibility, especially if e and M. are large.
Reduced feedback noise in simulations. We note that feedback noise is set to be independent Gaussian with standard deviation 0.1, and we use this value to adjust our confidence sets. The main reason for this is for the sake of computational efficiency: the value of the noise standard deviation essentially scales the quantity (r(8), and thus decreasing the noise standard deviation by factor (roughly) shrinks the boundary process B, by the same factor. Since the stopping time scale quadratically up polylog factors in the coefficient of Vt in B,, this change, in essence, reduces the stopping times by factor of about 100. Since repeat each of our runs 100 times, this represents significant computational saving. Indeed, midrange laptop computer running 2022 Ryzen-5U
with this change, these simulations took about 3 hours execute CPU. We note that the relative scaling of all behaviours with M., is left unchanged by this modification, but, should the actual values be important, the reader should scale them by 100 before interpretation.
Experimental setup. Below, we proceed by setting M. E {0.15, 0.2, .0.5,, and e E {0.55 0.7, 0.9}, and simulating the behaviour of FAST on the described instances 100 times for each pair of parameters. The choice of M, is largely to limit computational costs, while the choice of large reflects the natural application domain of FAST SLB problems, as discussed in $4.
Reliability Observations, and the discovery of very safe actions. We find that in all of our runs, the resulting feasibility- infeasibility decisions, as well as the actual margin of the output, were always correct, despite the fact that we ran our experiments with the reliability parameter from the fact that our boundary is too conservative (since a well-defined boundary would see about 10% of decisions being incorrect). We leave the question of finding such refined boundary to future work. Figure illustrates the same point the feasible case by showing the actual safety margin of the output å, relative to the true margin of the instance.
0.1. our opinion, this represents an inefficiency in the test design, stemming
Certified Margins Figure 2 shows the value of Mout output by the method on feasible instances, normalised by M.. In this case, we again observe that this value tends to be much higher than 1 which bears out the fact that the upper bound U; decreases too slowly (due to too conservative a 2.)
Stopping Time Behaviour Figure 3 shows the behaviour of the stopping time for both the infeasible case (for which the value of is immaterial), as well as for the feasible case with three values of e. Of these, the runs with g = 0.5 essentially
25

---

Feasible Action Search for Bandit LPs via Thompson Sampling
10
10
Safety Cost Incurred (S.)
10
Stopping Time (r)
10
10'
4-8 0.50
5-8 0.50
f- 0.70
8 0.70
1-c 0.90
0.90
Infessible
: I-feesssible
10
0.15
0.2
0.25
0.3
0.55
0.45 0.5 0.16
0.2
0.25
0.5
0.35
0.4
0.46 0.5
Optimal Margin M.
Optimal Margin M.
Figure Stopping Time (left) and excess-risk of exploration (right) of FAST both the infeasible (dashed) case, and the feasible case with different& e. Means over 50 runs with one-standard -e--saadddddeeiatioon error bars are presented. The refinement & discussed in this section yields significant improvement in stopping time, especially large (e, M.). ). Notice also that the excess-risk in feasible scenarios < 10, much smaller than the corresponding infeasible scenario. We further note that S, [1.08, M. in the infeasible case for all [M.]--
correspond to FAST with no refinement of & instead of L, (see below for why), and the stopping time with 0.5 exceeds that of the infeasible case by a factor of about 2. Notice further that the plot clearly demonstrates the inverse quadratic behaviour with M..
The early stopping criterion we described helps reduce stopping time mainly when the upper bound U2 takes long time to decrease. Indeed, in runs, for small f it essentially held that U. 1, T. -1. Thus, the stopping criterion in these cases boils down to & L. 2 (1 =), and significant gains in stopping time arise when both is large, and when M, is large enough so that L, grows quickly. This behaviour is demonstrated clearly in Figure 3 by both the sharp drop in stopping time for M,- = 0.4, and ę = 0.7, as well as the fact that the stopping time for e = 0.9 is always > 50x smaller than that for E = 0.5 despite the fact that (0.9/0.5)² is only 3.24.
Safety Costs Figure further shows the behaviour of the safety costs of exploration. There are two qualitatively distinct observations: in the infeasible case, the realised S, is typically 1.1 |.M.| T, bearing out Theorem 9 quite directly (up to the looseness in the bounds). In the feasible case, however, find that the bound of this theorem is extremely loose, and the S incurred is very small, being about 100x smaller than the safety costs of exploration in the infeasible case.
1.3.3. DECOUPLED NOISE
Estimates of Optimiem Rates Under Dooupled
Design (mrdians 100 rans length la')
Finally, we briefly investigate the behaviour of the natural design of a decoupled noise distribution, i.e., such that each H' drawn uniformly. We study the same set of laws, i.e., each row is drawn from Unif(v>dsd) inde- pendently, with y E 3(-7:1], Figure 4 shows the resulting optimism rates. The main observation is twofold. Firstly, it must be noted that the global and local optimism rates are significant for this noise design, even though our the- ory does not analyse it. The development of effective analyses for such noise yet another fascinating open question. The second key observation, however, is that the (global) optimism rates with this decoupled noise de- sign are significantly lower. This raises the values of G., since we need a larger = 3 3-2, and since x 0.5 is smaller. Roughly, we expect this to cause slowdowns of about (V3. 0. x 6 times.
Global
0.9
0..
0.7
86-
0.-
08
-4
log(>)/ log(3)
Figure 4. -istinats of the optimism rates with the decoupled noise design with the same setup otherwise as in Figure 1. Observe that the decoupled noise design loses optimism the same value of as the coupled design.
26

---

Feasible Action Search for Bandit LPs via Thompson Sampling
In fact, we observe this behaviour under simulations. These are executed with the above y (and appropriately adjusted boundary) for the larger values of M, {0.35, 0.4, 0.45, 0.50J, but with the same values of E. Figure 5 plots the ratio of the stopping time in this case relative to the stopping times determined for the decoupled design (Figure 3). Notice that in the infeasible and E = 0.5 feasible cases, the stopping time is indeed about 6 times higher than the coupled design. In the larger E cases for feasible noise, where early stopping plays a more critical role, the relative loss is smaller, but still significant. We observed the same 6-fold behaviour in the safety cost for the infeasible case, and while again larger, the behaviour was less regular for the feasible case (since S, is so much smaller, and thus harder to reliably estimate in a multiplicative sense). For this reason, we choose not to present the same data in the case of safety costs.
Stopping Time of Decompled Design Reelttive to Coupled Desiig
0.50
Infrawbbie
Optimal Margin M.
Figure 5. SSoopiigg time of FAST run with decoupled noise, compared to the same with coupled noise. As in Figure 3. means and bars over 100 runs are reported, here on a lincar scale. Observe that for small s in the feasible case, and in the infeasible case, see a net loss of about factor of 6. In the case of larger e; the loss is more limited, although still significant, typically larger than 2x.
standardddevialte
error
B.2. Comparison of FAST and EOGT
As a final set of simulations, we investigate the behaviour of EOGT and FAST to compare the merits of the two. Concretely, we will run FAST with the choice of noise and boundary discussed in the previous main section, in particular, setting ? (9vØ)-1, and the B, π values as in the previous section. As such, then, since the domain is significantly different (see below), the success of FAST in this regime serves as a validation of the robustness of this practical design.
Setup. We will implement the relaxed version of EOGT proposed in our prior work (Gangrade et al., 2024b). Recall that this requires us to solve (2d) matrix games in each round, and so for practical reasons, only small m can be implemented.
To set the instance, we follow our previous evaluation of EOGT (Gangrade et al., 2024b). Throughout, we work with m = 2 constraints. Explicitly, for feasible settings, we impose the constraints
at N 1/Va - M., d² 2 21/Vd- M.,
and in the infeasible setting, we impose the constraints
a' > Ma, a' S -M,,
Note that in both cases, the absolute value of the optimal margin is M,: in the infeasible case, the point (0, (0.... 0) has the required margin (-M,, since it is infeasible), and in the feasible case, the point (1/VQ, 1/Vd, has the required margin. This setup is entirely in line with the prior study of EOGT, except that we impose box constraints instead of ball constraints (which allows for faster optimisation).
and work with A = 1-1VV
We investigate the above setup for d E [2 : 10), and vary |.,| E {0.2, 0.6, 0.8). For the sake of simplicity in presentation, we show the data only for 0.5, although we executed the same for & = 0.7, 0.9 as well, and saw the same behaviours. As in the previous section, feedback noise is set to Gaussian with standard deviation 0.1.
The main reason for picking box constraints is that the game-solving can be sped up significantly. We do this in direct brute-force way: since m = 2, the parameter X is effectively one-dimensional. We grid this one dimension at the scale 0.002, and for any T. directly compute the values A T at each of these 500 points. For any single value of X and T. the optimal a is simply sigu(>$)/
and the value of max, A T &a is thus just ||x T Φ/|, which extremely fast to compute. From here, we can compute the minimising \ easily, and then work back to find a. Note that this procedure is actually solving for mInA max, A &a, but this is tine due to the minimax theorem. For EOGT, this process is carried out for each lying in the fj-confidence set (Gangrade al., 2024b), of which there are (2d) 4d
Due to the explicit request of reviewer of this paper, in these set of experiments we do not implement the early stopping procedure we presented in the previous section. This would largely only affect the large values e = 0.7, 0.9, which we may expect to be smaller for both methods if this were included.
All instances are simulated 50 times using a MATLAB environment.
27

---

Feasible Action Search for Bandit LPs via Thompson Sampling
Conclusion. The main observation is that while both FAST and EOGT are accurate methods that produce high quality solutions, FAST is strongly preferable because it has both strong statisical and computational advantage over EOGT, in that it stops much sooner (so requiring fewer iterations), and is much cheaper to compute per iteration.
Of course, the computational advantage is the main point behind the design of FAST, and so is to be expected, although we note that much of the theoretical advantage survives even the fixed costs expected in practice.
Given the theoretical development in the main text, however, the statistical advantage may be surprising. However, note that we are running FAST with a smaller than analysed scale on noise. Given thi, the observed behaviour is somewhat expected: it is well-established that while analyses of linear-TS only available for noise of scale vd, in typical practical settings, one can execute linear TS with 'non-inflated" constant-sized noise and outperform the regret behaviour of UCB-styles like OFUI. (e.g. Abeille & Lazaric, 2017). Within this context, then, FOGT is essentially built upon OFUT. while, of course, FAST exploits a linear-TS style underlying method. The relative advantage is further exacerbated by the fact that stopping times scales roughly quadratically with natural regret metrics, thus giving a very stark benefit.
The remainder of this section presents data supporting the above claim of strong statistical and computational advantage in the two regimes studied.
Fixed d, varying M.. For our first set of observations, we fix d 6, and vary M..
Firstly, we note that in every run, both methods either correctly detected infeasibility, or certified a point with margin at least M./2. In fact, the quality of the recovered points and the certificates are similar, as seen in Table 1. Of course, observe here that the variance is higher in FAST - this is to be expected, since this is a randomised method, while EOGT is deterministic (given the noise, of course).
Table 1. Comparison of the Quality of agus in the fixed d. varying M, setting for Feasible Instances, with & = 0.5. Observe that the quality of solutions essentially the same, and far excceds the required 50% both the certified and realised margin values.
Metric
Method
M.
0.2
0.4
0.6
0.8
Certificate LT/M. (%age)
FAST
66.6 + 0.5
66.4 0.5
66.4 + 0.6
62.6 + 0.1
EOGT
66.6 + 0.1
66.6 0.1
66.6 + 0.1
62.5 + 0.0
Realised Margin M MM, (%age)
FAST
99.6 0.4
99.4
99.1 0.7
98.7 1.1
BOGT
99.9 + 0.0
99.9 0.0
99.9 0.0
99.8 + 0.0
However, the corresponding values of the stopping time are starkly different, especially in the feasible case. Indeed, as shown in Table2, the stopping time of FAST in the infeasible case is typically about 30x smaller than that of EOGT, suggesting that FAST is strongly favoured statistically.
Table 2. Comparison of the stopping time of FAST and EOGT for d = 6, = 0.5 as M. varies. The advantage row lists how many times the mean for FAST is smaller than that for EOGT. Notice the stark advantage the feasible case. In the infcasible case, the advantage small, but still nontrivial.
Metric
M.
0.2
0.4
0.6
0.8
FAST
3935 + 1287
877 + 245
317 + 67
138 + 31
T, Feasible Case
EOGT
106276 + 331
24562 + 105
10292 = 43
4296 + 45
Advantage
27x
28x
32x
31x
FAST
731 + 44
348 + 14
119 +
48 =
T, Infeasible Case
ROGT
980 15
482 +
263 +
149 + 4
Advantage
1.34x
1.38x
2.21x
3.1x
This, of course, is accompanied by a drastic improvement in computation as well. Indeed, for d = 6, FAST is 144x faster (thcoretically) than EOGT. Practically, we in fact see a 122x speedup per iteration, recovering most of this theoretical gain even for this small d (see below for many more details). The net effect for us is that, e.g., in the M, = 0.2, feasible case, EOGT took about 2700s (with 5-fold parallelization). while FAST took about 1s. Of course, for the infeasible case, FAST remains similarly fast, while EOGT still took 30s.
28

---

Feasible Action Search for Bandit LPs via Thompson Sampling
We note that we similar behaviour in the safety costs of both methods: for infeasible 7, these grow roughly as |M,] т, and few percentage higher for EOGT. For the feasible case, both time x 1 for FAST in the M, 0.2 case, and & 8 for EOGT for the same these are miniscule relative to the scale of T.
Strong Advantage of FAST. This data clearly establishes that FAST is preferable to EOGT even in modest dimensions (d= = 6) the infeasible case, it buys little bit statistically, and in the feasible case, the statistical gains are massive. This accompanied by further strong computational gain (which would be further increased exponentially as m increases, and polynomially as d increases).
Fixed M., varying d. To complement the above study, we fix M, 0.4, E 0.5 and vary d from through 10.
Computation Per-Iteration with d. As discussed in the footnote below, we investigated the time-per-iteration as d grew. Nominally, of course, as d diverges, the relative costs are 4d but in practice, fixed costs per iteration at finite d tend to reduce in gain. In our experiment, there are two main sources of fixed costs: generating randomness for feedback, and maintaining V,, and various recording updates to track the data. We find that the time per iteration of FAST does not tend to go below 5.0ttm//ttnraiinn, even bottleneck, and reducing the theoretical advantage per iteration. For FAST, in d 6, the costs were about 0. 0.024ms/iteration, while EOGT took about 2.94ms/iteration. For the range investigated, due the polynomial growth in the time needed for linear programming, the time-per pen-teer-tteration of FAST never exceeded 0.04ms/iteration, while at d 10, that of EOGT was x 8.5ms/iteration, or > x more.
2, suggesting that for very small d these fixed costs begin to be the
Quality of Solutions. Again, this is similar: throughout, the certified margin is about 0.66M,, while the actual margin of aout is closer to M, We omit formal presentation this. Further, safety costs are similar in the feasible case, and scale directly with in the infeasible case.
Stopping Time. More importantly, FAST again has strong advantage in terms of the behaviour of the stopping time, as shown in Figure 6. The relative advantage stopping behaviour saw in d 6 persists across dimensions. In particular, for small d, we see about 5 10x gain, while for larger d, the gain is always 20x, hitting peak of 33x at d = 7. Again, coupled with a > 200x computational advantage per iteration at d = 10 (where the statistical advantage is z 22x), this makes a strong case that even with modest d and m = 2, FAST is strongly preferable to EOGT.
Stopping Time (r)
FAST, Fesusible Cone
DOGT Fessible Case
10
FAST,
Infeasible Case
1 EEGT. Infoodille Caor
Dimension (d)
Figure 6. Behaviour of the Stopping Time of FAST and EOGT as d is varied with m 2, M. 5 = 0.5 in the feasible (solid) and infeasible (dashed) cases. Observe the strong > 20x advantage in stopping behaviour of FAST relative to EOGT d 2 this setting, the infeasible case is significantly casier than the feasible, although we still find an advantage of 1.2 x -1.9x in stopping behaviour.
29


Reviews:
[{"review_id": "oOmi6Bsrd4", "reviewer": "Reviewer_Qe9e", "summary": "The paper studies the feasible action search problem for linear bandits. In particular, the goal of the learner is to identify a point in a convex set that satisfies a set of linear constraints. The learner repeatedly interacts with the environment and receives as feedback the value of all the constraints for the played action with some additional noise. The learner should stop when it identifies an action that almost maximizes the safe margin or determines that the system of linear inequalities is unfeasible. The approach is based on Thompson Sampling. The authors prove that the algorithm stops in $O(\\frac{d^3}{\\epsilon^2 {M_*}^2})$ rounds providing $O(d^3/|M_*|)$ cumulative constraint violation, where $M_*$ is the optimal safety margin. It detects feasibility or identify an $1-\\epsilon$ multiplicative approximation of an optimal solution. The designed algorithm can be exploited to derive novel results for regret minimization in linear bandits with safety constraints. In particular, it can be used to remove the assumption that the learner knows a safe action.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Our thanks for your work. Thanks also for the interesting reference. The section 8 of this paper certainly describes a related idea, although there is no real adaptation to the value of the Slater parameter ($\\equiv$ margin), which is an important aspect of our study. We will both try to carefully work out the concrete implications (by working out the primal/dual regrets appropriate here), and of course discuss this paper in the related work section.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "The problem under study is novel, even though it has many connections with other works extensively discussed in the paper.", "essential_references_not_discussed": "The literature on primal-dual methods for online learning with long-terms constraint is closely related to Low-Regret SLBs. There, one crucial component is the estimation of the Slater's parameter, which is essentially your optimal safety margin. Probably, the most closely related work is [1], which derives a general primal-dual method (that can be applied to linear bandits) to learn a strictly feasible solution. Even if not explicitly stated, their results should imply some constant (independent from $T$) bounds for your setting. \n\n[1] Castiglioni, M., Celli, A., Marchesi, A., Romano, G., & Gatti, N. (2022). A unifying framework for online optimization with long-term constraints. Advances in Neural Information Processing Systems, 35, 33589-33602.", "other_strengths_and_weaknesses": "The paper studies the important problem of learning safe strategies in linear bandits. This is a crucial component for designing regret minimization algorithms for linear bandits. Moreover, the proposed algorithm is efficient and the theoretical analysis is involved. Finally, the work has interesting connections with other problems as discussed in the comprehensive analysis of related works.", "other_comments_or_suggestions": "Line 29 right:  $\\alpha$  should be $0$.", "questions_for_authors": "None.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vDFIc49Eai", "reviewer": "Reviewer_6i4C", "summary": "This work studies Feasible Action Search problems with linear constraints, in which a learner aims to find a point with maximal safety margin. The learner may declare that the constraints are infeasible if it fails to find a feasible point.\n\nThe authors suggest an algorithm called FAST. It is based on Thompson Sampling:  in each time period, it makes a random perturbation on the estimated constraint matrix by adding some noise, and then selects a point that maximizes the safety margin with respect to the perturbed constraint matrix. The algorithm keeps track of an upper confidence bound on the optimal safety margin and a lower confidence bound on the progressive mean of safety margins, and employs a stopping rule such that declares infeasibility when the upper confidence bound drops below zero or outputs the average of attempted points when the lower confidence bound becomes $\\epsilon$-close to the upper confidence bound. Under a carefully chosen noise distribution for random perturbation, the algorithm finds $\\epsilon$-optimal point within $\\tilde{O}(d^3/\\epsilon^2 M_*^2)$ interactions with high probability, nearly matching the lower bound $\\Omega( d^2/\\epsilon^2 M_*^2 )$.\n\nThe algorithm FAST can also be useful for SLB problems in the sense that by running FAST in the initial phase the learner can find a feasible solution and then run SLB algorithms starting from the discovered feasible solution.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Our thanks for your work.\n\n- Max-safety-margin v/s only feasible. Thanks for bringing up this important point. The short answer is that our setup already accomodates the viewpoint you express through our use of the multiplicative approximation.\n    - Indeed, any feasible point would have a safety margin of at least $0$, and so would satisfy our notion of approximation with $\\varepsilon = 1$ (since $0 \\ge (1-1)M_*)$. So, if we just run FAST with $\\varepsilon = 1,$ we will stop with a feasible action in $\\tilde{O}(d^3/M_*^2)$ time, gaining a factor of $\\varepsilon^2$.\n        - We note that the stopping time bound above is just as tight as the general bound in Theorem 9. By the same reasoning as in line 340 col 2, if $m = 1,$ then finding a feasible point is equivalent to finding an $M_*$-approximate optimum in a low-regret problem, and so needs $\\Omega(d^2/M_*^2)$ samples. We lose a factor of $d$, which appears in all known efficient methods (line 346 col 2).\n    - Finding a point with near-maximum margin of course has practical applications, mainly in terms of building resiliency. For instance, a manufacturer balancing various quality and cost constraints would want the solution to be remain feasible under small perturbations of the process (translating to perturbations of $\\Phi\\_*$ in our setting). This would be true for a point with positive safety margin, but not so if the margin is close to zero. $\\varepsilon$ captures a tradeoff between the costs of identifying such a point, and its resilience.\n        - The application of optimising a different objective later is captured well by the low-regret SLB problem discussed in section 4. Here, in fact, positive margin is a necessity, since this margin determines the rate at which information can be accrued in the early rounds (also see the lower bound due to Pacchiano et al. 2021). This is reflected in the regret bounds scaling with $M(a\\_{\\mathsf{safe}})^{-1}.$ Our proposed solution improves upon this general bound: we pay an extra constant factor in the exploration costs to end up with a point with close to optimal margin, which in turn improves the regret by a potentially large factor of $M_*/M(a\\_{\\mathrm{safe}})$ (Line 80, Col 1). If instead we had stopped with near-zero margin, the regret would suffer. \n            - Of course, here exact optimal margin is not necessary, which is why Corollary 10 sets $\\varepsilon = 1/2$ for this application.\n    - We do want to say that your point is well-taken, and these aspect should indeed have be clarified and discussed in more detail in the paper. If accepted, we will include something like the above to clarify these issues in the paper. \n\n- UCB version: yes, this works, but is computationally infeasible. \n    - This method was proposed as a test by Gangrade et al 2024b (and can be extended to FAS via a tracking result similar to our Lemma 7).\n    - However, as discussed in the paragraph starting line 150, col 1, for continuous $\\mathcal{A}$, this technique needs to solve $(2d)^{m}$ games in each round. This makes it completely impractical even in the setting we simulated in section A (since for $d = m = 9, (2d)^m > 10^{11})$. For instance, our method runs in milliseconds per round, but this method would take years. Finding an efficient UCB-version of such algorithms is an open problem. \n\n- Does local optimism lead to over exploration? This may indeed be true, which is why the main CO condition (Def. 4) is formulated in terms of global optimism. \n    - However, we note that our bounds on the optimism rate match those of prior work on single-objective TS, even though they are studying global optimism.\n    - To be explicit: under the same conditions on the noise in which prior work shows $\\pi$-global optimism, our coupled construction gives $\\pi$-local optimism. This suggests that new techniques are needed to control global optimism rates well not only for FAST, but for linTS in general. This is beyond the scope of our submission.\n\n- Relation to online linear programming: while interesting, this appears to be a quite different problem. In the setup in the reference, the constraints are revealed one-by-one (and completely), while in our case, constraints are never directly revealed, but we can noisily measure (all of) their values at various $a_t$. Of course, the other important difference is that they are aiming to optimise, while we are aiming at maximin points. Nevertheless, we will read this thoroughly to see if it is appropriate to discuss.", "claims_and_evidence": "This paper mainly focuses on making theoretical claims. The proofs look solid to me.", "methods_and_evaluation_criteria": "I believe that the suggested algorithm is sensible -- it can also be implemented in practice.\n\nHowever, the choice of performance measure is not completely convincing to me. The suggested algorithm aims to maximize the safety margin, whereas the eventual goal would be to find out one feasible action.", "theoretical_claims": "I carefully read the statements and the discussions provided in the main body of the paper, and I couldn’t find any suspicious claim. Although I am not that familiar with the random perturbation technique, I was able to understand the technical novelty made by the authors (global optimism vs. local optimism).", "experimental_designs_or_analyses": "Some simulation study was included in Appendix. Although I couldn’t check all the details, the experiment was designed reasonably, and the behavior/performance of the algorithm is well reported.", "relation_to_broader_scientific_literature": "The authors have already discussed the relation to a wide range of literature, namely, Best Arm Identification, Best Safe Arm ID, Minimax and Pareto Bandits, Feasibility Testing, etc. I guess that this work may also be related with online linear programming (e.g., Li and Ye (2021), Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds), but I am not certain about the connection.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "This work adopts the safety margin as the learner’s objective. This choice allows the authors to utilize the techniques developed in minimax/pareto bandits, deviating from the existing work on safety bandits. This would be a unique feature of this work, but further justifications are needed. Why do we need the safest action if our goal is to optimize another objective eventually? Perhaps, the problem should be called “Safest Action Search” instead of “Feasible Action Search”.", "other_comments_or_suggestions": "See Questions for Authors.", "questions_for_authors": "- Will the UCB version of the suggested algorithm work? I am imagining the UCB-like algorithm that runs without random perturbation. More specifically, the algorithm may pick up the query point optimistically within the confidence ellipsoids for $\\Phi_*$, by solving $\\max_a \\min_\\lambda \\max_{\\Phi \\in C_t(\\delta)} \\lambda^\\top \\Phi a$. I guess that it could be easier for the authors to analyze this UCB version…\n\n- Does the notion of local optimism lead to over exploration? Since the occurrence of local optimism ensures the occurrence of global optimism, making the local optimism occur sufficiently often may induce global optimism to occur too often.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "L7wBIj6At3", "reviewer": "Reviewer_XXMP", "summary": "This paper studies the problem of identifying a point that satisifies a set of linear constraints, using only noisy observations of the linear constraints.\nThey give an algorithm that identifies a strictly feasible point after $\\tilde{O}(\\frac{d^3}{\\epsilon^2 M^2})$ rounds, where $M_*$ is the largest safety margin of any action.\nThey then consider the safe linear bandit setting and show that by combining their algorithm with standard safe linear bandit algorithms, they an guarantee $\\tilde{O}(\\sqrt{T})$ regret and $\\tilde{O}(1)$ cumulative violation (hiding all non $T$ factors).\n\n## update after rebuttal\n\nI maintain my positive score. The authors addressed the minor concerns that I had.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Our thanks for your work.\n\nQuestions:\n\n- Corollary 10: This is indeed an important point, thanks for your careful reading. The issue is resolved by Remark 11 (page 8) and Appendix F.1 (page 47) of the paper of Pacchiano et al. (https://arxiv.org/pdf/2401.08016). \n    - In short, remark 11 summarises how it is enough for them to have a lower bound on the safety margin of the safe action that is a constant factor away. In our case, the margin of the output $\\langle a\\rangle_\\tau$ is bounded between $L_\\tau$ and $U_\\tau$, and by the stopping condition, with $\\varepsilon = 1/2,$ we have $L_\\tau >  U_\\tau/2 > M(\\langle a\\rangle_\\tau)/2$, so we get exactly such an approximation. There is however, a small modification needed (as discussed by Pacchiano et al.) in that the orthogonal projection stuff in LC-LUCB cannot be carried out with only a lower-bound. This does not affect the regret bounds. \n    - We will expand upon the discussion  of section B.4 to discuss this aspect.\n    -  We also wanted to point out that in fact most such methods for SLBs only really need a lower bound on the margin of the safe action (and the regret then scales with this bound). Intuitively, the point is just that this bound yields an initial exploratory set, and determines the rate of expansion of the safe set estimate. LC-LUCB is a bit of a special case because of the orthogonal projection step they take.\n\n- $M_* = 0$: We will be happy to discuss this. Short answer is that in this case no method can operate in finite time.\n    - As an example, consider the case  $m = 1, d = 1$, and $\\mathcal{A} = \\{ 1\\},$ with standard Gaussian feedback noise. Then the questions becomes one of testing if $\\phi_* = 0$ or $< 0$ using samples from $\\mathcal{N}(\\phi_*,1)$. But with any finite number of samples $n$, we cannot reliably distinguish between $\\phi_* = 0$ and $\\phi_* \\in (-O(1/\\sqrt{n}),0)$, and so we can never reliably conclude the procedure in finite time. This simple scenario embeds into more rich situations, and so if the optimal margin is exactly $0$, we can never be $\\delta$-sure of this fact, and so never stop in finite time. This is also reflected in the $\\Omega(d^2/M\\_{\\*}^2)$ lower bound (line 340 col 2), which diverges to $\\infty$ as $M\\_{\\*} \\to 0$.\n\n- Rows instead of $\\lambda$: Yes, we can write things in this way with no change. The reason why $\\lambda$ was introduced was to give ourselves the option of using the minimax theorem when working the results out. This (surprisingly) ended up not being needed, but by the time we figured this out, much of the paper was already written in this language, and it was too late to rewrite all of it.\n\n---\n\nRelation to broader literature: while we mostly agree with your reading, we would like to point out that while yes, an extension of Gangrade et al. 2024b along the lines of our submission would do this job, this method is completely impractical.\n\n- Their proposed relaxation (page 9 of their ICML paper) requires solving $(2d)^m$ matrix games in each round. With $d = m = 9$ (the setting studied in our Appendix A), this requires $>10^{11}$ games in each round, and so each round would take years on a laptop, while our method runs in milliseconds.", "claims_and_evidence": "Overall, the claims look okay. I am looking for some clarification on the guarantees for the safe linear bandit setting as detailed in the Questions box \\# 3.", "methods_and_evaluation_criteria": "The approach of using thompson sampling for efficient decision-making is sensible. Evaluating the approach with stopping time, safety cost, regret, and risk makes sense.", "theoretical_claims": "My only possible concern with the theoretical claims is the proof of Corollary 10, which I detail in \\# 3 in the Questions box.\n\nOther than this, I did not check the proofs in close detail, but the theoretical results are consistent with what I would expect.", "experimental_designs_or_analyses": "There are no experiments.", "relation_to_broader_scientific_literature": "To my understanding, the paper has the following contributions to the literature:\n1. An efficient algorithm to the problem of identifying a feasible point of linear constraints with noisy feedback.\n2. The analysis approach extends the linear TS approach of Abeille and Lazaric (2017) to this new setting.\n3. An algorithm for safe linear bandits with $\\tilde{O}(\\sqrt{T})$ regret and $\\tilde{O}(1)$ risk without knowing a feasible point. I think this contribution is more minor given that a simple extension of Gangrade et al. (2024b) would give the same guarantees.", "essential_references_not_discussed": "None that I can think of.", "other_strengths_and_weaknesses": "No others", "other_comments_or_suggestions": "No others", "questions_for_authors": "1. The problem setup states that the algorithm only needs to handle the cases where the optimal margin is either strictly less than zero $M_* < 0$ or strictly greater than zero $M_* > 0$. As such, this doesn't handle the case where $M_* = 0$. I think it is important for the paper to discuss the case of $M_* = 0$ as the problem is still feasible in this case.\n2. What is the advantage of interpreting the minimum of the linear functions $\\min_i \\Phi_i a$ via the zero-sum game formulation $\\min_{\\lambda \\in \\Delta^m} \\lambda^\\top \\tilde{\\Phi} a$ ? This is mentioned several times and appears in the algorithm design, but at the end of the day it looks like the parameter distribution is chosen to be the same for each row of $\\Phi$ (actually each row uses the same realization). Couldn't we have gotten to the same result by treating each of the rows as separate linear functions and then used the minimum, as is done in the regret minimization safe linear bandit literature (e.g. Pacchiano et al. 2021)? I agree that the paper's approach is elegant, but the game theoretic formulation also seems to add more difficulty in understanding.\n3. In the application to safe linear bandits in Corollary 10, the paper applies the algorithm LC-LUCB from Pacchiano (2024). To my knowledge, LC-LUCB requires a safe action $x_0$ and the constraint value at that action $\\Phi_* x_0$. However, the paper only passes a safe action $x_0$ and the margin lower bound $M_{out} \\leq \\min_{i} (\\Phi_* x_0)_i$. I believe that it needs to be clarified how exactly LC-LUCB was applied here.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QNqj4AaxZo", "reviewer": "Reviewer_qJYJ", "summary": "This paper studies the linear feasible action search problem, where the goal is to find a point in the input space such that some linear constraints are satisfied. In each round the learner can query a point and observe a noisy version of its constraints. The authors provide a Thompson sampling approach to this problem and provide theoretical guarantees on its performance, both in the standalone feasible action search problem and when applied to the safe linear bandit problem.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Our thanks for your work.\n\nComparison to Gangrade et al 2024b. Thanks for pointing out these omissions, which we will fix.\n- Theoretical: Gangrade et al 2024b only study testing. We can extend it to FAS via something like our Lemma 7. In this case, the bound is a) $O(d^2/\\varepsilon^2 M_*^2)$ for their Algorithm 1, and b) $O(d^3/\\varepsilon^2 M_*^2)$ for the $(2d)^m$-game relaxation proposed on their page 9.\n    - These are similar to Thm 9, up to a factor of $d$ for us relative to a). This shows up in all known efficient methods (line 347, col 2).\n    - While they don't talk about safety costs, similar bounds to ours should also hold for them.\n- Experimental: As discussed starting line 150 col 1, the method of Gangrade et al. is inefficient. In particular, they propose choosing actions by solving $(2d)^m$ matrix games in each round (page 9 of their paper). The simulations in Appendix A work with $d = m = 9,$ and our method takes milliseconds for each round on a laptop. However, their proposal would need to solve $(18)^9>10^{11}$ games per round, which would literally take years!\n    - We will include a comparison for small $d,m$. \n    - However, making their method practical for nontrivial $d,m$ is an open problem beyond the scope of our submission. This would require studying how to appropriately relax and solve the optimisation problem described in (our) line 160 col 1.\n         - In particular, we want to point out that even simple ideas like nets don't work, since one would need a net of resolution $t^{-1/2},$ meaning $\\Omega(t^{d/2})$ games per round, which is prohibitive even for $t\\approx 100, d = 10.$ \n---\n Claims & Evidence: We disagree that terms are not defined, but are happy to clarify.\n \n- $\\omega_t$. This is defined on line 184 col 2 and used throughout the paper. It is the standard radius of the confidence ellipsoid. \n- Noise distribution: The underlying noise distribution is stated as $\\mathrm{Unif}(\\sqrt{3d} \\cdot \\mathbb{S}^d)$ in Theorem 9. This is indeed \"inflated\" in the sense of the common terminology for linTS (although our paper is not about linTS). \n- $m$: Recall that $\\Phi_* \\in \\mathbb{R}^{m \\times d}$ (line 30 col 2, line 162 col 2). So $m$ is the number of rows of $\\Phi_*$, or equivalently, the number of unknown constraints. Line 334, col 1 (just before Theorem 8) actually explicitly says this.\n- Theorem 8: We disagree. This theorem first describes a condition on a measure $\\nu$. Then it defines a measure $\\mu$ as the law of $\\mathbf{1}_m \\zeta^\\top$ when $\\zeta \\sim \\nu$ (equivalently, a pushforward of $\\nu$ under the map $\\zeta \\mapsto \\mathbf{1}_m \\zeta^\\top$), and says that $\\mu$ follows a $(B,\\pi)$-CO condition with instantiations of $B,\\pi$ in terms of the condition on $\\nu$. The CO-condition itself is described in Def. 4, and forms one of the central technical concepts of the paper.\n----\n Theoretical Claims:\n\n- \"Under $\\mathsf{Ball}_t$\": as stated on line 154 col 1, \"An inequality $a \\le b$ is said to hold under an event $E$ if $a {1}_E \\le b {1}_E$, where ${1}_E$ indicates $E$.'' The statement of the lemma defines the event $\\mathsf{Ball}_t$, and the inequality of line 267 col 2 holds once multiplied by an appropriate indicator. This \"under an event\" terminology is used to lighten the visual load of expressions in the cramped two-column format. \n    - Line 858: by definition, $\\bar{\\Phi}_t$ minimises $K(\\Phi)$ over $\\mathcal{E}_t$. Under $\\mathsf{Ball}_t,$ $\\tilde\\Phi_t \\in \\mathcal{E}_t,$ so this inequality is trivial.\n\n-  Theorem 8 proof, line 1019 - 1025: There is a typo in line 995: as stated in the statement of Theorem 8, $H = \\mathbf{1}_m \\zeta^\\top,$ so there is an extra $-$ sign in this line. If this is corrected, things should make sense.\n      - The display in 1019-1021 is opens up $H_t$. Then, by the discussion previous to 1019, if $\\zeta^\\top u\\_t \\ge \\\\|u\\_t\\\\|,$ we find that $\\tilde{\\Phi}\\_t a\\_{\\*} \\ge M\\_{\\*} \\mathbf{1}\\_m,$ which implies local optimism (the event $\\mathsf{L}\\_t$). But the condition on $\\nu$, and the independence of $\\zeta$ from the history directly means that this even has chance at least $p$ given the history (which fixes $u_t$). Finally, the norm of the rows of $H$ is just the norm of $\\zeta$, which is also controlled by the condition on $\\nu$. \n- Typo in Lemma 11: thanks. It should read $\\\\| (\\Phi - \\Psi) a\\\\|_\\infty$. \n- We will make sure to proofread the paper closely, and ensure that symbols are reiterated in their context to smooth over the issues you describe.\n----\nRelation to broader literature:\n- Line 55: This is the work of Gangrade et al. 2024b (discussed line 150 col 1).\n- Theoretical bounds of Gangrade et al. 2024b: see above. \n----\nRationale of the experiments: In a nutshell, appendix A attempts to build and study a practical methodology out of the theoretical study in the main text. The plan is discussed in detail on page 11. We will both discuss the early stopping trick in the main text, and include plots without it.", "claims_and_evidence": "- Some hyperparameters of the algorithm are not clearly specified (e.g. omega).\n- From the writing of the paper, I do not understand if the noise distribution is inflated. \n-  Theorem 8 is not written very coherently. The sentence below says that it reduces to something much more interpretable, which is not clear to see. Perhaps it would be better to just state the more interpretable condition?\n- On pg7 there is a discussion on the mild dependence on m, but m is not clearly defined here.", "methods_and_evaluation_criteria": "- There are no experiments in the main paper. In the appendix experimental results are shown but these are just comparison of their algorithm with different parameter settings. The algorithm run in these experiments seems to have a slightly different stopping time, it would be good to see how the original algorithm performs.\n- Most importantly, it would be interesting to see an experimental comparison to Gangrade et al (2024b).", "theoretical_claims": "- Statement and proof of Lemma 11 contains many typos.\n- Lemma 5 – not clear what ‘under ball’ means? Not enough details were provided to verify proof sketch of Lemma 5. Looking at the full proof of Lemma 5 in B.1, there were also some steps I could not verify, e.g. line 858.\n- I tried to verify the proof of Theorem 8 but could not. I particularly struggled with lines 1019-1025.", "experimental_designs_or_analyses": "I do not follow the motivation for the experimental setup, nor do I really understand what all the results are showing. It would be good to clarify the writing of Appendix A and give motivation for all parameter choices.", "relation_to_broader_scientific_literature": "- More referencing of related work that this paper builds upon would be good, e.g. line 55 the authors state that their approach builds on a recent bandit feasibility test but do not cite the work proposing this.\n- The authors mention that their approach builds on prior work by Gangrade et al (2024b) but the comparison of the results in this paper to those results is not sufficient. The authors claim their approach is more computationally efficient (which I can believe), but they do not mention how their theoretical bounds compare to those in Gangrade et al (2024b). Additionally, it would be good to see experiments to demonstrate the claimed efficiency gains.", "essential_references_not_discussed": "Missing discussions of Bayesian anslyses of TS, e.g. Russo & Van Roy", "other_strengths_and_weaknesses": "The introduction included a lot of notation which was not always defined. This made reading it quite difficult. \n\nIt would be good to give specific examples of where it is not possible to know a safe action a priori – this doesn’t seem like too strong of an assumption in many cases (e.g. often there is prior data available). However, it appears to be one of the key motivations of this work so some clear examples would be good.", "other_comments_or_suggestions": "Proofread carefully and make sure all notation is defined (and also include reminders to save having to scroll pages to find something hidden in the middle of a sentence).", "questions_for_authors": "1)\tTheoretical and experimental comparison to Gangrade et al (2024b).", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper tackles the problem of finding the point maximizing the safety margin relative to the unknown constraints and objective parameter of an LP, under noisy evaluations. Two flavours of this problem are studied. In one, the feasible action search setting (FAS), the goal is to find a point within a factor of $\varepsilon$ of the optimal safety margin with high-probability, while minimizing the number of samples required. In the other, the regret-control setting, the goal is to control both the safety cost as well as the regret, defined as the difference between the value of the objective function and the true optimal value of the objective function.

The authors introduce a Thompson Sampling based algorithm for this setting, FAST (Feasible Action Search via Thompson Sampling). The algorithm is accompanied by formal guarantees that is able to stop after $\tilde{O}(d^3 / \varepsilon^2 M_\*^2)$ samples in the FAS setting, where $M_*$ is the optimal margin and it is also shown that using FAST to instantiate existing safe linear bandit algorithms results in a regret scaling  as $O(\sqrt{d^3 T / M_{*}^2})$ and $O(1)$ risk.

The paper could benefit from improved clarity in notation and general presentation, numerical experiments and possibly a few words about the importance of the problem tackled here. Nonetheless, the reviewers agree that this submission presents a solid contribution to the conference.
Decision: Accept (poster)