  Today's online advertisers procure digital ad impressions through interacting
with autobidding platforms: advertisers convey high level procurement goals via
setting levers such as budget, target return-on-investment, max cost per click,
etc.. Then ads platforms subsequently procure impressions on advertisers'
behalf, and report final procurement conversions (e.g. click) to advertisers.
In practice, advertisers may receive minimal information on platforms'
procurement details, and procurement outcomes are subject to non-stationary
factors like seasonal patterns, occasional system corruptions, and market
trends which make it difficult for advertisers to optimize lever decisions
effectively. Motivated by this, we present an online learning framework that
helps advertisers dynamically optimize ad platform lever decisions while
subject to general long-term constraints in a realistic bandit feedback
environment with non-stationary procurement outcomes. In particular, we
introduce a primal-dual algorithm for online decision making with
multi-dimension decision variables, bandit feedback and long-term uncertain
constraints. We show that our algorithm achieves low regret in many worlds when
procurement outcomes are generated through procedures that are stochastic,
adversarial, adversarially corrupted, periodic, and ergodic, respectively,
without having to know which procedure is the ground truth. Finally, we
emphasize that our proposed algorithm and theoretical results extend beyond the
applications of online advertising.
