📊 statistics

On-Policy and Off-Policy Learning for Large Action Spaces

本论文通过提出用于改进探索和遗憾界的在线策略学习结构化贝叶斯方法，以及旨在通过优化目标函数和可微悲观方法来缓解估计误差并控制偏差-方差权衡的新型离线策略技术，解决了上下文多臂老虎机在大动作空间下的策略学习挑战。

原作者： Imad Aouali

发布于 2026-07-31

📖 1 分钟阅读☕ 轻松阅读

原作者： Imad Aouali

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一位正在试图穿越一个拥有数百万颗恒星的星系、寻找最佳航线的巨型飞船舰长。每当你选择一颗恒星进行访问时，你都会收到一个微弱且模糊的信号，告诉你这是一个好的选择还是一个坏的选择。这就是**上下文老虎机（contextual bandits）**的世界，它是人工智能的一个分支，旨在帮助计算机在还不了解游戏规则时做出决策。“上下文”是你在所处的情境（比如天气或心情），“动作”是你所做的行为（比如挑选一颗恒星），而“奖励”则是结果（比如发现宝藏或撞上小行星）。

棘手的部分在于选择的数量极其庞大。如果你必须猜测一百万颗恒星中哪一颗是最好的，而你一次只能检查其中几颗，你可能会把一辈子都浪费在探索错误的路径上。这就是“大规模动作空间”问题。这就像是在一座城市规模的干草堆中寻找一根特定的针，但你一次只能拔出一根稻草，并寄希望于它就是那根针。科学家们之所以关注这个问题，是因为它是驱动诸如推荐电影、向你展示合适的广告或甚至设计新药等技术的引擎。如果计算机陷入随机猜测，就会浪费大量的时间和金钱。

本篇论文探讨了如何教计算机在面对数百万个选项时做出明智的选择，并采用了两种不同的策略：边走边学（on-policy，在线策略）和从旧日志中学习（off-policy，离线策略）。

在线策略的冒险：带着地图边做边学

首先，作者研究了“在线策略”的情景，即计算机通过与现实世界实时交互来进行学习。想象一下，你正在探索一座拥有数百万本书籍的巨大图书馆，但你并不知道哪些书是好书。一个标准的探索者会选一本书，读一页，如果觉得无聊，就会完全放弃，从头开始尝试另一本书。这既缓慢又低效。

论文引入了一种更聪明的探索者，使用的是混合效应汤普森采样（Mixed-Effect Thompson Sampling, meTS）。这种探索者不再将每本书都视为一个独特的谜团，而是注意到书籍属于不同的类型。它学习到“科幻”类书籍具有共同的特征。通过将书籍进行分类（如“动作”、“浪漫”或“悬疑”），探索者可以仅通过阅读几本书就了解整个类型。如果它读到了一本优秀的科幻书，它就会得到一个暗示：其他科幻书也可能很棒。这种“信息的共享”极大地加快了学习速度。数学证明显示，计算机不再需要了解数百万本独立的图书，而只需要了解几十个“类型”（潜在效应）以及每本书在这些类型中的具体特性。

随后，作者通过**扩散汤普森采样（Diffusion Thompson Sampling, dTS）**将这一想法进一步深化。如果说第一种方法是像按类型对书籍进行分组，那么这种新方法就像是一位理解书籍之间深层复杂联系的超级图书管理员。也许一本书是“赛博朋克”与“历史小说”的结合，或者它与另一部不同世纪的书有着特定的写作风格。利用一种被称为“扩散模型”（与某些图像生成器背后的技术相同）的 AI，计算机学习了一个关于所有书籍如何相互关联的丰富且深层的地图。这使得它能够更快地探索图书馆，即使图书馆规模巨大。在模拟实验中，这些方法比那些将每本书都视为陌生人的旧方法更快地找到了最优秀的书籍。

离线策略的挑战：从混乱的日记中学习

接下来，论文处理了“离线策略”的情景。想象一下，你不再能亲自去探索图书馆了。相反，你必须通过一位口味迥异的前任探索者留下的混乱日记来进行学习。也许那位探索者只读恐怖片，而现在你需要寻找最好的浪漫电影。这就是“离线策略”问题：从他人收集的数据中学习。

作者挑战了该领域的一个普遍观点：即构建一个最准确的“奖励估计器”（一个预测选择好坏的预知能力）是最重要的。论文指出，在巨大的图书馆中，优化过程实际上才是更大的问题。这就像是拥有一个完美的地图（估计器），却试图用一个破损的指南针（优化算法）来导航。数学证明显示，使用这些地图的标准方式往往会陷入“平坦高原”或局部陷阱，导致无论地图多么完美，都无法找到最佳路径。

