acceptodds
Under review as a conference paper at ICLR 2027

Tight Rates for Bandit First-Price Autobidding

Abstract

Automated bidding is widely used to maximize advertising value under return-on-investment (ROI) and budget constraints. We study stochastic first-price auctions with independent values and competing bids under bandit feedback, where the bidder learns only whether it wins each auction. Under an ROI constraint alone, we first show that no algorithm can guarantee both exact expected ROI and sublinear regret. When sublinear constraint violation is allowed, however, our algorithm achieves a regret bound against the optimal randomized strategy in hindsight, with a violation bound of the same order. This improves the regret bound of Li et al. (2025) and closes the gap they left open under bandit feedback. We also construct instances that give a matching lower bound for this regret and violation guarantee. When a budget constraint is also imposed, our algorithm achieves regret and ROI violation bounds for budgets proportional to the horizon. The regret is measured against the optimal randomized strategy in hindsight subject to both constraints, and matches the known lower bound of Aggarwal et al. (2025) in this independent model. The improvement comes from continually updating optimistic estimates of win probabilities and controlling how estimation errors affect regret, without amplification by the constraint multipliers.

Primary area:
learning theory
Keywords:
online learning, autobidding, first-price auctions, bandit feedback

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_pxv2OpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper is generally understandable and has a sensible organization from the ROI-only setting to the budget extension. The distinction between candidate bids and submitted bids, and the role of the dual variables, is reasonably clear.

However, several distinctions require substantial effort to track. In particular, the paper should more clearly separate its realized cumulative ROI-violation metric from signed expected violation metrics used in related work, and should distinguish the conditional benchmark constraint from the online algorithm's overall expectation guarantee. A compact overview of the error decomposition and parameter choices would also improve readability.

Critical strengths
  1. Strong and practically meaningful constraint metric. The paper controls the expected positive part of the realized cumulative ROI deficit, E[(∑t(Pt−Rt))+],\mathbb E\left[\left(\sum_t(P_t-R_t)\right)_+\right], rather than only the positive part of an expected deficit. This is closer to campaign-level ROI risk and requires an additional martingale-transfer argument.

  2. Nontrivial ROI-budget extension. The budget version combines a second multiplier, prefix spending control, and a stopping rule to guarantee pathwise budget feasibility while retaining the O~(T2/3)\widetilde O(T^{2/3}) regret exponent for budgets proportional to the horizon. This substantially broadens the scope beyond the ROI-only setting.

Critical weaknesses
  1. The technical novelty relative to closely related work is not sufficiently isolated. UCB estimation, optimistic Lagrangian bidding, multiplicative dual updates, and upward rounding are all established ingredients. The paper should more explicitly identify which lemmas, error decompositions, and budget arguments are genuinely new, rather than extensions of an existing primal-dual bandit framework. This is particularly important given the closely related concurrent work on bandit first-price autobidding.
Questions for authors

Please provide a precise, theorem-level comparison with the closest concurrent and prior work. Which parts of the confidence analysis, dual-potential analysis, realized-violation transfer, and budget-stopping analysis are not implied by existing optimistic primal-dual bidding frameworks?

1 comment
AuthorsOpenReview ↗

Comparison with Prior Work and Technical Contributions

We thank the reviewer for the careful reading of our paper and the constructive comments.

The two works most closely related to ours are Aggarwal et al. (2025) and Li et al. (2025). We compare their settings, guarantees, and techniques with ours. Aggarwal et al. (2025) study stochastic auctions with budget and ROI constraints under both full-information and bandit feedback, allowing correlation between the bidder's valuation and the highest competing bid. Their benchmark is the best feasible mixture of Lipschitz bidding functions. Under a positive ROI feasibility margin, they combine discretization of values and bids with interval-regret learners and primal-dual updates to obtain O~(T3/4)\widetilde O(T^{3/4}) bandit regret and ROI violation. Under independence, they reuse observed competing bids across values to obtain a polynomial-time full-information algorithm with O~(T)\widetilde O(\sqrt T) regret and ROI violation. With bandit feedback, however, their O~(T3/4)\widetilde O(T^{3/4}) upper bound leaves a gap to the Ω(T2/3)\Omega(T^{2/3}) lower bound, even under independence. Focusing on ROI alone, Li et al. (2025) consider the independent stochastic model and unrestricted randomized hindsight benchmark used in our work. Their method convexifies the allocation–payment tradeoff and combines entropic primal-dual updates with an initial exploration phase, after which win-probability estimates remain fixed. This yields O~(T3/4)\widetilde O(T^{3/4}) bandit regret and signed expected ROI violation. Our work retains Li et al.'s model while updating win-probability estimates throughout bidding, achieving O~(T2/3)\widetilde O(T^{2/3}) bounds on both regret and the stronger expected positive-part realized ROI violation measure, with a matching joint lower bound (Theorems 1–2). With a hard budget and fixed β>0\beta>0, Theorem 3 attains the same rates, matching Aggarwal et al.'s regret lower bound in the independent model.

