技术摘要：在动态价值与聚合反馈下的重复第二价格拍卖中学习出价

1. 问题表述

本工作解决了在重复第二价格拍卖中学习最优出价策略的问题，其中投标人的价值是动态的。与投标人估值独立于过去行动的静态模型不同，此处赢得拍卖的价值取决于自投标人上次成功获胜以来所经过的时间。具体而言，价值函数 $k(\tau)$ 是自上次获胜以来时间 $\tau$ 的凹增函数，反映了数字广告中的用户广告疲劳等现象。

该设定涉及：

• 连续时间：拍卖根据强度为 $\mu$ 的泊松过程到达。
• 动态价值：在时间 $t$ 获胜的奖励为 $k(t - T_{last})$，其中 $T_{last}$ 是上一次获胜的时间。
• 平稳竞争：竞争对手的出价（需击败的价格）独立同分布地从一个未知的连续累积分布函数（CDF）$q$ 中抽取。
• 聚合反馈：投标人不会立即观察到单个拍卖的结果或价格。相反，反馈仅在“回合”（由从速率为 $\gamma$ 的指数分布中抽取的随机时间结束的一系列拍卖）结束时揭示。反馈包括该回合产生的总价值。
• 学习目标：投标人必须学习未知的原始参数 $k$（价值动态）和 $q$（竞争分布），以最大化 $N$ 个回合内的累积期望收益，最小化定义为 $Regret(N) = \sum_{l=1}^N (V_{\pi^*}(0) - V_{\pi_l}(0))$ 的遗憾。

2. 方法论与理论框架

2.1 最优控制表征

基于 [6] 中的连续时间动态规划公式，作者通过贝尔曼价值函数 $V^*(\tau)$ 刻画了最优策略 $\pi^*$。最优出价满足由贝尔曼价值导出的微分方程：
$$\dot{\pi}(t) = \dot{k}(t) - \gamma(V^*(0) + k(t)) + \mu f(\pi(t)) + \gamma \pi(t)$$
其中 $f(v) = q(v)v - p(v)$，且 $p(v)$ 是预期支付价格。求解需要找到一个特定的初始条件 $V^*(0)$，使得生成的轨迹保持有界，该问题通过二分法（即“求解器”$S$）解决。

2.2 通过即插即用估计器学习原始参数

由于 $k$ 和 $q$ 未知，作者提出从数据中学习它们，并将估计值代入求解器 $S$。

• 估计 $k$：建模为分段线性、凹增函数。估计通过对聚合回合数据执行**投影普通最小二乘法（OLS）**进行，将无约束估计量投影到凹函数的凸集上。
• 估计 $q$：建模为分段线性、递增的累积分布函数。估计利用获胜/失败结果和观察到的价格（当获胜发生时）进行最大似然估计（MLE）。

2.3 扩展不变性定理

核心理论贡献是扩展不变性定理（定理 4.1）。它确立了为了识别最优策略，无需学习整个分布 $q$。只需准确估计 $q$ 直至最大最优出价 $\beta(\pi^*)$ 即可。这一见解将出价空间的完全探索需求与学习最优策略的需求解耦，前提是学习算法确保出价覆盖相关区域。

3. 算法与遗憾界限

本文分析了四种基于即插即用估计器的算法：

1. 渐近收敛（迭代即插即用）：一种迭代方法，收集数据、更新估计器并重新计算策略。定理 5.1 证明，如果策略序列探索了 $q$ 可识别的区域（即 $\limsup \beta(\pi_n) > 0$），则该策略渐近收敛到最优策略。然而，这不能保证有限时间的遗憾界限。

2. 两阶段与三阶段算法：这些算法遵循“探索 - 然后 - 承诺”结构。

   • 两阶段：一个固定的探索策略（出价最大价值）运行 $N_1$ 个回合以学习 $k$ 和 $q$，随后进行利用。
   • 三阶段：分离 $k$ 和 $q$ 的学习。首先，一个固定策略学习 $k$；然后，学习到的 $k$ 指导一个策略去学习 $q$；最后进行利用。
   • 结果：两者均实现了 $O(\sqrt{N})$ 的次线性遗憾（定理 5.4 和 5.5）。

3. 置信界限算法（在线学习）：一种受上置信界限（UCB）原则启发的在线算法。

   • 它构建 $k$ 的乐观估计（UCB）和 $q$ 的悲观估计（下置信界限，LCB），以平衡探索与利用。
   • 关键的是，对于分段线性原始参数，它在无需显式随机化的情况下实现了近对数级遗憾 $\tilde{O}(\log N)$（定理 5.7），而显式随机化通常在第一价格拍卖中是必要的。
   • 该算法被证明是近极小极大最优的，因为推导出了 $\Omega(\log N)$ 的下界（定理 5.8），尽管处于动态设定中，其复杂度仍与静态情况相匹配。

4. 一般平滑原始参数：结果被扩展到一般的平滑原始参数（具有利普希茨连续导数的连续可微函数），方法是将其近似为分段线性函数。这产生了 $\tilde{O}(N^{1/3})$ 的遗憾界限（定理 5.10）。

4. 主要贡献

• 动态价值的首次遗憾分析：这是第一项为在重复第二价格拍卖中学习出价提供遗憾界限的工作，其中价值取决于自上次获胜以来的时间，该设定区别于标准的静态或预算约束模型。
• 扩展不变性：证明了只需准确估计竞争分布直至最优出价阈值，从而简化了学习要求。
• 最优遗憾率：证明了在这种复杂、动态的设定中，无需显式随机化即可实现近对数级遗憾，与静态情况的理论下界相匹配。
• 控制与学习的整合：本工作架起了连续时间最优控制（通过最优策略的常微分方程表征）与基于模型的强化学习（通过即插即用估计）之间的桥梁，为具有状态重置的问题提供了框架。

5. 意义与主张

作者声称，这项研究为具有动态价值的环境（如广告疲劳普遍存在的数字广告）中的自动出价提供了一种理论健全的方法。其意义在于：

1. 实际相关性：它解决了“规划问题”，即必须在即时收益与未来价值衰减之间取得平衡，而简单的特征工程或监督学习无法最优地解决这一挑战。
2. 理论洞察：它表明，即使使用聚合反馈和动态价值，只要使用正确的估计和控制工具，该问题在遗憾率方面（对数级与平方根级）并不会变得比静态情况更难处理。
3. 更广泛的影响：该框架为更广泛的强化学习文献提供了见解，特别是涉及重置和非线性奖励的连续时间控制问题。

本文结论指出，虽然分析是理论性的，但即插即用估计与基于微分方程的求解器的结合，表明了一条在现实世界拍卖系统中进行实际应用的可行路径。数值实验支持了理论发现，显示置信界限算法在遗憾增长方面优于“探索 - 然后 - 承诺”策略。