线性约束下的纯探索赌博机问题
本文研究了随机线性武装的固定置信度下的最佳武器识别问题,目标是在最小化采样预算的同时确定最佳武器。设计了一种简单的算法,其采样复杂度与已知的特定实例下界匹配,在几乎必然的情况下一致性和期望上。此算法依赖于跟踪最佳比例的武器采样规则,而且可以很少更新而不影响其理论保证。此外,与现有的最佳武器识别策略不同,我们的算法使用的停止规则不依赖于武器数量。实验结果表明,我们的算法明显优于现有算法。本文还对具有连续武器集的线性武装的最佳武器识别问题进行了首次分析。
Jun, 2020
本文研究线性贝叶斯最优化模型中的最优臂选择问题,提出样本分配策略来识别具有固定置信度的最优臂,并在最小化样本预算的同时改进了全局线性结构估计附近最优臂的奖励值,并将其与最优实验设计中使用的 G - 最优准则进行比较。
Sep, 2014
探讨了利用 Adaptive Constraint Learning 算法解决具有昂贵人类偏好未知约束的序列决策问题,特别是在驾驶行为中体现的安全和舒适性约束的识别,该算法在驾驶模拟中比其他算法更加高效
Jun, 2022
本研究完整表征了单参数赌博机问题中最优臂识别的复杂度,并提出了一种被称作 “Track-and-Stop” 的策略,该策略通过的新采样规则和所提出的 Chernoff 停止规则被证明是渐近最优的,并在样本复杂度上取得了一个新的紧致下界。
Feb, 2016
研究了多臂赌博机问题中学习者在选择臂时精度受限的变体,并且给出了期望停留时间的渐近下限并提出了一种修改后的算法用于处理非唯一最优配置,并且针对在简单的情况下访问不重叠臂的情况给出了非渐近下限和上限。
May, 2023
考虑在无限臂赌博机问题的固定置信度设置下,当不知道臂储备分布时,近似最优臂识别的问题。我们引入了类 PAC 的框架来推导和表述结果;推导了近似最优臂识别的样本复杂度下界;提出了一个算法,以高概率识别出一个接近最优的臂,并推导出其样本复杂度的上界,该上界比我们的下界小一个对数因子;并讨论了我们的 log^2 (1/delta) 依赖是否不可避免地适用于无限设置的 “两阶段” (先选择臂,后识别最佳)算法。这项工作允许将赌徒模型应用于更广泛的问题类别,其中较少的假设成立。
Mar, 2018
本文研究了一个约束的上下文线性赌博机问题,提出了一种算法 OPLB 并证明了其 T 轮后悔度的上限,针对多臂赌博机情况提出了高效算法,同时给出了问题的下限和模拟结果。
Jun, 2020
本文提出了一种基于 UCB 策略的新算法 Safe-LUCB,用于解决多臂赌博问题中考虑安全限制的约束,该算法具有探索和利用两个阶段,并控制遗憾值增长,提供了一般遗憾上界及与最佳行动位置有关的问题相关遗憾上界。
Aug, 2019
本文提出了一种适用于多臂赌博机问题的解决方案,只需要以线性时间复杂度存储未知参数,可以处理一般的掌握参数相关性的问题,并用于对网络中的最大权匹配、最短路径及最小生成树计算问题的解决。
Nov, 2010