- 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
-
Strong and practically meaningful constraint metric. The paper controls the expected positive part of the realized cumulative ROI deficit, 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.
-
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 regret exponent for budgets proportional to the horizon. This substantially broadens the scope beyond the ROI-only setting.
Critical weaknesses
- 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?
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) 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) regret and ROI violation. With bandit feedback, however, their O(T3/4) upper bound leaves a gap to the Ω(T2/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) 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) 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, 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)+] rather than E[ZT], where ZT=∑t(Pt−Rt) 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) 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) regret and realized ROI-violation rates for budgets proportional to the horizon (Appendix C.2).