研究最优臂辨识问题,发现新算法和上下限优化,并提出一个新的关于最优样本复杂度的猜想。
Nov, 2015
本文探讨了 Best-$k$-Arm 问题的样本复杂性边界,提出了一种新颖的复杂度度量方法和基于消除的算法,并展示了该算法的实例 - 边界下限和状态 - 界限的严格支配能力。
Feb, 2017
提出多臂老虎机算法中两个问题:如何识别平均值与最大平均值相差小于给定阈值的武器和如何识别平均值大于给定阈值的 k 支武器。在此基础上,给出了形式化的定义,匹配了样本复杂度的下界,并提供了几乎匹配上界的具体实用算法。
Jun, 2019
考虑在 $[0,1]$ 区间上的 $K$ 个臂构成的随机赌博机下,使用有限的轮次 $T$ 定位最佳赌博机的问题,证明了在该问题中误判率的最低下界。同时,该结论证明了基于臂的连续拒绝(Successive Rejection)的算法是最优的,填补了固定预算下最佳臂定位问题的上下限差距。
May, 2016
针对最佳臂识别问题,本文提出了一种基于阈值的最优排名算法,通过对强度的函数分配进行采样来识别最佳臂,分析表明该算法在极限情况下是最优的。
Mar, 2024
研究了如何在随机赌博机游戏中选择期望回报最高的 K 个赌臂问题,提出了一种基于概率近似正确算法,并引入了难度参数来量化问题难度。通过研究两种算法的采样复杂度,得出了更优的上界,并证明了该上界在某些情况下是紧的。同时得出了引入难度参数的实例相关算法需要额外的对数因子作为代价的下界。
Jun, 2017
在本文中,我们研究多信度最佳臂识别问题,通过提出一种以梯度为基础的方法,我们找到了具有渐近最优成本复杂度的解决方案,并针对每个臂还提出了最优保真度的概念。
Jun, 2024
本文研究了纯探索问题中具有无限多臂的赌博机问题,针对固定置信和固定预算两种情形,提出了两种算法,分别以最小的期望和固定样本复杂度为目标,最终准确选择一个高质量臂,使其平均奖励与前 $η$ 的部分的奖励最大值的差别小于 $ε$,并给出了理论证明。
Jun, 2023
提出了一种新的随机多臂老虎机问题称为好臂识别,在解决好臂识别过程中面临独特的置信度的探索 - 利用困境并为此提出了一种算法以最小化每个过程的样本数量,该算法在样本复杂度上达到了理论下限并已通过实验得到验证。
Oct, 2017
该论文研究带有重叠假设的顺序检测问题,在考虑一些特定的问题,如评估高斯分布的平均值是否小于或大于固定值时,我们提供了概率近似正确的最佳臂识别算法的复杂度,还在更加通用的测试问题上提出了一个并行广义似然比测验的非渐近误差上界,并根据信息论提出了更改度量引理的两个版本,进而提出了识别正确假设所需观察次数的下界。
May, 2019