acceptodds
Under review as a conference paper at ICLR 2027

Optimal Online Autobidding Algorithms in First-price Auctions with ROI Constraints

Abstract

We study a value-maximizing autobidder in repeated first-price auctions under an expected return-on-investment (ROI) constraint. Values and competing bids are drawn i.i.d. from two unknown, mutually independent distributions, and the bidder observes only whether it wins. The benchmark knows the competing-bid distribution and the entire value sequence and may be randomized. We show that an optimal benchmark randomizes in at most one round. Our algorithm, UCB-DMD, combines action-adaptive confidence estimates with a consistent optimistic Lagrangian and dual update. It achieves expected regret and expected ROI violation, improving the previous expected-regret bound without requiring continuity of the competing-bid distribution. Under a fixed positive-surplus condition, a surplus-target modification of of UCB-DMD guarantees the ROI constraint is satisfied in expectation for all sufficiently large horizons with the same regret rate without any additional input for the algorithm. A joint regret and ROI violation lower bound establishes optimality of the common rate up to logarithms. The lower-bound instance also satisfies the fixed positive-surplus condition and establishes near-optimal regret among algorithms that satisfy the expected ROI constraint.

Primary area:
learning theory
Keywords:
online leading, first-price auction, auto-bidding

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_2DpLOpenReview ↗
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 O(T2/3(log⁡T)1/3)O(T^{2/3}(\log T)^{1/3}) 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
  1. 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.

  2. Terminal expected ROI feasibility under a positive-surplus condition. The surplus-target algorithm goes beyond a sublinear violation guarantee and achieves Δ≤0\Delta\le0 for sufficiently large horizons while preserving the T2/3T^{2/3}-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
  1. 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.

  2. The strongest feasibility result relies on an additional and potentially restrictive assumption. The condition κ(G,F)≥κmin⁡>0\kappa(G,F)\ge\kappa_{\min}>0 excludes ROI-boundary instances with no uniformly available positive surplus, and Δ≤0\Delta\le0 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
  1. 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

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 GG has a jump, rounding a bid down to the grid can sharply reduce its winning probability.

We partition the bid space into KK equal intervals. For interval kk, let aka_k be its upper endpoint, ck=ak−1=ak−1/Kc_k=a_{k-1}=a_k-1/K its lower endpoint, and Ut,kU_{t,k} an upper confidence bound on G(ak)G(a_k). We submit akta_{k_t} 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: g~t=(vt−ckt)Ut,kt.\widetilde g_t=(v_t-c_{k_t})U_{t,k_t}. 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.

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

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

This paper studies an autobidder in repeated first-price auctions that maximizes its total value subject to a return-on-investment (ROI) constraint while only learning whether it won each auction. The setting and the benchmark follow Li et al. (2026), who obtained O~(T3/4)\tilde O(T^{3/4}) regret under this binary feedback. The authors propose UCB-DMD. For each bid on a grid, it keeps an optimistic estimate of the winning probability, and it adjusts a Lagrange multiplier for the ROI constraint by dual mirror descent, using the same estimate in both steps. They show that regret and ROI violation are both O(T2/3(log⁡T)1/3)O(T^{2/3}(\log T)^{1/3}), that a variant satisfies the ROI constraint in expectation under a positive-surplus condition, and that no algorithm can beat the T2/3T^{2/3} rate when regret and violation are measured together. They also show that the offline benchmark needs to randomize in at most one round.

Critical strengths
  1. The paper resolves the question that Li et al. (2026) left open. Under binary feedback, the achievable rate is T2/3T^{2/3} up to a logarithmic factor, and it is matched by a lower bound that accounts for regret and ROI violation together. Measuring the two jointly is the right choice, because an algorithm that ignores the constraint can obtain high value simply by overbidding. The results hold for any competing-bid distribution, including distributions with atoms.

  2. The analysis identifies the real difficulty in replacing a fixed exploration phase with adaptive confidence bounds. The Lagrange multiplier can grow over time and would magnify any estimation error that it multiplies. Using one consistent optimistic estimate for both bid selection and the dual update keeps the estimation error out of the terms weighted by the multiplier. This idea is simple and could be reused in other constrained bandit problems. I checked the main proofs and found them correct.

