arXiv:2604.07096cs.LGstat.ML2026-04

多目标强化学习不比单目标难,关键在于精准识别最优解。

Are Stochastic Multi-objective Bandits Harder than Single-objective Bandits?

  • 设计上下文置信区间估计算法,通过逐目标竞争选择最优动作。
  • 理论证明后悔值仅与最大次优差距相关,维度数不影响性能。
  • 实测显著降低后悔值,适合需要权衡多个目标的决策场景。

多目标老虎机因广泛适用性受到关注,其帕累托后悔值由 $d$ 维奖励向量决定。长期以来存在争议:这种结构是否使问题本质更难?本文证明,在帕累托后悔意义上,它并不更难:后悔值随 $g^ lat$(各目标中最大的次优差距)倒数变化,与最小目标的单目标经典后悔值一致。我们提出一种新方法,对每个臂-目标对使用上下置信界估计器,通过“前两名竞争”机制在各目标内比较臂,并采用不确定性贪婪策略将探索集中于最大目标差距 $g^ lat$,直至确定帕累托最优臂。该方法实现 $O( icefrac{\ ext{log} T}{g^ lat})$ 的帕累托后悔,且不依赖维度 $d$。匹配的下界 $Ω( icefrac{ ext{log} T}{g^ lat})$ 表明其最优性。在合成与真实数据集上的评估验证了理论结果,相比基线实现数量级的后悔值下降。真实结果还显示,该方法可能以牺牲经验公平性为代价确定帕累托最优臂,暗示单目标中不存在的潜在困难。

原文摘要 · Abstract (English)

Multi-objective bandits have attracted increasing attention for their broad applicability, with \(d\)-dimensional reward vectors inducing Pareto regret. There has been a subtle debate over whether this added structure makes the problem fundamentally harder than single-objective bandits. We answer this by showing that, in terms of Pareto regret, it is surprisingly no harder: Pareto regret scales inversely with \(g^\dagger\), the largest objective-wise suboptimality gap, and thus matches the smallest objective-wise classical regret. We formalize this idea via a novel method with upper and lower confidence-bound estimators for every arm-objective pair. It uses top-two races to compare arms within each objective and an uncertainty-greedy rule to allocate exploration toward the largest objective-wise gap \(g^\dagger\), until the corresponding Pareto-optimal arm is committed to. We prove that it achieves Pareto regret of \(O(\nicefrac{\log T}{g^\dagger})\), where \(T\) is the horizon, with \emph{no dependence on \(d\)}. A matching lower bound of \(Ω(\nicefrac{\log T}{g^\dagger})\) implies optimality. We evaluate the method on synthetic and real-world datasets, confirming the theory and achieving order-of-magnitude reductions in Pareto regret over baselines. Real-world results further show that our method commits to a Pareto optimal arm, possibly at the cost of empirical fairness, suggesting a potential hardness absent in single-objective bandits.

多目标强化学习老虎机最优性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。