💻 computer science

Bayesian Anytime Pareto Set Identification for Multi-Objective Multi-Armed Bandits

本文介绍了 Top-Two Pareto Front Thompson Sampling (TTPFTS)，这是首个用于多目标多臂老虎机（Multi-Objective Multi-Armed Bandits）的能够识别帕累托最优集的任意时间（anytime）贝叶斯算法，证明了其理论正确性、相对于现有最先进方法的卓越性能，以及在分子发现中的实际应用价值，并提出了一种用于监测学习进展的新型不确定性量化指标。

原作者： Lennert Saerens, Bram Silue, Eleni Litsa, Peter Vrancx, Pieter Libin

发布于 2026-06-19

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Lennert Saerens, Bram Silue, Eleni Litsa, Peter Vrancx, Pieter Libin

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

想象一下你是一位试图创造完美食谱的大厨。你的储藏室里有成千上万种食材（即“臂/arms”）。然而，你不仅仅是在寻找单一的最佳食材，你是在寻找能够平衡两个相互冲突的目标的最佳组合：一是让菜肴美味无比（目标 1），二是保持健康（目标 2）。

有时，某种口感极佳的食材可能非常不健康；而有时，某种非常健康的食材味道却很平淡。这里不存在唯一的“赢家”。相反，存在一组能够提供最佳权衡方案的食材。在数学世界中，这组食材被称为帕累托集（Pareto Set）。

问题在于，你无法品尝宇宙中所有的食材或组合；那会耗费太长时间，也会花费太多的金钱。你需要一种聪明的方法来采样其中的一部分，从中学习，并快速确定哪些属于你的“最佳权衡”名单。

这篇论文介绍了一位聪明的厨师：TTPFTS（Top-Two Pareto Front Thompson Sampling，双顶端帕累托前沿汤普森采样）。它是如何运作的，我们可以将其简单拆解如下：

1. 问题所在：“随时可用（Anytime）”的挑战

大多数旧方法处理这类问题时，就像是一个在严格限时内参加考试的学生。他们直到最后一秒才会决定答案。如果你在 10 分钟考试中的第 5 分钟问他：“你觉得答案是什么？”他可能会给你一个糟糕的猜测，因为他把所有的思考都留到了最后。

这篇论文引入了一种**“随时可用（Anytime）”**的算法。这意味着 TTPFTS 就像一位不断品尝并完善其最佳食材清单的厨师。在任何时刻，如果你问：“你目前最好的权衡清单是什么？”TTPFTS 都能给出一个可靠且最新的答案。

2. 策略：“双顶端（Top-Two）”之舞

TTPFTS 如何决定下一步品尝什么？它使用了一种基于概率（贝叶斯思维）的巧妙技巧。

想象一下，大厨脑海中有两组食材：

A 组（冠军组）： 目前看起来像是最佳权衡方案的食材。
B 组（挑战者组）： 那些几乎和冠军一样好，但可能被轻微低估了的食材。

TTPFTS 抛掷硬币：

正面： 它从 A 组 中随机挑选一种食材进行品尝。这是为了确认：“是的，这些仍然是最棒的。”
反面： 它从 B 组 中随机挑选一种食材进行品尝。这是为了检查：“等等，也许这个‘差一点就到顶’的食材其实比我们想象的还要好！”

通过不断地在“确认赢家”和“测试挑战者”之间切换，大厨能迅速摸清“足够好”与“最好”之间的界限在哪里。

3. “信心计（Confidence Meter）”（不确定性量化）

该论文最大的创新之一是引入了一种新的衡量信心的方法。

通常，要了解你的最佳食材清单是否正确，你需要知道“真实”答案（地面真值/ground truth）。但在现实生活中，你并不知道真实答案，这正是你进行实验的原因！

TTPFTS 引入了一个信心计（Confidence Meter）。它观察大厨脑海中“冠军”与“挑战者”之间的重叠程度。

高重叠： 大厨感到困惑。“冠军”和“挑战者”看起来非常相似。计分器显示：“我还不确定，继续品尝吧！”
低重叠： “冠军”明显优于“挑战者”。计分器显示：“我对我的清单非常有信心。我可以停止了。”