Critical weaknesses
  1. The paper is very hard to understand. It reads as if it was completely generated by an LLM, and without the help of an LLM it is difficult to follow what the paper is doing and why. The results may well be correct, but in its current form the paper does not communicate them to a human reader. I strongly encourage the authors to rewrite the paper themselves in plain language that a human reader can follow.

  2. The algorithmic contribution over Li et al. (2026) is modest. The earlier algorithm already discretizes bids on a grid, uses an optimistic estimate of the competing-bid distribution, raises the submitted bid by one grid step so that discretization only affects the ROI constraint, and updates the multiplier by dual mirror descent. The main change here is to replace its fixed exploration phase with confidence bounds that are updated throughout the horizon. The improvement from T3/4T^{3/4} to T2/3T^{2/3} is what this change usually yields in one-dimensional bandit problems, and Li et al. had already pointed to an Ω(T2/3)\Omega(T^{2/3}) barrier for this setting. The paper should state clearly which components it inherits and what is new. It should also avoid wording that suggests a larger gap. For example, the abstract stresses that the result does not require a continuous competing-bid distribution, but the earlier bandit result did not require one either.

Questions for authors

None

4 comments

Thank you for your feedback.

We first classify that the paper's logic are organized by ourselves. You state that our paper is hard to understand, but do not provide any unclear paragraphs or sections. Please provide specific passages and explain what is missing or difficult to follow. We will revise them accordingly. General statements about readability or how the manuscript was produced do not explain what needs to revise.

Your review states, “The paper resolves the question that Li et al. (2026) left open.” You also recognize the difficulty of combining adaptive upper confidence bounds with a growing dual variable. However, you describe our contribution as modest compared with prior work. We disagree with this assessment for the following reasons.

First, the central algorithmic contribution is a learning framework that performs exploration and exploitation simultaneously throughout the horizon. This change allows us to improve Li et al.'s bounds for a value-maximizing bidder in first-price auctions with an ROI constraint and binary feedback.

Li et al. use an explore-then-exploit framework: they collect a predetermined number of feedback at each exploration bid and estimate the competing-bid distribution. During exploitation, they keep this estimate fixed and update the dual variable through DMD. UCB-DMD instead continues to update the winning-probability estimates while selecting bids and updating the dual variable. It collects new feedback at the bids it chooses throughout the horizon. Exploration and exploitation therefore continue together during bidding.

We must analyze the estimates and the dual variable as the algorithm updates both. Different bids receive different numbers of feedback, so their estimates have different accuracies. Multiplying an estimation error by a growing dual variable could make the error too large. A regret improvement for a bandit problem without an ROI constraint does not, by itself, prove the same bound on both regret and ROI violation here.

For a grid with KK intervals, we submit the upper endpoint ak=k/Ka_k=k/K and use the lower endpoint ak−1a_{k-1} for bid selection and the dual update. Both calculations use the same quantity g~t=(vt−ckt)Ut,kt\widetilde g_t=(v_t-c_{k_t})U_{t,k_t}, computed from the estimates available before the round. 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]}\bigl((1+\lambda)v-\lambda b\bigr)G(b).$$ Here $U_{t,k}$ is an upper confidence bound on $G(a_k)$. The estimation error is not multiplied by $\lambda_t$. Lemma 2 bounds the sum of these estimation errors over all rounds by $O(K+\sqrt{KT\log T})$. Lemma 5 bounds $\sum_t\lambda_t\widetilde g_t$ for the regret analysis and $-\sum_t\widetilde g_t$ for the ROI-violation analysis. The difference between the submitted bid $a_k$ and the lower endpoint $a_{k-1}$ adds at most $T/K$ to the ROI-violation bound. Lemma 3 provides the comparison with the optimal policy that knows $G$ and the entire value sequence before bidding, may randomize, and satisfies ROI in expectation. Combining these bounds gives $O(T^{2/3}(\log T)^{1/3})$ expected regret and expected ROI violation for our algorithm, which continues to learn while bidding. Second, the lower-bound constructions concern different constraints. The $\Omega(T^{2/3})$ lower bound cited by Li et al. (2026) comes from Aggarwal et al. (2025). Their construction considers a value-maximizing bidder with a budget constraint and no ROI constraint. We already explain this distinction in the introduction (page 2, line 61). Our construction considers value maximization under an ROI constraint and proves a lower bound on regret and ROI violation together. It shows that no algorithm can improve both worst-case bounds to less than $T^{2/3}$. Our upper bounds achieve this power, with a logarithmic factor. Finally, both our bandit guarantee and that of Li et al. allow discontinuous competing-bid distributions. We will state this clearly and organize the comparison around how the algorithms learn during bidding and what regret and ROI bounds they achieve.

