联合界的经验过程方法:用于组合式和线性赌博机的实用算法
本文提出了两种渐近最优的算法,基于 Track-and-Stop 方法和博弈论方法,用于寻找多臂赌博机环境中具有一定置信度的最优策略,特别考虑了带有线性约束的情况,并探讨了约束难度对问题的影响。
Jun, 2023
本文研究了随机线性武装的固定置信度下的最佳武器识别问题,目标是在最小化采样预算的同时确定最佳武器。设计了一种简单的算法,其采样复杂度与已知的特定实例下界匹配,在几乎必然的情况下一致性和期望上。此算法依赖于跟踪最佳比例的武器采样规则,而且可以很少更新而不影响其理论保证。此外,与现有的最佳武器识别策略不同,我们的算法使用的停止规则不依赖于武器数量。实验结果表明,我们的算法明显优于现有算法。本文还对具有连续武器集的线性武装的最佳武器识别问题进行了首次分析。
Jun, 2020
本文研究了纯探索问题中具有无限多臂的赌博机问题,针对固定置信和固定预算两种情形,提出了两种算法,分别以最小的期望和固定样本复杂度为目标,最终准确选择一个高质量臂,使其平均奖励与前 $η$ 的部分的奖励最大值的差别小于 $ε$,并给出了理论证明。
Jun, 2023
本文主要研究的问题是:如何在样本预算有限的情况下,统一地估计多个分布的平均值。通过采集数量,可以根据它们的方差为已知来设计最优的采样策略,但在更实际的情况下,需要设计自适应采样策略来选择要采样的分布(根据先前观察到的样本)。文章描述了两种策略,根据样本数据以高概率上限置信界为比例,拉动分布并报告相对于最优配置的过度估计误差的有限样本性能分析。我们表明这些分配策略的性能不仅取决于方差还取决于分布的完整形状。
Jul, 2015
在固定预算环境下,我们研究了多臂赌博机的实值组合纯探索问题。我们提出了 Combinatorial Successive Asign(CSA)算法,该算法可以在动作类别的大小与臂的数量成指数关系时,找到最佳动作。我们证明了 CSA 算法的错误概率上界与下界在指数的对数因子上匹配。然后,对于动作类别大小为多项式的情况,我们引入了另一个算法 Minimax Combinatorial Successive Accepts and Rejects(Minimax-CombSAR),并证明该算法是最优的,与一个下界相匹配。最后,我们通过与先前方法的实验比较,证明了我们的算法表现更好。
Oct, 2023
本研究旨在探讨一种新颖的纯探索问题:在随机线性赌臂问题中具有固定置信度的 ε- 阈值赌臂问题(TBP)。我们证明了采样复杂度的下界,并将一种设计用于解决线性情况下的最佳臂识别问题的算法扩展到了 TBP 问题中,该算法是渐近最优的。
Feb, 2024
本文提出一种基于启发式算法的无参数算法,用于解决特定的组合纯探索随机赌博机问题,以寻找一组平均值高于给定阈值的摇臂,满足给定精度和一定的时间限制,并证明该算法是情况下的最优解决方案,并提供了相应的上下界。本文是首个针对纯探索设置的固定预算问题,并构建了最优策略。
May, 2016
本文提出了第一个完全自适应的算法用于求解线性赌博机中的最优选择问题,并且其采样复杂度与已有算法相当。此外,通过模拟实验表明,在合成和真实数据集上均远优于现有的方法。
Oct, 2017
在多臂老虎机游戏中,利用少量样本通过固定置信度水平下的置信区间,提出了一种最初的置信上界算法,该算法使用的样本数量与基于迭代对数定理的下限相比仅相差常数因子,同时使用了一种新的停止时间来避免在其他上置界型算法中观察到的臂联合的界限,从而进一步优化了算法,并通过模拟证明了算法的性能。
Dec, 2013