Tight Rates for Bandit First-Price Autobidding

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 $\tilde{O}(T^{2/3})$ regret bound against the optimal randomized strategy in hindsight, with a violation bound of the same order. This improves the $\tilde{O}(T^{3/4})$ 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 $\tilde{O}(T^{2/3})$ 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.