稀疏对决波段
对比辩论问题中实现严重非稳态度的底线非希望恶化情况下,解决 Borda 动态后悔上界问题的技术,揭示了 Condorcet 与 Borda 后悔目标在对比辩论问题中学习到严重非稳态度的根本差异。
Mar, 2024
提出了减少德杰斯特拉竞标者问题 (Dueling Bandits) 到传统 (随机) 多臂赌博机问题 (Multi-Armed Bandits) 的算法,我们的算法有着广泛的应用性以及在有限和无限的情况下证明了较优的回报上限。
May, 2014
本文研究具有相关性的多股臂的多对打算法,在推荐系统等领域可以更高效地学习和优化用户的基于偏好的关键特征,使用自对抗算法,结合高斯过程统计方法可以更准确地捕捉相关性,提升算法的效果。
Apr, 2017
本文研究了基于组合纯探索的对决党卫军(CPE-DB)问题,针对 Borda 获胜者和 Condorcet 获胜者情况,提出了多种算法,包括多臂匪徒问题(CPE-MAB)的算法和重要性采样算法。针对 Condorcet 获胜者问题,提出了一种全项式时间逼近法(FPTAS),并利用其作为 Oracle 设计了一种新的纯探索算法 CAR-Cond,其每轮运行时间为多项式时间,从而实现了在 CPE-DB 中识别 Condorcet 获胜者的算法首次达到多项式时间复杂度。
Jun, 2020
提出了一种新的 dueling bandits 模型来解决在线排名器评估中的探索 - 开发权衡问题,该模型使用对于无限数量的排名器的同时比较。实验结果表明,该算法与现有的最先进的 dueling bandit 算法相比,表现出了数量级的性能提升。
Aug, 2016
研究提出了两个算法以在 Condorcet winner 不存在的情况下解决 dueling bandit 问题。这些算法寻求最小化与 Copeland winner 相关的遗憾,Copeland winner 与 Condorcet winner 不同的是,它是有保障的存在。第一个算法 CCB 适用于少量的 arms,第二个算法 SCB 在大规模问题上表现更好。该研究提供了理论结果以界定 CCB 和 SCB 所积累的遗憾。这些结果大幅度改善了现有结果,并且没有附带限制性假设,提供了 O (K log T) 的最佳结果。
Jun, 2015
本文介绍了一种新的解决 K-armed dueling bandit 问题的方法,其扩展了 Upper Confidence Bound 算法并证明了有限时间的遗憾度为 O(log t)。 经实验结果证实,与现有技术相比,该方法在信息检索中取得了显着的优势。
Dec, 2013
对抗性多对决赌博机中的后悔最小化问题进行了介绍,并引入了一种新算法 MiDEX(Multi Dueling EXP3)来学习来自成对子集选择模型的偏好反馈。证明了 MiDEX 相对于从 K 个臂中选择 Borda 赢家的累计 T 轮后悔的期望上界为 O ((KlogK)^{1/3} T^{2/3}),同时证明了在该设置下预期后悔的下界为 Ω(K^{1/3} T^{2/3}),表明我们提出的算法是接近最优的。
Jun, 2024
本文研究了 K-armed dueling bandit 问题,提出了一种受 Deterministic Minimum Empirical Divergence 算法启发的算法,并得到了匹配下界的后悔上界,实验结果表明该算法明显优于现有算法。
Jun, 2015