No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints

Advertisers are increasingly using automated bidding to optimize their ad campaigns on online advertising platforms. Autobidding allows an advertiser to optimize her objective subject to various constraints, e.g. average ROI and/or budget constraints. In this paper, we study the problem of designing online autobidding algorithms to optimize value subject to ROI and budget constraints when the platform is running a first price auction or a mixture of first and second price auctions. We consider the following stochastic setting: There is one item for sale in each of 𝑇 rounds. In each round, the buyers submit their bids and an auction is run to sell the item. We focus on the bidding problem of one buyer, possibly with budget and ROI constraints. We assume that the buyer's value and the highest competing bid are drawn i.i.d. from some unknown (joint) distribution in each round. Our goal is to design a low-regret bidding algorithm to submit per-round bids on behalf of this buyer such that the buyer's constraints are satisfied. Our benchmark is the objective value achievable by the best possible Lipschitz function that maps values to bids, which is rich enough to best respond to many different correlation structures between value and highest competing bid, e.g. positive or negative correlation. Our main result is an algorithm with full information feedback (i.e. the bidder observes the highest competing bid after each round) that guarantees a near-optimal Õ ( √ 𝑇 ) regret with respect to the best Lipschitz function that maps values to bids. Our result applies to a wide range of auctions, most notably including any mixture of first and second price auctions (where the price is a convex combination of the first and second price). In addition, our result holds for both value-maximizing buyers and quasi-linear utility-maximizing buyers. We also study the bandit setting, where the algorithm only observes whether the bidder wins the auction or not. In this setting, we show an Ω(𝑇 2/3 ) lower bound on the regret for first-price auctions, showing a large disparity between the full information and bandit settings. We also design an algorithm with a regret bound of Õ (𝑇 3/4 ), when the value distribution is known and is independent of the highest competing bid.