Copeland 决斗问题:损失下限,最佳算法和高效算法
本文研究了 K-armed dueling bandit 问题,提出了一种受 Deterministic Minimum Empirical Divergence 算法启发的算法,并得到了匹配下界的后悔上界,实验结果表明该算法明显优于现有算法。
Jun, 2015
研究提出了两个算法以在 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
本文研究了针对在线内容推荐中的比较对策问题的两类后悔概念,提出了一种新算法 Winner Stays,并在模拟和实际数据方面进行了实验,结果显示 WS 算法在弱后悔和强后悔方面都显著优于现有算法。
Jun, 2017
通过研究三向反馈的对决问题,我们确定了一个学习算法的样本复杂度下限,提出了 POCOWISTA 算法,并证明了在特定条件下偏好概率的情况下,我们可以得到一个改进的样本复杂度。
Oct, 2023
对抗性多对决赌博机中的后悔最小化问题进行了介绍,并引入了一种新算法 MiDEX(Multi Dueling EXP3)来学习来自成对子集选择模型的偏好反馈。证明了 MiDEX 相对于从 K 个臂中选择 Borda 赢家的累计 T 轮后悔的期望上界为 O ((KlogK)^{1/3} T^{2/3}),同时证明了在该设置下预期后悔的下界为 Ω(K^{1/3} T^{2/3}),表明我们提出的算法是接近最优的。
Jun, 2024
这篇研究论文提出了一个基于连续空间的成本函数的对决 Bandit 问题解决方案,介绍了一种随机镜像下降算法,并表明该算法在成本函数的强凸和平滑假设下实现了 O (sqrt (T log T)) 的遗憾界。此外,它还探讨了对决 Bandit 问题遗憾最小化与成本函数凸优化的等价性。
Nov, 2017
研究了一种新型的 K 武装强盗问题,介绍了一种针对这一问题的新算法,并展示了在特定条件下可以实现有限的预期累计遗憾,同时提供了依赖于问题的累计遗憾下限,显示出至少在某些特殊情况下,新算法是近乎最优的。
Nov, 2014
提出了 REX3 算法来解决多臂对决问题中对于选择一对臂进行相对反馈而不是绝对反馈的问题,算法具有 O (sqrt (K ln (K) T)) 的期望有限时间遗憾上界,同时提供了从信息检索应用程序中使用真实数据的实验结果。
Jan, 2016
研究了随机多臂赌博问题中期望奖励是武器的 Lipschitz 函数的情况,提出了两种算法 OSLB 和 CKL-UCB,并衍生出上限,针对连续武器集合的情况建议首先离散化行动空间再应用算法,同时也考虑到了具有类似性质的背景下文本字形赌博。
May, 2014