Nov, 2014

有限臂结构赌博机的有界遗憾

PDF
TL;DR研究了一种新型的 K 武装强盗问题，介绍了一种针对这一问题的新算法，并展示了在特定条件下可以实现有限的预期累计遗憾，同时提供了依赖于问题的累计遗憾下限，显示出至少在某些特殊情况下，新算法是近乎最优的。
k-armed bandit problemalgorithmexpected cumulative regretproblem-dependent lower bounds
发现论文，激发创造
  • 优化置信区间上界算法：改进有限臂赌博机的遗憾

    提出了一种基于 UCB 并具有适当的置信参数平衡风险和过度乐观代价的随机有限臂老虎机算法，同时具有最优问题依赖性遗憾和最坏情况遗憾。

    Jul, 2015

  • 无限臂老虎机的简单遗憾

    本文针对无穷臂随机赌博机问题，提出一种算法用以最小化简单损失，并扩展到多种情况下，如未知时间跨度等。

    May, 2015

  • 探索先行，利用随后：强盗问题中后悔的真实形状

    本文研究多臂老虎机问题的遗憾下界，并利用 Kullback-Leibler 分歧的已知特性证明了非相对论、分布依赖的限制。这些限制特别表明，在初始阶段遗憾几乎线性增长，并且在最后阶段仅出现知名的对数增长。证明技术突出了信息理论论证的本质，并去除了所有不必要的复杂性。

    Feb, 2016

  • 多种最佳臂的遗憾问题

    本篇论文旨在应对多臂赌博机问题中存在多个最优 / 近似最优机械臂的后悔最小化问题，通过提出自适应算法来自动适应问题的难度，并在理论和实验方面展现了该算法的优越性。

    Jun, 2020

  • 批处理赌博机的遗憾界

    本文提出了一种简单有效的算法来解决批处理随机多臂赌博机和线性随机多臂赌博机问题，这些算法能够通过只使用对数数量的批次实现最优期望遗憾界，此外，文章还首次研究了批处理对抗性多臂赌博机问题，并发现了任何算法的最佳遗憾界（对数因子除外）的预定批处理大小。

    Oct, 2019

  • Dueling Bandit 问题的遗憾下限和最优算法

    本文研究了 K-armed dueling bandit 问题，提出了一种受 Deterministic Minimum Empirical Divergence 算法启发的算法，并得到了匹配下界的后悔上界，实验结果表明该算法明显优于现有算法。

    Jun, 2015

  • 非精确多臂赌博机

    我们引入了一种新颖的多臂赌博问题框架，其中每个臂与一个固定的未知置信集相关联，覆盖了结果空间（可以比奖励更丰富）。臂 - 置信集对应关系来自已知的假设类。我们定义了一种与这些置信集定义的下概率相对应的遗憾概念。等价地，这个设置可以被视为一个两人零和博弈，其中在每一轮中，代理选择一个臂，对手从与该臂相关联的选择集中选择结果分布。遗憾是相对于游戏价值定义的。对于某些自然的假设类，这些类类似于随机线性赌博问题（是结果设置的特殊情况），我们提出了一个算法并证明了遗憾的上界。我们还证明了特定特殊情况下的遗憾下界。

    May, 2024

  • 多臂赌博问题的纯探索

    研究随机多臂老虎机问题的性质和限制，探讨具有在线探索特性的预测器的表现，其中简单后悔被评估，讨论简单后悔与累计后悔的关系，在有限臂数的情况下展示了一种性能下限和预测器的上限后悔，并针对连续老虎臂问题进行了研究。

    Feb, 2008

  • 随机多臂赌博机中的广义风险厌恶

    探讨了在多臂赌博机中最小化遗憾的问题，其中臂的好坏度量不是平均回报率，而是平均值和方差的某个通用函数，特征化了学习可能的条件，并展示了对于某些情况自然算法无法实现亚线性遗憾的例子。

    May, 2014

  • 对抗性赌博机的改进下界

    该研究提供了敌对强盗算法必须遭受的遗憾的新的下界，并证明了对于最佳臂的总损失或损失的二次变化的上界是接近紧的。此外，研究还证明了两个不可能的结果，即单臂最优和遗憾不能随损失范围的提高而扩展。相比之下，在完全信息设置中这两个结果是可能的。

    May, 2016