Top-$k$ 帕累托老虎机：多目标板选择中的超体积遗憾

# 面向Top-k帕累托老虎机的超体积遗憾：多目标候选集选择

**摘要**  
我们考虑一个随机多目标老虎机问题，在每个时间步，agent选择一个包含k个臂的候选集，并在半反馈（semi-bandit feedback）下观测它们的d维奖励向量。我们的目标并非识别单个最优臂，而是维护一个能够联合逼近帕累托前沿的小规模动作集。我们通过所选臂子集产生的支配超体积来形式化这一目标，并定义了一个相对于事后可达到的最优大小为k的子集的α近似超体积遗憾，其中α=1-1/e反映了单调子模函数贪心最大化的近似保证。为解决该问题，我们提出了THV-UCB，一种乐观算法，基于对边际超体积贡献的乐观估计贪心地选择臂。我们建立了一个无间隙遗憾界Õ(d√(nkT))，适用于所有实例，以及一个间隙依赖的遗憾界Õ(nk^{2.5}/Δ_min)，当臂充分分离时该界随T呈多对数增长。我们的结果为在多种多目标应用中使用小子集逼近帕累托前沿提供了理论支持。

## 引言

大多数现实世界的决策问题都涉及平衡多个相互冲突的标准，相应的多目标优化（MOO）范式寻求的不是单一最优解，而是一组帕累托最优的权衡解（Tian等，2021；Fromer和Coley，2023）。这一挑战延伸至多臂老虎机（MAB）框架，其中每次拉动不仅产生一个标量，而是一个向量奖励，捕获竞争标准：推荐系统中的准确性与多样性（Letard等，2024；Zaizi等，2025），做市中的利润与库存（Fernández Vicente等，2026），临床试验中的疗效与毒性（KONE等，2023；Kone等，2025a）。当代研究有三个互补目标：1）忠实地且均匀地逼近帕累托前沿（KONE等，2023；Kone等，2025b,a；Shahverdikondori等，2025）；2）在噪声、样本有限的反馈（在线和老虎机设置的典型特征）下，最小化帕累托遗憾（Mandow等，2023；Xu和Klabjan，2023；Cao等，2025；Hüyük和Tekin，2021；Xue等，2025）；3）通过一元、无偏好的指标（如支配超体积）衡量进展（Guerreiro等，2021）。第三条路线通过支配超体积（HV）（Guerreiro等，2021）形式化MOO进展，这是唯一严格符合帕累托合规性的无偏好指标。在帕累托前沿覆盖最为重要的场景中，超体积最大化成为一种更自然的质量标准。HV在帕累托集学习（Zhang等，2023；Zhang，2024）和多目标强化学习（Liu等，2025a,b；Lee等，2026；Röpke等，2025；Song等，2025；Fernández Vicente等，2026；Letard等，2024）中常被用作训练信号。然而，先前的工作要么在连续黑箱域中操作，每轮只查询单个点，不随目标维度d>2扩展，缺乏理论基础，要么专注于特定类型的问题（如凹或凸），缺乏适用性和鲁棒性。据我们所知，没有先前的工作在跨域在线设置中应对这些挑战。我们通过引入THV-UCB，桥接了多目标优化领域的三条主要研究路线。该算法利用乐观奖励向量贪心地最大化边际超体积增益，同时利用逐坐标置信箱安全地剪枝被支配的臂，并进行初始强制探索。因此，我们形式化了一个随机多目标老虎机问题，其中在每个时间步t，agent从一个包含n个候选的集合中选择一个大小为k的候选集St，并在半反馈下观测它们的d维奖励向量。St的性能由其相对于参考点覆盖的支配超体积来评估，我们的理论分析将该性能与任何大小为k的子集所能达到的最优超体积进行比较。我们的主要贡献可归纳如下：

1. 我们引入了Top-k帕累托老虎机设置，并定义了一个相对于帕累托前沿最佳大小为k的子集的α近似超体积遗憾，更适用于许多现实世界场景；
2. 我们将先前竞争性工作（Drugan和Nowe，2013；Deb等，2002；Yahyaa和Manderick，2015；Mandow等，2023；Auer等，2002；Paria等，2020；Zhang和Golovin，2020；Zhang，2024）从帕累托优化和标量化方法扩展到该设置，并在Top-k半反馈设置下针对超体积最大化进行了实证评估，考虑了1）四种合成前沿（线性、凸、凹和聚类）；2）d∈Z∩[2,5]个冲突目标（帕累托前沿的维度）及相应的top-k∈Z∩[3,6]（候选集长度——每轮选择的臂数）；
3. 我们提出了THV-UCB，一种乐观算法，使用逐坐标l∞置信箱和对乐观边际HV增益的贪心选择。其构造与（Zhang和Golovin，2020；Zhang等，2024）的随机HV标量化不同，通过直接在离散k臂候选集设置中利用HV的子模性。实证上，THV-UCB在所有四种前沿几何形状和维度下实现了**最低的累积α遗憾**和**最高的超体积**，且优势随d增大而增加。理论上，我们证明了无间隙遗憾界Õ(d√(nkT))，以及间隙依赖的遗憾界Õ(nk^{2.5}/Δ_min)，这些界随T呈多对数增长。