这使得大厨能够在足够自信时精确停止实验，从而节省时间与金钱，而无需预先知道那个秘密的“真实答案”。

4. 现实世界测试：发现新药

作者们不仅在虚构的数学问题上测试了它，还将它应用于一个真实的、巨大的挑战：药物研发。

想象一下，有一个拥有 9400 万 个潜在新药分子的库。你想找到那些既能有效对抗疾病又对人体安全的分子。

旧方法： 一个接一个地检查每一个分子。这需要耗费极长的时间，并花费巨额资金。
随机方法： 随机挑选分子。你很可能会错过那些优秀的分子。
TTPFTS 方法： 该算法探索了这个库，并在检查不到 0.05% 的总库量的情况下，找到了完美的权衡分子。

它找到了与检查全部 9400 万个分子所能发现的同样优秀的分子，但它所用的时间仅为传统方法的一小部分。

总结

这篇论文展示了 TTPFTS，这是一个在面对多个冲突目标时进行决策的聪明、灵活的工具。

它是**随时可用（Anytime）**的，在任何时刻都能给你一个好的答案，而不只是在结束时。
它使用**“双顶端（Top-Two）”策略**，高效地测试最佳选项以及那些可能更好的选项。
它内置了信心计，能告诉你何时停止，从而节省资源。
它被证明在药物研发领域表现极其出色，能比传统方法更快地在庞大的库中找到最佳分子。

简而言之，它是一种更聪明、更快速、更灵活的方式，用于寻找复杂问题中的“甜点（Sweet Spot）”。

技术摘要：用于多目标多臂老虎机任务的贝叶斯随时性帕累托集识别

问题定义

本文研究了多目标多臂老虎机（MOMAB）问题，特别侧重于帕累托集识别（PSI）。与旨在最大化累积回报（遗憾最小化）或识别单个最佳臂的标准单目标老虎机问题不同，MOMAB 涉及同时优化多个潜在冲突的目标。在这种设定下，不存在一个在所有准则下都最优的单一臂；相反，存在一个代表最优权衡的帕累托最优臂集合（ $P^\star$ ）。

本文探讨的具体挑战是随时性（Anytime）PSI表述。虽然现有文献已广泛覆盖了固定预算（在给定样本数后最小化误差）和固定置信度（在达到目标精度前最小化样本量）的情境，但在能够提供在每次观测后持续更新有效估计、且无需预设停止规则的算法方面仍存在空白。这对于现实世界的应用至关重要，因为决策者需要监控进度，并可能根据置信水平而非刚性的资源约束来动态终止实验。

方法论：前二帕累托前沿汤普森采样（TTPFTS）

作者引入了前二帕雷托前沿汤普森采样（TTPFTS），这是首个专为 MOMAB PSI 问题设计的贝叶斯随时性算法。该算法将单目标最佳臂识别中的前二汤普森采样（TTTS）原理扩展到了多目标领域。

核心机制

TTPFTS 不会对目标进行标量化处理（即使用偏好向量将其简化为单目标问题），而是直接对帕累托前沿进行操作。在每个时间步 $t$ ：

后验采样： 算法从各臂相对于历史记录 $H(t-1)$ 的后验分布中，采样均值奖励向量 $\tilde{\theta}^{(t)}_a$ 。
前沿识别： 基于这些样本，识别出第一帕累托前沿（ $F^\star_1$ ），该前沿由不被任何其他采样臂所支配的臂组成。
随机选择： 通过一个概率为 $\rho$ $ρ$ 的伯努利试验来决定探索哪个前沿：
- 以概率 $\rho$ ： 从第一前沿（ $F^\star_1$ ）中均匀随机选择一个臂。这侧重于验证当前被认为是最优的臂。
- 以概率 $1-\rho$ ： 算法移除 $F^\star_1$ ，并从剩余的臂中识别出第二帕累托前沿（ $F^\star_2$ ）。随后从 $F^\star_2$ 中均匀随机选择一个臂。这旨在促进对最有潜力的次优臂（挑战者）的探索，以测试它们是否被低估，或巩固其次优地位。
更新： 抽取选定的臂，观测其奖励，并更新历史记录。算法始终维护一个推荐集 $\hat{P}^\star_t$ （后验均值的帕累托集）。