Compared with Li et al. (2025), we control the stronger measure E[(ZT)+]\mathbb E[(Z_T)_+] rather than E[ZT]\mathbb E[Z_T], where ZT=∑t(Pt−Rt)Z_T=\sum_t(P_t-R_t) is the realized ROI deficit. This prevents surplus on one run from cancelling a deficit on another. We retain their randomized hindsight benchmark, with expected feasibility conditional on the value sequence. Our budget extension additionally enforces the online budget on every run. Aggarwal et al. (2025) instead use a distributional benchmark restricted to mixtures of Lipschitz bidding functions, while ours imposes no such restriction.

We next explain the technical contributions and the key ideas that enable our improved guarantees. Li et al. (2025) analyze bandit learning through a fixed optimistic model obtained after exploration, balancing the upfront exploration cost against the error of that model over the remaining horizon. Their fixed-model comparison does not directly apply when estimates change throughout bidding. Aggarwal et al. (2025) reduce constraint control to interval-regret minimization under a positive ROI feasibility margin, which we do not assume. Our central contribution is a bound on regret and realized ROI violation that accumulates statistical error only at submitted bids, without amplification by the constraint multipliers. This comparison remains valid as the optimistic estimates change and uses the same unrestricted hindsight benchmark throughout learning. The key is to separate predicted value and ROI surplus from the Lagrangian score before accounting for estimation error. This allows rarely used bids to remain uncertain while controlling both value loss and the expected positive part of realized ROI deficit, yielding the optimal joint O~(T2/3)\widetilde O(T^{2/3}) rate in the ROI-only setting (Appendices A.2–A.4). Handling a hard budget requires a second contribution. The weighted budget and ROI surpluses can offset each other in the bidding score, so the ROI-only multiplier bound does not control them separately. We establish a joint potential bound that controls both predicted deficits at every prefix without a positive feasibility margin (Lemma 1, Appendix C.1). This provides the spending guarantee needed at the random budget stopping time and bounds the value lost to early stopping. It makes hard-budget feasibility compatible with the O~(T2/3)\widetilde O(T^{2/3}) regret and realized ROI-violation rates for budgets proportional to the horizon (Appendix C.2).

Reviewer_3stROpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The article presents a model and algorithm for first price autobidding, where bidders have an ROI constraint, and sometimes a budget constraint. The algorithm is shown to be order optimal in several senses.

Critical strengths

The results are largely complete - matching upper and lower bounds on various metrics that are considered important

Critical weaknesses

My key complaint is that I do not believe in the model. You assume that the valuations and the competitor bids are independent. This is just not plausible. Furthermore, your algorithm chooses to make bids dependent on the valuation, further undermining the modelling assumption.

The literature review lists other articles, but does not provide a good sense of what is the same or different between your approach and the prior work. In particular, which of the other articles also assume independent bids and valuations, and which do not?

The writing is also distinctly unclear. Many of the concepts are not well defined, or are reported in the main text without explanation but only defined in the appendix.

Due to these failings I have not carefully checked the proofs - even if they are correct, the article is not ready for publication in ICLR in my opinion

