Online Ad Procurement in Non-stationary Autobidding Worlds
Authors: Jason Cheuk Nam Liang
Haihao Lu
Baoyu Zhou
Venue: NeurIPS 2023 poster (2023)
Keywords: autobidding
online advertising
bandit online convex optimization
constrained optimization

Abstract: Today's online advertisers procure digital ad impressions through interacting with autobidding platforms: advertisers convey high level procurement goals via setting levers such as budget, target return-on-investment, max cost per click, etc.. Then ads platforms subsequently procure impressions on advertisers' behalf, and report final procurement conversions (e.g. click) to advertisers. In practice, advertisers may receive minimal information on platforms' procurement details, and procurement outcomes  are subject to non-stationary factors like seasonal patterns, occasional system corruptions, and market trends which make it difficult for advertisers to optimize lever decisions effectively. Motivated by this,  we present an online learning framework that helps advertisers dynamically optimize ad platform lever decisions while subject to general long-term constraints in a realistic bandit feedback environment with non-stationary procurement outcomes. In particular, we introduce a primal-dual algorithm for online decision making with multi-dimension decision variables, bandit feedback and long-term uncertain constraints. We show that our algorithm achieves low regret in many worlds when procurement outcomes are generated through procedures that are stochastic, adversarial, adversarially corrupted, periodic, and ergodic, respectively, without having to know which procedure is the ground truth. Finally, we emphasize that our proposed algorithm and theoretical results extend beyond the applications of online advertising.

