固定预算贝叶斯最佳臂识别中的UCB探索
考虑在 $[0,1]$ 区间上的 $K$ 个臂构成的随机赌博机下,使用有限的轮次 $T$ 定位最佳赌博机的问题,证明了在该问题中误判率的最低下界。同时,该结论证明了基于臂的连续拒绝(Successive Rejection)的算法是最优的,填补了固定预算下最佳臂定位问题的上下限差距。
May, 2016
研究Thompson Sampling在bandit问题中的应用,提出一种新的取样规则Top-Two Transportation Cost (T3C),结合贝叶斯停止规则进行采样复杂度分析,并给出bandit问题中Gaussian和Bernoulli rewards和共轭先验的后验收敛性结果。
Oct, 2019
本文研究了随机线性武装的固定置信度下的最佳武器识别问题,目标是在最小化采样预算的同时确定最佳武器。设计了一种简单的算法,其采样复杂度与已知的特定实例下界匹配,在几乎必然的情况下一致性和期望上。此算法依赖于跟踪最佳比例的武器采样规则,而且可以很少更新而不影响其理论保证。此外,与现有的最佳武器识别策略不同,我们的算法使用的停止规则不依赖于武器数量。实验结果表明,我们的算法明显优于现有算法。本文还对具有连续武器集的线性武装的最佳武器识别问题进行了首次分析。
Jun, 2020
提出了EB-TC𝜀,一种新颖的采样规则,可用于随机强盗中的𝜀-最佳臂识别,可在固定置信度或固定预算识别(不需要事先了解预算)。该规则的样本复杂度的期望上界在固定置信度设置下得到了证明,并说明了在其勘探参数进行自适应调节的情况下其渐近最优。我们通过数值模拟表明,EB-TC𝜀在不同情况下表现良好,优于现有算法。
May, 2023
研究在异质奖励方差的固定预算设置下的最佳臂识别问题,提出两种方差自适应的算法:SHVar和SHAdaVar,分别用于已知奖励方差和未知奖励方差情况下,通过不均匀预算分配实现对高方差臂的偏好,本文还给出了误判最佳臂的概率界限。
Jun, 2023
我们研究了基于贝叶斯的固定预算最佳臂识别(BAI)在结构化赌博问题中的应用,提出了一种算法,该算法基于先前的信息和环境的结构使用固定分配,我们对该算法在各种模型上的性能给出了理论上的界限,包括首次基于先验信息的线性和分层BAI的上界。我们的主要贡献是引入了新的证明方法,相比现有方法,该方法对多臂BAI的界限更紧。我们广泛比较了我们的方法与其他固定预算BAI方法,在各种场景下展示了其一致且稳健的性能,我们的工作提升了我们对结构化赌博中基于贝叶斯的固定预算BAI的理解,并突显了我们方法在实际场景中的有效性。
Feb, 2024
在贝叶斯设置下,我们研究了固定置信度最佳臂识别问题。我们证明了传统的FC-BAI算法在贝叶斯设置下会导致任意次优的性能,并且介绍了一种连续淘汰的变体,其性能与下界匹配,仅有一个对数因子的差距。模拟实验验证了理论结果。
Feb, 2024
本文介绍了携带固定预算的约束性最佳混合臂识别问题,提出了一个基于分数函数的连续拒绝算法,结合线性规划理论,以识别最佳支持并且证明了其误识别概率在给定学习预算N和问题实例难度常数下的指数衰减。
May, 2024