本文组织如下：相关工作回顾先前文献。问题设置描述问题设置和遗憾定义，而Top-k超体积UCB提出算法THV-UCB。遗憾分析展示我们对该方法的理论分析，并建立遗憾的上界。最后，实验描述我们的实验评估。

## 相关工作

##### 多目标优化（MOO）。
MOO有着悠久的研究历史，并且近期继续有大量工作（Tian等，2021；Ghanbarzadeh等，2026；Jiju和Manemaran，2025；Chen等，2025；He等，2026；Zaizi等，2025），将许多研究领域扩展。在深度强化学习中，近期可比的研究利用超体积既作为质量标准又作为优化手段，以降低学习整个帕累托前沿的计算成本（Zhang等，2023；Cai等，2023；Chen等，2023；Lee等，2026；Fernández Vicente等，2026）。更具体地说，HV驱动的帕累托集学习方法通过对神经偏好条件模型进行梯度下降来最大化HV（Zhang等，2023；Zhang，2024），而基于HV的MORL则将HV嵌入策略优化（Röpke等，2025；Song等，2025）。然而，正如Zhang等人（Zhang等，2024）所述，基于梯度的方法在超体积最大化中的一个主要缺点是计算超体积梯度的计算复杂度高。虽然在d=4个目标下显示出良好结果，但这些方法对于在线设置仍然不实用。

##### 多目标多臂老虎机（MOMAB）。
多目标多臂老虎机将经典老虎机框架扩展到向量值奖励和基于帕累托的最优性概念。早期工作引入了该设置，并基于帕累托遗憾调整了UCB/TS原则（Drugan和Nowe，2013；Q. Yahyaa等，2014；Yahyaa和Manderick，2015；Roijers等，2017；Xu和Klabjan，2023）。随后，一些工作通过多种标量化技术扩展了遗憾最小化的MOMAB，如：Chebyshev（Mandow等，2023）、词典优先级（Hüyük和Tekin，2021）、词典线性老虎机（Xue等，2025）和偏好感知定制（Cao等，2025）。另一条平行的研究路线研究**纯探索**目标，如识别可行臂或近似帕累托集至某个松弛容忍度，包括ε松弛帕累托集识别、约束变体和最佳组识别（Katz-Samuels和Scott，2018；KONE等，2023；Kone等，2025b；Shahverdikondori等，2025）。这些工作通常旨在恢复帕累托集的很大一部分，而不是维护一个固定大小k的**小代表子集**。标量化方法，无论是考虑单个聚合效用函数（Busa-Fekete等，2017；Roijers等，2013,2017；Mandow等，2023）还是多个不同的权衡（Zhang和Golovin，2020；Letard等，2024；Zhang，2024；Cao等，2025；Liu等，2025a,b），通常最适合在线老虎机设置。然而，这些方法涉及固定的偏好分布（Roijers等，2013,2017；Zhang，2024），并没有直接处理在半反馈下**大小为k的候选集**的**集合级**超体积，这补充了我们**无偏好**覆盖前沿的目标。

##### MOMAB中的支配超体积（HV）。
据我们所知，很少有工作将支配超体积作为MOMAB问题的学习目标。在黑箱多目标优化中，随机超体积标量化为探索帕累托权衡提供了可证明的保证（Zhang和Golovin，2020），对于UCB/TS贝叶斯优化，具有Õ(√T)的HV遗憾界。后来，这些界被（Zhang，2024）进一步改进，建立了最优的O(T^{−1/k})的超体积遗憾界。Kone等人（KONE等，2023；Kone等，2025b）和（Zhang，2024）研究的问题与我们的最为接近。然而，尽管臂选择分解方法增加了多样性，但它们主要适用于帕累托前沿识别，在超体积最大化方面性能较低（参见实验部分）。在概念上，与我们提出的THV-UCB算法最接近的现有方法是来自MORL文献的基于HV的方法（Zhang等，2023；Zhang等，2024）。然而，这些工作并未涉及我们研究的离散k臂候选集老虎机设置。

## 问题设置

##### 臂、时间范围和奖励。
我们考虑n个臂，索引为[n]={1,…,n}，在T轮的时间范围内，[T]={1,…,T}。在时间t拉动臂i产生一个d维随机奖励向量Xi,t∈[0,1]^d，其未知均值为μi=E[Xi,t]。我们假设(Xi,t)_{t∈[T]}在t和i上独立，并且每个坐标是η-次高斯（用于集中不等式）；η也作为算法的置信参数。

##### Top-k动作和半反馈。
在每个时间步t∈[T]，agent选择一个子集St⊆[n]，大小为|St|=k（一个**候选集**），并观测向量{Xi,t : i∈St}（半反馈）。

##### 支配和帕累托前沿。
对于a,b∈R^d，如果对所有j∈[d]有aj≤bj，则记a⪯b；如果此外至少有一个不等式严格成立，则记a≺b。如果μi⪰μj且至少一个坐标严格大于，则臂i**帕累托支配**臂j。