A Unifying Framework for Online Optimization with Long-Term Constraints
Authors: Matteo Castiglioni
Andrea Celli
Alberto Marchesi
Giulia Romano
Nicola Gatti
Venue: NeurIPS 2022 Accept (2022)
Keywords: online learning
long-term constraints

Abstract: We study online learning problems in which a decision maker has to take a sequence of decisions subject to $m$ long-term constraints. The goal of the decision maker is to maximize their total reward, while at the same time achieving small cumulative constraints violations across the $T$ rounds. We present the first best-of-both-world type algorithm for this general class of problems, with no-regret guarantees both in the case in which rewards and constraints are selected according to an unknown stochastic model, and in the case in which they are selected at each round by an adversary. Our algorithm is the first to provide guarantees in the adversarial setting with respect to the optimal fixed strategy that satisfies the long-term constraints. In particular, it guarantees a $\rho/(1+\rho)$ fraction of the optimal utility and sublinear regret, where $\rho$ is a feasibility parameter related to the existence of strictly feasible solutions. Our framework employs traditional regret minimizers as black-box components. Therefore, by instantiating it with an appropriate choice of regret minimizers it can handle both the full-feedback as well as the bandit-feedback setting. Moreover, it allows the decision maker to seamlessly handle scenarios with non-convex reward and constraints. We show how our framework may be applied in the context of budget-management mechanisms for repeated auctions in order to guarantee long-term constraints which are not packing (e.g., ROI constraints). 

