增强型UCB算法在阈值赌博机中的应用
在多臂老虎机游戏中,利用少量样本通过固定置信度水平下的置信区间,提出了一种最初的置信上界算法,该算法使用的样本数量与基于迭代对数定理的下限相比仅相差常数因子,同时使用了一种新的停止时间来避免在其他上置界型算法中观察到的臂联合的界限,从而进一步优化了算法,并通过模拟证明了算法的性能。
Dec, 2013
本研究利用UCB-like算法解决计算和采样高效的随机组合半贝叶斯在线学习问题,并分析了其$n$步遗憾的上界,这里的遗憾是指最优解和次优解之间的预期回报差距。
Oct, 2014
这篇论文提出了一种名为UCBoost的方法,用于解决多臂赌博算法在序贯决策问题中低复杂度且最优问题,该方法提供了一种可以在计算复杂度和最优性之间互相交换的方式。
Apr, 2018
本文研究自适应地从 K 个分布(臂)中抽样,以确定任意两个相邻均值之间的最大差距,即最大间隙赌博机问题。作者提出消除与UCB风格的算法,并证明了它们是极小化的最优解。实验结果表明,UCB风格的算法需要的样本数量比非自适应抽样少6-8倍。
Jun, 2019
提出了基于一种不精确预算方法的智能多臂赌博机构建UCB型算法的新方法;推导出了相应于最优化方法的收敛速度的遗憾界;提出了一种新的算法Clipped-SGD-UCB,并从理论和实证角度展示了在奖励中存在对称噪声的情况下,我们可以达到O(logT√KTlogT)的遗憾界,而不是当奖励分布满足E[X∈D][|X|^(1+α)]≤σ^(1+α)(α∈(0,1])时,即表现得比普遍的重尾赌博机下界所假设的要好。此外,即使奖励分布没有期望,也能保持相同的界限,即当α<0时。
Feb, 2024
本研究旨在探讨一种新颖的纯探索问题:在随机线性赌臂问题中具有固定置信度的 ε-阈值赌臂问题(TBP)。我们证明了采样复杂度的下界,并将一种设计用于解决线性情况下的最佳臂识别问题的算法扩展到了TBP问题中,该算法是渐近最优的。
Feb, 2024
该研究深入研究了阈值线性赌博机(TLB)问题,这是随机多臂赌博(MAB)问题中的一个细分领域,侧重于在资源约束下最大化对线性定义的阈值的决策准确性。我们提出了LinearAPT这个新算法,它适用于TLB的固定预算情景,为优化序贯决策提供了高效的解决方案。该算法不仅对估计损失提供了理论上界,还展示了在合成和实际数据集上的强大性能。我们的贡献突出了LinearAPT的适应性、简洁性和计算效率,使其成为解决复杂序贯决策挑战的重要工具。
Mar, 2024
我们研究了随机多臂赌博问题,提出了一种新的基于Hellinger距离的上界置信度算法Hellinger-UCB,并通过数值实验证明其在有限时间范围内有效。我们将Hellinger-UCB算法应用于解决金融应用程序内容推荐系统的冷启动问题,通过在线实验验证其在点击率方面优于KL-UCB和UCB1。
Apr, 2024
本研究解决了多臂老虎机问题中上置信界(UCB)算法的渐近行为及其对后续推断任务的影响。我们提出,当UCB算法满足某些稳定性条件时,可有效缓解顺序数据收集带来的挑战,发现UCB算法下样本均值呈渐近正态分布,表明算法在处理手臂数量随抽取次数增长时依然保持稳定,并且近似最优手臂数量相对较多。
Aug, 2024