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

We study a value-maximizing autobidder in $T$ 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 $O(T^{2/3}(\log T{)}^{1/3})$ expected regret and expected ROI violation, improving the previous $\tilde{O}(T^{3/4})$ 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.