On-Policy and Off-Policy Learning for Large Action Spaces
面向大动作空间的在线与离线上下文老虎机学习方法
🧭 大规模决策 · 上下文老虎机
CREST, ENSAE, Institut Polytechnique de Paris · Criteo AI Lab
通过结构化贝叶斯先验与优化友好的目标，使上下文老虎机在万亿级动作空间下高效探索与安全离线学习
📌 工作参考价值
- 冷启动与物品共享表示：meTS 和 dTS 利用共享的潜在效应或扩散模型先验，在不牺牲每个物品独立 embedding 灵活性的前提下实现信息共享，可直接用于推荐系统的在线探索，显著降低新物品的探索成本。
- 离线策略学习的结构化先验：sDM 通过层次化贝叶斯结构共享物品参数，避免传统直接法在大量物品下因数据稀疏导致的估计偏差，且无需强假设全日志支持，适合电商场景中日志覆盖不均的问题。
- 优化优于估计：在大动作空间（百万级）下，IPS 目标函数高度非凹且存在大量鞍点，应优先使用policy-weighted log-likelihood (PWLL) 目标，它具备强凹性，易于随机优化，能稳定获得高性能策略，已在大规模实验中验证。
- 安全离线学习：论文提出的基于指数平滑的可微分悲观目标，结合 PAC-Bayes 界，将方差控制与保守策略融入梯度优化流程，可直接用于线上推荐系统的离线训练，避免上线后因分布偏移导致的性能崩塌。
动机 推荐、广告等场景中动作空间动辄千万级，传统在线探索和离线策略学习方法面临统计效率低下、优化困难等瓶颈。在线探索中，独立建模每个动作导致缓慢收敛；离线学习中，日志覆盖稀疏、重要性权重方差爆炸、价值估计目标高度非凹，极大限制策略质量。本文系统性地提出一系列原则性方法，旨在同时提升在线和离线大规模决策的可行性。
方法关键点
- 在线混合效应汤普森采样（meTS）：引入共享潜在效应 Ψ 连接各动作参数，通过层次贝叶斯先验压缩有效动作数，推导闭合后验更新与拉普拉斯近似，实现 O(√T dK_eff) 遗憾界，计算复杂度从 O(K²) 降至 O(L²+K)。
- 扩散汤普森采样（dTS）：用预训练扩散模型提供深层先验，即便面对复杂动作结构仍可在线推断，后验保留扩散层次结构而非退化为单高斯，遗憾界进一步收紧，计算复杂度线性于层数 L。
- 结构化直接法（sDM）：将共享潜在效应迁移到离线学习，通过后验积分估计奖励，在贝叶斯框架下证明贪婪策略最优，且不需 π0(a|x) 全局正概率，收敛率 O(1/√n)，仅依赖最优动作的覆盖率。
- 策略加权对数似然（PWLL）：揭示大动作空间下 IPS 目标存在平坦区域与指数级局部极值，而 PWLL 在 softmax 参数化下为强凹函数，易于随机梯度优化，在百万动作数据集上表现全面超越 IPS。
- 可微悲观学习：基于指数平滑的估计量结合 PAC-Bayes 双侧界，导出可微悲观目标，所有惩罚项均可从数据计算，无需不可行常数，同时覆盖多种权重截断/平滑方法。
关键实验
- 在线实验中，meTS 和 dTS 在合成和真实数据集上均大幅超越标准 TS、LinUCB 等基线，优势随动作数 K 增长而扩大。
- 离线实验中，sDM 在 MovieLens 等数据上显著降低子优性差距，且随 K 增大增益更明显。
- PWLL 目标在高达百万级动作空间的实验中，与多种 IPS 变体及复杂估计器对比，稳定取得最高策略值。
- 悲观学习在 K=1000+ 环境中，策略值优于无惩罚的 IPS，且保持低方差，验证了可微悲观的实用价值。
最值得记住的一句话 在大动作空间的离线学习中，优化目标的可微性与凹性比估计的统计精度更重要，应优先设计优化友好的目标而非执着于高精度估计器。