No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
Authors: Martino Bernasconi
Matteo Castiglioni
Andrea Celli
Venue: ICML 2025 poster (2025)
Keywords: bandits with knapsacks
long-term constraints
adaptive regret
Primary area: theory->online_learning_and_bandits

Abstract: In the bandits with knapsacks framework (BwK) the learner has $m$ resource-consumption (i.e., packing) constraints. We focus on the generalization of BwK in which the learner has a set of general long-term constraints. The goal of the learner is to maximize their cumulative reward, while at the same time achieving small cumulative constraints violations. In this scenario, there exist simple instances where conventional methods for BwK fail to yield sublinear violations of constraints. We show that it is possible to circumvent this issue by requiring the primal and dual algorithm to be weakly adaptive. Indeed, even without any information on the Slater's parameter $\rho$ characterizing the problem, the interaction between weakly adaptive primal and dual regret minimizers leads to a ``self-bounding'' behavior of dual variables. In particular, their norm remains suitably upper bounded across the entire time horizon even without explicit projection steps. By exploiting this property, we provide best-of-both-worlds guarantees for stochastic and adversarial inputs. In the first case, we show that the algorithm guarantees sublinear regret. In the latter case, we establish a tight competitive ratio of $\rho/(1+\rho)$. In both settings, constraints violations are guaranteed to be sublinear in time. Finally, this results allow us to obtain new result for the problem of contextual bandits with linear constraints, providing the first no-$\alpha$-regret guarantees for adversarial contexts.

No- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
Martino Bernasconi
Matteo Castiglioni?
2
Andrea Celli
Abstract
1. Introduction
We consider problem in which a decision maker tries to maximize their cumulative reward over a time horizon T. subject to a set of m long-term constraints. At each round t, the learner chooses I₁ E X and, subsequently, observes a reward fx E [0, 1] and m constraint functions (x(z)) E [-1,1]m. Then, the problem becomes that of finding sequence of decisions which guarantees a reward close to that of the best fixed decision in hindsight, while satisfying long-term constraints Ei (xx) I up to small sublinear violations. This framework subsumes the bandits with knapsacks (BwK) problem, where there are only resource-consumpiio constraints (Badanidiyuru et al. 2018 Agrawal & Devanur 2019 Immorlica et al. 2022).
In the bandits with knapsacks framework (BwK) the learner has m resource-consumption (iee packing) constraints. We focus on the gen- cralization of BwK in which the learner has a set of general long term constraints. The goal of the learner is maximize their eumulative reward, while at the same time achieving small cumulative constraints violations. In this scenario, there ex- ist simple instances where conventional methods for BwK fail to yield sublinear violations of con- straints. We show that is possible to circumvent this issue by requiring the primal and dual algo- rithm be weakly adaptive. Indeed, even without any information the Slater's parameter p char- acterizing the problem, the interaction between weakly adaptive primal and dual regret minimiz- ers leads to a "self-bounding" behavior of dual variables. In particular, their norm remains suit- ably upper bounded across the entire time horizon even without explicit projection steps. By exploit- ing this property, provide best-of-both-wond worl-d guarantees for stochastic and adversarial inputs. In the first case, we show that the algorithm guar- antees sublinear regret. In the latter case, we establish a tight competitive ratio of p/(1 (1 + p). In both settings, constraints violations are guaran- teed be sublinear in time. Finally, this results allow to obtain new result for the problem of contextual bandits with linear constraints, provid- ing the first no-o-regret guarantees for adversarial contexts.
Inputs (fe:gt) may be either stochastic or adversarial. The goal is designing algorithms providing guarantees for both input models, without prior knowledge of the specific en- vironment they will encounter. Achieving this goal in- volves addressing two crucial challenges which prevent a direct application of primal-dual approaches based on the aagraaggeBvt framework in Immorlica et al. (2022).
1.1. Technical Challenges
In order to obtain meaningful regret guarantees, primal- dual frameworks based on Lagr angrangeBwK need to control the magnitude of dual variables. This is necessary as dual variables appear in the loss function of the primal algo- rithm, and, therefore, influence the no-regret guarantees provided by the primal algorithm. In the context of knap- sack constraints, this is usually achieved by exploiting the existence of strictly feasible solution with Slater's parame- ter /, consisting of a void action which yields zero reward and resource consumption. For instance, the frameworks of Balseiro et al. 2022 Castiglioni et al.) 2022a) guarantee boundedness of dual multipliers through an explicit projec- tion step the interval [o, 1/p]. However, in settings with general constraints beyond resource consumption, it is often unreasonable to assume that the learner knows the Slater's parameter / a priori. The problem of operating without knowledge of p has been already addressed in the stochastic setting (Agrawal & Devanur 2014 2019 Yu al., [017] Wei et al.) 2020 Castiglioni al. 2022b) For instance,
'Bocconi University, Milan, Italy "Politecnico di Milano, Milan, Italy, Correspondence to: Martino Bernasconi <mar- tino. www.bbrracconiiee.o unibocconi.it>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
simple approach for the case of stochastic inputs involves adding an initial estimation phase calculate an estimate of p, and subsequently treating this estimate as the true param- eter (Castiglioni et al.] 20226). However, these techniques cannot be applied in adversarial environments as estimates of p based on the initial rounds could be inaccurate about future inputs.
the unknown parameter as in Castiglioni al. (022b). In the adversarial setting, our framework guarantees com- petitive ratio of p/ (1 + p) against the best unconstrained strategy in hindsight. We provide lower bound showing that this cannot be improved if constraint violations have to be o(T). This is the first regret guarantee for our problem in adversarial environments.
Primal-dual templates based on LagrangeBwK usually operate under the assumption that the primal and dual al- gorithms have the no-regret property. In the case of stan- dard BwK, the no-regret requirement is sufficient to obtain optimal guarantees (see, e.g., (Immorlica et al. 2022 Cas- tiglioni et al. 2022a)). However, in our model, there exist simple instances in which the primal and dual algorithms satisfy the no-regret requirement, but the overall frame- work fails to guarantee small constraints violations (see Section 5. Moreover, known techniques to prevent this problem, such as introducing recovery phase to prevent excessive violations, crucially require a priori knowledge of the Slater's parameter p (Castiglioni et al. 20226).
Finally, we show that our model can be used to describe the contextual bandits with linear constraints (CBwLC) prob- lem, which was recently studied by [Slivkins et al. (202bb); Han et al. (2023) in the context of stochastic and non- stationary environments. Our framework allows to extend these works in two directions: we establish the first no-a- regret guarantees for CRWLC when contexts are generated by an adversary, and we provide the first Ö( guarantees for the stochastic setting when the learner does not know an estimate of the Slater's 's parameter of the problem.
2. Related Work
Bandits with Knapsacks. The (stochastic) BwK problem was introduced an optimally solved by [Bdanidiyuru et al.)
1.2. Contributions
Our approach is based on a generalization of the technique presented in Castiglioni et al. (2023) for online bidding un- der one budget and one The crux of the approach is requiring that both the primal and dual algorithms are weakly adaptive, that is, they guar- antee regret upper bound of o(T) for each sub-interval of the time horizon (Hazan & Seshadhri 2007). We gen- eralize this approach to the case of m general constraints, thereby providing the first primal-dual framework for this problem that can operate without any knowledge of Slater's parameter in both stochastic and adversarial environments.
[2013 2018). Other algorithms with optimal regret guar- antees have been proposed by [Agrawal & Devanur [0014] 2019 whose approach is based on the paradigm of opti-
constraint.
mism in the face of uncertainty, and in (Immorlica et al., 2019 2022). In the latter works, the authors propose the Lag LagrangeBwk framework, which has a natural interpre- tation: arms can be thought of as primal variables, and resources dual variables. The framework works by set- ting up a repeated two-player zero-sum game between a primal and a dual player, and by showing convergence to a Nash equilibrium of the expected Lagrangian game.
First, we prove "self-bounding" lemma for the case of m arbitrary constraints. It shows that, if the primal and dual algorithms are weakly adaptive, then boundedness of dual multipliers emerges as a byproduct of the interaction between the primal and dual algorithm. Thus, it is possible to guarantee a suitable upper bound on the dual multipliers even without any information on Slater's parameter.
Adversarial BwK. The adversaris BwK problem was first introduced in Immorlica et al. (2019) 2022). where they stud- ied the case in which the learner has m knapsack constraints, and inputs are selected by an oblivious adversary. Their al- gorithm is based on a modified analysis of Bag, and guarantees a (m log T') competitive ratio. Subse- quently, Kesselheim & Singla 2020 provided a new analy- sis obtaining a Olog m log T)) competitive ratio, which optimal. In the case in which budgets are 12(T). (ITT)/Cassiggiin Castiglioni et al. 2022a) showed that it is possible to achieve constant competitive ratio of 1/p where p is the per-iteration budget.
We use this result prove sorrf--boo-wooolldd no-regret guarantees for primal-dual frameworks derived from LagrangeBwK which employ weakly adaptive primal and dual algorithms. Our guarantees will be modular with re- spect to the regret guarantees of the primal and dual algo- rithms. In presence of suitable primal regret minimizer, we show that our framework yields the following no-regret guarantees while attaining sublinear constraints violations: in the stochastic setting, it guarantees sublinear regret with respect to the best fixed randomized strategy that is feasible in expectation. Remarkably, this result is obtained without having to allocate the initial 1/2 rounds for estimating
Beyond packing constraints. Castiglioni et al. 2022a) studies a setting with general constraints analogous to ours, and show how to adapt the LaagrangeBwK framework to obtain best-of-both-world guarantees when Slater's param- eter is known priori. Similar guarantees are also pro- vided, in the stochastic setting, by (llikkins et al.) (202b)). which then extend the results to the CBwLC model. Fi-
2

---

No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
nally, the work of Castiglioni al. (2023) introduces the use of weakly adaptive regret minimizers within the
imize the cumulative reward Rew(T) == Everyy (1 while minimizing the cumulative violation Vi(2) defined as
LagrangeBwK framework, and provides guarantees in the specific case of one budget constraint and one return-on- investments constraint.
Vi(T) = Σ gt,(2r)
CE|T]
Contextual bandits (CB). We briefly survey the most rele- vant works for our paper. Further references can be found in the monograph by [Slivkins al.
for each constraint i E [m]. We denote by V(T) = [ VT) the maximum cumulative violation across the m constraints.
(011)) As in (Slivkins ltt al. 2023a). we focus on CB with regression oracles (Fos- ter ct al. 2018 8; Foster& & Rakhlin 2020: Bietti et al.) 2021 Simchi- Levi & Xu 2022).. The contextual version of BwK was first studied by (Badanidiyuru et al. (2014) in the case of classification oracles. A
3.1. Baselines
We will provide best-of- both-worlds no-regret guarantees for our algorithm, meaning that achieves optimal theoreti- cal guarantees both in the stochastic and adversarial setting, In this section, we introduce the baselines used to define the regret in these two scenarios.
and oracle-efficient algorithm for this problem was proposed by Agrawal al. (016)) by exploiting the oracle-effiieent algorithm for CB by Agarwal et al. 2014). The first regression-based approach for constrained BwK was proposed by |Agraaal& & Devanur (2016) by exploiting the optimistic approach for linear CB
Adversarial Setting In the adversarial setting we employ the strongest baseline possible, i.e., the best unconstrained strategy in hindsight:
(Li et al., 2010; Chu et al.) 2011 Abbasi- Yabaoi-Yadkori et al. 2011). Han et al. (2023) propose a regression-
ap- proach for constrained BwK setup under stochastic inputs.
Finally, a notable special case of constrained CB is online
Op Adv = sup Σ f((x).
bidding under constraints (Balseiro& & Gur
2019 Celli et al.
xE EE|T]
2023
Gaitonde et al. 2023: | Feng et al.
2023 Wang et al.
2023
This baseline is more powerful than the best fixed strategy which is feasible on average (Immorlica et al. 2022 Cas iiglioni et al. 2022a), which is the most common baseline in the literature. Our algorithm will yield an optimal com- petitive ratio against this stronger baseline. In this setting, we define Paav as the feasibility parameter of the problem instance, i.e., the largest reduction of cumulative violations that the agent is guaranteed to achieve by playing a "safc" strategy E E (XX), where (xX) is the set of all probabil- ity measures on X'. Formally.
Other related works. Fikioris & Tardos (023) show how to interpolate between the fully stochastic and the fully ad- versarial setting, depending on the magnitude of fluctuations in expected rewards and consumptions across rounds. Liu let al. (2022) study a non-stationary setting and provide no- regret guarantees against the best dynamic policy through a UCB-based algorithm. Some recent works explore the case in which resource consumptions in BwK can be non- monotonic (Kumar& & Kleinberg, 2022; [Bernasconi et al. 2023). Finally, related line of works is the one online allocation problems with fixed per-iteration budget, where the input pair of reward and costs is observed before the learner makes a decision (Balseiro et al. 2022 2023)
Paáv == max Ex-eo [9t,(1))]
te[T],e[[
and
E ==
== arg inf max (EA(Z') [e]]]
E Enwg (0.-)()).((x)]
3. Preliminaries
When the reward and the costs are stochastic we denote by ʃ and ğ the mean of fs and gt. re- spectively. In particular, we have that the rewards are drawn so that (x)) = f(z) (and similarly for the costs), where Eroy denotes expectation over the environment mea- sure. We define the baseline for the stochastic setting as the best fixed randomized strategy that satisfies the constraints in expectation, which is the standard choice in Stochastic Bandits with Knapsacks settings (Badanidiyuru et al. 2013 Immorlica et al. 2022). Formally,
Stochastic Setting
There are T rounds and m constraints. We denote with X C kgKK the decision space of the agent. At each round t E [T], the agent selects an action E X' and sub- sequently observes a reward fz(xz) and costs function (x.) E [-1,1]" with fa : X - [0, 1] and Jt,i : X +> [-1, 1] for each E [m]] The reward and cost functions can either be chosen by an oblivious adversary or drawn from a distribution. The goal of the decision maker is to max-
In this work, for any a, & N. with a < b we denote with [a] the set (L...., a} while [a. b] the set (a + b).
Optstoc
sup -o
E [(x))
3

---

No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
Similarly to the adversarial case, define the feasibility parameter Pstce the "most negative" cost achievable by randomized strategies in expectation:
Algorithm Primal-Dual Algorithm
1: Input: Alg, and Al%p
2: for I. = 1,2,.... , do
3: Primal decision: Ja < Algr
inf max Ex Bx=<((((()) (x)] (EA(Z) iE [m]]
Pstoc
4: Dual decision: X + Algo
5: Observe: fe(xe) and g (21)
As it customary in relevant literature (see, e.g., (Immorlica et al. 2022 Castiglioni et al., 2022a b)), we make the fol- lowing natural assumption about the existence of strictly feasible solution. Note that we do not make any assump- tion on the variance of the samples (ft, gt) as we assume that they have bounded support, i.e., with probability holds that f((x) E [0, 1] and (z) E [-1,1] for all r E X' and i [m]]
Primal update: feed uł (2+)) to Al where
uf (xx + f(())) ge
8: Dual update:
8: Feed up x x ff(xx) + (Zee) to Alga
9:
end for
Remark 4.1 (Comparison with BwK). To model BwK prob- lems with our framework, we define ge(2)) - = where E [0, 1 is the vector of costs of the BwK instance and PaNX = B B/T. The zero cost action a of the BwK instance translates in the following PRav of our framework:
Assumption 3.1. In the adversarial setting, the sequence of inputs (ft, T is such that Paav > 0. In the stochastic setting, the environment Env is such that Pstce 0.
Remark 3.2. We will describe a best-of-both-wee worlds type al- gorithm, that attains optimal guarantees both under stochas- tic and adversarial inputs, without knowledge of the specific setting in which the algorithm operates. It should be noted that Padv and Pstoc are not known by the algorithm. While the algorithm could potentially efficiently estimate Pstoc in stochastic settings, as shown in Castiglioni et al. (2022b). ac- quiring knowledge of Psav in the adversarial setting would necessitate information about future inputs. This require- ment is generally unfeasible for most instances of interest.
Pawk gc(a²) 1
PAdv
Psux
Inverting the formula we obtain Pawk
Pady
and
P+
Piar This relation will be particularly helpful in inter- preting our results and comparing it with previous works.
In our set-up, considering arbitrary and potentially nega- tive constraints, we will present an algorithm for which the above holds for a == 1 + 1/Paav. The following result shows that this competitive ratio is optimal. In particular, we show that is not possible to obtain cumulative con- straint violations of order (TT) and competitive ratio strictly less that + 1/p20v (omitted proofs can be found in the Appendix).
4. On
Guarantees
We employ the expression best-of-bothhworlld as defined in Balseiro et al. (2222) for the case of online allocation problems with resource-consune consumption constraints. In this context, expect different types of guarantees depending on the input model being considered.
Theorem 4.2 (Lower bound adversarial setting). Consider the family of all adversarial instances with X {{1, a2), each characterized by a parameter Padv and optimal re- ward Opt Then, no algorithm can achieve, on all in- stances, sublinear cumulative violations IE[V [T)] o(T) and optaa//B/Hevl < 1 +1++7 +//pov
When inputs are stochastic, best-of-both bothoodd algorithm should guarantee that, given failure probability 8 > 0, with probability at least 1 -
max(Opt
()w()).V((T) = Ö(VT).
5. Lagrangian Framework
The dependency on T' is optimal since, in the worst case, it is optimal even without constraints (Auer et al. 2002).
Given the reward function f X - [0. 1] and the costs functions g X + [_1, we define the Lagrangian Lig X x RT - IR as:
In adversarial settings, a soat-of-both-worldde algorithm should guarantee that, with probability at least 1 1-6 8,
(, A) = f(x) - (2, (z))
max (Optaat-aRex(()))
- (TRe = Ö(VT)
We will consider modular primal-dual approach that em- ploys primal algorithm A ge, producing primal decisions It, and a dual algorithm Algp that produces dual deci- sions X, for all t. We assume that Algp and Alg, produce their decisions in order to maximize their utilities u/ and uP, respectively. We define of : x + L (z. Ae) and
where > is the competitive ratio. In the BwK scenario with only resource-consumption constraints, the optimal competitive ratio attainable is a = 1/Prav- In that setting, Paav denotes the per-iteration budget, which we can assume equal for each resource without loss of generality.
4

---

No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
up X + so (1e; A). The regret of the primal algo- rithm Algp on any subset I _ [7] is defined as:
follows: for L [2T/3] we have gt.1 (c.1(a2) -t.1 (1.)(a))))))))))))(()) 0. while (t.1 = gr,1 (03) 1 for all t E [27/3. T1. The instance is depicted in Figure
(x) == sup > (z) (2,)).
Proposition 5.3. Consider the instance of Example 5.2 Even if Aigg and Alg, suffer regret less than or equal then zero, the primal -ual framework fails to achieve sublinear constraint violations.
DEX TET
The regret of the dual algorithm Alg, is defined similarly for any bounded subset DD S IR::
Intuitively, the reason for which a standard primal-dual framework fails in Example [.22 is that the primal regret minimizer can accumulate enough negative regret in the first two phases to "absorb" large regret suffered in the third phase. This "laziness" of Algp allows it to play actions in the last phase for which it incurs linear violations of the constraint. For more details see the proof of Proposition [5.3] in Appendix A One could solve the problem employing the recovery technique proposed in Castiglioni al.. 2 which preseribes minimize the violations at prescribed time. However, selecting the right time to start the recovery phase crucially requires knowledge of the Slater's parameter, which is not available in our setting. The only approach which does not require knowledge of Slater's parameter is the one proposed in [aattiliinn et al.) (2023) for the case of
R
Σ
(A) -u (A.)).
sup AED YET
For ease of notation we write (2) and (D) when = [T], instead of Rirg (X)) and (D)
The interaction of Al and Alsp with the environment is reported in Algorithm|| [ Note that the feedback of Al is forced to be bandit by the fact that we do not have coun- terfactual information of Jt and gt. however Alg, go receives full feedback by design.
Remark 5.1 (The Challenges of the Adversarial Setting). In the stochastic setting, adaptive regret minimization is not re- quired (see, e.g.. [Slivkins et al. (2023b), as one can directly analyze the expected zero-sum game between Alg, and Algo. However, in the adversarial setting, the algorithms Alga and Alg, face a different zero-sum game at each time t. Indeed, since fa and Sr adversarial, the zero-sum game with payoffs f/ is only seen at time L. This is in contrast to what happens in the stochastic setting in which the zero-sum game (. at each time t is the same for all t.
constraints, whose core idea we describe in the next section.
Remark 5.4. We remark that it is not possible to prove that any choice of Alg, and Alg. satisfying the no-regret property fails in our setting. Indeed, we will end up choosing A gp and A Alg, algorithms that have a stronger no-regret property (and hence are also no-regret). Proposition [.3 shows that our arguments and algorithms must necessarily rely on a stronger version of regret, specifically no-adaptive regret.
5.1. No-Regret is Not Enough!
Typically, Lagrangian frameworks for constrained bandit problems are solved by instantiating A1 and Alg, with two regret minimizers, which are algorithms guaranteeing Re (X), RP (D) o(T), respectively (Immorlica et al.. 2022 Castiglioni et al. 2022a). The dual regret minimizer is usually instantiated with D = [o, M|"", for some constant M> 0. Ensuring that 'D is bounded is crucial to control the magnitude of primal utilities uf (-), whose scale influences the magnitude of the primal regret. In the following example, we show that we cannot rely solely on arguments based on the black-box no-regret property of Alg; and Alg, and hence we need stronger guarantees then simple no-regret.
5.2. No-Adaptive Regret
The reason why generic regret minimizes fail to give satis- factory result on the instance described in Example 5.2 is that they fail to adapt to the changing environment, even if the regret of the primal is zero on the entire horizon [T]] it fails to "adapt" in the final rounds [2T/3, T]. Indeed, in these last rounds, if the primal algorithm's 's objective is guarantecing sublinear regret over [T]. it is not required to updated its decision, since it accumulated large nega- tive regret of -2T/3 regret in the initial rounds [[2T/3]. Therefore, standard no-regret guarantees are not enough.
Example 5.2. We have one construint, i.e., m = 1 and the set X = {[11, a2,aaa,,. a3} is a discrete set of actions. The rewards of a1 is always 0, i.e., fe(a1) = 0 for all t E [T]] while its cost is always- -p. i.e., (1,1
A stronger requirement for the primal and dual algorithm being weakly adaptive (Hazan & Seshadhri] 2007). that is, guarantecing that in high probability sup, h sup/=[tt.4a)) [t.] R2
-p for all I E I.. The rewards for 02 and 0g are defined as follows: for t E [[] we have fe(a2) = 0 while f((z)) = 1. On the other hand, for t E [3/ /3] we have (az) =
o(T). Intuitively, this requirement would force Alga ge to change its action during the last phase of Example 5.2 This idea was first proposed in (Castiglioni et al., 20233 for the specific case of a learner with one budget and one return-on- investments constraints. In the following section, we show
while f((as) = O. Finally f((az) = fe(az) = 0 for all
t E [2T/3,T] T.. The costs for a2 and ag are defined as
5

---

No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
[(as)
9t.1
(((22)
9t.1 (02)
[((())
St.1 (4z)
27/3
Figure I: Reward and costs of each arm of the instance employed in Example 5.2
how such approach can be extended to the case of general constraints.
We remark that the self-bounding lemma shows that, if we choose OGD as Algp, together with a carefully defined learning rate of
6. Self- Self-Bounding Lemma
JJorr = ( max Re (T (I,,,TT)) VT))
One crucial difference with the previous literature is that the feasibility parameter not known priori, and thus we cannot directly bound the range of the Lagrange multipliers as in BwK. At high level we want that, regardless of the choices of fi and 9t, the i norm of the Lagrange multipliers is bounded by a quantity that depends on the (unknown) parameters of the instance. However, for this to hold we need that the primal algorithm A go is (almost) scale free, i.e. that its regret scale quadratically in the unknown range of its reward function Formally:
then the ---orrm of the variables )e is automatically bounded by the reciprocal of the feasibility parameter, even if the feasibility parameter is unknown to the learner. This is the central result that allows to build algorithms that work without knowing Slater's parameter.
The proof relies on the key observation that Lagrangian multipliers jointly affect the primal utility but evolve inde- pendently. Thus, we need to reason about the joint behavior of the Lagrangian multipliers and look at their & norm. In particular, the proof proceeds by contradiction (see Ap- pendix B the full proof): if the Lagrangian multipliers exceed certain threshold, then they must have remained "large" for an extended period of time (Equation (3) in the Appendix). Then, we leverage the scale-free property of the primal regret minimizer, along with its regret bound relative to the feasible action that satisfies the constraints (Equation (4)). establish that the cumulative primal utility is large over such interval (Equation (G)) However, this is in contradiction with the fact that the dual utility is also large (because of the growth of the Lagrangian multipliers, see Claim B.4. The proof of Claim B.4 is particularly in- volved, as it needs to analyze the separate behavior of the Lagrangian multipliers relative to different constraints. In- deed, it is possible for the norm of the multipliers to increase without having all individual components growing. This makes it nontrivial to conclude that the dual utility must have increased as well.
Definition 6.1. For any c 2 1, we say that Alg, is a c- scale-free and weakly-adaptive regret minimizer if, for any subset of rounds = [t,.t]] S [T]. with probability at least 1 - it holds that
R((()) S L RR (X),
where the maximum module of the primal utilities is su |uβ (z)l =: L, and Rd (2)) depends only on T' 5 and X, and is non-decreasing in the length of the time horizon T.
Now, we show that online gradient descent (OGD) (Zinke- vich 2003) with a carefully defined learning rate yields the required hoff-bounding property both in the stochastic and adversarial setting.
Lemma 6.2 (Self-bounding lemma). Let Toxo
(800- - m max (RT,,()), ETT,))) then if Alg, is OGD on the set D = En and the primal algorithm Alge 2-scale-free and has brobbbbrobabiiity weakly adaptive regret bound Re,, (X),, then with probubility at least 6:
Remark 6.3. Even in the simplest instances of bandit prob- lems one has T0 TT,((())) = ((VT) and, therefore, we can assume that Mou Ô ((mR T. T. (2))
13m
max 1E12
||
Remark 6.4. We will work with 2-scale-free algorithms, which suffice to obtain the desired guarantees for our frame- work. We observe that scale-free algorithms would yield tighter bound of 1/p in the Theorems 7.2 and 7.3 and a simpler analysis of Lemma 6..2 However, scale-free free algo- rithm are much more difficult to find and this would limit the extent to which our framework can be applied. On the other
P
where p = Paáy or p Pstoo depending on the setting and ET,8 = / 16T log (2T/6).
Usually say that an algorithm is scale-free Orabona & Pal (201)) if its regret scales linearly in the (unknown) range its rewards, Le,, 1-scale-free with our definition.
6

---

No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
hand, 2-scale-free algorithm seems be more abundant (see, e.g., Section D Indeed, as we show in Section 8 it is
8. Applications
In this section, we show how our framework can in- stantiated handle scenarios such as bandits with general constraints, as well as contextual bandits with constraints (i.e, CBwLC). Thanks to the modularity of the results de- rived in the previous sections, we only need to provide an algorithm Algp which is 2-scale-free and weakly adaptive for a desired action space X' and rewards uf
usually the case that setting the learning rate independent on the scale of the rewards provides A-scal-ffeeness, We leave such characterization to future research.
7. General Guarantees
First, we exploit Lemma 6.2 to bound the total violations of the framework.
8.1. Bandits with General Constraints
Theorem 7.1. Let Alg, be OGD with learning rate y as in Lemma 6.2 and let Aig, any 2-scale-free algorithm with no-adaptive regret. Then, with probability at least 1 -,,, it holds that
In this setting, the action space is X = [K]] Castigliin et al. (2023) showed that the EXP 3 3-8 IX algorithm introduced by Neu (2015) can be used as Alg=, since guarantees sublinear weakly adaptive regret in high probability, and is 2-scale-free.
V1 = (
m R' FTS(X))
where p= Padr in the adversarial setting and Pstoc in the stochastic.
Theorem 8.1 (Theorem 8.1 of (Castiglioni et al. 2023 EXP3 SIX instantiated with suitable parameters guaran- lees that, with probubility at least 6 that
Moreover, the proof of Theorem 7.1 can be easily adapted to show that the violations of any constraint E [[]]] is bounded on any interval [t] with & [7].
sup R7(X) O (V 1-(t,all
Now, prove that the framework, with high probability, yields optimal guarantees in both stochastic and adversarial settings. We start with the adversarial setting, for which the following result holds.
Thus, by applying Theorem 7.1 on the violations, and Theo- rem 7.2 and Theorem 7.3 on the adversarial and stochastic reward guarantees respectively, we get the following result:
Corollary 8.2. Consider multi armed bandit problem with constraints. There exists algorithm that w.h.p. guar- antees, in the adversarial setting, violations at most and
Theorem 7.2. If Algg is OGD with learning rate noeo and domain D := R0 and Alge is 2-scale-free, then, in the adversarial setting, with high probability:
m KT)
((
2
Rew 2 Pady Opt Ō
m
R RTTx()))
1 Padv
(povv) paov
Rew
Padv Opt
δ
( m
KT
1+ Pady
PAdv
On the other hand, for the stochastic setting can prove the following result:
while, in the stochastic setting, it guarantees violations at most δ
/T and reward at least
Theorem 7.3. If is OGD with learning rate Noco and domain D = Ry and Aig, is 2-scale-free, then in the stochastic setting, in high probubility;
Potce
Ō Ō m
Rew 2 Optstoc
KT
P5t0c
( m
Rew 2 Opt stoc -ō
((m
R [x))
8.2. Contextual Bandits with Constraints
PStac
Following Slivkins et al. (023a),, we apply our general framework to contextual bandits with regression oracles. In this setting, the decision maker observes context 24 E Z from some context set Z, where 2, is possibly chosen by an adversary. Then, the decision maker picks its decision a from action set A. Then, the reward is computed as a function of the context and the action, i.e., ft Z x A + [0, and similarly for the con- straints g. 2 x A + [-1,1]mm. At each f, fe and g: are drawn from some distribution. More precisely, there exist class of functions and f.G. 9 E F such that for all
Any algorithm with vanishing constraints vi- olations can be employed to handle also BwK constraints. In such setting, the learner has resource-comsumption con- straints with hard stopping (i.e., once the budget for re- source is fully depleted the learner must play the void action until the end of time horizon). This does not yield any fundamental complication for our framework. Indeed, we could introduce an initial phase of o(T) rounds in which the algorithm collects the extra budget needed to cover potential violations, before starting the primal-dus procedure.
Remark 7.4.

---

No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
Algorithm 2 Primal-Dual Algorithm
and the performance of the regressor is evaluated on the basis of its prediction for the tuple (zt, at). The online re- gression oracle O is updated with the labeled data point (Ze, oe, fe(2e, at)). Overall, its performance is measured by its cumulative E2-error:
for Contextual Bandits
1: Input: Al and Algp-
2: for [. = 1,2,...,7 T do
3: Observe context Ft
4: Dual decision: X; + Algo
5: Primal decision:
Err(O,) = E (f(t,)a)-F(s,,a))) ai)) LE|T]
6: Og < (z,)
7: Observe: fa(Ze, ar) and ( az)
8: Primal update: feed u, (at) to Algg. where
Each online regression oracle (O:) works analo- gously, and its performance is measured by Err(O,) = Exery (0r (z), - ((=),a)))²
9: ui (at)= at) (> (z,, az))
10: Dual update: feed up to Alg,, where
10:
(A(A)= Je( uz) + (X, (z,, dz))
11: end for
By combining the online regression oracles O, and [Oskee[m) we can build an online regression oracle O2 for the Lagrangian which outputs regressors 2. x A + R defined as:
Algorithm 3 Primal Algorithm for Contextual Bandits
1: Input: Learning rate The
2: Get regressors from online regression oracles:
C,(2,a) =
fe((z, - (Ae, gr a)), ((2,0), Nx) ) (()
3: f O,, and Ir,i < O for all i E [[]]
4: Observe context 2n and dual variable A
while we define ((2,a) == f ((2, X²). The fg-error of c can be bounded via the following extension of Theo- rem 16 in Slivkins et al. (002b))
5: For all a E A compute (a(a)= == ( Ac)
6: Compute& & E A(A) as:
Ee(a) = (Ite + The (max (d) - La(aa) -1
Lemma 8.3. The error of O2 can be bounded as
D. Pe is such that E. E ((A)
Err(O2) S 22Er)(0))+
sup
Σ Err(O,). rElmm
7: Sample 0₂ Et and return it.
[E[T]
8: Update online regression oracles:
9: Feed (ze, ar fe(z, ac)) to O,
The fundamental idea of (Foster & Rakhlin 2020 is to reduce (unconstrained) contextual bandit problems to on- line linear regression. Recently, this ideas was extended in (Slivkins al., 2023a Han et a 2023) in order to design primal algorithm Algp capable of handling stochastic contextual bandits with constraints (see Algorithm 3).
10: Feed (ze, at. St.5 (2,, at)) to O, vi e [m]
(z,4) E 2 2x x it that [[/a(z, (2,()zzzzzza a)]z,a] = f(z, a) and (2,,((2)))2,,d a] = g((2, a) for i e [m].
We slightly modify the primal-dual algorithm to handle contexts. In particular, Alg, gets to observe context 2 before deciding their action. Formally, machinery introduced in Section by taking X' as the set of deterministic policies II = { Z
To apply Algorithm too our framework we need to find an algorithm Algp which is 2-scale-free and weakly adaptive with high probability. We extend the result of (Foster & Rakhlin 2020) to prove that their reduction actually satisfies the required guarantees.
use the
+ A). Then, of (T²) = (())),(())))))>>>>.))))))))))))) (Ae. (z)))) and the action a, is computed through ny returned by the primal algorithm. Although this choice transforms the contextual framework into application of the framework introduced in Section 3 in practical terms, it is simpler to think of a the direct output of Alg; upon observing the context 2,. The extended primal-dua framework is sketched in Algorithm 2
Lemma 8.4. Assume that max(Err Err(O,)) < Err. Then, we have that Algorithm 3 with t/p VKT guarantees that
sup R7(II) = -m(m (m-EEr Err L?? VKT) 1=]6,da]
We assume to have m + 1 online regression oracles (O,, O,,..., Om) for the functions f and ....... 9m. re- spectively. The regression oracle O, produces, at each t, a regressor| f. E F that tries to approximate the true re- gressor f. Then, the oracle is feed with a new data point, comprised of a context 2t 2 and an action a E A,
with high probability, where L == suPte I wen |uf (T)).
Equipped with a 2-scale free algorithm that suffers no adap- tive regret with high probability, we can combine Alg, with the results of Theorems 7. to 7.3 to prove the first optimal guarantees for CBWLC with adversarial contexts.
8

