- Rating
- 2
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies online bidding in repeated stochastic first-price auctions with unknown i.i.d. values and competing bids under binary win/loss feedback. The bidder observes the current value before bidding and aims to maximize total value subject to an expected ROI constraint.
The paper first characterizes the randomized hindsight benchmark, showing that an optimal policy needs to randomize in at most one round. It then proposes UCB-DMD, which combines action-adaptive confidence bounds for grid bids with an optimistic Lagrangian and a multiplicative dual update. The paper proves expected regret and ROI-violation bounds without assuming continuity of the competing-bid distribution. Under a fixed positive-surplus condition, a surplus-target variant achieves expected ROI feasibility for sufficiently large horizons while preserving the same regret order. A joint regret/violation lower bound is also provided. The work is theoretical and does not include empirical evaluation.
Critical strengths
-
A clear structural characterization of the hindsight benchmark. The linear-program formulation with one aggregate ROI constraint explains why an optimal randomized policy needs to mix bids in at most one round. This provides a useful understanding of the benchmark rather than treating it as a black box.
-
Terminal expected ROI feasibility under a positive-surplus condition. The surplus-target algorithm goes beyond a sublinear violation guarantee and achieves for sufficiently large horizons while preserving the -scale regret. The proof connects the feasibility result to a controlled terminal dual multiplier and gives a meaningful boundary between general impossibility and feasible positive-surplus instances.
Critical weaknesses
-
The independent technical novelty relative to closely related work is not sufficiently isolated. UCB estimation, optimistic Lagrangian bidding, multiplicative dual updates, continuous win-probability learning, and bid rounding are shared with closely related bandit autobidding frameworks. The paper should clarify which parts of the one-round randomization theorem, virtual-price analysis, surplus-target feasibility proof, and positive-surplus lower bound cannot be obtained from existing techniques by a direct adaptation.
-
The strongest feasibility result relies on an additional and potentially restrictive assumption. The condition excludes ROI-boundary instances with no uniformly available positive surplus, and is only an expected guarantee, not sample-path ROI safety. The paper should discuss the necessity and practical scope of this assumption more fully. The absence of empirical evaluation also makes it difficult to assess how the surplus target behaves across different surplus margins and horizons.
Questions for authors
- Please provide a theorem-level comparison with the closest prior and concurrent first-price bandit autobidding work. In particular, which parts of the virtual-price analysis and the consistency between the optimistic score and dual update are genuinely new?
2 comments
Dear Reviewer 2DpL,
We are wondering if our response has resolved your concerns. If our response has addressed your concerns, we would highly appreciate it if you could re-evaluate our work and consider raising the score.
If you have any additional questions or suggestions, we would be happy to have further discussions.
Best regards,
The Authors
Thank you for your thoughtful feedback. We answer your questions one by one.
Distinction from prior work.
The main algorithmic contribution is a change from an explore-then-exploit framework to simultaneous exploration and exploitation. Li et al. first collect a fixed number of feedback at each exploration bid and then keep the resulting winning-probability estimates fixed during exploitation. UCB-DMD updates these estimates and the dual variable throughout the horizon. It uses the current value, estimates, and dual variable to choose a bid, then uses the win/loss feedback to update the estimate for later rounds.
The estimates come from bids chosen using earlier estimates and dual variables. The analysis must account for this dependence. Multiplying an estimation error by a growing dual variable could make the error too large. Also, when G has a jump, rounding a bid down to the grid can sharply reduce its winning probability.
We partition the bid space into K equal intervals. For interval k, let ak be its upper endpoint, ck=ak−1=ak−1/K its lower endpoint, and Ut,k an upper confidence bound on G(ak). We submit akt and use the feedback to update the estimate for later rounds. To select the bid and update the dual variable, we use the same quantity, calculated from the lower endpoint and the estimate available before the round: gt=(vt−ckt)Ut,kt. When all confidence intervals contain the true winning probabilities, Lemma 4 gives
\ge h_G(v_t,\lambda_t)-\lambda_t\widetilde g_t -v_t\bigl(U_{t,k_t}-G(a_{k_t})\bigr),$$ where $h_G(v,\lambda)=\sup_{b\in[0,1]}((1+\lambda)v-\lambda b)G(b)$. The estimation error is not multiplied by the dual variable. Lemma 2 bounds the sum of these errors over all rounds: $$\sum_{t=1}^T v_t\bigl(U_{t,k_t}-G(a_{k_t})\bigr) \le W_T:=K+2\sqrt{2KTL}.$$ Here $L=\log(2T^4)$, as in Theorem 2. Lemma 5 bounds $\sum_t\lambda_t\widetilde g_t$ in the regret analysis and $-\sum_t\widetilde g_t$ in the ROI-violation analysis. Using the upper endpoint as the submitted bid adds at most $T/K$ to the ROI-violation bound. Lemma 3 provides the comparison with the benchmark. Combining these bounds gives Theorem 2 and Proposition 1 for the estimates and bids produced by our algorithm. Li et al.(2026) gives $\widetilde O(T^{3/4})$ expected regret. Regret is measured against an optimal policy that knows $G$ and the entire value sequence before bidding. Our Theorem 2 and Proposition 1 improve bounds to $O(T^{2/3}(\log T)^{1/3})$ under the same binary feedback and benchmark. Theorem 4 shows that, for every algorithm, some instance has regret or expected ROI violation of order at least $T^{2/3}$. Thus, we close the gap left by Li et al. (2026) up to a log factor. **The positive-surplus assumption.** Previous work also uses positive-surplus assumptions to satisfy ROI/RoS constraints without violation, as discussed in Remark 2 of our paper. In particular, Feng et al. (2023) require the expected value minus payment from truthful bidding to be at least a fixed positive constant that does not depend on $T$. In a second-price auction, bidding one's value gives value minus payment equal to $(v-d)_+$. Their condition therefore uses the same quantity $\mathbb E[(v-d)_+]$ as our Assumption 1. We use this condition in first-price auctions, where the winner pays its own bid. Under this condition, Theorem 3 shows that, for all sufficiently large $T$, the expected total payment over the $T$ rounds is no greater than the expected total value, meaning that our algorithm ensures no ROI violation in expectation.