高效求解多目标老虎机的帕累托前沿，小误差下样本最优。
Sequential Learning of the Pareto Front for Multi-objective Bandits
- 基于序列学习设计算法，动态识别多目标奖励的帕累托前沿。
- 在小风险δ下达到最优样本复杂度，每轮计算时间O(Kp^d)。
- 适合需要高精度多目标决策的场景，如推荐系统与资源分配。
我们研究多目标多臂老虎机中帕累托前沿的序列学习问题。代理面临K个可选动作，每轮选择一个并获得向量奖励。当认为已具备足够信息识别各动作均值的帕累托前沿时，停止游戏并给出答案。目标是设计算法使答案正确概率不低于1-δ。主要贡献是实现了一种在δ较小时达到最优样本复杂度的高效算法。当有K个动作、维度为d，其中p个属于帕累托集时，算法每轮运行时间为O(Kp^d)。
原文摘要 · Abstract (English)
We study the problem of sequential learning of the Pareto front in multi-objective multi-armed bandits. An agent is faced with K possible arms to pull. At each turn she picks one, and receives a vector-valued reward. When she thinks she has enough information to identify the Pareto front of the different arm means, she stops the game and gives an answer. We are interested in designing algorithms such that the answer given is correct with probability at least 1-$δ$. Our main contribution is an efficient implementation of an algorithm achieving the optimal sample complexity when the risk $δ$ is small. With K arms in d dimensions p of which are in the Pareto set, the algorithm runs in time O(Kp^d) per round.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。