---

No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
Corollary 8.5. Consider finctional class F and an on- line regression oracle that guarantees Ez-error Err. There exists algorithm that w.h.p. guarantees violations at most Ô m² KT and reward at least
References
Abbasi-Yadkori. Yadkori, Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Agarwal, A., Hsu, D., Kale, S., Langford, J., Li, L., and Schapire, R. Taming the monster: A fast and simple algo- rithm for contextual bandits. International Conference on Machine Learning, pp.
Rew
Pady Opt Ó
Err Prav
m
KT
4 PAdv
in the adversarial setting, while it guarantees violations at most Ô
PMLR, 2014.
m² ErIVKT) and reward at least
Agrawal, S. and Devanur, N. Linear contextual bandits with knapsacks. Advances in Neural Information Processing Systems, 29, 2016.
Patoo
m
Rew 2 Optsroe
Ō
Err Pstoc
KT
Agrawal, S. and Devanur, N. R. Bandits with concave rewards and convex knapsacks. In Proceedings of the fifteenth ACM conference on Economics and computation, pp. 989-1006. ACM, 2014.
in the stochastic setting.
Foster& & Rakhlin (2020) includes many examples of func- tional classes F that have good online regression oracles, meaning that their emorr is subpolynomial in the time horizon T. We report here some notable mentions for completeness.
Agrawal S. and Devanur, N. R. Bandits with global convex constraints and objective. Operations Research, 67(5): 1486-1502, 2019.
If F is finite set of functions we have that Err Ollo [F]), which comes from using as regression oracles the Vovk forecaster (Vovk 1995). Another important exam- ples is the case in which
Agrawal, S., Devanur, N. R., and Li, L. An efficient al- gorithm for contextual bandits with knapsacks, and an extension concave objectives. In 29th Annual Confer- ence Learning Theory (COLT), 2016.
the class of linear functions, i.e., F {h(2, a) (za, 0) / IRd ||0||2 S 1).ie, i.e., each actions a is associated with known feature vector zu Rd which generates the reward/costs trough unknown param- eter that characterize the linear function. Here, there exists a online regression oracle which provides f--error Err = (TTo)()/)) (Azoury& Warmuth 2001).
Auer, P., Cesa- Bianchi, N., Freund, Y., and Schapire, R. E. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1 22(1):48777, 2002.
Azoury, K. S. and Warmuth, M. K. Relative loss bounds for on-line density estimation with the exponential family of distributions. Machine learning, 43:211-246, 2001.
Acknowledgements
Badanidiyuru. A., Kleinberg, R., and Slivkins, A. Bandits with knapsacks. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013, pp. 207-216. IEEE, 2013.
Funded by the European Union. Views and opinions pressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the Eu- ropean Research Council Executive Agency. Neither the European Union nor the granting authority can be held re- sponsible for them.
Badanidiyuru, A., Langford, J., and Slivkins, A. Resource- ful contextual bandits. In Conference on Learning Theory, pp. 1109-1134, PMLR, 2014.
This work is supported by ERC grant (Project 101 101166466 PLA-STEER), by the FAIR (Future Artificial Intelligence Research) project, funded by the NextGenerationEU pro- gram within the PNRRPE-AI scheme (M4C2, Investment 1.3, Line on Artificial Intelligence), and by the EU Horizon project ELIAS (European Lighthouse of AI for Sustainabil- ity, No. 101 120237).
Badanidiyuru, A., Kleinberg, R., and Slivkins, A. Bandits with knapsacks. J. ACM, 65(3), 2018.
Balseiro, S., Kroer, C., and Kumar, R. Online resource allo- cation under horizon uncertainty. SIGMETRICS Perform. Eval. Rev, 51(1):63-64, 2023.
Balseiro, S. R. and Gur, Y. Learning in repeated auctions with budgets: Regret minimization and equilibrium. Man- agement Science, 65(9):395--3968, 2019.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Balseiro, R., Lu, H., and Mirrokni, The best of many worlds: Dual mirror descent for online allocation prob- lems. Operations Research, 2022.

