几乎最优方差约束的最佳臂识别
本文介绍了非随机最佳臂识别问题,利用迭代机器学习算法并将其应用于超参数优化,以及资源分配改进算法等关键词,结果表明我们的算法可实现与基准方法相当测试准确率,但速度快一个数量级。
Feb, 2015
本研究完整表征了单参数赌博机问题中最优臂识别的复杂度,并提出了一种被称作“Track-and-Stop”的策略,该策略通过的新采样规则和所提出的 Chernoff 停止规则被证明是渐近最优的,并在样本复杂度上取得了一个新的紧致下界。
Feb, 2016
本文探讨了Best-$k$-Arm问题的样本复杂性边界,提出了一种新颖的复杂度度量方法和基于消除的算法,并展示了该算法的实例-边界下限和状态-界限的严格支配能力。
Feb, 2017
本文研究了随机线性武装的固定置信度下的最佳武器识别问题,目标是在最小化采样预算的同时确定最佳武器。设计了一种简单的算法,其采样复杂度与已知的特定实例下界匹配,在几乎必然的情况下一致性和期望上。此算法依赖于跟踪最佳比例的武器采样规则,而且可以很少更新而不影响其理论保证。此外,与现有的最佳武器识别策略不同,我们的算法使用的停止规则不依赖于武器数量。实验结果表明,我们的算法明显优于现有算法。本文还对具有连续武器集的线性武装的最佳武器识别问题进行了首次分析。
Jun, 2020
提出了EB-TC𝜀,一种新颖的采样规则,可用于随机强盗中的𝜀-最佳臂识别,可在固定置信度或固定预算识别(不需要事先了解预算)。该规则的样本复杂度的期望上界在固定置信度设置下得到了证明,并说明了在其勘探参数进行自适应调节的情况下其渐近最优。我们通过数值模拟表明,EB-TC𝜀在不同情况下表现良好,优于现有算法。
May, 2023
研究在异质奖励方差的固定预算设置下的最佳臂识别问题,提出两种方差自适应的算法:SHVar和SHAdaVar,分别用于已知奖励方差和未知奖励方差情况下,通过不均匀预算分配实现对高方差臂的偏好,本文还给出了误判最佳臂的概率界限。
Jun, 2023
介绍了具有线性反馈的安全最优臂识别框架,代理受到一些在未知参数向量上线性相关的逐阶段安全约束的限制,代理必须以保守的方式采取行动,以确保在每一轮中不违反安全约束的概率较高。提出了一种基于间隙的算法,实现了有意义的样本复杂度,同时确保逐阶段的安全性。通过实验说明了算法设计的合理性。
Sep, 2023
我们提出了三批最佳臂识别(Tri-BBAI)算法和几乎最优的批量最佳臂识别(Opt-BBAI)算法,分别在渐近和非渐近设置中实现了最优的样本复杂度和批量复杂度,并设计了一种独立的程序来检查是否消除了最佳臂。
Oct, 2023