Online Ad Procurement in Non-stationary Autobidding Worlds
Jason Cheuk Nam Liang
Haíhao Lu University of Chicago haihao. 1u@chicagobooth. edu
Baoyu Zhou University of Michigan zbaoyu@umi edu
MIT jenliang@mit.cm edu
Abstract
Today's online advertisers procure digital ad impressions through interacting with autobidding platforms: advertisers convey high level procurement goals via setting levers such as budget, target return-on-investment max cost per click, etc. Then ads platforms subsequently procure impressions on advertisers' behalf, and report final procurement conversions (c.g. click) to advertisers. In practice, advertisers may receive minimal information on platforms' procurement details, and procurement outcomes are subject to non-stationary factors like seasonal patterns, occasional system corruptions, and market trends which make difficult for advertisers to op- timize lever decisions effectively. Motivated by this, we present an online learning framework that helps advertisers dynamically optimize ad platform lever decisions while subject to general long-term constraints in realistic bandit feedback envi- ronment with non-stationary procurement outcomes. In particular, we introduce a primal-dual algorithm for online decision making with multi-dimensional decision variables, bandit feedback and long-term uncertain constraints. We show that our algorithm achieves low regret in many worlds when procurement outcomes are gen- erated through procedures that are stochastic, adversarial, adversarially corrupted, periodic, and ergodic, respectively, without having to know which procedure is the ground truth. Finally, we emphasize that our proposed algorithm and theoretical results extend beyond the applications of online advertising.
Introduction
Automated bidding (or autobidding for short) has become the dominant mode for advertisers to procure digital ad inventories and impressions, contributing to more than $120 billion dollar ad spend in 2022 and more than 90% of total online ad transaction volumes [. In autobidding platform, advertisers only need to convey their high-level procurement goals for an ad campaign to the platform, which then takes charge of procuring ads advertisers' behalf, Such procurement goals are communicated to platform through platform levers, which are adjustable parameters that advertisers can control to influence the bidding process and campaign performance. To exemplify, Figure [I displays certain several levers presented on the Google Ads interface, where an advertiser can set per-campaign budgets, target cost-per-actions, campaign duration, campaign schedules, targeting, etc: similar examples are also shown in related literature 22
ad campaigns autobidding platforms and influence ad conversion outcomes (e.g., clicks), making efficient lever decisions vital to advertisers to achieve their procurement objectives. However, advertisers face many challenges in practice when optimizing for lever decisions, namely high-dimensional decision making under long-term constraints, non-stationary autobidding environments, and limited procurement feedback.
As the primary avenue for advertisers
High- digh--imensional decision making and long-term constraint satisfaction. Making multiple lever decisions involves evaluating numerous possible combinations of lever contigurations, which is computationally intensive and time-consuming real-time decision making setups. Also, advertisers need to understand the potential interactions and dependencies between levers, adjusting one lever may have unintended consequences or interactions with other levers, making it challenging to
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Scturdayy- Sundey
12:00
Budget
UCDalia 1USO
$100.00
Longuages
Chinees trimoiteet
French
Cemmen
Pay
Damographicc
Grader
Bicding
Target CTA
Irarrctioos
Pomale
The
Targen
Male
35-54
11-200
48-14
End dite
Start and and didea
2012
55-04
50%
Figure I: Example levers on the Google Ads interface to create digital advertising campaigns.
predict the overall impact of adjustments accurately. Furthermore, advertisers may need to satisfy certain long-term constraints over time, e.g., limiting total spend under budget, or achieving certain return-on-inven -inteettnnn targets. Hence in addition to analyzing the interactions between different levers, advertisers also need to concern long-term consequences of making certain lever decisions.
Limited feedback procurement outcome and constraints. Despite the fact that autobidding via lever decisions greatly simplifies advertisers' ad procurement process as they no longer have to handle the intricacies of procuring individual ad impressions, the procurement procedure becomes black box for advertisers, as advertisers only have limited visibility into the specific details of how the platform executes ad placement processes. This lack of transparency can make it challenging for advertisers to control the nuances of their campaign execution through lever decisions, and it amplifies the complexity to conduct counterfactual analyses on outcomes for past lever decisions.
Many non-stationary autobidding worlds. Autobidding procurement environments are highly non-stationary, wide spectrum of latent factors online ad marketplaces may greatly vary procurement outcomes of the same lever decisions in different time periods. These latent factors include but are not limited changing user preferences, seasonality effects, shifts in market trends, occasional malfunctions in autobidding platforms, etc. These dynamics may influence how users interact with different types of ads, which necessitates continuous adjustment of lever decision strategies to adapt to current and future market conditions.
To address these challenges, in this work answer the following questions: How should advertiser dynamically set multiple levers to optimize conversion outcomes subject to long-term constraints under limited information? And can she run a unified algorithum that can perform well while being agnostic to many types of non ion-stationary autobidding procurement environments?
Motivated by these questions, in this work we study an advertiser's ss online high-dimensional lever decision problem with long-term constraints under limited bandit feedback in many non-stationary worlds. We summarize our main contributions as followed:
Modelling online lever decisions in many worlds using online constrained optimization with bandit function-valued feedback and uncertain constraints (Section(2) (2). We cast the advertiser lever decision problem as an online constrained optimization with bandit function function-valued valued feedback and uncertain constraints, where functions at which (lever) decisions are evaluated correspond to the conversion and constraint functions in our autobidding setup. Further, we model real-world non- stationarity in autobidding environments as possibly time-varying distributions from which conversion and constraint functions are sampled, and then further applied to lever decisions. Under this model, we discuss five different input procedures from which the sequence of functional distributions are sampled to model stochastic, adversarial, corrupted, periodic, and ergodic environments; see Section 2.2 for more details. To the best of our knowledge, from a modelling perspective this is the first work to model a high- high-dimensional lever decision problem in practical non-stationary autobidding worlds.
2. Proposing a constrained bandit optimization algorithm universally applicable to many worlds (Section 3). We develop unified bandit optimization algorithm with robust performance guarantees across different worlds. Our algorithm incorporates four key designs to handle bandit function-valued feedback and unknown non-stationary environments. 1. we utilize dual descent to update dual variables associated with long-term constraints and decouple decisions over time; 2. we employ primal-ascema aaaal--ccet--aaa based bandit online convex optimization (BOCO) approach to make (primal) lever decisions to cope with bandit function valued feedback; 3, we implement an exponential weights

---

expert algorithm on top of primal ascent BOCO, where each expert corresponds to a different primal ascent step size. This enables our algorithm to adapt to the optimal primal ascent step size for each world without prior knowledge on which world we are in; 4. our algorithm dynamically checks for realized constraint violations and applies "safe lever decisions" to ensure long-term constraint satisfaction. For further details, we refer the readers to Algorithm 1 in Section 3
Analyzing the performance of proposed algorithms in many worlds (Section 4). We present theoretical analysis (Theorem 4.2) on the regret bound of the proposed algorithm, and we show that our unified algorithm can achieve reasonable regret bounds with all five input procedures. These
regret bounds are summarized in the following Table
Stochastic
8-corrpptd
Adversarial
Periodic
Ergodic
(1 (1- OPT(PL.) +0 (A.73)
o(T
o +
ocT + QVT) o + RVT)
Table 1:
T-period regret bounds for Algorithm I Jnder different input models. Here A >> 0 is some algorithm dependent factor which we will later specify in Section 4
The parameters ç OPT(P q, k) are formally defined in Section 2.2 and Theorem 4.2 in Section we remark all results are applicable to other problems.
Finally,
1.1 Related works.
Autobidding, In an autobidding framework, there is considerable body of works that study the price of anarchy, which aims improve worst case individual or total advertiser welfare guarantees w.r.t. the optimal welfare via mechanism design frameworks; see e.g. [23] 7 20 38 (2]. We remark that this line of work does not concern developing online learning algorithms. On the other hand, numerous works have concentrated on developing online bidding algorithms for repeated ad auctions 41
10 31 30]. as well as designing repeated selling mechanisms for ad impression allocation; see 12 and references therein. However, as discussed in the introduction, autobidding platforms conduct bidding on behalf of advertisers while keeping bidding and selling mechanism details undisclosed. In this study, we treat the bidding procedure and selling mechanism as a black box and directly model bidding and auction outcomes using conversion functions; see Section 2 To the best of our knowledge, the most pertinent work to this paper is 2111 which explores similar ad procurement problem by optimizing levers within a bandit environment. However, this work solely focuses on the stochastic world and optimizing single lever (i.e., I-dimensional decision space). In contrast, our paper develops a unified algorithm capable of making high-dimensional lever decisions in many worlds.
27
Online convex optimization. In Section 2 we cast the advertiser's online learning problem of interest to a high-dimensional bandit online convex optimization problem with uncertain long-term constraints, and develop an algorithm that yields good performance guarantees under different procedures from which the objective and constraint functions are generated. There has been rich line of works that study bandit convex optimization with no long-term constraints in stochastic and 44 as well works that study (full ffll-information feedback) online
adversarial worlds (25 32 42
17
43 35) Further, works that study both bandit feedback and long-term constraints either consider single-dimensional (such as multi-arm bandits with constraints) [40 6
convex optimization with long-term constraints 36 33
4
24 or consider static regret (i.e., benchmarking performance to that of
16 [4] 37). This paper distinguishes itself from these two streams of works by considering high-dimensional decisions as well as dynamic regret, i.e., comparing to the best sequence of actions instead of single action; see Eq. (T). Finally, all aforementioned works only study algorithms in stochastic or adversarial setups, whereas in this work we go heyond these two worlds and address more complex learning environment such as periodic, corrupted, ergodic, and finite switching. To the best of our knowledge, the only related work that develops a universal algorithm under "many world" setups is [00] However, [10] considers a full-information scenario where the online decisions in period can be made after observing realized objective and constraint functions during that period. In this work, we present an efficient algorithm to handle bandit feedback.
single optimal action) [3
Notation, For any vector z E Rd let || be its Euclidean norm. Denote BB = fx E Rd ||x < 1} as the d-dimensional unit ball centered at O, and let $ = {z E Rdd : ||=||| = 1} be the unit sphere. For any set S, let US) be the uniform distribution over S. Let denote the vector whose components
3

---

are all I's, and e, be the unit vector whose j ''th position is 1. We use O notation to represent the asymptotic order of term when the period T > oo and ignore the log T terms.
2 Autobidding with bandit feedback in many worlds (input models)
2.1
Autobidding as a bandit online optimization with long-term uncertain constraints
Consider an advertiser repeatedly interacting with an ad platform over T E N periods, where each period can be interpreted single ad campaign that is
the platform. During each period t E {T], the advertiser makes d 2 lever decisions denoted as H, E X C E", c.g., setting the per-campaign budget, campaign duration, per-campaign target return-on-investment, and spend per conversion; see Figure ] for example lever decisions in practice. Here, X' is some compact and convex decision set whose diameter is D (uP(,,.')))))
æ'Il. For simplicity, assume 0 E X so ||||| < D for any æ E X. After the lever decisions 2; are made the campaign is fully executed via autobidding, the advertiser observes bandit feedback for her campaign outcomes; she only observes her realized conversion f((x)) E R20 (e.g.. number of clicks on her ads), as well as some constraint balance gi (æt) K² The conversion and constraint functions (fe: gt) are sampled from some (possibly infinite) support S according to distribution P. E (SS) (we will discuss how P,'s are generated by nature in Section 2.2 Using the notation Pirr = (Pt)aery the advertiser's hindsight
optimization problem is
OPT(PET)= max xEX
Ep, [f(((z)] s.t. Ep, (E(T]
Σ
Ep, (xx) 20 k == K. BE(T]
(1)
Here, constraint function Ik.t X' IR to characterize general performance metrics of the advertiser for her ad campaigns. In the following, we present several examples for constraint functions that are widely used in practice or studied in literature. For illustrative purposes, we assume It,1 = e; xe (i.e., the first lever) represents the per-campaign budget for the t'th campaign.
Long-term budget constraint. The advertiser has a total budget BT > Then by letting constraint function I (3) = B Ir, we have [eE(T] (xx) 2 0 = Eie(T Ir,1 S BT, which means total campaign spent over T periods (assuming each campaign fully depletes the campaign budget) must be less than the advertiser's ' total budget BT.
Long-term cituu--o--invsttnne on-investment y > 0, i.e., she attains long-term average of least y conversions per dollar spent. Then by considering (x,) = fe())) 1,,,, we have E [T] Ik, (xx) 2 0 = Eie(r) fe(#;) 2
constraint.
The advertiser intends to safeguard long-term return-
7 Eirry Ft,1, which means total conversion over T periods is at least y times total spend.
Finally, we make the following mild assumptions on conversion and constraint functions]
|
Assumption 2.1 (Mild assumptions on conversion and constraint functions). For any (f.g) e S. f. .1...91 ... all bounded concave functions, i.e., assume suppexllo(=))l>> I and sup=ex If(x) < F for some G, F < co. Moreover, and g are L-Lipschitz. i.e. for any (x,x1) S X. we have fxx - f(x') < L|x - x'Il and [[)()) g(x') (')'ll I L|x x'1l Furthermore, there
exists (J.g) E S such that minge minke[k] (x=) < O.
2.2 Five input models characterizing many autobidding worlds
In this subsection, we describe structural properties of the input distribution sequence Pi:r, and shed light on how utilize various properties to model a wide spectrum of autobidding environments (called worlds) such as time-varying user preferences, seasonality, shifts in market trends, etc., that may potentially lead to different procurement outcomes for the same ad campaign lever decisions.
There exists some probability distribution P e A(S) such that Pi =... = Pr = P. This stochastic world represents stationary autobidding environment where the underlying latent factors influencing user behaviors (and correspondingly conversion results) remain constant over time; see B1 119921 21].
Stochastic:
'These assumptions are justified in many related works in autobidding: see (1 14 and references therein. For example, [21] shows that the conversion function is concave and piecewise- linear when autobidding platforms procure ad impressions behalf of advertisers in standard second price or VCG auctions.

---

6-corrupted. There exists P E A(S) as well as ò E N periods T = f1i... .8) C [T] such that P. for all & T. This d-corrupted input sequence represents occasional anomalies in the autobidding environment that may be caused by systematic malfunctions in the autobidding platform, or deliberate attempts by malicious competitors exploit the system for their own benefit; e.g., some competitors may engage in click fraud to inflate the number of clicks on our ads to exhaust our budget or generate false data to manipulate autobidding algorithms (for example, see (29]).
Adversarial. PIr is adversarially chosen by nature before the process starts, and the distributions over time can possibly be non- con-identical and/or dependent. This adversarial world can be viewed a hypothetical extreme case for the δ- 6-corrupted world where each period the procurement outcomes can potentially be corrupted by an adversary. Adversarial input sequences have been widely studied in the literature to assess algorithmic performances in worst-case scenarios; see 3 30
Periodic. There exists period length q E N such that T = eq for some integer 2 with Pı:r
satisfying Pi:g= = Pq++1:2 = P( [e-1)9++117 This periodic world captures regular cyclie patterns or fluctuations in the user behavior over specific time intervals; e.g., seasonality, day-of-week patterns, and time of a day.
Ergodic. P1:1 is an ergodic process (e.g., an irreducible and aperiodic Markov chain stationary autoregressive processes), where there exists some k > and a stationary distribution such that the distance between s-step transition probabilities and this stationary distribution decreases exponentially fast in K. Mathematically, given the input distribution sequence PI:T. denote P(e+x)][t-1) as the conditional distribution of (fe+n: 9t+x) conditioned on the realizations {(frr ((fr.g)))es gr)ee Then, for the
ergodic input model there exists stationary distribution P A(S) and absolute constant R 0 such that
sup sup (err rE[T-N]
[|((+=)](--]]- - -PllV S == Rexp(-x);
(2)
We remark that exponentially decaying ergodic models have been studied widely in the context of online optimization; see e.g. [10] Section 5.2] for further discussions. To make the problem of interest tractable, we assume K. log(T)). Intuitively, an ergodic input sequence signifies that
the procurement outcomes in close time proximity are correlated, which commonly observed in real-world autobidding systems, as they often involve iterative processes that enable procurement algorithms (operated on behalf of advertisers) to converge to a stable state; see details in 282)
2.3 Minimizing regret subject to long-term constraints with a universal algorithm In this work, we take the perspective of an advertiser making repeated lever decisions as described in Section We focus on designing single online algorithm that determines a lever decision æ, E X in each period I with the goal to minimize regret RT (defined as follows) under any input sequence Pier while satisfying long-term constraints
R = OPT(PIT) - Eieryy E [fe(:) and Every E [g.e))))] 2 O.
Here, the expectation is taken w.r.t. randomness from the input sequence as well as any randomness in our algorithm. We highlight that our desired policy should be agnostic to the input model as well as the input sequence PI.r. We remark that our work distinguishes itself from related work that study solely stochastic and/or adversarial input models, as we aim to design universal algorithm that achieves salient performance over any input model described in Section 2.2
3 A universal constrained BOCO framework for many worlds
In this section, we focus on designing an algorithm that achieves low regret (per Eq. maintaining long-term constraint satisfaction in any world described in Section 2.2 without having to know which world are in. We first highlight three main challenges for our problem of interest.
5 while
Dynamic benchmark lever sequence and unknown input sequence Pi:r- Recall the hindsight optimal problem in Eq. [ with which we are comparing our algorithm'' 's performance to the optimal sequence of lever decisions over time given any input sequence Pi:r, instead of comparing to single optimal lever decision as in many related works; e.g., see [15] and references therein. This dynamic optimal sequence presents a very strong benchmark and makes learning very difficult as we (ideally) need to account for variations in the underlying non-stationary ground truth input sequence Pi:T. Nevertheless, we do not know the input sequence PI.r in advance, nor do we know in which world the sequence belongs (Section) 2.2
5

---

Bandit function-value (zeroth-order) feedback. Our setup concerns a bandit function-value feedback model, where the realized conversion and constraint functions in each period, namley ft : - R20 and 9: X + IR are never revealed to us. and we can only access their function values at our single lever decisions during the period. We also contrast our setup with a "two-point feedback" setup in online convex optimization literature, where in each period one can access function values twice (see [44] and references therein). Using the context of our setup, in a "two-point feedback" after nature samples ft X + R20 and gr XX' + R² from Pt, we can observe the values for two lever decisions {xt x E X, namely (fe(z)) g.) (zx and (x.
Universal algorithm for many worlds. Instead of developing separate algorithms that cope with each individual world described in Section 2.J] we aim to develop single universal algorithm that performs well in every world without exploiting any knowledge on the realized input sequence Pirr or its structural properties.
The key component of our algorithm to handle the aforementioned challenges is the following Lagrangian function: for any ft: X + R20 and gr : X' + R² let's define L; X x R R such that
(a 2) f(x A gx)).
Surrounding this Lagrangian function, our proposed algorithm is formally stated in Algorithm | with four key components described as follows.
1. Dual descent to decouple decisions across time. As our lever decisions over time should be somewhat intertwined with one another due to the presence of long term constraints, we decouple this cross-pett cross-period dependency by lagrangifying the hindsight problem in Eq. (L) w.r.t. some benchmark dual variables. In each period t. we maintain an estimate of dual variables X2 E R corresponding to each of our K constraints, and adopt a standard dual descent approach to dynamically adjust these estimates; see Eq. (9). In particular, after observing (fc (z))) 9r (2:)). we update our dual variable by projecting each coordinate of X 1/VxLr( Ax) = X 199. (Ix)) onto some interval [0,
F where n > is the dual descent step size, F is the maximum achievable conversion, and 3 "safety buffer" to be defined later.
some
2. Primal ascent to handle bandit function-valued feedback in many worlds. Given a dual variable A during period t, standard optimization frameworks suggest optimizing primal decisions (i.e.. lever decisions) by setting x, = arg maX Ep, (z, Ae)]. However, our setting this is not possible due to the bandit vunltid feedback structure: we do not know ft(-). gr(-) nor P., and hence cannot optimize for Ep, (-, ),)]. To handle this, we view the primal decision problem as bandit online convex optimization problem (BOCO) where the adversarial objective functions are C.(: A,), and run a BOCO algorithm to make primal lever decisions in each period.
Mathematically, we define the BOCO objective function he: : X' + RR as
hu hx( L. (ax A.) fa( + X, (x)).
(5)
Then, the BOCO algorithm constructs an estimate V. of V he (x) based on a random perturbation approach with perturbation parameter م > O (see Eq. 7 and (25) for more details in random perturbations methods to estimate gradients). Next, the BOCO algorithm computes primal decision æ; by an ascent type update, i.e., projecting x;-1 + 7 V, back onto X, where 7 > is the primal ascent step size; see Eq. ( The loss we incur by running BOCO primal update instead of setting arg max Ep, [he (x:)) in the full information setting depends
the specific type of world we are in, i.e., the input sequence PL.T- We later show in Lemma 4.3 that input sequences in each world induce some comparator sequence y1 ... yr E X' so the conversion loss due to BOCO primal ascent updates can be characterized as some BOCO "dynamic" regret Eie(r] hy by (a Later in Lemma 4.6, we show that our BOCO algorithm achieves low dynamic regret against any comparator sequence y.... .r X.
3. Choosing primal ascent step sizes from expert advice for different worlds. Different worlds (and correspondingly different BOCO comparator sequences) may require different "optimal" BOCO primal ascent step sizes in order to achieve optimal regret guarantees. Since we are unaware of the world from which the input sequence Pı. is generated, on top of our primal ascent procedure we run meta "expert" algorithm that allows us to adaptively approximate optimal step sizes in each world. In particular, we consider N experts, each corresponding to a primal ascent step size 74 > 0.

---

and produce independent lever decision based on primal ascent with her own step size; see Eq. ( Then, we dynamically maintain exponential weights w, E A in the N-dimensional simplex over N experts, based on their past performance measured by some surrogate loss function defined in Eq. (8). Finally we set the weighted average primal decision over experts as our ultimate primal decision; see Eq. (6). We later show in Lemma A.3 that such exponentially weighted average BOCO primal ascent decisions achieve low conversion loss compared to the "optimal" BOCO primal ascent expert (i.e., step size) in every world, without having know which world we are in.
Constraint violation check ensure constraint satisfaction. To ensure long-temn constraint satisfaction, we maintain constraint balance B, E I (x,) for each constraint & E [K] that keeps track of our deviation from satisfying the constraint. To make our problem tractable, we make the assumption that there always a "safe action" with which we are always guaranteed to attain some small positive constraint balance
Assumption 3.1 (Safe action). Assume there exists some 3 > 0 and an action Tg E X such that for any (f.g) g) S, we have gu (x( > for all [K].
With the constraint balance, in each period before making a lever decision, we check the following: by playing the safe action in all future rounds nearly violates constraints (step 2 in Algorithm [T. then we hard stop our algorithm and play the safe action in all subsequent rounds. We remark that we do not necessarily know the constraint function value lower bound > 0 in Assumption However, we show later in Theorem 4.1 that by considering any safety buffer 3 < B (e.g.. taking
= 1/ (T)) for large enough T),, we are hard stopping more conservatively, and thus maintain constraint satisfaction. Note that our final regret scales with yez see Lemma 4.6
Algorithm
Input:
Initial dual variable A = O, primal expert solutions ei = 0 for any E [M] perturbation parameter > 0 and E (0, 1): primal ascent step sizes for experts {?....., > 0: dual descent step size
learning rate of the meta-algorithm initial expert weights wi,1 for all i [N]: safety buffer 3 > 0. Initialize constraint balance BR.1 for
I:
[K]
while (for E K)) Bx.: G + (T - t 1) 2 0) do
3:
Compute exponentially weighted average forecaster:
EEciN) ii EiE[N) w/zl
(6)
4: Sample u4 U(S) uniformly random from the unit sphere.
Set æP T + prt, and observe f((m.) and (mx)). Update BE BR,t + (
6: Construct gradient estimate for V L(,,, Ae)
V. (fe(a)) + >T ge(x)))
Update exponential weights experts: Iet l; : X + R. a surrogate loss function to measure performance of each expert. Then we update expert weights by
Wit+1 ws,1 exp (f:))) where
(((z) V
(8)
8: Primal ascent per expert and dual descent:
11 7: V.) and det1 11 1o
( 1/ [2
(9)
9: end while
10: Set stopping time 7. L. For L TA safety option 2;, E...
4 Performance analysis of our constrained BOCO algorithm
In this section, analyze the performance of Algorithm T Jnder input sequence Pı. which may be generated from any world described in Section 2.2 Our first result Lemma 4.1 shows that our algorithm maintains long-term constraint satisfaction almost surely for any input sequence.
"The existence of a safe action not unnatural, and is studied many literature; see instance, let's recall our examples for constraint functions in Section 2. and assume we only have a long-term budget constraint. Then the corresponding safe action for the constraint function g B 21,1 would be any whose first entry Ie,1 so that acquire positive constraint value B > 0.
14
7

---

Lemma 4.1 (Strict constraint satisfaction). Suppose Assumption 3.7 hold, and T is large enough so that the safety buffer 3 To B, where 3 defined in Assumption 3.1 Then. for any [K],
we have EeErT (x,, > 0.
The main result of this paper is the following Theorem 4.2 Algorithm in all worlds specified in Section 2.2
where we bound the regret of our proposed
Theorem 4.2 (Bounding regret in many worlds). Let the safety buffer B Tog(Ty and the
number of experts N max (1. -log ( (1+ DT)ST (
where K is the to- tal number of constraints and D is diameter of the decision set X. Choose the corresponding primal ascent step sizes for the N experts as {i.... .N) = 12-2 + DT) :
+ +1).
O...N -13. Then by laking dual descent step size " = VKT' random perturbation parame-
ter p- = K à and =min (f,K and exponential weighted expert learning rate
min
e = T- we obtain the following bounds on RT in each input setting of interest: (1) Stochastic:
Rr S O(T3/4); (2) Adversarial: Rr S 1 (1- } OPT(P + +
/1 P(y)T) T where
E 1 - min (S.)es [ (x)x) > under Assumption 2.1 3 > is defined in As-
sumption 3.1 Ve = arg max f((a)) + XT (xx)), and P(irr) Eie l Ut+1ll:
(3) 8-corrupted: Rr S O(T8/4 + 8); (4) Periodic: Rr S O(T8/44 + qvT); (5) Ergodic:
Rr O(T3/4 TTT)..
We also summarize our regret bounds in Table [ Although it is always challenging to identify which input procedure the data currently comes from, Theorem 4.2 shows that the proposed Algorithm| [ achieves reasonable regret bound in five input settings without knowing which setting we are in. We remark that in the adversarial setting, our algorithm is (1 - } )-copetiitive, namely, it can achieve at
least a 1 -portion of the reward compared to OPT; later in Section we comment that no sublinear regret is achievable. For the 8-corrupted world, we corrupt instances in the input sequence over time, so if O, we recover the stochastic world and achieve diminishing O(T%/4) regret; in the case we corrupt all samples, then we recover the adversarial case, and the regret becomes ((T) as expected. In the periodic world, if period length q = 1, we recover the stochastic case.
Remark 4.1. We remark that our regret upper bound in the adversarial case depends on the dual variables {>t)tETT) generated throughout the algorithm, which contrasts adversarial regret bounds in [44] that only depend on the total variance of the optimal sequence of This is due to that fact that 444) handles a con-constrained online optimization problem, whereas we tackle a more difficult problem with long-term adversarial constraints that leads to more severe regret degradation as we ensure satisfaction of long-term adversarial constraints. We acknowledge that this bound should ideally be independent of dual variables, and we leave this for future work.
In the rest of this section, we present proof scratch of Theorem 4.2 and the formal proof of the results can be found in Appendix A The high-level idea of the proof is that we decompose total regret into three components in Lemma 4.3 bellow, namely the conversion losses due to hard stopping, dual descent, and primal ascent, respectively. Then, we bound each component's 's regret.
Lemma 4.3 (Regret decomposition). Let (Ae E IK ) be the sequence of dual variables gener- ated from Algorithm I and define hx(x)) = Li(e, Ar) where there Lagrangian function Le(x, A) is defined in Eq. Then we have
OPT(PI.T) Erem E [f(((=))] S -(TT-TTA Exetral AT gz(z)) + RBOCO(TA) (10)
where RBOCO(TA) admits the following bounds in each input setting: (1) Stochastic:
max Eietral
(z(x)) (2) Adversarial: Eietra) 14 h4(T)) (h, (1-11111 (1- OPT(PI:T)
where Yt = arg maX Ep, [f((x)) + Aj [x)]: (3) 8-corrupted: maxxex Ene(Ta) he(x))
hx(())) + 08); (4) Periodic: max Eie(ra) 1x(x)) - hz(x,) + O(1T)); (5) Ergodic:
maxxex Eme(Ta) he(x) hx(wx) (1TTT))
Here, we remark that the first term FIT TA) is the loss due to hard stopping to maintain long-ten term constraint satisfaction; the second term Exerra) A. gi (xx) is the loss due to dual descent; and the
8