为了解决这个问题，作者提出了一种新方法：策略加权对数似然法（Policy-Weighted Log-Likelihood, PWLL）。与其试图精确预测奖励，不如专注于让优化路径变得平滑且易于行走。这就像是从一条崎岖不平的山路切换到一条平缓蜿蜒的公路。即使道路不是笔直的，也更容易到达顶峰。在多达一百万个动作的实验中，这种简单的平滑方法始终优于那些陷入困境的复杂“智能”估计器。

论文还介绍了一种处理旧日记中“噪声”的新方法。当之前的探索者很少造访某些区域时，数据是不可靠的。作者建议使用**指数平滑（Exponential Smoothing）**结合“原则性的悲观主义（principled pessimism）”。可以将此想象为一个谨慎的探索者，他信任日记，但会增加一个安全缓冲。如果日记说某条路径很棒，但数据并不稳固，探索者就会假设它可能比报告的要稍差一些，以避免灾难。论文在数学上证明了这种方法在保持探索者安全的同时，仍能使其有效学习，并且即使在数据稀疏的情况下也能表现良好。

大局观

简而言之，这篇论文表明，当你面对数百万个选择时，你不能仅仅靠蛮力去闯。你需要找到隐藏的结构（如类型或深层联系）来共享你所学到的知识，并且你需要确保你的学习路径足够平滑，以便能够真正找到解决方案。无论是在实时学习还是挖掘旧日志，关键在于如何聪明地对信息进行分组，以及如何处理数学逻辑。这些方法在模拟数据和真实世界电影推荐数据集上的测试结果表明，这些新方法是使 AI 决策变得可扩展且高效的重要进步。

技术摘要：大规模动作空间下的在策略与离策略学习

问题陈述

本论文探讨了交互式系统（特别是上下文多臂老虎机，Contextual Bandits）中面临的基础挑战，即动作空间 $K$ 极其庞大（从数千到数百万不等）。在这种设定下，标准算法在在策略（On-Policy/在线）和离策略（Off-Policy/离线）学习方面都面临严重的扩展性瓶颈：

在策略学习： 标准的探索策略，如汤普森采样（Thompson Sampling, TS）或置信上限算法（UCB），通常依赖于每个动作具有独立参数的解耦模型。在大规模动作空间中，独立学习每个参数在统计上是低效的，会导致极高的累积遗憾（Regret）。相反，共享参数的联合模型由于需要维护和更新完整的协方差矩阵，其计算复杂度高达 $O(K^2)$ 或 $O(K^3)$ ，往往在计算上是不可行的。
离策略学习： 从由日志策略 $\pi_0$ $π_{0}$ 收集的静态日志数据中学习面临三个主要问题：
1. 统计低效性： 直接法（Direct Methods, DM）在动作很少被观测到时会产生高偏差。
2. 方差问题： 逆倾向得分（Inverse Propensity Scoring, IPS）估计量在日志概率 $\pi_0(a|x)$ 较小时会出现方差爆炸。
3. 优化不可行性： 论文指出，在大型动作空间中，基于标准 IPS 的目标函数的优化景观（Optimization Landscape）变得高度非凹，存在平坦平台和指数级数量的局部极大值，导致无论估计器的统计质量如何，基于梯度的优化器都会失效。

方法论与贡献

本论文分为两个部分，分别为每种学习范式提出了新颖的方法。

第一部分：在策略学习（扩展汤普森采样）

核心思想是在保留解耦奖励模型灵活性的同时，引入结构化贝叶斯先验，以实现跨动作的信息共享。

1. 混合效应汤普森采样 (meTS) —— 第3章

方法论： 作者引入了一种层次化贝叶斯模型，其中动作参数 $\theta_a$ 通过 $L$ 个共享的潜在效应参数 $\Psi = (\psi_\ell)_{\ell \in [L]}$ 进行耦合。生成过程假设 $\theta_a | \Psi \sim p_0(\cdot|\Psi)$ 。
算法： meTS 执行层次化采样：首先从其后验分布中采样全局效应 $\Psi_t$ ，然后基于 $\Psi_t$ 采样单个动作参数 $\theta_{t,a}$ 。
理论结果： 对于线性高斯模型，作者推导出了精确的闭式后验更新。他们证明了贝叶斯遗憾界为 $\tilde{O}(\sqrt{Td K_{eff}})$ ，其中 $K_{eff}$ 是有效动作数。当效应数 $L \ll K$ 时， $K_{eff} \ll K$ ，从而实现了相对于标准 TS 的乘性提升。
复杂度： 该方法将内存复杂度从 $O(K^2d^2)$ 降低到 $O((L^2 + K)d^2)$ ，并将运行时间从 $O(K^3d^3)$ 降低到 $O((L^3 + K)d^3)$ 。
扩展： 该框架通过易于处理的拉普拉斯近似扩展到了广义线性模型（GLMs）。

2. 扩散汤普森采样 (dTS) —— 第4章

