研究了如何提高非随机多臂老虎机的后悔保证,如果每轮损失的有效范围很小(例如,在给定轮次中两个损失之间的最大差异)。通过一些温和的额外假设,如可用的粗略估计损失或单个可能未指定的臂的损失的预先知识,我们展示了这是如何可能的。我们还开发了一种新的技术,可以将任何具有取决于损失范围的后悔的多臂老虎机算法转换为仅取决于有效范围的算法,同时完全避免有问题的臂。
May, 2017
在多臂赌博机领域,多智能体多臂赌博机方法已经受到了广泛关注,但对应的遗憾下界的研究相对较少。本文在不同情景下首次全面研究了遗憾下界,并证明了它们的紧密性。当图表现出良好的连通性和奖励是随机分布时,我们证明了实例相关上界的 O(log T)下界和平均差值独立上界的 sqrt(T)下界。在对抗奖励的假设下,我们建立了连接图的 O(T^(2/3))下界,从而弥合了以前工作中下界与上界之间的差距。当图表现为不连通时,我们还展示了线性的遗憾下界。与以前的研究相比,本文全面研究了这些情景下的紧密下界。
Aug, 2023
在对抗式多臂赌博机中,攻击者通过攻击策略干扰损失或奖励信号,以实现对受害者赌徒玩家的行为控制。我们向攻击者显示,攻击者能够引导任何无憾对抗性赌博算法,在每轮之外的几乎所有轮次中选择次优目标臂,而仅产生次线性的攻击成本。这个结果意味着在现实世界中,基于赌博机的系统中存在重要的安全问题,例如,在线推荐中,攻击者可能能够劫持推荐系统并推广所需的产品。我们提出的攻击算法只需要了解后悔率,因此对受害方使用的具体赌博算法没有任何限制。此外,我们还推导了任何受害者不可知攻击算法必须产生的理论下限,并与我们的攻击产生的上限匹配,这表明我们的攻击在渐近意义下是最优的。
Jan, 2023
本文研究了 K-armed dueling bandit 问题,提出了一种受 Deterministic Minimum Empirical Divergence 算法启发的算法,并得到了匹配下界的后悔上界,实验结果表明该算法明显优于现有算法。
Jun, 2015
本篇论文旨在应对多臂赌博机问题中存在多个最优 / 近似最优机械臂的后悔最小化问题,通过提出自适应算法来自动适应问题的难度,并在理论和实验方面展现了该算法的优越性。
Jun, 2020
本文研究多臂老虎机问题的遗憾下界,并利用 Kullback-Leibler 分歧的已知特性证明了非相对论、分布依赖的限制。这些限制特别表明,在初始阶段遗憾几乎线性增长,并且在最后阶段仅出现知名的对数增长。证明技术突出了信息理论论证的本质,并去除了所有不必要的复杂性。
Feb, 2016
本文提出了一种简单有效的算法来解决批处理随机多臂赌博机和线性随机多臂赌博机问题,这些算法能够通过只使用对数数量的批次实现最优期望遗憾界,此外,文章还首次研究了批处理对抗性多臂赌博机问题,并发现了任何算法的最佳遗憾界(对数因子除外)的预定批处理大小。
Oct, 2019
提出了一种新颖的算法,采用乐观性和适应性技术,结合在线镜像下降框架和特殊的对数障碍正则化器来解决对抗性多臂赌博机问题和组合半赌博问题,并在提高先前工作的同时,取得了多种新的数据依赖性遗憾界。
Jan, 2018
研究了一种新型的 K 武装强盗问题,介绍了一种针对这一问题的新算法,并展示了在特定条件下可以实现有限的预期累计遗憾,同时提供了依赖于问题的累计遗憾下限,显示出至少在某些特殊情况下,新算法是近乎最优的。
Nov, 2014
通过对经典多臂赌博机(Stochastic Multi-Armed Bandit)的研究,探讨了两种不同的准则下存在的遗憾下界。同时,研究了 UCB 等算法的变体,证明了这种情况下不可能设计一种自适应的策略来选择最优算法。
Dec, 2011