非随机最佳臂识别与超参数优化
本文介绍了一种基于贝叶斯方法的多臂赌博机最佳臂识别优化方法,其着重于建模与多臂之间的相关性,相比已有的方法在允许的函数评估数目较小时能够取得更优的效果,在自动机器学习工具箱等实际应用中表现良好。对多种方法进行对比分析,阐明了它们不同特征之间的相对优劣。
Mar, 2013
本文研究线性贝叶斯最优化模型中的最优臂选择问题,提出样本分配策略来识别具有固定置信度的最优臂,并在最小化样本预算的同时改进了全局线性结构估计附近最优臂的奖励值,并将其与最优实验设计中使用的G-最优准则进行比较。
Sep, 2014
本研究完整表征了单参数赌博机问题中最优臂识别的复杂度,并提出了一种被称作“Track-and-Stop”的策略,该策略通过的新采样规则和所提出的 Chernoff 停止规则被证明是渐近最优的,并在样本复杂度上取得了一个新的紧致下界。
Feb, 2016
本文研究了在多臂赌博机的延迟反馈场景下,如何利用局部反馈来提高标准算法的样本复杂度。采用模型化的方法探讨了局部反馈和延迟反馈之间的关系,并提出了一种用于处理偏差或无偏差情况下局部反馈的有效算法。另外,还针对并行多臂赌博机提出了一种新的算法扩展。在实际场景中,针对电池快速充电和野生动物走廊建设的计算可持续性领域中的策略搜索和超参数优化等问题的实验表明,利用局部反馈的结构可以显著提高标准算法的性能。
Mar, 2018
本文研究了随机线性武装的固定置信度下的最佳武器识别问题,目标是在最小化采样预算的同时确定最佳武器。设计了一种简单的算法,其采样复杂度与已知的特定实例下界匹配,在几乎必然的情况下一致性和期望上。此算法依赖于跟踪最佳比例的武器采样规则,而且可以很少更新而不影响其理论保证。此外,与现有的最佳武器识别策略不同,我们的算法使用的停止规则不依赖于武器数量。实验结果表明,我们的算法明显优于现有算法。本文还对具有连续武器集的线性武装的最佳武器识别问题进行了首次分析。
Jun, 2020
提出了EB-TC𝜀,一种新颖的采样规则,可用于随机强盗中的𝜀-最佳臂识别,可在固定置信度或固定预算识别(不需要事先了解预算)。该规则的样本复杂度的期望上界在固定置信度设置下得到了证明,并说明了在其勘探参数进行自适应调节的情况下其渐近最优。我们通过数值模拟表明,EB-TC𝜀在不同情况下表现良好,优于现有算法。
May, 2023
固定预算下的随机双臂赌博机最佳臂识别问题中,不存在优于均匀采样算法的算法,该问题的解决方案是引入一类称为“一致稳定算法”的自然算法,并证明该类算法与均匀采样算法的性能相同。
Aug, 2023
通过介绍一种新算法 ROBAI 和其变种,该研究识别并解决了在带有双重目标的多臂赌博机问题中达到最优臂的同时最大化奖励的难题;并对算法的停止时间、样本复杂性以及与经典 UCB 算法相比的性能进行了理论分析和数值实验,揭示出了经典 UCB 算法中的“过度探索”现象。
Sep, 2023
本文介绍了携带固定预算的约束性最佳混合臂识别问题,提出了一个基于分数函数的连续拒绝算法,结合线性规划理论,以识别最佳支持并且证明了其误识别概率在给定学习预算N和问题实例难度常数下的指数衰减。
May, 2024