arXiv:2511.05802cs.LGcs.AI2025-11AAAI被引 1

提出新算法,同时优化多目标决策的长期收益与最佳选项发现。

Beyond the Lower Bound: Bridging Regret Minimization and Best Arm Identification in Lexicographic Bandits

  • 分层淘汰策略,按优先级逐层剔除差劲选项。
  • 利用多目标间关联信息,性能突破单目标理论下限。
  • 适合需要兼顾长期收益和快速找最优解的场景。

在具有层级偏好关系的多目标决策问题中,词典序强化学习(lexicographic bandits)为按优先级顺序优化多个目标提供了自然框架。学习者反复选择动作并观察奖励向量,目标是最大化最高优先级目标的奖励,然后是次优先级目标,依此类推。现有研究主要聚焦于最小化累积遗憾(regret minimization),本文首次将遗憾最小化与最优动作识别(best arm identification)相结合。提出两种基于淘汰机制的算法:第一种按目标优先级逐层依次淘汰次优动作,其样本复杂度与遗憾界与最优单目标算法相当;第二种在每轮中同时利用所有目标的奖励信息,有效挖掘跨目标依赖关系。令人惊讶的是,该算法性能超越了已知的单目标强化学习下限,凸显多目标信息共享的优势。实验结果进一步验证了其相较于基线方法的优越性。

原文摘要 · Abstract (English)

In multi-objective decision-making with hierarchical preferences, lexicographic bandits provide a natural framework for optimizing multiple objectives in a prioritized order. In this setting, a learner repeatedly selects arms and observes reward vectors, aiming to maximize the reward for the highest-priority objective, then the next, and so on. While previous studies have primarily focused on regret minimization, this work bridges the gap between \textit{regret minimization} and \textit{best arm identification} under lexicographic preferences. We propose two elimination-based algorithms to address this joint objective. The first algorithm eliminates suboptimal arms sequentially, layer by layer, in accordance with the objective priorities, and achieves sample complexity and regret bounds comparable to those of the best single-objective algorithms. The second algorithm simultaneously leverages reward information from all objectives in each round, effectively exploiting cross-objective dependencies. Remarkably, it outperforms the known lower bound for the single-objective bandit problem, highlighting the benefit of cross-objective information sharing in the multi-objective setting. Empirical results further validate their superior performance over baselines.

多目标优化强化学习词典序算法设计

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