---

No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
Bernasconi, M., Castiglioni, M., Celli, A., and Fusco, F. Bandits with replenishable knapsacks: the best of both worlds, arXiv preprint arXiv:2306.0888 2023.
Han, Y., Zeng, J., Wang, Y., Xiang, Y., and Zhang. J. Opti- mal contextual bandits with knapsacks under realizability via regression oracles. In International Conference Ar- rificial Intelligence and Statistics, pp. 5011-5035. PMLR, 2023.
Bietti, A., Agarwal, A., and Langford, J. A contextual bandit bake-off. The Journal of Machine Learning Research, 22 (1):5928-5977) -972, 2021.
Hazan, E. Introduction to online convex optimization, vol-
ume 2. Now Publishers, Inc., 2016.
Castiglioni, M., Celli, A., and Kroer, C. Online learning with knapsacks: the best of both worlds. In Interna- tional Conference on Machine Learning, pp. 2767-2783. PMLR, 2022a.
Hazan, E. and Seshadhri, C. Adaptive algorithms for online
decision problems. In Electronic colloquium on computa- tional complexity (ECCC), volume 14, 2007.
Castiglioni, M., Celli, A., Marchesi, A., Romano, G., and Gatti, N. A unifying framework for online optimization with long-term constraints. In Advances in Neural Infor- mation Processing Systems, volume 35, pp. 33589-33602, 2022b.
Immorlica, N., Sankararaman, K. A., Schapire, R., and
Slivkins, A. Adversarial bandits with knapsacks. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, pp. 202-219. IEEE Computer Soci- ety, 2019.
Castiglioni, M., Celli, A., and Kroer, C. Online bidding in repeated non- non-truthful auctions under budget and ROI constraints. arXiv preprint arXiv:2302.00 200.00/00, 2023.
Immorlica, N., Sankararaman, K., Schapire, R., and Slivkins, A. Adversarial bandits with knapsacks, J. ACM, 69(6), 2022. ISSN 0004-5411.
Kesselheim, T. and Singla, S. Online learning with vector costs and bandits with knapsacks. In Conference Learning Theory, pp. 2286-2308 PMLR, 2020.
Celli, A., Castiglioni, M., and Kroer, C. Best of many worlds guarantees for online learning with knapsacks. arXiv preprint arXiv:2202.137100 2023.
Kumar, R. and Kleinberg, R. Non-monotonic resource utilization in the bandits with knapsacks problem. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Chu, W., Li, L.,, Reyzin, L., and Schapire, R. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208-2022 224, 2011.
Li, L., Chu, W., Langford, J., and Schapire, R. E. A contextual banddi approach to personalized news article recommendation. Proceedings of the 19th interna- tional conference on World Wide Web, pp. 661-670, 2010.
Feng, Z., Padmanabhan, S., and Wang, Online bidding algorithms for return-on-spend constrained advertisers. In Proceedings of the ACM Web Conference 2023, pp- 3550-3560, 2023.
Liu, S., Jiang, J., and Li, X. Non-stationary bandits with knapsacks. Advances in Neural Information Processing Systems, 35:16522-16532, 2022.
Fikioris, G. and Tardos, É. Approximately stationary bandits with knapsacks. In Proceedings of Thirty Sixth Confer- ence on Learning Theory, volume 195, pp. 3758-3782, 12-15 Jul 2023.
Neu, G. Explore more: Improved high-probabilityy regret bounds for non-stochastic bandits. Advances in Neural Information Processing Systems, 28, 2015.
Foster, D. and Rakhlin, A. Beyond ucb: Optimal and ef- ficient contextual bandits with regression oracles. In International Conference on Machine Learning, pp. 3199- 3210. PMLR, 2020.
Orabona. and Pál, D. Scale-free online learning. Theoret- ical Computer Science, 716:50-69, 2018
Foster, D., Agarwal, A., Dudík, M., Luo. H., and Schapire, R. Practical contextual bandits with regression oracles. In International Conference on Machine Learning, pp. 1539 1548. PMLR, 2018.
Simchi-Levi, D. and Xu, Y. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits un- der realizability. Mathematics of Operations Research, 47(3):1904-1995 1931, 2022.
Gaitonde, J., Li, Y., Light, B., Lucier, B., and Slivkins, A. Budget pacing in repeated auctions: Regret and efficiency without convergence. 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251, pp. 52, 2023.
Slivkins, A., Sankararaman, K. A., and Foster, D. Con- textual bandits with packing and covering constraints: A modular lagrangian approach via regression. In The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, volume 195, pp. 4633 4653,4656, 2023a.
10

