优化置信区间上界算法:改进有限臂赌博机的遗憾
本文提出了一种分布无关、数据驱动的上置信界(UCB)算法,结合最近发展的重新抽样中位数法(RMM)方法,对称奖励分布的研究中生成近乎最优的后悔边界,即使是重尾分布。
Jun, 2024
研究了一种新型的 K 武装强盗问题,介绍了一种针对这一问题的新算法,并展示了在特定条件下可以实现有限的预期累计遗憾,同时提供了依赖于问题的累计遗憾下限,显示出至少在某些特殊情况下,新算法是近乎最优的。
Nov, 2014
本文提出了一种基于乘数 bootstrap 的非参数和数据相关的 UCB 算法,并进一步将二阶校正融入该算法,在理论上,我们推导出了在比标准次高斯性更弱的尾部假设下的多臂老虎机的问题相关和问题无关的后悔边界,数值结果表明 UCB 算法相比其他基线在一系列多臂和线性老虎机问题中都有显著的降低后悔
Jun, 2019
研究了随机多臂老虎机问题,通过一个单峰函数来表示不完全有序的臂的期望奖励。对于离散和连续臂的情况,分别提出了 OSUB 和 UCB 算法,并得到了渐进的上下界和提高性能的实验结果。
May, 2014
通过对经典多臂赌博机(Stochastic Multi-Armed Bandit)的研究,探讨了两种不同的准则下存在的遗憾下界。同时,研究了 UCB 等算法的变体,证明了这种情况下不可能设计一种自适应的策略来选择最优算法。
Dec, 2011
提出一种基于元 - UCB 算法的简单方法,用于组合随机赌博算法,提高在劣势环境下的表现,实验结果表明算法可以在多种场景下取得与下界一致的效果,已验证线性赌博和模型选择问题的有效性。
Dec, 2020
本文研究了多臂赌博机问题在网络上的去中心化协作,采用加速一致性过程来计算所有智能体对每个臂的平均奖励,该算法采用上置信区间来决策,能够达到更好的回归界,同时不需要过多的底层网络信息。
Oct, 2018
提出了基于一种不精确预算方法的智能多臂赌博机构建 UCB 型算法的新方法;推导出了相应于最优化方法的收敛速度的遗憾界;提出了一种新的算法 Clipped-SGD-UCB,并从理论和实证角度展示了在奖励中存在对称噪声的情况下,我们可以达到 O (logT√KTlogT) 的遗憾界,而不是当奖励分布满足 E [X∈D][|X|^(1+α)]≤σ^(1+α)(α∈(0,1]) 时,即表现得比普遍的重尾赌博机下界所假设的要好。此外,即使奖励分布没有期望,也能保持相同的界限,即当 α<0 时。
Feb, 2024
本文提出了 kl-UCB ++ 算法,用于在具有指数分布族的随机赌博机模型中实现遗憾最小化,并证明了其同时渐近最优(按 Lai 和 Robbins 的下限界定)和极小化最优。这是第一种证明同时具有这两个性质的算法,因此将两种不同的研究方向合并在一起,并提供了简单明了的证明。
Feb, 2017