在动态拍卖中学习最优出价,突破传统静态策略局限。
Learning to Bid in Non-Stationary Repeated First-Price Auctions
- 引入新指标量化对手出价的非平稳性,构建动态基准。
- 理论证明在非平稳环境下可实现最优动态后悔率。
- 基于乐观镜像下降算法,实测优于现有方法。
第一价格拍卖在数字广告市场中日益重要,例如谷歌从第二价格拍卖转向第一价格拍卖。与第二价格拍卖中出价等于估值为优势策略不同,第一价格拍卖中的最优出价策略更复杂。从学习视角看,投标者可通过与对手的序列交互来推断其行为。现有研究多假设特定环境条件,并以最佳固定策略(静态基准)为对比目标。然而,即使在轻微非平稳环境下,静态基准也可能严重偏离最优策略。为此,我们提出动态基准——每步可达到的最大奖励之和,更适合作为目标。但实现相对于动态基准的无后悔学习需额外约束。通过分析在线第一价格拍卖中的收益函数,我们引入两个度量来量化对手最高出价序列的规律性,作为非平稳性的衡量标准。我们给出了满足任一规律性约束的对手最高出价序列类别的最小最大最优动态后悔率。主要技术工具是带有新颖乐观配置的乐观镜像下降(OMD)框架,适用于实现此情境下的最小最大最优动态后悔率。随后使用合成数据集验证理论保证,并证明所提方法优于现有方法。
原文摘要 · Abstract (English)
First-price auctions have recently gained significant traction in digital advertising markets, exemplified by Google's transition from second-price to first-price auctions. Unlike in second-price auctions, where bidding one's private valuation is a dominant strategy, determining an optimal bidding strategy in first-price auctions is more complex. From a learning perspective, the learner (a specific bidder) can interact with the environment (other bidders, i.e., opponents) sequentially to infer their behaviors. Existing research often assumes specific environmental conditions and benchmarks performance against the best fixed policy (static benchmark). While this approach ensures strong learning guarantees, the static benchmark can deviate significantly from the optimal strategy in environments with even mild non-stationarity. To address such scenarios, a dynamic benchmark--representing the sum of the highest achievable rewards at each time step--offers a more suitable objective. However, achieving no-regret learning with respect to the dynamic benchmark requires additional constraints. By inspecting reward functions in online first-price auctions, we introduce two metrics to quantify the regularity of the sequence of opponents' highest bids, which serve as measures of non-stationarity. We provide a minimax-optimal characterization of the dynamic regret for the class of sequences of opponents' highest bids that satisfy either of these regularity constraints. Our main technical tool is the Optimistic Mirror Descent (OMD) framework with a novel optimism configuration, which is well-suited for achieving minimax-optimal dynamic regret rates in this context. We then use synthetic datasets to validate our theoretical guarantees and demonstrate that our methods outperform existing ones.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。