在多目标强化学习中，高效识别满足约束的最优选项集。
Constrained Pareto Set Identification with Bandit Feedback
- 设计新算法，在固定置信度下比传统方法更快找到最优解集。
- 理论证明该算法样本复杂度接近理论下限，性能接近最优。
- 适合多目标优化中需兼顾约束条件的研究者使用。
本文研究在多变量老虎机设置下，于可行性约束条件下识别帕累托最优臂集的问题。给定一个具有未知均值 μ₁,…,μₖ ∈ ℝᵈ 的 K 臂老虎机，目标是找出那些在所有目标上都不劣于其他臂的臂（即不存在另一臂在所有维度上均更优），同时满足一组已知的线性约束，例如每项指标的最低性能要求。研究聚焦于固定置信度识别，提出一种新算法，显著优于竞速类算法和先筛选可行臂再找帕累托集的两阶段方法。进一步证明了任何算法在受限帕累托集识别问题上的信息论下界，表明所提方法的样本复杂度近似最优。理论结果通过一系列基准测试的广泛实验得到验证。
原文摘要 · Abstract (English)
In this paper, we address the problem of identifying the Pareto Set under feasibility constraints in a multivariate bandit setting. Specifically, given a $K$-armed bandit with unknown means $μ_1, \dots, μ_K \in \mathbb{R}^d$, the goal is to identify the set of arms whose mean is not uniformly worse than that of another arm (i.e., not smaller for all objectives), while satisfying some known set of linear constraints, expressing, for example, some minimal performance on each objective. Our focus lies in fixed-confidence identification, for which we introduce an algorithm that significantly outperforms racing-like algorithms and the intuitive two-stage approach that first identifies feasible arms and then their Pareto Set. We further prove an information-theoretic lower bound on the sample complexity of any algorithm for constrained Pareto Set identification, showing that the sample complexity of our approach is near-optimal. Our theoretical results are supported by an extensive empirical evaluation on a series of benchmarks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。