  Online advertising has recently grown into a highly competitive and complex
multi-billion-dollar industry, with advertisers bidding for ad slots at large
scales and high frequencies. This has resulted in a growing need for efficient
"auto-bidding" algorithms that determine the bids for incoming queries to
maximize advertisers' targets subject to their specified constraints. This work
explores efficient online algorithms for a single value-maximizing advertiser
under an increasingly popular constraint: Return-on-Spend (RoS). We quantify
efficiency in terms of regret relative to the optimal algorithm, which knows
all queries a priori.
  We contribute a simple online algorithm that achieves near-optimal regret in
expectation while always respecting the specified RoS constraint when the input
sequence of queries are i.i.d. samples from some distribution. We also
integrate our results with the previous work of Balseiro, Lu, and Mirrokni
[BLM20] to achieve near-optimal regret while respecting both RoS and fixed
budget constraints.
  Our algorithm follows the primal-dual framework and uses online mirror
descent (OMD) for the dual updates. However, we need to use a non-canonical
setup of OMD, and therefore the classic low-regret guarantee of OMD, which is
for the adversarial setting in online learning, no longer holds. Nonetheless,
in our case and more generally where low-regret dynamics are applied in
algorithm design, the gradients encountered by OMD can be far from adversarial
but influenced by our algorithmic choices. We exploit this key insight to show
our OMD setup achieves low regret in the realm of our algorithm.
