基于偏好选择的强化学习，高效找出最优策略
Preference-based Pure Exploration
- 用偏好锥定义多维奖励排序，识别帕累托最优臂
- 提出新下界，揭示偏好几何对探索难度的影响
- 算法在高斯奖励下渐近最优，适合多目标决策场景
我们研究具有向量奖励的带臂问题中的基于偏好的纯探索。奖励通过给定的偏好锥 $\ ext{C}$ 进行排序，目标是识别帕累托最优臂的集合。首先，为量化偏好影响，我们推导出以置信度 $1-δ$ 识别最偏好策略的样本复杂度的新下界。该下界揭示了偏好锥几何结构的作用，并凸显了与现有最优臂识别变体的难度差异。当奖励服从高斯分布时，进一步阐明了该几何结构。随后，我们对下界进行凸松弛，并据此设计了偏好追踪停止（PreTS）算法，用于识别最偏好策略。最后，通过为向量值奖励建立新的浓度不等式，证明了PreTS的样本复杂度渐近紧致。
原文摘要 · Abstract (English)
We study the preference-based pure exploration problem for bandits with vector-valued rewards. The rewards are ordered using a (given) preference cone $\mathcal{C}$ and our goal is to identify the set of Pareto optimal arms. First, to quantify the impact of preferences, we derive a novel lower bound on sample complexity for identifying the most preferred policy with a confidence level $1-δ$. Our lower bound elicits the role played by the geometry of the preference cone and punctuates the difference in hardness compared to existing best-arm identification variants of the problem. We further explicate this geometry when the rewards follow Gaussian distributions. We then provide a convex relaxation of the lower bound and leverage it to design the Preference-based Track and Stop (PreTS) algorithm that identifies the most preferred policy. Finally, we show that the sample complexity of PreTS is asymptotically tight by deriving a new concentration inequality for vector-valued rewards.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。