使用上置信界算法进行推断
在多臂老虎机游戏中,利用少量样本通过固定置信度水平下的置信区间,提出了一种最初的置信上界算法,该算法使用的样本数量与基于迭代对数定理的下限相比仅相差常数因子,同时使用了一种新的停止时间来避免在其他上置界型算法中观察到的臂联合的界限,从而进一步优化了算法,并通过模拟证明了算法的性能。
Dec, 2013
本文主要研究的问题是:如何在样本预算有限的情况下,统一地估计多个分布的平均值。通过采集数量,可以根据它们的方差为已知来设计最优的采样策略,但在更实际的情况下,需要设计自适应采样策略来选择要采样的分布(根据先前观察到的样本)。文章描述了两种策略,根据样本数据以高概率上限置信界为比例,拉动分布并报告相对于最优配置的过度估计误差的有限样本性能分析。我们表明这些分配策略的性能不仅取决于方差还取决于分布的完整形状。
Jul, 2015
考虑在 $[0,1]$ 区间上的 $K$ 个臂构成的随机赌博机下,使用有限的轮次 $T$ 定位最佳赌博机的问题,证明了在该问题中误判率的最低下界。同时,该结论证明了基于臂的连续拒绝(Successive Rejection)的算法是最优的,填补了固定预算下最佳臂定位问题的上下限差距。
May, 2016
考虑在无限臂赌博机问题的固定置信度设置下,当不知道臂储备分布时,近似最优臂识别的问题。我们引入了类 PAC 的框架来推导和表述结果; 推导了近似最优臂识别的样本复杂度下界; 提出了一个算法,以高概率识别出一个接近最优的臂,并推导出其样本复杂度的上界,该上界比我们的下界小一个对数因子;并讨论了我们的 log^2(1/delta) 依赖是否不可避免地适用于无限设置的“两阶段” (先选择臂,后识别最佳)算法。这项工作允许将赌徒模型应用于更广泛的问题类别,其中较少的假设成立。
Mar, 2018
本文提出了一种基于乘数bootstrap的非参数和数据相关的UCB算法, 并进一步将二阶校正融入该算法, 在理论上, 我们推导出了在比标准次高斯性更弱的尾部假设下的多臂老虎机的问题相关和问题无关的后悔边界, 数值结果表明UCB算法相比其他基线在一系列多臂和线性老虎机问题中都有显著的降低后悔
Jun, 2019
本文研究了随机预算多臂赌博问题,并提出了一种名为ω-UCB的新的上置信界(UCB)采样策略,该策略使用了不对称置信区间,并表明该方法具有对数遗憾且在合成和真实设置中始终优于现有策略。
Jun, 2023
在贝叶斯设置下,我们研究了固定置信度最佳臂识别问题。我们证明了传统的FC-BAI算法在贝叶斯设置下会导致任意次优的性能,并且介绍了一种连续淘汰的变体,其性能与下界匹配,仅有一个对数因子的差距。模拟实验验证了理论结果。
Feb, 2024
本文提出了一种分布无关、数据驱动的上置信界(UCB)算法,结合最近发展的重新抽样中位数法(RMM)方法,对称奖励分布的研究中生成近乎最优的后悔边界,即使是重尾分布。
Jun, 2024
本文聚焦于赖子在多臂赌博机领域的开创性贡献,提出了对于高斯奖励的上置信界的尖锐非渐近后悔界限,解决了研究中对常量探索级别的欠缺。同时,我们为赖1987年提出的基于样本量递减的探索函数的上置信界建立了新的非渐近后悔界限,结果显示出与赖-罗宾斯下界相匹配的常数,为多臂赌博机的研究提供了新的视角。
Oct, 2024