---

final term (TA) is the loss due to primal ascent. The first two components turn out to be identical in different settings, and the input model only affects the last term (TAC We next present our key results with which we use to bound first two components (dual descent and hard stop loss), and the third component (primal ascent loss), respectively.
Bounding dual descent and hard stop loss. Our strategy to bound the loss due dual descent and hard stopping relies on bounding some cumulative "complementary slackness" induced from dual descent in the following Lemma 4.4 We note that the bound in Lemma 4.4 holds for any À E [0, F e), and thus by choosing appropriate X. we can "internalize" the losses due dual descent and hard stopping, as demonstrted in Lemma
Lemma 4.4 (Bounding complementary slackness). For any X [0, fel and t E [T], have Ere(g (A, - - gr (x,) = Erejy (A, -
(x, S 3tK + in 1
Lemma 4.5 (Internalizing dual descent and hard stop losses.). Given the stopping time TA E [T].
w.p. 1 we have F(T TA) + ExE(ral ga))) s ЧTKG* Σ
+ + G..
Bounding primal ascent loss (dynamic BOCO regret). We present our main result Lemma 4.6 which bounds the loss due primal ascent for given any comparator sequence y ... y/T X.
Lemma 4.6 (Bounding primal ascent (dynamic BOCO regret)). For any i E [N], te E [T] and any
sequence yıat X we have Ere(1] hr (y+) - (x, o ((Ltaal + 1+P(y)TT >KT 21
+T++
where P(yr:r) = Eietr-ijll yt+ill, and parameters (a,, (o,",, are specified in Algorithm
Proof sketch. We define the smoothed versionss of BOCO rewards h, X - R as (x) E [Lr + pv, At)]. Then, we decompose the primal ascent loss (BOCO dynamic regret) (hr (yr) - (x,) into terms:
Eh --(((1a)))) (h a)v.) - Eren
hr (x,)),
where we recall the ã. is the un-perturbed version of our primal lever decision in Algorithm first and third summands can directly be bounded via exploiting Lipschtiz continuity properties for h (see Lemma A. The second summand can further be upper bounded (using Lemma A.2 by the surrogate loss difference between the primal decision weighted over all expert decisions and the comparator decision, namely & (ã,)
| The
E, [(1 - a)zr). Then, choose any expert i [N] corresponding to primal ascent step size 7/2 > as an "intermediary" and decompose cumulative surrogate loss as EiENy (&c (ā:) - & ((1
a)y))) = Everry (Ce (6,)-4, (z))) + (6e (æ:)
t, ((1 ([(11a))p ()).) The first summand corresponds to the cumulative loss of our unperturbed primal decisions against any expert, and the second summand represents the cumulative loss of any expert w.r.t. the comparator sequence. Both summands are bounded in Lemma A.3
We note that choosing different experts as the intermediary may yield different bounds. But since Lemma A.3 holds for any expert i E [N]. we can consider the expert with the "optimal" primal ascent step size each world, respectively.
5 Additional discussions
Lower bounds. A natural question ask is whether regret bounds in Theorem 4.2 are optimal. Here, we look at lower bounds in "relaxed" problem settings, e.g., bandit online convex optimization with no-constraints 11 44, online constrained optimization under full-information feedback R 10
Stochastic
8-corrupted
Adversarial
Periodic
Ergodic
R(VT)
19
Q(VT + 8)
((1-)))
R(VTT)
NA
These relaxed lower bounds are applicable to our setting (though they may not be the tightest bounds), and we can see that it may be possible to employ more complex machinery to attain better regret performances for our bandit convex online optimization setup with uncertain constraints. Yet, to identify algorithm that can achieve the optimal regret in many worlds is an extremely challenging

---

open problem. For instance, even in the relaxed setting of bandit convex optimization with no- constraints, to the best of our knowledge there no universal algorithm that achieves optimal regret in just the stochastic and adversarial worlds.
Other applications. Our proposed Algorithm I addressses a more general problem of online decision making with multt-dimennional decisions, bandit feedback and long-time uncertain constraints, That being said, our algorithm can also be applicable to other problem settings, for example:
Personalized recommendation and assortment in online retailing. Online retail platforms aim to optimize sales revenue by recommending a limited assortment of products to customers. However, the likelihood of customer purchases given an assortment as well as their preferences are unknown, and different customer types may change over time due to evolving market trends. Platforms only observe bandit binary purchase decisions. Hence in our context, the decision set X' represents a probability simplex over d items. The online decisions at E X' correspond to recommendation probabilities for each item. The function fe(xz) reflects the revenue generated from customer purchases, while gr (3x) captures assortment capacity constraints, product inventory limits, fairness considerations to ensure equal visibility for each product (18).
Real time posted pricing in E-commerce and cloud computing, In online E-commerce platforms such as Amazon and eBay, sellers set prices to sell various items to sequentially arriingg customers [5]4 126;; and in cloud computing, operators of cloud services such as Alibaba Cloud (Alicloud) or Amazon Web Services (AWS) set prices for renting out different computing capacities (virtual machines, VMs etc.) upon customer requests (39 The arrival of customer types as well as their demand may differ significantly over time (think about demand for sanitary products during pandemics outbursts, or computing resource demands during periodic business hours). Further, decision makers only get to observe (bandit) demand at the realized pricing decisions. Thereby, we can view 2; E X as the vector of prices for various sold products, fa(x))) as the generated revenue over given period, gr (3)) as real time product/resource capacity constraints, operating cost constraints, etc.
References
Programmatic advertising trends, stats, & news.
htttes//roirevvalttion.ccmm
progr programmatice amaatic-avverttiinngg stands-stats- swwesstttttteeee n Accessed: 2023-03-30.
[2] Programmatic digital display advertising in 2022: Ad spend, formats, and forecast. https: https:///ww /www
Insiderintell wwwrrritteegggene.nmmm www.ence..om/iiiieee
digittllddiial---- display-paaal spending/
Ac-
cessed: 2023-03-30.
[3] Shipra Agrawal. Zizhuo Wang, and Yinyu Ye. A dynamic near-optimal algorithm for online linear programming. Operations Research, 62(4):876-800, 2014.
[4] Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Linear stochastic bandits under safety constraints. Advances in Neural Information Processing Systems, 32, 2019.
[5] Moshe Babaioff, Shaddin Dughmi, Robert Kleinberg, and Aleksandrs Slivkins. Dynamic pricing with limited supply, 2015.
[6] Ashwinkumar Badanidiyuru, Robert Kleinberg. and Aleksandrs Slivkins. Bandits with knapsacks. Journal of the ACM (JACM), 65(3):1-55, 2018.
[7] Santiago Balseiro, Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. Robust auction design in the auto-bidding world. Advances in Neural Information Processing Systems, 34: 34:17777-17788, 2021.
[8] Santiago Balsciro and Yonatan Gur. Learning in repeated auctions with budgets: Regret minimization and cquilibrium. Management Science, 6509):395233968 2019.
[9] Santiago Balseiro, Anthony Kim, Mohammad Mahdian, and Vahab Mirrokni. strategies repeated auctions. Operations Research, 69(3):859-88) 8769 2021.
[10] Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. The best of many worlds: Dual mirror descent for online allocation problems. Operations Research, 7 11(1)1001-119 2023.
[11] Omar Besbes, Yonatan Gur, and Assal Zeevi. Stochastic multi-armed-barn bandit problem with non-stationary rewards. Advances in Neural Information Processing Systems, 27, 2014.
[12] Mark Braverman, Jieming Mao, Jon Schneider, and Matt Weinberg. Selling to no-regret buyer. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 523-538, 2018.
[13] Mattco Castiglioni, Andrea Celli, and Christian Kroer. Online learning with knapsacks: the best of both worlds. In International Conference on Machine Learning, pages 2767-2783 PMLR, 2022.
[14] Matteo Castiglioni, Andrea Celli, and Christian Kroer. Online bidding in repeated non- truttru auctions under budget and roi constraints. arXiv preprint ar22223002.0,203, 2023.
10

---

[15] Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Giulia Romano, and Nicola Gatt.. A unifying framework for online optimization with long-term constraints. Advances in Neural Information Processing Systems, 35:33589-33602, 2022.
[16] Sapana Chaudhary and Dileep Kalathil, Safe online convex optimization with unknown linear safety constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 6175-6182, 2022.
[17] Lin Chen, Mingrui Zhang, and Amin Karbasi. Projection free bandit convex optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2047- 2056. PMLR, 2019.
[18] Qinyi Chen, Negin Golrezaci, Fransisca Susan, and Edy Baskoro. Fair assortment planning. arXiv preprint arXiv:2208,07344 2022.
[19] Varsha Dani, Sham M Kakade, and Thomas Hayes. The price of bandit information for online optimization. Advances in Neural Information Processing Systems, 20, 2007.
[20] Yuan Deng, Negin Golrezaci, Patrick Jaillet, Jason Cheuk Nam Liang, and Vahab Mirrokni. Fairness in the autobidding world with machine-lcamee advice. arXiv preprint arXiv:2209.041
2022.
[21] Yuan Deng. Negin Golrezaei, Patrick Jaillet, Jason Cheuk Nam Liang. and Vahab Mirronni. Multi Multi-channel autobidding with budget and roi constraints. arXiv preprint arXiiv2330.0111 0133,,1122313 2023.
[22] Yuan Deng, Jieming Mao, Vahab Mirrokni, Hanrui Zhang, and Song Zuo. Efficiency of the first-price auction in the autobidding world. arXiv preprint 22xx:2208.00660 2022.
[23] Yuan Deng. Jieming Mao. Vahab Mirrokni, and Song Zuo. Towards efficient auctions in an auto-bidding world. In Proceedings of the Web Conference 2021. pages 3965-3973, 2021.
[24] Zhe Feng, Swati Padmanabhan, and Di Wang. Online bidding algorithms for return-on on-spend constrained advertisers. In Proceedings of the ACM Web Conference 2023, pages 3550-3560, 2023.
[25] Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without a gradient. Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 385-394, 2005.
[26] Negin Golrezaei, Patrick Jaillet, and Jason Cheuk Nam Liang. No-regret learning in price competitions under consumer reference effects. Advances in Neural Information Processing Systems, 33:21416-22127, 2020.
[27] Negin Golrezaei, Patrick Jaillet, and Jason Cheuk Nam Liang. Incentive-aware contextual pricing with non parametric market noise. In International Conference on Artificial Intelligence and Statistics, pages 9331 13319336. PMLR, 2023.
[28] Negin Golrezaci, Patrick Jaillet, Jason Cheuk Nam Liang, and Vahab Mirrokni. Bidding and pricing in budget and ROI constrained markets. arXiv preprint arXiv:2 107.07725, 2021.
[29] Negin Golrezaei, Vahideh Manshadi, Jon Schneider, and Shreyas Sekar. Learning product rankings robust to fake users. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 560-561, 2021.
[30] Yanjun Han, Zhengyuan Zhou, Aaron Flores, Erik Ordentlich, and Tsachy Weissman. Learning to bid optimally and efficiently in adversarial first-price auctions. arXiv preprint arXiv:2007.0455 2020.
[31] Yanjun Han, Zhengyuan Zhou, and Tsachy Weissman. Optimal no-regret learning repeated first-price auctions. arXiv preprint arXiv:2003.0973 2020.
[32] Elad Hazan and Yuanzhi Li. An optimal algorithm for bandit convex optimization. arXiv preprint arXiv: 1603. 2016.
[33] Rodolphe Jenatton, Jim Huang, and Cédric Archambeau. Adaptive algorithms for online convex optimiza- tion with long-term constraints. In International Conference on Machine Learning, pages 402-411. PMLR,
2016.
[34] Chia- Kuo, Hyun-Soo Ahn, and Göker Aydın. Dynamic pricing negotiate. Operations Research. 59(4):882- 897, 2011.
of limited inventories when customers
[35] 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.
[36] 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( (11):2503-2528 2012.
[37] Shic Mannor, John N Tsitsiklis, and Jia Yuan Yu. Online learning with sample path constraints. Journal of Machine Learning Research, 10(3), 2009.
[38] Aranyak Mehta. Auction design in an auto-bidding setting: Randomization improves efficiency beyond vcg. In Proceedings of the ACM Web Conference 2022, pages 173-181, 2022.
[39] Huijie Peng, Yan Cheng. and Xingyuan Li. sial-time pricing method for spot cloud services with non-stationary excess capacity. Sustainabiliry, 15(4):3363, 2023.

---

[40] Wen Sun, Debadeepta Dey, and Ashish Kapoor. Safety-aware algorithms for adversarial contextual bandit. In International Conference Machine Learning, pages 3280-3288. PMLR, 2017.
[41] Jonathan Weed, Vianney Perchet, and Philippe Rigollet. Online learning repeated auctions. Conference on Learning Theory, pages 1562-1583. PMLR, 2016.
[42] Scott Yang and Mehryar Mohri. Optimistic bandit convex optimization. Advances in Newral Information
Processing Systems, 29, 2016.
[43] Jianjun Yuan and Andrew Lamperski. Online convex optimization for cumulative constraints. Advances in Neural Information Processing Systems, 31, 2018.
[44] Peng Zhao, Guanghui Wang, Lijun Zhang, and Zhi- Hua Zhou. Bandit convex optimization in non-stationary environments. The Journal of Machine Learning Research, 22(1):5562-5606 2021.
12

---

Appendices for
Online Ad Procurement in Non-stationary Autobidding Worlds
A Proofs for Section 4
A.1 Additional definitions for Section
Definition A.1 (Total variation between probability distributions). Consider two distributions
(P,P') S (SS). Then we define their total variation as ||P -P'Ilv =
ʃs -(s)s_ssss)dds.
We also define the smoothed version of h2 : X2 - (see Eq. 5 for any t as follows:
hx(x)) (B) pr, Xc]]
(11)
where we recall the Lagrangian function L. is defined in Eq.
A.2 Additional lemmas for Section
Lemma A.1 (Lipschitz continuity). Let Assumption 2.1 hold, and we recall the definitions of he (x)
and (x) from Egs. (5) and (IT). respectively, and recall d1 .....8 Ar as the dual variables generated
from Algorithm 1 Then for any (æ.x') S N, we have (h+(x)) - he(xx') (1 K L || x'll
and [x)( he(()) S k
Lemma A.2 (Bounding BOCO dynamic regret with surrogate loss). Recall the definition hz(x)) (B) (x + pv, pv, ).)). Then, h,(x) is concave. Further, For any y (1-1a a) have hy(y)) - (T..) < Eur-U())) (xx,) (V)),, where 3t is defined in Eq. ( and the surrogate loss function l X TR. is defined in Eq. (8).
Lemma A.3 (Bounding surrogate loss for each expert). Recall the definition of individual forecasters Tt defined in Eq. (9), and the surrogate loss function l X defined in Eq.
08 Then for
any E [N] and any sequence yır E X2, by defining P(y)T) = -EE(T-I]ll yt+ (see
Lemma 4.6), we have (i) ExE(Ty(e (a+t) be ((L a)y:)) I O (01+P(mm)) TT and (ii) EIE(T (4e (4 (=:)) S O(Tc+ + 2). where the constant specified in Algorithm Here, recall D is the diameter of the decision set X.
71
The proof's of Lemmas A.I A.2 A.3 are shown in Appendices A.9
A.10 and A.1l respectively.
A.3 Proof for Lemma
Proof. For any A E [K] we have
(0)
Σ (.x)
Σ (.r(( + Σ gh.
2
Σ
B(T TA + 11
EE[T]
tE|TA-1]
t=TA
tE 1]
(12)
(6) 2
Σ
gk.e(x)) + B(T - TA) +
G + G+3>0,
1E|TA-1]
where in (a) we set D, 3 for all it = TA ... T and (w,) > 3 for any k E [K]; (b) follows from the definition of the stopping time such that for any t' TA and k E [K] we have Enele) Ik.t (xt).
G + 3(T -' 0.
A.4 Proof for Lemma 4.4
Proof. It is easy to
d
II (x (VL,(II
arg argmin XE( VaLiar (.) TA + +
A.l...
By the first-order stationary condition

---

at A4+1, we have for any À E [0, ee
V (aCr( (Aut+ - (2 dct1)
(A-de+1) 20.
Then for all X 200 it follows that
VALi(ar, A.) T(): - A)
= VALila, A T(): - Aet1) + VALi(EE X1) A - 2)
1
I VALolar A1) (Ax-
- -x+11) + (A141 A1) A(+1))
7
s VALi(a, A (A. - Aet1) +
| xe11
1 - 11-1
-11++1 Arl1
21
2nj
27
$ ! VIVA AOII a A,
2|
a Act1112
2n
2n
By telescoping argument, we have
(xT,
2) -A)
"
Σ
(0,, )+)112+
1
11 A1112
2
27
rE(1
rE((]
(13)
" Σ
V 11)
1
||
2 Tc((]
2m
where in the final equality used A 0. Also,
VVC,, )11 = (x+)) s KG"
(14)
Hence, combining Eqs. 13 and 14 we get the desired bound.
O
A.5 Proof of Lemma 4.5
Proof. If TA T, taking À in Lemma 4.4 yields Every (x,)) I TTK&² and thus the desired inequality holds. TA < T, then there exists some & E [K] such that Eie(ra) (
G (T - TA- - 1) < 0, so by taking À [ ex (ex E RR the unit vector whose kth entry is 1)
Lemma 4.4 yields
Σ
XT g((()) <
Σ gT + TKK +
_
1
21)
rE|TAl
LE[ral
F
Σ gxx) + TKK +
1
F
=
B
2n
3
tE(FAl
F
F
1 1/F F
B(T - - 11)
G+
!
TKŌ +
B
3
2
2n
3
= F(T - TA) + F+
F
G
"
TKK2
1/F F
8
2
2n
3
which completes the proof.
A.6
Proof of Lemma 4.6
Proof. Recall the definition of ha( in Eq. (5) Then, have
Σ TE(A]
ho (yr)
Σ h (x,)
TE(t)
(15)
Σ
(((())) (1-((1 - a)yr) 1+(((1 - a)yr) - Ter (x+) hr( - h (x()))
rElt
B

---

Bounding A.
hr(r)) - ((1- = hy( - (41 a)y, + h2 ((1 (1yr) - hr((1 (1((1-1()))))) a)y+))
(a) <
(1 + K Lall y- || +1 + K F
3 )Pp
(16)
(1 (1+ K LaD (1+ K F
Ip
3
where (a) follows from Lemma A.1 (b) follows from 0 E X.
||
137, - -0 I since we assumed
Bounding
Σ
((1 a)y,) hr (ãx)
TE(t]
(4)
Σ B8) [e (++) 6 a)y+)]
rE(t]
(17)
Σ
E Bu,~U(S) (xr) la (xx)) + tx((t, (+1 a))
rE[t]
P(yl:))
WK ET + Te -
%
p²
where (a) follows from Lemma A.2 and (b) follows from Lemma A.3 (i) and (ii).
Bounding C.
hr - 1r (xx)
h-()))
- 14 -xx(#r))
-,( 1,, (x.7)
(a)
F
) (1 K F
(1+
) 1|,1,1,, x
(b)
(1+
F
Lp + (1 + K F
[ pu
(18)
3
3
F
2p(1 K
) L
where (a) follows Lemma A.I (b) from the definition a, 8. + pul Algorithm
A.7 Proof of Lemma
In this section, we provide upper bounds of the regret term under five different environments of input procedures: stochastic, adversarial, 5-corrupted, periodic, and ergodic. The structure of the following proof might seem similar [00;; see [IO, Sections 3-5). However, we note that the proof techniques are fundamentally different since our paper considers the bandit feedback environment while [10] makes sequential decisions after observations.
Stochastic.
Proof. In the stochastic regime, we have P P1 Pr for some P. and therefore we can rewrite OPT(PI.) in Eq. (I) as followed
OPT(PI:))
F(x))
Σ (E|2]
G(a.) 2 0.
TETEAT
EE[T]
3

---

where we defined F(x) = (((a))))((()) and G(x) ((rg))=l)(()) for any X. Hence, for any À 2 we have
OPT(P1:T) T- OPT(P1:)+ + TA
(P:))
T
S -T-TA (F) + TA
Σ
(F(x)) A G(m))
max TLTEXT
T
tE[T]
(19)
(T - +
TA
(F(x) + G(x))
T
tE(T)
(T TA) F + TA max sE
(F(x)+ +
where in the inequality we applied Assumption 2.1 which states supwEx [f()) S F for all (f.g)
S. Choosing À A = + >ne(Ta) ) we have
OPT(PI:T)
$ E FA)F Ta max xE (F(x) X G(a))
< E (T FA)F
max Σ
+ ()( G(z)
rE[Ta]
E
(T F
P
Σ LE|Ta]
E
f((x)
X )x))( aPH6-))
(20)
(T
F
max
Σ
E he(()))
[(H4-1))]
xE
tE[TA]
s B (T TA)
Σ rE(Ta)
he((z)
max
#EX
where in (a) we used the fact that X, is measuurbbe, in (b) we used definitions h₂(x)
(r 2x) and Lx(:;)) A) f((x) X gx))) in Eqs.
(4) and (5) respectively.
On the other hand, we have
fx,)) = h,(x,) AT (x,))
(21)
so combining this with Eq. 20 we have
OPT(P Σ (ax)) < E E((T (T TA) + max
Σ
(hr(w)) - he(az)) +
Σ
XT g
ØEd (E[Ta]
1E|2]
TETA
(22)
where we also used the fact that f((x) 2 0 for all t TA +1+.. and x X.
Adversarial.
Proof. Recall the definition of & is Theorem 4.2
{= 1 min (gg)s minge K) Ih (x)
1.
(23)
For any t E [T], define D. = arg max f((x) + A (z).
By comparing to the safety action Øg X which ensures gu (xs) B for any E [K] and
(f.g) E S, as well as the optimal hindsight action x; E X' (i.e., ii... is the optimal decision sequence OPT(P we have
f(().) + A ( 2 f((2g) + X (x 2 BATe e
(24)
and f( A (.)) 2 f((x;) + X, (z;))

---

We further have
(.. (()))) + (5 - 1)f((())
f(())) + g((z)) - (.))( + (E - (->, - e)
(25)
f((x)) Xo g( - g. + +5 - e
V [(())) EX, g
where (a) follows Eq. (2 in (b) used the fact that (x.;(x)) + (E 1)3 0 since have
gg)es minke(K] K EEE (x) + 1)8) 2 0 (see Eq. 23 ). Hence we have
OPT(PIT) - Σ [xf((
LE|T]
B 1 (( fc(20e]
(PT(P + Σ
:E(T]
(26)
1 (1- OPT(P
+ Σ fe(T.) fe(xx) + 2,7 (T
AE(T]
s (1- )PT((P)))))
(T FA)F
(file) f((x)) + N, 9T.(
KETA
which completes the proof.
5-corrupted.
Here, we will prove more general d-corrupted model where the input distribution sequence Pi. satisfies the following:
Σ |P. LE|T
1 T
Σ Pallrv 8 SE[T]
(27)
where the total variation norm defined in Definition A. In fact, the definition in Section 2.2 for the d-corrupted regime satisfies the above property: recall the definition Section 2.2. there exists P E (SS) as well as 5 E N periods T = [TI... C [T] such that P = P for all7 & T, so for
any & T. we have
1 PP
E PallrV 1|p 1 +E[T]
(
TP (P. (P.-P))
-P)
11v
T
sET
(28)
5
Σ (P P.)llT S =11 T
2T
SE
On the other hand, we have for any t I. & ExEryy PallTV 2/2 After summing it up, get
Σ PPP T tE[T]
Σ P.lITV
Σ PP:
Σ
PallTV +
Σ IP T
1 Σ
Pallrv sE(T
=
T
SELT]
IET
xE[T]
EET
8
8
<
2 + (T
-
< 6
2T
which coincides with our general definition of ò-corruption in Eq. 27
We now prove the 5-corruption regime under the general definition in Eq. 27 Define P. =
+ Eser P., F(x) = [(),)))(((=))]) G(x)) = ((rr)))) (=))) F.(x)) = (( and
Gx(x) = P. (x))) for all E [T] and any X. Then for any À [0, fel. we have
5

---

(PT(P x
max #ir ELTENT
(F((x)) T Gx+)))
NE(T]
(F(m)) + G + (F + GK F )6
max #1T EXT
Σ LE[T]
3)
(29)
(F(x)) + + G(z)) (F GK F 3))
T
max =EA
where the last inequality follows the definitions of (F, G), Assumption 2.1 and the general definition
of 6-corruption in Eq. (27). After choosing À 74 Eie(ra) X similar to our proof in Eq. (20) for the stochastic case we have
(PT()).))
E
T TA OPT(P T
AA T
OPT(PITT
(0) S
E
(T FA)
TA max (f(z) + GTx(()) + IA (F + GK 3
ZEA
TA) + 7 [ + GK
88 + max
Σ
F(x)) + 2, ((x))
B
tE(TA)
2 B ( TA) + (1
)
TA
(F + GK
F
0 + max REX LE|Ta]
Σ (F((z)) - X (x))
T
8
F
FA)F+ SB (T (()= + (1+
TA
(F + GK
16 + max TEX tE|Ta]
Σ
[[HH)-))]
T
3
F
$ B (T FA)F + 2(F + GK )8
+ max mEX
Σ he(z))
B
[E|TA]
(30)
where (a) follows from Eq. 29 (b) follows from the definition of general 8-corruption in Eq. 27
Finally, we complete the proof by using the definition fi(x;) h,(x,) A, ge(z)) and following the same argument as in Eq. 22 for the stochastic regime.
Periodic.
Recall in Section 2.2 that in the periodic regime, there exists cycle length g E N such that T = cq for some integer 2 with PI.T as Pi.g = P
-P(c-11g+11T- For any ( E [T). define E [c] such that (c: 1)q + < t < egq. After denoting P = ExEele Pt, we define the mean deviation within a single cycle of length
MD(P1.g) = Σ [P: PlilV and 6=c (c.MD(P1:g)
(31)
15159
We define F(x) = E (( G(x)) = {())))))()))} Fe(x)) = [( and
Gx(x) = E(sg)>,, (x(x) for all t E [T]] and any I E X. Then for any A E [0, fel, we have
OPT(PITT) <
max
Σ
(F.( - x (z()))
ELTENT
(E[T]
Σ (Fi(.)) x Gx()))
C. max
m1 EX
po max F(x) F(x)+XT((=)) (F + GK F
B lc. (D
$ cq (nx (F + GK ))

---

where the equality follows the nature of periodic setting and the last inequality follows the def- -. X
initions of (F, G), Assumption 2.1 and 31 After choosing X Eneler -1] 74 (2-1)g+1
(er, -1)9 Aerr 1)g-11 we further have that
(PT(PI:T)
T- TA (OP((PITT) + TA (PT())
T
max F(x) + G(a))) + (F + GK F )) wed
$ (T - FA) + TA
(T - (f) + max TE
TaF(x)+ +
qd + (TΛ - -CTA 1) 1)041
G(x)
žElera !]
F (F GK )6
(T- - FA + max (1-
Σ
(((x) + X (e-1)tt1
#Ext
8ElerA-11
+ (TA (CT - 1}1) (F(#))
AT (C.A (o.t-1111G(ar))) + IA (f + GK 3) )8
7
F
(T -TA) + max
Σ
(f(x) + G()))) + G Σ 1A, (a-1)i+1l +
TA AA
GK F =
g )6.
T
BE(FA)
(E(Ta]
From Eq. (9) Algorithml
we know that || delli S nGK,, which further implies || 1] and thus
Xelli S rjGii for any i E
Σ a A Dotill S GK
Σ 6E/4-1]
is 1 2 GKncrag
(32)
tE[Ta]
After combining the two equations above, it follows that OPT(PI:T)
F
< E (T- F + max
Σ
(F(x) + X, x(T)) + 6 12 + TA + GK
B 10
T
xEX
tE|TAl
(F((z) + X, G((x)) + cp 12 + 2(F + GK F
< E
(T F
max
Σ
B 16
2EX
=2
tE(TA]
F
< B (T-Tx) + 2F + GK
18++ B
6 Knn + max
Σ
he(2))
[(H+-
(E|TA]
F c
< BT(T-TA)E FA) 2( + GK 18+
3 38
KngT + max
Σ he(z))
#EX
(E(Ta)
where the second last inequality follows from C, 4 S cq
Finally, we complete the proof by using the definition fi(w,) = h((w)) A7 g.))) and following the same argument as in Eq. 22 for the stochastic regime.
Ergodic.
Consider some x 2 log(T"). Given the input distribution sequence PI,T, denote P -( as the conditional distribution of (fites g(+x) conditioned on the {(fr ((fre)))rre(o)- Then, in the ergodic regime, there exists a stationary distribution P. E A(S) and absolute constant R 0 such that
sup sup [|P(e+))]|-1] -P S 6 = Rexp(-x) (e== tE[T-x]
(33)
7

---

see 10 Section 5.2] for further discussions. By defining F(x) = E (f G(z) = E [()))=)( (()) B(ta))-P---l-- G(+n(z) B(sg))Pa-ollt- [g(x)]
F((z) L.) [f()]] and G.( (g(=)) for all [2] and any x E X, we
F e]. it follows that know that for any x E [0,
(PI())
max E #LTEN
Σ (Fi(2)) + A G(()))
ME|T]
T
max E
Σ (Fi(2))) + X G((z))
+ max
E
Σ (Peta((ttN)) + A G(ta((etta))
Z EX'
R+TIPEXT-
[E|M]
(F(#)t)) + +X ((((4))) (F + GK F
(F + GK )x+
+
max
Σ
8) (T (T- K)6
3
EXT
1=1
(F xx+ GK F
F )
S T max (Fx)) A G(x)) + (F #E
)
3
(34)
By choosing x = 1 TA
Ede(Ta) As, we further have
OPT(P1:1)
TA OPT(PI:T) + IA OPT(PEE))
E
T
T
< E
(T
-T
TTA
max TEX
(F(x) (F(x)+ +XTā(=))] + (F
(F+ + GK F g)++ ( OK F
8 .T8
[(x))) + +(F + GK 8 g) (F+ GGK+ F
E
(T-
F
max
Σ
3)
EE
IE[TAL
(fita(x)) + 27 G(+ + (F GK F _
I 2(F + GK F 33)
< E
(T FA
+ max Σ
.T8 T8
LE[TAl
E
(T F + max E
(fite(()) + ATn + (d: - -x+xx) T Gete(
LE|TAl
F
+
(F + GK
)k 2(F + GK z) 3).88 T8
3
EE
(T F + max Σ
(F) + Gran(a)) KNT
tE(Tal
F nn+ 2(F + GK F 3) -K-)) 3TT8
(F + GK
3
S E
(T FT
max
Σ
(Fita(x) + AT Genn(()))) + KG
[E[TA-K]
F
+ +2(F= + GK + 2(F + 3) T8
nk
3
(
TA
kTTKK +2 + SLF++GK GG F
+ +GK F
E (T F
Σ
he(3r)
) .T8
max
SEAt
3
1=+t1
<
(T FF
max
Σ Nx(20] + KKTK + + + GK F
G + +GK 5 .T8
SE(TAl
8

---

( S
(T TA)F +
max
Σ
G))+ he(z)] + KOjKKG + +2(F + GK gi ) + GK
mEd
TE(TA]
where in (a). from (9) in Algorithm know that ||A++1 dell1 n,K, which further implies
| >xll1 S kTGK and thus
(A A4tR) - G(+n(ar) S KmK
(35)
In (b), used the fact that for any t 2 x 1, we have
Σ
(Fe+x(1)) + A
max mE
tELTA x)
Σ
R (eta((o) (r.gr)re(t-11)
max ØE
(36)
VE(TA N)
Σ
hetx(z))
max mEX
KE(TA-K x)
In (c) we used the fact that k 2 17g so 8 Rexp(-n) 2 R.
Finally, we complete the proof by using the definition f+(x)) = (x+)) X, g:())) and following the same argument as in Eq. 22 for the stochastic regime.
A.8 Proof of Theorem
Proof. We bound the regret in every world as followed
Rx = OPT(PIT) - Σ
E (xx(,))
1E|T]
(0)
E
F(T TA) + Σ
X gzx)) RBoco(TA) (TA)
LE[Ta]
E RROCO(TA)
where (a) follows from Lemma 4.3 and (b) follows from Lemma Lemma for each world.
4.5 Recall RBoco is specified
In the following we bound RBoCo(TA) for each world. Stochastic.
he(x)) -i((x))) 2 0
(4)
(p+t)T
1 KKT
B22 +Te !) @ o(Ti):
E RBUCO(TT))
E max xEN
Σ [E[TA]
+
B %
(37)
where (a) follows from Lemma 4.6 by taking the comparator sequence Yt arg m Eie(Ta) (x) for all Fax such that P(y = 1, as well as any primal
ascent expert E [N]: (b) follows from taking 1 = 1
VKT p T -
[r)
and finally choosing 7: K AT) Recall all primal ascent expert stepsizes are (m... ....... K- (1 + DT : O...N 1}.
5-corrupted, Periodic, and Ergodic. The proof is nearly identical with that of the stochastic world in Eq. (37) given that we still consider the comparator sequence arg max EeE(TA) (x( for all E [TA] such that P(y+.) 1. Hence we will omit the proof.

---

Adversarial. Recall the definition Dr arg maX f(())) + A, g(z)).
Then we have
E [RoccO(Ta]]
(1-5) OPT(PI:)+ +
Σ E
(T))
rE[TA]
S 0 (
1+ P(TIT)
RKT
+ +Te -) B2
(38)
B
7
(1- ( P(ÿn.T) .T?) T
where we chose the primal ascent stepsize 7/s s.t.
K - (( S ni S K 8 (1 (1+ P =T
(39)
We note that such % must exist because P 1 DT given all y X, so that the largest element in the primal ascent stepsize set, namely K à (1 DT) T7 is larger than the upper bound above, namely K- t + P(
A.9 Proof for Lemma
A.1
Proof. Recall the definition ha(x) = (xx) + X (x) in Eq. ( Then we have
(x(x)) - he(2z)) s fi(x) - f((x))f((z)) + || IIl. (I))(x)) - g((2'))l
(40)
② L| - x''l + K 411 o'l = (1+ K 3 )L 1|:0
x'1,
3
where (a) follows from the fact that any (f.g)= E S are L- L-lipschitz under Assumption On the other hand, recall the definition hx(2) = (B) (1 + no, Ae) in Eq.
2.1
Then we have
F he(x)) - (x) = Ee h((()) h1( + po)] & (1+ 3 Lp E
||aa|
s(1 K
Lp.
B
(41)
where the inequality follows from the first part of this lemma.
A.10 Proof of Lemma A.2
Proof. Recall the definitions hx()) = [e(x)) + 2, (x)) in Eq. 5 and h₂(x)) Ee Le(( (2)
pv, A:)] in Eq. TT Then, we have
he(y) - (..))
< (V)( -xi)
(b) Esn [hr + pu) u4 ã,)
Em ( he(@ē + pur) un y ã.)
(42)
Es))) [V y Ti)l
(d) Eu,-U(s) (wx) - E, (y))
where (a) follows from concavity he(:); (b) follows from Lemma B.2 by taking -hi- so that in the lemma - -V V.BBe-D(B) + pv)] Vh((w) and - -u--U)) [h(x pr) u] = Eu)u(s) [ha + pu)- u]: (c) follows from the gradient estimate in Eq. (7) where
d V. d (z. + X (x:)) u, - h...)) un p
d
-1 1-,,,,, + prs)) 4
P
Finally, (d) follows from the definition of surrogate loss functions in Eq. 8
10

---

A.11 Proof of Lemma A.3
Proving (i):
Proof. Let's denote V, = |vll. Since 3/41 = lla (0) + v.) we have l1y 1/+1l 5
lyy - (x) 76 V.)l for any y E (1 a... Then
y - || < lyy - (y ) + v
| 1 < | + 2y ( Ft) 2% V (y- mt) V
Hence by taking y (1 a)y E (1 - a and rearranging we get
2% (ee (z:) - 4 ((1 - -))x:)
2% V ((1 - a)y: x
(43)
S |ل ? |لا+م|| 1|2 + 2(1 a)yy (0/++1 x vV
Telescoping with r = 1 t we get
Σ
E
Σ l (11=a)y-)
TE(1]
$
a
yr (#7+1
xt) + 78
Σ V2
2%
%
2
tE|T]
7E((]
27/s
1
|
||
+
1
%
y: +++++
(yr yr+1)
T
+ 78 Σ
(44)
rE(t-1]
TE(()
1
[|2
1-
||3/ [19:1-11@0+++1
||
Σ
|/// yr+1ll
||0
22
Σ
v2
276
%
rE(L-11
rE((]
(1 - a)) D2
a)2D (1-o)²D
(1
(P(y).) + D) +
k
K
F
b.
27/
7
2p²
B
where P(Bre) is defined in the lemma statement.
Proving (ii):
Proof. First, have for any E [T) E [N]
d p (
F
(())) (z. ]
| aell
(1 a) (45)
where we recall D sup [cx - x'|
|| is the diameter of X, and both { σ.} C (1 a)x
Define W. = -EEENN) wae for all 1 E (T). then
W4+1 We
Wie exp (-el((z))
log
log
W₂
iE[M
log
Texp
(-el((a()))
(a)
5
elE,, We [e((at))
2
d
F
K G
F
(1 (1-ool (1-a)D)
(46)
2
p
3
(
dle (Bi.wi/Wi
1)
+
6
(d
F K F
0
(1 o)D
2
p
8
(c)
2
d
F
dl
(ix)
+
F
+
K
(1- a)D
2
p
B
11

---

Here (a) follows from Hoeffding's s Lemma as described in Lemma B.1 where we take X = (,
a= - F + k (
(1 D and b ( G (1 D) (b) follows from the
definition that (()z)= V. (a ã.) is a linear function in æ; (c) follows from (
Hence, telescoping the above get
W
(ā,) + 6e2
( F + k 5) (1 -a-a)))² 2
log
I - Σ
(47)
W1
2
=E(t]
On the other hand, we have
We+1
log
(og(W(41) lo1
W1
log(max Ws,e) log(NV)
[E[N]
= max log(w;.d) - log((N) [E[N]
(48)
))
max log (E(N)
Wi,1 exp
[ er
(it)) -log(N)
min NE[N]
Ey
log(NV.
7E(C]
Hence, after combining Eqs.
47 and
48
and dividing both sides by e > 0, we get
Σ
4
(
+
Le
F
+ K
G
(1 (1-a)D)
min iE[N] TE(1]
lr (r.
log(N)
2
p
TE((]
d
F + K G) (1 (1-a) (a-a)D) 2
log(N)
by (i,)
min
Ey
(x+)
N
2
p
7E(4
7E(()
4 (m+)
Σ l
T
v
le
(
d
F
K
F
(1 - -a))
log(N))
Vi E [N],
p
3
[E(
[
(49)
which completes the proof.
B Supplementary lemmas
Lemma B.1 (Hoeffding's lemma). Let X be some random variable such that S X < b almost
surely for some a, b E R. Then for any E R, have E [exp(-eX)] S exp (-dE [X] (b-a))
Lemma B.2 ((25) Lemma 2.1). Let h X + R be some convexfunction (not necessarily differen- tiable). Then for any x E E C IRd and 8 > O we have
d
V (B) 5v)] 8
-Eu-U()) (h(x + ōu)) u)
(50)
12


Reviews:
[{"review_id": "nFNDuwI3E0", "reviewer": "Reviewer_g73L", "summary": "The paper proposes a universally constrained online learning framework for ad procurement in non-stationary autobidding worlds. The paper makes contributions to the field by addressing the challenges of ad procurement in non-stationary autobidding worlds and developing a unified algorithm that can perform well in autobidding world while satisfying long-term constraints.\n", "questions": "What are the challenges with applying the algorithm to obtain experimental results?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper addresses the challenges of ad procurement in non-stationary autobidding worlds and develops a unified algorithm that can perform well in autobidding world while satisfying long-term constraints.\n- The paper makes contributions to the field by developing an algorithm that yields good performance guarantees under different procedures.\n- The paper is well-written and clearly presents the problem and the proposed solution.", "weaknesses": "- The paper does not have experiments to validate the theoretical findings.\n- The paper could provide more insights into the practical implications of the proposed algorithm and how it can be applied in real-world settings.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive and valuable feedback. \n\nRegarding Weakness 1 and Question 1 on experimental results: we agree that having experimental results would strengthen our paper’s key messages as well as contributions. We did not include experimental results in our paper due to space constraints, and we will add relevant discussions/results in our revision of this paper. We would like to point out that there are no major challenges in applying our algorithm to real or synthetic data to obtain experimental results, as the proposed algorithm is quite clean and easy to implement in practice. We would also like to mention that the main contributions of the paper lies in the modeling aspect (for autobidding under realistic non-stationary and limited information environments) as well as theoretical results.\n\nRegarding Weakness 2 on practical implications of our proposed algorithm: Online advertisers nowadays face a large array of advertising platforms such as search engines, social media platforms, web publisher display etc. Determining how to set advertising goals in each of these platforms (e.g. allocating total budget across different campaigns on a platform or setting target cost-per-click etc), especially in non-stationary environments due to changing user behavior, competition etc., becomes essential for online advertisers to optimize ad conversion outcomes. Our proposed algorithm presents a rigorous methodology that helps online advertisers set advertising goals in these ad platforms under non-stationary markets. As described above, we will also include experimental results in our revision to showcase the practicality of our proposed methodology for real-world settings.\n"}, {"review_id": "51IFZndtlf", "reviewer": "Reviewer_hupT", "summary": "This paper concerns a two-stage autobidding scenario, such as an advertising platform environment.  Each advertiser wants to maximize value received (e.g., clicks) subject to long-run constraints (e.g., budget or ROI).  As actions, the advertiser can specify certain instructions to an autobidding agent (e.g., a spend rate or ROAS target) and observe the results.  The advertiser observes bandit feedback, and wishes to tune their choice of actions/instructions to solve their long-run optimization problem.\n\nBecause the autobidders themselves are learning over time and potentially facing changing market conditions, the evolution of payoffs observed by the advertiser may not be stationary.  The paper considers a variety of different payoff evolution models, including partial adversarial corruption, periodic, and ergodic payoffs.  \n\nThe main result is a universal learning method for the advertiser that achieves good regret for each of these payoff evolution models.  The idea is to combine dual descent methods for constraints with a modified online convex optimization approach to adequately explore lever decisions given the dual variables.  This combination leads to vanishing regret in each of the settings considered.  The resulting regret rates are then compared with known lower bounds for each of these settings (many of which apply in relaxed settings, such a full feedback rather than bandit feedback).", "questions": "Are there natural conditions under which a scenario with mutually competing autobidders would fall into one of the analyzed worlds?", "limitations": "I feel that the paper is sufficiently up-front about its limitations, and the authors do an adequate job of describing what their paper does and does not do.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "I like this paper.  The modeling framework that separates true \"long-run\" objectives from \"short-term\" directive levers is extremely natural and, as far as I'm aware, novel.  It also tracks my understanding of how autobidding works in practice: advertisers need not keep their specified constraints (to the autobidder) fixed over time, but can manipulate them online as tunable knobs.  \n\nThe assumption of a safe action is likewise very reasonable, and the proposed algorithm makes use of it to good effect.  \n\nThe proposed algorithm combines multiple well-established ideas from the online optimization literature in a reasonable way.  The fact that this comes together into a unifying framework is an appealing feature, as is the need for only bandit feedback.  The regret rate suffers somewhat compared to known bounds, but not by too much --- what amounts to a rate of T^{3/4} for each of the non-fully-adversarial settings is quite good, while leaving room for future work to improve.  Getting these regret rates down to sqrt{T} (or showing this isn't possible) is a nice open challenge.\n", "weaknesses": "The biggest question for me is how \"real\" autobidding (e.g., competitive uniform bidding) falls into this scenario.  For instance: even in a stationary environment in terms of competitors, the relationship between levers and outcomes is not necessarily stationary for advertiser i because the underlying autobidder is learning over time how best to satisfy the directive communicated by a given lever setting.  So my understanding is that this scenario would fall under the ergodic setting.  But what if the competitors are not stationary, but are learning as well?  Can these theoretical frameworks be linked back to the motivating setting of autobidders that simultaneously learn?  Either way, it would be nice to have a more thorough discussion of this in the body of the paper.\n\nAnother potential weakness is that the technical contributions largely synthesizes known approaches, so the marginal technical contribution is not extremely high.  I therefore view the conceptual and modeling contributions as the main selling points for the submission.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive and positive feedback!\n\nRegarding Weakness 1 and Question 1: The game-theoretic interactions between actions among multiple agents is indeed an interesting yet challenging future direction. For this work, one can view the various environments of interest (namely stochastic, adversarial, periodic, Markovian, and corrupted) as “aggregate market-dynamics” driven by competitor algorithms. We believe that this is a reasonable aggregate view of real-world algorithmic bidding in online advertising markets: for example, the environment is mostly stationary (or i.i.d) when looking at a short time period, such as one hour (see [R1] for practical evidence); for longer time horizons, aggregate algorithmic interactions may exhibit periodicity (such as more aggressive and active bidding during non-work hours) see [R2] for practical evidence; competing algorithms may occasionally be driven by adversarial behavior due to the competition [R3] etc.. The beauty of the proposed algorithm is that the algorithm can achieve good performance without the need of knowing this “aggregate view\" on competitor algorithmic behaviors. We would also like to point out that most of the previous theoretical works on online learning in advertising focus on either stochastic i.i.d. model, which is too optimistic in practice, or adversarial model, which is too pessimistic. Nevertheless, we completely agree that our paper can benefit from including discussions on relevant multi-agent learning topics, and we will also support such discussions with practical evidence from the literature.\n\n[R1] Feldman, Jon, et al. \"Online stochastic packing applied to display ad allocation.\"\n\n[R2] Yuan, Shuai, Jun Wang, and Xiaoxue Zhao. \"Real-time bidding for online advertising: measurement and analysis.\" \n\n[R3] Golrezaei, Negin, et al. \"Learning product rankings robust to fake users.\"\n\nRegarding Weakness 2: We would like to respectfully respond to the reviewer’s comment “the technical contributions largely synthesizes known approaches, so the marginal technical contribution is not extremely high”. The most relevant previous theoretical work on this topic may be [R4], which studies the best-of-many-world setting for online allocation problems. The key difference is that the reward function and the constraint functions are known in [R4] before making the decision (i.e. [R4] studies the full information setting), while in this paper we study the bandit setting where the reward and constraint functions are unknown before a decision is made. This makes the analysis much more difficult than that of [R4], as we need to carefully handle unknown per-round constraint violation (before making decisions) to satisfy long-term constraints, while not allowing regret to decay too much. Our proposed algorithm requires much more complex design and analyses than that of [R4], which simply employs a mirror descent approach. We would also like to point out that although our proposed algorithm is inspired by well-established approaches, it is interpretable and implementable and thus can be easily adopted in practical setups. We also believe that our proposed algorithm can inspire future works to develop more complex algorithms and improve performance guarantees (to match with lower bounds for the full-information setting). \n\nFinally, as the reviewer describes, another key contribution of the paper is the modeling aspect, as to the best of our knowledge this is the first work that studies a universal algorithm that yields reasonable performance in various non-stationary autobidding setups under bandit feedback. \n\n[R4] Balseiro, Santiago R., Haihao Lu, and Vahab Mirrokni. \"The best of many worlds: Dual mirror descent for online allocation problems.\" \n"}, {"review_id": "zoLLgkBwsX", "reviewer": "Reviewer_EvVQ", "summary": "This work studies the problem of dynamic online allocation under constraints with bandit feedback, and derives a generic algorithm applicable to various input settings (stochastic, adversarial, $\\delta$-corrupted, ergodic, periodic). It recovers regret rates close to those of the lower bounds in each of these settings. The algorithm uses a dual gradient descent over $\\lambda_t$ to decouple the decisions over time by considering the lagrangian, a gradient ascent for the optimal choice of $x_t$ (that also uses the technique from Flaxman et al (2004) to handle the bandit feedback), and finally a multiplicative weight update to adapt the learning rates used to the correct input setting. ", "questions": "- Do the $T^{2/3}$ rates come from the use of the method to handle bandit feedback? How would a generic gradient feedback affect the rates, would we be able to derive tight rates with respect to the lower bounds presented? I think it might have been better to first present the results with gradient feedback, and mention in the appendix that bandit feedback can be handled by a standard technique. This would allow the main part of the paper to focus on the new contributions. \n- Could you give some intuition on what this optimal dynamic sequence looks like in the various settings? For instance, if my understanding is correct, the optimal dynamic sequence in the stochastic setting is simply a unique point (because the data is i.i.d). Could the optimal sequence for the ergodic setting be a function of $\\kappa$ close to the unique optimal point with respect to the stationary measure? \n- How much does the meta algorithm degrade the regret? (compared to assuming that we know the input setting)\n- l 657 Why is it $... +D \\dots$ and not $...+(t-1)D\\dots $ ?\n \nComments/Typos:\n- L304 and l324 stochstic ->  stochastic\n- I find the notation of $\\lambda \\in [0,F e/ \\beta]$ confusing, is it $\\lambda \\in [0,F/\\beta]^K$?\n- L553 ‘which states $\\max_{x \\in \\mathcal{X}} f(x)$: is a word missing?\n- L608 I am not sure to understand this statement, could you include a reference for this result? Is the sup taken over $(g_{\\tau},f_{\\tau})$ - over $[t]$ or $[T]$? \n- I think it would be nice to cite the paper of Mannor et al (Online learning with sample path constraints), which deals with very similar problem and started the works on online convex optimization with varying constraints\n- Equation below l643: $v$ -> $\\Vert v \\Vert$, and the last equality should be an inequality (as it is in the ball, not the sphere)\n- Equation below l655 I think some of the gradients are missing $\\Vert \\nabla_t \\Vert^2$ and $x^i_{t+}$ ->  $\\tilde{x}^{i}_{t}$. Why are some of the gradients bolded and not the others? \n- Same thing for the gradients below l657, in addition I am not sure where $P(y_1:T)$ is defined.\n- L 664 ‘$a=$ and $b=$’ it is unfinished \n\nI have not read through all the proofs, but I would recommend to read it again to look for additional typos\n", "limitations": "Yes the authors address some limitations in the section $5$ of the paper regarding the lower bounds. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The algorithm generalizes to multiple input settings and general constraints the problems related to Bandits with knapsack constraints, and of online learning with constraints. (to be clear this is an important strength of this paper!)\n- The problem is well motivated through the consideration of running multiple ad campaigns\n", "weaknesses": "- The assumption that there exists some safe action of level $\\beta$ do simplify the problem of constraint satisfaction by guaranteeing to be able to satisfy the constraint at the end\n- Some of the upper bounds (stochastic, periodic, corrupted) are a bit loose compared to their respective lower bounds\n- The writing can be improved, in particular in the proofs which are lacking discussion about their main ideas and intuition. As an example page $8$ of the appendices is almost only a sequence of inequality and is hard to follow. For instance the inequalities could be cut in multiple parts, and some comments could be added to better explain the goal of the proof. There are also some typos.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive and valuable feedback. \n\nRegarding Weakness 1 on the safe action: We would like to point out that the existence of a “safe action” is quite common in online advertising. Take for example the simple case where an advertiser only has a long-term budget constraint, and the only lever used is the budget set each round (i.e. a single decision variable that represents the maximum spend in each round/ad campaign). In this case, the safe action is to simply set the per-round budget to be 0, so the advertiser would always acquire some positive constraint balance (i.e. limit spend to ensure expenditure does not exceed long-term budget after $T$ rounds). Another example is the simple case where the advertiser only has a long-term ROI constraint which states total reward exceeds total spend after $T$ rounds, and again assume the single decision variable of interest is per-round budget. Then, by setting a small per-round budget, ad platforms tend to procure the most “lucrative ads” on behalf of the advertiser that have a large value-to-cost ratio, which generates a positive ROI-balance per round that helps satisfy the long-term ROI constraint after $T$ rounds. Similar assumptions are made in many related works see; e.g. [R1,R2]. Without the safe action, there is no guarantee that the problem is feasible and performance guarantees may be intractable.\n\n[R1] Deng, Yuan, et al. \"Multi-channel autobidding with budget and roi constraints.\"\n\n[R2] Feng, Zhe, Swati Padmanabhan, and Di Wang. \"Online Bidding Algorithms for Return-on-Spend Constrained Advertisers.\" \n\nRegarding Weakness 2 on loose upper bounds: We would like to point out that our setting is related to the more general problem of bandit online constrained optimization in continuous high-dimensions with single-point feedback (i.e. the decision maker can only make a decision once per round and observe a single feedback). To the best of our knowledge, there is no existing algorithm that achieves optimal bounds even in purely stochastic or adversarial environments (see discussions in [R3]). Our paper considers an even more complex setup than these “pure environments” as we demand a single algorithm that yields tractable performance across various non-stationary environments. Indeed, many of the lower bound stated in the paper are for a more restrictive class of problems under full-information feedback (i.e., the reward and constraint functions are known before making any decision, while we study bandit feedback). To the best of our knowledge, lower bounds for bandit feedback problems are unknown, so we present those for full-information feedback. The gap may come from the intrinsic difference between these two classes of problems. Nevertheless, we believe that this work has the potential to inspire future research to develop more sophisticated algorithms and close the upper-lower bound gap. \n \n[R3] Zhao, Peng, et al. \"Bandit convex optimization in non-stationary environments.\"\n\nRegarding Weakness 3: we thank the reviewer for pointing this out and agree that the exposition of the paper can be improved. We will revise our paper and include more discussions accordingly in both the main body and the technical results/proofs in the appendix.\n\nResponse to Question 1: The presented non-optimal rates are indeed due to the need to handle bandit feedback. In the full-information setup where the decision maker can first observe the reward and constraints in each period before making a decision,  it has been shown in [R4] that a simple mirror descent approach can achieve optimal rates. Nevertheless, we point out that the bandit setup considered in this paper is much more complex and requires our proposed techniques to effectively balance regret minimization and constraint satisfaction in a limited information bandit environment. See the response for weakness 2 for more details.\n\n[R4] Balseiro, Santiago R., Haihao Lu, and Vahab Mirrokni. \"The best of many worlds: Dual mirror descent for online allocation problems.\" \n\nResponse to Question 2: The reviewer’s insight is correct that in the stochastic setting the optimal dual variable sequence is a fixed point, and the optimal primal variables of course would depend on the observation. Nevertheless, to the best of our knowledge, it is not clear for the other settings what structural properties the optimal sequences possess, and the optimal sequence may vary significantly depending on the specific (unknown) underlying reward distribution sequences. Take an extremely simplistic example in the $\\delta$-corrupted environment, where there is only a single round at which the reward distribution is corrupted and the advertiser only has a long-term budget constraint. If the corrupted expected reward is very large (e.g. in the order of $T$), then she should spend most of her budget during that single round in the optimal decision sequence, and spend nearly nothing in other rounds; on the other hand, if the reward in the corrupted round is 0, then the setting reduces to the stochastic setting, and the optimal action in each round should be some fixed point. Nevertheless, we believe we can produce experimental simulations to characterize the structure of optimal sequences in simple settings, and we would include relevant discussions/results in the revised version of our paper.\n\nResponse to Question 3: \nWe will include a summary of the best existing upper bounds for each non-stationary environment, respectively, in the paper in our revision. \n\nResponse to Question 4: we apologize for the typo in line 657. In the second equality (within the large parentheses), we should have $y_{t}^\\top\\tilde{x}_{t+1}^i$ (which is independent of $\\tau$ that we sum over). This term can then be bounded by $D$ (as opposed to $(t-1)D$). \n\nFinally, we thank the reviewer for the comments and for pointing out typos. We will carefully review the paper and make corrections accordingly.\n"}, {"review_id": "OmnuF3mHhS", "reviewer": "Reviewer_bowu", "summary": "This work studies an advertiser's online high-dimensional lever decision problem with long-tern constraints under limited bandit feedback for different input models. The authors' main contributions include: (1) model formulation; (2) proposing an algorithm universally applicable to input models; (3) theoretical regret analysis. \n\nThere is an advertiser that repeatedly interact with an ad platform during a time horizon $T$, aiming to maximize her total conversions subject to multiple constraints. At each time $t$, the advertiser need to make a multi-dimensional lever decision and observed her realized conversion as well as her multi-dimensional realized cost. The authors propose an algorithm with universally good performance and provide regret lower bounds of this problem with respect to different input procedures.", "questions": "1. Line 13, multi-dimension -> multi-dimensional. \n\n2. Line 14. What does \"uncertain\" mean throughout this paper? The bidder should known their constraints at the beginning, e.g. known budget.\n\n3. Line 168, a redundant \"of\". \n\n4. Line 219, realzied -> realized. \n\n5. Line 283, violates constraints violation?\n\n6. Line 664, missing values for $a$ and $b$.\n\n7. Line 288, what does $\\alpha$ do in algorithm 1? To my understanding, it makes sure that the opinion of an expert lies in the interior of the domain. However, the value of $\\alpha$ is not specified. It seems fatal if $\\alpha$ is close to 1.\n\n8. Line 299, the number of experts $N$ seems to be negative when $T$ goes to infinity.\n\n9. Line 301, N experts or (N+1) experts?\n\n10. Line 539, the first term in the RHS of equation (15) is not bounded after timing $T$.\n\n11. Line 542, $\\tau$ -> $t$. The authors should check $t\\in [T]$ and $\\tau\\in [t]$ throughout the appendix. the order of $\\beta$ also seems wrong in equation (16).\n\n12. Line 626, observe that the sum operator is over $t\\in [\\tau_A]$ so the optimal $x$ does not vary to $t$. Does it implies all $y_t$ are the same?\n\n13. Line 629, arer -> are.\n\n14. Line 636, according to the theorem 4.2 one has $\\gamma_{0} = K^{-1/6} (1+DT)^{1/2} T^{-3/4}$ and $\\gamma_{N} = 1$. Then $\\gamma_{0}$ is not the largest element in the stepsize set since it goes to $0$.\n\nBe willing to raise my rating if it is confirmed there is no technical flaw.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The proposed algorithm is oblivious to input models such that it can achieve high performance without knowing which setting the decision-maker is in.\n\n2. It is novel to adopt the random perturbation approach and the expert-based decision-making in online autobidding. The regret analysis requires non-trivial insights and techniques. Particularly, the proof of lemma 4.6 that bounds the primal ascent regret stands out from standard primal-dual frameworks.\n\n3. The organization of this paper is great.", "weaknesses": "1. The idea of solving a problem in many worlds is not new. In addition to commonly studied stochastic and adversarial input models, [1] also considers $\\delta$-corrupted, periodic, ergodic input models. Actually, the proofs for the latter three cases are analogous to the stochastic case as they still assume stationary distributions to some extent.\n\n[1] Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. The best of many worlds: Dual mirror descent for online allocation problems.\n\n2. Some mistakes are spotted. Some statements are not clear enough. See the questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive and valuable feedback.\n\nResponse to weakness: The key difference between our paper and [1] is that the reward function and the constraint functions are known in [1] before making the decision (i.e. [1] studies the full information setting), while in this paper we study the bandit setting where the reward and constraint functions are unknown before a decision is made. This makes the analysis much more difficult than that of [1], as we need to carefully handle unknown per-round constraint violation (before making decisions) to satisfy long-term constraints, while not allowing regret to decay too much. Our proposed algorithm requires much more complex design and analyses than that of [1], which simply employs a mirror descent approach. We would also like to point out that although our proposed algorithm is inspired by well-established approaches, it is interpretable and implementable and thus can be easily adopted in practical setups. We also believe that our proposed algorithm can inspire future works to develop more complex algorithms and improve performance guarantees (to match with lower bounds for the full-information setting). \n\nResponse to questions: We apologize for the typos in the paper, and we will carefully review the paper to ensure accuracy of our statements and results. In the following we will address major technical questions raised by the reviewer, namely questions 2, 6, 7, 8, 9, 10, 11, 12, 14:\n\n(2). “Uncertain” refers to the fact that the amount of per-round constraint violation each period is unknown. Take for example a single long-term budget constraint which says total spend cannot exceed a certain amount. In our bandit setting, the incurred cost for making a decision is only observed after the decision is made, and hence there are two sources of uncertainty: (a) The decision maker does not know how much budget is consumed before making any decision; (b) The decision maker may not necessarily satisfy her long-term budget constraint if she does not act intelligently. \n\n(6). In line 664, we utilize Eq. (45) and choose $a = -\\frac{d}{\\rho}\\left(\\bar{F}+ K \\frac{\\bar{F}}{\\beta} \\bar{G}\\right)\\cdot (1-\\alpha) D$ and $b = \\frac{d}{\\rho}\\left(\\bar{F}+ K  \\frac{\\bar{F}}{\\beta}  \\bar{G}\\right)\\cdot (1-\\alpha) D$, while the original term of $\\frac{\\epsilon^2}{8}$ will be replaced by $\\frac{\\epsilon^2(b-a)^2}{8}$. We remark that the rest of the proof follows with this small correction.\n\n(7). You are absolutely correct that $\\alpha$ ensures the opinion of an expert lies in the interior of the domain.  In the input line of Algorithm 1 on page 7, we do require choosing $\\alpha \\in (0,1)$.  In particular, in the analysis (specifically for Lemma 4.6), we set $\\alpha$ to be a parameter with the same order of $\\rho$; i.e., $\\alpha = K^{1/3}T^{-1/4}$.  We will add the requirements on $\\alpha$ explicitly in the statement of Theorem 4.2.\n\n(8). Thank you for catching this typo!  Instead of the previous definition of $N$, we should set $N = \\max (1, \\lceil  -\\log_2 (K^{-\\frac{1}{6}}(1+D T)^{\\frac{1}{2}}T^{-\\frac{3}{4}}) \\rceil ) = O(\\log(T))$, which is always positive.\n\n(9). Thank you for pointing this out.  We should have $N+1$ experts.\n\n(10).  We take $\\alpha  = K^{1/3}T^{-1/4}$ as mentioned in the answer to Question 7. This ensures the regret due to this term after $T$ rounds is $O(T^{3/4})$, which matches our final regret bound.  We will emphasize this explicitly in the revised version of our paper.\n\n(11). Thank you for carefully reading our paper and catching this typo.  We will fix all these typos as the reviewer mentioned, including $(\\tau, t)$ and the order of $\\beta$ in Equation (16) (which should be squared). Note that this does not impact the final regret bound as $\\beta$ is in the order of $1/\\log(T)$.\n\n(12). Thank you for your comment.  Yes, all $y_t$ are the same in the stochastic setting, given the nature of i.i.d. randomness. We remark that to the best of our knowledge, it is not clear for the other settings what structural properties the $y_t$ sequences possess, as they may vary significantly depending on the specific (unknown) underlying reward distribution sequences. Mathematically this is one aspect that makes the problem we are tackling extremely challenging. Please see our response to Question 2 from reviewer EvVQ for more detailed discussions.\n\n(14). We believe this issue will be fixed after changing the value of $N$ as we suggested in the answer of Question 8. The primal ascent step sizes will then be decreasing as $i$ increases.\n\nWe hope the above response addresses the reviewer’s concerns about technical details, and we would be more than happy to answer other questions should they arise. Given our above responses to technical concerns, we would greatly appreciate it if the reviewer can re-assess the contributions of this submission as well as the corresponding rating. Again, we sincerely thank the reviewer for the comments, suggestions and questions.\n"}]

Author rebuttal:

Meta-review: Overall, reviewers are all positive about the submission. In particular, the reviewers think the paper has an interesting modeling and conceptual to the line of research in auto-bidding. 

On the other hand, reviewers do mention some weaknesses, for example (1) the paper does not have empirical studies, and it's not clear how well the theoretical findings fit practical applications (2) technical contributions might be marginal. These prevent the paper to get a higher rating. Reviewers also listed some typos and authors should try to fix them before publication.
Decision: Accept (poster)