Top-k帕累托赌博机：多目标候选集选择的超体积遗憾
本文研究了一种随机多目标赌博机问题，智能体每轮选择k个臂的候选集，并观察其d维奖励向量（半带状反馈）。目标是维护一个能联合近似帕累托前沿的小型动作子集，通过所选臂的子集支配的超体积来形式化目标。定义了α-近似超体积遗憾（α=1-1/e），并提出了基于乐观边际贡献估计的贪心算法THV-UCB，给出了无间隙和有间隙的遗憾界。
在多目标优化中，决策者常常需要同时考虑多个相互冲突的目标。例如，在推荐系统中，我们希望推荐的结果既相关又多样；在广告投放中，则需要在点击率和收益之间取得平衡。传统的优化方法通常只寻找单一的最优解，但在许多实际应用中，我们更希望获得一组能够覆盖帕累托前沿的多样化解决方案。近日，arXiv上发表的论文《Top-k帕累托赌博机：多目标候选集选择的超体积遗憾》正是针对这一问题提出了新颖的理论框架。
该论文由Nicolas Gutowski等四位研究者共同完成，将上述问题建模为随机多目标赌博机问题。具体而言，每轮智能体从n个臂中选择一个包含k个臂的候选集，并观察每个所选臂的d维奖励向量，反馈形式为半带状反馈（即仅观测到所选臂的奖励）。不同于经典赌博机问题追求单一最优臂，该研究的目标是维护一个能够联合近似帕累托前沿的小型动作子集。为了量化所选子集的质量，作者引入了支配超体积（dominated hypervolume）的概念，并定义了α-近似超体积遗憾，其中α=1-1/e。这一近似因子源于贪心算法对单调次模函数最大化的理论保证。
为了解决这一挑战，论文提出了THV-UCB（Thresholded Hypervolume Upper Confidence Bound）算法。该算法基于乐观原则，利用每个臂边际超体积贡献的置信上界，贪心地选择臂组成候选集。理论分析表明，THV-UCB具有两种遗憾界：无间隙遗憾界Ñ(d√(nkT))，适用于所有实例，随时间的平方根增长；以及间隙依赖的遗憾界Ñ(nk^(2.5)/Δ_min)，当臂之间的分离度足够大时，遗憾随时间呈对数增长。这些结果为使用小规模子集近似帕累托前沿提供了坚实的理论支撑。
该工作不仅具有理论意义，还有广阔的应用前景。研究人员指出，THV-UCB算法可应用于推荐系统、自动化决策、资源分配等多个领域。论文共21页、包含7张图表，并附有代码和数据的链接。这项研究为多目标场景下的候选集选择问题开辟了新的方向，也为后续工作奠定了基础。