动态出价策略学习：出价影响未来价值，算法实现近最优后悔值。
Learning to Bid in Repeated Second-Price Auctions with Dynamic Values and Aggregated Feedback
- 基于微分方程建模最优出价策略，结合插件估计器进行在线学习。
- 对分段线性场景达到近似最优的 $ ilde{O}("log N$) 后悔，一般光滑场景为 $ ilde{O}(N^{1/3})$。
- 适用于连续时间拍卖、仅获聚合反馈的动态出价场景，适合广告竞价研究者。
我们研究投标人在动态价值下的学习出价问题，即当前价值依赖于过往结果。具体考虑一位参与连续时间重复二价拍卖的投标人，其价值随上一次成功出价以来的时间变化，且仅在周期结束时获得聚合反馈。该投标人需权衡当前竞拍收益与其对未来价值的影响，并学习未知环境参数。本文推导了一类结合插件估计与最优策略微分方程表征的学习方法的后悔界，证明特定置信度边界算法在分段线性情况下可实现近最优后悔 $ ilde{O}("log N$)，在一般光滑情形下为 $ ilde{O}(N^{1/3})$，且无需显式随机化。理论结果得到数值实验支持。
原文摘要 · Abstract (English)
We study the problem of learning to bid when the bidder's value is dynamic, i.e., when the current value depends on past outcomes. Specifically, we consider a bidder participating in repeated second-price auctions whose value depends on the time elapsed since their last successful bid, with auctions arriving in continuous time and only aggregated feedback revealed at the end of the horizon. Such a bidder must (1) balance the immediate benefit of winning the current auction against its impact on future values and (2) learn unknown environmental parameters. We derive regret bounds for a class of learning methods that combine plug-in estimators with a differential-equation characterization of the optimal policy, and show that a specific confidence bound algorithm learns the optimal policy with a near optimal regret of $\widetilde{O}(\log N)$ for piecewise linear primitives, and $\widetilde{O}(N^{1/3})$ for general, smooth primitives, achieving these regrets without explicit randomization. These theoretical results are supported by numerical experiments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。