Questions for authors
  1. Please justify the independence of valuations and bids, both as a modelling assumption, and in terms of what is assumed in related literature.

  2. Please give an indication of the relationship between your work and the other articles in the literature review.

  3. In line 222, why is it reasonable to assume that F(1)=1?

  4. In line 230, you take a constant L_t throughout the algorithm. I would have expected this term to increase through the algorithm (ie depend on t instead of T). Why the fixed term?

  5. Please provide some motivation for the different components in the algorithm, in particular around equation (9). The ROI multiplier just appears, for example.

  6. I think I've understood this right, but if I have then it's a bit incongruous. (9) always selects actions at the left hand side of a bid interval. But the bid that is submitted is always at the right hand side of the interval, and q_t is the estimate at the right hand side too. Wouldn't things be much simpler if q_t and \tilde{b}_t corresponded to the same bid, the one that is actually submitted?

  7. Is (12) the definition of D_F etc? That's far from clear from the writing

  8. Both sentences following (12) are far from clear. I think they're referencing results from the Appendix. We need to know why to believe the statements when we read them though.

  9. Lines 306-308, what is referred to by "coefficients" here?

  10. Lines 309-310, what are "selected score", "multiplier", and why does the multiplier bound the summation, and in which direction?!

  11. Line 317, why does summing the confidence widths provide this bound?

  12. Overall, the description following Theorem 1 is uninformative, it gives just enough information so that not enough is defined, but not enough information to be able to follow the derivation.

  13. Line 345. Does "This interval" refer to the region where mass is going to be moved around, or to the grid interval?

  14. Line 367. Where is a two-point competing bid distribution defined?

  15. Line 426. Why is predicted spending at most beta*s+\sum...?

7 comments
AuthorsOpenReview ↗

Response to the key concerns

We thank the reviewer for the careful reading of our paper and the constructive feedback.

Question 1. Our independence assumption is standard in stochastic auction learning. We directly follow the stochastic model of Li et al. (2025), without adding assumptions, and resolve their open question on the optimal bandit regret–violation rate. The same independence condition is used by Han et al. (2024), Wang et al. (2023), and Achddou et al. (2021). In each round, the bidder first observes its own value vtv_t and then submits a bid btb_t. Let dtd_t denote the highest bid submitted by the other bidders. In a first-price auction, the bidder wins if bt≥dtb_t\ge d_t and pays its own bid btb_t upon winning. Our independence assumption merely requires the bidder's value vtv_t to be independent of the highest competing bid dtd_t. This condition follows directly from the classical independent-private-values (IPV) framework when competitors bid as fixed functions of their own values (Vickrey, 1961; Riley and Samuelson, 1981; Krishna, 2009). Under IPV, bidders' private values are mutually independent. If competitor jj bids βj(vj,t)\beta_j(v_{j,t}), then the competing bid dt=max⁡j≠iβj(vj,t)d_t=\max_{j\ne i}\beta_j(v_{j,t}) depends only on competitors' values, which are independent of our own value vt=vi,tv_t=v_{i,t}. Our independence condition is therefore weaker than this IPV setting. Our algorithm follows the same process by observing the value vtv_t and then choosing a bid btb_t using estimated win probabilities to balance value and ROI. Having our bid depend on the observed value is therefore fully consistent with independence between the bidder's value vtv_t and the competing bid dtd_t. The model also has a natural economic interpretation in advertising. An impression may be especially valuable to one advertiser because a user is interested in its product or brand, without increasing competitors' willingness to pay. Balseiro et al. (2015) model independent advertiser matches and private values, while Bergemann et al. (2021) show how independent private values can arise from models of viewer attributes and advertiser preferences. These models motivate independence when advertiser-specific matching drives value variation.

Question 2. Among the cited works on learning in first-price auctions, Han et al. (2024), Wang et al. (2023), and Li et al. (2025) assume independent valuations and competing bids. Han et al. (2020) allow adversarial sequences, while Aggarwal et al. (2025) allow correlation in their general stochastic model. Han et al. (2024) and Wang et al. study utility maximization with richer feedback. Our work belongs to the line of ROI-constrained value maximization. In this line, Feng et al. (2023) study truthful auctions, and Castiglioni et al. (2024) handle nontruthful auctions with finite value and bid spaces. Aggarwal et al. (2025) study continuous spaces with ROI and budget constraints, competing against mixtures of Lipschitz bidding functions and obtaining O~(T3/4)\widetilde O(T^{3/4}) bandit regret. Li et al. (2025) address ROI-only first-price auctions in the independent model, extending the benchmark to unrestricted randomized strategies in hindsight, again with a O~(T3/4)\widetilde O(T^{3/4}) bandit rate. Our work directly builds on Li et al.'s setting. Under the same model, feedback, and benchmark, we improve both regret and ROI violation to O~(T2/3)\widetilde O(T^{2/3}), with a stronger expected positive-part violation measure. Together with our matching joint lower bound for the ROI-only setting, this resolves their open question on the optimal bandit regret–violation rate. With an additional budget constraint, we also close the regret-rate gap left by Aggarwal et al. in the independent setting for budgets proportional to the horizon. Our budget result also holds against unrestricted randomized bidding rules and matches their Ω(T2/3)\Omega(T^{2/3}) regret lower bound. Technically, we build on the primal-dual approach of prior autobidding work. Li et al.'s bandit algorithm estimates win probabilities during initial exploration and keeps them fixed thereafter. We instead update optimistic estimates throughout bidding, allowing us to control cumulative estimation error at the bids actually submitted. Frequently chosen bids become more accurate, while rarely chosen bids contribute little error. Our analysis first bounds predicted value and ROI surplus, then transfers these guarantees to realized outcomes, so estimation errors enter without a multiplier factor. We will revise the related-work discussion to make these connections explicit.

