摘要：我们研究一个随机多目标 Bandit 问题：在每一轮中，智能体选择一个由 $k$ 个臂组成的候选集，并在半 Bandit 反馈下观测这些臂的 $d$ 维奖励向量。我们的目标并不是识别单一最优臂；相反，我们考虑维护一小组动作，使其能够共同逼近 Pareto 前沿的问题。我们通过所选臂子集诱导的支配超体积来形式化这一目标，并相对于事后可实现的最佳大小为 $k$ 的子集，定义 $α$-近似超体积遗憾；其中，$α = 1 - 1/e$ 反映了贪心最大化单调次模函数的近似保证。为解决这一问题，我们提出 \textit{THV-UCB}：一种乐观算法，基于各臂边际超体积贡献的乐观估计，以贪心方式选择臂。我们证明了一个适用于每个实例的无间隙遗憾界 $~O(d\sqrt{nkT})$，以及一个依赖间隙的遗憾界 $~O(nk^{2.5}/\Delta_{\min})$；当各臂之间的区分度足够高时，后者关于 $T$ 将变为多对数级。我们的结果为在各类多目标应用中，使用小型子集近似 Pareto 前沿提供了理论支持。

Abstract:We consider a stochastic multi-objective bandit problem where, at each round, the agent selects a slate of $k$ arms and observes their $d$-dimensional reward vectors under semi-bandit feedback. We do not aim at identifying a single optimal arm; instead, we consider the problem of maintaining a small set of actions that jointly approximate the Pareto frontier. We formalize this objective through the dominated hypervolume induced by the selected subset of arms, and define an $\alpha$-approximate hypervolume regret with respect to the best size-$k$ subset achievable in hindsight, where $\alpha = 1 - 1/e$ reflects the approximation guarantee of greedy maximization for monotone submodular functions. To address this problem, we introduce \textit{THV-UCB}, an optimistic algorithm that selects arms greedily based on optimistic estimates of their marginal hypervolume contributions. We establish a gap-free regret bound $\tilde{O}(d\sqrt{nkT})$ that holds on every instance, together with a gap-dependent bound $\tilde{O}(nk^{2.5}/\Delta_{\min})$ that becomes polylogarithmic in $T$ once the arms are sufficiently well separated. Our results provide theoretical support for using small subsets to approximate Pareto fronts in various multi-objective applications.