王畅-No-regret Learning in Repeated First-Price Auctions...

近年来，广告拍卖市场所使用的基本机制逐渐从二价拍卖转变为一价拍卖。尽管已经有一系列关于一价拍卖中的在线报价策略的工作，但如何处理问题中的预算限制仍然是一个悬而未决的问题。在本文中，我们发起针对带预算的重复一价拍卖中的在线报价策略的研究。我们提出了一种基于 RL 的报价算法。如果对手的最高出价在每轮结束时全部揭示，该算法的悔为 $\tilde O(\sqrt T)$-regret。如果买方胜出后看不到对手的最高报价，则利用统计学中生存分析技术得到的改进算法可获得 $\tilde O(T^{\frac{7}{12}})$ 的悔。我们的算法和分析还可扩展到更一般的场景——即任何一致有界的即时效用函数，同时保持相同级别的悔。