寻找众数中的最大平均值
本文探讨了Best-$k$-Arm问题的样本复杂性边界,提出了一种新颖的复杂度度量方法和基于消除的算法,并展示了该算法的实例-边界下限和状态-界限的严格支配能力。
Feb, 2017
本文研究了随机多臂老虎机的组合纯探索问题,提出了一种新的样本复杂度的下界和一种新的抽样算法,并用于凸优化的分离与优化等价和近似 Pareto 曲线等技术改进了多个普遍应用的组合约束条件的纯探索问题的已有方法。此外,我们还提出了更通用的问题,并针对其提供了样本复杂度的上下界。
Jun, 2017
本文在稳健统计学的背景下研究主动学习。具体而言,我们为受到污染的赌臂问题提出了一个变体,其中每个臂的拉动具有生成任意污染分布样本的概率 ε,而不是真正的基础分布。我们开发了紧凑的、非渐进的样本复杂度界限来高概率地估算受到污染的样本的前两个鲁棒矩(中位数和中位数绝对偏差)。利用这些结果,我们将几个经典的最佳臂识别算法适应于受到污染的赌臂环境,并为我们的问题导出样本复杂度上限。最后,我们提供了关于样本复杂度(最多小的对数因子)的匹配信息论下界。
Feb, 2018
本文研究自适应地从 K 个分布(臂)中抽样,以确定任意两个相邻均值之间的最大差距,即最大间隙赌博机问题。作者提出消除与UCB风格的算法,并证明了它们是极小化的最优解。实验结果表明,UCB风格的算法需要的样本数量比非自适应抽样少6-8倍。
Jun, 2019
提出多臂老虎机算法中两个问题:如何识别平均值与最大平均值相差小于给定阈值的武器和如何识别平均值大于给定阈值的k支武器。在此基础上,给出了形式化的定义,匹配了样本复杂度的下界,并提供了几乎匹配上界的具体实用算法。
Jun, 2019
本文研究了随机线性武装的固定置信度下的最佳武器识别问题,目标是在最小化采样预算的同时确定最佳武器。设计了一种简单的算法,其采样复杂度与已知的特定实例下界匹配,在几乎必然的情况下一致性和期望上。此算法依赖于跟踪最佳比例的武器采样规则,而且可以很少更新而不影响其理论保证。此外,与现有的最佳武器识别策略不同,我们的算法使用的停止规则不依赖于武器数量。实验结果表明,我们的算法明显优于现有算法。本文还对具有连续武器集的线性武装的最佳武器识别问题进行了首次分析。
Jun, 2020
通过大偏差原理,我们在适应性算法中建立了样本抽取比例与样本奖励之间的联系,从而改进了现有算法并设计了新算法,我们证明了新算法的性能优于现有算法,包括对众多抽样的广泛实验证实了这一观察结果。
Dec, 2023