Data-Dependent Regret Bounds for Constrained MABs
Authors: Gianmarco Genalti
Francesco Emanuele Stradi
Matteo Castiglioni
Alberto Marchesi
Nicola Gatti
Venue: NeurIPS 2025 poster ()
Keywords: Data-Dependent Bounds
MAB
Hard Constraints
Primary area: theory

Abstract: This paper initiates the study of data-dependent regret bounds in constrained MAB settings. These are bounds that depend on the sequence of losses that characterize the problem instance.  Thus, in principle they can be much smaller than classical $\widetilde{\mathcal{O}}(\sqrt{T})$ regret bounds, while being equivalent to them in the worst case. Despite this, data-dependent regret bounds have been completely overlooked in constrained MABs. The goal of this paper is to answer the question: Can data-dependent regret bounds be derived in the presence of constraints? We provide an affirmative answer in constrained MABs with adversarial losses and stochastic constraints. Specifically, our main focus is on the most challenging and natural settings with hard constraints, where the learner must ensure that the constraints are always satisfied with high probability. We design an algorithm with a regret bound consisting of two data-dependent terms. The first one captures the difficulty of satisfying the constraints, while the second one encodes the complexity of learning independently of their presence. We also prove a lower bound showing that these two terms are not artifacts of our specific approach and analysis, but rather the fundamental components that inherently characterize the problem complexity. Finally, in designing our algorithm, we also derive some novel results in the related (and easier) soft constraints settings, which may be of independent interest.

Data-Dependent Regret Bounds for Constrained MABs
Gianmarco Genalti"
Francesco Emanuele Stradi'
Politecnico di Milano
Politecnico di Milano
gi gianmarco, genalti@polimi.
francescoemanuele. stradi@polimi..
Matteo Castiglioni
Alberto Marchesi
Politecnico di Milano
Politecnico di Milano
matteo. www.tiillooioollmmiiiii.....
al alberto.. wwe cecheee@@plmmmm...
Nicola Gatti
Politecnico di Milano
ni nicola. acool..gattine. patti@polimi..1
Abstract
This paper initiates the study of data-dependent regret bounds in constrained MAB settings. These are bounds that depend on the sequence of losses that characterize the problem instance. Thus, in principle they can be much smaller than classical (VVT) regret bounds, while being equivalent to them in the worst case. Despite this, data-dependent regret bounds have been completely overlooked in constrained MABs. The goal of this paper to answer the question: Can data- dependent regret bounds be derived in the presence of constraints? ? We provide an affirmative answer in constrained MABs with adversarial losses and stochastic constraints. Specifically.
main focus is on the most challenging and natural settings with hard constraints, where the learner must ensure that the constraints are always satisfied with high probability. We design algorithm with regret bound consisting of two data-dependent terms. The first one captures the difficulty of satisfying the constraints, while the second one encodes the complexity of learning independently of their presence. We also prove a lower bound showing that these terms not artifacts of our specific approach and analysis, but rather the fundamental components that inherently characterize the problem complexity. Finally, designing our algorithm, we also derive some novel results the related (and easier) soft constraints settings, which may be of independent interest.
Introduction
Over the past few years, constrained multi-armed bandit (MAB)
problems have gained increasing
popularity in learning theory (see, e.g., [Liakopoulos et al.) 2019 Pacchiano al. 2021 Castiglioni
et al. 2022a Chen et al. 2022). ). In unconstrained MAB problems, the learner is evaluated solely in terms of regret, which measures the difference between the learner's performance and the performance of an optimal-ine -anaddii---iiighhh decision. Constrained settings introduce additional challenges, as the violated excessively while learning.
learner must also ensure that certain constraints
growing trend in unconstrained MAB research the derivation data-dependent regret bounds (see, e.g., Neu 2015al Lee et al. 2020al) These bounds depend the sequence of losses that
"Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

