用小集合近似多目标最优前沿，理论保证高效选择。
Top-$k$ Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection
- 基于乐观估计贪心选择，最大化所选集合的超体积贡献。
- 理论证明在任意实例下后悔界为 $ ilde{O}(d oot{n}{kT})$，分离充分时呈对数级增长。
- 适用于推荐系统、资源分配等需权衡多个目标的场景。
我们研究一种随机多目标强化学习问题：每轮中，智能体从 $k$ 个臂中选出一个包含 $k$ 个臂的提案集（slate），并基于半反馈观察到其 $d$ 维奖励向量。目标不是寻找单一最优臂，而是维护一组能联合逼近帕累托前沿的小规模行动集。通过所选臂集合诱导的被支配超体积来形式化该目标，并定义了相对于事后可实现的最佳大小为 $k$ 的子集的 $α$-近似超体积后悔，其中 $α = 1 - 1/e$ 反映了单调次模函数贪婪最大化的近似保证。为此，我们提出 extit{THV-UCB} 算法，该算法根据对边际超体积贡献的乐观估计进行贪心选择。我们建立了无间隙的后悔界 $ ilde{O}(d oot{n}{kT})$，该界在所有实例上成立；同时给出了依赖于间隙的边界 $ ilde{O}(nk^{2.5}/Δ_{ ext{min}})$，当臂之间足够分离时，该界随 $T$ 呈对数增长。结果为在多目标应用中使用小规模子集近似帕累托前沿提供了理论支持。
原文摘要 · Abstract (English)
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 $α$-approximate hypervolume regret with respect to the best size-$k$ subset achievable in hindsight, where $α= 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}/Δ_{\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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。