提出高效算法FraPPE，快速找到多目标强化学习中的最优解集
FraPPE: Fast and Efficient Preference-based Pure Exploration
- 利用结构特性与弗兰克-沃尔夫优化加速计算
- 在K臂L维场景下实现O(KL²)时间复杂度
- 适合需要精准识别最优解的多目标决策场景
基于偏好纯探索（PrePEx）旨在以给定置信度识别向量值（即多目标）老虎机中帕累托最优的臂集合，其中奖励向量通过给定的偏好锥 $/mathcal{C}$ 排序。尽管PrePEx及其变体已广泛研究，但尚无计算高效的算法能在任意偏好锥下达到现有下界。本文通过高效求解下界中的极小化与极大化问题，成功填补该空白。首先推导出下界的三项结构性质，实现极小化问题的可计算简化；随后采用弗兰克-沃尔夫优化器加速极大化过程。结合二者，将最大最小优化问题的求解时间降至 $\mathcal{O}(KL^{2})$，远超现有方法。进一步证明所提算法FraPPE渐近达到最优样本复杂度。在合成与真实数据集上的数值实验表明，FraPPE在所有现有算法中实现最低样本复杂度以精确识别帕累托集。
原文摘要 · Abstract (English)
Preference-based Pure Exploration (PrePEx) aims to identify with a given confidence level the set of Pareto optimal arms in a vector-valued (aka multi-objective) bandit, where the reward vectors are ordered via a (given) preference cone $\mathcal{C}$. Though PrePEx and its variants are well-studied, there does not exist a computationally efficient algorithm that can optimally track the existing lower bound for arbitrary preference cones. We successfully fill this gap by efficiently solving the minimisation and maximisation problems in the lower bound. First, we derive three structural properties of the lower bound that yield a computationally tractable reduction of the minimisation problem. Then, we deploy a Frank-Wolfe optimiser to accelerate the maximisation problem in the lower bound. Together, these techniques solve the maxmin optimisation problem in $\mathcal{O}(KL^{2})$ time for a bandit instance with $K$ arms and $L$ dimensional reward, which is a significant acceleration over the literature. We further prove that our proposed PrePEx algorithm, FraPPE, asymptotically achieves the optimal sample complexity. Finally, we perform numerical experiments across synthetic and real datasets demonstrating that FraPPE achieves the lowest sample complexities to identify the exact Pareto set among the existing algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。