Online Learning with Unknown Constraints
Authors: Karthik Sridharan
Seung Won Wilson Yoo
Venue: ICML 2025 poster (2025)
Keywords: Online Learning
Safe Learning
Primary area: theory->online_learning_and_bandits

Abstract: We consider the problem of online learning where the sequence of actions played by the learner must adhere to an unknown safety constraint at every round. The goal is to minimize regret with respect to the best safe action in hindsight while simultaneously satisfying the safety constraint with high probability on each round. We provide a general meta-algorithm that leverages an online regression oracle to estimate the unknown safety constraint, and converts the predictions of an online learning oracle to predictions that adhere to the unknown safety constraint. On the theoretical side, our algorithm's regret can be bounded by the regret of the online regression and online learning oracles, the eluder dimension of the model class containing the unknown safety constraint, and a novel complexity measure that characterizes the difficulty of safe learning. We complement our result with an asymptotic lower bound that shows that the aforementioned complexity measure is necessary. When the constraints are linear, we instantiate our result to provide a concrete algorithm with $\sqrt{T}$ regret using a scaling transformation that balances optimistic exploration with pessimistic constraint satisfaction.

Online Learning with Unknown Constraints
Karthik Sridharan' Seung Won Wilson Yoo
Abstract
is determined by parameters of the environment that unknown to the learner. For example individual fairness constraints may be defined by an unknown similarity metric (Gillen et al., 2018), or in robotics applications, safety may hinge on uncertainties such as an unknown payload weight (Brunke et al., 2022). Thus in such situations, the learner must learn the unknown parameters that characterize the safety constraint.
We consider the problem of online learning where the sequence of actions played by the learner must adhere to an unknown safety constraint at every round. The goal is to minimize regret with re- spect to the best safe action in hindsight while multaneously satisfying the safety constraint with high probability on each round. We provide a general meta-algoria aatt--aggoiitmm that leverages an online regression oracle to estimate the unknown safety constraint, and converts the predictions of an on- line learning oracle to predictions that adhere to the unknown safety constraint. On the thcoretical side, our algorithm's 's regret can be bounded by the regret of the online regression and online learning oracles, the eluder dimension of the model class containing the unknown safety constraint, and a novel complexity measure that characterizes the difficulty of safe learning. We complement our result with an asymptotic lower bound that shows that the aforementioned complexity measure necessary. When the constraints are linear, we in- stantiate our result to provide concrete algorithm with VT regret using scaling transformation that balances optimistic exploration with pessimistic constraint satisfaction.
In this work, we study the general problem of online learning with unknown constraints, where the learner only observes noisy feedback of the safety constraints. We consider ar- bitrary decision spaces and loss functions. Our goal is to design algorithms that can simultaneously minimize regret while strictly adhering to the safety constraint at all time steps. Naturally, regret is measured w.r.t. the best deci- sion in hindsight that also satisfies the constraint on every round. The learner only has access to an initial safe-set of actions/decisions to begin, and must gain more information about the safety constraint.
To solve this problem, we assume access to general on- line learning oracle that has low regret (without explicit regard to safety) and general online regression oracle that provides with increasingly accurate estimations of the unknown constraint function. The key technical insight in this work is in exploring what complexity or geometry al- lows us to play actions within guaranteed safe-sets while expanding the safe-sets and simultancously ensuring regret is small. We introduce a complexity measure that precisely characterizes this inherent per-step tension between regret minimization and information acquisition with respect to the safety constraint (with the key challenge of remaining within the safe set). We complement our results with a lower bound that shows that asymptotically, whenever this complexity measure is large, regret is also large. Our results yield an analysis that non- non-constructively shows the existence of algorithms for the general setting with arbitrary decision sets, loss functions, and classes of safety constraints. Fur- thermore, we instantiate these results explicitly for various settings, and give explicit algorithms for unknown linear constraints and online linear optimization obtaining the first algorithm with (VVT) regret.
1. Introduction
Online learning is key tool for many sequential decision making paradigms. From a practical view point, it is often the case that either due to safety concerns (Dobbe et al., 2020), to guarantee fairness or privacy properties (Zafar et al., 2019), (Levy et al., 2021), or many cases, simply due to physical restrictions the real world (Atawnih al., 2016), the agent or learner often must pick actions that not only effective but also strictly adhering some constraints every round. Often, the safety constraint
Department of Computer Science, Comell University, Ithaca NY, United States, Correspondence to: Scung Won Wilson Yoo <sy536@ cornel.edu'>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Online Learning with Unknown Constraints
Key Contributions
2. Related Works
Online Convex Optimization and Long Term Con- straints: (Mahdavi et al., 2012) initiated the problem of online convex optimization with long term constraints, a variant of online convex optimization where the learner is given a set of functional constraints (fi(-) S 0) and is required to ensure that the sum of constraint violations > E f((zz) is bounded rather than ensuring that the constraints are satisfied at every time step. For the case of known and fixed constraints, (Mahdavi et al., 2012) obtain (TT1/2) regret and (TT3/4) constraint violation. This was recently improved in (Yu & Neely, 2020) to be (33) regret and (1) constraint violation. Furthermore, (Neely & Yu, 2017) study a variant with time varying constraints (+,+()) < 0) and and achieve ((T1/2) regret and long term constraint violation. (Sun et al., 2017), (Jenatton et al., 2016), and (Yi et al., 2020) study variations of this problem.
We introduce novel complexity measure Vx(t) de- fined in eq. 5, that characterizes the difficulty of safe learning. On high level, it captures the per-timestep trade off between loss minimization and information gain w.r.t. unknown constraint with K. serving as the weight placed on information gain.
We provide a new safe learning algorithm under an known constraint (Algorithm 1) that utilizes an online regression oracle w.r.t. F, where F is the model class to which the unknown safety constraint belongs, and an online learning oracle that guarantees good perfor- mance w.r.t. II, where II is benchmark policy class. Notably, algorithm is able handle adversarial contexts drawn from X, arbitrary action set A, safety model class F, benchmark class II, operates under gen- eral modeling assumptions, and enjoys the following regret bound:
Bandits with Unknown Linear Constraint: The area of work most similar ours is the study of safe bandits with unknown linear constraints. Initiated by (Moradipari et al., 2021), this line of works studies a linear bandit setting, where a linear constraint is imposed on every action a of the form of (f, a,) - I 0 with unknown f and known b. Similar settings involving linear bandit problems with uncertain and per-round constraints have been studied by (Amani & Thrampoulidis, 2021), (Pacchiano et al., 2021), (Hutchinson et al., 2024). (Pacchiano al., 2021) study the setting where constraints are satisfied in expectation, and (Pacchiano et al., 2024) and (Hutchinson et al., 2024) improves this to high probability satisfaction. Safe Convex Optimization with Unknown Constraint(s): Safe convex optimization with unknown linear constraints and noisy feedback was studied in (Usmanova et al., 2019). (Fereydounian et al., 2020) seeks to optimize a fixed convex function given unknown linear constraints, and focuses on sample complexity. Closest to our work is that of (Chaud- hary & Kalathil, 2022), where the authors study time vary- ing cost functions and achieve ((T2/3) regret. A recent concurrent work due to (Hutchinson et al., 2025) improves this O O(VT). (Hutchinson & Alizadeh, 2024a) studies a variant with non- non-linear constraints and first order feedback, and (Hutchinson & Alizadeh, 2024b) studies a variant with d + 11 points of feedback.
Regrety 1
T inf Σ +
aT Regon F)& a)
a
+ Regor RegoL(T,8,1]
where Regon 6T, denotes the regret bound guaranteed by the online regression oracle on F, a(F,a) denotes the eluder dimension of F, and Regol (T, 6, II) denotes the regret bound guaranteed by the online learning algorithm w.r.t. IT.
Via lower bound, we show that asymptotically, if there exists a for which
lim T-000
1/T
Σ c0 c0 0, I=1
no safe algorithm is able to obtain diminishing regret.
If per- per-timestep constraint satisfaction is relaxed to long term constraint satisfaction, we show a modified version of our main algorithm yields bounds without (1).
For several settings including finite action spaces, lin- car & generalized linear, and polytopic settings we give an instantiation of A = x² that satisfies (t()) < and,
Per Timestep Tradcoff Between Loss Minimization and Constraint Information Gain The SO-PGD algorithm due to (Chaudhary & Kalathil, 2022) adopts an explore- first then exploit strategy which results in O(T2/3) regret bound, whereas the ROFUL algorithm due to (Hutchinson et al., 2024) strikes a better balance between regret mini- mization and conservative exploration of the constraint set. The Decision Estimation Coefficient (DEC) due to (Foster et al., 2023), (Foster et al., 2022) explicilly strikes a balance loss minimization and the information gained due to obser-
Regret, S k" inf { aI' Regor (T, Regog(T, (T Regoo (T,
a
For linear settings we instantiate this result to give an algorithm with O(VT) regret. We extend our main algorithm to handle valued constraints
2

---