characterize the problem instance. Some example of such bounds bounds-typically called small-loss regret bounds-are are of the form (*) where L* denotes the cumulative loss of an hitimallin-hindsighhe decision. Clearly, data-dependent bounds can be much smaller than classical Ö(VT) regret bounds, while being equivalent to them in the worst case. Despite this, data-dependent regret bounds have been completely overlooked in the literature on constrained online learning problems.
The main goal of this paper is to initiate the study of data-dependent regret bounds in constrained MAB settings. In particular, aim at answering the following research question:
Can data-dependent regret bounds be derived in the presence of constraints?
In this paper, we provide an affirmative answer to the question above, as described in the following.
We refer the reader to Appendix B for a complete discussion on related works.
1.1 Original Contributions
Given an impossibility result by Mannor al. [2009]. which prevents from obtaining sub-linear regret in constrained settings where both the losses and the constraints are selected adversarially: in this paper we focus on constrained MABs with adversarial losses and stochastic constraints, as customarily done in the literature (see, e.g., [Qiu et al.) (220]). Specifically, our main focus is on the most challenging and natural settings with hard constraints, where the learner's ss goal is to minimize the regret while ensuring that the constraints are satisfied at every round with high probability.
1.1.1 Warm-Up: Soft Constraints
As preliminary step toward our final goal, we design an algorithm with a small-loss regret bound in constrained MAB settings with soft constraints, which may be of independent interest. These settings only require that the constraint violations grow sub-linearly with the number of rounds T, thereby allowing to violate the constraints in some rounds. Although soft constraints are technically easier than hard ones, our algorithm incorporates some key components that are also central to the algorithm for hard constraints. At a high level, our algorithm builds upon approach introduced by Lee et al. [2020a] to derive small-loss regret bounds in unconstrained problems. Our algorithm-calle Constrained OMD with Log- cog-BBrrier (COLB) applies this approach "safe" set of decisions that optimistically satisfy the constraints. This allows to attain linear violations with a high-probabilipg
regret bound of Ö( IT=r ej x=), where x" is decision that is optimal in hindsight while satisfying the constraints in expectation.
1.1.2 Hard Constraints
Our main result in this paper is an algorithm with data-dependent regret bound in constrained MAB settings with hard construints. Our algorithm for these settings-called Safe OMD with Log- Barrier all the core components of COLB, and it adds new ones to deal with hard constraints. Specifically, SOLB always chooses a suitable combination between the decision suggested by COLB and a decision that strictly satisfies the constraints, which is given as input to the algorithm. The SOLB algorithm achieves high-probabilltyy regret bound that is characterized by two data-dependent terms, described in the following.
The first term is Ö( O(VE7 (e_ (x+ )²)),,, where x is the decision that strictly satisfies the constraints given as input. This term captures the difficulty due to constraints.
The second term is Ō( Ö(VE VVV 1 (T*)), and it intuitively encodes the performance of a decision x that is optimal in hindsight while satisfying the constraints in expectation.
Finally, we also provide a lower bound that demonstrates that the two terms in the regret bound of the SOLB algorithm are not artifacts of our specific approach and analysis, but rather the fundamental components that inherently characterize the complexities of the problem. Interestingly, this result also shows that detendepe regret bounds can not only outperform classical ((VT) bounds, but also offer insights into the underlying complexities of learning problems.

---

2 Constrained Multi-Armed Bandits
In the multi-armed bandit (MAB) framework [Lattimore and Szepesvári 2020], learner is repeatedly faced with a decision among K E N4 actions over ' E N4 rounds. At each round E [r]] the learner chooses strategy (i.e., probability distribution over actions) æ; E Ak, where AK the simplex of dimension K 1. Then, they play an action de ~v I; sampled according to this strategy and observe a loss (at), which is defined by vector L, E 10, of losses at round t In this paper, we study a constrained version of the MAB framework (Pacchiano et al. [021]. At each & E [7], in addition to loss, the learner also observes m + constraint costs at,a(aa) one for each constraint i [m]. Each of them is determined by vector Ir.; E [0, 1]K of constraint costs round t. Each threshold 04 [0, 11, and it is considered satisfied by a leamer's strategy whenever the constraint cost is below a; in expectation.
constraint E [m]] is associated
Motivated by well-known impossibility result by Mannor et al. 2009 in this paper we focus on constrained MAB problems in which the losses are chosen adversarillyy and the constraint costs are selected stochastically. Specifically, we assume that, at each round / E [T), the loss vector L is chosen by an adaptive adversary that is aware of the history of interaction up to round - 1, while each cost vector it for i E [ml] is sampled independently from probability distribution G.. For ease of notation, in the following we use L1.T to denote the sequence of all loss vectors L, for ł E [T], while we denote by 9; == Eg-o, [g] the expected value of G; for every E [m].
The performance (in terms of losses) of a learning algorithm is usually measured in terms of regret with respect to a baseline. In the constrained MABs addressed in this paper, the baseline formally defined by the following optimization problem parametrized by L1. and g, for i E [m]:
min #EAK
Σl= CT x
s.t.
OPT(LL:T ticm))) =
(1)
9, x S as
E [m].
Program (T) encodes the value of a strategy that is optimal in hindsight, i.e., strategy that minimizes the cumulative loss while ensuring that the constraints are satisfied expectation. In the following. we denote one such strategy, which is an optimal solution to Program ( as x² E Ak. Then, for sequence of losses lI.T, the (cumulative) regret over the T rounds is defined as
T
Σ aT - OPT((, (g))ie(m) = = a Ee.or - t=1
Ri (e
Remark (On the regret definition). Differently from the standard MAB framework (Lattimore and Szepesvári 2020 in constrained settings an optimal strategy x² may not coincide with vertex of the simplex Ag. iee. an optimal action may not exist. This is intuitive since, whenever the action associated with the smallest loss in hindsight does not satisfy the constraints in expectation, an optimal strategy x² may play that action as much as possible, while satisfying the constraints in expectation. This is the reason why the regret Rr((er)) is defined with respect (randomized) strategies, rather than actions. This defimition is standard in constrained online learning settings (see, e.g. (Efroni et al.) 2020 Pacchiano et al. 2027 Bernasconi et al. (022
In this paper, our goal is to design learning algorithms for constrained MAB settings that achieve small- loss style regret bounds of the form (r(E)T) S ōlvE Ei=1 CTTx.)) where Σ eg x= represents the cumulative loss incurred by a strategy x= that is optimal in hindsight. These regret bounds are arbitrarily better than common ((VT) regret bounds when x' outperforms other strategies on the sequence of losses fi.,, while being equivalent them in the worst case. It well known that small
loss regret bounds can be achieved in unconstrained MABs (see, e.g., [Lee et al., 2020a ) but it remains an open question whether they can also be derived in constrained settings.
In constrained MABs, a fundamental challenge is the fact that the learner must account for constraint violations during learning. Our primary focus is on satisfying the constraints at every round with high probability. However, we also derive some results for the weaker goal of minimizing cumulative violations, as a preliminary step. Next, we formally introduce these two goals.
2 Giien E N. we denote by [n] the set {l.... n of the first n natural numbers.
2 In this paper. we use the notation c(i) to denote the i-th element of vector c.
Mannor et al. (2009) show that if both losses and costs are selected adversarially, no algorithm can simultaneously achieve sublinear (in 2') regret and sublinear (in I') cumulative constraint violation.
3

---

Soft Constraints In this setting, the goal of the learner is to minimize the (cumulattve) positive
constraint violations over the T'' rounds, defined as VT [ Σx [g x a:] ai]" where
we let [-] == max -0. Intuitively, Vr represents the total constraint violation accumulated by the learner during the learning process, and it also ensures that negative violations (i.e.. constraint satisfactions) do not cancel out positive ones. The goal is to guarantee that VT = o(T)
Hard Constraints In this setting, the goal of the learner is guarantee that g, 2e S aq for every constraint i E [m]] and round t [7] with high probability This objective is only attainable under the following two assumptions, which are common in the literature on hard constraints settings (see,
e.g., (Pacchiano et al. 202T Liu et al. 2021 Bernasconí et al. 2022))
Assumption (Slater's condition). Program [ satisfies Slater's 's condition, i.e., it admits a strictly feasible solution x" E Δk, which is a strategy such that g x² < for every constraint i E [m]]
Assumption 2 (Knowledge of strictly feasible strategy). The learner knows a sstrictly feasible strategy x := arg max minke[m (a; - g x] and its associated cost 0, == g, x We denote by p E [0, 1] to margin by which x² satisfies the constraints, formally p = minig[m] [a; 0,l.
Intuitively, Assumptions T and are necessary to ensure that, in early rounds when little information is available, the learner has sufficient exploration opportunities without violating the constraints.
3 Being Safe While Learning With an Increasing Learning Rate
We begin by presenting two core components of our algorithms presented in Sections and 5 The first one is safe decision space, which is restricted set of strategies used to control constraint violations. The second component is OMD with log-barries [Lee et al. (2020a], which is an existing algorithm that achieves data-dependent regret bounds in unconstrained settings and serves foundation for our algorithms. The goal of this section is to show how these two components can be combined to achieve data-dependent regret bounds while controlling constraint violations.
3.1 Costs Estimation and Safe Decision Spaces
Estimating costs is a crucial task for any algorithm operating in constrained MABs. However, using these estimates in order to control constraint violations may not be trivial. Next, we describe the approach used by our algorithms. In the following, we let (a) = Σ 1 (a, be the number of rounds up to i. E (T) in which action a E [K] is played. Then, an unbiased estimator for the cost of
constraint i E [m]] when playing action a E [K] is (a) = max max{[I.N.co] Ere(g) [a)((a){aa,=)))) The following result quantifies the uncertainty associated with the estimator above.
Lemma 1. Let 8 E (0, and (a = min { 1, (TKm//)/mmx(( No(a) for E [K]. Then, with probability at least 1 5, (a) - 9:(a)) S Be 8) for every t E [T), i E [m], [K].
This above lemma is a trivial consequence of Hoeffding's 's inequality and a union bound. We denote by He.5 E [0, 1|Kk the vector whose entries are the estimates (a, while we let (d) E [0, 1jx be the vector of the bounds 3e (a, 8). For clarity, in the rest of the paper we omit 5 from the argument of (8))). Moreover, we denote by (6) the event defined by Lemma] which satisfies (() 2 1 - 8.
*Let us remark that, in the soft constraints setting, we are interested in obtaining small-loss bounds only for the regret. Indeed, small-loss bounds naturally belong to adversarial settings, as they become vacuous in stochastic ones (recall that constraint costs are stochastic in our setting). Moreover, an optimal-in citimal-nnhinndsee -i-hindsighht strategy x² satisfies the constraints in expectation, by definition. Thus, it would not make any sense derive small-loss bound for the cumulative positive constraint violations Vr.
"A constraint E [m]] is satisfied at é E [T] whenever its cost is below ai in expectation over the randomness
of the strategy 2i and the cost gt. i. This is standard in constrained MABs (e.g. [Pacchinno et al. (02T)).
7 'Previous works (see, e.g., [Pacchiano et al. 2021 Liu al. 2021 Bernasconí at [002 ) usually assume to
know a generic strictly feasible strategy. For ease of presentation, in this work we assume to know a strategy that satisfies the constraints as much as possible. Nonetheless, our results can be generalized to the case commonly considered in the literature.

---

Safe Decision Space Lemmal 1 provides some confidence intervals for the estimated costs. Next, we describe how these intervals can be used define a sequence of sets, called safe decision spaces, which contain strategies that an algorithm can employ to control the cumulative constraint violations, that is, attaining V1 S Õ(VT). Formally, for every round E
[T], we let
S: = (z E Ax (0t, -,)² S a; Vi E [m]]
be the safe decision space at time This definition is standard in the constrained MAB literature. Intuitively, an algorithm that selects strategies from St ensures that, with probability at least 1 8, the expected (optimistic) incurred costs remain below the thresholds at every round & [2'] and for every action E [K] and constraint i E [m]. It is easy to see that this holds thanks to Lemma and the way which the safe decision spaces are constructed.
3.2 Data- Pata-Dependent Bounds via Increasing Learning Rate
Next, we recall some needed details of the OMD with log-burrier algorithm by Lee et al. [0200a] This algorithm achieves small-loss guarantees unconstrained MABs, with a regret of O L*) with high probability, where L is the cumulative loss of an action that is optimal in hindsight. The algorithm works as standard OMD with log-barrier regularization (1(2)) Σx
In (where a(a)
ne.a
Dec (t.-) is the Bregman divergence built given (i), where At is an increasing sequence of learning rates. Specifically, each time the probability of selecting an action goes below certain threshold, the learning rate is increased by constant factor, while the threshold is increased. This procedure key achieve the desired data-dependent regret bound. One of the main technical features of OMD with log-barrier is its restricted decision space. Indeed, differently from most of the OMD>-like algorithms, is only allowed select strategies belonging to the truncated simplex, which is defined as Ω ;= {ar E Ax xx(a) 2 1 Va E [K]] This design choice avoids forced uniform exploration, and remarkably simplifies the analysis.
3.3 A Truncated Safe Decision Space
Our algorithms, presented in the following sections, rely on combining an OMD with log- barrier sub-routine with safe decision-making This raises some challenges, since both components put some restrictions on the space from which strategies are chosen. In particular, OMD with barrberrier requires selecting strategies from the truncated simplex Ω2 while safe decision-makin involves choosing strategies from the safe decision space S. Unfortunately, these two sets may in general be disjoint. Our algorithms implement procedure that enables these two elements to work together. Specifically, at each round E [T', they employ a larger safe decision space Sy which is defined as:
K Vi E [m]]
S = x E AK: ( B,) a
This decision space is strictly larger than the safe decision space Sz.
The following lemma characterizes the decision space obtained by intersecting Ω and St: the truncated safe decision space.
Lemma 2. For every E [T], let St 22 n St be the intersection of the truncated simplex and the safe decision space. Then, under E(8), it holds that (ee(r]S, is non-empty.
The above lemma can be proven by showing that any x E A that satisfies the constraints in K expectation included in Si. Moreover, ||æ: T||| < 7,, where Thus, क belongs to both Ω and ST- Additional details can be found in Appendix C Intuitively,
arg min Q
| xx ||
Lemma 2 states that, with high probability, every round E [T] there exists strategy satisfying both the requirements of OMD with log-barrier and a "suitably-relaxed" safety condition.
Warm-Up: Small-Loss Guarantees in MABs with Soft Constraints
As preliminary step toward our main result for the hard constraints settings. we design an algorithm with small-loss regret bound for soft constraints settings. Although these settings are technically easier than hard constraints ones, our algorithm incorporates some key components that are also central to the algorithm for hard constraints settings designed in Section Moreover, the algorithm may also be of independent interest for other learning settings with soft constraints.
5

---

Algorithm COLB
Require: Learning rate vj > 0, confidence E (0, 1), thresholds {as (etm)
1: Define increase factor A +- eInT
2: Initialize 21
1 h1,a 2K, M1o for all [K], 91.e + 0 for all E [mm) 3,
3: for t E [2'] do
4: Select action dt att
5: Observe loss fe(aa) and constraint costs (r.:(ae) Vi [m]]
6:
Update 9t,, and 33 described in Section 3.1 Compute safe decision space Si as described in Section 7:
8:
Compute the truncated safe decision space Se Q
9:
if S. is not empty then
10:
Compute ({(a) < (1(0)((umma] Va E [K] 2x(a)
11:
Lc++ + arg min, &s Du. (2, æt), where ve(x)) Ex 1 In for [K] do
me. z(e)
12:
13:
if *1+1(0) 14, then
14:
h141. + z++1(a)" M1+1aa t n1,ak
15:
else
16:
het1a + he Met1. +
17:
else
18:
Select strategy m141 Ω randomly
4.1 The COLB Algorithm
Algorithm 1 provides the pseudo-code of Constrained OMD with Log-Barrier (COLB). At high level, the algorithm implements the combination OMD with log-barrier and safe decision spaces introduced in Section Indeed, Algorithm i conceptually split into two main blocks. One block contains the set of instructions necessary to control constraint violations, highlighted blue. The other block, highlighted in green, defines the OMD with log-barrier sub-routine. Algorithm first defines a factor that is employed to increase the learning rate Th.a for action the probability of choosing the action falls below certain threshold h4,a (Line Tp. At each round, after playing an action and observing some feedback (Lines 5). the algorithm updates empirical means and confidence bounds for constraint costs (Line 6) Then, it builds the truncated safe decision space Se (Line 8 as described in Section 3 If this set is not empty (Line then an update of OMD with log-barrier is performed over S, (Lines 10 11). Moreover, the probability specified by computed strategy is too small for some action E [K]. i.e., 1/m411(a) > Irr,a. then the learning rate T),a is increased by a и: factor and the threshold increased to 2/mes((a) (Line 13 16). Finally, if S, empty,
then strategy is sampled randomly from the truncated simplex (Line 18
In the following, we provide the theoretical guarantees attained by COLB, starting from constraint violations.
Theorem 1. Let e (0, Then, with probability at least 28, the COLB algorithun suffers cumulative positive constraint violations VT S 2 (VKTIn (TKm/8)
The proof of Theorem relies on Lemma] 2 and it can be found in Appendix The bound provided in the theorem matches, up to constant factors, the lower bound provided Theorem of Bernasconi al. 2022].
We are now ready to prove the main result this section, which is small-los regret bound for COLB, This is stated in the following theorem.
TIn(H/s), (T((111)) / K/ a in(/)) }. where H == Theorem 2. Let 8 1) and = min 1/40H
In (Iau(T)1331m((7110)) Then, with probability at least - 48, COLB suffers a cumulative regret that can bounded as (r(E))) 2ō (V -T ej
In (1(()))

---

Theorem is proved by noticing that, even though the strategy update of Algorithm ! works on changing decision spaces St, projecting does not prevent the OMD sub-routine from guaranteeing small-loss bounds. The proof can be found in Appendix C.2 Some remarks are in order.
Remark 2 (Tightness). The bound in Theorem is tight, up to constants and logarithmic terms. Indeed, Theorem 3 of Gerchinovitz and Lattimore 2016] provides a regret lower bound S ( in unconstrained MABs, where L. is the total loss of an optimal-in-hing iit--iiiihhhhh action. The bound in Theorem 2 scales with the total loss of an optimal innaal-i---iae in-hindsight randomized strategy x'. However, optimal action,
since in unconstrained settings an optimal (randomized) strategy is as powerful the lower bound of [Gerchinovitz and Lattimore 2016 carries over to our setting as well.
Remark 3 (Knowledge of Σ f, x*). Assuming knowledge of L' to the learning rate is
standard in the literature on small-loss bounds. As discussed in Remark of (Allenberg et al.) 2006) and Remark of [Lee et al.) 2020ay. a doubling trick can relax this requirement, while ensuring that the regret bound does not deteriorate. This procedure is described in Appendix C.3 of (Lee et al. 2020b]. In our case, we require that 2x=1 L x² is known, instead of L'. However the considerations made for L still hold, and our algorithms can be made adaptive w.r.f. this quantity.
5
Data-Dependent Guarantees in MABs with Hard Constraints
This section is entirely devoted to the main contribution of this paper, which is an algorithm that achieves (tight) data-dependent regret bound in constrained MABs with hurd constraints. The section begins by introducing the algorithm, which builds on the COLB algorithm introduced in Section for soft constraints. After proving the guarantees attained by the algorithm, the section ends by proving a lower bound demonstrating that the regret bound of the algorithm is tight.
5.1 The SOLB Algorithm
Algorithm 2 provides the pseudo-code of Safe OMD with log-barrier (SOLB). Notice that the algorithm takes additional inputs compared to COLB. Specifically, it takes as inputs strictly feasible strategy, i.e., a strategy x E A as defined in Assumption 2 and its associates costs {0, he)))
Algorithm 2 highhlghht in pink its differences with respect to Algorithm [ COLB and SOLB is that the strategy chosen by the latter is not readily the selected through the OMD update. Specifically, at each round t, SOLB plays a convex combination between the strictly feasible strategy x given as input and the one selected by OMD, denoted Φ., The combination factor Tt. is chosen in an adaptive way to guarantee that the resulting strategy o, satisfies the constraints with high probability. Intuitively, the combination factor 7, weights how safe is to play the strategy computed by OMD rather than the strietly feasible strategy. If the strategy 2g produced by the OMD update satisfies the constraints with high probability, then Yt is set to zero, and the algorithm selects strategy Et A larger 7/2 weights more the strictly feasible strategy x than Tt In the first rounds, since confidence intervals for cost estimates are large, 7t' strictly greater than zero, while, as the confidence intervals become smaller, "/t approaches zero. As in Algorithm [ when the truncated safe decision space not empty, the algorithm runs a step of the OMD with log-barrier sub-routine. Then, a new combination factor is computed (Line 19). On the other hand, if the truncated safe decision space is empty, then ?t. is set to one (Line 23). and the algorithm thus selects the known strictly feasible strategy. In Figure i in Appendix A we provide a graphical intuition on how æ, is selected when K-
The key difference between
5.2 Theoretical Guarantees of SOLB
In this section, we provide the theoretical guarantees attained by SOLB. We start by showing that SOLB satisfies the constraints at every round with high probability.
Theorem 3. Let ó E (0, 1). With probubility at least - 6, SOLB guarantees that g xx S oz holds for every constraint [m]] and round E (T].
Theorem 3 can be proven by analyzing the behavior of the combination factor Tr. We show that Tt. is large enough to compensate the violations potentially suffered by the strategy a++1 computed by the OMD update. Specifically, "t = 0 when T4+1 satisfics the constraints with high probability.
7

---

Algorithm 2 SOLB
Require: Learning rate > 0, confidence parameter E (0, 1), thresholds [as) strictly feasible strategy
x² E Ax with its associated costs (0:)ae[m) (see Assumption
1: Define increase factor 8 e
2: Initialize 31
1 Pr,a 2K, mh, + for E (,. for all E [m]] B t
3: Initialize
ma 1-0:
1-01
4: Select
7oo="" + T1
5: for i E [T] do
6: Select action di Zt.
7: Observe loss (e(as) and constraint costs Ir,; e [m]
8:
Update G.., and 33 described in Section 3.1
9:
Compute the safe decision space St as described in Section 3.3
Compute the truncated safe decision space & - n
11:
if S, is not empty then
12:
Compute (((a) (o)ma) Ya [K] 21(e)
13:
ē1+1 <- arg min E, Dv, (x, wi), where (xx) Ede In for
14:
[K] do
15:
if
((41(0) he, then
16:
1441, (a) M,+1aa <- 1/t
17:
else
18:
11,1, ha 11+1o <
19:
Compute the combination factor:
min (Ca,, (8,)) ( R. 1.:1 if & holds
ta maxiEM
(i. :B,) 0141.1)-0,
otherwise
20:
where M {i E [m] ( + =
x1+1 a.j = i [m] (.., + Ta > a.}
22:
Select strategy Æ++1 Ω randomly
23:
Set the combination factor to +-
24:
#141 +- 7x20 + (1 - Fe41
Otherwise, "Y is proportional the pessimistic violation that T441 would suffer. Assuming that x is strictly feasible implies that ? < in every round in which the truncated safe decision 1-a: space non-empty. To see this, notice that 7 S maX4e[m] I-0, S max I-actp Thus, minimum amount of exploration is always guaranteed. When the truncated safe decision space is empty, the algorithm uses the strictly feasible strategy.
1-ay
We now analyze the regret suffered by SOLB. Before presenting main result, we introduce some technical lemmas that are useful to understand the nature of the regret bound.
Lemma 3. Let E 10 and 2 12K T
Then, with probability at least 28, SOLB satisfies:
K
(x====))) (xx)=x))) mx))²
KTm
K p
KTm
(G((TT)) 50
e (x:-
+
In
(2)
p
where (p(.))))== M- (xx - x²).
Intuitively, the above lemma states that the regret accrued by the strictly feasible strategy, when weighted by the combination factors, is not large. Specifically, the term that appears in Equa- tion (2) is the scaled Euclidean norm of the sequence of instantaneous regrets suffered by x This quantity represents some sort distance between an optimal strategy and the strictly feasible one. At the end of this section, we provide discussion on the role of this quantity, showing that it represents source of complexity for the problem instance.

---

Lemma 4. Let 8 E 10. and n S 40H in
where H = In (Ilu(T)) (//())/))) Then, with
probability at least 26, SOLB satisfies:
( K ? RT(()T) 0
Kn
1 ④
T Σ
T 7
x In (7) )
+
E
ll
e xt In
11
t=1
p
t=1
where R1 = 1 7- (it x²).
Lemma A provides an upper bound on the regret accrued by the strategy proposed by OMD, when weighted by 1 - T/.
- The bound seems involved. However, the terms we are more interested in are the second and the fifth, which dominate the other ones. In particular, we highlight how the quantity (fr:)) is bounded by sum of the total loss of the strategy played by SOLB and the total loss of the optimal strategy. This provides a link between the total loss of the strategy proposed by OMD, the total loss of the strategy that is actually played by SOLB, and the total loss of the optimal strategy. Keeping in mind that our goal is to obtain a regret bound for SOLB that scales with the latter, Lemma plays a key role in the final result. The proofs of the lemmas are in Appendix D.I
We are now ready to present our main result, i.e., a high-probability regret bound for SOLB.
P Theorem Let 5 E (0, 1), p 2 12K, and r = min 20 Im V /K/ET_1 f m in(1/6) where
T,
H = In (1T))1)1 Then, SOLB suffers cumulative regret bounded as:
K (1/()))
T
T
)
(r(()r)) 5
Σ
c (x
- x²))
K
e x In
(3)
8
P
(A) Safery Compiexity
(B) Bandit Complexity
where Ô hides universal constants and logarithmic terms not depending on 6.
Theorem 4 is proved by decomposing the regret in the quantities analyzed in Lemmas 3 Jand 4
By construction, 3t = 72-120 + +(1 (1-7t-)) which implies (e1r)) R2 (f1:r) + (brr)) Thus, we can sum the upper bounds presented in Lemmas 3 and 4 Finally, noting that, by definition of it _ holds 2 >Σ= e x; S Rt + p >T= e, x=,
solve the deriving quadratic incquality in Rr, which yields Equation 33.. A detailed proof of Theorem 4 is in Appendix D.I. Theorem i one of the main results of this paper. It establishes a regret bound that depends on two contributions: the total loss incurred by an optimal-in-hinnn in-hindsight strategy (B), and the total squared difference between the losses of the strictly feasible strategy and the benchmark (A). This result provides a natural interpretation on the intrinsic difficulty of MABs with hard constraints. On the one hand, our bound scales as the performance of an optimal strategy, which is common to any small-loss bound in unconstrained MABs. We call this contribution Bandit Complexity, as it represents the complexity of learning independently of the presence of the constraints. On the other hand, we pay an additional term-peculiar of our setting-that encodes the distance between the benchmark and the strictly feasible strategy given as input to the algorithm. We call this contribution Safety Complexity, as it represents the complexity of learning an optimal feasible strategy while satisfying the constraints at every round with high probability. We acknowledge that the state-of fate-of-the-are art bounds in online settings with hard constraints are of order (T/oVT) (e.g., [Pacchiano al. 2021 ). Indeed, our bound not only improves the aforementioned result the best case, while being equivalent in the worst one, but it also decomposes the former in two quantities that are easily interpretable.
5.3 A Small-Loss Style Regret Lower Bound
In this section, we provide a small-loss style regret lower bound for the hard constrained bandit problem. In [Gerchinovizz and Lattimore 2016) the authors show that, in adversarial non-constrained bandit problems, the regret suffered by every algorithm is lower bounded as O(VL*), where L' is the total loss accrued by the benchmark. This term is represented, our setting, by the Bandit Complexity contribution. In our setting, the strictly feasible strategy x is crucial in defining how hard is an instance: in fact, Equation 3 shows that SOLB benefits instances where the optimum close (in terms of performances) to the strictly feasible strategy, which translates in a small Safety Complexity. This

---

behavior is natural as the strictly feasible strategy represents a starting point for the exploration, and the algorithm remains somehow tied to that. This raises the natural question on whether this double de- pendency, one on the optimal total loss and the other on the difference with the strictly feasible strategy, actually tight. The next two results bridge Theorem 4 with the standard literature results, i.e. regret bounds depending on T, and show that the performance of SOLB is optimal when disregarding logarith- mic terms. We start by introducing an important technical notion, that is handy in bridging constrained small-loss bounds and standard bounds depending on I only. We define the constrained small-loss
balls as B,, == ferr E [0, 10]1 Ei= a Swn
Σ Ei= (2, (x²
< <A²} The quantities
T
T
w. A E [0, 1] represent two different sources of difficulty for the learning algorithm: w express how difficult is the identification of the optimum in non-constrained bandit problem, and A represents the additional difficulty provided by the constraints satisfaction. The next result allows us to rephrase the regret upper bound provided in Theorem 4in terms of the constrained small-loss ball. In fact, it is a trivial consequence of Equation (3) and the definition of constrained small-loss ball.
Corollary 1. For all w E [0, 1] and for all E [0, 1), it holds Su E (( -
δ KA T 3 0 (WT) where the expectation is taken w.r.t. the internal algorithm randomization.
Notice that w and A can be treated as instance-dependent parameters, as they represent how far an instance is from the worst-case one, i.e. when those two are both equal to Finally, the next result shows that no algorithm can have a better dependence on the parameters w and A.
Theorem 5. Let K 2 2 max {2. (11 + T) (3) ) and E [1 ( 2 + InT) .]] Then for
every randomized algorithm, have supttreBB..a. (( 2 Ω ( ( VWT) where the expectation is taken with respect to the internal randomization of the algorithm.
detailed proof of Theorem 5 can be found in Appendix D.3 This result shows that SOLB achieves an optimal dependence on both A and w.
Finally, leave open question whether the dependence on the constant p in contribution (B) of the regret upper bound can be removed. Notice that p is a constant tied to the strictly feasible strategy and it encompasses the difficulty provided by the constraints to the instance. Thus, we helieve that the 1/p dependence should affect contribution (A) only and we conjecture that our lower bound is actually tight, while it the upper bound that can be lowered.
Acknowledgments
This paper is supported by the Italian MIUR PRIN 2022 Project "Targeted Learning Dynamics: Computing Efficient and Fair Equilibria through No-Regret Algorithms". by the FAIR (Future Artificial Intelligence Research) project, funded by the NextGenerationEU program within the PNRR- PE-AI scheme (M4C2, Investment 1.3, Line on Artificial Intelligence), and by the EU Horizon project ELIAS (European Lighthouse of AI for Sustainability, No. 101 10237).
References
Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire. Corralling a band of bandit algorithms. In Conference on Learning Theory, pages 12-38. PMLR, 2017.
Zeyuan Allen-Zhu Sébastien Bubeck, and Yuanzhi Li. Make the minority great again: First-order regret bound for contextual bandits. In International Conference on Machine Learning, pages 186- 196.194, PMLR, 2018
Chamy Allenberg, Peter Auer, László Györfi, and György Ottucsák. Hannan consistency in on-line learning in case of unbounded losses under partial monitoring. In Algorithmic Learning Theory: 17th International Conference, ALT 2006, Barcelona, Spain, October 7-10, 2006. Proceedings 17, pages 223-243. Springer, 2006.
Peter Auer, Nicolo Cesa- Bianchi, Yoav Freund, and Robert E. Schapire, The nonstochastic multiarmed bandit problem. SIAM journal computing, 32(1):48-77, 2002.
10

---

Qinbo Bai, Vaneet Aggarwal, and Ather Gattami. Provably efficient model-fiee algorithm for mdps with peak constraints. arXiv preprint arXiv:2003. 055555, 2020.
Martino Bernasconi, Federico Cacciamani, Matteo Castiglioni, Alberto Marchesi, Nicola Gatti, and Francesco Trovò. Safe learning in tree-form sequential decision making: Handling hard and soft constraints. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Reseurch, pages 1854-1873. PMLR, 2022.
Matteo Castiglioni, Andrea Celli, and Christian Kroer. Online learning with knapsacks: the best of both worlds. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 2767-2783. PMLR, 2022a.
Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Giulia Romano, and Nicola Gatti, A unifying framework for online optimization with long-term constraints. Advances in Neural Information Processing Systems, 35:33589-33602, 2022b.
Tianrui Chen, Aditya Gangrade, and Venkatesh Saligrama. Strategies for safe multi-armed bandits with logarithmic regret and risk. In International Conference on Machine Learning, pages 3123- 3148. PMLR, 2022.
Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanovic. Provably efficient safe exploration via primal-dual policy optimization. In International conference on artificial intelligence and statistics, pages 3304-3312, PMLR, 2021.
Yuhao Ding and Javad Lavaei. Provably efficient primal-dual reinforcement learning for cmdps with non-stationary objectives and constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 7396-7404, 2023.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploiaaiie in constrained mdps, 2020.
Aditya Gangrade, Tianrui Chen, and Venkatesh Saligrama. Safe linear bandits over unknown polytopes. In Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 1755-1795. PMLR, 2024.
Sébastien Gerchinovitz and Tor Lattimore. Refined lower bounds for adversarial bandits. Advances in Neural Information Processing Systems, 29, 2016.
Rodolphe Jenatton, Jim Huang, and Cédric Archambeau. Adaptive algorithms for online convex optimization with long-term constraints. In International Conference on Machine Learning, pages 402-411. PMLR, 2016.
Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial Markov decision processes with bandit feedback and unknown transition. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 4860-4869. PMLR, 2020.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Chung-Waz Weing-Weiii Lee, Haipeng Luo, Chen- Yu Wei, and Mengxiao Zhang. Bias no more: high- high-probability data-dependent regret bounds for adversarial bandits and mdps. Advances in neural information processing systems, 33: 33:15222-15533, 2020a.
Chung-Wes Wei Lee, Haipeng Luo, and Mengxiao Zhang. A closer look at small-loss bounds for bandits with graph feedback. In Conference on Learning Theory, pages 2516-2564. PMLR, 2020b.
Nikolaos Liakopoulos, Apostolos Destounis, Georgios Paschos, Thrasyvoulos Spyropoulos, and Panayotis Mertikopoulos. Cautious regret minimization: Online optimization with long-term budget constraints. In International Conference on Machine Learning, pages 3944-3952 PMLR, 2019.
Tao Liu, Ruida Zhou, Dileep Kalathil, Panganamala Kumar, and Chao Tian. Learning policies with zero or bounded constraint violation for constrained mdps. Advances Neural Information Processing Systems, 34:17183-17193, 2021.

---

Mehrdad Mahdavi, Rong Jin, and Tianbao Yang. Trading regret for efficiency: online convex optimization with long term constraints. The Journal of Machine Learning Research, 13(1): 2503-2528, 2012.
Shie Mannor, John N. Tsitsiklis, and Jia Yuan Yu. Online learning with sample path constraints. Journal of Machine Learning Research, 10(20)569-590,, 2009.
Adrian Müller, Pragnya Alatur, Volkan Cevher, Giorgia Ramponi, and Niao He. Truly no-regret learning in constrained mdps. In Forty-first International Conference on Machine Learning, 2024.
Gergely Neu. Explore more: Improved high-probability regret bounds for non-stochastic bandits. Advances in Neural Information Processing Systems, 28, 2015a.
Gergely Neu. First-order regret bounds for combinatorial semi-bandits. In Conference on Learning Theory, pages 1360-1375. PMLR, 2015b.
Aldo Pacchiano, Mohammad Ghavamzadeh, Peter Bartlett, and Heinrich Jiang. Stochastic bandits with linear constraints. In International conference on artificial intelligence and statistics, pages 2827-2835. PMLR, 2021.
Shuang Qiu, Xiaohan Wei, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. Upper confidence primal- dual reinforcement learning for cmdp with adversarial loss. In Advances in Neural Information Processing Systems, volume 33, pages 15277-15287. Curran Associates, Inc., 2020.
Francesco Emanuele Stradi, Jacopo Germano, Gianmarco Genalti, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Online learning in CMDPs: Handling stochastic and adversarial constraints. In Proceedings of the 41st International Conference on Machine Learning. volume 235 of Proceedings of Machine Learning Research, pages 16722-46721. PMLR, 2024a.
Francesco Emanuele Stradi, Anna Lunghi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Learning constrained markov decision processes with non-stationary rewards and constraints, 2024b.
Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Learning adversarial mdps with stochastic hard constraints. In Forty-second International Conference on Machine Learning, 2025.
Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Publishing Company, Incorporated, 1st edition, 2008 ISBN 0387790519.
Honghao Wei, Xin Liu, and Lei Ying. Triple-q: A model-free algorithm for constrained reinforce- ment learning with sublinear regret and zero constraint violation. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 3274-3307, PMLR, 2022.
Honghao Wei, Arnob Ghosh, Ness Shroff, Lei Ying, and Xingyu Zhou. Provably efficient model-free algorithms for non-stationary cmdps. In International Conference on Artificial Intelligence and Statistics, pages 1527-6570 PMLR, 2023.
Xiaohan Wei, Hao Yu, and Michael J. Neely. Online learning in weakly coupled markov decision processes: A convergence time study. Proc. ACM Meas. Anal. Comput. Syst. 2(1), 2018. 8. doi: 10.1145/3179415.
Hao Yu, Michael Neely, and Xiaohan Wei. Online convex optimization with stochastic constraints. Advances in Neural Information Processing Systems, 30, 2017.
Liyuan Zheng and Lillian Ratliff. Constrained upper confidence reinforcement learning. In Proceed- ings of the 2nd Conference on Learning for Dynamics and Control, volume 120 of Proceedings of Machine Learning Research, pages 620-629. PMLR, 2020.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract and introduction state all the main contributions made by the paper.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
All the assumptions are clearly stated in Section 2
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification: All the theoretical results clearly state their assumptions, while all their proofs are provided in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppp.ccppulli//uuuii wwwiiccgguie//eeeeeeee CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
15

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The paper conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed, since the work is mainly theoretical.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The paper does not involve LLMs as any important, original, non-standard components.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
19

---

Appendix
The Appendix is structured as follows:
Appendix
A
we provide a graphical representation Algorithm 2 update.
In Appendix
B
we provide the complete discussion on related works.
In Appendix
C
provide the omitted analysis for the soft constraints setting.
In Appendix
we provide the omitted analysis for the hard constraints setting.
A Graphical Representation of the Update of Algorithm 2
Ct++1
1t++1
11++1
Ø3 01++1
2:
(a)
(b)
01+1
3t++
2
(c)
Figure I: A graphical representation the update performed by Algorithm For the sake exposition, we omit the constraint xaa) 2 1/7, Va [K]. Specifically, in Figure ((a) we provide the graphical representation of the safe subset of the simplex. Notice that, the strictly safc strategy x associated to the Slater's parameter vertex of the simplex. In Figure [[b] we provide the graphical representation of the estimated safe decision space. Notice that, 2 lies on this set as prescribed by the projection both Algorithm and Algorithm
Finally, in Figure [[c) we provide how the convex combination is performed. Notice that, # is computed pessimistically. Indeed, due to the high uncertainty in the constraints estimation, 2 is an interior point of the safe space.
B Related Works
Data-Dependent Regret Bounds Over the last two decades, in the literature on (unconstrained) adversarial MABs there has been an increasing interest in providing regret guarantees that depend on the difficulty of the specific instance faced by algorithm. Such bounds are usually referred to as data-depente dependeennddntt bounds or instance-des mestance-depedeet bounds. Examples include, but are not limited to, small-loss bounds (also called first-order bounds). An algorithm enjoying small-loss guarantees has its regret upper bound scaling with O(VL.", where < is the total loss accrued by the benchmark. Small loss bounds over the expected regret have been obtained in several settings, from MABs to contextual bandits [Allenberg et al.) 2006 Neu 2015b Allen- -Zu et al.) 2018 Lee et al.. 2020b]. However, few works managed to recover small-loss guarantees that hold with high probability Neu 2015a Lee et al. (2020a]. The tightness small-loss bounds has been analyzed only recently. In particular, in [Gerchinovizz and Lattimore| 2016) the authors provide data-dependent lower bounds for adversarial MABs, showing that the O L*) rate cannot be improved.
20

---

Constrained Online Learning Online leaning with unknown constraints has been widely inves-
tigated (see, e.g., [Mannor al. 2009 Liakopoulos et al. 2019 Castiglion al., 2022a b)). Two
main settings are usually studied. In soft constraints settings (see, e.g., [Chen et al. (022 ), the
aim to guarantee that the constraint violations incurred by the algorithm grow sub-linearly. In
hard constraints settings, the algorithms must satisfy the constraints at every round, by assuming knowledge of a strictly feasible decision (see, e.g., [Pacchiano et al. 2021]). Both soft and hard constraints have been generalized to settings that are more challenging than MABs, such as linear bandits (see, e.g., [Gangrade et al., 2024)) and games (see, e.g. [Bernasconi et al., 2022 ). None of these works in the constrained online learning literature studies data dependen regret bounds. There also exists a huge literature on constrained Markov decision processes (see, e.g.. [Wei et al.
2018
Zheng and Ratliff 2020 Bai al.) 20200 Efroni al.] 2020 Qiu et al.) 2020 Ding al.
2021
Liu et al. 2022 Wei et al. 2022 2023
Ding and Lavaei| 2023 Stradi et al. 2004bb Müller
al.
2024 Stradi et 2025 2024a]). Most of these works focus stochastic settings, and none
of them provides data-dependent regret bounds. Finally, some works focus on constrained online convex optimization settings (see, e.g., [Mahdavi al., [012 Jenatton al. 2016 Yu et al.) (017)). Nonetheless, they do not provide data-dependent regret bounds.
C Omitted Proofs for Soft Constraints
C.1 Non-Emptiness of the Truncated Safe Decision Space
Lemma 2. For every E [T), let St 22 S be the intersection of the truncated simplex and the safe decision space. Then, under {6), it holds that Ove[T]S non-empty.
Proof. Consider feasible strategy x", namely, 9 x s aa for all i E [m]]. Under the event { Cemmaaiimplia
- 3.) x S as, vt E (T].
Notice that, since x" is feasible, the aforementioned reasoning still holds for the constrained optimal solution.
Then, notice that for any æ E Δx, there exists strategy ã E Ω s.t. - æ111 S K T Thus, employing the reasoning above and taking:
arg min ||+ x0111. aen
we have, for all i E [m] and for all t E [T]:
@ - B,) T
(gt. B,) (w + x²)
(gr.; B,) T x + +@i. -B,) TT xx²)
S 0 + - 20111
K
$ a4 + T
which holds with probability at least 1 - and implies that St is never empty. To conclude the proof, notice that:
n
S, n
(SNS))
tE[T]
(E[T]
QN
n
S
kE|T]
Noticing that, by Equation (4) and employing the same reasoning above, it holds;
i E 0 S,
eE[T]
concludes the proof.
21

---

C.2
Cumulative Regret of COLB
Lemma S. For any å E (0, 1), for any s. a E ( Algorithm
guarantees the following
bound:
T Σ
I
T
h
(at - u) S 50
Σ Es(ar)
10
tm1
with probability at least 1 1-60 5.
Proof. We fix s.t. u O that is, any possible vector belonging to the intersection between the safe sets built by Algorithm!] [
Then, we apply standard OMD with log-barrias results
(see [Agarwal et al. 2017) to obtain:
Σ
le a u)
(u, Da, (u, m(41))
na (a) (a).
(5)
The result above holds since S; is polytope (thus, convex) for any E [7]. As S, is included in Ak. then the intersection convex. Moreover, we notice that, by Lemma 2 least - 6, that ( is non-empty, by construction of the estimated safe set. Equation (5) holds under the event mentioned above.
we have, with probability at
For the last term of Equation
we simply notice that, for any E [T], holds:
(2)
nt (a) (a) = n,,021 (a)
(a) 1fa: = a}
Me, el (a(e))
ne, la(
I nr, le(ar)
where the last inequality holds since 17,, = xm Ma.a where n. is the number of times Algorithm) increases the learning rate for arm a, and nm S
In the following, we define h(y) y In y. Thus we bound the first two term of Equation as follows:
Σ (Der (u, Øt) Dws, (u, xl+1))
< D (u. (1)
+
D Pers (4,1) Dan, (u, m(41))
(6)
1=1
u(a))
h
1/+1,a
Mt.a
Fe+1
where Inequality 66 holds since the Bregman is always greater equal than zero.
Thus, we focus on the first term, bounding as follows:
u(a)
K Σ
In(Ku(a))
(7)
1)
21 (a)
K In
(8)
where Equation holds since æ. is initialized uniformly and Inequality ( holds since u(a) 2 1/T for all a E [K].
To bound the final term, we will refer as tu to the last time step where the learning rate of arm is increased. Thus, we proceed as follows.
u(a)
1-kn K u(a)
h
11,+1a
It, 1
kmim
1 (a)
22

---

ula)
+1y+1(a)
5x) In T u(a)/rr.a
5m In
u(a) 2
a(o)ATT. +1
In
5ry In 7
u(a)/T..
5r) I11 T
where we used that S - In Combining the previous bounds concludes the proof.
- and ula
11)) S T.
2
Theorem 2. Let ô E (0,1) and y min (1AO V <//E_, a in( [[("=(((/ J. where H In (((()))(33m((())1))) Then, with probability at least 1 - 48, COLB suffers a cumulative regret that can be bounded as Re((err) o (VKE af In (1/6)
Proof. We first decompose the regret follows:
Rr
Σ
l (xt x²)
1=1
T
Σ l (x:: - u) + Σ (Ce l.)) Bt +
E -x) TT)TTu=
uu > eg (u-wa) x*)
T
T
T
< e (x: -u + Σ (le - (.) at +
Σ (ee Lx) t=1
u + K,
t=1
t=1
where we take u as min after noticing that, under the event of Lemma 2 which holds with probability at least 1 6, the maximum & distance between the safe optimum x and u is K/T.
m ||2
2111 and the inequality follows from the Hölder inequality
We will bound the remaining quantities separately.
Bound on the first term The first term follows from Lemma
Bound on the second term sequence, where any difference is bounded
To bound the second term we notice that it is a Martingale difference
T
E,
C
E.
x
I max
Ee
Øe,
Er,
Lg
(((a)
max
Ir (a)
1:at
aa,
Ee
[e
xz((a)
<
1.
Similarly, we bound the second moment as:
27
((e, Ee
2
E2
E,
ē.
E,
x
E,
xt
<
E,
2 xc
e
Zt..
23

---

Thus we can apply the Freedman inequality to attain, with probability at least 8:
(1
T Σ
T
(1)
(
(e, E.) TT 00= t=1
Σ
lg my In
Bound the third term To bound the third term, again notice that the quantity of interest is a Martingale difference sequence, but we apply a modified version of the Freedman incquality (see [Lee et al. 2020a))
First we notice that:
(ee (e) u h E [1,
We now focus on bounding the second moment as follows:
E2 ((e.
(x) TTTT 2
S Ex
27 l
((a)))²
xa(aa)
u (a)e((a)).
S h f, u.
Thus, with probability at least 6, we have by Theorem 2.2 of [ee al. 2020a
T E 2x) u 11
(
T
>e 1=1
e
un
H
2h In
H
8
t=1
where [Iog(T)] [3 log((T)
Final result Combining the previous results and applying Union Bound, have, with probability at least 1 - 35:
Pr 5o
K
In
+
T
le(az)
hTuu
o
(12
Ee
Σ eg xe In
T
( In
11
10n T
T=1
H 8 Σ e u u in (M)
)1)
H
H
+ 2h u In
(
Now we notice that, applying Freedman inequality, it is easy show the following bound:
T
T Σ e x. In
(1) In
Σ
(a.)
Ee
a. 2
5
T=1
t=1
which holds with probability at least and implies, by AM-GM inequality:
Σ ((a)) < > e, + 2 (t)
T
1=1
Now, going back to the regret bound, it holds, with probability at least 1 - 48, by Union Bound:
Ry 5
KlnT T
+ 7n Σ e œ. + 17 (2))
T
hTu
+0
Σ
T
e x, In
(7))
8
+
10n In T
1=1
1=1
24

---

H
+ H
Σ
e h u in
+ 2h u In
8
t=1
K In T
1
(1)
hT
0
11
In
8
Σ
e ae In
88
10n In
20H In T
T
(H)
+
Σ
eg u
hfun in
(5)
+ 2h u In
20/4ln' In?
K I
1
(1)
h
00
l + In
e In
11
10n In
1=1
H
H
H
+ +100H
In T
L
uln
h + 2Hh In
(9a)
n IT
8
1=1
Knn
+1
T
e 2
+ In
1
+
Σ
T
e
az In
(5)
8
11
1=1
T
+
+160H In
Li u
In
(9b)
K
1 + Σ
(
<
0
+ 1)
e 84
Σ le xc In
l
u In
9
K
T Σ
T Ee xe In
1 11
T
1
+
ej
vt.
+
e x
In
(9c)
7
1m1
t=1
where Inequality
9a holds by AM-GM inequality, Inequality
9bb holds for S
and
10H la T In #
Inequality 99 holds after noticing that by definition of Σt= e, u S ΣT eg x² + K. Since
7 S 2. we have:
T
e wi S
Rr + 17
x7 x
2
1=1
and the regret can be rewritten as:
T
T +
2K
RT < δ
+ 2
2
Mr
+ 11
Σ 1=1
eu xr
In
4n
e
x
2
We then set 1) min
K Σi= 2. x In(3)
and we solve the quadratic inequality in
401f In T (3))
Rr, obtaining the following regret bound:
(1
T
RT δ
K >
l x In
-
1
1=1
This concludes the proof.
C,3
Cumulative Violations of COLB
Theorem 1. Let E 10, Then, with probability at least 25, the COLB algorithm suffers cumulative positive constraint violations Vy S O [VTTlu (TKm/8)
25

---

Proof. First, we underline that the following analysis holds for every constraint E [m], including the one being violated the most, i..,, i E arg ma E
9 x -aal
By Lemma we have that, under the clean event, 2t E S. By construction, this implies 10,- 11-1) T 2z S a, + for every t [2]. Employing Lemma
| we get, under the clean event:
K T g az ai]*
+ 2B,
To bound the second term we proceed as follows:
T
T K
3
1t
(c-1())))(a)
1=1
1=1
B ((-1(a)1((o) + 2 1og
(10)
1= o=1
TKm
T
Le(a)
4ln
max N 1a))
t=1
TKm
S 3
4ln
NT (2T1n(--1)
(11)
8
(TKm))
S 4KT
2T In((")))
(12)
where Inequality (10 follows from Azuma Inequality,with probability at least 6, Incquality
holds since EtT vi 3vT, and Inequality (12) from Cauchy-Schwand Inequality and the fact that
EK (T(a)= = T.
Finally, it holds:
VT
9: St ail
t=1
K
2,0 2,
(TKm)
< K +3
4KTln
( + 22T1n(8-1).
Employing Union Bound concludes the proof.
D Omitted Proofs for Hard Constraints
D.1 Cumulative Regret of SOLB
Lemma 3. Let E 10 and 2 12K T Then, with probability at least
25, SOLB satisfies:
KTm )
K p
Σ (x (x - x²1)² ((=x==xx))
KTm
K p
(9 50
+
In
(2)
where (EI.T = ET 1- (xx x²).
Proof. We first split the round two sets Ti, T2. Ti encompasses the rounds [T] s.t. 7-1 S 1/22. Th the remaining rounds.
26

---

Bound in Ti
We apply the Schwarz inequality obtaining the following bound:
Σn-ll (x - =0)=
Σn x2-
Σ
Σ MET
e (x - xx1) -000=)x))))
tET1
METI
Σ
Σ
e (2+ (x0))
BE
We will now focus on the bounding the sequence Σien R--1. We proceed follows:
min (g) + 3 T 3t, 1] a;
Σ
2
Σ
max iEM
min 91-1, + 3 T Zz 1} 8
IE
tET1
91-1 + + 1t 03j
max iEM
9 9--1, + B(-1)
0
TE
5 Σ
2/3 t-
T2 + P
K T
LET,
Σ
2
2/ -
Zt
2K
P
p²
IET;
where the second inequality holds by definition of and by Lemma ! with probability at least 1 Thus we bound the following quantity:
Σ tT
2(1 71-1) )²
TT
[ ( x0 )²
K
41n(TKKm/))
Nax(11NN-11aa) ()(a)))(()))))))))))){)))
4ln(TKk/0))
4K
V max [1, (N)) (2
T
K
$ K166)(TKm//)
max (1, N, (a)} Te(a)
t=1 a=1
T
K
sn(a) (a)
1,(a)
K166n(TKm/8)
N
max(1, 1
1=1
where the first step holds since 7-11 S 1/2. We can bound the second term as:
T
1,(a) max Nz < K
ΣΣ
1
3K + 2K IT().
1=1 a=1
To bound the first term notice that it is martingale difference sequence in which any martingale difference is bounded by 1. Thus, we proceed as follows:
K
(a) - I,(a) max (1, N,
27
K (a( - (a 27
E,
<
E,
max N1
a=1
27

---

K
Ex [(ra(a) [
max max N2
K
2x(1a) - 21(a))
K
max (1, [
K
IT(a)
$ K
and we apply Lemma 9 of [Jin et al.
2020 with À = 1/2K to obtain, with probability at least 8:
xz (a) (.(a)
Iz(a)
Σ
S
max (1, (1, 2K +2Kln(11 In(1/6).
max (1, N2-1(a)
Thus, employing a Union Bound, we obtain, with probability at least 28:
Σ BEI,
((_1
96K In(TKm/5) + 128K In (TKK/m/))
and similarly:
Eni5 p²
768 k² Ln(KKm0))
1024
K² In (TK(/mm/0) 2K²
0²
p²
To conclude, we have, with probability at least 1 22:
-h- eg (x x²)
T
e (x) -x-) 2
Σ
xa))
IET1
768
1024 K2 IT(TKm/5)+
K2 Im 2 (TKK//m)))
2K² p²
Σ
L T
(x - -x+))
p²
p²
43K (T(Km/8)))
T
(100-wx)))
P
Bound in Tg
We first apply the Hölder inequality to obtain the following bound:
Σ n- (a: x²)=
T-1-
GET
tET,
To bound the aforementioned terms, upper bound the cardinality of the set T2. This is done by first bounding the cardinality of the following set:
K T3 (T):
p²
E0-1()))
2
8
a=1
From the definition we can state the following lower bound:
K
B (a)1 2 73g p² 8
ΣΣ
LET, a=1
We first bound the quantity ΣIeTs Σ
Br (a)) similarly to what done in Theorem
as:
TKm 8
Σ
( 3
4K| In
tET a=1
28

---

which holds with probability at least 1 - 8. Combining the previous bounds, we obtain:
p²
TKm
T3
3
4K T3l In
which implies:
2304
TKm
T3l S
K
In
Ø²
Thus, employ the reverse Markov inequality bound the probability that E T2 O T3. First lower bound the following quantity:
K
E2
Σ
B
(a)
-T_122 1z
(1 7t- 7t-1) 11)
1
B
1+ p
1² pk
T
82
6
where the last steps hold since:
1 - ag
7- max mm(m]
max E fml
0g
ai
1 1+p
0 ,_ 2 T
K when E T2, under the clean event and for >
12K
We can now employ the
I
reverse Markov inequality to state:
K Σ
(a) 2 8 F
2
2
24
Employing the equation above we can state that:
2304
TKm
p²
In
[Ta
T2l.
pa
24
from which:
55296
TKm
722
S p
K
8
To conclude, we have, with probability least 1 8, the following bound:
55296
TKm
Σ Tn-ele (x xx)) <
Σ
7-1 [22|
K
In
BET2
LET2
Combining everything Considering the quantity of interest, we have the following bound with probability at least 1 - 26 by Union Bound:
7t l, (xx- - -x")= Σ
En-el (x=
1x - -x")+ + Σ 1- (x: - xx")
LET,
IET,
43K (TK/00))
T
e (xx - -x²1)²
55296 +
TKm
K In
P
8
1=1
This concludes the proof.
29

---

Lemma 4. Let 8 E (0. and n S 40H in
where H = In
Then, with
probability least
26, SOLB satisfies:
Kn
T
In ())
T +
(1) )
(CLT))) - 0 +
e
+
In
+
Σ
e x
"ee x In
17 1=1
P
8
P t=1
where RT(L):T)= Ei=(1
)eg
(3:
x²))
Proof. Similarly to the analysis employed to prove Theorem as follows:
2 decompose the quantity of interest
Σ (1 7t- 1)6 (ãt - x')
T
T
T 7- - -a) u
(1 14 (2t; u) +
Σ
(1 7o 1e ET)TT +
Σ
(1
t=1
1=1
t=1
T
eg (u x²)
1=1
T
7t- Ue (3:: u)
Σ () TT)
Σ
(1
7 7-
Rb) ssTus K.
We proceed bounding each term separately.
Bound on the first term To bound the first term, we can apply similar analysis to the one of
Lemma 5 since, H, is played independently on 7 except for the loss estimator, to attain, under the clean event:
T
Σ 11 (t-1)
[t. - u)
K In
h
K
0
min (1 (E(T]
7-
Σ (1 7--1) Σ
nt 25 (a) (a)
17
10n In
1=1
a=1
K In
hru u
0
71-1)
n 2
(a)ee
(a). (a).
"
10n In T
To bound the last term, we proceed as follows:
2 (a)) (1 1- (a) (1 70- 7-1)m,
lie: =a
[7(aa)
(())
2-1 - (1- m "
1aa a}
{0)
(a)a)
nn (a)
[a a}
0
27((a)
< Ne.. (a))
me la(as)
p
mr. le(at)
Thus, we obtain the following final bound, which holds with probability at least - 5:
T
In T
h (((ae) - -PTOn In
Σ
11-72-)
(x. u) 50
1=1
30

---

Bound on the second term To bound the second term we first notice that (1 (1-2t-1āā; S 2z. Thus, we proceed similarly to Theorem [ noticing that the quantity of interest is Martingale difference sequence, where any difference is bounded as:
(1 10-7-11
(E
es
Eg)
Tt S - (1--1-1) 1)1
Tt.
li T 2t
K
xz(a) (a(a)
Σ
1 1(a a}
(1(a))
1.
Furthermore, we bound the second moment as:
Er (1-
27
27
1)
EE
ex
E.
at
Ex
- (1- 1) ( - Ex)
att
(1 - Mイ- ee, Tz) S]
E,
2
$ E2
C at
$ R2
le
L, xt.
Thus we can apply the Freedman inequality to attain, with probability at least 1 - 6:
T
TT, so
x.
(
Σ
T
e, x In (3) In 111
(1)
Bound on the third term To bound the third term, we notice that the quantity of interest is a Martingale difference sequence. To apply the modified version of the Freedman inequality (see (Lee
et al. 2020a)), )) we notice that:
K
(1 - n (o) u (1--
Σ
u(a)
xx(a)
==1
K
= (1 - 1
1- (a) + (1 (2)) u(a)
a=1
K
1
1 (1 1-11)
(1 - (3))a( u(a)
K
min T (a) u(a)
< h u E [1,7)
We now focus on bounding the second moment follows:
Es (1-
70- 10-
21) 2)) 27
E,
(1 - 1) T 2
- 1 22 (a (a)))())))
E,
27((r)
17 (3(0))u2(a)
$ E,
(1 フナ )
(1 - 72) 27))
31

---

K a (a)er(a)/TT
I hhju L u.
Thus, with probability at least 8, we have by Theorem 2.2 of [Lee al. 2020a]:
T Σ (1--7e () ke) u= H
T
H1
H 8
8
Σ
e
n In
htuln
)
[m((T)[33n(7T)
where = In
Final result Combining the previous equations, get, with probability least 1 36, by Union Bound, the following bound:
T
12-1));
(it
xx)
O
K InT
+ !! Σ
E((ee)
P h
+0
e In
1 (1) 8
+ In
110
8
7
p 1=1
T
H
H 5
+H
l u
u In
+ u
+ K
1=1
0
K KlnT
Σ t=1
(((0t) +
Σ
T
e xz In
1
1 u 10n In T
11
8
H (
H 5)
+ H
C.u e
u h In
1 In
where H =In In
[In(T)]33 lu(2))
Finally, we proceed similarly to Theorem obtaining:
Σ
1) (#, - x*)
KInT
2n
21 In
1
T
1
h u 10n In T
0
e
+
5
+
e
az
In
P [=1
P
1=1
H 5
H
+ H
Lg u
h In
+
h In
Kln T
2n
T
2n
T
h u 10n In T
=0
L xt +
In
+
Σ
e
a, In
[=1
1=1
20 In
H
H
H
fuuln
h u In
20pHn In
8
KlnT
21
T
21
T
1
h u 10n In T
00
f x
+
In
+
Σ 1=1
e
In
32

---

160H 17
In T
T
H
H
eg u
+
n + Hhzull
8
20H In T
(
K 1
l
Kn In
+
Σ
l In ( +
Σ
e in (
t=1
where the first step holds by Freedman inequality and a union bound, setting the confidence to 1 46, and AM-GM inequality, the third step by AM-GM inequality and the last step holds for
77 S 40 Ia 4)
This concludes the proof.
Theorem Let 8 E (0, p 2 12K and n = min 20 In I #l/ VK/Ei_, e, at In(1/6)) J. where
e
T
H In (In(())((3 Then, SOLB suffers cumulative regret bounded as:
(T((I:)) s 0
K (4/6))
Σ
e (a:
xxx)
K
l xx In
1 8
(3)
P
t=1
(A) Safety Complexity
(B) Bandit Complexity
where ① hides universal constants and logarithmic terms not depending on
Proof. We first notice that the regret can be decomposed as:
Rr Σ x, x,2"
T Σ n-ll (x -x") (1- (x)).
Employing Lemma 3
Lemma and a Union Bound, we have, with probability at least 56:
Rr S
43K In (T(K0/00)
Σ
L (x) - xx))²
+
55296
K
In
TKm
P
p
0
K
+
P
K1 In
1
T
In
7
T
e
In
17
p
p
8
P
t=1
1=1
t=1
K
Σ
T
4
(x - xx
2
+
K
+
n p [=1
T Σ
E
xt
+
Kn
In
+
T
e
xe
17
1
e " In
Since 77 $ 2. we have:
"
Rr + Σ e x
and the regret can be rewritten as:
K
e (x - -x-)
x=+))++2 2K
RT
P
t=1
33

---

T
T L In
47
+
Rr
+
4
x²
in
+
1 1=1
t=1
We then set = min
and we solve the quadratic inequality in
40H in
In( 7
Ei= ef x ln(
Ry, obtaining the following regret bound:
Rr S O
K
Σ t=1
l (ar -a+)=
x²))²
1
K le x=
In
(1))
p
t=1
This concludes the proof.
D.2 Safety Property of SOLB
Theorem 3. Lei E (0, 1). With probability at least SOLB guarantees that g at S oz holds for every constraint i E [mi] and round E (T].
Proof. To prove the result, consider separately the case in which 7/- 0 and T (0, 1). When = O, by construction, it holds that Vi E [m] (Gr.s + B,) T(+1 ae and 2++1 H(+1-
Thus, we have:
0; (gt, +,,) 3x+1
(0.,- + B.) a+++1
9 01+1.
where the last step holds thank to Lemma with probability at least 1 - 8.
When 7/- (0, 1), can be selected either as maXie(m]
1-04 or as max
0., #:+1-a; For
1-0;
(0.+ 2:+1-8,"
simplicity, we study each constraint separately, removing the max operator. In the first case, holds:
9: Lt+1
g. (7xx + (1 Yt. (+)))++))))+++++++++)))))))))(
n0 + (1 7+)
1 aj (0, - 1) +
0,
1
(0, 1) +1
a;.
Similarly, in the latter case, holds:
g. xt+1 9 (na + (1 - 7 )
76 + - (1-7)) Te+1
7:0; + (,.,
: + 3,) TT)T.. Øz41
T
(r (θ.,, + (,) T(+1) + (g., + (,, T
(ō., + 3,) T,)TT.11 T,+1
(Ø., + (,) k141 8, (0, -Gr + (,) T(+1) + (,.,, + (3)) T441
(ā., + B,) Ti41 (0, (g., B,) 2 + (ā., + 3,) T1+1
@ + 3,) T141
a.-
Observing that, thanks to the convexity the estimated feasible set, the max operator allows the aforementioned reasoning to hold for each constraint i [m]) concludes the proof.
D
34

---

((a1)
((a2))
(s(a3)
9r (a(a))
(a(a2)
g:(a3)
V1
W2/2
W
(W++A)/
Dr
Dr
Ct
V/2
W1/2
V
(W++A)/
B
B
C2
V/3
11/2
Wi/2
(We+A)/
Bt
B₁
C2
V4
V1/2
V1/2
(We+A)/2
B,
B,
C₁
Table Summary of the losses (first three columns) and constraints costs (last three columns) associated to each of the four instances.
D.3 Regret Lower Bound in MABs with Hard Constraints
Theorem 5. Let 2,T max (2. (11 In ( and E + ( + 1n1) 2.1. Then for
every randomized algorithm, we have BB....r (((T((EL))) 2 a VT + vwT) where the expectation is taken with respect to the internal randomization of the algorithm.
Proof. We split the proof in two parts: first, we prove a Ω (VWT + AVT/P) lower bound for the
expected regret of any randomized algorithm, when the losses are stochastic. stochastic setting, represents the double of the expected value of the loss of the best strategy, while A the double of the expected value of the difference between the strictly safe strategy and the benchmark. Second, we show that there exists least sequence of loss belonging Bu,A,T such that the lower bound from the first step holds.
Step Let B(w) indicate Bernoulii probability distribution with mean (0,1), 1). We start by introducing four instances of the hard constrained bandit problem where both losses and constraints costs stochastic. To do so, assume that both losses and constraints sampled in advance, and introduce the following auxiliary sequences, for all / E (7]:
W. B(w),
Y, ~ B(w + 1b),
B, B(1/2).
C. ~ B(1/2 - p),
D. ~ B(1/2+
where w E (0, })2 v E (0, 10,1-u) and p.e (0, 1). We consider four instances {vi)1= each with K actions, namely 01 42 and a3. In Table we summarize how losses and constraints costs are generated for each action and in each instance. Instance V1 the only one having different constraints costs, while action 03 has, for every [Z'], the same loss every instance. In all instances, x = (0,0, 1) is the only strictly safe strategy.
We start by considering : in order be safe with high probability, for given confidence level E (0, 1), any algorithm must satisfy:
Pe.
Vt E (a() 2 -
:
2
where æ; is the strategy of the algorithm at time and Pr, the probability measure of instance v which encompasses the randomness of both environment and algorithm. As consequence, we have:
PA Σ xa(as) 2 T +
2 21
We now leverage Pinsker's inequality to relate the probability measures Pr, and Fry, with j e {2, 3, 4), as follows:
T
T
Pu Σ
xr(aa) 2 2T_
2 Prn
Σ
xx((s) 2 T
- (LT(,,
ctp)
c+p
35

---

where (L,( is the KL-divergence between the probability measures Fr, and Pe, after T rounds of history.
Using the KI. decomposition argument from Lemma of Gerchinovitz and Lattimore 2016 (which holds for correlated losses, in case), and by upper bounding the KL. between Bernoulli r.v.s using the x² diveeregee (see Lemma 2.8 from Tsybakov (2008). ), for every E {2, 3, 4), we have
KLr(U,, - (B(K + 1)), ((w)) + KL(((1/22, B(1/2 + c)))
2
2²
S T
w(1 w)
(3 + + -c)
1
$ 4
where the last step obtained by setting vi $ - and bb 7. (2,3,4)
Thus, for every j
T
Pus
Σ
T-
T
2
3
E
Which implies, for every 8 (0, 4):
1 T 1 e
E Σ xp(as)
(13)
Now, we focus on instance 122 and wr: in the former the optimal strategy is to always pull a,, while in the latter to always pull a2 Hence, we can compute the expected regrets as:
2E,, [RT] = Ep
3 T
(w + 2 vizz, (a1) + (A (a))
Tw,
2E,, [Ryl = Eyg
11=1 (w + 3 2izz + (A
()s))
- T
2Buu [Rr] Tvb - 1/
(x)(()) + 2i (as))
+ +A
Σ/e 1== Iee (az)
pE [Ryl = Tab Eb
(02) + x4 (aa))
+ AE
Σ/ Ire (aa)
We now leverage Lemma A.1 from with Ep,;
Auer et al. 2002 and relate the expectations Ey,, for j E (2,3).
In 2 KLT(vs,
Ex, Σ (ai)
< Ey
Σ (a:)
+ +TV
(14)
2
for every ag where KLr indicates the KL-between the probability measures after T rounds history, and can be bounded a
KLT(Va,V)) w(1 - w)
(15)
follows:
2E,, [Rr] = T4h v Eu,
( + xx((a))
2 w[l-o] + A AEEZ
HOTS
Σ T
23 (as)
2Ep [Rr] = Tyy E
Σt (az) + +x((as))
In2 ve7s
w0l-w + AEE,
ΣT 24 (as)
2E,, [Rir] = EEE,
Σ 12)
In2 N-7S
+ AE
-= 21((3))
[[I-w]
2E,, [Rr] = Evr
Σt= 11))
h22 6e7s
+ AE
Σ 24 ((s)
2 (1|-w)
'Note that KL divergence is invariant to scaling, thus we directly compare Bernoulli distribution instead of the distributions derived by dividing two.
36

---

where the first step is a consequence of Equation 15 and the second step follows from the identity xx(a1) + (02) + (2)) for every E [T]. We are now ready lower bound the average expected regret between instances V2 and V3-
In2 1/T33
Ex, [Rr] + Egg [Ry] 2 E
Σ (a1) z(((2))
+ ARES
Σ x1(ss)
2
w 1 w)
Tb
v
T
In2 WATS
+
A
Ey,
v2((s))
2
2
w0 w)
Lt=1
T
TA
In2 1/773
2
8
c+ P V 2 w(1 w)
1 16 w(1 w)T + AVT
48p
where the second inequality follows from Equation 13 and the fact that A v/ the last inequality
from the definition of 1b and e, and the fact that 2 e. Noting that max (Ev, [[T], Ev, [Rr]] 2 (Ex, [RT] Eug RtT) /2, we conclude first step.
Note that + = V( W - 2 thus the (deterministic) term a V is equivalent to the
Step 2
quadratic term describing the average squared distance between the optimal policy and the strictly safe strategy instances V2 and V33
Consider T 2 max 2, (11 + In
and 2 w 2 7 max {1, ( + InT). Note that the never empty due to the condition on T.
set of existence
Consider modified versions of these instances with ت : we apply Bernstein Inequality to obtain that, with probability at least 1 - 8':
T
W
Σ t=1
e
x
Σ
2
1=1
Tw
(1)
1
+
2T
W) In
+
In
2
2
8'
8'
Tw
Tw
Tw 2
(16)
4
4
by observing that (3)² In ④7) < Tw, which holds true for 8' 2287+ given the conditions T and w. Thus, instances 1/2 and V/3 may generate, with high probability, loss sequences in which the optimal one is bounded by _t We conclude the proof by showing that, among these loss sequences, at least one satisfics the previously derived lower bound. Without loss of generality, consider 1/2 to be the instance with the higher expected regret, then apply the lower bound derived in Step I with @ to get
9 VT 1024
1 AVT,
Ex, (RTT))
(17)
48p
where f1T a fixed loss sequence generated 22, and using that w I that, for every fITT s.t. Equation (66) holds, then
Suppose by contradiction
1 AVT,
Ev, (Rr(CI)))
Tww +
2048
48p
Then, by setting 8'
7287 we have:
1
Ev, [R (Rr:r)] E,,
(Rr(Errr )1 Eq
Eu,
(RI.T) - Egg [6)
[6
9
1
TTw +
AVT +
2048
48p
228
37

---

9
Tw + 48p
AVT.
1024
where the first inequality derives from bounding the regret with and the definition of 8", and the second inequality derives from observing that Tw (9.228) 2 given the conditions on T and w. This represents a contradiction with the lower bound derived in the first step, and thus there must exist loss sequence such that Equation (16) and Equation 117 hold simultaneously.
38


Reviews:
[{"review_id": "Dvlf357hRc", "reviewer": "Reviewer_JrAR", "summary": "In this paper, the authors consider a constrained MAB formulation, where the goal is to provide data-dependent regret bounds. Here, losses are adversarial, but constraints are modelled as being stochastic. The authors propose an algorithm that adapts OMD in conjunction with 'safe' decision spaces.", "questions": "1. Can the authors provide an intuitive explanation of why lower confidence bounds (LCBs), rather an UCBs, of the arm constraints are used to define safe decision spaces? I am referring to the display equation after Line 155 on Page 4. Note that with high probability, the actual $g_i$ are higher than their LCB. So the following sentence that with high probability, the set $\\mathcal{S}_t$ contains actions that satisfy the constraints also feels suspicious.\n\n2. Line 11 of Algorithm 1: The function $D_{\\psi_t}(x,x_t)$ is not defined anywhere as far as I can tell. The meaning of this does not follow from the definition of $\\psi_t(x)$ that follows. A similar comment applies to Algorithm 2.\n\n3. Note that regret calculations here include expectations with respect to algorithm randomisation. However, it feels clumsy to provide a \\emph{high-probability} bound on the \\emph{average} regret. Now, I understand the \"high-probability\" bit is due to the stochastic constraint modelling, and the \"average\" bit is over the algorithm randomisation. A brief commentary on this would be useful, IMO.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "One natural concern is whether it is reasonable to assume adversarial losses in conjunction with stochastic constraints. While the authors do point to an impossibility result to justify the assumption, it is not clear to me whether the proposed setting captures any application reasonably.\n\nMoreover, the algorithms are assumed to have bounds on the loss of optimal action in hindsight, plus a strictly feasible strategy (Assumption 2). Again, it is perhaps true that the problem is intractable in the absence of such knowledge, but I wonder is what that  really means is that the problem is ill-posed.\n\nAside from the above reservations on the problem formulation itself, the paper seems to make useful algorithmic contributions. The decomposition of the regret into safety complexity and bandit complexity is also quite interesting.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the positive evaluation of our work. \n\n> One natural concern is whether it is reasonable to assume adversarial losses in conjunction with stochastic constraints. While the authors do point to an impossibility result to justify the assumption, it is not clear to me whether the proposed setting captures any application reasonably.\n\nAs the Reviewer noticed, the main motivation of our setting with adversarial losses and stochastic constraints is theoretical, as it is provably not possible to attain sublinear regret and violation when the constraints are adversarial as well. Nonetheless, we think that there are several applications where the loss (reward) function exhibits some sort of non-stationarity, and the constraints are instead sampled from fixed distributions. Indeed, losses (rewards) may be determined from events occurring in the external environment and possibly influenced by other learning agents (being thus possibly non-stationary), while in many applications, constraints encode some inherently stationary requirements, e.g., some resource consumption not affected by the external environment.\n\n> Moreover, the algorithms are assumed to have bounds on the loss of optimal action in hindsight, plus a strictly feasible strategy (Assumption 2). Again, it is perhaps true that the problem is intractable in the absence of such knowledge, but I wonder if what that really means is that the problem is ill-posed.\n\nWe thank the Reviewer for the interesting question. For the bound on the loss of the optimal action, we underline that a standard doubling trick approach can easily remove this assumption, that is, the quantity can be estimated on the fly, paying an additional logarithmic factor in the regret [1,2]. As concerns Assumption 2, this is met in every application where there exists a void action that attains $0$ violation, such as online auctions, where the bidder may decide to bid the $0$ value, not incurring any cost. If knowledge on the strictly feasible strategy is not available, the problem becomes ''unlearnable'' according to the standard bandit definition, i.e., the worst-case regret suffered is linear.\n    \n[1] Chung-Wei Lee, Haipeng Luo, and Mengxiao Zhang. A closer look at small-loss bounds for bandits with graph feedback. In Conference on Learning Theory, 2020.\n      \n[2] Lee, C. W., Luo, H., Wei, C. Y., Zhang, M. (2020). Bias no more: high-probability data-dependent regret bounds for adversarial bandits and mdps. Advances in neural information processing systems, 33, 15522-15533.\n    \n> Can the authors provide an intuitive explanation of why lower confidence bounds (LCBs), rather an UCBs, of the arm constraints are used to define safe decision spaces? I am referring to the display equation after Line 155 on Page 4. Note that with high probability, the actual $g_i$ are higher than their LCB. So the following sentence, that with high probability, the set $S_t$ contains actions that satisfy the constraints also feels suspicious.\n\nWe thank the Reviewer for the comment. We believe that there is a possible misunderstanding. Playing in $S_t$ at each round allows us to obtain a sublinear cumulative violation. The safety property is attained by an additional convex combination with the safe known strategy.\n\nFrom a technical perspective, LCBs are employed since the safe optimum must be included in $S_t$ at each $t$; thus, it is necessary to be optimistic on the constraints satisfaction, which results in employing the lower confidence bound. Then, it is easy to show that $S_t$ concentrates on the true safe set at a rate of $1/\\sqrt{T}$, resulting in a $\\widetilde{\\mathcal{O}}(\\sqrt{T})$ violation bound.\n\n> Line 11 of Algorithm 1\n\nWe thank the Reviewer for pointing out this aspect. We forgot to explicitly state the Bregman divergence definition, since this directly follows from the regularizer $\\psi_t$ definition. Nonetheless, we will explicitly specify it in the final version of the paper.\n\n> Note that regret calculations here include expectations with respect to algorithm randomisation. However, it feels clumsy to provide a \\emph{high-probability} bound on the \\emph{average} regret. Now, I understand the \"high-probability\" bit is due to the stochastic constraint modelling, and the \"average\" bit is over the algorithm randomisation. A brief commentary on this would be useful, IMO.\n\nWe thank the Reviewer for the interesting comment.  Our regret definition employs strategy mixtures in place of the actual actions played by the algorithm and compares them to the optimal mixed strategy. This is done to be consistent with the constrained online learning literature, where the optimum is not pure, but it is a distribution over the actions. We remark that we do not take the expectation over the algorithm's randomization in the regret definition: indeed, we use OMD with log-barrier to deal with the loss estimation without taking the expectation on the algorithm's randomization. Thus, the ''high probability'' also encompasses the algorithm's randomization.\n    \nWe will surely include this comment in the final version of the paper. Please let us know if further discussion is necessary."}, {"review_id": "w3aeetVJw3", "reviewer": "Reviewer_UfDE", "summary": "This paper studies data-dependent regret bounds in constrained Multi-Armed Bandit (MAB) seetings. The authors focus on the scenario of adversarial losses and stochastic hard constraints (due to the impossibility result for fully adversarial scenarios). They propose two algorithms, which are Constrained OMD with Log-Barrier (COLB) for soft constraints and the main algorithm Safe OMD with Log-Barrier (SOLB) for hard constraints. SOLB satisfies the constraints with high probability by dynamically combining and OMD-suggested strategy with a strictly feasible one. They show that the high probability regret bound has two data-dependent terms: a safety complexity term that quantifies the difficulty introduced by satisfying the constraints; and a bandit complexity term that represents the learning complexity independent of the constraints. The authors also provide a lower bound to demonstrate that these two terms are in fact fundamental and inherent characteristics of the problem and the proposed algorithm SOLB is optimal up to logarithmic terms.", "questions": "1) Can you possibly relax (or maybe adaptively learn) the strictly feasible strategy and its associated costs? It would be nice to discuss this even as a future research direction.\n\n2) Can you give a more in-depth explanation for your conjecture that the $1/\\rho$ dependence should affect only the Safety Complexity term (A), and not the Bandit Complexity term (B)? What specific challenges exist in your derivations in achieving a tighter bound?\n\n3) The learning rate for COLB and SOLB requires knowledge of the optimal cumulative loss. While \"doubling trick\" is mentioned, how would this trick specifically be applied?\n\n4) What are the hypothetical practical applications where your algorithm and results would be most critical and beneficial?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "## Strengths\n\n1) The algorithms seem novel. COLB for soft constraints serves as a warm-up by achieving small-loss regret bounds and the primary contribution SOLB provides optimal regret for hard constraints.\n\n2) The theoretical insights on the data-dependent regret bound, especially the natural interpretation of the two independent terms safety and bandit complexity is very nice.\n\n3) The regret bound is optimal (up to logarithmic factors).\n\n## Weaknesses\n\n1) SOLB requires Slater's condition and explicit knowledge of a strictly feasible strategy and its associated costs as input, which seems limiting, especially in practical applications.\n\n2) The initial setting of the learning rate requires knowledge of the optimal cumulative loss.\n\n3) While not a major weakness, there are no empirical validation.", "was_revised": true, "final_justification": "I am keeping my score, which remains positive.\n\nThe algorithms (COLB, SOLB) are novel, addressing a previously overlooked area and providing an affirmative answer to the research question about data-dependent regret bounds in constrained MABs. The decomposition of regret into \"Safety Complexity\" (difficulty of satisfying constraints) and \"Bandit Complexity\" (complexity of learning independently of constraints) offers valuable insights. A lower bound shows these terms are fundamental, and SOLB's bound is optimal up to logarithmic factors. The authors confirmed that a standard \"doubling trick\" can handle the requirement of knowing the optimal cumulative loss, incurring only negligible logarithmic factors while maintaining safety guarantees. A hypothetical example in online advertisement was provided, offering context for the algorithms.\n\nSOLB requires explicit knowledge of a strictly feasible strategy and its associated costs as input. While theoretically justified to prevent impossibility results and ensure exploration, this assumption limits broader applicability where such a strategy might not be readily available. The paper is purely theoretical, which is acceptable but means practical insights lack empirical support.\n\nThe strong theoretical contributions and proofs (novelty, decomposition, tightness) heavily outweigh the identified practical limitations and remaining subtle theoretical questions.", "rebuttal": "We thank the Reviewer for the positive evaluation of our work. \n\n> SOLB requires Slater's condition and explicit knowledge of a strictly feasible strategy and its associated costs as input, which seems limiting, especially in practical applications.\n\nWe thank the Reviewer for the opportunity to further elaborate on the assumptions. **Assumption 1.** Assumption 1 (namely $\\rho>0$) is provably necessary in the hard constraints setting, as highlighted by Theorem 5. To see this, notice that, when Assumption 1 does not hold, a strategy that is arbitrarily close to the safe one (that is, the strategy with $\\rho=0$) could violate the constraints, thus preventing any form of exploration. \nWe underline that Slater's condition is commonly accepted in the constrained online learning literature.\n**Assumption 2.** Assumption 2 states that the algorithm is given a strictly feasible solution (and its costs).\nFrom a theoretical perspective, this assumption allows the algorithm to simultaneously explore and satisfy the constraints when no information on the environment is available, that is, in the very first rounds. For instance, in the first round, the algorithm has to play randomly; Assumption 2 allows to be safe in the first round while possibly ``exploring\" of a $\\rho$ factor.  **From a practical perspective**, we believe that this requirement is met in many real-world interesting scenarios, where a void action, that is, an action with zero constraint violation and zero reward, is available to the learner (e.g., online auctions, where the bidder may bid $0$ whenever its budget is depleted). \n\n> The initial setting of the learning rate requires knowledge of the optimal cumulative loss. The learning rate for COLB and SOLB requires knowledge of the optimal cumulative loss. While \"doubling trick\" is mentioned, how would this trick specifically be applied?\n\nThe doubling trick we mention is the one developed in [1] (Appendix C.3) and [2] (Remark 1). In [1], the authors introduce such a doubling trick for adapting to the very same quantity. Their setting involves graph-feedback, but one can plug an unconnected graph and resort to a standard bandit feedback, recovering the exact algorithmic steps.\n\n[1] Chung-Wei Lee, Haipeng Luo, and Mengxiao Zhang. A closer look at small-loss bounds for bandits with graph feedback. In Conference on Learning Theory, 2020.\n      \n[2] Lee, C. W., Luo, H., Wei, C. Y., Zhang, M. (2020). Bias no more: high-probability data-dependent regret bounds for adversarial bandits and mdps. Advances in neural information processing systems, 33, 15522-15533.\n\n> Can you possibly relax (or maybe adaptively learn) the strictly feasible strategy and its associated costs? It would be nice to discuss this even as a future research direction.\n\nWe believe that it is possible to dynamically learn the Slater's parameter and the strictly feasible strategy on the fly, paying an additional constant term (independent of $T$) in both regret and violation, that is, **the safety property is not attainable** but constant violation is. This probably can be done employing, for a constant number of rounds, a primal-dual Lagrangian approach on the constraints only, so that the optimal solution becomes the safest one corresponding to Slater's parameter. Then, it is sufficient to run our algorithm for the hard constraints with the estimates attained in the previous phase. \n\nWe will include this discussion in the final version of the paper. \n\n> Can you give a more in-depth explanation for your conjecture that the  $1/\\rho$ dependence should affect only the Safety Complexity term (A), and not the Bandit Complexity term (B)? What specific challenges exist in your derivations in achieving a tighter bound?\n\nWe thank the Reviewer for the interesting question. From a high-level perspective, the (B) term arises from the intrinsic hardness of attaining small loss regret bounds. Differently, the (A) term arises from the safety property, which forces any algorithm to play the strictly feasible solution a number of times that depends on $\\rho$. Thus, if we consider unconstrained MABs, which are the trivial case of constrained MABs, the (A) term disappears, and the regret bound consists of the second term only. Thus, since the $\\rho$ terms do not appear in unconstrained cases, it is reasonable that it is linked to the (B) term only.\n\nAs concerns the technical challenges to achieve a tighter bound, they are summarized in the following. The main idea we had to prove the tight bound was to split the analysis of Lemma 4 in two phases: (i) when the convex combination parameter $\\gamma_t$ is large and (ii) when the convex combination parameter is small enough---notice that a similar approach is employed in the current analysis of Lemma 3, to avoid a $1/\\rho^2$ dependence---, and proving that $\\widetilde R_T$ in the first phase ($\\gamma_t$ large) is constant while $\\widetilde R_T$ in the second phase is independent on $\\rho$. There are two key challenges in doing that. First, it is necessary to show that after a constant number of rounds, $\\tilde{\\boldsymbol{x}}_t$ is not to far from the uniform strategy (that is, the initialization). This can be done only assuming that $T$ is very large. Second, it is not true that there exists a round $\\bar t$ which splits exactly the two phases. Thus, the analysis may result inconsistent in adversarial settings, since the rounds must be consecutive to properly bound the \"regret\", or, in this case, $\\widetilde R_T$.\n\nPlease let us know if further discussion is necessary.\n\n> What are the hypothetical practical applications where your algorithm and results would be most critical and beneficial?\n\nIn the following, we provide a practical application in the context of online advertisement. In an online advertisement scenario, from the perspective of a publisher, multiple ads (say, $K$ distinct ads) are available to be displayed to incoming users. Every ad is associated with an expected revenue, which may depend on the type of ad or its position. In an unconstrained scenario, the problem would just be to find the most profitable ad strategy. However, displaying an ad is associated with an economic cost (the spend-per-impression), and a marketing campaign has limited funding. In this sense, a publisher trying to maximize its profits in an online manner resorts to the constrained MAB model, with either soft or hard constraints, depending on its own spending policy.\n\nWe will surely include this discussion in the final version of the paper."}, {"review_id": "TWlhRr07pB", "reviewer": "Reviewer_5KbZ", "summary": "Constrained bandits represent a compelling and practically relevant problem, motivated by numerous real-world applications. While the existing rich literature primarily focuses on horizon-dependent guarantees, this paper initiates the study of **data-dependent guarantees** in the setting of **adversarial losses** and **stochastic constraints**. The authors make the following key contributions:\n1) **COLB** : An algorithm designed for the soft constraint setting, where the learner is allowed to violate constraints. The authors provide a classical upper bound on constraint violations and a data-dependent upper bound on the regret.\n2) **SOLB** : An algorithm tailored for the hard constraint setting, where the learner must satisfy the constraints at each round with high probability. The authors prove that the algorithm does not violate the constraints and provide a data-dependent upper bound on the regret.\n3) **Lower Bound**: The paper also presents a lower bound that supports the tightness of the proposed upper bounds, reinforcing the theoretical soundness of the results.", "questions": "**Questions and remarks:**\n1) Please address the weaknesses mentioned above.\n2) In the proof of Lemma 2, particularly the first inequality following line 546, it is unclear how the bound holds uniformly for all $t$ without any additional assumption on the norm of $\\hat{g}_{t,i} - \\beta_t$. Could you please elaborate on this step?\n3) In the proof of Lemma 5, you use the inequality $\\kappa^{n_a} \\leq 5$. Could you please explain how this bound is derived?\n4) In the proof of Theorem 2, could you please clarify the inequality that appears after Line 586? It seems to me that $\\hat{l}_t$ is sparser than $l_t - \\hat{l}_t$.\n5) I suggest modifying the definition of $V_T$ by placing the '$\\max$' operator inside the summation. This adjustment would ensure that there is no compensation between rounds across different arms. Moreover, the theoretical proofs provided in the paper would remain exactly the same under this modification.\n6) Can you please share your opinion on the case where the losses (or rewards) are stochastic while the constraints are adversarial?\n\n**Minor typos:**\n1) In Line 13 of the SOLB algorithm, should it be $\\tilde{x_{t+1}}$ instead of $x_{t+1}$?\n2) In the proof of Lemma 2, the second equality following line 548 appears to reference the set $\\tilde{S}$. However, I believe it should be $S^{\\circ}$ instead, based on the context and the structure of the argument.\n\n\nI am fully open to revising my evaluation and raising my score if the issues I raised are adequately addressed.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n1) The paper is well written and easy to follow. \n2) The problem addressed is interesting and opens a promising direction for research. \n3) The mathematical analysis appears to be sound.\n\n**Weaknesses:**\n1) While the question of data-dependent guarantees for constrained MABs is novel, both data-dependent regret bounds for unconstrained MABs and algorithmic design for constrained MABs have been extensively studied. This paper appears to combine several previously proposed techniques and results. In particular, the OMD with log-barrier algorithm introduced by [lee et al. 2020] is heavily utilized in the proposed algorithm, especially in the analysis techniques, which are central to the proofs of the main theorems. Additionally, the structure of the feasible sets and the combination factor idea bear strong resemblance to those presented in [Pacchiano et al. 2021] and [Amani et al. 2019] .\n2) I have an issue with the paragraph titled **Safe Decision Space** (Lines 152--160). I am unable to see how, by invoking Lemma 1, one can conclude that selecting a strategy from $S_t$ ensures satisfaction of the constraints with high probability. Specifically, the definition of $S_t$ involves a subtraction, and I believe the claim would only hold if the definition used a '+' instead of a '-' sign, or alternatively, if the constraints were of the form $g_i^\\top x \\geq \\alpha_i$. As it stands, the justification for the safety guarantee is unclear.\n3) The quantity $D_{\\psi_{t}}$ is used extensively throughout the algorithms. However, unless I missed it, it does not appear to be explicitly defined in the main text.\n4) It would strengthen the paper to include numerical simulations that empirically validate the theoretical claims. Currently, the paper lacks such experiments, which are essential for demonstrating the practical relevance and performance of the proposed algorithms.", "was_revised": true, "final_justification": "I have read the authors’ rebuttal as well as the discussion from other reviewers. I find the paper to be well written and easy to follow, with a high level of mathematical rigor. The work addresses a novel and previously unexplored question, although it does so by adapting well-established techniques from the literature (such as Online Mirror Descent and algorithmic frameworks for bandits with constraints).\n\nOverall, I am positive about the paper and believe it makes a contribution to the field.", "rebuttal": "We thank the Reviewer for the positive evaluation of our work. \n\n> While the question of data-dependent guarantees for constrained MABs is novel, both data-dependent regret bounds for unconstrained MABs and algorithmic design for constrained MABs have been extensively studied. This paper appears to combine several previously proposed techniques and results. In particular, the OMD with log-barrier algorithm introduced by [lee et al. 2020] is heavily utilized in the proposed algorithm, especially in the analysis techniques, which are central to the proofs of the main theorems. Additionally, the structure of the feasible sets and the combination factor idea bear strong resemblance to those presented in [Pacchiano et al. 2021] and [Amani et al. 2019] .\n\nWe certainly agree with the Reviewer on the fact that our algorithm for the soft constraints setting relies on existing algorithms that attain data-dependent bounds in unconstrained settings. \n    \nNonetheless, we believe that our results contain technical novelty and may be of independent interest. Both the regret upper bound and the regret lower bound require a novel (and challenging) analysis w.r.t. state-of-the-art unconstrained settings. This is a consequence of the fact that the (A) term and the (B) term must be treated separately (in both upper and lower regret bounds), preventing the use of existing techniques. \n\nMoreover, while our techniques to handle the constraints satisfaction may share similarities with [Pacchiano et al. 2021] and [Amani et al. 2019], we underline that their techniques cannot be generalized to our setting, due to the adversariality of the losses. Indeed, their approach is summarized as follows. They play the strictly safe strategy for a certain number of rounds, then they play on a pessimistic safe set. We cannot adopt their approach, since adversarial no-regret algorithms do not work on enlarging decision spaces, such as pessimistic ones. Instead, we optimize on an optimistic decision space (that is, a decreasing one) and then perform a convex combination on the strictly safe strategy. \n\n> I have an issue with the paragraph titled Safe Decision Space (Lines 152--160).\n\nWe thank the Reviewer for the opportunity to clarify this aspect. We believe that there is a possible misunderstanding. Playing in $S_t$ at each round allows us to obtain **sublinear cumulative violation**. The safety property is attained by an additional convex combination with the safe known strategy.\n\nFrom a technical perspective, lower confidence bounds are employed since the safe optimum must be included in $S_t$ at each $t$; thus, it is necessary to be optimistic on the constraints satisfaction, which results in employing the lower confidence bound. Then, it is easy to show that $S_t$ concentrates on the true safe set at a rate of $1/\\sqrt{T}$, resulting in a $\\widetilde{\\mathcal{O}}(\\sqrt{T})$ violation bound.\n\nWe will better specify it in the final version of the paper.\n\nSince this is a crucial aspect, please let us know if further discussion is necessary.\n\n> The quantity $D_{\\psi_t}$ is used extensively throughout the algorithms. However, unless I missed it, it does not appear to be explicitly defined in the main text.\n\nWe thank the Reviewer for the comment. We forgot to explicitly state the Bregman divergence definition, since this directly follows from the regularizer $\\psi_t$ definition. Nonetheless, we will explicitly specify it in the final version of the paper.\n\n> In the proof of Lemma 2, particularly the first inequality following line 546, it is unclear how the bound holds uniformly for all  $t$ without any additional assumption on the norm of $\\hat g_t-\\beta_t$. Could you please elaborate on this step?\n\nWe thank the Reviewer for the comment. The Reviewer is correct. In general, in UCB approaches, when the rewards are bounded in $[0,1]$, the quantity (empirical mean of the) rewards plus concentration bound is capped to $1$. Similarly, in our case, we do the same for the constraints, taking $0$, when $\\hat g_t -\\beta_t$ is negative.\n\nWe will better clarify it in the final version of the paper.\n\n> In the proof of Lemma 5, you use the inequality $k^{n_a}\\leq 5$. Could you please explain how this bound is derived?\n\n$\\kappa$ is defined as $e^{1/\\ln T}$. We can upper bound $n_a$ with $\\ln 5 \\ln T$, noticing that $x_t(a)$ is lower bounded by $1/T$ and initialized to $1/K$ and $h_a$ is initialized as $2K$ and updated as $2/x_t(a)$ every time $1/x_t(a)>h_a$. \n\n> In the proof of Theorem 2, could you please clarify the inequality that appears after Line 586? \n\nThe Reviewer is correct in stating that $\\hat{\\boldsymbol{\\ell}}\\_t$ is sparser than $\\boldsymbol{\\ell}$, even if $\\hat{\\boldsymbol{\\ell}}\\_t$ is larger than $\\boldsymbol{\\ell}$, in terms of $||\\cdot\\||_{\\infty}$ norm. Nonetheless, the bound (at the end of the inequalities) trivially holds by bounding the difference with $\\mathbb{E}_t[(\\boldsymbol{\\ell}_t^\\top \\boldsymbol{x}_t)^2]$. Thus, in the proof, we focus on the term $\\mathbb{E}_t[(\\widehat{\\boldsymbol{\\ell}}_t^\\top \\boldsymbol{x}_t)^2]$, which needs more explanation. In the final version of the paper, we will better specify this step. We thank the Reviewer for spotting this aspect.\n\n\n\n> I suggest modifying the definition of $V_T$ by placing the $\\max$ operator inside the summation. This adjustment would ensure that there is no compensation between rounds across different arms. Moreover, the theoretical proofs provided in the paper would remain exactly the same under this modification.\n\nWe thank the Reviewer for the comment. We employed our definition of $V_T$ since it is standard in the literature. Nonetheless, we do not understand how placing the $\\max_{i\\in[m]}$ operator inside the summation would prevent compensation between arms. Indeed, the compensation between rounds is prevented by the $[\\cdot]^+$ operator, while the definition of violation is with respect to the strategy, and not with respect to a specific action.\n\n> Can you please share your opinion on the case where the losses (or rewards) are stochastic while the constraints are adversarial?\n\nThe impossibility result on learning with adversarial constraints carries on when the losses are stochastic, too. Technically, it still holds for deterministic fixed losses. We refer to [1] for additional details.\n\n[1] Online learning with sample path constraints. Shie Mannor, John N. Tsitsiklis, and Jia Yuan Yu (2009)\n\n> In Line 13 of the SOLB algorithm\n\nWe thank the Reviewer for pointing out the typo, we will correct it in the final version of the paper.\n\n> In the proof of Lemma 2, the second equality following line 548 appears to reference the set $\\tilde S$. However, I believe it should be $S^\\circ$ instead, based on the context and the structure of the argument.\n\nWe thank again the Reviewer for pointing out the typo.  We will correct the typo in the final version of the paper."}, {"review_id": "LqYorqKY4g", "reviewer": "Reviewer_eMxG", "summary": "The paper studies the multi-armed-bandit (MAB) problem where the learner chooses an arm among K fixed choices at each round t from 1 to T. At each t the learner receives a reward associated to the chosen arm and strives to maximise the cumulated sum of rewards. The paper considers adversarial rewards, and so good strategies are randomized and actually need to choose a vector of probabilities for each arm, at each round.\n\nWhile this problem is very classical, the specificity of the paper is consider constraints. At each round there are realizations (iid over rounds) of constraints, and the probabilities chosen by the learner must satisfy the constraints, either by having a sublinear cumulated sum of violations, or by having no violation with high probability. \n\nThe paper studies the regret, defined as the difference between an optimal strategy in hindsight that satisfies the constraints, and the cumulated sum of rewards obtained by the learner. The goal is to provide bounds that are called \"data-dependent\", that is that depend on the actual adversarial sequence of rewards. These bounds are more informative than worst-case bounds. \n\nThe paper provides an algorithm called SOLB (safe OMD with log barrier) and prove an upper bound for its regret that is data-dependent and is interpreted as the sum of a safety-complexity term and a bandit-complexity term. The paper provides a lower bound as a counterpart, that also has these two terms.", "questions": "Remark 2 uses a lower bound from 2016 for unconstrained MABs. I was surprised that the remark writes that, thus, an upper bound for constrained MABs is tight. Would there be a restricted class of constrained MABs that are \"far from unconstrained ones\", and for which it would be an open question to provide a lower bound?\n\nCould a discussion of concrete motivations for studying constrained MABs be added to the paper. Many readers can have practical motivations in mind for unconstrained MABs (say, for online advertisment) but I think many readers would benefit from examples of concrete constraints. \n\n\nLine 332, is it the fifth term rather than the fourth?", "limitations": "YES", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "STRENGTHS The paper is well-written. Although the content is technical, the authors have made an effort to provide intuition, along the exposition. The topic is important for machine learning theory. The contribution is strong, with a main informative data-dependent regret bound, that is globally matched by a lower bound. The upper bound required to design a new algorithm. The proofs appear to have required a lot of work and appear to be theoretically interesting. \n\n\nWEAKNESSES I would prefer not to point out a specific weakness, as I do not have notable weaknesses in mind for the paper.", "was_revised": true, "final_justification": "Given the author's response to me, and to the other reviews, I am quite confident in my positive evaluation of the paper, in the end.", "rebuttal": "We thank the Reviewer for the positive evaluation of our work.\n\n> Remark 2 uses a lower bound from 2016 for unconstrained MABs. I was surprised that the remark writes that, thus, an upper bound for constrained MABs is tight. Would there be a restricted class of constrained MABs that are \"far from unconstrained ones\", and for which it would be an open question to provide a lower bound?\n\nOur algorithm, COLB, matches the existing regret lower bound for the unconstrained settings. However, we remark that our algorithm also exhibits an upper bound on the cumulative violations. This ''double'' guarantee differentiates the performance analysis of MAB algorithms in the soft constraints setting from the ones in the unconstrained setting. It doesn't matter how much constrained the instance is; the worst-case upper bound on the regret is still in that order of magnitude, as well as the bound on the cumulative violations. This is due to the worst-case nature of the result.\n\n> Could a discussion of concrete motivations for studying constrained MABs be added to the paper. Many readers can have practical motivations in mind for unconstrained MABs (say, for online advertisment) but I think many readers would benefit from examples of concrete constraints.\n\nIn the final version of the paper, we will add the following discussion about applications to online advertising. In an online advertisement scenario, from the perspective of a publisher, multiple ads (say, $K$ distinct ads) are available to be displayed to incoming users. Every ad is associated with an expected revenue, which may depend on the type of ad or its position. In an unconstrained scenario, the problem would just be to find the most profitable ad strategy. However, displaying an ad is associated with an economic cost (the spend-per-impression), and a marketing campaign has limited funding. In this sense, a publisher trying to maximize its profits in an online manner resorts to the constrained MAB model, with either soft or hard constraints, depending on its own spending policy.\n\n> Line 332, is it the fifth term rather than the fourth?\n\nWe thank the Reviewer for spotting the typo. We will surely modify it in the final version of the paper."}]

Author rebuttal:

Meta-review: This paper considers the problem of deriving data-dependent small-loss type bounds for multi-armed bandits with constraints.  The authors give two algorithms for soft and hard constraints, COLB (soft) and SOLB (hard), and prove data-dependent regret bounds for them that decompose into “safety” and “bandit” complexities; the authors also give matching lower bounds which suggest that the regret bounds are (qualitatively) optimal. Reviewers were generally positive on the paper, and felt that it gives a relatively complete answer to a question that has not been explicitly explored in the existing literature.
Decision: Accept (poster)