本文研究线性贝叶斯最优化模型中的最优臂选择问题,提出样本分配策略来识别具有固定置信度的最优臂,并在最小化样本预算的同时改进了全局线性结构估计附近最优臂的奖励值,并将其与最优实验设计中使用的G-最优准则进行比较。
Sep, 2014
研究最优臂辨识问题,发现新算法和上下限优化,并提出一个新的关于最优样本复杂度的猜想。
Nov, 2015
本研究完整表征了单参数赌博机问题中最优臂识别的复杂度,并提出了一种被称作“Track-and-Stop”的策略,该策略通过的新采样规则和所提出的 Chernoff 停止规则被证明是渐近最优的,并在样本复杂度上取得了一个新的紧致下界。
Feb, 2016
研究了多臂赌博机中的最佳臂辨识问题,提出了一个基于顺序淘汰算法的通用框架,并基于采样机制和每轮淘汰臂数量提出了性能评估指标,设计了一种按剩余臂数的非线性函数划分预算的算法,能够在纯探索场景下获得改进的理论保证和实验性能。
Sep, 2016
考虑在无限臂赌博机问题的固定置信度设置下,当不知道臂储备分布时,近似最优臂识别的问题。我们引入了类 PAC 的框架来推导和表述结果; 推导了近似最优臂识别的样本复杂度下界; 提出了一个算法,以高概率识别出一个接近最优的臂,并推导出其样本复杂度的上界,该上界比我们的下界小一个对数因子;并讨论了我们的 log^2(1/delta) 依赖是否不可避免地适用于无限设置的“两阶段” (先选择臂,后识别最佳)算法。这项工作允许将赌徒模型应用于更广泛的问题类别,其中较少的假设成立。
Mar, 2018
本文研究了随机线性武装的固定置信度下的最佳武器识别问题,目标是在最小化采样预算的同时确定最佳武器。设计了一种简单的算法,其采样复杂度与已知的特定实例下界匹配,在几乎必然的情况下一致性和期望上。此算法依赖于跟踪最佳比例的武器采样规则,而且可以很少更新而不影响其理论保证。此外,与现有的最佳武器识别策略不同,我们的算法使用的停止规则不依赖于武器数量。实验结果表明,我们的算法明显优于现有算法。本文还对具有连续武器集的线性武装的最佳武器识别问题进行了首次分析。
Jun, 2020
固定预算下的随机双臂赌博机最佳臂识别问题中,不存在优于均匀采样算法的算法,该问题的解决方案是引入一类称为“一致稳定算法”的自然算法,并证明该类算法与均匀采样算法的性能相同。
Aug, 2023
该论文研究了在集中置信度下的最佳臂识别问题,提出了一种结合汤普森采样和最佳挑战者规则的策略,在样本复杂度较低的情况下取得了近乎最优的性能。
Oct, 2023
本文介绍了携带固定预算的约束性最佳混合臂识别问题,提出了一个基于分数函数的连续拒绝算法,结合线性规划理论,以识别最佳支持并且证明了其误识别概率在给定学习预算N和问题实例难度常数下的指数衰减。
May, 2024
在本文中,我们研究多信度最佳臂识别问题,通过提出一种以梯度为基础的方法,我们找到了具有渐近最优成本复杂度的解决方案,并针对每个臂还提出了最优保真度的概念。
Jun, 2024