---

No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
Slivkins, A., Sankararaman, K. A., and Foster, D. Con- textual bandits with packing and covering constraints: A modular lagrangian approach via regression. In The Thirty Sixth Annual Conference on Learning Theory, Pp. 6656.4656. PMLR, 2023b.
Slivkins, A. et al. Introduction multi-armed bandits. Foundations and Trends@ in Machine Learning, 12(1- 2):1-286, 2019.
Vovk, V. G. A game of prediction with expert advice. In Proceedings of the eighth annual conference on Compu- tational learning theory. pp. 51-60, 1995.
Wang, Q. Yang, Z., Deng, X., and Kong, Learning to bid in repeated first-price auctions with budgets. In Proceed- ings of the 40th International Conference on Machine Learning, ICML'23, 2023.
Wei, X., Yu, H., and Neely, M. Online primal-dual mir- ror descent under stochastic constraints. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(2):1-36, 2020.
Yu, H., Neely, M., and Wei, X. Online convex optimization with stochastic constraints. Advances Neural Informa- tion Processing Systems, 30, 2017.
Zinkevich, M. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (ieml-03), pp. 928 936, 2003.

---

No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
A. Omitted Proofs from Section 4 and Section S
(a)
(a)
T/2
T
T
(a)))
(a)
-
88p
T/2
T
Figure 2: Lower bound adversarial setting: rewards and costs the two instances and B.
Theorem 4.2 (Lower bound adversarial setting). Consider the family of all adversarial instances with X' = {ai. 02). each characterized by a parameter Padv and optimal reward 2pt Then, no algorithm can achieve, on all instances, sublinear cumulative violations E. [[)] o(T) and EB < 1 + 1/paar.
Proof. We show that, forall e > 0 and 5 E (0, 1), there exists two instances such that it impossible to obtain B(V(T)) SET and
Opt Paav (1 61 2
1 Padv
E Reww
in both instances. The two instances are denoted by A and B respectively, with x' (ar, (2) and sequences of inputs of length T. The two instances identical in the first 7/2 rounds. Rewards in instance are, for each E (f and (a,) = 1[t s T/2]. On the other hand, in instance B we have f. (a2) O, and (a1) 1 for all t [T]] Costs for the first instance A are define as
(a))) = { -1
if S T/2
otherwise
and gी (a2) -p for all t [T]. In the second instance B, costs (0() 1 for all t e [T], and
(a2) =
-p
if T/2 otherwise
8p
for some 8 > 0. The two instances are depicted in Figure
Let N be the expected number of times that action is played in rounds [T/2]. that is
N =
Σ E I. = ai]
Ea = ai),
1E[T/2]
1//3/3]
where expectation is with respect to the algorithm's randomization. We observe that the algorithm plays in the same way in both instances up time T/2, they are identical (formally, the KL between instance and B is zero in the first 7/2 rounds). Then, we have that the optimal action in instance is play deterministically action 01 Therefore, Opt T/2. The expected reward in instance A comes only from the number of plays of a₁ in the first T/2 rounds: [Ree]]] N. On the other hand, call M the expected number of times an algorithm plays action in the last [T/2, T] rounds of instance B, that is
M =
E² =1]
[E[T/2,T]
We have that, in order to have [²)) & eT violations in the second instance, we need to play a1 a small number of times:
T
M + N - p (3
(T - N)) s ET,
M 8p
2
which yields
T(p(E + +1) 2c)
N <
2(p 11)+1)
12

---

No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
Then, get that
Opt Adv
1+1 p(1 + 2c
E Rew
which concludes the proof since Piay = p.
Even if Alg, and Algo suffer regret less than or equal then zero, the primal-dual framework achieve sublinear constraint violations.
Proposition 5.3. Consider the instance of Example 5.2
Proof. Consider the instance described in Example 5.2 and consider an algorithm Algp for {ai, 02 as) such that Tt d3 for E [T/3], while I, a2 for [T/3, T Moreover, consider algorithm Alg, instantiated D [0, M).
with M l/p, that plays X for all [2T/3]. and A M for all t [2T/3, TT]
We start by analyzing the primal regret achieved by Algg:
R = sup Σif((z) f((x)) Ae(9)2(1)) 1x,1(x)))] EE LE[T]
sup
Σ
[f(()) (x)r,(10)]
2 T
MpT
zEX tE|T]
3
3
T
Σ [f((ai) - )..r1
(Mp 2)
TE[T]
T
pM
+ (Mp - 2)
3 3
T
(2Mp - 2) 00
3
where we replaced the sup with the utility at a₁ since M Z 1/p. Moreover, the dual regret is such that
R = sup X
Σ
(A gx,1
1E[27/311]
T (A M) p=
sup XE(O.M]
However, for a suitable choice of p. the violations are linear since
Vi(T)= = Σ gr,1
P = Q(T).
LE[T] 3
This concludes the proof.
B. Proof of Lemma 6.2
We start by providing the following auxiliary lemmas.
Lemma B.1. Let y: E 17 be generated by OGD with learning rate n and utilities y + g.). where l|golloo S 1 for all
t [[]] Then:
|1 S m n
Proof. The update of the i-th component of yo+1 can be written
1 = max (0, Vr.i 7)9t,))
If gt.. 2 0 then the update can be simplified to 1++1,1 = Vr + 79., I y: + y7. If gr, < 0 then Fr+1, 2 Ve,i + 79t.. 21. Thus |yt+1,5 Vr,sl < y for all E [m]] By summing over all component we have that || - yell1 S m 17. By triangular inequality we have the desired statement.
13

---

No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
Lemma B.2. [Chapter 10 Hazan ( [2016]] For any L1, l2
[T] with < l2, it holds that if Xe is generated by OGD with
learning rate dj > 0 on set D, then:
Ri ((A))
+ 2.m..
2nj
with probability probability one on the randomization of the algorithm, i.e., = O. Moreover it also holds component-wise. for all X 2 0:
(A (A-
(a (1)) I
2 nT.
2n
Lemma B.3, In the stochastic setting, for any A(X) and (0, 11, with probability at least 1 8, it holds that:
Σ
E. Eowe ((
Σ
Enng
ET. and
1ET
SET
ERWE [fc(z)] 2
Σ
Bxwe [f(x)
ET
(2)
IEl
TE!
for any interval 1 = [2] S [T], where ET, = v 16T
27 5
and M
sup |||||
1E[2]
Proof. We start by proving that the all the inequalities of Equation
! holds simultaneously with probability 1 - 8/2.. We
have that given I = [t,, t2] S [T]. with probability at least 6/(27))
27
21
E (2,,, 9 (x))
Σ SET
Eawe 0. s M Vy log
I M V
16T log
where the first inequality holds by Azuma-Hooffdiae inequality. By taking a union bound over all possible intervals (which are at most ) obtain that all the first set of equations holdswith probability at least 1 5/2.
Equation 2 can be proved in similar way. Indeed, for any fixed interval [t,, [2] C [2'. and for any strategy mixture & E (X)), by the Azuma-Hoefiin Hoeffding inequality we have that, with probability at least 1 - 8/(2x²), the following holds
2T
2T
Exns [f(x)]
-E [f(())]
2
4T log
8
By taking union bound over all possible 2 intervals, we obtain that, for all possible intervals J, the equation above holds with probability 1 1-- 6/2.
The Lemma follows by a union bound on the two sets of equations above.
These auxiliary technical lemmas are used in proving the following result.
Lemma 6.2 (Self-bounding lemma). Let new == (800 - m max { R T,,(X), Er,s)) then if Alg, is OCD on the set D = Bn and the primal algorithm A Alg, is 2-scale-free and has a high-probubility weakly adaptive regret bound R (T,) then with probability at least 1 8:
13m
max [7]
| S
where p == P2av or p = Pstoc depending on the setting and ET, == /16T log (2T/8).
Proof. Let c = 2 and 02 == 13m and any learning rate 7, for OGD with y I Moss- By contradiction, suppose there exists a time such that |Aell1 2 /2/ p. and let to E [T] be the smallest t for which this happens. We unify the proof of the adversarial and stochastic setting. particular, let p Paav if the losses (ft, 9r) are adversarial, and let p = Pston if (fe, gt) are
14

---

No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
stochastic with mean (f.g). The extra stochasticity coming from the environment in the stochastic setting will be handled through Lemma B.3 In order streamline the notation, define Er,8 == / log (2T/5).
Then, let 1 E [t be the largest time smaller than t2 such that ||,, 2 d and || +
Step 1. First, need to bound || |l and || |l. To do that, we exploit Lemma B.1 In particular, by telescoping the sum in the lemma, we obtain that:
\12 11 [2 mmm(t2 -1).
Moreover, by the definition of Xe, and Ae2 we have:
Ar,l1 1 | mn S C
+ mn
p
and similarly
< 12,112 S | + my S p
+ mn.
P
This, together with the inequality above, yields
c S t2 t1. 21mp
(3)
Step 2. The range of the primal utilities in the turns [tt,, t2] can now be bounded as:
sup x
|x((x)1 5
sup
{lf((z))
+ -Allll (z)
02
+
m
P
12m + 1
+
0
14m
L.
Now, by the assumption that Alg, is weakly adaptive and 2-scale-frree, we obtain:
R R (X) s R. 1,))),))
which holds with probability at least 1 - 8.
we apply the primal no-regret condition above for strictly safe strategy 8" E A(X) we have
Σ [E]
Cs (zr, 2 Exngo
Σ (E
(e, (z, Ar) - LL2RE (.))
(4)
Moreover, by definition of safe strategy we have that in the adversarial setting Eaner [3), S -Padv for all i E [m]]] and t e [[t,, te]l while in the stochastic setting by Lemma B.3 it holds
Σ re(()ta]
Exngo (A).,
Σ
EEneo (At,, + M Fr,,8
re]tital
and
Eg-go (T.(E)) < -Patoe
Wi [m],
where we recall that Fy,5 / 167 log (2T/)) and M sup |All1-
tE|T]
15

---

No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
Therefore, lower bound the first term of the right-hand side of Equation
the stochastic setting as:
Σ
Le Ac)
= Beng"
Σ
fc(x) - (Ar.g((z))
reltnaal
2 -Bene"
(()r)
-Ezug" [(e,g(z))]
sup [E|T]
|All2
E1,5
Potoc
Aelli
sup [E[T]
|||||
ET
(00e
C2
Pstoc
Aelli
+ man
Er,5
Pstoc
62
+ mn) ETT
2 (1222 - (
Psto=
In the adversarial setting we can more easily conclude that Ex settings it holds that:
E
Ling (a de)) 2 c1(22 - -1) and thus in both
se[11,t2]
02 10 + +mn) ET.
Exweo
E
Σ te
to 2r)
(1122-11)
Pstcc
Combining the two incqualities of Equation (4) and Equation 5). we can conclude that the overall utility of the primal algorithm Alg, can lower bounded by:
u (at) 2 c12 - 41) - L T, - ( mis) ET.s
Σ tE
(6)
Now, we need an auxiliary result that we will use to upper bound the left hand side of the previous inequality.
Claim B.4. It holds that:
Σ
(Ae. (e())()))) 2 m
2p²n
Then, we upper bound the left-hand side by using Claim B.4
Σ of (xx)
Σ
Li At)
Σ [f((1)) - (e (x.)))
S (12 (1) 2p2111
Thus, combining Equation 7 and 6
1/ 4 < L (,(0) - 2p2
C2 + mn) ET,
+
Combining it with Equation
one obtains that:
1
(127 (.)))
m
( 02 mm Er.))
2mmp < ci 1
2p2m
p
16

