本文针对无穷臂随机赌博机问题,提出一种算法用以最小化简单损失,并扩展到多种情况下,如未知时间跨度等。
May, 2015
研究了随机多臂老虎机问题,通过一个单峰函数来表示不完全有序的臂的期望奖励。对于离散和连续臂的情况,分别提出了 OSUB 和 UCB 算法,并得到了渐进的上下界和提高性能的实验结果。
May, 2014
在多臂赌博机领域,多智能体多臂赌博机方法已经受到了广泛关注,但对应的遗憾下界的研究相对较少。本文在不同情景下首次全面研究了遗憾下界,并证明了它们的紧密性。当图表现出良好的连通性和奖励是随机分布时,我们证明了实例相关上界的 O(log T)下界和平均差值独立上界的 sqrt(T)下界。在对抗奖励的假设下,我们建立了连接图的 O(T^(2/3))下界,从而弥合了以前工作中下界与上界之间的差距。当图表现为不连通时,我们还展示了线性的遗憾下界。与以前的研究相比,本文全面研究了这些情景下的紧密下界。
Aug, 2023
通过对经典多臂赌博机(Stochastic Multi-Armed Bandit)的研究,探讨了两种不同的准则下存在的遗憾下界。同时,研究了 UCB 等算法的变体,证明了这种情况下不可能设计一种自适应的策略来选择最优算法。
Dec, 2011
研究了一种新型的 K 武装强盗问题,介绍了一种针对这一问题的新算法,并展示了在特定条件下可以实现有限的预期累计遗憾,同时提供了依赖于问题的累计遗憾下限,显示出至少在某些特殊情况下,新算法是近乎最优的。
Nov, 2014
提出了一种基于 UCB 并具有适当的置信参数平衡风险和过度乐观代价的随机有限臂老虎机算法,同时具有最优问题依赖性遗憾和最坏情况遗憾。
Jul, 2015
本文提出了一种简单有效的算法来解决批处理随机多臂赌博机和线性随机多臂赌博机问题,这些算法能够通过只使用对数数量的批次实现最优期望遗憾界,此外,文章还首次研究了批处理对抗性多臂赌博机问题,并发现了任何算法的最佳遗憾界(对数因子除外)的预定批处理大小。
Oct, 2019
研究如何在有空间限制的情况下,解决随机赌博机问题,给出了一种算法,可以在 $O (1)$ 的空间使用下,通过对奖励差距的对数求和来减少遗憾,同时保持接近最优的解决方案。
Dec, 2017
本文研究了 K-armed dueling bandit 问题,提出了一种受 Deterministic Minimum Empirical Divergence 算法启发的算法,并得到了匹配下界的后悔上界,实验结果表明该算法明显优于现有算法。
Jun, 2015
该研究提供了敌对强盗算法必须遭受的遗憾的新的下界,并证明了对于最佳臂的总损失或损失的二次变化的上界是接近紧的。此外,研究还证明了两个不可能的结果,即单臂最优和遗憾不能随损失范围的提高而扩展。相比之下,在完全信息设置中这两个结果是可能的。
May, 2016