AuthorsOpenReview ↗

Response to Questions 4–6 — Algorithm design and parameters

Question 4. This is a natural concern, since standard UCB confidence radii often use a logarithmic factor that grows with tt. With a known horizon TT, we can use a uniform upper bound, Lt≤LTL_t\le L_T for all t≤Tt\le T. For the same number of observations, this only enlarges the confidence radius. Hoeffding's inequality and a union bound over grid bids and sample counts ensure that, with probability at least 1−δ1-\delta, all confidence intervals contain their corresponding true win probabilities throughout the run. The upper estimates therefore never underestimate the true win probabilities on this event. Meanwhile, the radii still shrink as more observations are collected, even though LTL_T is fixed.

Question 5. Our algorithm scores candidate bids using optimistic estimates, chooses the highest-scoring candidate through (9), and submits its rounded bid. Higher bids can improve the chance of winning but increase payment, so the score balances value maximization and ROI, as outlined in the technique overview (lines 74–77). Specifically, the score is vtQt(b~t)+λt(vt−b~t)Qt(b~t)v_tQ_t(\tilde b_t)+\lambda_t(v_t-\tilde b_t)Q_t(\tilde b_t), where Qt(b~t)Q_t(\tilde b_t) estimates the win probability at the submitted bid btb_t associated with candidate b~t\tilde b_t and λt\lambda_t weights predicted ROI surplus. ROI is cumulative, so bids above value are allowed if their deficits are offset elsewhere. After each auction, win/loss feedback updates the empirical win rate and sample count at the submitted grid bid (lines 268–269). We use these updated statistics to obtain the next round's optimistic win-probability estimates Qt+1Q_{t+1}. The ROI multiplier is updated from predicted surplus using (10), increasing after a predicted deficit and decreasing after a predicted surplus. These updates, together with the next observed value, determine the next round's scores.

Question 6. The candidate price b~t\tilde b_t is used for scoring, while the submitted bid bt=σ(b~t)b_t=\sigma(\tilde b_t) is the interval's right endpoint and is paid upon winning. We learn win probabilities only at submitted bids. The score is vtqt+λt(vt−b~t)qtv_tq_t+\lambda_t(v_t-\tilde b_t)q_t, where qtq_t estimates the win probability at btb_t. We use the lower candidate price so that the extra payment imposed by the grid does not discourage wins available to the continuous benchmark. For example, let vt=0.45v_t=0.45 and fix the highest competing bid at 0.450.45. Knowing this distribution, the benchmark bids 0.450.45 and wins with zero ROI surplus. Our grid with spacing 0.10.1 does not contain 0.450.45, so the smallest available winning bid is 0.50.5. If we evaluate both win probability and payment at 0.50.5, as suggested, the score is 0.45−0.05λt0.45-0.05\lambda_t, since this bid wins with certainty and qt=1q_t=1. This penalizes the winning bid simply because it was rounded up. We still submit bt=0.5b_t=0.5 and use the same qtq_t, but evaluate ROI surplus at candidate b~t=0.4\tilde b_t=0.4, giving score 0.45+0.05λt0.45+0.05\lambda_t. This correction keeps the higher winning bid attractive, helping the algorithm retain the value achieved by the continuous benchmark. We use the same candidate price in the multiplier update and account for the extra payment in our ROI violation bound.

