针对组合多臂赌博机问题中的非线性奖励函数和批处理选择,引入一种新的平滑度标准 —— 基尼加权平滑度,证明了现有算法中的线性后悔量与批大小的关系可以被该平滑度参数取代,并在概率最大覆盖问题中获得了明显的精度提高。
May, 2019
本文提出了一种适用于多臂赌博机问题的解决方案,只需要以线性时间复杂度存储未知参数,可以处理一般的掌握参数相关性的问题,并用于对网络中的最大权匹配、最短路径及最小生成树计算问题的解决。
Nov, 2010
研究了在最大价值和指标反馈下的组合多臂赌博问题,并提出一种算法来保证概率有限支持中随机手臂结果的遗憾。
May, 2023
本篇论文旨在应对多臂赌博机问题中存在多个最优 / 近似最优机械臂的后悔最小化问题,通过提出自适应算法来自动适应问题的难度,并在理论和实验方面展现了该算法的优越性。
Jun, 2020
本文研究了随机和对抗性组合多臂赌博问题。在随机情况下,我们提出了一种特定问题的遗憾下限,并讨论了其与决策空间维数的比例关系。我们提出了 ESCB 算法,该算法能有效地利用问题的结构,并对其遗憾进行了有限时间分析。ESCB 具有比现有算法更好的性能保证,并在实践中显着优于这些算法。在对抗性情况下,我们提出了 CombEXP 算法,其遗憾比比现有最先进算法相同,但对于某些组合问题具有较低的计算复杂度。
Feb, 2015
该研究提供了敌对强盗算法必须遭受的遗憾的新的下界,并证明了对于最佳臂的总损失或损失的二次变化的上界是接近紧的。此外,研究还证明了两个不可能的结果,即单臂最优和遗憾不能随损失范围的提高而扩展。相比之下,在完全信息设置中这两个结果是可能的。
May, 2016
本文考虑了带障碍的多臂赌博机问题中,包含组合优化的情况下解决局部最优策略的方法。我们扩展了现有模型,使得多个手臂可以按照可行性约束同时进行决策。本文提出了一种自然的贪心算法,并针对其在多种情况下的表现给出了严格的理论保证。
May, 2021
研究了随机多臂老虎机问题,通过一个单峰函数来表示不完全有序的臂的期望奖励。对于离散和连续臂的情况,分别提出了 OSUB 和 UCB 算法,并得到了渐进的上下界和提高性能的实验结果。
May, 2014
考虑到重复使用某些选项可能是不可取的或不可行的,本文提出了一种新颖的随机多臂赌博机设置,并通过映射到 PINWHEEL 调度问题证明了问题的优化累积奖励不允许有伪多项式时间算法,但它设计了一种贪婪算法和一种基于 UCB 的算法,具有一定的优异性。
Jul, 2019
介绍了一个基于线性回归的优化算法,用于解决组合随机半汉带问题中的依赖关系,分析证明其是最优的,并且推出了一个与被拉动手臂数的对数因子成比例的新的下界。
Dec, 2016