在严格投入产出比约束下，设计在线出价算法面临根本性挑战，即使数据独立同分布也无法实现次线性后悔。
Online Bidding Algorithms with Strict Return on Spend (ROS) Constraint
- 基于广告价值与中奖概率的乘积最大化，约束总支出不超过总收益
- 证明了即使在理想情况下，任何在线算法都无法避免线性后悔
- 针对恒定出价价值场景，提出对数最优的后悔上界算法
研究在严格投入产出比约束（ROSC）下的自动出价问题，即算法需根据揭示的广告价值决定出价，而分配和支付函数未知。目标是最大化所有时间槽上广告价值与中奖概率乘积的期望总和，同时要求总期望支出低于总期望收益。本文推导出一个令人惊讶的不可能性结果：即使价值、分配和支付函数从未知分布中独立同分布，任何在线算法也无法实现次线性后悔。即使在广告价值恒定的情况下，该问题仍具挑战性，并提出了一个后悔界接近最优（仅差对数因子）的算法。
原文摘要 · Abstract (English)
Auto-bidding problem under a strict return-on-spend constraint (ROSC) is considered, where an algorithm has to make decisions about how much to bid for an ad slot depending on the revealed value, and the hidden allocation and payment function that describes the probability of winning the ad-slot depending on its bid. The objective of an algorithm is to maximize the expected utility (product of ad value and probability of winning the ad slot) summed across all time slots subject to the total expected payment being less than the total expected utility, called the ROSC. A (surprising) impossibility result is derived that shows that no online algorithm can achieve a sub-linear regret even when the value, allocation and payment function are drawn i.i.d. from an unknown distribution. The problem is non-trivial even when the revealed value remains constant across time slots, and an algorithm with regret guarantee that is optimal up to logarithmic factor is derived.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。