AuthorsOpenReview ↗

Response to Questions 7–12 — Theorem 1 proof overview

We apologize for the compressed proof overview. Here we explain the intuition behind the proof of Theorem 1 in the following four steps.

1. Upper-bound the benchmark's expected value (Questions 7–8). Equation (12) indeed defines the quantities used to bound the benchmark's expected value. We will label it explicitly as a definition. Here FF is the CDF of the highest competing bid, known to the benchmark. The score vF(b)+λ(v−b)F(b)vF(b)+\lambda(v-b)F(b) combines expected value and weighted ROI surplus. Maximizing over bids gives fF(v,λ)f_F(v,\lambda), and averaging over values gives DF(λ)D_F(\lambda). For any feasible benchmark strategy with bids btb_t and λ≥0\lambda\ge0,

\le \mathbb E\!\left[\sum_t\bigl(v_tF(b_t)+\lambda(v_t-b_t)F(b_t)\bigr)\right] \le TD_F(\lambda).$$ Expectations are over the value sequence and the benchmark's randomized bids, with competing-bid randomness already averaged through $F$. The first inequality holds because expected total ROI surplus is nonnegative and $\lambda\ge0$. The second follows by maximizing the score in each round and averaging over values, as in $f_F$ and $D_F$. We then take the tightest upper bound $TD_F^\star$, giving $\mathbb E[\mathrm{OPT}]\le TD_F^\star$ (lines 302–304). **2. Compare the algorithm's score with this upper bound (Question 9).** We next seek a lower bound on the algorithm's expected cumulative score using the benchmark bound above. The “coefficient” in $f_F(v,\lambda)$ is $(1+\lambda)v-\lambda b$, multiplying $F(b)$. The score in (9) uses this same coefficient with $Q_t(b)$ in place of $F(b)$. We show that this replacement does not decrease the maximum score over bids. By construction of $Q_t$ (lines 236–244), $Q_t(b)\ge F(b)$ with high probability. The comparison is immediate for nonnegative coefficients. Negative coefficients give nonpositive true scores, dominated by candidate zero's nonnegative estimated score (lines 305–308). This keeps promising bids from being undervalued and provides a guarantee on the algorithm's expected cumulative score. Specifically, we obtain the lower bound $TD_F^\star-1/T$. Details are in Appendix A.3. **3. Recover predicted value from the score (Question 10).** The “selected score” is the score of the candidate bid chosen in (9). Using the quantities defined in (10), it is $r_t^Q+\lambda_tg_t^Q$, where $r_t^Q$ is predicted value, $g_t^Q$ is predicted ROI surplus, and the “multiplier” $\lambda_t$ weights this surplus, as outlined in the technique overview (lines 74–77). The previous step lower-bounds the expected cumulative score, $\mathbb E\sum_t r_t^Q+\mathbb E\sum_t\lambda_tg_t^Q$, relative to the benchmark's expected value. We therefore need to bound the second term from above so that the first cannot fall far below the benchmark. The update in (10) lowers $\lambda_t$ after a predicted surplus and raises it after a predicted deficit. Analyzing this update over all rounds gives an $O(T^{2/3})$ upper bound on the second term. The detailed calculation is given in Appendix A.3, equation (24). Subtracting it from the score bound yields $\mathbb E[\sum_t r_t^Q]\ge\mathbb E[\mathrm{OPT}]-O(T^{2/3})$, giving the desired guarantee on cumulative predicted value. The same update also controls predicted ROI deficit. **4. Transfer to actual outcomes (Questions 11–12).** The previous step controls predicted value $r_t^Q=v_tq_t$, where $q_t$ estimates the win probability at the submitted bid $b_t$, while the conditional expected value actually earned is $v_tF(b_t)$. We therefore need to bound the sum of the probability estimation errors $e_t=|q_t-F(b_t)|$ to turn the guarantee on predicted value into a regret bound. As explained in the technique overview (lines 79–82), frequently submitted bids have increasingly accurate estimates, while rarely submitted bids contribute little to the total error. Recall that $Q_t$ uses upper bounds from confidence intervals around empirical win rates. With high probability, both the true win probability $F(b_t)$ and its upper estimate $q_t$ lie in the corresponding confidence interval. Their difference $e_t$ is therefore bounded by the interval’s width. Summing these confidence widths over all rounds gives $\mathbb E[\sum_t e_t]=\widetilde O(T^{2/3})$. The detailed calculation is given in Appendix A.2, equation (20). This lets us transfer the guarantees on predicted value and ROI surplus to actual outcomes. Combining the losses from Steps 2, 3, and 4, we obtain $\mathrm{Reg}_T\le 1/T+O(T^{2/3})+\widetilde O(T^{2/3})=\widetilde O(T^{2/3})$. Applying the analogous transfer to the predicted ROI deficit bound gives $\mathrm{Viol}_T=\widetilde O(T^{2/3})$ (Appendix A.4, (28)–(31)).
Reviewer_yJsUOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies constrained autobidding in repeated first-price auctions where values and competing bids are drawn independently from unknown distributions and feedback is bandit (only the win/loss bit is observed). The goal is to maximize total value subject to an ROI constraint and, optionally, a budget constraint, measured against a randomized hindsight benchmark that knows the competing-bid distribution and the realized value sequence. Main results: • With an ROI constraint alone, the proposed algorithm keeps learning win probabilities throughout bidding and achieves O~(T^{2/3}) regret with constraint violation of the same order, improving the O~(T^{3/4}) bound of Li et al. (2025) and matching the minimax lower bound; • Proposition 1 shows that requiring the ROI constraint to hold exactly in expectation forces linear regret, so allowing sublinear violation is necessary; Theorem 2 gives a matching Omega(T^{2/3}) lower bound on max{regret, ROI violation}; • With an additional budget B = beta*T, Theorem 3 gives O~(T^{2/3}/beta) regret and O~(T^{2/3}) ROI violation while never exceeding the budget on any sample path; Corollary 1 extends this to a distributional benchmark. The work is purely theoretical: theorem proofs and lower-bound constructions, with no experiments.

