Off-Policy Learning in Large Action Spaces: Optimization Matters More Than Estimation

技术摘要：大规模动作空间中的离线策略学习：优化比估计更重要

问题陈述
大规模动作空间中的离线策略学习（Off-policy learning, OPL）旨在从日志数据 $D_n = \{(X_i, A_i, R_i)\}$ 中学习一个最大化期望回报 $V(\pi)$ 的策略 $\hat{\pi}$。目前的主流范式是优化一个基于逆倾向得分（Inverse Propensity Scoring, IPS）的离线策略评估（Off-policy Evaluation, OPE）估计器，例如 $\hat{\pi} = \arg\max_\pi \hat{V}_{IPS}(\pi)$。尽管近期的研究致力于开发具有更优统计特性（如降低方差或偏差）的复杂估计器，以更准确地逼近 $V(\pi)$，但本文认为，这种以估计器为中心的路径忽视了一个关键的实际障碍：优化景观（Optimization landscape）。

在大型动作空间中（即动作数量 $K$ 可达数百万时），与标准策略参数化（如 softmax）结合使用的基于 IPS 的目标函数表现出严重的优化病态现象。这些现象包括梯度上升停滞的长平台期，以及指数级数量的劣质局部极大值。本文指出，即使是具有卓越统计保证的估计器，也会因为底层的优化问题变得难以处理，从而无法产生优秀的策略。

方法论与分析
作者通过理论分析和实证证据支持了以下观点：在大型动作空间中，优化稳定性比估计准确性更为关键。

1. 基于 IPS 目标函数的理论分析：

   • 本文分析了各种基于 IPS 的估计器（包括标准 IPS、截断 IPS (cIPS)、指数平滑 (ES)、双重稳健 (DR)、边际化 IPS (MIPS)、OffCEM、POTEC 和策略卷积 (PC)）的“预言机策略”（Oracle policies，即理论上的期望目标最大化器）。
   • 优化病态现象： 作者证明，对于使用 softmax 策略的线性-$\pi$ 估计器，梯度上升可能会在次优区域中停留 $O(K_{eff})$ 次迭代，其中 $K_{eff}$ 是有效动作空间的大小。此外，该景观包含数量级与 $K_{eff}$ 指数相关的局部极大值。
   • $K_{eff}$ 的作用： 即使是专为大规模动作空间设计的算法（如 MIPS 或 OffCEM），如果是在完整的动作空间 $A$ 上进行优化，通常也无法缓解这一问题（此时 $K_{eff} = K$）。唯一识别出的例外是 POTEC，它将优化限制在聚类层面，从而有效地减小了 $K_{eff}$。
   • 面向目标的参数化： 作者建议将策略类与估计器的归纳偏置对齐。例如，对于基于 IPS 的方法，将策略支持集限制在日志策略的支持集 $S_0$ 内；或者对于基于聚类的方法，使用两阶段分解。这可以减少 $K_{eff}$ 并提高可训练性，而不改变统计目标。然而，这仅能缓解症状，并不能治愈 IPS 类目标函数本质上的非凹性问题。

2. 策略加权对数似然（PWLL）目标函数：

   • 作为一种根本性的替代方案，本文探索了形式为 $\hat{U}_g(\pi) = \frac{1}{n} \sum g(R_i, \pi_0(A_i|X_i)) \log \pi(A_i|X_i)$ 的 PWLL 目标函数。
   • 凹性： 与 IPS 目标函数不同，当使用线性-softmax 策略时，PWLL 目标函数本质上是凹的（在使用 $\ell_2$ 正则化时是强凹的）。这是因为从分值到对数概率的映射是凹的。
   • 优化保证： 作者确立了在 PWLL 目标函数上的随机梯度上升具有 $O(1/\sqrt{T})$ 的全局收敛速率，并在有正则化的情况下加速至几何级收敛。
   • 变体： 研究评估了特定的 PWLL 变体，包括局部策略改进（LPI）、截断 LPI（cLPI）和正则化 KL（RegKL）。值得注意的是，cLPI 被证明通过凸优化问题实现了与 cIPS 相同的贪婪决策规则。

核心贡献

1. 随动作空间缩放的优化理论： 本文形式化了优化病态现象（平台期和局部极大值）如何随动作数量 $K$ 缩放，解释了为什么基于 IPS 的目标函数在 $K$ 增长时会变得越来越难以优化。
2. 面向目标的参数化： 作者识别了各种目标（源自预言机策略）的最小充分策略结构，并证明通过限制或分解策略以匹配这些结构，可以提高可训练性和性能。
3. 作为优化友好型目标的 PWLL： 本文证明了对于线性-softmax 策略，PWLL 目标函数会产生表现良好的凹优化景观，为直接价值最大化提供了一个鲁棒的替代方案。
4. 大规模实证压力测试： 在三个大规模数据集（$K=60k$ 的 MovieLens，$K=200k$ 的 Twitch 和 $K=1M$ 的 GoodReads）上的广泛实验表明，基于 IPS 的方法对超参数（批大小、学习率调度）高度敏感，而 PWLL 方法则非常鲁棒且一致地获得更高的回报。
5. 实践指导： 本文总结了针对大规模动作空间的设计规则：优先考虑优化稳定性，使用面向目标的参数化，并倾向于使用 PWLL 式的目标函数而非复杂的 IPS 估计器来进行策略学习。

结果

• 优化敏感性： 在受控的参数扫描中，基于 IPS 的目标函数（包括最先进的方法如 POTEC）在次优超参数下表现出高方差和性能崩溃。相比之下，PWLL 方法（特别是 cLPI）在所有配置下均保持了高性能。
• 估计 vs. 学习： 本文强调了一个反直觉的发现：作为价值估计器具有较低均方误差（MSE）的方法（如 MIPS）并不一定能产生更好的策略。相反，作为较差价值估计器（高 MSE）的 PWLL 方法却产生了最好的策略。这表明在大型动作空间中，优化目标的能力是预测策略质量比统计准确性更强的指标。
• 参数化的影响： 将有效动作空间限制在与目标归纳偏置相匹配的范围内（例如，使用支持集受限的策略用于 IPS 方法），显著提高了 IPS 方法的稳定性和性能，尽管它们仍落后于 PWLL 方法。
• 鲁棒性： 与基于 IPS 的方法相比，PWLL 方法在面对回报噪声和不同的日志策略支持集时展现出了更优的鲁棒性。

意义与主张
本文声称，离线学习领域过度关注于精炼估计器，而忽视了优化景观这一关键瓶颈，尤其是在大规模动作空间中。作者认为：

• 优化是瓶颈： 在大型动作空间中，优化非凹 IPS 目标的难度削弱了即使是最具统计学先进性的估计器的实际应用价值。
• 简单即胜利： 比起复杂的方差缩减型 IPS 估计器，像 PWLL（特别是 cLPI）这样简单且对优化友好的目标函数表现更好，因为它们允许稳定且可靠的收敛。
• 设计转向： 针对大规模动作空间的 OPL 算法开发必须明确解决优化问题。本文倡导从“以估计器为中心”的设计转向“以优化为中心”的设计，并建议确保一个易于处理的优化景观比实现高保真度的价值估计对于学习策略而言更为重要。

作者指出其局限性：PWLL 目标函数不适用于需要精确价值估计的离线策略评估（OPE）或策略选择场景。此外，PWLL 的凹性保证严格适用于线性-softmax 策略；虽然深度网络可能会失去形式上的凹性，但其梯度结构仍比基于 IPS 的目标函数更为温和。