A Unifying Framework for Online Optimization with Long-Term Constraints
Matteo Castiglioni' Politecnico di Milano
Andrea Cellit Bocconi University
Alberto Marchesi" Politecnico di Milano
Giulia Romano" Politecnico di Milano
Nicola Gatti"
Politecnico Milano
Abstract
We study online learning problems in which decision maker has to take a sequence of decisions subject m long-term constraints. The goal of the decision maker to maximize their total reward, while at the same time achieving small cumulative constraints violation across the T rounds. We present the first best-offbbothwee type algorithm for this general class of problems, with no-regret guarantees both in the case which rewards and constraints are selected according to an unknown stochastic model, and in the case in which they are selected at each round by an adversary. Our algorithm is the first to provide guarantees in the adversarial setting with respect to the optimal fixed strategy that satisfies the long-term constraints. In particular, it guarantees a p/ (1 + p) fraction of the optimal reward and sublinear regret, where is feasibility parameter related to the existence of strictly feasible solutions. Our framework employs traditional regret minimizers as black-box components. Therefore, by instantiating it with appropriate choice of regret minimizers can handle the full-feedback as well as the bandit-feedback setting. Moreover, it allows the decision maker to seamlessly handle scenarios with non- convex rewards and constraints. We show how our framework can be applied in the context of nudget-management mechanisms for repeated auctions in order guarantee long-term constraints that are not packing (e.g., ROI constraints).
Introduction
We study online learning problems where a decision maker takes decisions over T rounds. At each round f, the decision I; E X' is chosen before observing a reward function f: together with a set of time-varying constraint functions gt. The decision maker allowed to make decisions that are nor feasible, provided that the overall sequence of decisions obeys the long-term constraints ET1 (x,) 0, up to small cumulative violation across the T rounds. The problem becomes that of finding sequence of decisions x; which guarantees a reward close to that of the best fixed decision in hindsight while satisfying long-term constraints. This type of framework was first proposed by Mannor et al. (36), and it has numerous applications ranging from wireless communication [36] and multi-objective online classification [13,, to safe online learning
Mannor et al. 366 show that guaranteeing sublinear regret and sublinear cumulative constraints violation is impossible even when Jt and are simple linear functions. Therefore, previous works cither focus on the case which constraints are generated i...d according to some unknown stochastic
DDEIB, Politecnico Milano, (matteo. /matteo.castigliont alberto marchesi.. romaia, nicola.gatti @ppoimii.t. it. i Computing Sciences Department, Bocconi University, andrea.celli2 unnibocconi.it.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Non-convex ft and gr
Bound
constant
Bound - arbitrary&
Algorithm
Constr.
Reward
Violation
Reward
Violation
Yu al. 44
SToc
X
OPT O(T
Ö(T\/1)
STOC
/
OPT /3
((T
OPT Ö(Tritt) O(T
Ours
ADV
A CPT (T
Ö(T)//3
Table 1: Comparison between the performance of our algorithm and previous work using the same baseline as ours. Bounds for settings that were not previously tractable are highlighted in gray. OPT is the reward of the baseline.
model, without providing any guarantees for the adversarial case, provide results for adversarially- generated constraints under some strong assumptions on the structure of the problem or using a weaker baseline (a detailed discussion of related works can be found in Appendix Ap. A few examples in the latter case are [16] 21 40 42 In the former setting (i.e., stochastic constraints), Wei et al. 41 consider weaker baseline that is feasible for each constraint Ir. going against the basic idea of long-term constraints. A notable exception is the work by Yu et al. 44 who employ the same baseline as ours, and provide an upper bound of (T2 for both regret and constraints violation (see Table [I. We also mention that there are some works studying the problem in which constraints are static (see, e.g., [31 35 43 451), or focus on specific types of constraints, such as knapsack constraints 7 30]. Our framework differs from those works as deal with arbitrary and time- varying constraints. Moreover, it also extends the online convex optimization framework introduced by Zinkevich [46] by allowing for general non-convex loss functions ft, arbitrary feasibility sets X, and arbitrary time-varying long-term constraints.
1.1 Original contributions
Given the negative result by Mannor et al. (36]. natural question is what kind of guarantees we can reach in the adversarial setting, when adopting the standard baseline of the best fixed decision in hindsight satisfying (in expectation) the long-term constraints. We provide the first positive result going in this direction, by designing a no-a-regret algorithm that guarantees a sublinear cumulative constraints violation. Moreover, we make step forward in the line of work initiated by Bubeck algorithm for
and Slivkins [14], by showing that our algorithm is also the first pest-of-both-wond problems with arbitrary long-term constraints. This allows our algorithm to guarantee good worst- case performance (adversarial case), while being able to exploit well-behaved problem instances (stochastic case). The only assumption which we require is the existence of a decision that is strictly feasible with respect to the sequence of constraints. We denote by the "margin" by which this decision is strictly feasible (see Section 2 for a definition). At the same time, we show that even without this assumption, we can recover sublinear regret and violation with stochastic constraints.
Previous work usually assumes that P is given constant. In that case, our algorithm matches the guarantees by Yu et al. [44] when constraints are generated i.id. according to an unknown distribution, and has no-a-regret with a p/ (1 + p) in the adversarial case (see Table D). Our algorithm only requires a lower bound on the real value of the feasibility parameter p. In the stochastic case, the lower bound may even be unknown, and the algorithm can efficiently estimate it from data. Moreover, argue that if p is allowed to depend on 7 and take arbitrarily small values, then there are certain values (p < (14), for which any regret bound depending on 1/p would be useless (i.e., not sublinear in T, Section 3). This setting is usually overlooked by previous work, which assumes p to be given constant. We show that, in the case of an arbitrary fcasibility parameter p. in the stochastic setting our algorithm guarantees an upper bound of ((13/4) for regret and cumulative constraints violation.
Our framework employs traditional regret minimizers as black box components. Therefore, by instantiating it with an appropriate choice of regret minimizers it can handle feelbbee as well as kandit-feedback settings. In the former case, after playing æt, the decision maker gets to observe fe and gt. while in the latter case only the realized values (x,)) and ge (xx)) ) are observed. Moreover, this allows the decision maker to seamlessly handle scenarios with non-convex reward and constraints, by employing a suitable regret minimizer for non-convex losses (see, e.g., (39). Our algorithm is based on two-stage approach in which primal and dual players interact through Lagrangian games.
2

---

In the first (play) phase, the primal player tries to balance out the maximization of their rewards with constraints violation. In the second (recovery) phase, the primal player only makes "safe decisions" to avoid violating constraints too much. It is possible to prove that, in the case of stochastic rewards and constraints, the algorithm never enters phase two. This property is particularly relevant for budget-pacing mechanisms in repeated auctions, since it is related to how budget is allocated. Our framework can also be instantiated to perform budget allocation subject to constraints that were previously not tractable by traditional mechanisms, such as ROI constraints [ 22].
2 Preliminaries
The decision maker has a non-empty set of available strategies X' (this set may be non-convex, integral, and even non-compact). In each round E [ the decision maker first chooses æ, X, and the environment selects a reward function Sa : X [0, 1| and a constraint function 9: : X' + [-11]] conditioned on the past history of play up time
(i.e. the environment chooses fa and gr without knowledge of xt). Notice that both ft and 9r need not be convex. The latter specifies a set of m constraints of the form ge (a) S O, with (2x S 0 denoting the i-th constraint In the following. we denote as F, respectively 9, the set of all the possible ft. respectively 9t. functions (e.g.. F and may contain all the hipschitz-continnn decision maker can condition their decision on prior feedbacks and on the sequence of prior decisions 21,.... 1t but no information about future rewards and constraint functions is available.
functions defined over X). each round & E [T]. the
2.1 Strong duality through strategy mixtures
In the following, we define the optimization problem (Problem [.g which is used to define the baselines against which we compare the performances the decision maker. Such a problem involves probabilistic mixtures of strategies in X, which are crucial in order to recover strong duality
First, we introduce the set of probability measures on the Borel sets of X. We refer to such a set as the set of strategy mixtures, denoted as E. We endow X' with the Lebesgue a-algebra, and we assume that all the functions in F and G are measurable with respect to every probability measure & E E. This ensures that the various expectations taken are well-defined, since the functions are assumed to be bounded above, and they are therefore integrable. In the following, for ease of presentation and with slight abuse of notation, whenever we write & E E in place of an æ E X, we mean that we are taking the expectation with respect to the probability measure g. For instance, given f and g E G, we have that f(E) = (x)) and g(E) E==eg(r)).
Then, given two functions f E F and g G, we define the following optimization problem, which chooses the strategy mixture & E = that maximizes the expected reward encoded by f. while guaranteeing that the constraints encoded by g are satisfied in expectation.
sup EEE
f(E)
OPT
(LP
g(E) S.
We denote by d, E 1-1, 1] the largest possible value for which there exists strategy mixture E = satisfying the constraints g(E) S 0 by a margin of at least dg. Formally,
dg == sup min - 9: (E).
$E [E(m)
In order to ensure that OPTy,, y. is always well defined, we assume that it is always the case that dy 2 0. Notice that, if dy > 0, then Problem LP f.g satisfies Slater's condition.
In the following, we prove some auxiliary results relating to Problem LP f that will be useful in the rest of the paper. First, introduce Lagrangian relaxation of the problem.
IIn this work, we denote by [ar] the set .I....,z) of the first natural numbers.
Fooussig on the case (x) < 0 is w.l.o.g. since any set of constraints can be represented in such form. *The optimal fixed strategy mixture provides an arguably stronger baseline than optimal fixed strategy. In stochastic settings, this baseline is related to the best dynamic policy. In particular, we consider the case in which the observed functions are defined as the average of functions fi and gi across the I rounds, then the optimal mixture provides the same utility the best dynamic policy (see (7) for similar result).
3

---

Definition 2.1 (Lagrangian Function). Given two arbitrary functions f E F and E G the L function f. Rm R of Problem LP f.g
defined as
(E = ((E) (1, (E))(()))
If Problem LP f.e satisfies Slater's condition, then Theorem 1 of Chapter 8.3 in [34 readily gives us that strong duality holds even if' f and g are arbitrary non-convex functions. Formally:
Corollary 2.2. Given f E F and E such that dg > O, it holds
sup inf (E, - inf sup =) S. SEB AERT. 20
AER EEE
Next, we show that, if dg > O, then strong duality holds even when we restrict the admissible dual vectors À E R% to the set Dag where, for any q E Ryo, we let D = {> E Rno ||Al| - 1/4]
(omitted proofs can be found in Appendix (B).
Theorem 2.3. Given E F and E 9 such that dg > 0, it holds
sup inf EEz A
L5.l(E inf sup -5 AEDa, EEB
2.2 Stochastic adversarial: baselines and feasibility
We consider several settings, differing in how functions ft and gi are selected, either stochastically or adversarially. We say that functions fa (respectively gt) selected stochastically, when they independently drawn according to a given probability measure μ4r over J (respectively Mgg over G). Instead, say that functions Sa (respectively gi) are selected adversarially if each fa (respectively 9r) is chosen by an adversary based on the sequence of prior decisions, namely æi...., Lt-1-
Consistently with previous work (see, e.g., (36]), we compare the performance of the decision maker (in terms of reward cumulated over the T rounds) against the baseline T T'OPT, f.g (as defined by where f and I are suitably-defined functions. In particular:
Problem LP fa
When functions ft. respectively 9t. are selected stochastically, then define function f. respectively g. so that (xx = E [=)], respectively g(x) = Eg [g(x).
When functions fi, respectively It. are selected adversarially, then we define function f.
respectively so that f(x) = 4 Σ (xx),, respectively g(x) +
Intuitively, in the stochastic case, the baseline is instantiated with an expectation of functions taken with respect the probability measure μar (respectively (g)). Instead, in the adversarial case, the baseline uses the average of functions ft (respectively g.) observed over the T rounds.
Let remark that, when the set X' is compact convex and functions ft and 9: convex, then Problem LP defining our baselines can equivalently re-written by using strategies æ E X rather than stralegy mixtures & E, since there always exists an optimal solution to Problem LP f.g that places all the probability mass on a single strategy.
Our goal is to design online algorithms for the decision maker that output sequence of decisions I.....y Ey such that both the cumulative regret with respect the performance of the baseline. defined as Re = T OPT Ei= (xx)), and the cumulative constraints violation, defined as ΣT St, (x: grow sublinearly in the number of rounds T.
VT max mn]
In conclusion, we introduce a problem-specific parameter that strictly related to the feasibility of Problem LP
f.a
We call it the feasibility parameter p R, which is formally defined follows:
When functions 9i selected stochastically, supeez minte[m) (E).
When functions ge are selected adversarially, p = supgez minierry minse[m] (E).
Intuitively, in the stochastic case, p is equal to dg. while in the adversarial case it is computed similarly, but considering the worst case with respect to the functions Sr observed each round I.
Notice that, when p >> 0, Slater's condition is satisfied for Problem LP f.

---

In the following, we denote by 5* E E a strategy mixture that optimal for Problem LP f.g Moreover, we always assume that functions ft and Sr are such that Problem LP F.g is feasible, and we let 8 E E be the feasible strategy mixture that is optimal for the problem defining p
2.3 Regret minimizers
A regret minimizer (RM) for a set W is an abstract model for decision maker repeatedly interacting with an environment, At each f. a RM performs two operations: (i) NEXTELEMENT), which outputs an element w, E W; and (ii) the feedback received from the environment. This is either a utility function uy : W + [a. bj having range (a. bj S R (full feedback) or only the value us (ww)) ) (bandit feedback), with uh possibly depend- ing adversarially on W1.- w The objective of the RM to output a sequence wi...... Wr
which updates the internal state of the RM using
of points in W so that its cumulative regret, defined as wee W Σi=1 (u+(w) - (,,(w)) grows asymptotically sublinearly in T. See [19] for review of the various RMs available in the literature.
For the ease of presentation, we introduce the concept of regret minimizer constructor, which is a procedure, say INIT(W, [a, b), n)), that builds RM on the basis of the three parameters given input. In particular, the procedure returns a RM instantiated for the set W, working with utility functions having range (a, b]. and such that its cumulative regret is guaranteed to grow sublinearly in the time horizon T with probability at least - Vz.
3 A unifying meta-algorithm
In this section, we present our meta-algorithm. Its core idea is to instantiate suitable pairs of RMs, where one is working in the domain X' of primal variables and the other in a suitable subset of the domain RT of dual variables. At each round t E [T]. the algorithm makes the RMs "play" against each other in a Lagrangian game, where the utility functions observed by them are related to the Lagrangian function f (ar, A) of Problem fr
Algorithm D provides the pseudo-code of the meta-algorithm, which takes as input: the total number of rounds T. a failure probability E (0, 1) such that the guarantees provided by the algorithm hold with probability at least 8, and lower bound أ 2 on the value of the feasibility parameter p.
Algorithm description. The algorithm works in two phases. In the first one, called play phase, the algorithm builds primal RM, called R2. working in the primal domain X' and dual RM, called Ri, operating on the subset Dr of the dual domain RT, where P is set in Line The algorithm makes the two RMs playing against each other (see the call LAGRANGIANGAMETTS either the cumulative violation V incurred by the algorithm exceeds a given threshold (see Line 4 where Mj is defined in Equation (2) or round T is reached. Then, in the second phase, called recovery phase, the algorithm constructs a new pair of primal, dual RMs, with the latter working on the (m 1)ddimensional simplex An. The recovery phase uses the remaining rounds to make these new RMs play against each other, with the primal RM observing modified utility functions that do not account for functions fe (see the call LAGRANGIANGAME Ri 0)). Intuitively, this is needed in order to ensure that the algorithm plays strategies D; that satisfy the constraints, thus balancing out the cumulative constraint violation accumulated in the first phase. The pseudo- code describing one "play" between two RMs, called RD and RP, is defined by the sub- aub-procedure LAGRANGIANGAMEN
RR 1)) until
RP,,) in Algorithm ] The additional parameter u EE (0, 1} is used to control the feedback fed into the primal RM R specifically, if v = 1, then R. observes a utility function that also accounts for fa (play phase), otherwise, v = 0, the observed utility function only accounts for the term depending 9t (recovery phase).
Regret minimizer constructors. Algorithm [ also needs access two suitably-defined regret minimizer constructors, namely INIT" (W, [a, bl,7)) and (NW [a, b), m)) where the former is used
'Notice that 5" and _o may not be well defined in all the cases in which the problem that defines them does not admit a maximum. Nevertheless, in such cases, we assume that E" (or (*) is strategy mixture arbitrarily "close" to the supremum, so that all of our results continue hold up negligible additive approximations that are dominated by other approximation factors, and we can safely ignore them for ease of exposition.
'The idea of having pairs of primal, dual RMs playing Lagrangian game was originally introduced by Immorlica et al. [30], restricted to the case of knapsack constraints.
5

---

Algorithm 1 META- METTAALLORRTTM(
Algorithm 2 LAGRANGIANGAME (R,, R²
1: A < max
17 < 6/3,t+11
1: dt + RR. NEXTÉLEMENT()
Phase I: Play
2: X, < RP. -EETEILEMENT)
2: Ri + INIT 1/,,-1/0,1+11
3: Play æ, and get ft and ge
> Full f. Bandit f.
3: Ri INIT 11/p.11/
Play æ; and get fxx))) and ge(e))
b. Primal RM update
4: while s + Ms 1At t T do
4: Let u. + (ff(2)) 9c()))
> F f.
5:
It 6 LLAGAAGGAANAAMECRR RF,
6:
++
uf (xx) + vf(())))))))))))))))))())))))v (e (xx))
Sc
Bandit f.
R" O.B.BBVUUTLLLIY((O..
b Full f.
7: Ti 66-1
5: R OBSERVEUTILLTY
(z+))
Bandit f.
D Phase II: Recovery
8: Ri + INIT (X, [-1, 11.
D. Dual RM update
6: Let ug X (xz))
9: Ri f INIT [Am.1-1,11
7: RD. -OBSERVEUTILITY (1))
10: while t < ' do
11: I1 f LAGRANGIANGAME/RA RR.
12:
++++1
to build RMs working in the primal domain and the latter for those operating on the dual one. Their actual implementation depends on the specific problem hand. In the following, we let εi,, be the regret upper bound (on E [T'] rounds) for primal RMs R dealing with utility functions having range [0, I]. as returned by the call INIT (X, [0, I), Notice that, when the range (a, b). the same RM can be adopted by first normalizing utility values, that the resulting regret upper bound is (b - a),,,,, As for dual RMs R", we let E be the regret upper bound (on t E [T'] rounds) provided by the RM defined for the set Am. while 8 is the upper bound for the dual RM instantiated on the set Dj. Notice that, since dual RMs always have full feedback, we can safely assume that the regret bounds ET hold deterministically. We also assume that RMs provide bounds that increase with the number of rounds, i.e., such that E7,, S Ey and E. S E.. for all t S t'.
How to construct RMs. INIT can be implemented by using online mirror descent (OMD) with domain Am (or D)) and a negative entropy regularizer. Since the utility function uf, is linear in X,
we get regret bound for the primal RM of Eg. = D(VTloogmm) log(m)) (see, e.g., 112 37 ). The design of
INIT depends on the structure of X' and functions ft and Jt- For instance, in convex settings with full feedback we can employ OMD [29] while with bandit feedback we can use [5]. Finally, for
non-convex functions we can employ, e.g. the RMs 33.. All these RMs guarantee Ö(VT) regret.
How to get away with no knowledge of In Section 7 we show that a lower bound ` is not necessary when functions g. are selected stochastically. Indeed, it sufficient to add a preliminary phase to Algorithm D which is used to infer suitable lower bound on P from experience. In order to do this, only T rounds are needed, so that the bounds on the cumulative regret and the cumulative constraint violation achieved by the algorithm are not compromised. When functions Jr are chosen adversarially, as we show in Section 7 it is impossible to compute a lower bound on the feasibility parameter p by only adding preliminary phase to Algorithm which uses VT rounds.
Remark 3.1 (Dependence on the lower bound P). Algorithmm 7 can take as input any p 2 0. However, since our regret bounds include a factor 1/p. by choosing the trivial lower bound ò we incur in regret of Ö(VT/P) = O(T3/4). In order to obtain optimal bounds, we would like to have أ -= 22(p).
Remark 3.2 (Dependence on the feasibility parameter p). In our analysis, we include the dependence on the feasibility parameter p in the regret and constraint violation bounds achieved by the algorithm. As customary, the goal is devising bounds of the form poly(intancce) h(T"), where the first term is polynomial function of the parameters defining the problem instance, and h(T) o))). Therefore, we cannot include a factor 1/p in the regret bounds if p can be arbitrarily small. Even from practical standpoint, when p is too small, a 1/p regret bound is too large to be significant. For those reasons, we sei ò in Algorithm to be the maximum between the feusibility parameter lower bound ò and T-1/1, Notice that the value T-1/1 has been carefully chosen so as to minimize the maximum between the cumulative regret and the cumulative constraint violation when the lower bound on the feasibility parameter P is too small.

---

4 Analysis with stochastic constraints and adversarial rewards
We start by analyzing the performance of our meta-algorithm (Algorithm) I when the reward and constraint functions are selected stochastically and adversarially, respectively.
Given & [T] and (0, 1), we let Et., = /8t (og(18mt² /n) be the value bounding differences between expectations and empirical means of constraint functions, obtained by applying the Azuma-
Hoeffding inequality, and holding with probability at least 1 Given y (0, 1), we also let
3 M, = :===-VV VT + 2 7)
En. + (1-2)
2
1 -
(2)
which is recurring term related to the maximum violation that Algorithm T aaccepts in play phase.
First, introduce useful event E that encompasses all the cases in which [ terminates. Then, Lemma 4.2 shows that such an event holds with probability at least 1 5. In particular, E holds when the regret bounds of Ri and Ri hold, and, additionally, the differences between expectations and empirical means of constraint functions are bounded as desired.
Definition 4.1. We denote with E the event in which Algorithm [ satisfies the following conditions (recall that 77 = 6/3): (i) the regret incurred by Ri after Ti rounds is upper bounded by & (ii) the regret cumulated by Rí after the remaining (iii) for every pair of rounds t, E
Ti rounds upper bounded by - and [T] & S t' and resource E [m] holds:
(xx -f
-
Ev-em
Ex dr (r, Er d (1())) s Ev- (assss ||-/|12
(tie 3:(E)) S Ev-nn for E (E", ("),
Ei )-T+; E'= (E) s Ee-to max |>1l for & E {²)
Lemma 4.2. After running Algorithm y the event E holds with probability at least 1 8.
Next, we lower bound the cumulative reward obtained by Algorithm T during the play phase. Intuitively, we show that, if the cumulative constraints violation is large, then the decisions I; in the first Ti rounds provide a per-round reward much higher than that achievable by 5". This allows us to employ the following recovery phase decrease constraints violation eumulated in the play phase, while also ensuring that the cumulative regret stays low at the end of the algorithm. Formally:
Lemma 4.3. If event E holds, then after round Ti of Algorithm the following inequality holds:
E (x(x)) E (=(E)) (T (T) _ 11+ 2 T 1
In the recovery phase, the only goal of Algorithm is to decrease constraints violation. In the following Lemma 4.4 we show that, at each round of the recovery phase, the algorithm is "close" to satisfying (in expectation) all the constraints by least p. Formally:
Lemma 4.4. If event E holds, then after Algorithm halts, the following holds for every i E [m]] -T.n El Ei (t. (x,, I -T Ti)p - ET_T, + ET-Tim
Now, we ready to present the two main results of this section. First, provide bound on the cumulative regret and constraints violation when the lower bound f is sufficiently large.
Condition 4.5. It holds that á 2 2T-1/44 1/4
Notice that, under Condition 4.5 أ 0/2. This gives us the following result:
Theorem 4.6. Suppose that functions ft and gt are selected adversarially and stochastically, re-
spectively. If Condition 4.5 satisfied, then, with probability at least 1 8, Algorithm Algorithm[prroiieee provides RT < Er., + (1
1.. + E and VT < Mp + 2 + ET + Er,n-
Finally, we also prove that even if Condition sufficiently large, the following holds:
4.5 not satisfied, i.e. the lower bound p is not

---

Theorem 4.7. Suppose that functions ft and 9t are selected adversarially and stochastically, re- spectively, Algorithm| Searithmmggaaaaaan A guarantees that the following bounds hold with probability least 6: RT S TT,EET, + +01 (1+2T!/1) E + +TL/2g and VT S T3/ + MT + 28 Eg Er
Remark 4.8. Notice that, by using primal and dual RMs whose regret bounds are of the order of Ö(VT), Theorem 4.6 allows us to recover D(VT// regret and Op) constraints violation for the case in which Condition 4.5 holds. Theorem 4.7 still provides ( regret and constraints violation when the condition is not met, which is necessary the case when p = 0.
5 Analysis with stochastic constraints and stochastic rewards
In this section, we focus on the case in which both reward and constraint functions are selected stochastically. In this setting, we are able show that Algorithm never enters the recovery phase. As we argue in Section [8] this is an important property for meddgee-mangemmntt applications, since it related to the round which the budget fully depleted.
In order to prove our result, we extend the event E to capture also the Azuma-Hoeffding Hoeffding bounds for the reward functions, which are stochastic in this setting The core idea that we exploit to prove our result is that we can think of the two RMs as if they are playing a stochastic repeated zero-sum game, which is the repeated Lagrangian game whose functions are sampled according to the probability measures f and fgg. By Theorem 2.3 strong duality holds, and the game has an equilibrium. Hence, it is possible to show that the per-round utility of the primal RM is close the value of the game, which is OP f.g. At the same time, it is possible to show that, if the cumulative constraints violation becomes large during the play phase (and, thus, Ti < T), then the per-round utility of the primal RM is below J reaching contradiction that proves the following theorem.
Theorem 5.1. Suppose that functions ft and 9: are selected stochastically. With probability at least 1- 8, Algorithm
I never enters the recovery phase, namely Ti = =T.
Notice that regret bounds analogous to the ones in Theorems 4.6 and 4.7 also hold in the case in which both reward and constraint functions are selected stochastically.
6 Analysis with adversarial constraints
In this section, we study settings in which the constraint functions I. are selected adversarially. As shown by Mannor et al. (36), it is impossible to obtain sublinear cumulative regret and constraints violation when using our baseline, i.e., the best fixed strategy mixture & satisfying (in expectation) the long-tern constraints. However, we show that it is possible to achieve a p/ (1 + p) fraction of the cumulative reward obtained by always playing e", while guaranteeing sublinear constraints violation. The dependence of the approximation factor on the feasibility parameter p is similar to the dependence on the per-round budget in problems with budget constraints (see the related works in Appendix A for more details). Moreover, as we discuss later in Section R when restricted to the case of budget constraints and adversarial reward/cost functions, approximation factor matches the state-of-the-an bounds provided by Castiglioni et al. [17].
As first step to prove our result, we provide a lower bound on the cumulative reward of the primal RM during the play phase. We show that it achieves least a p/(1 +p) fraction the value obtained by the optimal solution in the first Ti rounds. Moreover, the algorithm provides an additional utility compensating for the last rounds in which the algorithm only focuses in satisfying the constraints. Finally, we show that, in the recovery phase, the constraints are satisfied by at least p at each round, up to term related to the regret of Ri and RJj proving the following theorem.
Theorem 6.1. Suppose that functions ft and gi are selected adversarially. If Condition 4.5 is satisfied, then, with probability at least 1 33. Algorithm guarantees that the following holds:
ET fe(x;) 2 -he LT OPT (1+3) 84,, _ and VT < <M3 + 28 + E7.
A similar result can be also derived for the case of stochastic rewards and adversarial constraints.
Accounting for the martingale difference sequences fi( - f(xz) and fi(E*) f(E").
8

---

Corollary 6.2. Suppose functions ft and 9: are selected stochastically and adversarially, respectively.
If C'Cddittion 4.5 is satisfied, then, with probability at least 1 - 8, Algorithm 1 provides Ei=1 f((x))) 2 3) - 2m and V M2 + r Eq ET.
Itp Ei= F
Remark 6.3. By using primal and dual RMs whose regret bounds are of the order of ((VT). Theorem 6.1 and Corollary 6.2 allows us to recover ft=1 2 P
Ltp Ei=1 OPT Op)
and (VVTTi ()) constraints violation for the case in which Condition 4.5
7 How to get away with no knowledge about the feasibility parameter
We show how to extend Algorithm T in order to deal with settings in which a lower bound on the feasibility parameter p not known, when functions It are selected stochastically, We propose Algorithm y which runs Algorithm by first devoting a given number Tú < ''' of rounds to inferring a suitable lower bound و on the feasibility parameter p. Ideally, we would like to have ( so as to recover bounds the order (V)Tpp). In particular, we show that we can run Algorithm 3 with To = / obtain an approximation of p that has an additive approximation error of the order T This is sufficient to get st(p), since a good approximation of p is only needed when p 2 T
Let us remark that our approach only works when constraints functions 9, selected stochastically. When these are chosen adver- sarially, it is easy to see that it is impossible to compute a lower bound on the feasibility parameter p by only using the first rounds. For instance, think of a setting in which very large in the first rounds, while it be- comes small during the last ones.
Algorithm 3 META-ALGGRRITHMI To,
1: Re + INIT (x, 1,
2: RD t INIT (Am,1-1,1),0
3: (+1
4: while 1. S To: do
5:
0t LAGRANGIANGAME R
To exploit the guarantees of A pre- sented in the previous sections, it is enough to show that, after the first To rounds of Al- holds with high probability.
6:
1 6- ++1
7: p To max Σ/= gr, ) + Exr,6
8: Run Algorithm
I Twith T To. 5, and أ as inputs
gorithm أ S
Lemma 7.1. If = VT, then Algorithm guarantees that p S with probability at least 8.
In order to recover a good estimate of p. we need the value of p to be sufficiently large. Condition 7.2. holds that p 2 72 + -E +
E.,))
Remark 7.3. Notice that, by using primal and dual RMs whose regret bounds are of the order Ö(VT) and by setting To VT, Condition 7.2 is satisfied when p (T-4)
Next, we show that X = (p)). which allows us to exploit the guarantees proved for Algorithm I in order to provide analogous ones for Algorithm Formally:
Lemma 7.4. By setting To VT, and assuming that Condition 7.2 is satisfied, after To rounds of Algorithm 3 we have that p 2 p/2 with probability at least
20.
By applying the results of the previous sections on the guarantees of Algorithm and by using primal and dual RMs whose regret bounds are of the order Ö(VT), we get D(VT/p) and Ó(VT/p) regret and violation bounds, respectively, when the functions Ir are selected stochastically.
8 Applications to repeated auctions settings
Internet advertising platforms usually operationalize large auction markets by using proxy bidders that place bids in repeated auctions on the advertisers' behalf. A proxy-bidder selects bids according to budget-pucing mechunism, which manages the usage of the advertisers' budget over time [1 22 9. In this section, we discuss the application of our framework to aadget-managemenn in auctions, arguing that it can deal with more general constraints on ad slots allocation with respect to what currently achievable with multiplicative pacing algorithms, which manage only knapsack constraints.

---

We consider the problem faced by a bidder who takes part in sequence of repeated auctions. We focus on the case of second-price and first-price auctions, since they are the de facto standard in large Internet advertising platforms. At each round 1. E (7), the bidder observes their valuation i, from finite set of ny possible valuations V C [0. 1]. Such valuation models targeting preferences of the advertiser. Then, the bidder chooses a bid by E B, where B C [0. 1] is finite set of n, possible bids such that E B (i.e., the bidder is allowed to skip items without incurring in any cost). The utility of the largest among competing bids, denoted by 3. In particular, the utility is
the bidder depends computed as f+(b,) = (v: - ce (bb 2 Br), where the cost e is such that ce (b(be) = (1(b, 2 3. in second-pries -rince auctions, and (b(b))
b, (b, 2 Br} for first-price ones. Finally, the bidder has a target per-round budget of p > O, which yields an overall budget B = pT that limits the total bidding. strictly feasible solution can be easily achieved by always bidding O. Using the target per-round budget = B/T we can write the budget constraint as Ever (b,) S O, with (b) (b) P for any E B. Notice that, in this setting, we have the same feasibility parameter p for both the stochastic and the adversarial case.
spending over the T rounds. In the case of budget-constraine
As a benchmark to evaluate the algorithm, we consider the best feasible static policy π : V - B. The set of static policies can be represented by X' = 8 where a vector b E 8 encodes the policy's s bids for each possible valuation. To apply our framework to this problem, it is sufficient to design a primal regret minimizer constructor (recall that, in order to design dual RMs,
employ OMD). This can be implemented by instantiating a regret minimizer EXP3.P .P (5] for each possible valuation in
V. Given a failure probability v E (0, 1). each RM guarantees a regret bound O ((v /Tn,, (og(m//// /v)) with probability at least 1 V. Thus, given desired failure probability n) (0. 1), by setting
v = 77/ n. we get that, with probability at least - 17, the bounds of all the RMs hold. Hence, by a
union bound, we get that the regret of a primal RM is TTn = O(, v TTg log(n..../n))
Guaranteed budget completion in the stochastic case. The crux of budget- paalett-pacingggce mechanisms is ensuring that the advertisers' budget is not depleted too early (thereby missing potentially valu- able future ad advertising opportunities), while being fully depleted within the planned duration of the campaign. Theorem S.T shows that, when inputs are generated according to some stochastic model, Algorithm | never enters the recovery phase. This is crucial in the context of budget-pacing mechanisms, because whenever the algorithm enters the recovery phase it will converge to always bid 0 in order to mitigate constraints violation. Therefore, the bidder could miss out on potentially valuable items. Moreover, if the platform wanted to guarantee that the bidder does not spend more than the budget B, it would be enough to set a virtual budges of B- - ((T)/2) to compensate for the potential constraints violation. Finally, we argue that, in large-scale markets, individual bidder has almost no impact on prices, and, thus, stochastic behavior of costs is a reasonable assumption.
Adversarial case. Theorem 6.1 of [7] shows how to construct an algorithm that provides a fraction of the optimal utility for problems with budget constraints and adversarial inputs. The ratio p/(1+ + p) obtained in Theorem 6. matches such result. The latter assumes that rewards and costs are in [0, 1]. and, thus, 9t E I-pp P. (as they only model budget constraints). However, in our case we have 9: E 1]. By normalizing the former range to match with ours, we get E [-p/(1 - p). 1]. Therefore, the feasibility parameter would be p' p/(1 p). By rewriting our guarantees function of p, we get p/ //1(1 + p¹) = p. which is the same guarantee of [7].
are based on primal-dual algorithms that are near optimal in settings with knapsack constraints only, and they cannot be generalized to deal with other types of long-term constraints. However, there are many real- world situations in which guaranteeing other types of constraints is crucial for practical applications (see, e.g., (26 (2)). One example is the case of return on investment (ROI) constraints 66,26] 32) The recent work by Golrezaci et al. 255 presents threshold- based algorithm for repeated second- price auctions under budget and ROI constraints. Our framework allows advertisers to reach a target ROI while keeping expenses under control also in the setting of repeated first-price auctions. In particular, given a target ROI w, we define the ROI constraints as gr (be) = (w - rr/bb,) 1 (b, 2 } < 0. Then, it is enough to instantiate our framework as described before to immediately get that the cumulative violation of the budget and ROI constraints are upper bounded by Ö(T1/2). This holds both in the fully stochastic and in the fully adversarial setting.
Handling ROI constraints. Traditional budget-pacing mechanisms (see, e.g., I g
See Appendix C for detailed discussion on the types of constraints that our framework can handle.
10

---

References
[1] Deepak Agarwal, Souvik Ghosh, Kai Wei, and Siyu You. Budget pacing for targeted online advertisements linkedin. In Proceedings of the 20th ACM SIGKDD international conference 2014.
on Knowledge discovery and data mining, pages
[2] Shipra Agrawal and Nikhil R Devanur. Bandits with concave rewards and convex knapsacks. In Proceedings of the the fifteetth ACM conference on Economics and computation, pages 989-1006.
ACM, 2014.
[3] Shipra Agrawal and Nikhil R Devanur. Bandits with global convex constraints and objective. Operations Research, 67(5): 486-1502, 2019.
[4] Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Concrete problems in Al safety. arXiv preprint urXiv:/6000 160v:/600.006655,, 2016.
[5] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal computing, 32(1):48-77, 2002.
[6] Jason Auerbach, Joel Galenson, and Mukund Sundararajan. An empirical analysis of return on investment maximization in sponsored search auctions. In Proceedings of the 2nd International Workshop on Data Mining and Audience Intelligence for Advertising, pages 1-9, 2008.
[7] Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knap- sacks. J. ACM, 65(3), 2018
[8] Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. The best of many worlds: Dual mirror descent for online allocation problems. arXiv preprint arXiv:201 1. 10124, 2020.
[9] Santiago Balseiro, Anthony Kim, Mohammad Mahdian, and Vahab Mirrokni. Budget- management strategies in repeated auctions. Operations Research, 2021.
[10] Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. Regularized online allocation problems: Fairness and beyond. In International Conference on Machine Learning, pages 630-639. PMLR, 2021.
[11] Santiago R Balseiro and Yonatan Gur. Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Science, 65(9):3952-3968, 2019.
[12] Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-175, 2003.
[13] Andrey Bernstein, Shie Mannor, and Nahum Shimkin. Online classification with specificity constraints. Advances in Neural Information Processing Systems, 23, 2010.
[14] Sébastien Bubeck and Aleksandrs Slivkins. The best of both worlds: Stochastic and adversarial bandits. In Conference on Learning Theory, pages 42-1, JMLR Workshop and Conference Proceedings, 2012.
[15] Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan. Kernel-based methods for bandit convex optimization. Pruceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, page 72-85, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450345286.
[16] Xuanyu Cao and KJ Ray Liu. Online convex optimization with time-varying constraints and bandit feedback. IEEE Transactions automatic control, 64(7):2665-268) 2018.
[17] Matteo Castiglioni, Andrea Celli, and Christian Kroer. Online learning with knapsacks: the best of both worlds. In International Conference on Machine Learning, ICML 2022, pages
2767-2783, 2022.
[18] Andrea Celli, Riccardo regularizer for pacing in auction markets. In Proceedings of the ACM Web Conference 2022, pages 162-172, 2022.
Christian Kroer, and Eric Sodomka. The parity ray
[19] Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[20] Tianyi Chen and Georgios B Giannakis. Bandit convex optimization for scalable and dynamic iot management. IEEE Internet of Things Journal, 6(1):127--1286 2018.
11

---

[21] Tianyi Chen, Qing Ling, and Georgios B Giannakis. An online convex optimization approach to proactive network resource allocation. IEEE Transactions on Signal Processing, 65(24): 6350-6366 6364, 2017.
[22] Vincent Conitzer, Christian Kroer, Eric Sodomka, and Nicolas E. Stier-Moses. Multiplicatiive pacing equilibria in auction markets. Operations Research, 2021.
[23] Jérémie Gallien and Shobhit Gupta. Temporary and permanent buyout prices in online auctions. Management Science, 5315):814-83,, 14-833, 2007.
[24] Lodewijk Gelauff, Ashish Goel, Kamesh Munagala, and Sravya Yandamuri. Advertising for demographically fair outcomes, arXiv preprint arXiv:2006. 03983, 2020.
[25] Negin Golrezaei, Patrick Jaillet, Jason Cheuk Nam Liang, and Vahab Mirrokni. Bidding and pricing in budget and roi constrained markets. arXiv preprint arXiv:2107.0772: 2021.
[26] Negin Golrezaei, Ilan Lobel, and Renato Paes Leme. Auction design for roi-constrained buyers. In Proceedings of the Web Conference 2021, pages 3941-3952, 2021.
[27] Elad Hazan. Efficient algorithms for online convex optinizaton and their applications. Princeton University, 2006.
[28] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2):169-192 2007.
[29]
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157-325, 2016.
[30] Nicole Immorlica, Karthik Abinav Sankararaman, Robert Schapire, and Aleksandrs Slivkins. Adversarial bandits with knapsacks. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, pages 202-219. IEEE Computer Society, 2019.
[31] 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.
[32] Bin Li, Xiao Yang, Daren Sun, Zhi Ji, Zhen Jiang, Cong Han, and Dong Hao. Incentive mechanism design for roi-constrained auto-bidding. arXiv preprint arXiv:2012.02655: 2020.
[33] 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.
[34] David G Luenberger. Optimization by vector space methods. John Wiley & Sons, 1997.
[35] 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.
[36] Shie Mannor, John N Tsitsiklis, and Jia Yuan Yu. Online learning with sample path constraints. Journal of Machine Learning Research, 10(3), 2009.
[37] Arkadij Semenović Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
[38] Shai Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and Trends@ in Machine Learning, 4(2):107-194, 2012.
[39] Arun Sai Suggala and Praneeth Netrapalli. Online non-convex learning: Following the perturbed leader is optimal. In Aryeh Kontorovich and Gergely Neu, editors, Proceedings of the 31 International Conference on Algorithmic Learning Theory, volume 117 of Proceedings of Machine Learning Research, pages 845-861, PMLR, 08 Feb-11 Feb 2020.
[40] Wen Sun, Debadeepta Dey, and Ashish Kapoor. Safety-aware algorithms for adversarial contextual bandit. In International Conference on Machine Learning, pages 3288- PMLR, 2017.
[41] Xiaohan Wei, Hao Yu, and Michael Neely. Online primal-dual mirror descent under stochastic constraints. Proceedings of the ACM on Measurement and Analysis of Computing Systems, (2):1-36, 2020.
12

---

[42] Xinlei Yi, Xiuxian Li, Lihua Xie, and Karl H Johansson. Distributed online convex optimization with time-varying coupled inequality constraints. IEEE Transactions on Signal Processing, 68: 731-746, 2020.
[43] Hao Yu and Michael J. Neely. A low complexity algorithm with o(vT) regret and o(1) constraint violations for online convex optimization with long term constraints. Journal of Machine Learning Research, 21(1):1-24, 2020.
[44] Hao Yu, Michael Neely, and Xiaohan Wei. Online convex optimization with stochastic con- straints. Advances in Neural Information Processing Systems, 30, 2017.
[45] Jianjun Yuan and Andrew Lamperski. Online convex optimization for cumulative constraints. Advances in Neural Information Processing Systems, 31, 2018.
[46] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928-936, 2003.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We present the goal of our paper and summarize the theoretical results. In the Original Contribution section, we underline the novelty of work and in the Related Work section compare our results with those in the literature (see also Table T).
(b) Did you describe the limitations of your work? [Yes] The assumptions characterizing the settings in which our results hold are clearly stated throughout the paper.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] The results presented in this work does not have any foresccable negative societal consequence. (d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set assumptions of all theoretical results? [Yes] In each theorem statement we provide all the assumptions needed for the result to hold.
(b) Did you include complete proofs of all theoretical results? [Yes] They are provided in Appendix B and Appendix C.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL.? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
13

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "sj40NStfE2", "reviewer": "Reviewer_DJUD", "summary": "This paper studies the problem of online optimization with long-term constraints, where the goal is to maximize the reward and minimize the violation simultaneously. The authors provide a best-of-both-worlds (BOBW) algorithm to handle stochastic and adversarial constraints. This algorithm uses a general regret optimizer (RM) oracle, which can handle the different reward functions and feedback models. For the analysis, a new notion of $\\rho$, which measures the margin of strict feasibility, is used to give BOBW performance guarantee.", "questions": "~I hope the authors can justify my concern in the weakness part.~\n\nAlso, are there any lower bound results based on $rho$, saying that $\\frac{\\rho}{1+\\rho}$ is the best we can do and $O(T^{3/4}$ types of results are the best for the stochastic case? Can the authors explain more about this?", "limitations": "Yes, the authors adequately addressed the limitations and there is no potential negative societal impact of their work.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n1. The authors propose a general framework that connects several lines of works based on different types of constraints.\n\n2. The algorithm proposed by the authors is very interesting and intuitive. It consists of two phases: the play phase to select aggressive actions to maximize the reward according to a constraint violation threshold and the recovery phase to compensate for the violation by playing safe actions.\n\n3. The authors give a new notion of $\\rho$, and based on $\\rho$, the authors provide promising results with weaker assumptions for the stochastic constraint case when $\\rho$ is constant. The authors also give results when $\\rho$ is not constant and can be arbitrarily small, meaning the constraints are quite difficult to satisfy. Under this case, they provide the first result for the stochastic case, though weaker than the constant case.\n\nWeakness\n~1. My main concern is about the adversary case. This work gives a $\\frac{\\rho}{\\rho+1}OPT-O(\\sqrt{T})$ reward guarantee, but the authors require $\\rho \\le O(T^{-1/4})$ and could approach 0 (when $T$ is large), which means the reward guarantee is $0-O(\\sqrt{T})$ and the result seems meaningless.~\n\nPost-rebuttal: This concern has been satisfactorily addressed.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "broTJ7ulfm", "reviewer": "Reviewer_SuMQ", "summary": "The paper deals with the problem of online learning with long term constraints, where the latter are either stochastic  or adversarial. The main contribution is a meta-algorithm based on no-regret online learning for the primal and dual problems, which are solving the \"Lagrangian game\" introduced by Immorlica et al. (for different type of constraints): one online learner tries to maximize the Lagrangian while the other to minimize it. A novel idea is that, when the constraint violation exceeds a threshold, the algorithm takes care only of the constraints, disregarding the objective function. \n\nThe authors prove that their proposed algorithm: (i) achieves, in the case of adversarial constraints, an objective at least a constant fraction of the optimal action in hindsight, while having a constraint violation residual sublinear with T in the case of adversarial constraints where (a bound on) the slack from the Slater condition is known (the constant factor depends on this slack) and (ii) in the case of stochastic constraint achieves a sublinear in T regret and constraint residual even if this bound is not known.   \n\nThe objective and constraint functions can be non-convex  and the action sets can be non-convex or discrete; this achieved by essentially randomizing the action by finding a probability distribution over the action space (and have the constraints and objectives be the expectation over this probability distribution).   ", "questions": "1. It would be nice to have some examples with some concrete implementations of the Regret Minimizers and their related operations (e.g. in an appendix); this would help towards a better understanding of the algorithms. \n\nFor example, in the case of concave rewards and convex costs (and convex action set $\\mathcal{X}$), does the algorithm run on a probability distribution over $\\mathcal{X}$ or the actions themselves? \n\n2. It would also be nice to have some numerical results about the performance and implementation of the algorithm in the repeated auctions setting of Section 7. \n\n3. In Section 7, why is the auction model restricted to discrete valuations and actions? ", "limitations": "This is a theoretical work, so I can think of no potential negative social impact. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. This is the first paper, to my knowledge, to provide performance guarantees for adversarial long-term constraints when the benchmark action is allowed to satisfy the long term constraint (instead of satisfying the constraint in every round or windows of rounds). These guarantees are a step towards understanding more about online learning problems with long term constraints (the result of Mannor et al. just states that the adversary can force $\\Omega(T)$ regret if the constraint residual is to be sublinear).  \n2.  The fact that when constraints are stochastic the slack in the constraints needs not to be known is also a nice result and a nice addition to the related literature. \n\nWeaknesses: \n1. The presentation is quite high level and difficult to follow and understand how exactly it works and how it can be implemented. \n2. The constant factor depends on the slack $\\rho$, which can, at least in theory be very small in the adversarial setting (by the adversary choosing, e.g. constraints that are barely satisfied and/or choosing e.g. $\\rho$ as a decreasing function of $T$): it is not clear how useful the approximation bound is in this case.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WDKPFkWiABr", "reviewer": "Reviewer_AWdY", "summary": "The paper proposes a no-regret meta-algorithm that jointly has:\n- no constraint regret (i.e. sublinear) if the constraints are stochastic,\n- no-$\\rho/(1+\\rho)$-regret if they are adversarial (i.e. no-regret w.r.t. $\\frac{\\rho}{1+\\rho}\\mathrm{OPT}$), where $\\rho$ is the strict feasibility margin of the problem.\n\nThe main contribution is that the proposed algorithm attains suitable rates across the array of settings considered in past works (hence the title, 'unifying framework'). The paper also studies the application of the algorithm to the repeated auction setting, showing it satisfies \"guaranteed budget completion\" under certain assumptions (due to guarantees of the algorithm under stochastic constraints *and* rewards). ", "questions": "- Could your algorithm provide a zero constraint violation guarantee if employed with a safety barrier as in [37] section 3.2? [answered in rebuttal, see below]\n- Could you delineate the trade-offs between their algorithm and the main competitors (e.g. does one or the other have better constants? is one or the other easier to implement?)", "limitations": "- I think authors should prioritize moving more of the related work discussion from Appendix A to the main body, especially given the nature of the work,\n- Similarly, the authors should include a conclusion that clearly address any limitations w.r.t. the existing approaches,\n- Could Table 1 be exteded to include more related work? even if the comaprator is different, the comparator type could be noted in an additional column.\n\nMinor Comments:\n- should it be 'constraint' rather than 'constraint*s*' in line 4?\n- equation $\\mathrm{LP}_{f,g}$ could work better as one line?\n- maybe change ', e.g. RMs in [41]' to 'RMs such as the ones in [41]' on line 214?\n- line 256 : 'allow' -> 'allow*s*'\n- line 287: 'to capture also' -> 'to also capture'\n- line 339: 'incurring in any cost' -> 'incurring any cost'", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is very well written and provides an elegant general algorithm,\n- Having a play phase and a recovery phase is something that I personally haven't seen in the related work (but I have only read a handful of papers in this particular sphere, online optimization with long-term constraints), and it seems to be amendable to downstream analysis of induced properties (e.g. showing the recovery phase is not entered implies the \"guaranteed budget completion\" property under stochastic constraints and rewards).\n\nWeaknesses:\n- there is no *clear* rate improvement with respect to prior work\n- the algorithmic approaches and analysis are somewhat standard and expected (given the 'unifying' character of the work this is somewhat natural in my opinion)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept