No-Regret Online Autobidding Algorithms in First-price Auctions
Authors: Yilin LI
Yuan Deng
Wei Tang
Hanrui Zhang
Venue: NeurIPS 2025 poster ()
Keywords: Autobidding
No-regret Autobidding algorithm
Repeated auctions
ROI constraint
Primary area: theory

Abstract: Automated bidding to optimize online advertising with various constraints, e.g. ROI constraints and budget constraints, is widely adopted by advertisers. A key challenge lies in designing algorithms for non-truthful mechanisms with ROI constraints. While prior work has addressed truthful auctions or non-truthful auctions with weaker benchmarks, this paper provides a significant improvement: We develop online bidding algorithms for repeated first-price auctions with ROI constraints, benchmarking against the optimal randomized strategy in hindsight. In the full feedback setting, where the maximum competing bid is observed, our algorithm achieves a near-optimal $\tilde O(\sqrt{T})$ regret bound, and in the bandit feedback setting (where the bidder only observes whether the bidder wins each auction), our algorithm attains $\tilde O(T^{3/4})$ regret bound.

No- No-Regret Online Autobidding Algorithms in First-price Auctions*
Yilin Li Chinese University of Hong Kong yl1i250cse. cuhk. edu hk
Yuan Deng Google Research dengyuanOgoogle, com
Wei Tang
Hanrui Zhang
Chinese University of Hong Kong weitangScuhk.cd edu. hk
Chinese University of Hong Kong hanrui@cse, cuhk, edu. hk
Abstract
Automated bidding to optimize online advertising with various constraints, e.g. ROI constraints and budget constraints, is widely adopted by advertisers. A key challenge lies in designing algorithms for non-truthful mechanisms with ROI constraints. While prior work has addressed truthful auctions or non- non-truthful auctions with weaker benchmarks, this paper provides significant improvement: We develop online bidding algorithms for repeated first-price auctions with ROI constraints, benchmarking against the optimal randomized strategy in hindsight. In the full feedback setting, where the maximum competing bid is observed, our algorithm achieves near-optimal Ö( ((VT)) regret bound, and in the bandit feedback setting (where the bidder only observes whether the bidder wins each auction), our algorithm attains ((73/4) regret bound.
Introduction
Autobidding has become the predominant paradigm in online advertising. The idea is that advertisers compete for ad opportunities through repeated auctions, where each advertiser employs automated bidding algorithm (i.e., an autobidder) to bid on behalf the advertiser. Autobidders are essentially online constrained optimizers: As auctions happen over time, an autobidder maximizes the fly certain objective quantity, e.g., clicks or conversions, subject to constraints, e.g., the total spending cannot exceed predetermined budget, return-on on-investment, or ROI ratio) must be at least given target ratio. Normally, advertisers are free customize these components of autobidders better serve their own goals.
the ratio between the return and the investment (i.e., the
Over years, advertisers seem to have converged to the following common practice: An overwhelming autobidders that behave like ROI-constrained value maximizers. This
majority of advertisers highlights the importance of designing good online bidding algorithms in this very setting. The problem, roughly speaking, is the following: Initially, auction mechanism (e.g., first-price second-price) is chosen externally by the advertising platform, which is used in all subsequent auctions. At each step, auction happens, and the algorithm observes the "value" of winning in this auction. Then, the algorithm must immediately submit a bid based on historical observations and the value, after which the algorithm observes the outcome of the auction, i.e., whether it has won and possibly also the highest bid by other advertisers, In the long run, the algorithm must (approximately) maximize the total value obtained over all auctions, subject to the constraint that the overall ROI ratio is at least predetermined target ratio. The key challenge here is that at each step, the algorithm
'The full version of the paper available at htttss://arrtiiii wwtpe/ii.vrgg/bb////eeaeoeea 16869
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

must decide the bid without knowing the future, or even the competing bid in the current auction. Nonetheless, must ensure that its decisions are almost optimal from hindsight (i.e., it has no regret), and the ROI constraint is approximately satisfied over the entire horizon.
Indeed, considerable effort has been invested into this task. Here, we refrain from prolonged discussion (see Section [.I for further related work) and focus on the most related results. Feng al. [21) study the problem when the auction mechanism is truthful, and give an almost optimal no-regret online bidding algorithm. Despite its undoubted importance, one severe limitation of their result is that it does not apply to some of the most common auction mechanisms in reality, including first-price auctions and generalized second-pris -price auctions - for these mechanisms are not truthful. To address this issue, Aggarwal et al. [3] design alternative no-regret bidding algorithms that work for nontruthful auctions. However, their algorithms only have no regret against weaker benchmark, i.e., the optimal Lipschitz-coninnee
bidding strategy from hindsight, which in general can be much worse than the unconditionally optimal bidding strategy. This leaves the following question open: Is possible to design a no-regret online bidding algorithm against the unconditionally optimal strategy for nontruthful auction mechanisms?
Our results. We provide an affirmative answer to the above question. For concreteness, we derive our results for first-price auctions (which is the most representative nontruthful auction mechanism). We consider two natural feedback models commonly studied in the literature:
Full feedback: the algorithm learns the auction outcome and the competing bid, after each auction; Bandit (or one-bit) feedback: the algorithm learns only the outcome of the auction and nothing else after each auction.
The latter setting is more challenging than the former, since the algorithm obtains less information.
In the full feedback setting, a folklore lower bound of Q (T)) is essentially inherited from the most fundamental setting of stochastic bandits Slivkins et al. 34 prove the a lower bound regret
2( ((VKT), where K is the number of arms and T time horizon stochastic bandits We present an online bidding algorithm that achieves the optimal (up to polylog factors) regret bound of (VVT) against the unconditional, possibly randomized, optimal strategy in hindsight, where T is the time horizon. This generalizes the result by Feng et al. [21] and strengthens the one by Aggarwal et al. 3 in the same setting. In the bandit feedback setting, we present an algorithm that achieves regret bound of Ö(T3/1) against the unconditionally optimal strategy, which strengthens the result by Aggarwal et al. 3 in the same setting. + These results paint considerably clearer picture of online bidding algorithms for ROI-constrained value maximizers.
Technique overview. The key technical challenge in designing online autobidding algorithms, which has also been observed by Aggarwal et al. (3, is that unconditionally optimal bidding strategies appear to have rich structures. This tends to baffle existing techniques, which normally require the class of strategies optimized over to be "simple" and / or "structured" in some way. Below we first briefly review how prior work deals with this challenge.
Feng et al. [21] restrict their attention to truthful auctions, in which optimal bidding strategies admit clean characterization: Without loss of generality, they only need to consider "uniform bid scaling", i... bidding strategies defined by a single multiplier 6, such that the strategy places a bid of 0 - when the value of winning is v. Restricted to such bidding strategies, one essentially only needs to optimize the multiplier 6, which allows Feng et al. [1] to essentially reduce their problem (in a nontrivial way) to one that can be handled within the powerful mirror descent framework. Aggarwal et al. 3 take an approach that is in sense more general: They consider bidding strategies that are Lipschitz-continuuus, which subsume uniform bid scaling as a subclass. By doing so, Aggarwal et al. 3 manage to further incorporate technical insights from the Lipschitz bandits literature, which help establish nontrivial regret bounds for nontruthful auctions.
We take an approach that is in spirit similar to 21 We first make a more general structural observation, that even in nontruthful auctions, optimal (and possibly randomized) bidding strategies
A detailed discussion about the lower bound is provided in the full version of the paper 16
II the bandit feedback setting, Aggarwal et al. B establish a lower bound of 2/32 closing the gap between this lower bound and our upper bound remains an important open direction for future work.

---

are essentially parametrized by a single number, which roughly corresponds to the marginal ROI of the bidding strategy. We present an algorithmically compatible characterization of this class of strategies (see Section B). which allows us to (1) generalize the mirror-descent-basee algorithm used in [21 to nontruthful auctions and (2) without loss of generality, focus on deterministic bidding strategies. provided one condition: The algorithm needs to know the distribution of competing bids This condition is crucial, since the structure of optimal bidding strategies necessarily depends on the distribution of competing bids, and without knowing the former, one simply cannot guarantee the conditions for the mirror-descent primitive to produce the desired regret bound @ In our setting, of course the algorithm cannot know this distribution beforehand. Below we discuss how this requirement can be removed.
We first show that the requirement can be relaxed without hurting the regret too much. In particular, desceed--eteteeeeeeeeee algorithm with slightly inaccurate
we show that if we run the generalized distribution of competing bids given as input, then its per-round regret can only degrade to the extent that the input distribution is inaccurate. With that as a primitive, we construct an algorithm that "bootstraps" itself without any prior knowledge about the environment in the full feedback setting (see Section 4 The algorithm "restarts" itself periodically as it gathers more information about the distribution of competing bids. Upon each restart, it runs a fresh instance of the mirror-descent-basee primitive with the latest estimated distribution as its input, which allows it to gradually lower the per-round regret over time as the estimation becomes more accurate. By properly pacing the restarts, we manage to beat the O(T2/3) bound via simple exploration-exploiaa and achieve an almost optimal bound of Ö(VT)
In the bandit feedback setting, the above strategy does not work any more, and we have to fall back to simple exploration-exploitttiii
In our setting, even this conceptually simple high-level strategy requires nontrivial technical ingredients to implement: In fact, here we need a slightly stronger property of the primitive, because can longer guarantee uniform estimation error of the distribution of competing bids. We show that the property holds for a slightly adapted version of the primitive used in the full feedback setting. With that as building block, by optimizing the granularity of discretization and the tradeoff between exploration and exploitation, we manage to establish a regret bound of Ō(T3/4) (see Section 5). which matches the guarantee established by Aggarwal benchmark. Notably, the ideal O( bound is
et al. 3 against the weaker Lipschitz-continee impossible in this setting due to a lower bound of 22(22/3) by Aggarwal et al. 3 We leave closing this regret gap as an important furture direction.
1.1 Related Work
Most closely related to our work is the line of research on online bidding algorithms in repeated auctions, with ROI-constrained salue-maximizing bidders. In the paradigm with ROI constrained value maximizing bidders, Feng et al. [21] propose an algorithm based on the primal-dual framework proposed by Balseiro al. (6) which achieves nearly optimal Ö(VT) regret bound for truthful auctions. Castiglioni et al. [4] propose an algorithm that achieves no regret in repeated, possibly nontruthful, auctions, under the assumption that the spaces of values and bids are both finite. Aggarwal et al. [3] design an algorithm which works with nontruthful auctions and continuous value / bid space, and achieves no regret against any Lipschitz-continnne
bidding strategy. Our work generalize / strengthen all these results by achieving the nearly optimal Ö(VT) regret against the unconditionally optimal bidding strategy without further assumptions []] Also conceptually related is the work by Vijayan al. [36), who consider "harder" setting where the algorithm does not even observe the value of winning, and instead, must learn to estimate this value on the fly. Their result is orthogonal to ours, in particular because they also assume a finite space of bids.
Beyond autobidding, there is an extremely rich body of research on online bidding algorithms in repeated auctions. To name a few results: Balseiro et al. [6] propose a primal-dual framework and apply their framework to repeated second-price auctions with budget constraints and derive no-regret bidding algorithms. Wang et al. (37 study the same problem in repeated first-price auctions.
è NNte that the problem remains nontrivial, because the algorithm does not know the distribution of its value. "This is not issue in 21 since the structure they need is independent of the distribution of competing bids.
'The Ö( ((TT) bound applies to the full feedback setting. In the bandit feedback setting, we match the bound by Aggarwal et al. (3] against weaker benchmark, thereby also strengthening their result.
3

---

Cesa-Bianchi et al. [15] study online bidding algorithms in first- first-price auctions without budget or ROI constraints, and pin down the optimal regret in number of settings. Kumar et [28] present no-regret bidding algorithms that are strategically robust. Susan et al. [35] design no-regret bidding algorithms for multi-platform settings, where the bidding algorithm repeatedly participates in multiple parallel auctions. Berriaud et al. [11] discuss the repeated auction problem in artificial currency mechanisms with payment redistributed uniformly in each round. More generally, there is a long line of research no-regret algorithms and dynamics for allocation problems under constraints, e.g..
[33] 38). We refrain from an extensive discussion since these results concern fairly different problems from ours, both conceptually and technically.
5 2 12 13
P2
[ 24 25 26 27
B1
Our results are also conceptually related to the growing literature on the design and analysis of auctions and marketplaces with autobidders. Prior research in this direction concerns various topics, including the efficiency of traditional auction mechanisms [2
29]. the design of (approximately)
optimal mechanisms [ g comprehensive exposition.
T0
19
30
32
etc. See the recent survey by Aggarwal et al. [1] for
2 Preliminaries
We consider an online bidding setting where a single bidder participates in single-item first-price auctions, repeated in T rounds. At each time step / [T', the learner realizes the value in the current round and then submits a bid b, based on the current value and the historical information up to now. The bidder wins the item if her submitted bid is not less than the (highest) competing bid d, (d, E [0, 1D in this round, and we denote by ze (b,, d,) = 1(b, 2 de the ex post allocation outcome of the current round. If the bidder wins the item, she pays price b, which equals to her submitted bid, otherwise she pays 0. Therefore, the payment function, denoted by p: (b,, de), is Pe(b,, de) by (bb 2 de)- We focus value-maximizing bidder where the bidder's 's utility at time t given by re de) = U2 Iz (b,, de).
Benchmark and regret definitions. We assume that the sequence of value vi is drawn indepen- dently and identically (i.i.d.) from unknown distribution, whose CDF is denoted H. The bidder's 's objective is to design an online bidding algorithm ALG that maximizes her total realized utility subject to Retur-On-IInestmeen (ROI) constraint Namely, her total utility must be least times her total payment: p Ene(T) Polbe, de) < >xE(T) Iz(b,, de) where p > 0 is the target
ROI ratio of the bidder.
max E
Σ Eem Vt x.(bb.
S.L. E Pile, de)
S E
E vt 2: (be,
where the expectation is over the possible randomness of the bid sequence {b,} and the randomness of the maximum competing bid [de)- W.l.o.g., we assume that p
We assume that the (maximum) competing bid d, at each round is i.i.d. realized from an unknown competing bid distribution F. In this context, the allocation and the bidder's 's payment in round t are determined by her submitted bid by: the allocation function xe (b,, de) = F(bb) and the payment function Pa (bb,,, d+) = b, F(b.).
We denote the bidder's value sequence by V (Dt) An online bidding algorithm takes input of the bidder's s historical information and the realized value at the current round, and outputs a (possibly randomized) bid. Given an online algorithm ALG, let Reward(ALG. (F, VT) (resp. Payment (F, VT)) denote the bidder's total expected utility (resp. total expected payment)
'For pedagogical reasons and for presentation simplicity, we focus exclusively on ROI constraints. Our results and analysis can be readily generalized to the setting with additional budget constraints, e.g., through techniques introduced 7 The extension to budget constraints is discussed in the full version of the paper [16]. in which we also present extensions to general non-tre non-truthful auctions. For p F 1, we rescale bidder's value to be p. and all our analysis/results can be carried over similarly.

---

given the value sequence V and competing bid distribution F::
Reward(ALG (F, (T) = BLGG)AAGG Enerr v F(bb)
Payment(ALG (F,, v²)) B(b.)-ALG Enetry be F(()))))))))
Thus, the ROI violation given by A(ALG | (F,V") = Payment(ALG | (F,V*)
Reward (F, V.).
Let OPT the corresponding optimal bidding algorithm hindsight for the program i.e. OPT has knowledge about the competing bid distribution F and the realized value sequence 7 Thus, an algorithm's 's regret relative to OPT under the input value sequence 1
Regret(ALG (F, V))) Reward (F,VT) Reward (F,V")).
We measure the performance of an algorithm ALG by its expected regret over the distributions F and H, defined follows:
Regret(ALG (F) = EVTwHT Regget (ALG) (F, V²))]
(I)
and expected ROI violation over the distribution and H:
(AAG (F) = EVTTHT [AALG (F, (F,V"))]
The feedback models. We now specify the feedback that the bidder receives at the end of each round. In this paper, consider the following two feedback models.
Full feedback: At the end of round f, the bidder observes the competing bid de- Bandit feedback: At the end of round f, the bidder only receives a binary signal win, {0, indicating whether she won the item or not, i.e., win; 1(de I be)-
Optimal Randomized Autobidding Strategy
In this section, we first present the bidder's optimal bidding strategy in hindsight, where the sequence of values VT is known. We then design an online bidding algorithm that has low regret and low ROI violation when competing bid distribution F is known, while value distribution H remains unknown.
We first define the following allocation-payment curve, which will be helpful for our analysis.
Definition 3.1 (Allocation payment curve G). Given a competing bid distribution F E A(0 1)), an intocatiio-payymenn curve G [0. [0, 1] is defined as: G(b F(b)) F(b) for all b E [0.
iilocation--pamment
The allocation allocation-payment curve G captures the relationship between the payment and the allocation (as well as the reward, which is proportional to the allocation when the value of winning is fixed) induced by any bid b.
payment
3.1 Characterizing Optimal Bidding Strategy
We start with the following example which shows the suboptimality of deterministic bidding strategies.
Example 3.2 (Suboptimality of deterministic strategy). Consider following competing bid distri- bution: Pr(d 0] Pr(d = 1|= 1/22. The bidder always has a value 1/2. Let T = 1, and the target ROI ratio = 1. One optimal deterministic bidding strategy would be to always submit a bid b = 0, which yields expected reward 1/4 and expected payment
note that restricted to deterministic bidding, there is no way to utilize this "slackness" " in the ROI constraind On the other hand, consider the following randomized bidding strategy: Pr(b 0) 2/2, Pr(b strategy yields an expected reward 1/3 and an expected payment 1/3. Both strategies satisfy the ROI constraint, while the randomized strategy gives a strictly higher reward.
1/2. This
Herr and in the rest of the paper, we assume ties are broken in favor of the bidding algorithm. This makes difference when the distribution of competing bids is continuous.
5

---

shows that to maximize the bidder's expected reward, it may be necessary to solve program over all randomized bidding strategies. This is (at least superficially) incompatible with the primal-dual framework that underlies all previous results on online autobidding, which presents new technical challenges. To address this issue, we present a constructive reduction that brings us back to the deterministic world, where we can cast the primal-dual framework more naturally. In particular, we show that given any input value sequence V and any competing bid distribution F, is always possible to construct another distribution Foonv that captures essentially the same tradeoff between reward and payment as F' induces, with one key difference: With F' replaced by Feonvv we can focus attention to deterministic bidding strategies without loss of generality.
Example 3.2
Theorem 3.1 (Optimal randomized bidding strategy). Fixing any input value sequence VT. For any competing bid distribution F, there exists distribution Feony E A((0, 1) such that: For any (randomized) strategy under V and F, there is deterministic strategy under V and Foonv inducing reward and payment that are both no worse, and vice versa.
To prove Theorem 3.1 we first characterize the relation of allocation F(b) (i.e. the probability of winning) and payment ((b). b by the allocation-pan payment curve G, where (F(b)- b, F(b) is point on the curve. Curve G' is parametrized by deterministie bid b. To incorporate randomized bidding, we observe that randomizing between two bids corresponds to taking a convex combination of two payment curve. As result, the best tradcoff' between allocation and payment under randomized bidding given by the concave envelope Geone of the allocation parmmmetnn-pymentt curve G. Therefore, if there is distribution Feone whose corresponding allocation-payment payment curve is Geone. the deterministic bidding strategies on Feons are equivalent randomized bidding strategies on F (i.e. for any randomized strategy on F, we can find a corresponding deterministic solution on Feonv and vice versa) ). We prove the existence Fomm by constructing from F.
points on the allocation- allocation-payment
With Theorem 3.1 we can simplify our algorithm design as follows: instead of designing an online bidding algorithm that has low regret against the optimal randomized bidding strategy under (F, VT), we can turn to designing an algorithm that has low regret against the optimal deterministic strategy under the corresponding (Feone, V²).
We conclude this subsection with proof sketch Theorem 3.1 where its full proof is quite technical, and thus, we defer it to the full version of the paper [16].
Proof of Theorem 3.7 Fixing any input value sequence VT, For any competing bid distribution F, consists of three main steps:
the proof of Theorem 3.1
Step 1 - Prove that the "concave envelope" Geone of aallocaiion-payeeet curve G attains the maximum expected reward: In our first step, show that given any fixed value v, any (possibly randomized) bidding strategy that leads to an expected payment of x has an expected reward at most e Geoay (I))
Step 2 Construct the distribution Fronv: In this step, we construct such distribution Feonv that corresponds to an illocation-payment curve Gronv, which is essentially the concave envelope of the allocation-pay iobocation-payment curve G induced by F.
Step 3 - Prove the reward equivalence: In this step. we show that any reasonable randomized bidding strategy under (F, VT) is equivalent to generating bid on the allocation paatoennt-paettttt curve Geonv, which corresponds to a deterministic bidding strategy under (Feouv, VT), and vice versa.
3.2 No-Regret Autobidding Algorithm for Known Competing Bid Distribution
In this subsection, we describe a no-regret online bidding algorithm (see Algorithm IT when the competing bid distribution F' is known to the bidder, while the value distribution H still remains unknown. This algorithm will serve as building block for our algorithm design when the both F and H are unknown to the bidder.
Technically. Geany might differ from the actual concave envelope of G. but this can happen only on the part of Geony that never matters for our purposes.

---

We first note that after introducing the Lagrangian multiplier À 2 0, we can reformulate the program
P as follows
max Σ 0z F(be) + minx20 Eneri (vr F(b.) - b, r(bi))
Following a similar dual-prime framework proposed by (6). we proceed by choosing bid by at round t maximize the objective Eqn. (2) using fixed Lagrangian multiplier X and then update X to A++1 use the observed feedback. Notice that given fixed X round t, the problem in Eqn. (2) is equivalent to
1 1++ de Xe
c.. -( F(b)
max
As we show Example 3.2,
the optimal bidding strategy may be randomized. Thus, using Theo- rem 3.1 instead of directly solving the problem Eqn. 33) we consider solving a bid b, that maximizes 1+ Ct Feonv (b) Feonv We then construct the equivalent randomized bidding strategy to be implemented in practice. We then update the dual variable X using the a generalized negative entropy in the mirror descent framework to adjust the penalty for the future rounds. We summarize the algorithm details in Algorithm]
by - be 10 [11 + Aτ) Feonv - de- Feonv (b)]
Algorithm No-regret bidding algorithm for known
Input: Time horizon T, competing bid distribution F, the value sequence V (revealed sequentially). Initialize: Initial dual variable λ = and the dual mirror descent step size a 1/VT
1: Let Feony be the distribution defined as in Theorem 3.1 (its construction is in the full version 16)..
2: for f- T do
3: Observe the value Ut..
4: Compute b < arggmx
1+ Xr
v4 Feonv b Feonv (b)
5: Given bi construct the equivalent randomized bidding strategy mentioned in Theo- rem 3.1 and realizes a bid bg /* Such randomized bidding strategy can be constructed effici afficiietly, see the proofs
the full veraion [16]
*/
6: Submit the bid by (to the outer environment or algorithm).
7: Update (b,) = Feony (b,) - F. (b.).
8: Update λ441 X, expl- 9.
9: end for
10: return The bid sequence (b. (br))
The performance of Algorithm is detailed below, whose analysis follows similarly to 6 2
Proposition 3.2. For any unknown value distribution H, the expected regret of Algorithm 7 Junder any competing bid distribution F is bounded by Regret (Algoritmm 7 (F, (T) O(VT), and the expected ROI violation is bounded by A(Algorithm 7 (F, H)) < log
4 No-Regret Autobidding Algorithm with Full Feedback
In Section we present an algorithm (see Algorithm D when the competing bid distribution is known that achieves low expected regret and ROI violation. In practice, both the competing bid distribution may unknown, and the bidder needs to use the observed feedback
F and the value distribution to learn these uncertainties by exploring different bids. In this section, we consider full feedback model where the bidder can observe the realized competing bid d, the end of each round, and we provide algorithm (see Algorithm 2 with low expected regret and low ROI violation.

---

Algorithm descriptions. At a high-level, Algorithm 2 operates as a stage-baue bange-based algorithm. In each stage E [M] where M is the number stages determined shortly, we use the competing bids observed in all previous stages to maintain an empirical CDF Fm for the underlying competing bid distribution F. Let Tm N+ be the number of rounds in stage m and Nn -=m'(mm1 T' be the
number of total rounds right before the stage
We maintain Fm as follows:
Fm
N Σ [E(
1 d:).
b be [0,
(5)
To account for the estimation error and maintain optimism in our bidding strategy, we further define the optimistic CDF Fm.
(b) (Fm(() + Em ^1, 6 [0,
(6)
where Em is parameter carefully chosen to balance the exploration and exploitation tradeoff 10 We
then implement Algorithm by feeding the distribution F (while the actual competing bids are still generated according to the true unknown competing bid distribution F). We summarize the algorithm
details in Algorithm 2
Algorithm 2 No-regret bidding algorithm with full feedback
Input: Time horizon T, the value sequence V" (revealed sequentially).
Input: Let M [log(T + 1)] be the number stages.
Initialize: Let Fi be an arbitrary distribution. Ni
1: for m < to M do
2: Current stage length: T.. <- 2m-1
3: Feed the Algorithm | with inputs: <- Tmy < Fm /* Note that we compute submitted bid and update dual variable de from Algorithm | based on Fm. while the actual competing bids are generated according to F.
4: Tm rounds of maximum competing bids {d: : 2m ,... 13 are revealed.
5: Nm+1 + Tm + Nm
6: Optimism parameter Em++1 log(Nm+1)
V /N.11
7: Update the empirical CDF Fm be F Fm41 with the observed maximum competing bids
[d, == 1, 2 - }} according to Eqn. (5)
8: Obtain Fm+11 defined as in Eqn. (6)
9: end for
return The bid sequence (br)eeT))
Algorithm performance. We summarize the performance of Algorithm as follows.
Theorem 4.1. For any unknown competing bid distribution F' and unknown value distribu- tion H, under the setting with full feedback, the expected regret of Algorithu 2 is bounded by Regret(AAee Algorithm 2 (F, H)) = Õ(VT), and the expected ROI violation is bounded by
A AAllgorithm
2
We conclude this section by providing proof sketch for Theorem technical details are deferred the full version [6]].
4.1 All missing proofs with
We first discuss the regret and ROI violation incurred with any fixed value sequence VT, The analysis of regret and ROI violation of algorithm 2 consists of three main steps:
Proof of Theorem 4.1
Step 1 Accuracy of the optimistic CDF F: In this step, proved that when e., θ log N...
VN
the CDF Fm (defined in Eqn. (6) serves as an optimistic estimate the true underlying competing bid distribution (Fm > F with high probability), while still remains close, specifically we have sup, (b) F(b) 2sm with high probability.
10 As shorthand, we write
min(2.y) v).

---

Step 2 - The performance approximation when implementing Algorithm with estimated distributions: In this step, we establish the performance guarantee (evaluating in an environment with competing bid distribution F) of the bids generated by feeding Algorithm |
with distribution
Ft that satisfies Ft 2 F and sups PT (b) F(D) S 2e,
(egget(ALG1(E")) I (F.V") O(VT) + 2=T, A(ALGI(FT) I =
2=T. Here we denote by ALG1(FT) the bids generated by feeding Algorithm | with a distribution Ft. In stage m, when we use the estimated optimistic F'm input for Algorithm D both the regret and ROI violation will be amplified by T'. 22,.. compared to using the true CDF as input.
cDF
Step 3 - Aggregating the regret and ROI violation over M stages: With ém selected in Step 1, the regret of Algorithm is bounded by Õ(VT). The ROI violation is bounded by O O(VT).
Thus, when value sequence V is i..d. drawn from H", the expected regret and ROI violation over the distribution F and H satisfies
Regret Algorithm
2 (F, H)) = Bvt- [Regret A Algorithm 2 (F, (F,VT)) Ö(VT).
A (Algorithm (F, Byr-HT (AAlgorithm 2 (F. (F.V")) Ö(VT).
5 No-Regret Autobidding Algorithm with Bandit Feedback
In this section, we consider a more challenging learning setting in which the bidder receives only bandit feedback at the end of each round specifically, whether they won the item not. This bandit feedback model is common in practice and has been extensively studied in the literature (see, e.g., 15). The main results in this section are an online autobidding algorithm (see Algorithm 3 with the provable performance (see Theorem 5.I] under such bandit feedback.
Algorithm descriptions. At high-level, our proposed Algorithm 3 operates as an explore-then- exploit type algorithm. The algorithm starts with an exploration stage that explores different bids to obtain sufficient knowledge about the underlying competing bid distribution. Then, the algorithm implements a "conservative" variant of Algorithm with the estimated competing bid distribution over the remaining rounds.
In the exploration phase, explore different bids, discretize the bid range (0, 1] into K equal intervals with grid points {c=) kE(K where c = b/K for k E [K] U {0]. We then bid each grid point O consecutively for M rounds, and then use the observed bidding outcomes to compute an empirical estimate F for the underlying competing bid distribution F: for f [1:K- 1]
F(cs)= = maxxe(( M "[E(k-MHH M
l 2 d.}
(7)
and we let ((ck) Note that in the bandit feedback setting, de unknown and only the indicator of winning or not, denoted as 1 (be 2 d. is revealed. We also extend the definition of f to any bid b E [0. 1) as a step function: F(b) = F(cx) if E [CR, Ck++). After exploring all the grid bids, we can have sufficient observations to maintain a good estimate F for the underlying the competing bid distribution. Similar to Algorithm
2 we also define the optimistic CDF F as follows:
F(b)= ((cx) +8) A1, if E [ck, Ck+))
(8)
where & again is a parameter carefully chosen to balance the exploration and exploitation tradeoff
In Algorithm with full feedback, after obtaining the optimistic CDF F, directly implement Algorithm assuming the underlying competing bid distribution F. However, this approach may fail under our bandit feedback setting, we can longer guarantee uniform error bound on F (i.c., sup; (b) F(b) might be large). Instead, in the exploitation phase of Algorithm 3 we implement Algorithm for the remaining rounds in "conservative" way. In particular, we define conservative version of the optimistic CDF F as follows:
F*(b) = F ((b ((b+1/A) (1K))),)
be [0.1].
We then feed Algorithm 1 with the input T K M as the time horizon, and E as if the underlying competing bid distribution is F to generate a sequence of bids (bf) for the remaining rounds. Instead of directly using these bids, we submit the bids also in a conservative way. particular, we bid (b.) where each bid be + (6E + 1/x) A 1.

---

Algorithm 3 No-regret bidding algorithm with bandit feedback
Input: Time horizon T, the value sequence V (revealed sequentially).
Initialize: Initialize dual variable X1 1, K M.
/* Exploration phase */
1: Discretize [0, 1] to obtain grid points {co, c1, C2 ,,,..,,,
2: for k <- to K do
3: Bid Cæ consecutively for M time rounds.
4: Observe the allocation outcomes 1(6; 2 di M++
5: end for
6: Obtain the empirical CDF F, the optimistic CDF F and the conservative CDF F defined as in
Eqn. 77 (8) and
9 respectively.
/* Exploitation phase */
7: Feed the [ inputs: T K-M,F
8: Let {b{) be the bids generated from Algorithm| [ with these input specifications.
9: Submit the bids {b,] over remaining rounds where each bid b, t (bf + l/k) 1.
10: return The bid sequence (brJeez
Algorithm performance. The performance of Algorithm is summarized as follows:
Theorem 5.1. For any unknown competing bid distribution F and unknown value distribution H, under the bandit b feedback, the expected regret of Algorithm 3 with M = O ((VT), = @(T' is
bounded by Regret(A (aaeettAAlggiittin Algorithm 3 (F, H)) = O(T")), and the expected ROI violation is bounded
by A AAAlorrithm (F, H)) ((7)))
The proof of Theorem 5.1 and all relevant lemmas (with proofs) are deferred to the full version [6]
References
[1] Gagan Aggarwal, Ashwinkumar Badanidiyuru, Santiago R Balseiro, Kshipra Bhawalkar, Yuan Deng, Zhe Feng, Gagan Goel, Christopher Liaw, Haíhao Lu, Mohammad Mahdian, et al. 2024. Auto-bidding and auctions in online advertising: A survey, ACM SIGecom Exchanges 22, 1 (2024), 183.
[2] Gagan Aggarwal, Ashwinkumar Badanidiyuru, and Aranyak Mchta. 2019. Autobidding with constraints. In Web and Internet Economies: 15th International Conference, WINE 2019, New York, NY, USA, December 10-12, 2019, Proceedings 15. Springer, 17-30.
[3] Gagan Aggarwal, Giannis Fikioris, and Mingfei Zhao. 2025. No-regret algorithms in non- truthful auctions with budget and roi constraints. Proceedings of the ACM on Web Conference 2025. 1398 1415.
[4] Santiago Balseiro, Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. 2024. Optimal Mechanisms for a Value Maximizer: The Futility of Screening Targets. In Proceedings of the 25th ACM Conference on Economics and Computation. 1101-1101.
[5] Santiago Balsciro, Negin Golrezaci, Mohammad Mahdian, Vahab Mirrokni, and Jon Schneider. 2019. Contextual bandits with cross-learning. Advances in Neural Information Processing Systems 32 (2019).
[6] Santiago Balsciro, Haihao Lu, and Vahab Mirrokni. 2020. Dual mirror descent for online allocation problems. In International Conference on Machine Learning. PMLR, 613-628.
[7] Santiago R Balseiro, Kshipra Bhawalkar, Zhe Feng, Haihao Lu, Vahab Mirrokni, Balasubra- manian Sivan, and Di Wang. 2024. A Field Guide for Pacing Budget and ROS Constraints. In International Conference on Machine Learning. PMLR, 2607-2638.
[8] Santiago R Balseiro, Yuan Deng, Jieming Mao, Vahab S Mirrokni, and Song Zuo. 2021. The landscape auto-bidding auctions: Value versus utility maximization. In Proceedings of the 22nd ACM Conference Economics and Computation. 132-133.
10

---

[9] Santiago R Balseiro and Yonatan Gur. 2019. Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Science 65, (2019), 3952-3968.
[10] Xiaohui Bei, Pinyan Lu, Zhiqi Wang. Tao Xiao, and Xiang Yan. 2025. Optimal Auction Design for Mixed Bidders. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 39. 13614-13621.
[11] Damien Berriaud, Ezzat Elokda, Devansh Jalota, Emilio Frazzoli, Marco Pavone, and Florian Dörfter. 2024. To Spend or to Gain: Online Learning in Repeated Karma Auctions. arXiv preprint arXiv:2403. 04007 (2024).
[12] Christian Borgs, Jennifer Chayes, Nicole Immorlica, Kamal Jain, Omid Etesami, and Mo- hammad Mahdian. 2007. Dynamics of bid optimization in online advertisement auctions. In Proceedings of the 16th international conference on World Wide Web. 531-540.
[13] Matteo Castiglioni, Andrea Celli, and Christian Kroer. 2022. Online learning with knapsacks: the best of both worlds. In International Conference Machine Learning. PMLR, 2767-2783.
[14] Matteo Castiglioni, Andrea Celli, and Christian Kroer. 2024. Online Learning under Budget and ROI Constraints via Weak Adaptivity. In International Conference on Machine Learning. PMLR, 5792-5816.
[15] Nicolò Cesa- Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. 2024. The role of transparency in repeated first-price auctions with unknown valua- tions. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 225-236.
[16] Yuan Deng, Yilin Li, Wei Tang, and Hanrui Zhang. 2025. No-Regret Online Auto- bidding Algorithms in First-price Auctions. arXiv preprint arXiv:2510.1688 (2025). arXiv:2510. 16869 [cs.GT] https://arxiv.ot wttgg//bs//1/.... 16869
[17] Yuan Deng. Mohammad Mahdian, Jieming Mao, Vahab Mirrokni, Hanrui Zhang, and Song Zuo. 2024. Efficiency of the generalized second-price auction for value maximizers. In Proceedings of the ACM Web Conference 2024, 46-56.
[18] Yuan Deng, Jieming Mao, Vahab Mirrokni. Hanrui Zhang, and Song Zuo. 2024. Efficiency of the first- auction in the autobidding world. Advances in Neural Information Processing Systems 37 (2024), 139270-139293.
[19] Yuan Deng, Vahab Mirrokni, and Hanrui Zhang. 2022. Posted pricing and dynamic prior- independent mechanisms with value maximizers. Advances in Neural Information Processing Systems 35 (2022), 24158-24169.
[20] Yiding Feng, Brendan Lucier, and Aleksandrs Slivkins. 2024. Strategic budget selection in competitive autobidding world. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 213-224.
[21] Zhe Feng, Swati Padmanabhan, and Di Wang. 2023. Online Bidding Algorithms for Return-on- Spend Constrained Advertisers. In Proceedings of the ACM Web Conference 2023. 3550-3560.
[22] Giannis Fikioris and Êva Tardos. 2023. Approximately stationary bandits with knapsacks. In The Thirty Sixth Annual Conference on Learning Theory. PMLR, 3788-3782.
[23] Giannis Fikioris and Éva Tardos. 2023. Liquid welfare guarantees for no-regret learning in sequential budgeted auctions. In Proceedings of the 24th ACM Conference on Economics and Computation. 678 6988
[24] Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins. 2023. Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence. In /4th Innovations Theoretical Computer Science Conference (ITCS 2023), Vol. 251. Schloss Dagstuhl-Leibnn Leibniiz- Zentrum für Informatik, 52.
[25] Yanjun Han, Zhengyuan Zhou, Aaron Flores, Erik Ordentlich, and Tsachy Weissman. 2020. Learning to bid optimally and efficiently in adversarial first-price auctions. arXiv preprint arXiv:2007.0456 (2020).

---

[26] Nicole Immorlica, Karthik Sankararaman, Robert Schapire, and Aleksandrs Slivkins. 2022. Adversarial bandits with knapsacks. J. ACM 69, 6 (2022), 1-47.
[27] Thomas Kesselheim and Sahil Singla. 2020. Online learning with vector costs and bandits with knapsacks. In Conference on Learning Theory. PMLR, 2286-2305.
[28] Rachitesh Kumar, Jon Schneider, and Balasubramanian Sivan. 2024. Setregiicaly-Roobuee Learning Algorithms for Bidding in First-Price Auctions. In Proceedings of the 25th ACM Conference Economics and Computation. 893-893.
[29] Christopher Liaw, Aranyak Mchta, and Andres Perlroth. 2023. Efficiency of non-truthful auctions in auto-bidding: The power of randomization. In Proceedings of the ACM Web Conference 2023. 3561-3571.
[30] Pinyan Lu, Chenyang Xu, and Ruilong Zhang. 2023. Auction design for value maximizers with budget and return-on-spend constraints. In International Conference on Web and Internet Economics. Springer, 474 491.
[31] Brendan Lucier, Sarath Pattathil, Aleksandrs Slivkins, and Mengxiao Zhang. 2024. Autobidders with budget and roi constraints: Efficiency, regret, and pacing dynamics, In The Thirty Seventh Annual Conference on Learning Theory. PMLR, 3642-3643.
[32] Hongtao Lv, Xiaohui Bei, Zhenzhe Zheng, and Fan Wu. 2023. Auction design for bidders with ex post roi constraints. In International Conference on Web and Internet Economics. Springer, 492-508.
[33] Thomas Nedelec, Clément Calauzènes, Noureddine El Karoui, Vianney Perchet, et al. 2022. Learning in repeated auctions. Foundations and Trends@ Machine Learning 15, (2022). 176-334.
[34] Aleksandrs Slivkins et al. 2019. Introduction to multi-armed bandits. Foundations and Trends@ Machine Learning 12, 1-2 (2019), 1-286.
[35] Fransisca Susan, Negin Golrezaei, and Okke Schrijvers. 2023. Multi-platform budget manage- ment in ad markets with non-ic auctions. arXiv preprint arXiv:2306.07352 (202)))
[36] Sushant Vijayan, Zhe Feng, Swati Padmanabhan, Karthikeyan Shanmugam, Arun Suggala, and Di Wang. 2025. Online Bidding under RoS Constraints without Knowing the Value. In Proceedings of the ACM on Web Conference 2025. 3096-3107.
[37] Qian Wang, Zongjun Yang. Xiaotie Deng, and Yuqing Kong. 2023. Learning bid repeated first-price auctions with budgets. In International Conference Machine Learning. PMLR, 36494-36513.
[38] Jonathan Weed, Vianney Perchet, and Philippe Rigollet. 2016. Online learning in repeated auctions. In Conference Learning Theory. PMLR, 1562-1583.
12

---

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

---

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

---

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

---

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

---

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

---

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

---

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


Reviews:
[{"review_id": "SEvFogcOIc", "reviewer": "Reviewer_jSPN", "summary": "The paper addresses the design of online bidding algorithms for repeated first-price auctions with ROI constraints. It benchmarks performance against the optimal randomized strategy in hindsight, focusing on two feedback settings: full feedback (where the highest competing bid is observed) and bandit feedback (where only win/loss outcomes are known). The goal is to minimize regret and ensure the ROI constraint is met.", "questions": "NA", "limitations": "NA", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The result of near-optimal algorithm for the repeated first-price auctions with ROI constraints is important.\n2. Concrete theoretical analysis of the regret bounds for the proposed algorithm.\n\nWeaknesses:\n1. The algorithm design is kind of straightforward. Basically, it is built on an optimal algorithm requiring known distribution, and a subtle process dealing with estimating the unknown distribution.\n2. The budget constraint is not considered. Although it is claimed that the result can be generalized to the setting with budget constraints, it seems not to be trivial.", "was_revised": true, "final_justification": "The author clearified how to deal with budget constraint, which addressed part of my concerns. I am positive on this paper now, although still think it is a boardline paper.", "rebuttal": "Thank you for your insightful and constructive feedback. \n\n> Weakness 1: The algorithm design is kind of straightforward. Basically, it is built on an optimal algorithm requiring known distribution, and a subtle process dealing with estimating the unknown distribution.\n\nAs discussed in our technical overview, there are several concrete technical challenges: characterizing ostensibly unstructured optimal strategies, reconciling the mirror-descent-based primitive and our characterization, dealing with unknown distributions of competing bids, etc. While an individual step in our roadmap might appear natural in hindsight, it was certainly not straightforward that this was the right path towards an almost optimal algorithm before the fact. Also, as we compare with the most relevant prior work in our paper, Feng et al. [1] study the problem with truthful auction mechanisms, where the distribution of competing bids is irrelevant, and Aggarwal et al. [2] design the algorithm against a weaker benchmark -- the best Lipschitz bidding function that maps values to bids. Both prior results, which already bear a remarkable amount of technicality, solve only special / weaker cases of the problem under restrictive conditions. Given that, we would argue that even if we disregard all technical details, the fact that we manage to handle non-truthful actions and compete against unconditionally optimal benchmarks is evidence that there is something nontrivial going on. Further details can be found in the technique overview part of the paper.\n\n> Weakness 2: The budget constraint is not considered. Although it is claimed that the result can be generalized to the setting with budget constraints, it seems not to be trivial.\n\nWe are sorry for being overly brief. The reason that we (implicitly) stated that the generalization is \"easy\" is that the mirror-descent-based primitive is known to work naturally for both budget and ROI constraints in similar settings (see, e.g., the work by Feng et al. [1]), and to handle budget constraints instead of / in addition to ROI constraints in our setting, one would simply combine the budget-constrained version of the primitive with all the additional work done in our paper, including all steps discussed in our technical overview. When we add the budget constraint, the corresponding changes we need to make is similar to what Feng et al. [1] did in Section 5.1 of their paper, which roughly involves (1) introducing a new Lagrangian multiplier $\\mu$ corresponding to the budget constraint, (2) updating $\\mu$ in a way similar to how $\\lambda$ is updated in our paper, and (3) terminating the algorithm when the remaining budget is too small. The way bids are computed needs to be adapted accordingly. More specifically, Eq. (2) should be modified into the following:\n$\\max \\mathbb{E} \\left[\\sum_{t\\in[T]}  v_t \\cdot F(b_t) + \\min_{\\lambda \\ge 0} \\lambda \\cdot \\sum_{t\\in[T]} (v_t\\cdot F(b_t) - b_t \\cdot F(b_t)) + \\min_{\\mu \\ge 0} \\mu \\cdot (B - \\sum_{t\\in[T]} b_t \\cdot F(b_t))\\right],$\nwhere $B$ is the total budget; bids should be computed in the following way:\n$\\widetilde b_t \\gets argmax_{b\\in[0, 1]} \\left[(1+\\lambda_t)\\cdot v_t\\cdot F_{conv}(b)- (\\lambda_t + \\mu_t) \\cdot b \\cdot F_{conv}(b)\\right].$\n\nRegarding the analysis of the regret bound, in Feng et al.'s paper, they point out that the combination of budget and ROI constraints is intuitively straightforward, since the analyses of the algorithms with the two types of constraints respectively are linear in nature. This means one can handle these two constraints separately, and taking the linear combination, the regret under both constraints is still $O(\\sqrt{T})$. Overall, the adaptation would be somewhat repetitive technically (with respect to both our analysis of the case with ROI constraints, and Feng et al.'s work [1]), which we wanted to avoid because of limited space; rather, we chose to focus on the additional challenges posed by non-truthful auction mechanisms. We will add a more detailed discussion in the paper.\n\n[1] Zhe Feng, Swati Padmanabhan, and Di Wang. Online Bidding Algorithms for Return-on-Spend Constrained Advertisers.\n\n[2] Gagan Aggarwal, Giannis Fikioris, and Mingfei Zhao. No-regret algorithms in non-truthful auctions with budget and ROI constraints."}, {"review_id": "wWQT3ONxhp", "reviewer": "Reviewer_xKcP", "summary": "This paper focuses on the design and analysis of autobidding algorithms for online first-price auctions. More specifically, the focus is on the problem of bidding repeatedly under a certain Return Over Investment constraint. This is motivated by the fact that these kinds of auctions and of constraints are common practice in online advertising auctions. The main challenge in this problem comes from the fact that the opposing bid distribution $F$, and the distribution of the agents' value $H$ are unknown and need to be learned online. This paper considers two types of feedback after each round: full information and bandit feedback. Before stating their algorithm, the paper provides a reduction of their problem against an arbitrary distribution $F$ to a problem against a concavified version $F$, which simplifies the problem and ensures known techniques can be better adapted. They then provide an algorithm, regret, and ROI constraint violation guarantees for this algorithm. They show their algorithm can guarantee a regret upper bounded by $\\tilde{\\mathcal{O}}\\left ( \\sqrt{T} \\right )$ under full-information feedback and $\\tilde{\\mathcal{O}}\\left ( T^{3/4} \\right )$ under bandit feedback. This result improves on the literature, not in terms of regret rates but on the class of comparator strategies against which the regret is computed (General vs Lipschitz).", "questions": "1. I am wondering about the link with auctions with replenishing budget. It does seem that if we consider the setting where an algorithm for bidding is constrained by its budget but receives additional budget (say $\\rho v^t$ when the auction is won), an algorithm should be similar to the one in your setting? A setting of this kind is fully described in [1]. \n\n2. I understood that once the transformation (concavification of $F$) is done, the best strategy for each valuation $v$ is a deterministic bid. Therefore, we could define a function which maps the value observed to the best bid corresponding $b(v)$. I am wondering whether this function would be Lipschitz (or maybe only right/left Lipschitz). Do you have any counterexamples? I am asking to understand better the scale of the contribution. If the best in hindsight function $b(v)$ in the concavified version of the problem is Lipschitz, then one could use the result from previous work, right? \n(I understand that making the link between the concavified and original problem and showing how uncertainty in one is related to uncertainty in the other would remain an issue.)\n\n3. You did not provide in the paper any result on lower bounds. It seems from the theoretical results alone that it is unclear whether the tight regret bound should be $T^{2/3}$ or $T^{3/4}$. Do you have any insight? Did you run experiments for which a regret of $T^{2/3}$ could be attained?\n\n4. Is it clear that the optimal bound in the full-information feedback is $\\mathcal{O} ( \\sqrt{T} )$? Is there an existing lower bound in the literature, or could such a result be derived?\n\n\n[1] Berriaud, Damien, et al. \"To Spend or to Gain: Online Learning in Repeated Karma Auctions.\" arXiv preprint arXiv:2403.04057 (2024).", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "This paper presents a well-motivated and technically sound approach to autobidding in first-price auctions under ROI constraints, offering improved regret guarantees in both full-information and bandit settings, though it would benefit from lower bounds and empirical validations.\n\n# Strenght : \n\n- The paper is well written and motivated. The problem studied is interesting and the tools needed to obtain the result are non-trivial. \n\n- The paper proves new results that do not immediately follow from known ones.\n\n- The paper is technically sound and includes a helpful overview of the technical challenges, both in the introduction and in the proof sketches. \n\n# Weaknesses : \n\n- The paper doesn't provide matching lower bounds for the result stated. This makes it difficult to assess whether the rates obtained are optimal or if there is still room for improvement. \n\n- The paper lacks experiments. It would specifically be nice to have some in order to compare their result with the work of Aggarwal et al. [3], which is referred to in the paper. Their result strengthens this result in a non-straightforward manner (by extending the family of functions to which the fixed best strategy used to compute the regret belongs), as a result, it is difficult to gauge the difference made by this change. Experiments would provide a nice way to give some intuition. \n\n- The paper states that their result easily generalizes to other auction mechanisms (line 49, and footnote 4, page 4) as part of their result. It would be preferable to avoid emphasizing this claim without proof. I would be more comfortable if that was mentioned in the introduction and or conclusion (not in result / setting sections). Otherwise, you could provide (eventually in the appendix) a note describing how this would generalize to a few specific common auctions.", "was_revised": true, "final_justification": "Given the discussion with the authors, I am confident in my first opinion about the paper. Furthermore, I believe the weakness we discussed the most can be easily addressed. I therefore maintain my rating for this paper.", "rebuttal": "Thank you for your detailed and thoughtful feedback.\n\n> Weakness 1: The paper doesn't provide matching lower bounds for the result stated. This makes it difficult to assess whether the rates obtained are optimal or if there is still room for improvement.\n\n> Question 3: You did not provide in the paper any result on lower bounds. It seems from the theoretical results alone that it is unclear whether the tight regret bound should be $T^{2/3}$ or $T^{3/4}$. Do you have any insight? Did you run experiments for which a regret of  $T^{2/3}$ could be attained?\n\n> Question 4: Is it clear that the optimal bound in the full-information feedback is $\\Omega(\\sqrt{T})$? Is there an existing lower bound in the literature, or could such a result be derived?\n\nLet us respond to the 3 closely connected questions together. In the full feedback setting, there is a folklore lower bound of $\\Omega(\\sqrt{T})$, so our upper bound of $\\tilde{O}(\\sqrt{T})$ is almost tight. The folklore lower bound is essentially inherited from the most fundamental setting of stochastic bandits, even with only two discrete actions. The idea is that to distinguish two actions whose expected rewards are within $\\Delta$ of each other, one roughly needs $\\Omega(\\Delta^{-2})$ rounds to be confident enough. So after $T$ rounds, intuitively, one would be able to find an action that is optimal up to an additive error of $\\Theta(1 / \\sqrt{T})$. This translates to a cumulative error of $\\Theta(T \\cdot 1 / \\sqrt{T}) = \\Theta(\\sqrt{T})$. To instantiate this bound in our setting, one could, for example, consider the following setup: the value distribution is supported on $\\\\{1/3, 2/3\\\\}$, whose mean is either $1/2 - \\varepsilon$ or $1/2$; the competing bid distribution is a point mass at $1/2$, i.e., the competing bid is always $1/2$. The optimal bidding strategy, depending on the mean of the value distribution, is either (1) always bidding $1/2$ (when the mean is $1/2$), or (2) bidding $1/2$ deterministically when the value is $2/3$, and bidding $1/2$ with probability $1 - \\Theta(\\varepsilon)$ (and bidding $0$ otherwise) when the value is $1/3$. But to figure out which one is better, the algorithm must first estimate the mean of the value distribution accurately enough, which takes $\\Omega(\\varepsilon^{-2})$ rounds. By arguments similar to the one sketched above, one can establish an $\\Omega(\\sqrt{T})$ lower bound. We will add a remark in the paper.\n\nIn the bandit feedback setting, Aggarwal et al.'s work (reference [3] in the paper) establishes a stronger lower bound of $\\Omega(T^{2/3})$, which in particular means the bandit feedback setting is strictly harder. Unfortunately, as you point out, we don't have much evidence supporting either $T^{2/3}$ or $T^{3/4}$ as the \"right\" bound. If we had to take a guess, we would tend to pick $T^{2/3}$, since the lower bound construction by Aggarwal et al. appears quite difficult to improve. If that is the case, then progress on the upper bound side would probably require a non-exploration-exploitation approach. In particular, our algorithm by design must suffer a regret of $\\Omega(T^{3/4})$, because of the exploration phase of length $\\Omega(T^{3/4})$.\n\nAs for numerical experiments: we did not try them, because (1) our algorithm by design cannot perform better than $\\Omega(T^{3/4})$, as discussed above, and (2) even if, hypothetically, the \"right\" bound was $\\Theta(T^{3/4})$, it would be difficult to spot a hard instance that forces this bound via random guess. Presumably, \"common\" instances would be easy, i.e., we would almost always end up with \"easy\" instances if we generate them randomly in a natural way (the hard instance forcing $\\Omega(T^{2/3})$ by Aggarwal et al. is fairly delicate). Experimenting on such instances likely wouldn't provide much insight.\n\n> Weakness 2: The paper lacks experiments. It would specifically be nice to have some in order to compare their result with the work of Aggarwal et al. [3] ...\n\nWe agree that experiments would be generally helpful. Nonetheless, we did not perform them for two main reasons: (1) The paper is already fairly packed with the main theoretical results (with almost all proofs deferred to appendices), and we figured it would serve the audience better to focus on the theory part and convey the main ideas and messages properly. (2) As you point out, the improvement over Aggarwal et al.'s result is non-straightforward, particularly in the sense that on some instances, the improvement is extremely large, while on others, it is much less significant. So if we were to run experiments, we'd ideally run them on real-life data to better quantify the practical improvement. Such data, unfortunately, is unavailable due to the nature of the online advertising industry (regulation, privacy, business considerations, etc.).\n\n> Weakness 3: The paper states that their result easily generalizes to other auction mechanisms (line 49, and footnote 4, page 4) as part of their result. It would be preferable to avoid emphasizing this claim without proof ...\n\nThanks for the suggestion. The generalization involves mostly the characterization in Section 3.1. Recall that the current characterization turns the input competing bid distribution into a \"concavified\" version, by concavifying the allocation-payment curve corresponding to the competing bid distribution and mapping it back. If one were to use another auction mechanism, the mapping between the competing bid distribution and the allocation-payment curve would change depending on the allocation and payment rules of the auction mechanism, but other than that, one would be able to perform essentially the same operation on the competing bid distribution. After this step, one only needs to solve the Lagrangified value maximization problem under the new auction mechanism (corresponding to the current Eq. (2) and (3)). Again, the specific form of the objective here depends on the allocation and payment rules of the mechanism, but other than that, everything in Algorithm 1 remains exactly the same. No further changes are needed in Algorithms 2 and 3, which simply call the modified Algorithm 1 as a subroutine. We will add a discussion of this (possibly as an appendix).\n\n> Question 1: I am wondering about the link with auctions with replenishing budgets. It does seem that if we consider the setting where an algorithm for bidding is constrained by its budget but receives additional budget (say $\\rho v^t$ when the auction is won), an algorithm should be similar to the one in your setting? A setting of this kind is fully described in [1].\n\nThis is an interesting insight. The way we view this connection is it provides a different perspective on the problem, though it's not immediately clear how it might help technically. The setting in [1] in particular seems to differ from ours in a number of ways (equally redistributed \"karma\" among agents, step-wise budget feasibility constraints, etc.), though of course the conceptual connection (non-truthfulness of second-price auctions, etc.) is interesting. It would also be interesting to see if one can unify these models into a single framework. We will discuss this in the paper.\n\n> Question 2: I understood that once the transformation (concavification of $F$) is done, the best strategy for each valuation $v$ is a deterministic bid. Therefore, we could define a function which maps the value observed to the best bid corresponding $b(v)$. I am wondering whether this function would be Lipschitz (or maybe only right/left Lipschitz). Do you have any counterexamples? I am asking to understand better the scale of the contribution. If the best in hindsight function $b(v)$ in the concavified version of the problem is Lipschitz, then one could use the result from previous work, right? ...\n\nThis is indeed a natural idea. Unfortunately, the mapping you mention (value to optimal bid after concavification) is not always Lipschitz: consider a value distribution supported on $\\\\{1/2 - \\varepsilon, 1/2 + \\varepsilon \\\\}$ for some small $\\varepsilon > 0$ (probabilities to be fixed later), and a competing bid distribution supported on $\\\\{0, 1\\\\}$, say with equal probabilities. One can tune the probabilities on $1/2 - \\varepsilon$ and $1/2 + \\varepsilon$ respectively, such that the mapping $1/2 - \\varepsilon \\mapsto 0, 1/2 + \\varepsilon \\mapsto 1$ is the unique optimal strategy (one only needs to make sure the ROI constraint is binding under this strategy). This strategy can be highly \"not continuous\" when $\\varepsilon$ is small. Letting $\\varepsilon \\to 0$ then rules out any finite Lipschitz constant. In other words, at least one cannot apply techniques from Lipschitz bandits in a straightforward way.\n\nIndependent of Lipschitz continuity, we'd also remark that the choice of the innermost primitive is technically insignificant. Most technical work in the paper lies in reducing and transforming the problem to a form that can be handled using existing machinery -- in our paper, we chose to use the mirror-descent-based primitive. The adaptation we made for the primitive to work in the exact way we need it to is relatively minor compared to the rest of the reduction. Suppose, hypothetically, that the mapping discussed above was in fact Lipschitz, then one would be free to choose either the mirror-descent-based primitive or the Lipschitz bandits primitive as the innermost block, which, in our opinion, wouldn't affect the nature of the algorithm. However, even in this hypothetical world, one still wouldn't be able to run the Lipschitz bandits primitive in an end-to-end fashion (i.e., as a standalone algorithm), because without knowing the competing bid distribution, one wouldn't be able to interpret \"deterministic\" bids generated by the primitive, or even compute effective rewards."}, {"review_id": "m1D86Vqnxr", "reviewer": "Reviewer_Xvxb", "summary": "This paper studies the autobidding problem under the setting of ROI-constrained value maximizers in first-price auctions. It considers two distinct feedback settings: (1) the full-feedback setting, where the maximum competing bid is observed, and (2) the bandit-feedback setting, where the bidder only observes whether they win each auction. For each setting, the paper develops corresponding bidding algorithms with regret guarantees.", "questions": "1. Do the value vectors $v_t$, for $t \\in [T]$, need to be i.i.d. in your setting?\n2. Should the input to Algorithm 2 include the maximum competing bids revealed sequentially?\n3. How does definition (6) depend on $c_l$? $d_t$ should not be known in the bandit feedback setting.", "limitations": "See  Weaknesses", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strength: \n1. The paper addresses an important problem in online advertising and provides useful regret bounds in a novel setting that avoids some of the assumptions made in prior work.  \n2. The paper is well-written and well-organized.\n           Weakness: \n1. The paper considers only ROI constraints and does not incorporate budget constraints, which are important in practical settings.\n2. The paper lacks numerical results and real-world applications, leaving open questions about the practical feasibility and effectiveness of the proposed approach.", "was_revised": true, "final_justification": "The authors have partially addressed my concerns, but the practical feasibility and effectiveness may need to be further elaborated. I will maintain my current positive score and remain slightly inclined toward acceptance.", "rebuttal": "Thank you for your thoughtful and helpful feedback.\n\n> Weakness 1: The paper considers only ROI constraints and does not incorporate budget constraints, which are important in practical settings.\n\nAs mentioned in the paper, our results generalize naturally to settings with ROI and / or budget constraints. We did not discuss the generalization in detail, since the mirror-descent-based primitive is known to work naturally for both budget and ROI constraints in similar settings (see, e.g., the work by Feng et al. [1]), and to handle budget constraints instead of / in addition to ROI constraints in our setting, one would simply combine the budget-constrained version of the primitive with all the additional work done in our paper, including all steps discussed in our technical overview. When we add the budget constraint, the corresponding changes we need to make is similar to what Feng et al. [1] did in Section 5.1 of their paper, which roughly involves (1) introducing a new Lagrangian multiplier $\\mu$ corresponding to the budget constraint, (2) updating $\\mu$ in a way similar to how $\\lambda$ is updated in our paper, and (3) terminating the algorithm when the remaining budget is too small. The way bids are computed needs to be adapted accordingly. More specifically, Eq. (2) should be modified into the following:\n$\\max \\mathbb{E} \\left[\\sum_{t\\in[T]}  v_t \\cdot F(b_t) + \\min_{\\lambda \\ge 0} \\lambda \\cdot \\sum_{t\\in[T]} (v_t\\cdot F(b_t) - b_t \\cdot F(b_t)) + \\min_{\\mu \\ge 0} \\mu \\cdot (B - \\sum_{t\\in[T]} b_t \\cdot F(b_t))\\right],$\nwhere $B$ is the total budget; bids should be computed in the following way:\n$\\widetilde b_t \\gets argmax_{b\\in[0, 1]} \\left[(1+\\lambda_t)\\cdot v_t\\cdot F_{conv}(b)- (\\lambda_t + \\mu_t) \\cdot b \\cdot F_{conv}(b)\\right].$\n\nRegarding the analysis of the regret bound, in Feng et al.'s paper, they point out that the combination of budget and ROI constraints is intuitively straightforward, since the analyses of the algorithms with the two types of constraints respectively are linear in nature. This means one can handle these two constraints separately, and taking the linear combination, the regret under both constraints is still $O(\\sqrt{T})$. Overall, the adaptation would be somewhat repetitive technically (with respect to both our analysis of the case with ROI constraints, and Feng et al.'s work [1]), which we wanted to avoid because of limited space; rather, we chose to focus on the additional challenges posed by non-truthful auction mechanisms. We will add a more detailed discussion in the paper.\n\n> Weakness 2: The paper lacks numerical results and real-world applications, leaving open questions about the practical feasibility and effectiveness of the proposed approach.\n\nWe agree that experiments would be generally helpful. Nonetheless, we did not perform them for two main reasons: (1) The paper is already fairly packed with the main theoretical results (with almost all proofs deferred to appendices), and we figured it would serve the audience better to focus on the theory part and convey the main ideas and messages properly. (2) To better quantify the practical feasibility of our results, ideally, we'd run experiments on real-life data. Such data, unfortunately, is unavailable due to the nature of the online advertising industry (regulation, privacy, business considerations, etc.).\n\nAs for real-world applications: our results (as well as the most related prior work) can be naturally applied in online advertising -- in fact, this is the very motivation for our study. Major players such as Google and Meta are known to run algorithms of this kind (i.e., autobidders) on their advertising platforms on behalf of advertisers. We cannot provide URLs in the response, but relevant information can be found on the respective websites of these platforms.\n\n> Question 1: Do the value vectors $v_t$, for $t \\in [T]$ need to be i.i.d. in your setting?\n\nYes, we assume they are i.i.d., as Feng et al. [1] and Aggarwal et al. [2] do in their work. This is in some sense necessary, since one wouldn't be able to get sublinear regret if these values are adversarial.\n\n> Question 2: Should the input to Algorithm 2 include the maximum competing bids revealed sequentially?\n\nYes, you are right. We apologize for the confusion. The maximum competing bids should be revealed sequentially, and the sequence of realized competing bids are used in Eq. (4) to update the empirical distribution iteratively. We will make this more explicit in the paper. \n\n> Question 3: How does definition (6) depend on $c_l$? $d_t$ should not be known in the bandit feedback setting.\n\nIn Eq. (6) (assuming this is what you referred to), $F(c_\\ell)$ depends on $c_\\ell$ through the maximization over $k \\in [\\ell] \\cup \\\\{0\\\\}$. Moreover, $F(c_\\ell)$ only depends on the indicator of winning or not ($\\mathbb{1}[b_t \\ge d_t]$). While $d_t$ is unknown to us, this indicator is precisely the one-bit response we observe in the bandit feedback setting. We will clarify in the paper.\n\n[1] Zhe Feng, Swati Padmanabhan, and Di Wang. Online Bidding Algorithms for Return-on-Spend Constrained Advertisers.\n\n[2] Gagan Aggarwal, Giannis Fikioris, and Mingfei Zhao. No-regret algorithms in non-truthful auctions with budget and ROI constraints."}, {"review_id": "AkLhbPeqgm", "reviewer": "Reviewer_CqEZ", "summary": "The paper presents online autobidding algorithms for repeated first-price auctions with ROI constraints. These algorithms compete against the optimal randomized strategy in hindsight. More specifically, the authors consider the problem where a single bidder participates in single-item first-price auctions repeated over $T$ rounds. At each time step, the learner observes the value $v_t$​ and then submits a bid $b_t$ based on this value and the history. The bidder wins the item if her submitted bid is not less than the highest competing bid  $d_t$ in that round. If she wins, she pays her submitted bid; otherwise, she pays nothing. The goal is to design an online bidding algorithm that maximizes the total realized utility, subject to a Return-On-Investment (ROI) constraint, meaning the total utility should be greater than the total payment. The authors first focus on the offline optimal strategy, which may be randomized, and show—using a convexification argument on the allocation-payment curve—that this randomized problem can be reduced to a deterministic one by replacing the original allocation function with its concave envelope. Based on this, they develop Algorithm 1 for the case where the distribution of the competition is known, and prove that it achieves a regret of order $O(T^{1/2})$. When the distribution of the competition is unknown, they consider two settings: full feedback, where the bidder observes the competing bid $d_t$ at the end of each round, and bandit feedback, where the bidder only observes a binary win/loss signal (0 or 1). For the full feedback setting, they develop an algorithm based on mirror descent that achieves a regret of $O(T^{1/2})$, and for the bandit setting, they propose an explore-then-commit strategy that achieves a regret of $O(T^{3/4})$, leaving a gap with the known lower bound for this problem $\\Omega(T^{2/3})$.", "questions": "- Could the authors provide intuitions on how the problem or solution would change if a budget constraint were introduced?\n- Are there any ideas or insights on how the regret bound in the bandit feedback setting might be improved ? \n- Can the authors discuss how the setting and results might extend to the more realistic case where multiple bidders are learning simultaneously, as is common in online advertising ? \n\nMinor comment: There appears to be a formatting typo at the end of page 9 in the expressions for $T^{1/4}$ and $T^{3/4}$, where the closing brace is missing or misplaced.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n- The paper is well motivated and addresses an important problem in online advertising. \n- From a technical standpoint, the author use a key convexification argument to reduce the randomized constrained optimization problem of the optimal strategy (OPT) to an equivalent deterministic optimization problem.\n- When the distribution of the bids of the competition is known, they propose an algorithm based on this convexification argument that achieves a regret of $O(T^{1/2})$. \n- When the distribution of the bids of the competition is unknown, and the bidder has a full feedback (the competing bid) at the end of the round, they propose an algorithm based on mirror descent that achieves a regret of order $O(T^{1/2})$. \n- In the more challenging bandit feedback setting—where only a binary win/loss signal is observed, they propose an algorithm based on explore-then-commit strategy that achieves a regret of order $O(T^{3/4})$, \n\nWeaknesses:\n- The paper lacks numerical simulations to empirically demonstrate the performance of the proposed algorithms.\n- Although the authors acknowledge the remaining gap in the regret bound for the bandit setting, the paper does not propose potential directions to reduce this gap.\n- The explanation of why the convexification argument preserves the optimal solution could be elaborated; in particular, the transition from optimizing under the original distribution $F$ to its concave enveloppe $F_{conv}$ needs more intuitions. \n- While the paper focuses on ROI constraints, which are important, it does not address how budget constraints—commonly present in real-world bidding environments—could be integrated into the proposed framework.", "was_revised": true, "final_justification": "Given the discussion with the authors, I am confident in my first opinion about the paper.  I therefore maintain my rating for this paper.", "rebuttal": "Thank you for your detailed and insightful feedback.\n\n> Weakness 1: The paper lacks numerical simulations to empirically demonstrate the performance of the proposed algorithms.\n\nWe agree that numerical experiments would be generally helpful. Nonetheless, we did not perform them for two main reasons: (1) The paper is already fairly packed with the main theoretical results (with almost all proofs deferred to appendices), and we figured it would serve the audience better to focus on the theory part and convey the main ideas and messages properly. (2) To better quantify the practical feasibility of our results, ideally, we'd run experiments on real-life data. Such data, unfortunately, is unavailable due to the nature of the online advertising industry (regulation, privacy, business considerations, etc.).\n\n> Weakness 2: Although the authors acknowledge the remaining gap in the regret bound for the bandit setting, the paper does not propose potential directions to reduce this gap.\n\n> Question 2: Are there any ideas or insights on how the regret bound in the bandit feedback setting might be improved?\n\nAs you point out, we were unable to determine the optimal regret bound for the bandit-feedback setting, but not for lack of trying -- for what it's worth, Aggarwal et al. [2] couldn't close the gap either despite the fact that they investigated a weaker benchmark than ours. As for directions for improvement: if we had to make a guess, we'd say the lower bound by Aggarwal et al. [2] is more likely to be tight. On the other hand, the exploration-exploitation approach doesn't seem to have the potential to give a better bound than $O(T^{3/4})$ (e.g., our algorithm has an exploration phase of length $T^{3/4}$, which already generates regret of order $T^{3/4}$). So, to improve the upper bound, one would likely need to take a fundamentally different approach.\n\n> Weakness 3: The explanation of why the convexification argument preserves the optimal solution could be elaborated; in particular, the transition from optimizing under the original distribution $F$ to its concave envelope $F_{conv}$ needs more intuition.\n\nThe proof itself is not straightforward, and we had to place (most of) it in an appendix. Here is the intuition behind the proof: to understand the structure of optimal strategies, it is more convenient to work with the allocation-payment curve $G$, rather than the distribution $F$ of competing bids itself. The allocation-payment curve $G$ can be viewed as a parametrized curve by the bid $b$: when the algorithm bids $b$, the probability of winning (i.e., the allocation) is $F(b)$, and the expected payment is $F(b) \\cdot b$, so $(F(b), F(b) \\cdot b)$ is a point on the curve. Letting $b$ vary across all possible bids in $[0, 1]$, we get a curve that describes the relation between the allocation and the amount of payment required to achieve the allocation, when the algorithm bids deterministically. Now to incorporate randomized bidding, observe that randomizing between two bids corresponds to taking a convex combination of two points on the allocation-payment curve. As a result, the best tradeoff between allocation and payment under randomized bidding is given by the concave envelope $G_{conv}$ of the allocation-payment curve $G$. Now observe that if there is another distribution $F_{conv}$ whose corresponding allocation-payment curve happens to be $G_{conv}$, then deterministic bidding strategies on $F_{conv}$ are \"as good as\" randomized bidding strategies on $F$. We show that this is in fact always the case: $F_{conv}$ always exists and we can construct it from $F$. This finishes the proof. We will add a discussion in the paper if space allows.\n\n> Weakness 4: While the paper focuses on ROI constraints, which are important, it does not address how budget constraints—commonly present in real-world bidding environments—could be integrated into the proposed framework.\n\n> Question 1: Could the authors provide intuitions on how the problem or solution would change if a budget constraint were introduced?\n\nAs mentioned in the paper, our results generalize naturally to settings with ROI and / or budget constraints. We did not discuss the generalization in detail, since the mirror-descent-based primitive is known to work naturally for both budget and ROI constraints in similar settings (see, e.g., the work by Feng et al. [1]), and to handle budget constraints instead of / in addition to ROI constraints in our setting, one would simply combine the budget-constrained version of the primitive with all the additional work done in our paper, including all steps discussed in our technical overview. When we add the budget constraint, the corresponding changes we need to make is similar to what Feng et al. [1] did in Section 5.1 of their paper, which roughly involves (1) introducing a new Lagrangian multiplier $\\mu$ corresponding to the budget constraint, (2) updating $\\mu$ in a way similar to how $\\lambda$ is updated in our paper, and (3) terminating the algorithm when the remaining budget is too small. The way bids are computed needs to be adapted accordingly. More specifically, Eq. (2) should be modified into the following:\n$\\max \\mathbb{E} \\left[\\sum_{t\\in[T]}  v_t \\cdot F(b_t) + \\min_{\\lambda \\ge 0} \\lambda \\cdot \\sum_{t\\in[T]} (v_t\\cdot F(b_t) - b_t \\cdot F(b_t)) + \\min_{\\mu \\ge 0} \\mu \\cdot (B - \\sum_{t\\in[T]} b_t \\cdot F(b_t))\\right],$\nwhere $B$ is the total budget; bids should be computed in the following way:\n$\\widetilde b_t \\gets argmax_{b\\in[0, 1]} \\left[(1+\\lambda_t)\\cdot v_t\\cdot F_{conv}(b)- (\\lambda_t + \\mu_t) \\cdot b \\cdot F_{conv}(b)\\right].$\n\nRegarding the analysis of the regret bound, in Feng et al.'s paper, they point out that the combination of budget and ROI constraints is intuitively straightforward, since the analyses of the algorithms with the two types of constraints respectively are linear in nature. This means one can handle these two constraints separately, and taking the linear combination, the regret under both constraints is still $O(\\sqrt{T})$. Overall, the adaptation would be somewhat repetitive technically (with respect to both our analysis of the case with ROI constraints, and Feng et al.'s work [1]), which we wanted to avoid because of limited space; rather, we chose to focus on the additional challenges posed by non-truthful auction mechanisms. We will add a more detailed discussion in the paper.\n\n> Question 3: Can the authors discuss how the setting and results might extend to the more realistic case where multiple bidders are learning simultaneously, as is common in online advertising?\n\nPut in our language, this essentially means the distribution of competing bids changes over time in a certain way (depending on the learning algorithm used by other bidders). To handle such cases, one straightforward idea would be to design no-regret algorithms in adversarial environments.  Unfortunately, this is impossible for the goal we are trying to achieve (i.e., competing against the optimal bidding strategy, rather than the optimal fixed bid). Alternatively, one might try to relax the stochastic model a little and consider, e.g., a model where the distribution of competing bids shifts *slowly* over time. In such a model, one could make easy modifications to our algorithms to achieve nontrivial guarantees, e.g., by pretending the competing bid distribution is stationary, and restarting the algorithm from scratch every once in a while when the distribution shift becomes significant enough.\n\n[1] Zhe Feng, Swati Padmanabhan, and Di Wang. Online Bidding Algorithms for Return-on-Spend Constrained Advertisers.\n\n[2] Gagan Aggarwal, Giannis Fikioris, and Mingfei Zhao. No-regret algorithms in non-truthful auctions with budget and ROI constraints."}]

Author rebuttal:

Meta-review: This paper focuses on the design and analysis of autobidding algorithms for online first-price auctions. More specifically, the focus is on the problem of bidding repeatedly under a certain Return Over Investment constraint. This is motivated by the fact that these kinds of auctions and of constraints are common practice in online advertising auctions. The main challenge in this problem comes from the fact that the opposing bid distribution, and the distribution of the agents' value are unknown and need to be learned online. They show their algorithm can guarantee a regret upper bounded by sqrt(T) under full-information feedback and T^2/3 under bandit feedback.

All reviewers agree that the problem is interesting and the results are clean.
One main concern about this paper is about the lack of experimental results. Even if there is no previously known algorithms for the generalization considered in this paper, experimental results would have been useful (e.g., how much stronger is the stronger benchmark considered in this work with respect to previous ones? If not much, then it would have sense to compare proposed algorithms with algorithms for weaker benchmarks)

Nevertheless. mainly due to the theoretical nature of the paper, these concerns does not outweigh the pros of this paper, and thus we propose to accept this paper.
Decision: Accept (poster)