论文标题
具有预算的广告活动的最佳支出利率估算和节奏
Optimal Spend Rate Estimation and Pacing for Ad Campaigns with Budgets
论文作者
论文摘要
在线广告平台为广告商提供预算管理工具，旨在最大程度地提高预算限制的转换次数。随着印象的数量，转换率和价格随着时间的流逝而变化，这些预算管理系统将学习一个支出计划（随着时间的推移找到预算的最佳分配），并运行遵循支出计划的起搏算法。 本文考虑了两种随时间变化的印象和竞争模型：a）一个情节模型，在每个情节中都表现出平稳性，但是每个情节都可以与下一个插曲有任意的不同，b）价格和价值的分布随时间缓慢变化。我们介绍了第一个学习理论保证支出计划的准确性和由此产生的端到端预算管理系统。我们提出四个主要结果：1）对于情节设置，我们为支出速率预测问题提供了样本复杂性界限：给定每个情节中的$ n $样本，具有较高的概率，我们有$ | \widehatρ_e-ρ_e| \leq \tilde{O}(\frac{1}{n^{1/3}})$ where $ρ_e$ is the optimal spend rate for the episode, $\widehatρ_e$ is the estimate from our algorithm, 2) we extend the algorithm of Balseiro and Gur (2017) to operate on varying, approximate spend rates and show that the resulting为情节设置的最佳支出估计和在线起搏算法组合的组合系统令人遗憾的是，历史样本的数量消失了$ n $ $ n $的数量以及$ n $ $ t $，3）的数量，3 $，3））对于非剧本但缓慢变化的分布，我们表明，我们显示的方法相同的方法近似于依赖速度和依赖的速度差异，我们可以依赖于速度的分配和4个，而我们依赖于汇率的范围，而我们的分配却是4个，而我们的分配却是4个范围的4. 4）在各种环境中都胜过静态支出计划，也不是不挑选的。
Online ad platforms offer budget management tools for advertisers that aim to maximize the number of conversions given a budget constraint. As the volume of impressions, conversion rates and prices vary over time, these budget management systems learn a spend plan (to find the optimal distribution of budget over time) and run a pacing algorithm which follows the spend plan. This paper considers two models for impressions and competition that varies with time: a) an episodic model which exhibits stationarity in each episode, but each episode can be arbitrarily different from the next, and b) a model where the distributions of prices and values change slowly over time. We present the first learning theoretic guarantees on both the accuracy of spend plans and the resulting end-to-end budget management system. We present four main results: 1) for the episodic setting we give sample complexity bounds for the spend rate prediction problem: given $n$ samples from each episode, with high probability we have $|\widehatρ_e - ρ_e| \leq \tilde{O}(\frac{1}{n^{1/3}})$ where $ρ_e$ is the optimal spend rate for the episode, $\widehatρ_e$ is the estimate from our algorithm, 2) we extend the algorithm of Balseiro and Gur (2017) to operate on varying, approximate spend rates and show that the resulting combined system of optimal spend rate estimation and online pacing algorithm for episodic settings has regret that vanishes in number of historic samples $n$ and the number of rounds $T$, 3) for non-episodic but slowly-changing distributions we show that the same approach approximates the optimal bidding strategy up to a factor dependent on the rate-of-change of the distributions and 4) we provide experiments showing that our algorithm outperforms both static spend plans and non-pacing across a wide variety of settings.