Online Learning with Unknown Constraints
()))) S 0. The learner in turn is also only vation. Our proposed algorithm seeks similarly balance loss minimization and exploration of the constraint set.
allowed to take actions da s.t. I (7), S 0. Since we are interested in making no constraint violations while taking our actions, learning is impossible unless we are at least given an initial set of safe actions. For any context & E X, we assume that we are given a non-emply set An S A that is guaranteed to be safe. For settings with no context (i.e. X 0). we denote the initial safe set as Ag.
3. Setup and Preliminary
We consider the problem of online learning with unknown constraints imposed on actions the learner is allowed to play from. The learning problem proceeds for T rounds as follows.
3.1. Additional Notation
For / = ,
We use the notation ls{(z) to denote the projection of a vector I E R onto some convex set S S R For a positive definite matrix M E Raxdd and vector E Rd we denote the norm induced by M as || == Vz, We denote the convex hull of a set S as Conv(s). Let { == 21,..... It be shorthand for a sequence. For a scalar-valued function class F S A x X' + [0, 1]. we denote AF x) == sup,, f(a, x) - f'(a, x). For a vector-valued function class F A x - [-1, 1]mh, de- note 43 (a, r (l.
Nature selects a context 3t X
The learner selects a safe action 0t E A
Nature selects an outcome Y/: EV
The learner receives safety feedback 24 Z
where X' is the context space, A is the action space, y is the outcome space and 2 is the safety feedback space. Here, the context chosen by nature z E X, action chosen by learner a E AA and outcome chosen by nature y E y define the loss suffered by the learner É(a, x. y). for a bounded loss function é A x X' x y + [0. 1]. We assume a full information feedback setting with respect to the losses the learner observes ye E Y.
) where
|| ll is the fox norm. For a set G, we denote (G()) the set of distributions over G. For a vector E Rd and i E [d]. let æ|i] be the i'th coordinate of I. We adopt a non-asymptotic big-oh notation: for functions f.g: : X + R+, f O(g) if there exists some constant C > such that f(x) S Cy(x)
Given a context E X, an action chosen by the learner A is considered safe if (a, O for unknown function f* E F S A X + 1-1, While f is un- known to the learner, the functiin class F is known and encodes prior knowledge about the safety constraint. F may be parameterized by linear models, neural networks, or other rich function approximators depending on the problem setting. At every timestep 1, the learner receives feedback on unknown safety function f* through safety feedback 2, ~ Psignal f xx))), where Psignal [-1, + !(Z) and (Z) denotes the set of distributions over Z. We high- light the fact that given Ot and Tt, 2t is conditionally in- dependent of the history. This captures a wide variety of feedback settings, including those where Z F and 2, f (at,, x22) + for noise variable &., and those where Z = 10 and 2, is the result of coin flip with suc- cess probability determined by ['((a,,z)) 2z). Whenever the feedback function is not made explicit, we assume that the feedback is given by 2, = f (at, x.) + &.. Throughout the paper, we will compare the performance of our algorithm against a known policy class IT C X' - A. The goal of the learner is minimize the regret defined as:
for all x E X. We write f = o(g) if for every constant e,
there exists a zo such that fx) S cg(x) for all x 2 z0.
3.2. Online Regression Oracles and Signal Functions
Similar to prior works concerned with estimation of function classes (Foster et al., 2018a), (Foster & Rakhlin, 2020), (Foster et al., 2021), (Sekhari et al., 2023a), (Sekhari et al., 2023b), we assume our algorithms have access to an online regression oracle, OracleoR- However, unlike these prior works that assume that the provided online regression oracle enjoys a sublinear regret bound, we require that our oracle satisfy slightly weaker condition that allows for algorithms geared towards realizability.
Assumption 3.1 (Online Regression Oracle). The algo- rithm Oracleor guarantees that for any (possibly adversar- ially chosen) sequence {ar, 24 YT> for any 8 E (0, 1), with probability at least 1 6, generates predictions {&) satisfying:
T Σ - f & RegoR FF
Regret, ==
Assumption 3.1 is closely linked with the model Psigual that produces feedback about constraint value, and any regret- minimizing oracle for strongly convex losses can be con- verted into an oracle that satisfies the assumption with high probability. We formalize this in Lemma C.6 in the ap- pendix. For instance, if 2t ~ Psignal (f (at, 2x)) is given
T Σ
T Σ (1)
E(a,, Dz, vr) 1=1
min REIl ((((()))a))00=
which is the regret with respect to the optimal policy a in hindsight that is safe on every round, i.e. Vt E
3

---

Online Learning with Unknown Constraints
by 2 M (a1,,)) + & where & is any sub-gaussian dis- tributed random variable, then any online square loss regres- sion algorithm on class F that uses 2, corresponding out- comes will satisfy Assumption 3.1. Similarly, if 24 E {0, 1} is drawn as P(z = (at, at)) i exp(f"(ae,x)) = Psigual (a,, o4)) (ie. the Boltzman distribution), then one can show that Assumption 3.1 satisfied by running any online logistic regression algorithm over class with 2, as labels.
straints, we will pass increasingly accurate approximations of the true set of safe actions for given context 2t (i.e. {a E A (a, xz) S <0} in place of A, to OracleoL. The complexity of the unconstrained variant of Assumption 3.2 is well understood ((Rakhlin et al., 2010)). On a first glance, it may appear that the adversarially chosen constraint sets A may pose significant challenge to learnability. We show that this is not the case using online symmetrization argu- ments developed in ((Rakhlin et al., 2010)) and minimax analysis:
(Rakhlin & Sridharan, 2014) characterized the minimax rates for online square loss regression in terms of the offset sequential Rademacher complexity for arbitrary F. This for example, leads to regret bounds of the form, RegoR
Proposition 3.3. There exists an algorithm satisfying As- sumplion 3.2 with
Regol (T.6,I) S Rad (T) where Rod
= Olog (F1) for finite function classes F. and RegoR (T,
(T. RegoR(T.F)
(od)o(()) when F is d- dimensional linear class. More examples can be found in (Rakhlin & Sridharan, 2014) (Section 4) and efficient im- plementations can be found in (Krishnamurthy et al., 2017) and (Foster et al., 201
(T) is the sequential Rademacher complexity of the loss class, defined as:
Radion to1l (T)
sup E. yx
sup TEll
Eel ((a
x
3.3. Online Learning Oracles with Given Constraints
where in the above supremum over and x are taken over all mappings of the form y U [+1]² + y and
Next, we consider the following online learning problem with given constraints, which will be instrumental in solving our problem of online learning with unknown constraints. On every round 1, nature first announces context it E X and constraint set corresponding to this context Ax(x,) S A. Because the context is fixed every timestep, we drop the dependence 2, and abbreviate the constraint set as A,.
(=1' + X respectively.
Various properties and examples of bounds on Rad (T) can be found in (Rakhlin al., 2010). Notably, this result is non-constructive and only guarantees the existence of such regret minimizing oracles. In section 5 we provide constructive -eeseet based algorithm in the online linear optimization setting.
The learner responds with a distribution pa E (2() and draws a2 ~ Pt. Nature then produces loss function y/ E V. The learner suffers loss E(ac. 31)
Let IT C X A be some given policy class the learner is benchmarked against. A policy π E II satisfies the given constraint time i if <(xx) E Ar. Let denote the set of policies that satisfy all given constraints (in hindsight) as I1 = { E II : Vt, (xx) E Ar).
3.4. Eluder Dimension
Before delving into our main results, we recall the following definition of e-dependence and eluder dimension (Russo & Roy, 2013), (Foster et al., 2021), (Foster et al., 2023).
Definition 3.4.
The goal of the learner is to minimize regret w.r.t. the best policy in lly. We assume access to an online learning oracle, Oracleol that has bounded regret for the problem of online learning with given constraints:
An action, context pair (a, x) E A x X' is dependeent on {a;, x; 21 )im1 C Ax X' w.r.t if every f. f e F satisfying v ()=n((a,, 2;) f' 2;))² S also satisfies f(a, f) x) S e. (a, x)) is e-independent w.r.t. F is not e-dependent on {(a,, 2))]i=
Assumption 3.2 (Online Learning Oracle). For any se- quence of adversarially chosen sets, contexts and outcomes (At, Tr. y/ IT_ and any 5 E (0, 1) with probability at least 1-& 8, the algorithm Oracleol produces a sequence of distri- butions {pe ) satisfying Pt E ((A:)) for all i E [T] with expected regret bounded as:
The eluder dimension E(F, is the length of the longest sequence of pairs in x X such that for some e' >, each pair is e é'-independent of its predecessors.
Σ
I (1...,,, min ac
Melly Σ (TT())
The eluder dimension is bounded for variety of function classes. For example, when F is finite, e) < | 1, and when FF the class of linear functions, E(F,c) < (dlog(1//e) The eluder dimension of function class F will be a component of our regret bounds.
< Regoo (T, II
In our application to online learning with unknown con-
4

---

Online Learning with Unknown Constraints
4. Main Results
respect O(F(, implies competitiveness with all safe actions.
We will deliv further into this intuition later in this section.
We first propose our complexity measure (-) that captures the per timestep trade-off between loss minimization and in- formation gain w.r.t safety function set JF. We show that this complexity characterizes the diffieulty of online learning with unknown constraints by showing an upper bound fea- turing (-) and lower bound that demonstrates a bounded (-(+) is asymptotically necessary. Finally, we supplement our results by slightly modifying our algorithm to attain long term constraint satisfaction allowing us to contribute to the literature on online learning with long term constraints. Notably, (+) does not appear in this bound, suggesting this complexity measure is inherent to per-timestep constraint satisfaction.
For a set 9 S F. we recall the definition of the width of g with respect to action a and context x introduced (Russo & Roy, 2013):
As(a,
sup g(a, x)) - g (a(a.x)
(3)
g.g'Eg
For any action a O(G.z) and g E 9, (6.a(a, I Ag(a, hence the width captures notion of how far an optimistic action is from being pessimistic. Simultaneously if (a, is small, all functions in G have similar values on indi- cating that a provides little information if our goal is to differentiate members of g. These two facts will be instru- mental in our analysis.
4.1. Complexity Measure and Main Theorem
We now utilize the regret-minimizing properties of Oracleol to be competitive w.r.t. O ((F,, Suppose we pass given context z, and optimistic set O inputs to the online learning oracle OracleoL- Denote fr. E (2(+t) as the dis- tribution recommended by OracleoL- Because Or contains all constraint-san seassraint--attsfyingg actions with high probability, com- bined with the regret guarantee of OracleoL in Assumption 3 3.2, this guarantees that actions drawn from P. will have good performance in regret.
Given the oracle assumptions, we introduce few building blocks, define our complexity measure Vx, and provide our main theorem. We first introduce sets of functions likely to contain our true safety function f", and from these sets of functions, build a pair of sets approximating the true safe action set.
Suppose up until some timestep t we have played ac- tions {a.) [0 and seen contexts and noisy observations {z,, 2. > so far. Given the history {a,, Tx, 2g P-= sup-
As Proposition 4.1 suggests, playing actions from Ps en- sures constraint satisfaction. Motivated by this fact, we aim to play actions drawn from Q(P:) optimizing a certain objective striking a balance between matching the perfor- mance of (potentially unsafe) p: E ((O,) and information acquisition captured by width. To this end, let M be any mapping (2O.)) - ((P.)) parameterized by the function class F, and context Iz. We will show that when draw can bound regret by quantities involving the eluder dimension, Regon. Regor. and a novel complexity measure yM defined as:
1--1 pose OracleoR produces a sequence { Let us define a version space Fe C. Fo defined as:
F
(- Fo: E(raa. - 2.)² S Reson (T, Fo))
(1)
By Assumption 3.1, the sum of squares deviations (E I' (o,,, < Regon (T, a. Fo) with high probability. Therefore, the version spaces Fr contain f with high prob- ability. Now suppose we have some set S F containing the true safety function f". Given a context X, we de- fine the optimistic action set x)) and pessimistic action set ((),xx) as:
actions P:: Fr,
VM (pe, F,,
sup wEy
E ((s
[(a,, v)]
E. aerip
[E(āe, xr, w)
O(G,z)= = {a A 3f 9, x(a 5 a( = {a A Vʃ E / 5}
(2)
KK (F
E
( (ar,
Consequently for a given k, the optimal mapping M' is to optimize for this complexity measure through a saddle-point optimization:
As shorthand, we denote O, == O(F, P:: := ((F,, The optimistic set represents the set of all ac- tions that could be safe, and the pessimistic set represents the of all actions that are guaranteed be safe. We capture this notion in the following proposition:
M (F,, Fe,
argmin sup P.E((()) wEy aempp
2.,0,, 22, v)]
E. Semp.
(K (4)
Proposition 4.1. Suppose f E F. Then:
E [AF, (a), acmpp
x)),,) (a A: (a, A < 0} C (g).x)
Wherever it is clear what the arguments to the mapping are may drop them e.g. in non-contextual setting, the context argument dropped.
Intuitively, this proposition suggests an algorithm playing from xt) is always safe, and competitiveness with
5

---

Online Learning with Unknown Constraints
We note that the above optimization can be (inefficiently) solved desired accuracy through standard techniques by treating it as two-player game where the min-player chooses and the max-pia max-player choses f. f', y and we form an e-net over the set of actions. Later in section 5, we will give examples efficient mappings that can be used instead of this optimal mapping. Let us define the complexity mea- sure (+) == VMM (+) as the value attained by the optimal mapping:
Algorithm General Constrained Online Learning
Input: OracleoL. OracleoR, An(-), 6 E (0, 1), K, M Fo (ʃ E F Vr E X, Va Ao( 00 3: for 1, , do Receive context St.
Fi = ( Σ (f) - 22.)²
Regon 6, Fo)
O2 O(Fi, 344) P: P(F(,
6: P: Oracleol (Zr, O,)
7: Pt (F,
(pr, Fr, xx)
8: Draw d₁ Pt
inf sup R [Mae: p.En(PA) -empp
I ap-pe
(5)
Receive noisy feedback 24
10: Update & OracleoR:(M: Tt, z))
-R E |A (ar, aprpp
11: Play a and receive yr
12:
end for
Vx is similar in spirit to the Decision Estimation Coefficient (DEC) of (Foster et al., 2023) in that it balances a notion of worst-case loss with one of information gain. Specifically, Vx captures the per-step tension between loss minimization with respect to āj ~ Pt produced by Oracleol and informa- tion gain with respect to safety function set Fe, measured by the width of action de on Fr. We now present our main thcorem:
Theorem 4.3. For any ō E (0, 1) with probability at least 35, Algorithm I when using mapping M produces sequence of actions {ar)e=s that are safe and enjoys the following bound on regret:
Regret, S inn K20
Vx (pe, Fe,
Theorem 4.2. For any (0, there exists an algorithu that with probability least 35, produces sequence of actions (oot= that are safe and enjoys the following bound on regret:
+ {all' + 20 Regon (T, 8,
RegoL Regor 2T log(t)
Furthermore, using K (F.M) defined as
Regrety S inf =20
Σ
Val Valpi,
Bow az [K wil Ea-g(t(a.x.1))
in faT + 20 RegoR (T,8, (o)
sup PEF.EEx.PAA
B A (1,z))
+ Regor (1) + log(
have
Regrety I K5 inf oT 20RegoR ( (o)6,
Moreover, there exists a problem setting such that if there exists >> 0 satisfying
a
+ Regor (T, + TToog(
1
lim
Σ (p.. Fi,z) > 0,
The proof follows by leveraging the low-regret guarantee of OracleoL, manipulating the definition of >/M on a per- timestep basis, and bounding the sum information gain terms A,, (at, xx) by an extension of techniques first pre- sented in (Russo & Roy, 2013). In the next section, we give concrete examples of efficient M which yield bounded x* for a few important settings.
then, safe algorithm (with high probability) can ensure that Regrety- o(T).
Theorem 4.2 follows by combining the upper bound (Theo- rem 4.3) with the lower bound (Theorem 4.4), presented in the following subsections.
4.3. Lower Bound
4.2. Algorithm and Upper Bound
Assuming the existence of Oracleol with bounded Regor. is reasonable as f could potentially be the always-safe zero function fo A + 0, reducing the problem down to exactly the unconstrainted online learning problem as O, = A. Being able to perform regression on F using a OracleoR with bounded RegoR and assumption that eluder dimension
We now present an algorithm that attains the upper bound in Theorem 4.2. While using the optimal mapping M* gives us the best upper bound, solving the optimization involved (eq. 4) may be difficult. To address this, we allow the use of any (potentially efficient) mapping M.
6

---

Online Learning with Unknown Constraints
of F is well behaved are also commonplace. However, the reader may question if the sum Σi= Ft, must necessarily be small for safe learnability. We show that at least asymptotically, Ei=1 (P.. zz) indeed must be small to guarantee sublinear regret. We capture this notion in the following theorem:
Notably, (.(+) does not appear in either bound. This moti- vates the question: is assuming access an online learning oracle and online regression oracle and that the eluder di- mension of F is small enough for us to create algorithms that make no constraint violations with high probability?
Unfortunately the answer is no. We need more assumptions on the initial safe set which is what the mapping is utilizes. Specifically consider the case where {(a I, y) = y TTo a. the constraint set is F {(a, x) + fTa Il - 1} and suppose Ao {0}. In this case E(F e) = d'log(//e, and both the online learning oracle and online regression oracle are readily available and satisfy Assumptions 3.1 and 3.2 (e.g. use gradient descent and online linear regression algorithm). However, since Ao = {0} the initial pessimistic set is Pi {0]. However since we are forced to play in this set, don't gain any information about f and hence in the subsequent rounds F, = F and P. = P1. Thus we cannot hope to play anything other than the single safe choice an = 0 which prevents us from achieving low regret.
Theorem 4.4. Suppose we are given some Au, X' = O.
y = 0. I' E F and losses f. A + R are fixed such that for any a E A satisfying (a) > O, l(a) =
mi (a)) P(a"). ) Furthermore suppose Ve, ((F.c) is finite. Then, if there exists
such that
T lim E
F.).
then, safe learning is impossible, i.e. no algorithm that is safe on every round (with high probability) can ensure that Regret,- = oTT).
On high level, we show that if is such that limy- 1 T ET=IVaL Fz) c² > O, then there must be a p 3 Ao that is is guaranteed to be safe and Va E p* we can estimate (a) to arbitrary accuracy. Simultaneously we show that this p* has the property that all actions within it are sub-optimal in loss by at least c* when compared to best safe action. Further, this set p* non-expandable, meaning that we cannot find more actions that are guaran- teed to be safe based on playing a E P*. Once we show the existence of P satisfying the aforementioned proper- ties, we can simply announce to any learning algorithm Ao P Because the set is non-expandable, and since the learning algorithm must be safe, we conclude any algorithm is doomed to only play actions within p* which is known to be c* sub-optimal.
5. Examples
In this section, we will give examples of function classes F where we can construct mappings M that have bounded x² (F, M). Consequently, this results in concrete regret bounds from Theorem 4.2 if these mappings are used in Algorithm 1.
5.1. Finite Action Spaces
We first consider the setting of finite action spaces, where A = [K] X' is arbitrary, J.AS C x X' + [-1, and losses are functions E A x' - [0, 1]. Suppose we make the following assumption that promises some separa- tion between function values:
4.4. Per- Timeseest Constraints vs Long Term Constraints
Assumption 5.1. VF C FFAS s.t. f F and P(F, + O(F, x)), maxaeP(F,a) .) AF(a, 2 Do > 0
Suppose we are only interested in ensuring that the sum of constraint violations Σi fa .r)) is o(T), as is the goal in the line of works studying online learning with long term constraints (Mahdavi et al., 2012), (Yu & Neely, 2020), (Sun et al., 2017). We show that this can be done without use of the mapping M present in the main algorithm- the idea will be to simply play the output of the online learning algorithm given sets (T Algorithm defined in the appendix guarantees:
This assumption is in fact necessary for safe learning for large T. To see this, suppose F C FFAS satisfies P(F*, ,x) j O(F*, x) but Va E P(F*,x), 2x), Then, we have no hope of shrinking F and consequently expanding P(F*, .)). If the adversarial losses have values of for all a E P(F*,z) and values of for all a & P(F ..), we'd suffer constant loss for all subsequent rounds.
(a, x) 0.
Now, for a set of functions F S FEAS and context let A x) = argmax,e 1) be the width- maximizing action in the pessimistic set. We define a map- ping for this setting as:
Lemma 4.5. For any 8 E (0, 1) with probability at least 1- 28, Algorithm 2 produces a sequence of actions {a
that satisfies:
(a)(F.)) if if # (P(F,))+O(F))) ((F
PAS (p: =
Regret, S Regor(T, (T, 11) and
P
otherwise
Σ (2) S inl NTT+ 20RegoR (T, (F)
a
Where er is the distribution that places all its mass on a. The
7

---

Online Learning with Unknown Constraints
above mapping leads an explore then exploit algorithm with respect to JFAS that plays the maximum width safe ac- tion until no uncertainty remains w.r.t JFAS, We show that MFAS as defined above has bounded s= (FFAS, (FFAS,MPPS,) MFAS).
(e), b E R we provide online gradient descent based algorithm satisfying As- sumption 3.2 (Algorithm 3). It is randomized algorithm that plays elements of the convex hull of ((F) and is stated in the appendix.
losses, where E(at ((
Lemma 5.2. Suppose Assumption 5.1 holds. Then, N² **FPAS, _MAAS 5 2.
Lemma 5.7. Suppose Assumption 5.4 holds. Then Algo- rithm 3 satisfies Assumption 3.2 with:
Remark 5.3. We note that we only require the existence of An and not knowledge of it. Ae is only required to set n-' - x* (JFFA MFAS). In appendix section C.1, we describe procedure of adaptively selecting time-varing Kt at every timestep such that Vx, (t) < 0 and max; K₁ S 2x*
Regoi (T, S 4DrDoyTlog(2))
Finally, (Russo & Roy, 2013) show that the Eluder di- mension of the linear function class is E {(Fineear, c) = log(/e)). Combining these facts with our main re- gret bound, we have:
5.2. Linear Constraints
Next, we consider the setting of linear constraints where A C Rd, X = 0. II = {. + a E A} and losses are functions : Axx' + 1]. show randomized variant of the scaling-basee -banng---aedddee doubly-optimistic method presented in (Hutchinson et al., 2024) (Hutchinson et al., 2025) has bounded x*. Suppose we make the following assumption on A and
Corollary 5.8. In linear case, for any 8 > O, with prob- ability at least 1 - 5 Algorithm satisfies: Regret, =
O { [ log( /)olog((--)
5.3. Composing an Activation Function
Assumption 5,4. The action set A S IR is convex, com- pact, and bounded, max ||a||2 S Da. The losses are lipschitz with constant Dg, Vy E y, Va, E A, [((a, y) E(a', v)l S Dzlla d'|]. The constants D, Dg are known to the learner.
Suppose we know that some function class 9 C A x X' +
[-1, has bounded k (G, Mg) for some mapping Mg. Consider a fixed activation function o : [-1, - [-1, 1] satisfying the following:
Assumption 5.9. a [-1,1] + [-1, is a fixed, dif-
ferentiable non-decreasing function such that o(0) = 0. Furthermore, there exists g such that for all x E [-1, 1). 0 < < o' (z), where a' is the derivative of
Let consider the following function class: Flin ((a,x) x)) + (f.a) - fl E ) where b > 0 is fixed, and the unknown constraint is (f", - b < 0. Suppose the initial safe given to the learner is Ao = {a E A: ||||| - 6). Then, any Fn = (ʃ e Rdd : |fll < 1}, since f with [| > 1 has f
Consider the following function class formed by composing G with a: (g) = {(a, x)) - a (g(a, x)) lg E g} The un- known constraint is then (ggg (a,x)) S for some g* E G. We show that if k= (G, Mg) is bounded for some mapping Mg. K* (a(G), Mc) is also bounded. As a consequence of Lemma 5.6 for FLin and the below lemma for compositions with activation functions, generalized linear function classes ((Kakade et al., 2011)) have bounded n²"
(f.b [[]] b > 0, yet || E Ao violating the promised initial safe set.
Remark 5.5. Suppose that An is the & ball of diameter b instead of the lg ball of diameter b. Then Fo becomes the unit for ball- and the eluder dimension (Foo c) increases by a factor of log(d).
Now, for a set of functions F and à E let), (e; = max {7 E [0, 1] 7ā E P(F)}. Define M (5: F) as the distribution induced by drawing à ~ f and outputting F)ā In other words, we scale down each action to ensure that it is safe. We show that this scaling-based map- ping MLin has bounded x² (FLin MLin).
Lemma 5.10. Let & be function class with bounded K" (G. Mg) for some mapping Mg. Suppose assumption 5.4 holds. Then R² (a()). < (9.
5.4. Vector- Valued Constraints
Our algorithms naturally generalize to settings where the learner must satisfy vector-valued constraints. Specifically, given a context æ E X, an action a E .A is now considered safe if fa llx I 0 for unknown vectur-valued function i E F A X + 1|m We formalize this notion in the appendix subsection C.4 it is a straightforward ex- tension of our main results. Notably, for the setting of m linear constraints, with probability at least 1 8, regret is O mnd log( VTloo) /Tlog(6-1)). T
Lemma 5.6. Suppose Assumption 5.4 holds. Then, H² (FFiin MLin) < D.D.
Using the mapping MLin, we can get concrete algorithms for the setting of linear constraints, no contexts, and linear losses. Specifically, we set OracleoR to be the Lel-Azoury-Waramne forecaster (Vovk, 1997), (Azoury & Warmuth, 2001) which satisfies Assumption 3.1 with RegoR F) S Odlog( ())). In the case of linear
8

---

Online Learning with Unknown Constraints
Interestingly, we can interpret each of the coordinates as an independent safety feature, all of which must adhere to safety. Consequently, [a]] denotes how unsafe action is on safety feature i, and the constraint is that it cannot ex- ceed b. In this scenario, suppose the safety feedback space is 2 [m] and let the safety feedback function Peignal (f() as per the Boltzmann distribution on [[]][[]] ... [a]l This a natural form feedback known as the Bradley-Luce- Shepherd rule (CCrisstiano et al., 2017), (Bradley Terry, 1952)) that outputs which constraint is most likely be violated when given options of varying magnitudes, human- -eeerrtgeee feedback has been shown to follow such distribution ((Ghosal et al., 2023)). In this setting, we can use the logistic regression oracle w.r.t F as OracleoR- When learning linear predictors, (Foster et al., 2018b) provide an efficient algorithm with RegoR I T
control of redundant robots with guaranteed joint limit avoidance. Robotics and Autonomous Systems, pp. 122- 131, 2016.
Azoury, K. S. and Warmuth, M. K. Relative loss bounds for on-line density estimation with the exponential family of distributions. Machine Learning, pp. 211-246, 2001.
be given by: P(= = i a) Eye(m] (()))
exp( [d]]]))
Bradley, R. A. and Terry, M. Rank analysis of incom- plete block designs: I. the method of paired comparisons. Biometrika, pp. 324-3444555 1952.
Brunke, L., Greeff, M.. Hall, A. W., Yuan, Z., Zhou, S., Panerati, J., and Schoellig, A. P. Safe learning in robotics: From learning- based control to safe reinforcement learn- ing. Annu. Rev. Control. Robotics Auton. Syst. pp. 41 444, 2022.
Chaudhary, S. and Kalathil, D. M. Safe online convex optimization with unknown linear safety constraints. In Thirty- -Srrty--iithhaa AAAI Conference on Artificial Intelligence, pp. 6175-6182 AAAI Press, 2022.
5.4.1. POLYTOPIC CONSTRAINTS WITH SCALAR FEEDBACK
Suppose the safety function class is polytopic: FPoly [(,,)) Fa - F E Rdxm]
Christiano, P. F., Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, D. Deep reinforcement learning from human preferences. In Advances in Neural Information Processing Systems 30, 2017.
Furthermore, suppose the unknown constraint is R. for some E JPoly, In this setting, M as defined in Lemma 5.6 has bounded n= for JPoly:
ll <
Dobbe, R., Hidalgo-Gonvzlez,, P., Karagiannopoulos, S., Henriquez-Auba, R., Hug, G., Callaway, D., and Tomlin, C. Learning to control in power systems: Design and analysis guidelines for concrete safety problems. Electric Power Systems Research, pp. 106615, 2020.
Lemma 5.11. Suppose Assumption 5.4 holds. Then, x* *"(PPoly, M < D.D.
Acknowledgments
Fereydounian, M., Shen, Z., Mokhtari, A., Karbasi, A., and Hassani, H. Safe learning under uncertain objectives and constraints. arXiv preprint 1iXXi:2000.1332000 2020.
KS acknowledges support from LinkedIn-Cornell grant.
Impact Statement
Foster, D. J. and Rakhlin, A. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In Proceedings of the 37th International Conference on Ma- chine Learning, pp. 3199-3210. PMLR, 2020.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Foster, D. Agarwal, A., Dudík, M., Luo, H., and Schapire, R. E. Practical contextual bandits with regression oracles. In Proceedings of the 35th International Conference on Machine Learning, pp. 1534-1543. JMLR.org, 201 8a.
References
Agarwal, A. Selective sampling algorithms for cost- sensitive multiclass prediction. In Proceedings of the 30th International Conference on Machine Learning, pp. 1220-1228. PMLR, 2013.
Foster, D.J., J., Kale, S., Luo, H., Mohri, M., and Sridharan, Logistic regression: The importance of being improper. In Conference On Learning Theory, pp. 167-208, 2018b.
Amani, S. and Thrampoulidis, C. Decentralized multi-agent linear bandits with safety constraints. Proceedings of the AAAI Conference on Artificial Intelligence, pp. 6627- 6635, 2021.
Foster, D. J., Rakhlin, A., Simchi-Levvi, D., and Xu, Y. Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement-bee based perspec- tive. In Conference on Learning Theory, pp. 2059. PMLR, 2021.
Atawnih, A., Papageorgiou, D., and Doulgeri, Z. Kinematic

---

Online Learning with Unknown Constraints
Foster, D. J., Rakhlin, A.. Sekhari, A., and Sridharan, K. On the complexity of adversarial decision making. In Advances in Neural Information Processing Systems 35, 2022.
Levy, D., Sun, Z.,, Amin, K., Kale, S., Kulesza, A., Mohri, M., and Suresh, A. T. Learning with user-level privacy. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Process- ing Systems 2021, NewrlPS 2021, December 6- 14, 2021, virtual, pp. 22466-12479, 2021.
Foster, D. J., Kakade, S. M., Qian, J., and Rakhlin, A. The statistical complexity of interactive decision mak- ing, 2023.
Mahdavi, M., Jin, R., and Yang, T. Trading regret for efficiency: online convex optimization with long term constraints. Journal of Machine Learning Research, pp. 2503-2528, 2012.
Ghosal, G. R., Zurek, M., Brown, D. S., and Dragan, A. D. The effect of modeling human rationality level on learn- ing rewards from multiple feedback types. In Thirty- Seventh AAAI Conference on Artificial Intelligence, pp. 5983-5992, 2023.
Moradipari, A., Amani, S., Alizadeh, M., and Thram- poulidis, C. Safe linear thompson sampling with side information. IEEE Transactions Signal Processing, pp. 3755-3767, 2021.
Gillen, S., Jung, C., Kearns, M. J., and Roth, A. Online learning with unknown fairness metric. In Advances in Neural Information Processing Systems 31: Annual Con- ference on Neural Information Processing Systems 2018, NewrlPS 2018, 3-8 December 2018, Montréal, Canada, pp. 200226201444 2614, 2018.
Neely, M. J. and Yu, H. Online convex optimization with lime-varying constraints, 2017.
Pacchiano, A., Ghavamzadeh, M., Bartlett, P. L., and Jiang, H. Stochastic bandits with linear constraints. In The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, pp. 2827-2835. PMLR, 2021.
Hutchinson, S. and Alizadeh, M. Safe online convex opti- mization with first-order feedback. In American Control Conference, pp. 1-7. IEEE, 2024a.
Pacchiano, A., Ghavamzadeh, M., and Bartlett, P. Contex- tual bandits with stage-wise constraints, 2024.
Hutchinson, S. and Alizadeh, M. Safe online convex op- timization with multi-point feedback. In Learning for Dynamics and Control Conference, pp. 168-180. PMLR, 2024b.
Rakhlin, A. and Sridharan, K. Online non-parametric regres- sion. Proceedings of The 27th Conference on Learning Theory, pp. 1232-1264. PMLR, 2014.
Hutchinson, S., Turan, B., and Alizadeh, M. Directional optimism for safe linear bandits. In International Confer- ence on Artificial Intelligence and Statistics, pp. 658-666. PMLR, 2024.
Rakhlin, A., Sridharan, K., and Tewari, A. Online learning: Random averages, combinatorial parameters, and learn- ability. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2010.
Hutchinson, S., Chen, T., and Alizadeh, M. Optimistic safety for online convex optimization with unknown lin- ear constraints. In International Conference on Artificial Intelligence and Statistics, 2025.
Russo, D. and Roy, B. V. Eluder dimension and the sample complexity of optimistic exploration. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pp. 2256-2264, 2013.
Jenatton, R., Huang, J., and Archambeau, C. Adaptive al- gorithms for online convex optimization with long-term constraints. In Proceedings the 33nd International Con- ference on Machine Learning, pp. 402 411. JMLR.org. 2016.
Sekhari, A., Sridharan, K., Sun, W., and Wu, R. Contextual bandits and imitation learning via preference-based active queries, 2023a.
Sekhari, A., Sridharan, K., Sun, W., and Wu, R. Selective sampling and imitation learning via online regression. In Thirly-seventh Conference Neural Information Pro- cessing Systems, 2023b.
Kakade, S. M., Kalai, A., Kanade, V., and Shamir, O. Ef- ficient learning of generalized linear and single index models with isotonic regression. In Neural Information Processing Systems 20/ /, pp. 927-935, 2011.
Sun, W., Dey, D., and Kapoor, A. Safety-aware algorithms for adversarial contextual bandit. In Proceedings of the 34th International Conference on Machine Learn- ing. ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pp. 3280 3288. JMLR.org, 2017.
Krishnamurthy, A., Agarwal, A., Huang, T.-K., Daumé, III, H., and Langford, J. Active learning for cost-sensi classification. In International Conference on Machine Learning, pp. 1915-1924. PMLR, 2017.
10

---

Online Learning with Unknown Constraints
Usmanova, Krause, A., and Kamgarpour, M. Safe convex learning under uncertain constraints. In The 22nd Interna- tional Conference Artificial Intelligence and Statistics, AISTATS 2019, 16- 18 April 2019, Naha, Okinawa, Japan, pp. 2106-21 14. PMLR, R, 2019.
Vovk, V. Competitive on-line linear regression. In Advances in Neural Information Processing Systems 10, [NIPS Con- ference, Denver, Colorado, USA, 1997]. pp. 364-370. The MIT Press, 1997.
Yi, X., Li, X., Xie, L.,, and Johansson, K. Distributed online convex optimization with time- varying coupled inequality constraints. IEEE Transactions on Signal Processing, pp. 1-1, 2020.
Yu, H. and Neely, M. J. low complexity algorithm with O(vT) regret and O(1) constraint violations for online convex optimization with long term constraints. Journal of Machine Learning Research, 2020.
Zafar, M. B., Valera, GomezzRodriguez, M., and Gum- madi, K. P. Fairness constraints: A flexible approach for fair classification. Journal of Machine Learning Research, 2019.

---

Online Learning with Unknown Constraints
A. Proofs from Section 3: Setup
Definition A.1. A function & ||1,1]] + R is X-strongly convex if for all 2, E [-1, 1], it satisfies
2 (z' 2) =) x - ((2) ((z)(= - 22)s
where o(.) is the derivative Q.
The following formulation of link functions standard the literature (Sekhari et al., 2023a)
Definition A.2. For a link function that is the derivative of a A-strongly convex function 2 we define the associated loss:
(z(z,²) = 55 11)
Assumption A.3 (Online Regression Oracle, Regret Version). The algorithm OracleoR guarantees that for any (possibly adversarially chosen) sequence {a,, #1)=1 generates predictions {&e] satisfying:
Σ
inf 2)
Σ 21) S Regor (T.F)
FEF t=1
where b ~ (ar
The following lemma is adapted from (Sekhari et al., 2023a), Lemma and related to (Agarwal, 2013), Lemma
Lemma A.4. Suppose that 2, is generated with a link function & that is X-strongly convex. Suppose that the regression oracle satisfies assumption A.3. Then for any 8 E (0, 1) and T 2 3, with probability at least 8, the regression oracle satisfies assumption 3.1 with:
RegoR (T,6F) x RegoR (T,F) + 16 16-224 24X
log log(T)
X
Proof. The proof is an application of (Sekhari et al., 2023a) Lemma 9. Proposition (Proposition 3.3 restated). There exists an algorithm satisfying Assumption 3.2 with
Regor (T', 8,11) 2 Rad (T)
where Rad (T') is the sequential Rademacher complexity of the loss class, defined as:
Radson zofl (T) == sup E,
sup TEll 1=1
y.x
where in the above supremum over y and x are taken over all mappings of the form y ( + y and UT- (+1)* +> X' respectively.
Proof. We show that expected regret is bounded by 2Raden toll (T) through a minimax analysis with sequential sym- metrization techniques that are now standard from (Rakhlin et al., 2010). We use the notation (Operator,) [A] to denote Operator, {Operator, Operatory[A] }}. Furthermore, we denote the set of safe policies in hindsight as Ih == {Ir E IT: vt, (Tx2 E At). We view our online learning setting as a repeated game between adversary and learner where on each round adversary picks a context and a set A, learner picks a (randomized) action from this set and finally adversary picks yu for that round. The value of this game can we written as:
Valy
sup inf sup Earops 1e p. P.E))AA) wey
Σ
E(as, Iz. yi)
min xell
el ((T( Ite yo)
t=1
T
sup sup inf E d, ((( a.EA,
Eying
Σ
E(a,, Z1.
min HElly
((T(())) Fe. v..
12

---

Online Learning with Unknown Constraints
T
sup
sup
By a
Σ
inf at A.E.
Bygngg [e(ue, Le, [e,
min relly
(x)())) x..
Fude q (E(
t=1
Eyinge an.d (((())
sup sup
max HElly
Σ
E Bycag [C(T((F))) ((T (31e); 2e me0
t=1 T
(L(T(2)), Fr, v/) [(T(())), B0)) }
sup sup
E B/
max Fellr
Ar qu EE)
1=1
sup An E()()))))))))))))))))))))))))))
sup
E v/
Bes
max Elll
(e(=(1x)) 21, 16) (xx( W:))
T
sup
sup Be,
max FEllT
c (((T(2)), v/) - ((T(((((()))) (
An Br. EY
1=1
T
T
c (4(T(2)), o4, v/) - E(T 24, }
sup sup Ar J.Y
Ee,
max well
where first line obtained using repeated application of minimax theorem (which holds with minor assumptions on action sets and context etc. that can be found in (Rakhlin et al., 2010)). Second line is rearrangement. The next line is by noting that each loss-minimizing action a₂ A, has smaller losses than T(;;) A,, The rest of the steps above standard sequential symmetrization arguments. The key step is the last inequality above where we use the fact that IT C IT. But once this is done, the inner terms are devoid of A 's and so we drop them in the supremums and this results in two times the sequential Rademacher complexity of the loss class yielding:
Valr Rad (T)
Since the minmax value Valy is bounded, there exists a regret minimizing algorithm with required bound and this concludes the proof.
B. Proofs from Section 4: Main Results
Proposition (Proposition 4.1 restated). Suppose f G F.F. Then:
P(g,x) S fa (a, s 00] C (g,
Proof. First suppose a such that (a, S 0. Since I E 9, a 0g) Hence, (a E A f'(a, 24) S 0} S xg), Now suppose a E p(), Then, Af E G, f(a, 2.) I 0. Since fr E 9, (a, S 0, and hence (a, f 50
a.), C {a e A:
Theorem (Theorem 4.2 restated). For any 5 (0, 1) there exists an algorithm that with probability at least 35, produces
sequence of actions (ar) that are safe and enjoys the following bound regret:
Regrety < inf 6S00
Σ (i, + k inf faT + 20 RegoR Re,oR(TT, (7)6, oi]
+ Regoi (e,oL(7,6,1) + v (2Tlog(H)
Moreover, there exists problem setting such that if there exists 0 satisfying
lim T-0
Vn > 0,
then, safe learning is impossible, i.e. no algorithm that is safe on every round (with high probability) can ensure that Regret, = oT))
Proof. The first statement follows by applying Theorem 4.3 using the optimal mapping M M (defined in eq. 4). The second statement follows from Theorem 4.4.
13

---

Online Learning with Unknown Constraints
B.1. Proofs of Upper Bounds Lemma B.I. With probability least 8, for all [T], f F
Proof. This follows immediately from Assumption 3.1 which guarantees with probability at least
T
Σ v.) -2,2 S Fo,
==1
and hence for any t E [T],
Σ x.) "5{²= < RegoR (T,8 $=1
which shows f E Ft.
Proposition B.2. Let (FitT=1 be the sequence of version spaces generated by Algorithm 1. For any 8 E (0, 1) with
probability at least (1 8) we have for any t [T]
P(F(, S A 5 ((),)))))))
Proof. By Lemma B.1, have with probability least 5 that f* Fr simultancously for all [T]. Applying Proposition 4.1 immediately yields the result.
The following lemma bounds the number of times the width of the Fi can exceed some threshold, and variant of Proposition 3 of (Russo& & Roy, 2013). It is slightly different F; are constructed around the predictions produced by OracleoR. We state it for completeness.
Lemma B.3. Let the sequence {Fr, Oe, 20) be generated by Algorithm Then, for any sequence of adversarial contexts TT and e 0, it holds that
ARegon FoF) + E(Fo,e)
Σ #1) >
Proof. First we claim that for & [T] Ar, (a) 2 e, then (a,, xz) must be c-dependent on at most 1Regon (T,5,Fo) dis- joint subsequences of (a1, 21) (0 1). Since AF, (ar, xx) > e, there must exist functions f E F. satisfying ((a,,2)) f' (a,, 21) of its predecessors, we must have (f Ri,) - l'(a,, T4y ) > e². Therefore, if (a,, is e-dependent on N such subsequences it follows that Σ (f(o,,z) - f(a),
By the definition of d-dependence, if (at, 2t) is e-dependent
sequence (a., 2i, .... (a.,, T.,)
> N Therefore:
+1 (f(a), - -f
Ne² <
Σ (((a, - -2, 1 (aaj,,
1-1
2 2 2 2,) 2,)2 + Σ - -2,)
==1
< 4RogoR FT)
where the second inequality follows from (a + 6)2 < 2a + 26 and the third follows from f.f' E Fc.
14

---

Online Learning with Unknown Constraints
Second, we claim that for any 1: E [7] and any sequence (d1,#1) .... (dt, FR), there must be a j S & such that 2g is e-dependent at least N [ c) 1] disjoint subsequences of its predecessors. We will show iterative process of finding such an index j. Let S1 ... Sx be N subsequences initialized as S; [()) for i e [M]. For j E [N + 1, k] first check if (aj, 2n) is e-dependent of all S, i [N]. If is, we have found the index j satisfying our condition. Otherwise, pick a Sy such that 2y is e-independent of 5,. and add 2 to that S. By the definition of eluder dimension, the maximum size of each S,, E [M] is EFoo e), and because N * (Foo, c) I k - 1, the process will terminate.
Now, let (at,; (i, .... (aig: )i2)) be the subsequence such that for E [k], (a,, > e. By the first claim, each element of this subsequence is e-dependent at most (T disjoint subsequences. By the second claim, there is some element that is e-dependent on at least [(k- 1)/E(Fo, s) disjoint subsequences. It follows that [(//E(Fo, e) 1] S
4ReeoR (T.8.Fo)
and hence k << 4ReRoR (T.6.Fo) 1) (FF.
The following Lemma utilizes Lemma B.3 to upper bound the sum AF, It is similar in spirit to Lemma 2 of (Russo Roy, 2013), but our analysis is different and captures a trade-off between T and Regon (T, 6, (F).
Lemma B.4. Let the sequence (Fr,Pe]T=1 be generated by Algorithm 1. Then, for any sequence of adversarial contexts {zr)i=z
Σ E (A S inf { aT 20Regon ( aempe
Proof. For run of Algorithm let {at))== be any sequence of actions drawn d, ps for all / [T]. Furthermore, to simplify the notation, let us denote A, == Ar, (ar, xt). Let us consider some arbitrary >> O. Then, for this sequence of actions and contexts,
Σ 1=1
=
Σ
A
1=1
1og(2/a)-1
Σ
A +
Σ
Σ
A
:d.Sa
1=0
1.2"a<2,22-10
1og(2/a)-1
< ST +
2 a
1=0
1. 52it1a
log (2g(2/))-1
(1)
S aT
+
Σ
2i+1 a
[ReeoR
+ + 8(Fo,
2
log(2/a)-1
(16)
aT +
Σ
2
5ReBoR (T, (T,
E(Fo,
22
1og(2/a)-1
10RegoR (T,
SaT
+
E(Fo,
2'a
(iv) S aT + E(F a
10RogoR (0R Fo)
2'a
1=0
(0)
S aT 20RggoR (T, 5, Fu)
E aF
In (i) we set the upper bound to the sum as log(2/a) - 1 since all functions f E F map to [-1, hence A, S 2 so it is enough to consider i 2 xr < 2 and (ii) follows from Lemma B.3, (iii) follows from the fact that 1 < Regon [e for
(2 a3
i (log(2/a) 1] if T > 1, (iv) follows from the fact that EFF,,) .) is nonincreasing in its second argument, and (v) an
15

---

Online Learning with Unknown Constraints
upper bound from the sum of infinite series. Therefore, for any sequence (Fi: (1, relf=1 generated by Algorithm I we have
Σ Fr, (ac, S aT 20RegoR (T, Fo) {(Fo.a)
Now, since this holds for any sequence (Ft, 0t )= generated by the algorithm and adversarial contexts (1t) holds in expectation over the algorithm's 's draws.
Theorem (Theorem 4.2 restated). For any (0, with probability at least 38, Algorithm when using mapping M produces sequence of actions {ar]== that are safe and enjoys the following bound on regret:
}
Regrety S inf #30
Σ M Fi. 21) + ininf (aT + 20 a (1,,o((,
+ RegoR (T, + / /2r log(())
where,
y x (pri (e, suu sup yEy (iiFF
[((a,, [1,9]]
A (ar,
āc-
Banmier (, Fan Fampl((am..)))
Furthermore, using n² = = sup SUPACF.EEX,EEIIO w)) Bannappf (a
Regrety S n¹ inf oT 20RegoR (O)
Re, + T log((=11)
Proof. By Proposition B.2, with probability least 1 - 8, if we play actions from Pt, we can guarantee the all the constraints satisfied. On the other hand, to bound the regret of our algorithm w.r.t. the optimal action in hindsight that also satisfies constraint every round, note that
Regrety
Elar, Tt, Me)
min nellivt
Σ
(TT())), I4,
f (1)
M(ar, Te,
min xEll-v xxx)EE0
Σ
E(a, xe, (t)
((a,,
E
[e(ās, Vi)) + Σ
E [e(ā,, Te, ve)l apmpe
min f(a, *ellivt m(z))00
Tympe
(laa, Fe,
E
[e(ā,, V:)l) + Regor (T,8,II)
(1)
T
Σ
E [((0,, 21.21)) aerppt
+ Regor (T, II) + (Tloo(--1)
aempe
< inf K2H
VM (prs Fr, +
Σ
| (ar, (at) aprupt
E
Regoi (T, II) + / Tlog(0-1)
where (i) follows from the fact that by Proposition B.2, a policy v satisfying VI, l (TTE) ( 0 satisfies Vl, T(x))) O.. (ii) is an application of Hoeffding Azuma to bound ΣT Elar, Ht, v.) Σim Earn. [f(as, Te, vr)] and:
x (MG (ze; Fe) = sup
[(( [((ar, vt, [ yEy (FF
E aeoup
[((r,, M2, 1. - (.
E
A (a),
16

---

Online Learning with Unknown Constraints
by Lemma B.4 can bound the Σ Buinpi A (ar, 2T)] term, hence,
T
M Fi, + xinf aT (OR 0
Regrety S inf 620
Regor (T, IT) + V (Tog(68-1)
This concludes the first bound which holds with probability at least 1 - 30 as we take a union bound over the online regression oracle guarantce, the online learning oracle guarantce, and the application of Hoeffding Azuma. To conclude the second part of the statement, we need to show that for
E aamM(p:P.a) .2) [e(a, v, v) Eaup [e(a, 2, v)l
n²' = (F, M)
sup FE wEY
E (aM A
we have that V (pr; F1, x2) < 0. To this end, note that
DM (p:; F(, x1)
sup vey
E (a
(((a,,)+.)))
E Gerupe
[e(āe, Rez w|l
x²*
E a)-M((
A (4),
= sup yEy
E (a
[l(āe, Fe, 22.1 8/1
āc-ii B BaM((BFa)
- sup ACF PEF
(E(a, 2r, w)]
Banp [((ā,,,))]
E aoM((FFFF..)))
An xa),
E Ba-MBtt
A x]]
sup yey
E (a
[e(ar,).:))]
E [((ār, am-R
supuey MGG
Barmi, (((ee
E Ar (at, #t)]
Bag Ar, (+)
0
B.2. Proofs of Lower Bounds
We formalize the notion of pa 3 Ao with the properties described in subsection 4.3 with the following lemma, and show its existence.
Lemma B.5. Assume that we have fixed loss function E : TR such that for any a E satisfying f*(a) > O. ((a) min E.nff (a::-(a-)50 E(a"). Furthermore, assume that the eluder dimension of at any scale (with input space A) is bounded. for some c* 0, K 2 O, any regret minimizing oracles Oracleol and OracleoR (assuming regret in both cases is o(T)) lim $ ΣT (e,, F.) 2 e" then, there exists a set P 2 Ao with the following properties,
1. Set pa satisfies constraints, i.e. Va E P", 50
2. Define F (f Va E P", ff For every action E AAPP. 3f E F" such that f(a) O. That is, P cannot be expanded larger set guaranteed to satisfy constraint.
3. Pa is such that in ((a) infoeA: E(a) 2
Proof. First, since loss is fixed and using the property of the loss assumed, any online learning oracle that minimizes regret would have to return distributions over actions p. such that limr $ Σ'= Barn, [((ā))] = infaEA ((a). We have from the premise that Tim 1 Σt Vi (p,, Fi) 2 e" and by the definition of Vie()) = inf DM (.), every mapping M satisfies
17

---

Online Learning with Unknown Constraints
1e +E (Mr;FFF c" Hence this means that for any mapping giving us distributions pt, have that
T Σ a
lim T
E
[((at)]
inf (E):
f(a) 2 c*
T
since Bawpi AAx (at)] 2 0. Further, note that since the loss is fixed, if at some point we are able to find distribution Pt such that Berrp, [e(at]] - inf {(a) < c* then by returning this distribution we would violate the premise
that 10m T 1= V. (ft, Ft) 2 c² Hence have that for any mapping, and any (..-M(......) [e(a:)]
(a) {{a) 2 c². Since this holds for all mappings, let consider the following mapping
if min E(a) in) ((a) + (argmax A,, (a)) otherwise
(rrgmin ((a))
M(d: =
where 8(-) is the point mass distribution. In the above we assume the argmin and argmax exists otherwise we can do limiting argument. The above mapping is valid one since loss is fixed and given. Now note that since already showed that any valid mapping satisfies P.P.... [?(ar)] inf (0))500/ {(a) 2 e* we can conclude min f(a) 2 (ayo ((a) + c", Now define the set
P = UP P 121
Since Pi's are all guaranteed to be safe, have that P is also safe, satisfying property 1. Second, since for every t, minger, f(a) 2 inf inf {(a) + c* we have that inf {(a) - inf ( {(a) 2 c². Thus, p satisfies property 3 as well. Finally, to prove property 2, we use the assumption that eluder dimension for any scale e is finite and that the regression oracle ensures that regret is sub-linear. Specifically, assume that online regression oracle guarantees an anytime regret guarantee of (t) with probability 1 - for any rounds. In this case, using Lemma B.3 we have that with probability least 1 5, for all T 2 1 and all e 0,
T Σ
(T 2
(0))
> c
+1 E(F,C)
for a,'s produced by the above mapping. However, since we are picking at that maximize AF, (as) on every round and because the Pt 's are nested, the indicators in descending order. Hence, with probability at least ō, for any (0, let T. be the smallest integer such that
T. Øs (T.)
5E(F,c) 2²
This is where the condition that regret bound (T.).) is o(T.) is needed so that the above yields valid lower bound on Te. We have that for any for every action a E Pt. Fi+z, is such that sup If(a) [*(a]] < The reason take Fetr, is because / is the first round in which actions in P. not in earlier sets come into consideration and so we need T, more rounds to ensure that for all actions in this set, estimation error is smaller than e. Thus if we consider the set N1ZI F, this set corresponds to the set F = {f : Va E P f(a) = (a)). Further, by definition of Pt's 's we have that if there were some action a such that ff E F faa < O, then this action would be contained in P Thus we conclude that every action not in pa is such that it evaluates to a positive number for some function f E F Thus we have shown property 2 as well.
Once we have the existence of Pa Ao with the properties described in subsection 4.3 we show that learning is impossible. Proposition B.6. If there exists a set Pa that has the following properties,
1. Set Pa satisfies constraints, i.e. Va E P", (a) 5
P"; f(a) = (a)). For every action a E E P", E E such that f(a) That is, P 2. Define F {f Va P*,
cannot be expanded to larger set guaranteed to satisfy constraint.
3. Pa is such that inf. f(a) - infaeAr 2
18

---

Online Learning with Unknown Constraints
Then, safe learning is impossible, and any learning algorithm that is guaranteed to satisfy constraints every round (with high probability) has a regret lower bounded by Regrett 2 Tc*
are guaranteed that Pa is safe any safe algorithm must play actions that it can guarantee safe with high probability, initially any algorithm initialized with p has to play from within this set till it can verify some action outside of this set is safe. However by property 3, any action within p at least c* suboptimal. Any feedback we obtain in the process of playing actions Og E P would certainly help us evaluate (())) more accurately. However, property 2 implies that even if we were given the values of f* for every action in the set p* we still would not be able to find another action outside of this set that we can conclude safe unless we make further assumptions on f*. This is because, each probe/feedback by playing action a yields value of ('())) + Σt. Since the noise is standard normal variable, at best might he able learn only (a) for every However, even if we had this information, the best we could conclude is that f is one of the functions in F However, property 2 ensures that for every E A A P*, there is function in E F that matches the value of I* in P but has f(a) > O. Since we have no information about which f E F is the true f", no learning algorithm will be able to safely try any action outside of pa and so any safe learning algorithm will suffer a sub-optimality at least c* on every round and thus Regret, 2 Te*
Proof. By property
can start any algorithm with initial safe set Ao P Since
P*.
every action
Theorem (Theorem 4.4 Restated). Suppose we are given some Ao, x= (). (I f" E and losses l: (:A+) are fixed such that for any a E satisfying (*(a) > 0, E(a) = mitla (A:f(((a)) E(a*). Furthermore suppose Ve, EFF finite. Then, if there exists x > such that
lim Σ Vel T-x T
then, safe learning is impossible, i.e. no algorithm that is safe every round (with high probability) can ensure that Regrety = o(T).
Proof. Combining Lemma B.5 and Proposition B.6 trivially yields the statement of the theorem.
B.3. Proofs of Per-Timester Constraints vs Long Term Constraints
Lemma (Lemma 4.5 restated). For any å (0, 1), there exists an algorithm that with probability at least 1 26 produces sequence of actions {ar)7 that satisfies:
T (or, S inf { of (o.
Regrety I Regor. (T,8, 6, and Σ
We provide a modified version of Algorithm 1, stated in Algorithm 2, where we do not maintain an pessimistic set, and directly play the output of the OracleoL. We claim that Algorithm satisfies the guarantee from Lemma 4.5.
Algorithm 2 Online Learning with Long Term Constraints
1: Input: OracleoL, OracleoR: Ao(:), e 10,
2: Initialize Fo (ʃ E F Vx E X, Va E Ao(a), (a, 50
3: for pr 1.... ,T' do
4: Receive context I2
5: F. = [ʃ Fo (1 2,)² < RegoR (T, 6, Fo)
6: O = ((F, // Optimistic set; cf. eq (2)
7: = OracleoLe(T; O,)
8: Draw a, ~ Pt
9: Receivenoisy feedback 2t
Update
OracleoR: (a:, (T, 2x)
11: Play de and receive y/:
12: end for
19

---

Online Learning with Unknown Constraints
Proof. By Lemma B.1, we know that with probability least for every T simultaneously. f" E Fc. Now for a given timestep i [T] consider the action played by the algorithm dz. Because ot was generated by OracleoL, dt Oz. For this action, let ft := Jegmingeet, ((a,,zz) Then
fi(a,, 21) 50 filar, 24) felay, + f (a,, 21) S Ar, (0)
f (a,, s Ar, (ot, D1)
Summing up all terms, we get
T Σ Ar, xt) 1=1
(a, x1) S
Now, using Lemma B.4 with each defined as point distributions putting all its mass on de, we can further bound the above as:
Er inf oT + 20Rcgon (T, 8, (o)((.))
a
Finally, since we are just playing the output of our oracle Oracleol, the regret bound is simply
T Elar Re, Mt)
T
Regrety =
min mellivt
Σ
(T(()), v1)
(slo))),.)s0 t=1
lla,, Tes Ie,
min selliv =xx))E0
Σ lla,z We)
1=1
< RegoL (T,
where the second inequality follows from the fact that by Proposition B.2, a policy и satisfying Vt, (T((),, S satisfies Vt, 7 (2+) E Oz. The theorem statement holds with probability least 1 28 as we apply union bound over the online regression oracle guarantee and the online learning oracle guarantee
C. Proofs from Section 5: Examples
C.1. Proofs for Finite Action Spaces
Procedure for selecting adaptive Kę Let us define x² x *FFFFAS MFAS) (defined in Theorem 4.3 statement). '² need to be known but we will show we can attain similar as or potentially much better results than k* nonetheless. For timestep t, given context F, and Fe, Pt. generated by the algorithm, let Ve(x) be the value of the soddle-point optimization in eq which monotonically decreasing in K. Observe that since inf, aT 20Rego (T.6..))
vT, K. ranges from
a
(0, vT] in order for the regret bounds to be o(T). Therefore, starting with K2 = VT, repeatedly halve He while Ve(Rg) < 0. Set K2 to be the last K2 satisfying Vy(n,) < O, and play P: as the minimizer of (Kz)). By definition, x* satisfies V((x*) < and therefore at worst K2 < 2x* while simultaneously K; may be be much smaller as we are adapting to 24, Fr, Pt, Pt- Consequently, our final regret bound would depend max, Kr S 2k.. Thus we can easily obtain the result competing with *** corresponding the best mapping. As a further note, some appropriate to get more general rates. Lemma (Lemma 5.2 restated). Suppose Assumption 5.1 holds. Then, x² (TFFAS MEAS) <
relax the condition Vi(Ne) < 0 by V((Ne) < T for
A
Proof. First suppose Pt # O₂. Then we have FAS (p; = (.A(T.)) Let F be the maximizer of K* (FFAS FAS)). Then:
CO.MPAS o)) [((a, x. v)] - Eanp [l(ā x, v)]
(FFFAS =FAS)=
sup TEX. :))
E Be F- (a, x)]
20

---

Online Learning with Unknown Constraints
((A - p) ==X. Ay- (F+ ,),
sup =EX
(0 11
Ao
MEX.
2
Ap
where the first inequality follows from the fact that given a context æ, a (F* ,2) maximizes AF (,, and hence by
Assumption 5.1 D (a (F*, 2.) x) Åo-
Now if P. Os, MEAS (p,, Pt, Fi) Pt- Clearly, by definition, x*(FRAS MMAA) 0.
C.2. Proofs for Linear Constraints
Lemma (Lemma 5.6 restated). Suppose Assumption 5.4 holds. Then, K² (Fliin MM 1 DrDa.
We first introduce a lemma that lower bounds "(ā;; F).
Lemma C.1. Let F be arbitrary subset of Flin and consider some à E O(F). y(a;)) max (7 [0, 1] rā E P(F)} is lower bounded as:
b
(ā; F) 2 b (a
Proof. Recall that FF C Flin := {(a,2) + (f.a) blf E Rd Define f argmin JeF f(ā), and let 7 be some arbitrary
function in F. From the definition of à O(F), we have f(ā) S 0. Then:
[(ā) 0
[(ā) bbbb
[(a)+ - [(]) +b5+++rb000
+b)+
where the third inequality follows from the definition of Ay()). Let = [āj Notice that 7(a) + is linear function (w. a} for some e RRd. follows that a(f(ā) + = a a = aā) = f(aā) + Using this fact,
f(ā) (ba)+bbb+Ab a (F()) +b) b) s a(b A)(
7(aā) b
Maa)) <
Since ʃ was arbitrary function in F. this shows that aă E P(F). Since we defined r(ā;F) max {7 E [0, 1] pā e P(F)}
[(; 2 b (
We now prove Lemma 5.6.
21

---

Online Learning with Unknown Constraints
Proof. Let F* be the maximizer of n² (F MLia). Using the definition of x*,
Ba-Miin Mui [e(a, v, v\1 - Banp (( x, x,11]
n² (Ftii MLin)
sup BEX D.Y
Ba-MiiBB A (a,
{(MLina;; F)),) ((ū,1)
sup aEO(F))e)
Dr. (M (0: F*))
((((ā; F )ā. y) - f(ā, v)
sup aeO(T)),e)) J.v
Dr- (7;;
Fel all A (T
sup aEO(F)),E)
DeDa ((;
sup aEO(F)),vE)
Now Lemma C.I implies
1 -a;
1 (1
b
b AF (ā)
(F- )
b+ (a)
A (ā)
Fa)
b+ A (a)
+ (a)
and hence
D.Da
15 (FLiin Mlin) <
C.2.1. PROOF OF LEMMA 5.7
We present constructive online learning oracle Oracleol for the case of linear cost functions. Recall that Oracleou must satisfy Assumption 3.2 restated below:
Assumption (Online Learning Oracle). For any sequence of adversarially chosen sets {At)T= and any (0, 1) with probability least 6, the algorithm Oracleol produces sequence of distributions {p.) satisfying p. Q2(,,) for all & E [T' with expected regret bounded as:
Σ
E a
[l(ar, Fz, ye)l
min
Σ ((, < Regor. (T, II)
aent
Algorithm 3 is stated below, and it is a projected online gradient descent based algorithm. Let the losses encountered at timesteps t E [T' be denoted by E(ar, : 31) = (le, az).
Algorithm 3 OracleoL for Linear Losses
1: Input: A, Da, Dr, E (0, 1),7)
2: for timesteps = 1, ... _T do
3: Receive A: = O,
4: āg + [A)o (āt-1 1161-1)
5: Decompose āz = Ed+t ae,s Vi, 0z, E A
6: Sample ā Pt:
7: Receive V. = Ee
8: end for
We briefly describe the the steps in Algorithm Convex Hulls of A, (line 4)
22

---

Online Learning with Unknown Constraints
Because the action sets A, - O₂ are sublevel sets of a minimum of affine functions, they not necessarily convex, making them incompatible with projection based online learning algorithms. In order address this, we take the convex hull of A,, Con)(A.), our projection set.
Projected Online Gradient Descent (line 4)
Our algorithm then performs projected online gradient descent sets Conv(At), generating a sequence of vectors f..... 1......y. arr produced by ag = [A) (āc-1 - r/(,-)). We note that while we use projected online gradient descent, because the vectors {ār ... är) are maintained and updated independently, we could alternatively use a projected variant of any other online convex optimization algorithm that guarantees low regret instead.
Sampling Point in A, (line 5)
Due to Carathéodory's theorem, we know that can write any 0e Conv(A.) as linear combination of at most d + 1 vectors in A4, 0 Ei=1 Pr,; Vi, 0t,1 E A,, In line 4, we perform this decomposition, and in line 5, we sample the vector ā according to this distribution pr. Notably, the point âr satisfies Blā, az.
Lemma (Lemma 5.7 restated). Suppose Assumption 5.4 holds. Then Algorithm satisfies Assumption 3.2 with:
RegoL(T, (T,
Proof. At every timestep E [2], Algorithm receives a A, Oz, and produces â by:
ā f- (oCo((AA) (āt-1 - 1
then, it decomposes each az as:
d+1
0r = Σ Vi, E Ae
and then a, is produced by sampling: ā, Pc. We analyze the regret of Algorithm 3 by decomposing it into two terms:
Regor (T,
Σ (1, min oent= Ar
a),,
T
(le ōz) - (le, ae) +
Ele,
min (c, ae ài
Term
Term
Bounding Term We show that Term is difference between bounded random variable and its expectation, and use Hoeffding's inequality to bound it. Let Sy = -'= (le, āz). Then:
E[Sr] = E lla az)l = Σ (4, E(a.)) = Σ (le,
1=1
where the second equality follows by linearity of expectation. Note that each summand in ST satisfies [(e, ax)l < ||]]||@@||| D.Da. Hence, by Hoeffding's inequality, with probability least 1 - 5,
T
Term I = E (e),āa) - (ce, ar) ST E S D3
(6)
1=1
Bounding Term II
Term II captures the performance of the online gradient descent portion, line 4, of Algorithm 3. A difference is that the projection set is time-varying- yet this does not pose problem for us since we only need to guarantee performance w.r.t. a a" in the intersection of all the sets. Let a" == argmin (fe, a). with this,
T Term II = ((, min (le,a) E - a²)
t=1 a ae
tml
23

---

Online Learning with Unknown Constraints
Therefore, it is sufficient to bound the terms (c,, dz a²). For any timestep 4, we have:
|ā - -a'll = ||l (a: m/1)) a²1l
S |0g 1/6 a" a²l1²
0 a 112 + +1² 1lel12 2n (le, a. -a)
where the inequality follows from the fact that a" E ni= - A., so projection Ar only decreases the distance. Rearranging,
1 (lā+ - a'112- - |a++t a²(1²) + 7
(le, de -a) 5 21j
2
Summing up the terms t E (T). we get:
T
T
(4, ūg a²) -
1
Σ
|1āe
a²12 | - -1ā--11-a111 + 2 t=1
||all1
2n
t=1
t=1
(1|ā1 - a a²112 112 ||āT+1 - a²12) + 7 TDD
2n
2
4D2
7 TD
2n
2
2D, Setting 17 D we get
Term II
Σ (6,0a-aa) a²) S2D.D.T
Combining the bounds from equations 6 and 7, we get
min an Σ a.)
(l,,a) = Term I Term $ 44D.De/TToo(2//)
C.3. Proofs for Composing an Activation Function
Lemma (Lemma 5.10 restated). Let G be a function class with bounded '² Mg) for some mapping Mg. Suppose assumption 5.4 holds. Then K² (9),, (g)) < <'(G,M,)
Proof. For any set C (g) let 9F be the set for which F = (9F).. Since (0) = 0 and o is non decreasing, for any x X' we have P(F,x) = P(G,,z) and O(F = 0(G x). Given context x E X, notice that Mg is mapping from distributions over optimistic sets to pessimistic sets. It follows that Mg is valid mapping satisfying (,(;9r, Mg(;F, 2). Let F* be the maximizer of n² (o((),, Mg). Using the definition of k*,
E Baw .x) [K(a, y)] EanD [l(ā x, v)
H² (o()))
sup DENIOE wEY
E Ea-Me .x) A (a,x))
f(ā, x.
sup TEX .tyyyy
Ay. (0; F*)x)))
(Ma x). N. y) - E(ā,@ (ū, u)
sup
As- (Mg (a; Fr,r))
aEX w.
A g- (Mo(a: GFr x)) e(Mg Grs x), v. 2.)) Agy. (Mg 9x-
sup
AF. (Mg (ā; ;x)))
24

---

Online Learning with Unknown Constraints
Ag,. (Mç( 2)) S n² (g,
A (Mg(@: @; 2))
Now, for any a E A, &' and F g == argmax gEGz g(a, x) and g == argmin g(a, x)
(gx
g(a, x)) g(a,
As(a)
x)) zl)(
Fa, g(a.z)
g()(a.z) 2) - =(a,x))
where the second inequality follows from o(0) and for any [-1,1], (1)) is bounded below by g. Therefore
1² (o((), v (G(
C.4. Proofs for Valued Constraints
Recall that given context E X, action E is considered safe if [I, x) 0 for unknown vector-valued function E F S A x X - [-1, Notably, Proposition 3.2 continues hold guaranteeing the existence of an oracle OracleoL- We recall that for a vector-valued function class F S A X [-1, 1]m denote (a, sups,f'e Ilf (a o)), where 11o0 is the loo norm. We define the following vector valued analogues of optimistic and pessimistic sets:
O(9,2) =
= fa 3E E ( 50}
P(G.z) = (a E A Vf E 9, (If S 0}
Algorithm 4 General Online Learning with Vector- Valued Constraints
1: Input: Oracleou. OracleoR. Initial safe set Ao, 8 E (0,1) [i] E F; Va E Ao, Vx E X. [f x)|| 5
2: Fi = { r) + f(a, x
3: Fu = Fo x FM" Fm
4: for 1= 1= do
5: Receive context I2
6: F, E Fo ( a)) // opttimitiic/Pessiiittii;;; cf. eq (8)
2. < RegoR (T))
7: O (()
8: Pt = OracleoLe O₂)
9: = FF,
10: Draw a; ~ Pt
Receive noisy feedback 2t
Update = OracleoR (a:, Ft, 21)
Play de and receive y/:
14: end for
The following assumption is variant of Assumption 3.1 that applies to multiple constraints.
Assumption C.2 (Online Regression Oracle with Vector Valued Constraints). The algorithm OracleoR guarantees that for any (possibly adversarially chosen) sequence 2T for any (0, 1), with probability at least - 6, generates predictions 1T with each & E 1_,, satisfying:
T
Σ
2 fla,, 1il1. < RegoR (T,5F)
The following formulation of link functions standard in the literature (Sekhari al., 2023b).
25

---

Online Learning with Unknown Constraints
Definition C.3. A function Φ [11,, 1| R is A-strongly convex if for all v E 1-,1, it satisfies
|| - S - (o()),
where (b.) (.)())
Definition C.4. For a link function o(-) = (.) for a A-strongly convex function b, we define the associated loss:
() (vv) v[=]
Assumption C.5 (Online Regression Oracle with Vector Valued Constraints, Regret Version). The algorithm OracleoR
guarantees that for any (possibly adversarially chosen) sequence {a,, 2,),2 generates predictions {&, ) satisfying:
T
T
lol2,, 21) inf Σ 2)) fEF
RegōR (T,F)
where 2t ~ p(f(ar,
The following lemma is adapted from (Sekhari al., 2023b), Lemma and related (Agarwal, 2013), Lemma
Lemma C.6. Suppose that 2t generated with a link function & that is the gradient of a X-strongly convex function. Suppose that the regression oracle satisfies assumption C.S. Then for any å (0, 1) and T 2 3, with probability at least
1 - 6, the regression oracle satisfies assumption C.2 with:
112 ReBoR (T, F) S X Regon (T,F) + X²
log (15- log(T))
Proof. The proof is an application of (Sckhari et al., 2023b) Lemma 5.
Lemma C.7 (Variant of Lemma B.I for Vector Valued Constraints). With probability at least 6, for all t fT, F
Proof. First, notice that as f is safe for all actions in Ao. f E Fo. Assumption C.2 guarantees with probability at least 1 - 8.
(.) < RegoR(T, Fo,
and hence for any E [T],
Is) 2oll3 < RegoR (T,8,Fo)
which shows j Fi.
Proposition C.8 (Variant of Proposition B.2 for Vector Valued Constraints). Let (Fi)t= be the sequence of version spaces generated by Algorithm 4. For any 8 (0,1) 1) with probability at least (1 5) we have for any t E (T)
P(Ft, S fa E A: xi)ll I 0} S O(F,
Proof. By Lemma C.7, have with probability least 1 that f F, simultaneously for all E [T]. Take some arbitrary
I E [T]. First suppose such that (l a,)loo I 0. Since f E Fe, a E O(Fe, x). Hence, {a A (I, ax)) S 0) S ((F, Now suppose a E P(F, x.). Then, vʃ E Fo, [lf(a,,)))ll S 0. Since E F., (I 2x)ll & 0, and hence
P(F(, S (a E A: ( (0, m4) 1x 5)
Lemma C.9 (Variant of Lemma B.3 for Vector Valued Constraints). Let the sequence {Fi, ur, &n &T be generated by Algorithm 4. Then, for any sequence of adversarial contexts {xt]T= and e > 0, it holds that
T
4Regon (T, +1)
Σ
( 21) > 5
Σ E(F.))) ic(m)
2
t=1
26

---

Online Learning with Unknown Constraints
Proof. For all i E [m], let = 15 Fo
E0 - 21)² < RReooR (,, We appeal directly Lemma
B.3.
T
T
1 |{ (at;
(at; v4) > =
Σ1
1
max A (ae, (et, > c Iem
A 5/ (a,, 12) 22)
[m] t=1
4RegoR (T, Fo..Fo)
+1) E(F)..)
i [m]
t=1
T
ARegoR (T,
+1)
Σ {(F
6
tml
ic(m]
where the third line follows from Lemma B.3.
The following lemma is similar to Lemma B.4 we state it for completeness. Lemma C.10 (Variant of Lemma B.4 for Vector Valued Constraints). Let the sequence (Fe.Pelem generated by Algorithm 4. Then, for any sequence of adversarial contexts {x1]
A (a,, x+)] S inf { aT 20Regon (T, Fo) a(F)
E ae
a
Proof. For a run of Algorithm 1, let {at)T=1 be any sequence of actions drawn 04 Pt for all / E (T]. Furthermore, to simplify the notation, let us denote A, == Ar, (at, Ft). Let us consider some arbitrary a > 0. Then, for this sequence of actions and contexts,
Dr. (ar x1)
Σe A
1og(2/a)-1
A
Σ
D
(:2'54A522+1a
1og(2/a)-1
Σ
2it1
log(2/a)-1
Σ ((1)) ))
(1)
I oT
+
Σ
2i+l
4RReoR (T, (T,5
+1)
22
1=0
jElmJ
(10)
log(2/a)
5RegoR (T, Fo)
E(Fi, 2(Fi) ))
aT +
Σ
2 a
22
1=0
JE(m)
log 1og(2/a)-1
(10RggoR (T,5,Fo)
<aT +
Σ
8(F), 2'a)
Vaa
1=0
JE|m]
(cv)
10Regon 8,
S a
Σ
E(H),))
2aa
jc(m)
1=0
(0)
20RegoR (T, O, Fo) Eme(m) E(F), a)
27

---

Online Learning with Unknown Constraints
In (i) we set the upper bound the sum as (2g(2/o) since all functions f E map to [-1,1],
1), hence A, so is
enough to consider i 2 a S 2 and (ii) follows from Lemma B.3, (iii) follows from the fact that 1 < MoRoR(T,5.2 for i E [2/g(2/a)
(2
if 1, (iv) follows from the fact that (FF,)) is nonincreasing in its second argument, and (v) an upper bound from the sum of infinite series. Therefore, for any sequence {Fi, at, 24 = generated by Algorithm I we have
T
20RegoR (7,6, Eje(m ((F),))
(a,, It)aT +
Now, since this holds for any sequence {F,, at 41 generated by the algorithm and adversarial contexts (xx))=1- it holds in expectation over the algorithm's 's draws.
The following is an analogue of Theorem 4.2 for multiple constraints.
Corollary C.11. For any 5 (0, 1) with probability at least 1 35, Algorithm 4 produces sequence of actions foz ( that are safe, and enjoys the following bound on regret:
(Fr; 24) winf aT 20RegoR (7,6,Fo) Eielmi E(Fo: a) !
Regret, S inf #30
Σ
a
+ Regol (T) + 1og(11)
where,
V Fe, sup yEY
E (...(())......)))
[lar, Tz,
E
[e(ā,, w|l 1
( (ar:
āp-Dt
E Ea (0 (a,)),)) Bans then the above,
Further, if we use 15* n² (F, M) == WEE.SSEEE.....EIIIE.......... WE)
BunMis A (a..)
VM (pri (e) S and so we can conclude that:
Regrety S x² inf of+ 20ReBoR Eie a(Fó. ReegoL(T,,,1)) + Togo((-
Proof. By Proposition C.8, with probability least 1 - 8, if play actions from P., we can guarantee the all the constraints satisfied. On the other hand, to bound the regret of our algorithm w.r.t. the optimal action in hindsight that also satisfies constraint every round, note that
Regret,
llae, Fz, ve)
min Relliv (0
Σ ( v)
Eaae, Vr.
min rellevt alZ,)E0,
Σ (a,
t=
t=1
(l(a,, De, ve)
E demup
[l(āe, Fz, 24, v1))
E á
(((ā,,
min selliv =(re)CO,
l(a, Zz. Ve)
T
(f(ar, Re, we) )
E apmpi
[l(de, Vz, U1ll + Regor (T, (T)
E (e,e,
E ac-m
(1,,, Vz, + Regor. (T,,, + (loog(-11)
aempp
1m1
28

---

Online Learning with Unknown Constraints
S inf a>0
m (P::FF, xx) +
E
A F.
(ax, mx)]
Regor (T,,, (T,go,(TTo,n + v (log(6-1)
where (i) follows from the fact that by Proposition C.8, policy satistying Vt, (1T) I 0 satisfies Vi, (xre) Os, (ii) is an application of Hoeffding Azuma to bound Ei= Eaa,, (e, Ei=z Bar [e(ar, Ite yc]] and:
y Fe,
E yEY ((Be
sup
[l(ae, Ft, F1,
E ār-ei
[e(ās, ze. w|l M(p..
E
[ (ac,
by Lemma C.10 we can bound the E k Borrp (A, (ae, [] term, hence,
ym MM (pri (e) + xinf at' (T, Ei= E(F). a)
(T)
Regret, S inf
x30
a
+ Regoo (T, 11) + Tlgg(6-1)
This concludes the first bound which holds with probability at least 36 as we take a union bound over the online regression oracle guarantee, the online learning oracle guarantee, and the application Hoeffding Azuma. To conclude the second part of the statement, we need to show that for
E Ma 22) [e(a, x. y)] Eaup [e(a, 2. v)l
n² = (F,
sup F.F
E Ba
A (a,
we have that V. (pr; xz) S 0. To this end, note that
MM x
F(,
= sup yEy
[l(a,, 02,80]
[e(āe, Fz, s2,011
R²*
E ai-M
[ [ (a),
āc-ii
sup E (PriM((i) ((a,,
E ap-p
[l(āe 2z, 2,,
yEy
E Ba [e(a, x, y)] - Bang [L 2,]]
sup FC
E. a a)-MiiF
| xz)
E Ma
(a)
< sup yEy (.
[K(ār, 20, ((06,21,.11 E derup [((ar,
sup Mi (a (10) Be, 1 A,, (1)
E M.MM
[ (az, 2[]
0
C.4.1. PROOFS POLYTOPIC CONSTRAINTS WITH SCALAR FEEDBACK
Recall that Lin (F: is defined the distribution induced by drawing and outputting (ā;; where ((ā max fy [0, qā E P(F)). First show lemma that lower bounds F(;FF.
Lemma C.12. Let F be arbitrary subset of Poly and consider some à (OF)) r(aFF)
max (7 E [0, 1] rā E P(F)} is lower bounded as:
b
(ā; F) 2 (r
29

---

Online Learning with Unknown Constraints
Proof. From the definition of O(F), know [l b for some / E F. Let f be arbitrary function in F.
Then: Let a (4)
lf(aa)]lo = IIf(aā) + f(aā) - f(aā)
2 (I((a)) 1lo + [If((aa) l(a
s a(b Ax(ū))
b
This shows that od & P(F) f was arbitrary. Since we defined F) max ( [0, : E P(F)), it follows that
(a;F) 2 a= b (5(āa
Lemma. (Lemma 5.11 Restated) Suppose Assumption 5.4 holds. Then, K* (JPPlly MMLnn v DzPa.
Proof. Given Lemma C.12, the proof is analogous to that Lemma 5.6.
30


Reviews:
[{"review_id": "GYzRlieAA3", "reviewer": "Reviewer_pLb5", "summary": "This paper studies the problem of bandit with constraints. Specifically, the forecaster wants to minimize the regret, while keeping the safe constraints satisfied with high probability. To resolve this question, the authors propose a new complexity measure, and they provide upper bounds and lower bounds to the regret\n1. They proposed an algorithm with regret bounded in terms of this complexity measure.\n2. If the sum of this complexity measure from step one to $T$ scales linear with $T$, then no algorithm can achieve sublinear regret.", "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": "We would like to thank the reviewer for their review and questions. If the reviewer wishes, we are more than happy to engage in follow-up discussions through OpenReview! \n\n> \"The upper and lower bounds do not match\" and \"Can you prove a lower bound stating that the regret is lower bounded by the sum of $\\mathcal V(\\mathcal F_t)$?\" \n\nThis is true - getting exactly matching upper and lower bounds is a work in progress. The main take away of the lower bound was to show that at least asymptotically, minimizing the proposed complexity measure is necessary for safe learning. \n\n> \"In the lower bound you designed, we have to solve the optimization problem to find p to minimize $M(p)$. Is there any efficient algorithm that can achieve this? \n\nWe are a little confused why the reviewer is interested in the optimization problem to find p minimizing $M(p)$ in the lower bound. As for solving this optimization in the upper bound,  (line 243 right column), we notice that this is a saddle-point optimization. This can be solved up to desired accuracy (through standard techniques) by treating it as a two-player game where the min-player who chooses $p$, and the max-player chooses $f,f',y$. This can be solved by forming an $\\epsilon$-net over the set of actions and while the optimization time complexity would be exponential in the dimension, it is still optimizable and gives a concrete mapping for a fixed $\\kappa$. For finite, linear and generalized linear examples we show computationally efficient (but sub-optimal from point of view of optimization in line 243) mappings such as scaling etc suffice and provide upper bounds through our techniques.", "claims_and_evidence": "Yes, the claims in this submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes. I checked the proofs of main theorems including Theorem 4,2, Theorem 4.3 and Theorem 4.4.", "experimental_designs_or_analyses": "No experiments in this paper.", "relation_to_broader_scientific_literature": "Previous literature either studies safe bandit with known constraints, or linear bandit with unknown constraints, or convex optimization with unknown constraints. The setting considered in this setting of bandit with function approximation and unknown constraints, is new and not appeared in previous literature.", "essential_references_not_discussed": "Not that I know of.", "other_strengths_and_weaknesses": "Strengths:\n1. This paper is well written. The proofs are correct.\n2. The developing of this new concept $V_\\kappa$ is insightful, as it provides both upper and lower bounds to the regret.\n\nWeaknesses:\n1. The upper and lower bounds do not match.", "other_comments_or_suggestions": "I don't have further comments and suggestions.", "questions_for_authors": "I have the following questions regarding this paper:\n1. The lower bound only states that when the sum of $V(F_t)$ is at least $\\Omega(T)$, then no algorithm can achieve sublinear regret. Can you prove a lower bound stating that the regret is lower bounded by the sum of $V(F_t)$?\n2. In the lower bound you designed, we have to solve the optimization problem to find the p to minimize $M(p)$. Is there any efficient algorithm that can achieve this?", "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": "DFgvquTrqk", "reviewer": "Reviewer_cCk6", "summary": "This paper is on contextual online learning with unknown constraints that are stochastic and roundwise. Let $\\ell$ be a given loss function, of an action $a \\in \\mathcal{A},$ a context $x \\in \\mathcal{X}$ and an \"outcome\" $y \\in \\mathcal{Y}$; and let $f_* \\in \\mathcal{F}$ an unknown constraint function parametrised by $a$ and $x$. It is demanded that, without knowing $f_*$ a priori, the learner must ensure that the selected action $a_t$ satisfies $f_*(a_t, x_t) \\le 0$, serving as a hidden constraint. This is enabled both by the a priori knowledge of, for each possible context $x$, a safe set $\\mathcal{A}_0(x) \\subset \\mathcal{A},$ which allows for initial selection of actions, and noisy feedback of a safety signal $z_t$ (which one can just think of as $f\\_*(a\\_t, x\\_t) + \\mathrm{noise},$ although richer structures can be accommodated). This essentially constitutes a stochastic feedback of the unknown constraint, and actions meeting these constraints are termed safe.\n\nOf course, while meeting this constraint, the learner attempts to optimise a cost. This is captured through a regret with respect to a policy $\\pi$ of the form $\\sum \\mathbb{E}\\_{a_t \\sim p_t}[ \\ell(a_t, x_t,y_t)] - \\ell(\\pi(x_t), x_t,y_t)$. Here, this outcome signal $y_t$ is not revealed to the learner until after the action $a_t$ is selected, and $p_t$ is a law over actions that the learner uses to select $a_t$ (and this must be supported on $a : f_*(a, x_t) \\le 0$). Thus, this boils down to a mildly structured version of the standard adversarial online learning setup (which is used for reasons that will be seen below). \n\nThroughout, the set of competing policies is restricted to the elements of a known class $\\Pi$ that are always safe, i.e., $\\Pi_T := \\{ \\pi \\in \\Pi : \\forall t, \\pi(x\\_t) \\in \\mathcal{A}\\_t \\},$ where $\\mathcal{A}\\_t = \\mathcal{A}\\_t(x\\_t) = \\\\{a : f\\_*(a, x_t)\\le 0\\\\}$. \n\nAt a high level, then, this setup considers online learning with unknown unconstraints, where the constraint information follows a stochastic bandit framework, while the cost minimisation follows the adversarial online learning framework. As such, the setting mixes aspects of safe stochastic bandits, specifically the roundwise enforcement of constraint using noisy bandit observations of the same, and online learning with unknown static constraints. \n\nThe paper aims at general characterizations of when sublinear regret and roundwise-safety can be attained in this setting, along with general methods that may attain the same. Towards this, the authors begin with an algorithmic framework that generalises a \"optimistic to pessimistic projection\" idea of Hutchinson et al. that was proposed for the setting of safe linear bandits. At a high level, let $\\mathcal{F}\\_t \\subset \\mathcal{F}$ denote the version space of functions that agree with the constraint feedback, constructed via an online regression oracle (and naturally, under and Eluder dimension constraint on $\\mathcal{F}$). This version space induces two natural sets of actions at time $t$\n - the optimistically safe actions $O\\_t = \\\\{ a : \\exists f \\in \\mathcal{F}\\_t : f(a, x_t) \\le 0 \\\\},$ and \n-  the pessimistically safe actions $P\\_t = \\\\{a : \\forall f \\in \\mathcal{F}\\_t : f(a,x_t) \\le 0\\\\}$.\n\nNote that $P\\_t$ is all of the actions that certifiably are safe (with high probability et c.) given all of the safety feedback (and the known safe actions a priori). As such, to ensure safety, the learner _must_ be restricted to selecting actions only from $P\\_t$. Thus, a crucial challenge of this setup is the expansion of $P\\_t$ towards the true set of feasible action (this also shows up in safe bandits). On the flipside, the competing policies cannot select an action outside of $O\\_t$, and so if we could pick actions from this set using a low-regret method, we would ensure good cost regret. The algorithmic approach taken is to map from a good law over actions in $O\\_t$, to a law over $P\\_t$. \n\nConcretely, let $M$ be a map from laws over $O\\_t$ to laws over $P\\_t$ (that can further utilise the $\\mathcal{F}\\_t$ and the context $x_t$). The algorithmic framework proposed in the paper is thus:\n - using an online learning oracle, compute a distribution $\\tilde{p}\\_t$ over $O\\_t$. It is assumed that this is low-regret against policies in $\\Pi_T$\n- Draw and play $a_t \\sim p\\_t = M(\\tilde{p}\\_t , \\mathcal{F}\\_t, x\\_t)$. \n\n$\\newcommand{\\vv}{\\mathcal{V}} $ To control the regret of such play, the authors define a complexity measure associated with this map $M$, and parameterised by a number $\\kappa \\ge 0$,  $$  \\vv\\_{\\kappa}^M(\\tilde{p}\\_t, \\mathcal{F}\\_t, x\\_t) := \\sup\\_{y} \\\\{ \\mathbb{E}\\_{a \\sim M(\\tilde{p}\\_t)}[ \\ell(a, x_t, y)] - \\mathbb{E}\\_{a \\sim\\tilde{p}\\_t}[ \\ell(a, x_t, y)] \\\\} - \\kappa \\mathbb{E}_{a \\sim M(\\tilde{p}\\_t)}[\\Delta\\_{\\mathcal{F}\\_t}(a, x_t)].$$ \n\nThe first term above is a worst-case bound on how much extra cost is incurred due to playing according to $p_t = M(\\tilde{p}\\_t),$ while the second term is the expected width, wherein $\\Delta\\_{\\mathcal{F}\\_t}(a, x) = \\sup_{f,f' \\in \\mathcal{F}\\_t} |f(a,x) - f'(a,x)|$. Note that, just by using the fact that we can bound $\\mathbb{E}\\_{M(\\tilde{p}\\_t}[ \\ell(a, x_t, y_t)] - \\mathbb{E}\\_{\\tilde{p}\\_t}[ \\ell(a, x_t, y_t)]$ in terms of $\\vee_\\kappa^M + \\kappa \\mathrm{width}$, this gives a bound on the regret of the form $$ \\mathrm{Reg}(\\textrm{Online Learing}) + \\kappa ( \\mathrm{Reg}(\\textrm{Width})) + \\sum_t \\mathcal{V}^M\\_\\kappa(\\tilde{p}\\_t, \\mathcal{F}\\_t, x_t),$$ where this second term is bounded in terms of a regression cost, the eluder dimension, and an accumulated approximation level.   \n\nThe authors offer the interpretation of $\\vv\\_{\\kappa}^M$ as a tradeoff between the cost of gaining information about the constraint function $f\\_{\\*}$, and between minimising regret (which in turn requires fidelity to the unsafe distribution $\\tilde{p}\\_t$). Naturally, for any $\\kappa,$ we can define an optimal $M_*$ by minimising the objective, which yields a (trajectory-dependent!!) \"measure of complexity\", $\\vv\\_\\kappa(\\tilde{p}\\_t, \\mathcal{F}\\_t, x_t).$ This is presented as an analogue of the decision-estimation coefficient for this problem. \n\nOne can also, for a fixed $M$, optimise the $\\kappa$ to yield the strongest bounds, and various results of this type are stated. Naturally, there are two questions of interest: how pertinent is the measure $\\vv\\_{\\kappa}$ to such regret problems, and if there are situations with maps $M$ that yield sublinear regret in the above setup. \n\nTo address the first, the authors show a lower bound, which essentially says that in a context-free situation with a fixed known loss that is optimised at a safe point, and with a good regression oracle and bounded Eluder dimension, there was a $\\kappa$ such that $\\sum \\vv\\_{\\kappa}(\\tilde{p}\\_t, \\mathcal{F}\\_t) = \\Omega(T),$ then one can find a non-expandable subset of safe actions $P\\_{\\*}$ that are a) all suboptmal by a constant amount, and b) non-expandable (i.e., information about $f\\_{\\*}$ for actions in $P\\_{\\*}$ does not leak information about $f\\_{\\*}$ for actions outside of $P\\_{\\*}$). This implies a strong result, that if the initial safe action set if $P\\_{\\*},$ then sublinear regret is impossible.\n\nFor the second point, the authors study the behaviour of linear constraints (recovering extensions of prior work of Hutchinson et al.), and show a compositionality result that, e.g., extends this to generalised linear models.", "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": "Thank you for the careful read and very helpful suggestions, which we will be sure to incorporate into our final version. If the reviewer wishes, we are more than happy to engage in follow-up discussions through OpenReview!\n\n> The obvious issue here is that this is strongly trajectory-dependent. Now, if the lower bound had said (and this would be very strong indeed) that no matter the situation, if $\\mathcal V_\\kappa$ is not summable, then no method can learn, then I would agree that nothing more can be said, but that's not quite what the lower bound shows: the setup is very particular. \n\nWe believe this point to be important in the reviewer's assessment of the strength of our lower bound. We would like to ask the reviewer **what they meant by \"no matter the situation\"**. We would like to clarify that $\\mathcal V_\\kappa(\\cdot) := \\inf_{M} \\mathcal V_\\kappa^M(\\cdot)$ (line 248 right column), and hence the lower bound states that if even the best mapping is not summable, no method can learn. On the other hand, if this optimal mapping makes $\\mathcal V_\\kappa$ summable then this mapping can be used in upper bounds. Correspondingly, our lower bound is in a setting where $\\mathcal V_\\kappa$ is not summable no matter what mapping is used. Furthermore, while this complexity indeed is trajectory-dependent, the lower bound correspondingly also sums across the trajectory of the best mapping. When we use a particular mapping, the trajectory is what is generated by that mapping. As to the setup being very particular, this setup was engineered to show the necessity of the $\\mathcal V_\\kappa(\\cdot)$ terms. The other terms in the upper bound (Eluder and oracle bounds) are well justified in the literature and each one can already individually shown to be necessary. So we justify the necessity of the novel complexity term we introduced alone. \n\n>  A final issue, of course, is the efficiency of this method: it is not clear to me that in general this viewpoint recovers tight bounds. I do appreciate that this gets the right rates in the linear setting, but is this enough? Certainly, Assumption In other words, I don't quite buy that $\\mathcal V_\\kappa$ \"characterizes the difficulty of safe learning\" (line 56, col 1): the evidence is too thin for such a strong claim, both from the viewpoints of upper and lower bounds.\n\nTo the best of our knowledge at the time of writing, existing works have focused solely on the linear setting. We believe our methodology is a first step towards the analysis of more general settings.  \n\n> I don't know if this is essential, but work on doubly-optimistic methods is omitted from the discussion of safe bandits (Chen et al., ICML 2022, \"Startegies for Safe...\", Gangrade et al., COLT 2024, \"Safe Linear Bandits over Unknown Polytopes\").\n\nWhile these works do indeed have a \"doubly optimistic\" flavor to them, these works do not study the same setting of per-round strict safety constraints. Among \"doubly optimistic\" works, we believe that the referenced work of Hutchison et al., AISTATS 2024 \"Directional Optimism for Safe Linear Bandits\" is the most relevant as it considers a per-round strict safety constraint setting. \n\n> One important weakness is that the paper is that the main ideas are presented in a pretty rushed way... . It somehow seems like in order to assert the generality of the result, some level of comprehensibility is sacrificed. \n\nThank you for the feedback, and we will work towards expanding the presentation in sections 4 and 5. As the reviewer later suggests, shortening section 3.3 to make space for this expansion seems like a wonderful idea. As noticed by the reviewer, a focus of our paper was to express the generality of the approach (as existing works focus solely on the linear setting) - and we will work to make this presentation more digestible. \n\n> There are jarring variations in line spacing ... \n\nWe will fix this in our final version! \n\n> The discussion following assumption 3.2 should simply describe, in words, that this property holds true, and move Proposition 3.3 to the appendix ...\n\nThank you for the feedback, we will shorten this section. The reason we provided the proposition was because while the underlying proof technique is standard, we couldn't just cite existing results and claim Sequential Rademacher Complexity upper bounds the online learning regret as we needed to satisfy the given constraints - which requires some nontrivial manipulation. \n\n> Please be explicit about the independence structure of the feedback ...\n\nWe will make a note early on explicitly mentioning independence structure. We had hoped $z_t \\sim p_{\\text{signal}}(f^*(a_t,x_t))$ would highlight this.", "claims_and_evidence": "The paper is positioned as providing a general complexity measure for this problem, $\\vv\\_{\\kappa}$ and a general methodology driven by this object. The main claims beyond this are that this methodology can yield nontrivial regret bounds in certain scenarios (which is demonstrated for linear losses and constraint), and that without sublinearity of $\\sum \\vv\\_{\\kappa}(\\tilde{p}\\_t, \\mathcal{F}\\_t),$ there may be situations where no method can obtain sublinear regret.\n\nFor me, all of the subsequent claims are fine, and the main sticking point, naturally, is whether I buy this $\\vv\\_{\\kappa}$ as a general complexity measure. The obvious issue here is that this is strongly trajectory-dependent. Now, if the lower bound had said (and this would be very strong indeed) that no matter the situation, if $\\vv\\_{\\kappa}$ is not summable, then no method can learn, then I would agree that nothing more can be said, but that's not quite what the lower bound shows: the setup is very particular. The authors also appeal to the DEC formulation, but note that this paper is careful to state things in terms of a static model class. A final issue, of course, is the efficiency of this method: it is not clear to me that in general this viewpoint recovers tight bounds. I do appreciate that this gets the right rates in the linear setting, but is this enough? Certainly, Assumption  In other words, I don't quite buy that $\\vv\\_{\\kappa}$ \"characterizes the difficulty of safe learning\" (line 56, col 1): the evidence is too thin for such a strong claim, both from the viewpoints of upper and lower bounds.", "methods_and_evaluation_criteria": "This is a theoretical paper. The main methodological idea in the proposed framework is to project distributions over an optimistic estimate of the feasible set to that over a pessimistic estimate of the same, which (significantly) generalises an existing approach of Hutchinson et al. in safe bandit problems (and so makes sense).", "theoretical_claims": "I at least skimmed through most of the proofs, and they appear correct to me. I read appendices A and B more closely, and these are correct as far as I can tell.", "experimental_designs_or_analyses": "N.A.", "relation_to_broader_scientific_literature": "I think the contributions are novel, and extend certain existing ideas strongly and in a insightful way. The results themselves are interesting. The observation that (although in a restricted setting) if $\\vv\\_{\\kappa}(\\tilde{p}\\_t, \\mathcal{F}\\_t)$ is not sublinearly integrable, then _no method_ can learn nontrivially is, to me, surprisingly and insightful. The general upper bound is also interesting, especially since it can be realised well for linear models, but leaves the question of how generic it really is open. Overall, despite the gaps, I am certain that the results will be of interest to the online learning community at ICML.", "essential_references_not_discussed": "I don't know if this is essential, but work on doubly-optimistic methods is omitted from the discussion of safe bandits (Chen et al., ICML 2022, \"Startegies for Safe...\", Gangrade et al., COLT 2024, \"Safe Linear Bandits over Unknown Polytopes\").", "other_strengths_and_weaknesses": "One important weakness is that the paper is that the main ideas are presented in a pretty rushed way. Take page 5, column 2, the main motivation and presentation of the underlying idea. The introduction of $M$ would benefit from some explanation as to why this projection idea could possibly get good regret, which would help introduce the idea of $\\vv\\_{\\kappa}^M$. This would also benefit from an explanation of what the terms therein are, and why they are arising/natural. In part this is also true of section 5. \n\nI also found the order of the presentation to be confusing, and did not really understand the idea of the paper until I went and stared at Algorithm 1, understood the methodological idea, and then went back to the general complexity measure being proposed. It somehow seems like in order to assert the generality of the result, some level of comprehensibility is sacrificed. I think this hurt the paper more than it helps it.\n\nNote that this may well be an issue of space: the DEC paper, which the authors compare their contributions to, takes a 130+pages (with 60+ pages in the main text) to explain its ideas and convince them that they really have something concrete. If this is the reason, then the authors should, IMO, think about if a conference paper with limited page counts is really the right venue to send their work to, and if it may not instead benefit with a more comprehensive treatment sent to a journal. \n\n\nIn any case, right now I think I find the claims of $\\vv\\_{\\kappa}$ being a general complexity measure that captures safe online learning to be somewhat exaggerated, and find the presentation a bit lacking, but I do think that the results are strong and interesting. The former mostly is why my recommendation below is a weak accept rather than an accept.", "other_comments_or_suggestions": "- There are some jarring variations in the line spacing across the document (compare, e.g., line 127 onwards in columns 1 and 2). Usually people do this for space, but there's like enough whitespace floating about the document for this to not be necessary. Please fix this, it just distracts from reading.\n\n- IMO the discussion following assumption 3.2 should simply describe, in words, that this property holds true, and move Proposition 3.3 to the appendix --- this is not per se adding much to help explain the main ideas of this paper, and this space can be more valuably spent doing that, or expanding upon the very terse treatment of section 5. I think in part I am saying this because for most online-learning algorithms I can think of, one begins with a round-wise control on the loss of the actions, and with this view it is not surprising to me that as long as the action space available to the learner contains the actions of all competing policies, the regret is controlled. There may well be issues with this (haven't thought too much), but IMO a reader would be happy to buy the assumption on the basis of this (and a general proof of achievability in the appendix).\n\n- Please be explicit about the independence structure of the feedback (rather than telling me about its generality): in particular, my reading is that it is intended that $z_t$ is conditionally independent of the history given $x_t$ and $a_t$ (which should be stated).", "questions_for_authors": "-", "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": "JLBevmw4WK", "reviewer": "Reviewer_EPZo", "summary": "This paper studies the online adversarial learning problem of achieving no-regret guarantees while playing actions subject to an unknown constraint at each time-step. At each round $t$, the set of safe actions is a function of the adversarially chosen context and an unknown safety constraint $f*$; after playing an action the learner receives a loss vector and safety feedback correlated to the unknown constraint value. The goal is to achieve cumulative loss with sublinear regret with respect to the best action in hindsight that satisfies all constraints, while also playing actions that satisfy the constraints with high probability each round. The authors present a generalized algorithm that achieves this, making use of a black-box no-regret algorithm with constrained actions sets (used to make predictions that achieve low regret while simultaneously choosing only safe actions), and a black-box online regression model (used to predict the value of the unknown constraint function $f*$ at each round). They show that a simpler version of this algorithm solves the slightly-modified problem of achieving no-regret guarantees while satisfying long-term constraints (as opposed to a constraint at each round). Finally, since the algorithm is non-constructive (assuming the existence of a mapping function satisfying a particular property), they discuss several settings of action sets, safety constraints, and loss functions for which this mapping can be concretely defined, and thus the algorithm itself. \n\nThe general idea of the algorithm is to use the regression model’s predictions of the value of $f*$ at each round to determine a subset $\\mathcal{F}_t$ of the constraint functions that includes the true safety function with high probability. Then the constrained no-regret algorithm can be used to predict a distribution over actions by constraining to the set of actions that could be safe (inferred from $\\mathcal{F}_t$), which is mapped to a distribution $p$ over the set of actions which are definitely safe using a mapping function $M$. The authors define a complexity measure (defined in part by $M$) that at a high-level, trades off between how much worse your loss regret may be because you need to play a safe action, and how much new information you expect to learn about $f*$ using the current distribution $p$. By optimizing for $M$, one can keep the sum of this measure over time small, and the overall regret can be bound by this sum as well as the regrets of the two black-box algorithms used as subroutines.", "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": "We would like to thank the reviewer for their review and questions. If the reviewer wishes, we are more than happy to engage in follow-up discussions through OpenReview! \n\n> In Section 4.4, the authors say that Assumption 5.1 is necessary for safe learning in the given setting, but this seems misleading – they show this by providing a counter-example, but this doesn’t prove the necessary condition – couldn’t there be settings where Assumption 5.1 doesn’t hold and still safe learning is possible (unless the adversary is choosing the safety function, which I don’t think they are doing). \n\nWe would like to point out that $f^*$ is unknown and fixed - we could indeed interpret it as being chosen by the adversary before the game starts (and hence the adversary could choose $f^*$ in the offending $\\mathcal F^*$ mentioned in the counter-example). Alternatively, we could view Assumption 5.1 as being $f^*$-dependent. We could instead require that $\\forall \\mathcal F \\subseteq \\mathcal F^{FAS}$ s.t. $f^*\\in \\mathcal F$ ... the gap-condition in the body of Assumption 5.1 holds.  \n\n> On line 134 ... is $p_{signal}$ a distribution parameterized by $f^*(a,x)$? Should the mapping be from [-1,1] to a distribution over $\\mathcal Z$ \n\nYes, $p_{signal}$ is a distribution parameterized by $f^*(a,x)$. And yes! Thank you for pointing out this typo, we will update this in our final version. \n\n> In Section 3.3, performance is compared to some set of policies $\\Pi$ which I assume need not be deterministic. Does this mean $\\Pi_T$ is the set of policies $\\pi$ which always only induce distributions over actions whose support is within the constrained action set, or is it comparing to specific runs of the policy that satisfy the constraints? \n\n$\\Pi_T$ would be the set of policies which only induce distributions over intersection of constrained action sets $\\cap \\mathcal A_t$. This aligns with the fact that generally we compare against policies that are always safe (induce distributions over safe unknown safe set).", "claims_and_evidence": "The claims are all proved.", "methods_and_evaluation_criteria": "Yes, the defined setting seems reasonable. The assumption of receiving (possibly noisy) feedback as a function of the safety function’s value generalizes to many safety-critical settings.", "theoretical_claims": "I looked at the proof for the main Theorem 4.2 (which looked good), though not all of the lemmas preceding it.", "experimental_designs_or_analyses": "There are no experiments.", "relation_to_broader_scientific_literature": "I am not very familiar with the learning with constraints literature – based on the papers cited by the authors it seems that the main difference between these results and prior ones are that other algorithms either focus on achieving strong safety guarantees without prioritizing achieving low regret, or bound the number of “unsafe” actions that will be taken over a long time, rather than consistently playing safe actions with high probability.", "essential_references_not_discussed": "Not to my knowledge", "other_strengths_and_weaknesses": "Strengths:\n\nSafety-critical settings often coincide with non-distributional / adversarial settings, so this is an interesting area of study and the algorithm seems novel and applicable. The complexity measure introduced which is not only sufficient (in a sense) for bounding to get low regret, but also necessary to have low for safe learning to be possible indicates that it does measure something critical to the safe learning setting. The extension of this work to the long-term constraints setting is interesting because the approach seems quite different from what I have generally seen in the area (usually involving no-regret algorithms using the Lagrangian or some modification as a loss function). I also think the paper is very well-presented, with the structure and intuition behind the ideas / proofs making it fairly easy to follow throughout, even for people not familiar with the area. \n\nWeaknesses:\n\nIn Section 4.4, the authors say that Assumption 5.1 is necessary for safe learning in the given setting, but this seems misleading – they show this by providing a counter-example, but this doesn’t prove the necessary condition – couldn’t there be settings where Assumption 5.1 doesn’t hold and still safe learning is possible (unless the adversary is choosing the safety function, which I don’t think they are doing).", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1.\tOn line 134, is $p_{signal}$ a distribution parametrized by $f^*(a,x)$? Should the mapping be from [-1,1] to a distribution over $\\mathcal{Z}$?\n2.\tIn Section 3.3, performance is compared to some set of policies $\\Pi$ which I assume need not be deterministic. Does this mean $\\Pi_T$ is the set of policies $\\pi$ which always only induce distributions over actions whose support is within the constrained action set, or is it comparing to specific runs of the policy that satisfy the constraints?", "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": "rWA8VkUUht", "reviewer": "Reviewer_zBP3", "summary": "The paper addresses the problem of online learning with unknown safety constraints, where constraint satisfactions is required per round. The authors provide a general meta-algorithm based on the Online Learning oracle for online learning strategy with known constraints, and Online Regression oracle for constraints estimation. The algorithm is based on constructing Optimistic and Pessimistic safe action sets, and a mapping strategy from the optimistic to the pessimistic set. The paper provides an upper regret bound which is also depending on the Eluder dimension describing complexity of the constraint function class and on a new complexity measure $\\mathcal V_{\\kappa}(\\cdot)$.  The paper also provides a lower bound demonstrating that if $\\lim_{T \\rightarrow \\infty} \\sum_{t = 1}^T \\mathcal V_{\\kappa}(\\tilde p_t, \\mathcal F_t) > 0$, then no safe algorithm can ensure a sublinear regret. The paper also provides concrete algorithm and bounds in some problem cases such as with linear constraints.\n\n## Update after rebuttal:\n\nI thank the authors for the response. I have also read the other reviews, and I decided to keep my initial score.", "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": "We thank the reviewer for their review and helpful suggestions, which we will be sure to incorporate into our final version. If the reviewer wishes, we are more than happy to engage in follow-up discussions through OpenReview!\n\n> In particular, the novel complexity measure proposed is recalled as $\\mathcal V_t(\\kappa)$ in the introduction, and $\\mathcal V_k(\\cdot)$ further in the paper. \n\nThank you for the feedback - we had made this notational choice in the \"key contributions\" section as we wanted to emphasize the dependence on $\\kappa$, and avoid cluttering the definition with technical definitions of $\\mathcal F_t, \\tilde p_t$. We will update the measure as $\\mathcal V_\\kappa(t)$ in the \"key contributions\" to keep it more consistent. \n\n> Also, it is unclear to me why the complexity measure depends on the time step? In particular, it depends on $(\\tilde p_t, \\mathcal F_t, x_t)$ \n\nThis is true, the complexity measure really is a function of just those three parameters. The complexity measure captures the difficulty of matching a target $\\tilde p_t$ using distributions from $P_t$ (defined through $\\mathcal F_t$ and $x_t$) under worst case loss while off-setting information gain w.r.t $\\mathcal F_t$, weight by $\\kappa$. However, when applied to our Main Algorithm (Algorithm 1), the instantiations of those three parameters depend on time-step. \n\n> Maybe a typo, but in Theorem 4.4 the dependence on $x_t$ is omitted \n\nThis is not a typo - as stated in the theorem statement, our Theorem 4.4 considers a simplified non-contextual setting (i.e.  $\\mathcal X = \\\\{ \\\\}$). In non-contextual settings, we drop the context argument (mentioned in line 274 right column footnote). \n\n> How can the complexity measure dependent on the contexts? Should it maybe be rather defined in a way which is independent, like a worst case? \n\nThis indeed is a valid alternative way of defining the complexity measure - we could instead have taken worst case contexts. However, as the pessimistic and optimistic sets are dependent on contexts, we thought this would make the notational a little less convoluted.  \n\n> How can this complexity measure be estimated in advance in practice? \n\nIn practice, we believe the best way to address this complexity measure is to use a choice of $\\kappa^*$ that ensures that $\\mathcal V_{\\kappa^*} < 0$ (various concrete examples of this methodology described in section 5). If one wanted to directly estimate the value of the complexity measure, one could deploy the methodology mentioned in the response to reviewer pLb5. \n\n> ... it follows that one needs to have not just bounded complexity measures $\\mathcal V_t(\\kappa)$, but their sum to be growing less than linearly on T\n\nYes, this suggests we'd need the sum of $\\mathcal V_t(\\kappa)$ to be asymptotically growing sublinearly in T (otherwise safe learning is impossible). This is precisely our main takeaway in justifying the necessity of $\\mathcal V_t(\\kappa)$ as a measure of the complexity of safe learning! \n\n> ... the intuition on the notion of $\\kappa$ is not clear. \n\nThank you for the feedback. As mentioned in line 57 left column, $\\mathcal V_t(\\kappa)$ defined in eq 5 ... captures the per-timestep trade off between loss minimization and information gain w.r.t. unknown constraint. $\\kappa$ is the parameter that controls the weight placed on information gain. While this is evident upon inspection of eq 5, we agree that it would be illuminating to mention this explicitly. We will update this paragraph to make this more clear! \n\n>  Is there a way to have a more general notion of complexity? Maybe the asymptotic sum directly, under some conditions on the feedback $x_t$? \n\nYes, we could instead use the asymptotic sum directly as the measure of complexity instead. Getting the upper and lower bounds to match is an ongoing work, and we would like to arrive at a unified measure of complexity. \n\n> Typos in lines 260 and 275 \n\nThank you for pointing out these typos to us. We will fix them in the final version.", "claims_and_evidence": "Yes, it seems so, mostly. However, there are some inconsistent notations and unclarities regarding the new complexity measure. In particular, the novel complexity measure proposed is recalled as $\\mathcal V_t(\\kappa)$ in the introduction, and $\\mathcal V_{\\kappa}(\\cdot)$ further in the paper. It would be good to keep them consistent. Also, it is unclear to me why the complexity measure depends on the time step? In particular, it depends on $(\\tilde p_t, \\mathcal F_t, x_t)$ (Maybe a typo, but in Theorem 4.4 the dependence on the $x_t$ is omitted $(\\tilde p_t, \\mathcal F_t) $ ) Here $x_t$ is a context received at step $t$. How can the complexity measure dependent on the contexts? Should it maybe be rather defined in a way which is independent, like a worst case? And as an asymptotic sum? How can this complexity measure be estimated in advance in practice?\n\nAlso, at the beginning of Section 4 it is written that a bounded $\\mathcal V_{\\kappa}(\\cdot)$ is asymptotically necessary. Although, does from theorem 4.4 it follows that one needs to have not just bounded complexity measures $\\mathcal V_{\\kappa}(\\cdot)$, but their sum to be growing less than linearly on T. \n\nAlso, the intuition of notion $\\kappa$ is not very clear. It would be great if it explained more.", "methods_and_evaluation_criteria": "The proposed method makes sense, the problem seems to be quite general.", "theoretical_claims": "I did not check the proofs in the appendix, and not all the derivations in the paper body. In general they seem correct", "experimental_designs_or_analyses": "There are no experimental designs", "relation_to_broader_scientific_literature": "The paper provides new insights about the complexity of a per-step online learning, also in comparison to the complexity of cumulative constraints satisfaction.", "essential_references_not_discussed": "Not that I am aware of.", "other_strengths_and_weaknesses": "The paper is quite clearly written in general and tries to add the intuition for any notion and claim they state. However, the number of the notations is quite high, and sometimes hard to follow. Also, the complexity notion $\\mathcal V_t$ is questionable since it depends on time-step $t$ and on the particular realizations of the context $x_t$ and the estimated version space $\\mathcal F_t$. Is there a way to have a more general notion of complexity?  Maybe the asymptotic sum directly, under some conditions on the feedback $\\{x_t\\}$?", "other_comments_or_suggestions": "There are a few typos I noticed, apart from $\\mathcal V$:\n\n- line 260, right side: \"with respect to with respect to\"\n- line 275, right side: comma", "questions_for_authors": "See Claims and Evidence", "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": "Ceodu0gdH2", "reviewer": "Reviewer_sXWZ", "summary": "The paper provides new insights into the problem of online learning with unknown constraints. Lower and upper bounds that connect the difficulty of the problem with Eluder dimension are derived.", "questions": "", "limitations": "", "rating": 2, "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": "We thank the reviewer for their questions. If the reviewer wishes, we are more than happy to engage in follow-up discussions through OpenReview!\n\nWe would like to highlight the fact that our paper is theoretical in nature, and our main focus is to establish information theoretically when safe learning is possible, and to develop algorithms for safe online learning with general safety function classes $\\mathcal{F}$ given access to an online learning oracle and an online regression oracle. \n\n> The practical motivation of the problem setup and the how the proposed modelling of the safety sets and the associated feedback mechanisms are connected to real-life applications is highly unclear. \n\nWe believe there is practical motivation in enforcing a strict per-round safety constraint. The feedback mechanism is general enough to encompass a standard $f^*(a_t,x_t) + $ (subgaussian gaussian noise) model commonly assumed in the literature as well as binary feedback following a Boltzmann distribution, which is a well-studied form of feedback in sociology known as the Bradley-Luce-Shepard rule. \n\n> Why is the constraint function assumed to be fixed? Environment changes over time can very well induce changes in functional forms of the constraint set.\n\nWhile other works (e.g. Neely et al 2017 \"Online convex optimization with time varying constraints\") consider time-varying constraints in the setting of \"long term constraints\" (a significantly weaker safety ask), in the setting of strict per-timestep constraints, one would need a fixed safety constraint for there to be any hope of learning such a function in a every-time safe way. Let us further recall that we allow for a context and that the safety function is also a function of this context. Thus one could encode changes in safety set over time by encoding time as a part of context. \n\n> The feedback mechanism $P_{sig}$ is assumed to be known to select the online regression oracle. How practical is it to obtain such prior knowledge or to even verify such assumptions?\n\nIf we have prior knowledge about the problem at hand we can select for the appropriate feedback mechanism. For example, in settings with instrument readings with noise, we could adopt a standard  $f^*(a_t,x_t) + $ (subgaussian gaussian noise) model. With human-generated feedback models, we could use the Bradley-Luce-Shepherd rule and assume that the feedback is binary following a Boltzmann distribution. \n\n > The assumed regret minimization online oracle is only shown to be computationally feasible in a simplified setting of linear optimization. In general the computational feasibility of this assumption is unclear. This also adds into my concerns regarding the usefulness of the proposed methodologies in real life applications.\n\nThis is true, we only show a concrete implementation for safe linear optimization. In this paper, our focus is more theoretical in nature, instead opting to show the existence of such online learning oracles, and proving that the performance of our algorithm depends on variations of complexity measures found in the online learning literature. \n\n> In Assumption 3.2, the functional form of the loss $\\ell$ remains fixed. Do we have to know in advance, the form of loss function in general (example, it is squared error, or loss from the GLM family like linear or logistic regression type losses). Or can the loss be selected adversarialy by nature?\n\nYes, we assume we know the form the loss function takes - we believe this is a standard assumption in the online learning literature. \n\n> How computationally feasible is to do the sampling in Line 8 of the Algorithm 1?\n\nThis wholly depends on choice of mapping $\\mathbf M$ - for the linear optimization example, this is simply sampling from a set of $d+1$ vectors. Discovering other settings where all steps/oracles are computationally efficient is an active work in progress.  \n\n> Though the paper provides theoretical insights, the provided upper and lower bounds do not match.\n\nThis is true - getting exactly matching upper and lower bounds is a work in progress. The main take away of the lower bound was to show that at least asymptotically, minimizing the proposed complexity measure is necessary for safe learning.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "See Questions for Authors", "theoretical_claims": "No", "experimental_designs_or_analyses": "No", "relation_to_broader_scientific_literature": "It is well addressed in Related works, though I have concerns. See Questions for Authors.", "essential_references_not_discussed": "Not to my knowledge.", "other_strengths_and_weaknesses": "See Questions for Authors.", "other_comments_or_suggestions": "See Questions for Authors.", "questions_for_authors": "Mainly I have doubts on whether the proposed methods are only theoretical constructs with very weak practical implications.\nThe concerns are noted below:\n\n1)\tThe practical motivation of the problem setup and the how the proposed modelling of the safety sets and the associated feedback mechanisms are connected to real-life applications is highly unclear.\n2)\tWhy is the constraint function assumed to be fixed? Environment changes over time can very well induce changes in functional forms of the constraint set.\n3)\tThe feedback mechanism $P_{sig}$ is assumed to be known to select the online regression oracle. How practical is it to obtain such prior knowledge or to even verify such assumptions?\n4)\tThe assumed regret minimization online oracle is only shown to be computationally feasible in a simplified setting of linear optimization. In general the computational feasibility of this assumption is unclear. This also adds into my concerns regarding the usefulness of the proposed methodologies in real life applications.\n5)\tIn Assumption 3.2, the functional form of the loss $\\ell$ remains fixed. Do we have to know in advance, the form of loss function in general (example, it is squared error, or loss from the GLM family like linear or logistic regression type losses). Or can the loss be selected adversarialy by nature?\n6)\tHow computationally feasible is to do the sampling in Line 8 of the Algorithm 1?\n\n7) Though the paper provides theoretical insights, the provided upper and lower bounds do not match.", "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: This paper studies the problem of online adversarial learning with unknown constraints, where the goal is to minimize regret while ensuring safety at each round. At every time step, the learner is presented with a context chosen adversarially, and must select an action from a set that depends on this context and an unknown safety constraint. After taking an action, the learner receives a loss vector and feedback correlated with the constraint. The authors show that their algorithm enjoys a regret bound in terms of a complexity measure. They also show that
if the sum of this complexity measure scales linear with the number of rounds $T$, then no algorithm can achieve a sublinear regret.

The proposed algorithm is non-constructive, relying on the existence of a mapping with a certain desired property. However, the authors do demonstrate that in several practical settings—defined by specific types of action sets, constraints, and loss functions—this mapping can be made explicit and hence the algorithm is implementable in those cases.

The majority of the reviewers (4 out of 5) recommend a weak accept, while one recommends a reject (whose main concern is its practical implications, which could be subjective). A potential weakness of this work might be whether the proposed algorithm can be _efficiently_ implemented in practice and if the setting is highly relevant to the real world. But a couple of reviewers believe that this can still be of interest to the online learning community at ICML. Furthermore, the majority of the reviewers agree that this paper is well written and the technical analysis are solid.  Hence, this paper is moved to a weak accept if room.
Decision: Accept (poster)