Critical strengths

(1)The paper cleanly resolves an explicitly open rate question, providing upper bounds in both the ROI-only and the budget setting together with matching lower bounds. The conclusions are crisp and checkable, and they directly advance the line of work they build on. This is the main reason I lean toward acceptance. (2) The technique is transferable. Replacing "fixed exploration then fixed estimates" with anytime learning plus cumulative-error control at the submitted bids, and keeping the multiplier from amplifying estimation error, should apply to other bandit problems with long-term constraints. Retaining the same rate under a stronger violation measure makes the result more credible.

Critical weaknesses

(1) The contribution primarily lies in improving the regret rate within an established framework rather than introducing a new formulation. While the combination of techniques and matching bounds is nontrivial, most individual components have precedents in constrained-bandit literature. Moreover, the analysis relies on restrictive assumptions, including i.i.d. values, independence from competing bids, and a single-slot, context-free setting. Discussing which assumptions are essential and how the results might extend to realistic autobidding scenarios would strengthen the paper. (2) The guarantees degrade as the budget tightens, and this regime is not discussed. Theorem 3 holds for every beta in (0,1] with an explicit 1/beta factor in the regret, and is tight for constant beta, but the paper does not examine what that factor implies when beta decays with T - a regime closer to real campaigns. This is not a purely asymptotic concern: since regret is trivially at most T, the stated bound carries no information once beta is of order T^{-1/3} or smaller, and the paper does not mark where its guarantee stops being informative. Whether the factor is intrinsic or an artifact of the stopping analysis determines how the result should be read for tight budgets, and the paper does not say.

Questions for authors

• Is the 1/beta factor in Theorem 3 intrinsic or an artifact of the stopping analysis? Concretely, can the authors say which lemma produces it and whether a bound with a weaker dependence is attainable when beta = beta(T) tends to zero? If the factor is shown to be necessary, that would also settle how the result should be read for tight budgets. • Which steps of the proof use independence between values and competing bids? If the two may be correlated as in Aggarwal et al. (2025), which of the ROI-only and budget results survive and which fail? A pointer to the specific lemmas would let readers judge the reach of the results.

1 comment
AuthorsOpenReview ↗

Response to Questions

We thank the reviewer for the constructive feedback and for highlighting the possible extensions.