---

No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
which gives as solution rj
m² -2--13m 13mp
Which is contradiction since:
302m R (. 4-22222200 2m2 BappErrCe a
1
m - 2p + 13mp
7 S FOGD
800 m max { [Te T2)), ET,8}
392m RV T + 2mmpET,s + 13m)
Thus, we can conclude that | & c2/p for each t [T]]
Now, we provide the proof of Claim B.4
Proof of Claim B.4 We define 4 the last time in [2,,4]] in which Aiaa = 0, or b,, 41 if Xe, > 0 for all E [[1, [2]
Formally:
1 max t1
sup 7 S =E[t=]A>,,=0)
are now going to analyze separately for E [m]] the rounds [4,, [1il] and the rounds [[,,5 12]
Phase First, analyze the rounds [ti, 81.a]. By definition, it can be either that Xt, 0 f1.1 tj. In the latter case, f1&1 and the dual algorithm incurs zero regret. In the former case, we can use Lemma B.2 and write that the regret
over the interval with respect to X; = 0s is
1 1 nT
(e. + 2 + nT.
S
Σ Ae
(x1)) +
Σ 1E[G,6.
(8)
2m 2
2n
Phase 2: Now, we consider the rounds [f,,; te]]. We take X defined as follows: X; = for all [m]]
Let A = A1255 A Due to the definition of 1,,6 gradient descent never projects the multiplier relative constraint i, and we can write that
A
(0,((01)=
1
and, therefore,
Σ xx(,((0)) = A
(9)
pr)
Now we can use Lemma B.2 find that:
(2; - >o
Σ xg))()))s
Σ (x +
21
12
Combining with Equation p yields the following
(X A
)2
1
2 T..
(10)
pm
2m
Combining Equation 10 and Equation
g we obtain:
A
(X5 >
X2
Σ
2
TT
pn
2m
21
teltt
(2;)² + X2
X2
7/..
(T]
2n
2n
17

---

No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
Now, by summing over all i [[m]] and by letting X; be the vector that has A its i-th component, get:
Σ
(ee, (e)))) 2 | ||
1a
1
(I
12,,
1 (as S 1/vV))
PM
20j
Arg
|||
1
(1
+
21
12) -
(|a|)) 2 c2/p and || 11 S [12, IIi)
1
pM
2n
02
01
1
m
)
)
+
mn
+
+ mn
p&
PM
2T
p²
02
01 +1
m
2(c1
+ +12
(1) S 1/om)
1&
1&
2p
2p
202
24 m
2p²
2p
where the last two inequalities hold due to the choice of parameters in the proof of Claim B.4 that is c1 = 2 and C2 = 13m. This concludes the proof.
C. Omitted Proofs from Section
Theorem 7.1. Let Algo be OGD with learning rate 1) in Lemma 6.2 and let Al Al any 2-scale-free algorithm with no-adaptive regret. Then, with probability at least - 6, it holds that
VT = δ (T RC T RTT,(())
m²
where p Paávv in the adversarial setting and Pstoc in the stochastic.
Proof. The update of OGD for each component E [m] is A441, = (Ne, + ng..
Thus:
A411, 2 Ae, + (oou),,
and by induction:
X411, 2 d0,i + MoGo Σ --.(xx))
By rearranging and recalling that Ao, = 0 we obtain:
Σ (x,( S AT <
Ar+illi
Moon
1E
Moreover, by Lemma 6.2 we can bound |Arll & 13m which holds with probability at least 1 Thus, with probability
least 1 8, it holds:
13m
VT max Vi(T) S TE[mm]
MouuP
The proof is concluded by observing that 1Jaac = ((mR² (x))
Theorem 7.2. If Algp is OGD with learning rate noen and domain D = Rm 20" and Algg is 2-scale-free, then, in the adversarial setting, with high probability:
-ō ((( Padv
Padv Opt adv
Re TTT,(2))
Rew
>
1 Padv
18

---

No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
Proof. Define x² X' such that:
Σ fi(x') = Opt EE[2
Now, consider randomized strategy & that randomized with probability a between and 5", where çe is any strategy for which Ez (xxa] S -Padv- This strategy exists by assumption. Formally, for any x E X the randomized strategy assigns probability to z:
{ ad.- (x) (1 (z)
Then, compute the component of the primal utility of & due to constraint i E [m]]] as follows:
E E
Σ (E|T]
(x))),(()))
Σ (x. + (-))E
Σ
(x))))(())
tE[T]
AE(T]
S a Σ
X - -1 Pn)rar
Σ Ad,i
1E[2]
LE[T]
S (a (1-a)) a))
Xt,i-
LE|T
Thus, setting a
Prov 14pade
we have that Exng Eieryy )
S 0, and Σ (Av.e(=x))) s O.
tE[T]
We now compute the reward of & for I+
Exwg
Σ Se(t))
Σ [(xx)++(1 (1-))+ Be
Σ Selar)
IE(T]
LE[T]
LE|T]
Padv
Opt
+ Paáv
Now, we consider the regret of Alg, with respect to & and we find that:
Li (Et, Ax) Σ [T
Σ EE|T]
Cr (x, Ae)
12 IP T,)
where L is the maximum module the payoff's of the primal regret minimizer, i.e., :- suP Ju (x)].
Exploiting the definition of Cra. (-)+) in the inequality above we obtain that:
Σ [e(x))) - (xt))) 2 ExwE LETT]
Σ fe(x) - (Ar,
L?. RE T.)
LETT]
E9
En
Σ f((x)
1,2 R x,(()
KETT
Paav
Opt
L T.(()
(11)
1 +
Prav
Then, lower bound the term
Σ tE[T]
(ee, ((x))) by using the dual regret of Alg, with respect to X' =0. -0. Indeed,
Σ -x--xx (xe)) s Rro(((1)))
[E|T]
19

---

No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
implies that
[T[T]
Combining with Equation
gives:
Σ f((x)) 2 +
Padv Opt 1.2 Te T R.rr(((X')))
Padv
EE[T]
Now, we use Lemma 6.2 which bounds I. s 2 13m and Lemma B.1 which we can use to bound R ({A²)).
Prov
In particular, rr (A*}) can be bounded with:
Rd. r. - TooD mo. mT,
and thus:
2
Rew
Σ f((z)) 2
Padv
Opt
676
R (,,((()
Bow m..
+ Padv
Padv
1E12
The proof is concluded by noting that TooO = Ô RR (.,)))))())--))
Theorem 7.3. If Alge is OGD with learning rate NJoo and domain D = stochastic setting, in high probability:
R 20 and Alge is 2-scale-free, then in the
-ō
(( m
((p55))) R
Festx))
Rew 2 Opt
Proof. By Lemma 6.2 we have that with probability at least 1 â we have that supteli1 Aelll S way S
13m
and in the same
Poras
1u [1
2 13m
Pstoc
Define & the best strategy that satisfies the constraints, i.e., Optssoc == T Bizng [f(x)] and [e=e(ār<x)] $ 0. The no-regret property of Algp with respect to gives that with probability 1 5 it holds:
Σ [f(())) - gxx)))
2 13m 2
2 Exng
Σ [fe(x) (Ac))(()))]
RR T,,(
-
PsLoc
tE|T]
> Exag
Σ
[f(x) (Ae.g(x)))
676
m
2
Rp (x) -2
13m Pstoc
ET,
Pstoc
TE[T]
T Opt 676
m
RR 1,6 (X)
26m
Er,b:
Pstoc
PScoc
where the second inequality follows from Lemma
B.3 with M
13m
Moreover, the no-regret property of the dual regret minimizer Algo, with respect to X 0, gives that:
- (z)))) < MT
Finally, we can combine everything from which follows that:
Rew 2 Opt - 676
m
RS (,a(
26m
ET.5 A.onm..
PSLOc
PatoG
The proof is concluded by observing that Nour = Ô (T,)())))- and Fr. = Ô(VT)
20

---