Dear Reviewer JTUx,

We find that you changed your assessment of the soundness score from 1 to 3 but have not provided a response.

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

Sorry for the late reply. I have no doubts about the algorithm and the proofs of this paper, and I put soundness at 3. My concern is that the paper is hard to read. The introduction don’t makes clear why the problem matters, how it relates to earlier works, and what the authors are trying to do differently. The text also moves from one point to the next without connecting them, so I often lost track of why a sentence followed the previous one. In my view, the paper is not easy to read. A paper has to be understood before its results can be appreciated, and I think this paper needs a major revision for clarity. For these reasons, I am keeping my original overall evaluation.

Thank you for your reply. We first clarify that why the problem is important, how it relates to earlier works, and what we did differently from the previous work are all mentioned in the introduction.

The first paragraph of our introduction explicitly explains the importance of studying auto-bidding algorithms. See line 31 - line 34. " Autobidding plays a central role in online advertising: advertisers specify a value-maximization objective subject to constraints such as budgets or return on ad spend, while the platform selects bids on their behalf."

We also mentioned how it relates to earlier works. See Line 48 - Line 49. "Under bandit feedback, Li et al. (2026) achieve O(T3/4)O(T^{3/4}) regret through an explore-then-optimize approach." We also mentioned in our abstract that "It achieves O(T2/3(log⁡T)1/3)O(T^2/3(\log T)^{1/3}) expected regret and expected ROI violation, improving the previous O(T3/4)O(T^{3/4}) expected-regret bound", which shows that our work is to answer the open question left by Li et al. (2026).

In lines 57- 58, we mentioned why our method is different from others. "UCB-DMD uses this shared information consistently when selecting bids and adjusting its emphasis on ROI, rather than treating the two tasks independently." The prior work by Li et al. (2026) uses an explore-then-optimize approach, which treats the task of learning the winning probability and the task of updating the bid strategy to satisfy the ROI constraint independently.

Reviewer_fJL7OpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This is a purely theoretical paper that introduces an algorithm for ROI constrained (in expectation) auto-bidding in first price auction based on online mirror descent and optimism. It is shown to be optimal thanks to a lower bound. The paper is mostly made of statements and proof sketchs that point toward an appendix.

Critical strengths
  • I found the paper particularly well written
  • The contribution closes a gap in the theoretical literature on ROI constrained auto biding
Critical weaknesses
  • the authors could better identify what comes from the underlying literature (Balseiro...) and what is really novel in the proof techniques
  • the related work section could be better organised and better situate the different past contributions
  • the authors could have provided their insight on how they built the hard example for the lower bound

---- minor

  • assumption 1 is mentioned before being stated
Questions for authors
  • could explain how you came up with the hard example for the lower bound?
2 comments

Thank you for your thoughtful feedback. We first give a detailed comparison with prior work.

Distinction from prior work.