Question 1. Lemma 1 in Appendix C.1 analyzes the unstopped algorithm, which allows budget violation. The algorithm achieves O~(T2/3)\widetilde O(T^{2/3}) regret, ROI violation, and budget violation, with constants independent of β\beta. A key point is that its budget multiplier regulates spending toward an average rate of β\beta per round. In Theorem 3, we enforce the budget by switching permanently to zero bids once less than one unit remains. At an early stop, the allowance for the remaining rounds is at most the excess spending plus this remaining balance. Dividing by the allowance of β\beta per round therefore gives O~(T2/3/β)\widetilde O(T^{2/3}/\beta) expected remaining rounds. Each can lose at most one unit of value, so adding the loss from stopping to the learning error during active bidding gives

\le \widetilde O(T^{2/3})+\widetilde O(T^{2/3}/\beta) =\widetilde O(T^{2/3}/\beta).$$ The factor $1/\beta$ thus arises from converting excess spending into remaining rounds, as shown in Appendix C.2, (66)–(67), and the main text (lines 452–465). The bound remains valid for $\beta=\beta(T)$, but no longer guarantees sublinear regret once $\beta$ is of order $T^{-1/3}$ or smaller. A key difficulty in obtaining a weaker dependence on $\beta$ comes from discretization error. Suppose we discretize the continuous bid space into $K$ equally spaced points. Consider $v_t=1$ and a deterministic competing bid $d_t=\beta$ between grid points. The benchmark bids $\beta$ and wins every round. If the smallest winning grid bid is $\beta+\varepsilon$, the budget $B=\beta T$ supports at most $B/(\beta+\varepsilon)$ wins for our algorithm, giving regret at least $T\varepsilon/(\beta+\varepsilon)$. Rounding raises the minimum payment per win from $\beta$ to $\beta+\varepsilon$. If $\varepsilon\ll\beta$, the resulting regret lower bound is approximately $T\varepsilon/\beta$, or $T/(K\beta)$ when $\varepsilon\asymp1/K$. If $\varepsilon=\beta$, each win costs twice as much, so the same budget buys at most $T/2$ wins and regret is at least $T/2$. More generally, when the rounding error is comparable to or larger than $\beta$, the algorithm loses a constant fraction of the benchmark's $T$ wins, giving linear regret. This loss persists even with perfect knowledge of the distribution because the available bids are still restricted to the grid. The example shows that sublinear loss from rounding requires $\varepsilon\ll\beta$. Our grid spacing of order $T^{-1/3}$ satisfies this condition for fixed $\beta>0$. Thus, for budgets proportional to the horizon, our algorithm achieves $\widetilde O(T^{2/3})$ regret and ROI violation bounds. The regret rate matches the known lower bound of Aggarwal et al. (2025) in this independent model. For tighter budgets, improving the dependence may require new algorithmic ideas, while establishing its necessity would require a matching lower bound. We will discuss these directions in the future work section. **Question 2.** Independence supports learning the win probabilities used in the score (9). It allows feedback to be shared across values, yielding the confidence and cumulative error bounds in Appendix A.2, (18)–(20). It also identifies $F(b_t)$ as the conditional win probability after observing $v_t$ and selecting $b_t$ (Appendix A.4, (27)–(29), and Appendix C.1, (60)–(61)). With correlation, this becomes $F(b_t\mid v_t)$. Extending these steps requires conditional upper estimates $Q_t(b\mid v_t)$ with the same simultaneous confidence guarantee and $\widetilde O(T^{2/3})$ cumulative error at submitted bids. Learning the additional value dimension requires a new statistical analysis, so the current upper bounds do not automatically extend to arbitrary correlation. Bid selection, multiplier updates, and their pathwise bounds do not themselves require independence. They use bounded predicted outcomes and a nonnegative selected score (Appendix A.3, (24)–(25), and Appendix C.1, (55)–(57)). Given the conditional estimates above in $[0,1]$ and i.i.d. pairs across rounds, the benchmark comparison, outcome transfer, and stopping analysis can be adapted using conditional win probabilities (Appendices A.1, A.3–A.4, and C.2, (64)–(67)). This would recover Theorem 1 and Lemma 1, and Theorem 3. Hard-budget feasibility remains valid regardless of correlation, as do the lower bounds in Theorem 2, Proposition 1, and Appendix C.4, whose hard instances have constant values. Aggarwal et al. (2025) allow correlation but compare against mixtures of Lipschitz bidding functions, so their guarantees do not directly cover our unrestricted randomized hindsight benchmark.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.