方法ology： 为了捕捉动作之间更复杂的非线性依赖关系，作者使用由预训练扩散模型控制的深层潜在变量结构取代了单层潜在结构。先验被定义为一个由非线性链接函数 $f_\ell$ 连接的潜在变量马尔可夫链 $\psi_L \to \dots \to \psi_1 \to \theta_a$ 。
算法： dTS 采用递归推理程序。它通过维护一个“后验扩散模型”来近似难以处理的后验，其中链接函数和协方差通过类似于高斯的更新（结合先验精度和数据精度）进行更新，而无需对神经网络进行反向传播。
理论结果： 在线性高斯设定下，遗憾界随有效动作数及 $L$ 层中所有方差之和进行缩放。其复杂度随 $L$ 线性缩放，即 $O((L+K)d^2)$ ，优于 meTS。
意义： 这证明了深度生成模型不仅可以用于表示，还可以用于构建高效探索所需的结构化不确定性。

第二部分：离策略学习（解决估计与优化问题）

论文挑战了主流的“以估计为中心”的范式，并提出了三种互补的方法。

1. 结构化直接法 (sDM) —— 第6章

方法论： 与 meTS 类似，sDM 在离线设定中引入共享潜在向量 $\psi$ 来耦合动作参数。它计算潜在效应的后验以及动作参数的条件后验。
结果： 作者证明了 sDM 在不需要“全日志支持（Full Logging Support）”这一严格假设的情况下，实现了 $O(1/\sqrt{n})$ 的贝叶斯次优性收敛。该界限取决于日志策略与最优策略之间的对齐程度。
洞察： 在所考虑的贝叶斯次优性准则下，贪婪策略被证明是最优的，并且可以优于悲观策略，这与在频繁派主义（Frequentist）设定中通常需要悲观主义的做法形成对比。

2. 优化比估计更重要 —— 第7章

方法论： 作者证明，在大型动作空间中，优化误差主导了估计误差。标准的基于 IPS 的目标函数会导致非凹的景观，从而使优化器陷入困境。
提议： 论文主张不再是先估计价值再进行优化，而是采用策略加权对数似然 (PWLL) 目标函数：
$\hat{U}_g(\pi) = \frac{1}{n} \sum_{i=1}^n g(R_i, \pi_0(A_i|X_i)) \log \pi(A_i|X_i)$
结果： 对于线性 Softmax 策略，PWLL 目标函数是凹的（且在 $\ell_2$ 正则化下是强凹的），保证了存在唯一的全局最大值。在拥有高达一百万个动作的数据集上的实验表明，这些简单、稳定的目标函数始终优于复杂的基于价值估计器的方法。

3. 指数平滑的原则性悲观主义 —— 第8章

方法论： 为了解决 IPS 的方差问题，作者引入了可微的指数平滑 (Exponential Smoothing, ES) 估计器，它在无正则化与强方差缩减之间进行插值。
理论： 为这些正则化估计器推导了一个双侧 PAC-Bayesian 泛化界。该界限将误差分解为散度、正则化偏差和剩余方差。
应用： 该界限产生了一个可微的、悲观的学习目标，可以通过随机梯度上升进行优化。该框架统一涵盖了其他正则项，如裁剪（Clipping）和隐式探索。
扩展： 作者还引入了对数平滑 (Logarithmic Smoothing, LS)，这是一种相比于裁剪更温和、可微的替代方案，能够实现更紧凑的集中界限。

实验结果

所提方法在合成数据集和真实世界数据集上均得到了验证：

在策略： 在合成线性与逻辑回归 Bandit 环境中，meTS 和 dTS 显著优于基准算法（LinTS, GLM-TS, HierTS），且随着动作空间 $K$ 的增大，性能差距进一步扩大。在 MovieLens 实验（推荐系统）中，即使在真实奖励模型被误设的情况下，meTS 仍能实现最低的遗憾，展示了鲁棒性。
离策略：
- sDM 优于标准的直接法，且优势随 $K$ 的增长而增加。
- PWLL 目标函数（第7章）在高达一百万个动作的数据集上始终优于最先进的基于 IPS 的方法，表现出对超参数调优的卓越鲁棒性。
- PAC-Bayesian 悲观目标（第8章）在各种日志策略质量下（尤其是日志策略非均匀分布时）均取得了比基准方法（包括 London 等人和 Sakhi 等人的方法）更好的回报。

意义与主张

本论文声称弥合了理论 Bandit 算法与现代工业系统约束（例如拥有数百万商品的推荐系统）之间的鸿沟。其核心论点是，扩展到大规模动作空间需要：

结构化不确定性： 使用层次化和基于扩散的先验，在动作间共享统计强度（在策略）。
重新评估目标函数： 认识到在大型空间中，优化景观的可行性与估计器的统计准确性同样至关重要（离策略）。
可微悲观主义： 开发具有理论依据且计算可行（而非依赖于难以处理的常数）的悲观目标。

该研究断言，通过摆脱独立的动作建模和标准的价值估计，上下文多臂老虎机可以有效地部署在动作空间经常超过数千甚至数百万的环境中。