理论保证

论文证明了渐近正确性（定理 1）。在标准假设（有限臂、一致后验、严格帕累托间隙以及充分探索）下，算法的估计值 $\hat{P}^\star_t$ 随着 $t \to \infty$ 以概率 1 收敛到真实的帕雷托集 $P^\star$ 。该证明依赖于引理 1，该引理确立了 TTPFTS 确保了所有臂几乎处处进行无限探索，从而防止任何臂被永久地“冻结”在采样过程之外。

核心贡献

首个用于 MOMAB PSI 的随时性贝叶斯算法： TTPFTS 填补了文献中关于随时性帕累托集识别算法的空白，为固定预算和固定置信度方法提供了灵活的替代方案。
新型不确定性量化（UQ）指标： 作者引入了一种独立于真值的指标，用于估计算法对其当前帕累托预测的置信度。该指标计算了估计的第一前沿（ $\hat{P}^\star_1$ $\hat{P}_{1}^{⋆}$ ）与第二前沿（ $\hat{P}^\star_2$ $\hat{P}_{2}^{⋆}$ ）的后验密度之间的巴氏距离重叠（Bhattacharyya overlap）。
- 高重叠表示高不确定性（难以区分最优与次优臂）。
- 低重叠表示高置信度（前沿之间界限清晰）。
- 该指标作为识别性能的实时代理，能够实现动态停止准则。
在分子发现中的实际应用： 该算法在一个具有挑战性的、超大规模按需合成分子库（9400 万候选分子）的环境中得到了验证，展示了其在识别优化冲突属性（结构相似性和 LogP）分子的实用价值。

实验结果

合成基准测试

TTPFTS 在八个具有不同帕累托前沿几何形状和维度的合成环境中，与最先进的固定预算算法（经验间隙消除法 EGE 的 Successive Rejects 和 Successive Halving 变体）进行了对比评估。

性能： TTPFTS 一致优于均匀采样和 EGE-SH 算法。尽管面临更严格的随时性约束，它在所有环境中均达到了与 EGE-SR（最强的固定预算基准）相当的性能。
可扩展性： 在动作空间较大（如 $K=200$ ）的环境中，TTPFTS 显著优于 EGE 变体，这表明其基于后验驱动的分配比基于刚性间隙消除的方法在规模化问题上更有效。
鲁棒性： 即使在弱先验假设（均匀先验）下，该算法也表现良好。

分子发现案例研究

在探索一个 9400 万化合物库的过程中：

效率： TTPFTS 仅评估了数据库的 0.05%，便识别出了与地面真值帕累托前沿完全吻合的分子（52 个）。
对比： 它显著优于随机搜索（后者找到了零个最优分子）以及最先进的主动学习方法 MolPAL。
不确定性相关性： 提出的 UQ 指标与 Jaccard 指标（准确率）呈现强负相关。随着算法改进其帕累托集估计，不确定性指标随之下降，验证了其作为可靠的、无需真值的收敛指示器的有效性。

意义与主张

本文声称 TTPFTS 提供了一种在复杂多目标环境下监测学习进度的稳健方法，且无需预先知晓真实的帕累托前沿。通过结合随时性探索策略与新型不确定性量化指标，这项工作将帕累托集识别问题从静态采样任务转变为动态决策支持系统。

作者强调，这种方法允许决策者：

动态确定何时帕累托前沿已得到充分解决，从而终止实验。
在计算资源与发现置信度之间优化权衡。
将这些优势应用于如药物发现等现实场景，在这些场景中，详尽的筛选是不可行的，且偏好可能并非预先已知。

论文对于有限时间误差界的讨论保持了谦逊，承认虽然证明了渐近正确性，但推导显式的有限时间速率仍是一个挑战，这与过去标准汤普森采样所面临的问题类似。然而，作者认为，结合了渐近完备性、强大的实证表现以及不确定性指标的实用价值，确立了 TTPFTS 是多目标决策领域的一项重要进展。