带有固定置信度的结构化最佳臂识别
在多臂老虎机游戏中,利用少量样本通过固定置信度水平下的置信区间,提出了一种最初的置信上界算法,该算法使用的样本数量与基于迭代对数定理的下限相比仅相差常数因子,同时使用了一种新的停止时间来避免在其他上置界型算法中观察到的臂联合的界限,从而进一步优化了算法,并通过模拟证明了算法的性能。
Dec, 2013
本研究完整表征了单参数赌博机问题中最优臂识别的复杂度,并提出了一种被称作“Track-and-Stop”的策略,该策略通过的新采样规则和所提出的 Chernoff 停止规则被证明是渐近最优的,并在样本复杂度上取得了一个新的紧致下界。
Feb, 2016
通过总结深层树结构的置信区间并在根节点应用最佳选择算法,我们开发了一种新的算法来解决游戏树搜索问题,并证明了样本复杂度保证具有对问题实例的精细依赖性。实验证明,与现有的基于排除算法和深度为2的树的专用方法相比,我们的算法具有更好的表现。
Jun, 2017
考虑在无限臂赌博机问题的固定置信度设置下,当不知道臂储备分布时,近似最优臂识别的问题。我们引入了类 PAC 的框架来推导和表述结果; 推导了近似最优臂识别的样本复杂度下界; 提出了一个算法,以高概率识别出一个接近最优的臂,并推导出其样本复杂度的上界,该上界比我们的下界小一个对数因子;并讨论了我们的 log^2(1/delta) 依赖是否不可避免地适用于无限设置的“两阶段” (先选择臂,后识别最佳)算法。这项工作允许将赌徒模型应用于更广泛的问题类别,其中较少的假设成立。
Mar, 2018
本文研究了随机线性武装的固定置信度下的最佳武器识别问题,目标是在最小化采样预算的同时确定最佳武器。设计了一种简单的算法,其采样复杂度与已知的特定实例下界匹配,在几乎必然的情况下一致性和期望上。此算法依赖于跟踪最佳比例的武器采样规则,而且可以很少更新而不影响其理论保证。此外,与现有的最佳武器识别策略不同,我们的算法使用的停止规则不依赖于武器数量。实验结果表明,我们的算法明显优于现有算法。本文还对具有连续武器集的线性武装的最佳武器识别问题进行了首次分析。
Jun, 2020
本文提出 VA-LUCB,并分析其在严格限制下寻找最佳选择时的表现,通过实验结果表明 VA-LUCB 在风险受限制的最佳选择问题类别中具有最低的样本复杂度。
Jan, 2022
在贝叶斯设置下,我们研究了固定置信度最佳臂识别问题。我们证明了传统的FC-BAI算法在贝叶斯设置下会导致任意次优的性能,并且介绍了一种连续淘汰的变体,其性能与下界匹配,仅有一个对数因子的差距。模拟实验验证了理论结果。
Feb, 2024
本文介绍了携带固定预算的约束性最佳混合臂识别问题,提出了一个基于分数函数的连续拒绝算法,结合线性规划理论,以识别最佳支持并且证明了其误识别概率在给定学习预算N和问题实例难度常数下的指数衰减。
May, 2024
本研究解决了固定预算情况下最佳臂识别中的理论不足。提出了一种基于UCB的探索算法,通过学习先验信息,显著提升了算法的表现。实验结果表明,该方法在固定预算贝叶斯最佳臂识别问题上优于现有的最先进算法。
Aug, 2024