Our main algorithmic contribution is a framework that performs exploration and exploitation simultaneously throughout bidding. It improves expected regret from O~(T3/4)\widetilde O(T^{3/4}) to O(T2/3(log⁡T)1/3)O(T^{2/3}(\log T)^{1/3}).

Our dual update builds on the dual mirror descent (DMD) framework of Balseiro et al. However, the dual update alone does not solve our problem. We compare second-price and first-price auctions under a value-maximizer with an ROI constraint. Let G(b)G(b) denote the probability of winning with bid bb.

In a second-price auction, the winner pays the highest competing bid dtd_t. We choose a bidding policy π\pi to maximize expected total value subject to the ROI constraint:

\sup_{\pi}\quad &\mathbb E\left[\sum_{t=1}^T v_tG(b_t)\right],\\ \text{s.t.}\quad &\mathbb E\left[\sum_{t=1}^T v_tG(b_t)\right] \ge \mathbb E\left[\sum_{t=1}^T d_t\mathbf 1\\{b_t\ge d_t\\}\right]. \end{aligned}$$ Introducing a dual variable $\lambda\ge0$ for the ROI constraint gives the following dual problem: $$\inf_{\lambda\ge0}\sup_{\pi} \mathbb E\left[ \sum_{t=1}^T \bigl((1+\lambda)v_t-\lambda d_t\bigr) \mathbf 1\\{b_t\ge d_t\\} \right].$$ For a fixed $\lambda>0$, the following bid maximizes each term in the sum: $$b_t=\min\left \\{ 1,\left(1+\frac{1}{\lambda} \right)v_t \right \\}.$$ This bid wins when $(1+\lambda)v_t-\lambda d_t\ge0$ and loses when this quantity is negative. It maximizes the term for every possible competing bid, so choosing it does not require knowing $G$. When $\lambda=0$, bidding $1$ is a maximizer. The bidder can therefore choose its bid from the observed value and current dual variable, then update the dual variable using the value obtained and payment made. In a first-price auction, the winner pays its own bid $b_t$. The optimization problem becomes $$\begin{aligned} \sup_{\pi}\quad &\mathbb E\left[\sum_{t=1}^T v_tG(b_t)\right],\\ \text{s.t.}\quad &\mathbb E\left[\sum_{t=1}^T v_tG(b_t)\right] \ge \mathbb E\left[\sum_{t=1}^T b_tG(b_t)\right], \end{aligned}$$ with the corresponding dual problem $$\inf_{\lambda\ge0}\sup_{\pi} \mathbb E\left[ \sum_{t=1}^T \bigl((1+\lambda)v_t-\lambda b_t\bigr)G(b_t) \right].$$ For a given dual variable $\lambda_t$, the bid would therefore solve $$b_t\in\operatorname*{argmax}_{b\in[0,1]} \bigl((1+\lambda_t)v_t-\lambda_t b\bigr)G(b).$$ Increasing the bid changes both the winning probability and the payment upon winning. Even after $\lambda_t$ is fixed, choosing the best bid generally requires knowing $G$. The algorithm must estimate the winning probabilities from its win/loss feedbacks. Updating the dual variable alone does not provide these estimates. Li et al. (2026) address this problem through an explore-then-exploit approach. They first collect a predetermined number of feedback at each exploration bid and estimate $G$. They then keep this estimate fixed while selecting bids and updating the dual variable during exploitation. UCB-DMD continues to learn winning probabilities while choosing bids and updating the dual variable throughout the whole bidding process. It uses win/loss feedback from the bids it selects to update the estimates for later rounds. Within each round, bid selection and the dual update use the same estimates, computed from feedback collected before that round. We must bound regret and ROI violation while both the estimates and the dual variable change. Some bids receive more feedback than others, so their estimates have different accuracies. An error multiplied by a growing dual variable could become too large. In our regret bound, the estimation errors enter through the sum $$\sum_{t=1}^T v_t\bigl(U_{t,k_t}-G(a_{k_t})\bigr)$$ Each error is multiplied by the current value $v_t$, and there is no factor of $\lambda_t$. Here the bid grid has $K$ intervals, $a_k=k/K$ is a grid bid, and $U_{t,k}$ is an upper confidence bound on $G(a_k)$. When the confidence intervals contain the true winning probabilities for all bids and rounds, Lemma 2 bounds this sum by $O(K+\sqrt{KT\log T})$. The bound uses the number of feedback collected at each selected bid. The algorithm submits $a_k$ but uses the lower endpoint $a_{k-1}$ when selecting bids and updating the dual variable. This difference adds at most $T/K$ to the bound on expected ROI violation. Choosing $K$ to balance $T/K$ with the bound on the sum of estimation errors gives the improved rate. Regret is measured against the same benchmark as in Li et al.: the optimal policy that knows $G$ and the entire value sequence before bidding, may randomize its bids, and satisfies ROI in expectation.

