K 臂对决赌徒问题的相关上限置信界

Dec, 2013

K 臂对决赌徒问题的相关上限置信界

Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem

Masrour Zoghi, Shimon Whiteson, Remi Munos, Maarten de Rijke

TL;DR本文介绍了一种新的解决 K-armed dueling bandit 问题的方法，其扩展了 Upper Confidence Bound 算法并证明了有限时间的遗憾度为 O（log t）。经实验结果证实，与现有技术相比，该方法在信息检索中取得了显着的优势。

Abstract

This paper proposes a new method for the k-armed dueling bandit problem, a variation on the regular K-armed bandit problem that offers only relative feedback about pairs of arms. Our approach extends the Upper Confidence Bound algorithm to the relative setting by using estimates of the

k-armed dueling bandit problem upper confidence bound algorithm finite-time regret bound information retrieval

发现论文，激发创造

Dueling Bandit 问题的遗憾下限和最优算法

本文研究了 K-armed dueling bandit 问题，提出了一种受 Deterministic Minimum Empirical Divergence 算法启发的算法，并得到了匹配下界的后悔上界，实验结果表明该算法明显优于现有算法。

Jun, 2015

Copeland 决斗问题：损失下限，最佳算法和高效算法

研究了 K-armed dueling bandit 问题，提出了 CW-RMED 和 ECW-RMED 算法来解决 Copeland winners 的推荐问题，并通过实验比较证明 ECW-RMED 算法的有效性优于现有算法。

May, 2016

用于对抗性基于效用的决斗多臂赌博机问题的相对指数加权算法

提出了 REX3 算法来解决多臂对决问题中对于选择一对臂进行相对反馈而不是绝对反馈的问题，算法具有 O (sqrt (K ln (K) T)) 的期望有限时间遗憾上界，同时提供了从信息检索应用程序中使用真实数据的实验结果。

Jan, 2016

具有相关臂的多路对决自适应波段算法

本文研究具有相关性的多股臂的多对打算法，在推荐系统等领域可以更高效地学习和优化用户的基于偏好的关键特征，使用自对抗算法，结合高斯过程统计方法可以更准确地捕捉相关性，提升算法的效果。

Apr, 2017

改进的多臂赌博机问题的近乎紧密逼近保证

我们对改进的多臂赌博机问题给出了近似最优的上下界。我们证明了对于任何随机在线算法，存在一个实例使其相对于最优收益至少有一个 Ω(√k) 的近似因子。然后，我们提供了一个随机在线算法，在事先告知最优臂可达到的最大收益的情况下，保证了一个 O (√k) 的近似因子。我们接下来展示了如何消除这一假设，以增加 O (log k) 的近似因子，从而实现了相对于最优的 O (√k log k) 的整体近似。

Apr, 2024

具有相关臂的多臂赌博机

针对多臂赌博机框架中奖励之间相互关联的情况，我们提出了一种统一的方法来优化这种关联并基于这种情况推广经典赌博算法，其中 C-UCB 是上置信边界算法的相关版本。我们证明了算法的正确性，并通过 MovieLens 和 Goodreads 数据集的实验验证了该算法与经典的赌博算法相比的显著改进。

Nov, 2019

有限臂结构赌博机的有界遗憾

研究了一种新型的 K 武装强盗问题，介绍了一种针对这一问题的新算法，并展示了在特定条件下可以实现有限的预期累计遗憾，同时提供了依赖于问题的累计遗憾下限，显示出至少在某些特殊情况下，新算法是近乎最优的。

Nov, 2014

具有潜在随机源的相关多臂赌博机

该论文提出了一种新的多臂赌博机框架，在该框架下将 K-armed bandit 问题转化为 C+1-armed 问题。通过利用该框架下的广义上限置信区间算法可以降低算法的遗憾量，以实现一定的算法性能优势。

Aug, 2018

Copeland 对立双臂赌博算法

研究提出了两个算法以在 Condorcet winner 不存在的情况下解决 dueling bandit 问题。这些算法寻求最小化与 Copeland winner 相关的遗憾，Copeland winner 与 Condorcet winner 不同的是，它是有保障的存在。第一个算法 CCB 适用于少量的 arms，第二个算法 SCB 在大规模问题上表现更好。该研究提供了理论结果以界定 CCB 和 SCB 所积累的遗憾。这些结果大幅度改善了现有结果，并且没有附带限制性假设，提供了 O (K log T) 的最佳结果。

Jun, 2015

多臂赌博机问题：一种有效的非参数解决方案

该研究提出了高效的非参数性多臂赌博机过程，旨在解决机器学习算法和数据分析中的应用问题，并分析了参数和非参数设置下的 UCB 过程的修改版本及非效率性。

Mar, 2017