No-Regret Algorithms in non-Truthful Auctions with Budget and ROI
  Constraints
Gagan Aggarwal Giannis Fikioris Mingfei Zhao
Advertisers increasingly use automated bidding to optimize their ad campaigns
on online advertising platforms. Autobidding optimizes an advertiser's
objective subject to various constraints, e.g. average ROI and 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 any mixture of first and second price auction.
  We consider the following stochastic setting: There is an item for sale in
each of $T$ rounds. In each round, buyers submit bids and an auction is run to
sell the item. We focus on 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. We design a low-regret
bidding algorithm that satisfies the buyer's constraints. 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. Our main result
is an algorithm with full information feedback that guarantees a near-optimal
$\tilde O(\sqrt T)$ regret with respect to the best Lipschitz function. Our
result applies to a wide range of auctions, most notably any mixture of first
and second price auctions (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 we show an $\Omega(T^{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
$\tilde O(T^{3/4})$ regret, when the value distribution is known and is
independent of the highest competing bid.