Thank you for your thoughtful feedback. We then give the intuition for our lower-bound construction. We will add this in the next version of our paper.

Intuition for the lower-bound construction.

We construct competing-bid distributions that are difficult to distinguish from win/loss feedback but allow different expected values and different ROI.

Following the construction of Aggarwal et al. (2025), we begin with a distribution satisfying bG∘(b)=4G∘(b)−3bG_\circ(b)=4G_\circ(b)-3 at the candidate grid bids. Setting v⋆=4/13v^\star=4/13 and λ⋆=1/12\lambda^\star=1/12 gives, for every candidate grid bid bb, ((1+λ⋆)v⋆−λ⋆b)G∘(b)=14.\bigl((1+\lambda^\star)v^\star-\lambda^\star b\bigr)G_\circ(b)=\frac14. Between grid points, G∘G_\circ is constant, so increasing bb only lowers the expression above. Mixing bid zero with any of the higher grid bids so that expected payment equals expected value gives reward 1/41/4 per round. Thus, the best total expected reward under ROI is T/4T/4.

We then move the probability mass at βj+ε\beta_j+\varepsilon to βj\beta_j. The lower bid now has the same winning probability, while winning probabilities outside this interval stay unchanged. In our construction, a zero bid wins with probability 3/43/4 and pays nothing. A bid of βj\beta_j wins more often but pays more than the bidder's value when it wins. A policy that knows which interval was changed can mix these two bids so that its expected payment equals its expected value. This policy earns Θ(ε)\Theta(\varepsilon) more per round than the optimum under G∘G_\circ.

For any algorithm, at least one of the mm candidate intervals receives at most T/mT/m bids in expectation under G∘G_\circ. We change the distribution in this interval. Bids outside it give no information about the change. Each bid inside it contributes only O(ε2)O(\varepsilon^2) to the KL divergence, which measures how distinguishable the observations are under the two distributions. With the parameters chosen below, the total divergence stays small. For sufficiently large TT, the proof then shows that the algorithm makes at most T/48T/48 bids in this interval in expectation under the changed distribution.

Let MjM_j count these bids. The algorithm's total expected value satisfies

\le \frac T4+\frac{\Delta}{12} +\frac{\varepsilon}{12}\mathbb E_j[M_j],$$ where $\Delta$ is its expected total payment minus its expected total value, and $\mathbb E_j$ denotes expectation under the changed distribution. The benchmark satisfies ROI in expectation and earns at least $T/4+c\varepsilon T$ for a constant $c>0$. The inequality shows that an algorithm with too few bids in this interval must either earn less than the benchmark or allow expected payment to exceed expected value. Combining it with the bound on $\mathbb E_j[M_j]$ gives $$\operatorname{Regret}+\frac1{12}[\Delta]_+\ge\Omega(\varepsilon T).$$ Here $[\Delta]_+=\max\\{\Delta,0\\}$. With $\varepsilon\asymp1/m$, choosing $m=\Theta(T^{1/3})$ with a sufficiently large constant factor keeps $T\varepsilon^2/m$ small enough for the comparison of observations above. The last inequality then gives the $\Omega(T^{2/3})$ lower bound on regret and ROI violation together.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.