No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
D. Proofs omitted from Section g Lemma 8.3. The error of Og can be bounded as
2
Err(Oc) & 2Err(O)) +2
sup (E(T]
|Aell
Σ Err(O,).
sE[m]
Proof. Consider the following inequalities:
Err(Oz)) = Σ - (Le(z,, (x) -(((,,))
<E[T]
S Σ
(f((e))))) -((t,at))((()00))) a1)
+2
Σ ((A,,)(2), (Aig(zt, az)))² tE[T]
1E[T]
(By AM-GM inequality: 2ab I a² + 62 for a 62 0.)
-2-Err(Oj) +2 Σ ((),, - -2,,, a:)))
rE[T]
{2-Err(Or)+ +2
Σ
| (()((z)))) - g(2,, 11)
(a, b) S 1|a//1 11]llc))
LE[T]
$2-Err(O,) +2
sup [E[T]
Axeli
(1,, a.) -g(2); az)
:E[T]
-2-Err( EEr((O)) +2
sup | 11
Σ
Σ
(0e, az) - -c((zz a,))
[E[T]
tE[T] mm]
2 (2rr((O0)) +
sup [E[T]
|
Σ
Err(O,)
sm[m]
which concludes the proof.
Lemma 8.4. Assume that max(E)((O)) Err(O)) S Err. Then, we have that Algorithmt with me VKT guarantees that
sup R (II) = Ô (m Err 1.2 KT)
I= [t[tatlll
with high probability, where L == sue (T)).
Proof. Consider any interval T= [[1,,22) S [7]. Since the prediction error at each time positive, one trivially has that:
Σ
(Li(ze)aa) - E(z).a)) (Err(Oc).
tt]
Then, applying Lemma 8.3 we have that:
Σ rettntal
(Ce(ze, az) - ((2)aa) < 2EEr=(O))+2 +2 sup
|vl Σ Ezr(O,).
[E[T]
<c|m]
Moreover, by the assumption the errors of the oracles it holds that:
Σ tllt
(Li(zs) L(22,, ae)) 2 & 2m(1 sup EMrr)
(12)
rE[T]
21

---

No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
Note that we could pretend that the algorithm starts any time E [T]] and the same analysis of Theorem by Foster Rakhlin 2020
would hold, their algorithm behavior does not depend on its past behavior. Hence, the following holds:
R [ta (II = sup
Σ [E[((.12]
- - v.
tell
E [C((T(z))) Cx(T((z)))
sup
=en tE](1.a
Σ [C((T(Z))) Lx(ai]
sup
xell re[t1.11
(2T
2K T
2T2
$ 2
Err(Oc) + 4np log
+
27 2T log
8
n7
which holds with probability 1 - (
Thus, by an union bound, and combining it with Equation 12)
we obtain that:
2T
T 2T log
2T
& (II) S m= + sup +E]2]
| [Alr + 47p log
+
2K
1/2
which holds with probability 1 5/22. Finally, by tuming 7) VKT and applying an union bound on all the T2 possible intervals [[t t2], we obtain that with probability 5 it holds that:
R(g (I) < 504 m Err 1 1og((T2/))) KT. [=
sup
22


Reviews:
[{"review_id": "jDgTkQExKd", "reviewer": "Reviewer_5ZmK", "summary": "This paper studies the general constrainted optimization problem where the reward and cost functions can either be stochastic or adversarial. By extending the LagrangeBwK framework by requiring the primal & dual algorithms to be weakly adaptive in addition to being no-regret, the authors designed a best-of-both-worlds algorithm which doesn't require the knowledge of the Slater's condition constant $\\rho$. The results are exemplified for two constrained online learning problems.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### **On the competitive ratio**\n\nThank you for raising this possible source of confusion about the competitive ratio. The issue here is primarily one of nomenclature rather than our choice of a stronger benchmark. We agree that adding further clarification in the final version will be beneficial.  \n\nThe key distinction lies in the interpretation of $\\rho$ in our work versus its meaning in the BwK literature. In our setting, we normalize the constraint so that costs must remain below a fixed threshold of 0, whereas in the BwK literature, the costs are constrained by a per-round budget of $\\rho_{BwK}$.  \n\nTo see how our approach translates to the BwK model, consider how we would redefine the costs $g_t$ to solve BwK via our framework. Specifically, we could set $g_t(x) = \\frac{x^\\top c_t - \\rho_{BwK}}{1 - \\rho_{BwK}}$. Under this transformation, playing the void (``free’’) action in the BwK setting results in $g_t(0) = \\frac{-\\rho_{BwK}}{1 - \\rho_{BwK}} = -\\rho_{Adv}$, where $\\rho_{Adv}$ is what we called $\\rho$ in our paper. From this, it becomes evident that our competitive ratio of $1 + 1/\\rho_{Adv}$ is equivalent to $1/\\rho_{BwK}$.  \n\nWe thank the reviewer again for highlighting this potential source of confusion, and we will incorporate this clarification, including this short proof sketch, in the final version of the paper. \n\n\n### **On technical contributions**\n\nDue to space constraints, we have deferred all proofs to the appendix and instead focused on providing a clear and intuitive explanation of the key ideas in the main paper. We are pleased that the reviewer appreciated our efforts to make these concepts more intuitive and accessible (especially how Example 5.2 highlights the necessity of using adaptive regret minimizers). However, we respectfully disagree with the idea that our contributions lack technical depth. \n\nSeveral key components of our proof are far from straightforward. In particular, in Section 6, we discuss the self-bounding lemma, which demonstrates that the Lagrangian variables remain automatically bounded when using scale-free primal algorithms. We find the proof of the main lemma (Lemma 6.2) highly nontrivial, and we will include a sketch of the proof in the main paper using the extra page available in the camera ready. See the answer to Reviewer Ldsh for more details on the proof (that we will include in the final version of the paper).\n\nMoreover, we believe that handling general constraints is a highly non-trivial task.Indeed, many previous works on BwK have attempted to achieve similar results under assumptions as weak as ours. However, they have only partially succeeded, addressing the problem only in the stochastic setting [1,2,3,4,5]. Removing the knowledge on the Slater parameter is both important on the practical size and interesting from a technical standpoint, even more so when it comes from the elegant idea of using adaptivity to self-bound the Lagrangian multipliers. \n\nThese results are not only technically challenging but also highly relevant as they enable significant applications. In the paper, we highlight two key examples: bandits with general constraints and the contextual bandits with linear constraints problem recently introduced by Slivkins et al. (2023b). Both models have practical implications, including applications in autobidding for first-price auctions. Given the generality of our approach, it is likely that there are additional applications we have yet to explore.\n\n**References:**\n\n[1] Agrawal, Shipra, and Nikhil R. Devanur. \"Bandits with concave rewards and convex knapsacks.\" Proceedings of the fifteenth ACM conference on Economics and computation. 2014.\n\n[2] Agrawal, Shipra, and Nikhil R. Devanur. \"Bandits with global convex constraints and objective.\" Operations Research 67.5 (2019): 1486-1502.\n\n[3] Yu, Hao, Michael Neely, and Xiaohan Wei. \"Online convex optimization with stochastic constraints.\" Advances in Neural Information Processing Systems 30 (2017).\n\n[4] Wei, Xiaohan, Hao Yu, and Michael J. Neely. \"Online primal-dual mirror descent under stochastic constraints.\" Proceedings of the ACM on Measurement and Analysis of Computing Systems 4.2 (2020): 1-36.\n\n[5] Castiglioni, Matteo, et al. \"A unifying framework for online optimization with long-term constraints.\" Advances in Neural Information Processing Systems 35 (2022): 33589-33602.", "claims_and_evidence": "Looks convincing, although I didn't verify the correctness of every claim", "methods_and_evaluation_criteria": "Yes, they're consistent with previous ones in the literature", "theoretical_claims": "I checked the proof of Lemma 6.2 Appendix B and it looks correct. I intuitively understood Proposition 5.3 via Figure 1. Didn't check Theorem 4.1 and those in Sections 7 & 8.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "Looks like the observation that weak adaptivity can result in bounded decision variables can be used in other constrained optimization problems.", "essential_references_not_discussed": "Didn't see any obvious missing references", "other_strengths_and_weaknesses": "Strengths:\n\n1. The baseline for adversarial case is stronger than previous ones. The upper bound is complemented with a lower bound, showing that the seemingly bad $1+\\rho^{-1}$ competitive ratio is already the best one can hope if we do not want to incur $\\Omega(T)$ violations. -- but see also Q1.\n2. The idea why we need weakly adaptive properties in addition to no-regret is clearly depicted via Example 5.2. \n\nWeakness:\n\n1. The technical results are not explained, making it hard to understand why these technical results are of importance.\n2. Because of 1, it is unclear what is the main technical contribution of this paper. It seems to me that everything is based on the observation that \"a direct application of LagrangeBwK may result in super large dual variables; but if we additionally require the plug-in algorithms to be weakly adaptive, it works\". See Q2.", "other_comments_or_suggestions": "There's a typo in the citation of Lemma B.2.", "questions_for_authors": "1. Regarding the Strength 1, is the worse competitive ratio due to the stronger baseline? That is, if the baseline is instead the standard one in the literature (which requires average cost <= ...), what's the best competitive ratio one can hope? If applicable, does the performance of your algorithm have a better guarantee in this case?\n2. Is the understanding in W2 correct? What are the main technical contributions?\n\n---\n\nBoth resolved in authors' rebuttals. Updated score accordingly.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "McZ2SQcs8s", "reviewer": "Reviewer_w2eb", "summary": "The paper addresses the problem of bandits with general constraints, extending beyond the traditional bandits with knapsacks (BwK) framework. The authors generalize the setting where the learner does not know the Slater's parameter $\\rho$ and give an algorithm following the primal-dual framework.\nPrevious works (Balseiro et al., 2022; Castiglioni et al., 2022a) need to know the exact value of $\\rho$ to find the boundedness of dual multipliers.\nIn this paper, one key contribution is the \"self-bounding\" lemma for bounding dual variables if both the primal and dual algorithms are weakly adaptive.\nThe authors provide best-of-both-worlds guarantees (sublinear regret and constraint violations) and applications to contextual bandits with linear constraints (CBwLC). Theoretical results show competitive ratios of $\\rho/(1+\\rho)$ in adversarial settings and near-optimal regret in stochastic settings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**On the questions about the Theoretical proofs:**\n\nThanks for taking the time to carefully read our proofs. We really appreciate the effort.\n\n* Thanks. We meant to cite the following works:\n    - At line 660: Hazan, Elad. \"Introduction to online convex optimization.\" Foundations and Trends® in Optimization (2016). \n    - At line 1100: Foster, Dylan, and Alexander Rakhlin. \"Beyond ucb: Optimal and efficient contextual bandits with regression oracles.\" International conference on machine learning. PMLR, 2020.\n\n* Yes, you are right; $c_2$ should be 13m. \n* The confusion likely stems from our informal definition of $t_1$, which we agree could be improved upon. We will update it with the following more precise definition: $t_1$ is the largest time smaller that $t_2$ such that $\\|\\|\\lambda_{t_1}\\|\\| \\ge \\frac{c_1}{\\rho}$ and $\\|\\|\\lambda_{t_1-1}\\|\\|\\le \\frac{c_1}{\\rho}$. Therefore, $\\|\\|\\lambda_{t_1-1}\\|\\|\\le \\frac{c_1}{\\rho}$ holds by definition. Remember that the Lagrangian multipliers are initialized to $0$, and at time $t_2$ they reach $\\frac{c_2}{\\rho}$, which is strictly larger than $\\frac{c_1}{\\rho}$.\n\n**On the paper by Ding et. al (2013):** \n\nWe appreciate the reviewer for bringing this paper to our attention. We will include it in our discussion of related work on the stochastic BwK model. While the paper explores a variant of the stochastic BwK model, its connection to our work is relatively limited. Several key differences set the two settings apart: their setting assumes rewards and costs are generated i.i.d., whereas we focus on algorithms that remain robust even in adversarial environments; their costs are discretized; and their regret baseline is defined with respect to the stopping time of the algorithm rather than a fixed time horizon $T$. As a result, the guarantees they achieve (i.e., a regret bound of $O(\\log B)$) are not comparable to those in our setting. In particular, in the stochastic case, our framework aligns with the standard lower bound of $\\Omega(\\sqrt{T})$ from the (unconstrained) multi-armed bandit problem, making a direct comparison challenging.", "claims_and_evidence": "The claims made in this paper are clear and supported by proof in the appendix. However, there are some typos in the proof, and I listed them in the Theoretical Claims. If the authors can answer them, I will be convinced that the evidence is clear.", "methods_and_evaluation_criteria": "The authors use the Regret or Reward gap to the optimal strategy, which is standard in the Bandit area.", "theoretical_claims": "I have some questions on the Theoretical proof and I list them below:\n\n- line 660, missing reference in Lemma B.2\n- line 711, constant used in $c_2$ is 12, which does not match with 13 used in the lemma statement?\n- line 725 - 727, in the proof of Self-bounding lemma (Lemma 6.1), one step shown in the mentioned line is upper bounding $ \\| \\lambda_{t_1 - 1} \\|_1 + m \\eta \\leq c_1/\\rho + m \\eta$ because the inequality $ \\| \\lambda_{t_1 - 1} \\|_1 \\leq c_1/ \\rho $. I am not aware of any properties of $\\|\\lambda_{t}\\|_1$ and if it is not monotonically increasing with $t$,  $\\| \\lambda_{t_1 - 1}\\|_1$ can be larger than $c_1/\\rho$ since the definition of $t_1$ is the largest time between $0$ and $t_2$ for which $\\|\\lambda_{t_1}\\|_1 \\in [c_1/\\rho,  c_2/\\rho]$ and we cannot assume when $t \\in [0, t_1]$, $\\|\\lambda_t\\|$ is always smaller than $c_1/\\rho$. Correct me if I am wrong.", "experimental_designs_or_analyses": "No experimental designs are founded in this paper.", "relation_to_broader_scientific_literature": "The assumption used in this paper is weak and can be applied to many specific cases, such as multi-armed bandit (MAB) and contextual bandit (CB). The weakly adaptive regret bound for primal and dual problems is reasonable since many algorithms satisfy this property, like *EXP3-SIX* for MAB and *Vovk forecaster* for the finite function class. This paper can be used as a fundamental work to develop more realistic algorithms.", "essential_references_not_discussed": "The key contribution of this paper focuses on developing a near-optimal algorithm for the bandit problem with general constraints. I would like to know how this work is related to Bandit with budgets [Ding et al., 2013] published in AAAI 2013.", "other_strengths_and_weaknesses": "This work removes the strong assumption that Slate's parameter is known to the learned used by prior works. This can be considered as a more realistic setting.", "other_comments_or_suggestions": "This paper is well-written, and it is smooth to go through from the beginning to the end.", "questions_for_authors": "Please look at the Theoretical claims.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "No ethical concern."}}, {"review_id": "WJTAqQ0d80", "reviewer": "Reviewer_Ldsh", "summary": "The authors study the BwK setting where a learner is tasked with repeatedly performing actions and gain high cumulative reward while also satisfying multiple general long-term constraints. Specifically, they consider a best-of-both worlds objective in which a given algorithm has to perform optimally whether or not the environment is stochastic or adversarial, and show that if a primal-dual scheme is applied with weakly adaptive regret minimization algorithms, such best-of-both-worlds guarantees are achievable without prior knowledge of the Slater parameter $\\rho$ characterizing the problem instance, which is the main contribution of this work over previous works. They establish the fact that OGD with a specific choice of learning rate is indeed such a weakly adaptive regret minimizer which gives an explicit algorithm for the problem. The authors also provide explicit scenarios where their results can be applied, specifically contextual bandits with constraints.\n\n## update after rebuttal:\nAfter reading the other reviews and the authors' comments, my assessment of the paper remains as is.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback about our paper. \n\n* The weak adaptivity property was used in a simplified setting in the very recent paper by Castiglioni et al. (2024). Here, the authors only study the case in which they have a single budget constraint and a single consumption constraint (ROI). \nHowever, in our paper, we have to deal with an arbitrary number of constraints. In particular, proving lemma 6.1 in this setting is far more challenging. Indeed, the multiple constraints “move” independently but affect the constraints “jointly”. This originates difficult technical challenges that we highlight in more detail in the answer to your third question.\n* Some prior works, such as Balseiro et al. (2020), could, in principle, accommodate stronger benchmarks through a refinement of their analysis. However, this was not explicitly pointed out by the authors, likely due to their adherence to the conventions of the online allocation literature and its standard benchmarks. Some very recent works also highlighted this stronger benchmark (see, e.g., Bernasconi, Martino, et al. (2024)). \n* The proof relies on the key observation that Lagrangian multipliers jointly affect the primal utility but evolve independently. Thus, we need to reason about the joint behavior of the Lagrangian multipliers and look at the L1 norm. In particular, our proof proceeds by contradiction:  if the Lagrangian multipliers exceed a certain threshold, then they must have remained \"large\" for an extended period of time (Equation 3 in the appendix). Now we can exploit the scale freeness of the primal regret minimizer and its regret property with respect to the action that satisfies the constraints (Equation 4), to claim that the primal utility is large in such interval (Equation 6). However, this is in contradiction with the fact that the dual utility is also large (because of the growth of the Lagrangian multipliers, see Claim B.4). The proof of Claim B.4 is particularly involved, as it needs to analyze the separate behavior of the Lagrangian multipliers relative to different constraints. Indeed, it is possible for the  $\\ell_1$ norm of the multipliers to increase without having all individual components growing. This makes it nontrivial to conclude that the dual utility must have increased as well.\n\n**References:** \n\n- Castiglioni, Matteo, et al. \"Online learning under budget and ROI constraints via weak adaptivity.\" ICML 2024\n- Balseiro, Santiago, Haihao Lu, and Vahab Mirrokni. \"Dual mirror descent for online allocation problems.\" ICML 2020\n- Bernasconi, Martino, et al. \"Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints.\" NeurIPS 2024", "claims_and_evidence": "The claims made in the submission are supported by rigorous proofs provided in the supplementary material.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I did not check the correctness of the proofs presented in the submission, however, given my relative familiarity with the research topic, the claims seem sound and I didn't find any soundness issues.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The authors provide adequate references to related previous works in the context of BwK, with a particular focus on recent works by Castiglioni et al. which is the most relevant to this work in studying best-of-both worlds objectives for BwK. The authors make clear how in those previous works, either the Slater parameter $\\rho$ has to be known or the constraints have a specific structure, thus emphasizing the generality of their contribution. The authors also sufficiently cite papers relevant to the LagrangeBwK primal-dual framework which they heavily use in this work.", "essential_references_not_discussed": "I am not familiar with essential references that were not discussed in this work.", "other_strengths_and_weaknesses": "Strengths:\n\n* The authors present what seems to be the first optimal best-of-both-worlds guarantees for BwK with general constraints with algorithm that doesn't require knowledge of the problem's Slater parameter.\n\n* The contributions are presented clearly.\n\n* The observation that regret minimizers for primal and dual algorithms does not suffice for the adversarial setting seems interesting.\n\n* The upper bounds apply generally in the sense that they are black-box upper bounds which only require the input primal and dual algorithms to be weakly adaptive regret minimizers with the primal algorithm being scale-free, thus allowing for a wide range of algorithms.\n\nWeaknesses:\n\n* The paper contains numerous typos and confusing wording in some places.\n\n* I would have appreciated some analysis sketch in the main text, to give some intuition and also highlight any technical novelties in the analysis.", "other_comments_or_suggestions": "As mentioned earlier, the paper contains quite a few typos, some of which are listed in the following:\n\n* In Algorithm 1 and Algorithm 2, I believe $\\mathbf{c}_t$ should be replaced with $\\mathbf{g}_t$.\n\n* In the statement of Theorem 4.1, I believe the last part should have $<$ instead of $>$, as the current statement does not make sense for a lower bound.\n\n* Lines 224-225 - \"... it is not required adaptive regret minimization\" - wording is confusing here.", "questions_for_authors": "My main question to the authors concerns the technical novelties of this work when compared to previous works. Specifically: \n\n* Is the observation that adaptive regret minimizers are necessary (rather than regret minimizers) a novel observation (referring to the construction in Example 5.2)?\n\n* Is the fact that the benchmark in the adversarial setting isn't required to satisfy the constraints novel for this work? Or is such a benchmark used in previous works of adversarial BwK?\n\n* I would appreciate it if the authors could briefly summarize the technical challenges and novelties of their analysis. Is it mostly the self-bounding lemma? If so, what are the challenges in proving it?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper extending the bandits with knapsacks (BwK) framework to the setting with long-term constraints. By exploring weakly adaptive primal and dual algorithms, the authors develop best-of-both-worlds guarantees for stochastic and adversarial inputs, without knowing the  Slater’s parameter. Given the strength of the contribution, all reviewers unanimously recommend acceptance. That said, the authors are encouraged to further improve the paper, particularly in terms of paper presentation.
Decision: Accept (poster)