关于最佳臂识别的最优样本复杂度
解决乐观抽样的样本复杂度问题,提出了一种高度非平凡的算法来提供最大均值臂的实例 wise 样本复杂度上界,同时对于任意的高斯贝叶斯多臂老虎机有一定的下界。
Aug, 2016
本文探讨了 Best-$k$-Arm 问题的样本复杂性边界,提出了一种新颖的复杂度度量方法和基于消除的算法,并展示了该算法的实例 - 边界下限和状态 - 界限的严格支配能力。
Feb, 2017
本文研究了随机线性武装的固定置信度下的最佳武器识别问题,目标是在最小化采样预算的同时确定最佳武器。设计了一种简单的算法,其采样复杂度与已知的特定实例下界匹配,在几乎必然的情况下一致性和期望上。此算法依赖于跟踪最佳比例的武器采样规则,而且可以很少更新而不影响其理论保证。此外,与现有的最佳武器识别策略不同,我们的算法使用的停止规则不依赖于武器数量。实验结果表明,我们的算法明显优于现有算法。本文还对具有连续武器集的线性武装的最佳武器识别问题进行了首次分析。
Jun, 2020
本文研究线性贝叶斯最优化模型中的最优臂选择问题,提出样本分配策略来识别具有固定置信度的最优臂,并在最小化样本预算的同时改进了全局线性结构估计附近最优臂的奖励值,并将其与最优实验设计中使用的 G - 最优准则进行比较。
Sep, 2014
本研究完整表征了单参数赌博机问题中最优臂识别的复杂度,并提出了一种被称作 “Track-and-Stop” 的策略,该策略通过的新采样规则和所提出的 Chernoff 停止规则被证明是渐近最优的,并在样本复杂度上取得了一个新的紧致下界。
Feb, 2016
研究了多臂赌博机问题中学习者在选择臂时精度受限的变体,并且给出了期望停留时间的渐近下限并提出了一种修改后的算法用于处理非唯一最优配置,并且针对在简单的情况下访问不重叠臂的情况给出了非渐近下限和上限。
May, 2023
提出多臂老虎机算法中两个问题:如何识别平均值与最大平均值相差小于给定阈值的武器和如何识别平均值大于给定阈值的 k 支武器。在此基础上,给出了形式化的定义,匹配了样本复杂度的下界,并提供了几乎匹配上界的具体实用算法。
Jun, 2019
研究了如何在随机赌博机游戏中选择期望回报最高的 K 个赌臂问题,提出了一种基于概率近似正确算法,并引入了难度参数来量化问题难度。通过研究两种算法的采样复杂度,得出了更优的上界,并证明了该上界在某些情况下是紧的。同时得出了引入难度参数的实例相关算法需要额外的对数因子作为代价的下界。
Jun, 2017
本文在稳健统计学的背景下研究主动学习。具体而言,我们为受到污染的赌臂问题提出了一个变体,其中每个臂的拉动具有生成任意污染分布样本的概率 ε,而不是真正的基础分布。我们开发了紧凑的、非渐进的样本复杂度界限来高概率地估算受到污染的样本的前两个鲁棒矩(中位数和中位数绝对偏差)。利用这些结果,我们将几个经典的最佳臂识别算法适应于受到污染的赌臂环境,并为我们的问题导出样本复杂度上限。最后,我们提供了关于样本复杂度(最多小的对数因子)的匹配信息论下界。
Feb, 2018