Oct, 2019

批处理赌博机的遗憾界

PDF
TL;DR本文提出了一种简单有效的算法来解决批处理随机多臂赌博机和线性随机多臂赌博机问题，这些算法能够通过只使用对数数量的批次实现最优期望遗憾界，此外，文章还首次研究了批处理对抗性多臂赌博机问题，并发现了任何算法的最佳遗憾界（对数因子除外）的预定批处理大小。
stochastic multi-armed banditstochastic linear banditbatched algorithmsexpected regret boundsadversarial multi-armed bandit
发现论文，激发创造
  • 批次赌博机问题

    简要摘要：本文研究小批量策略下随机赌博机问题的后悔，提出一种简单策略并证明合理情况下批量数量很小即可达到极小极大后悔度界限，同时推导得到低转换成本下的最优随机赌博机策略。

    May, 2015

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

    研究了一种新型的 K 武装强盗问题，介绍了一种针对这一问题的新算法，并展示了在特定条件下可以实现有限的预期累计遗憾，同时提供了依赖于问题的累计遗憾下限，显示出至少在某些特殊情况下，新算法是近乎最优的。

    Nov, 2014

  • 组合多臂老虎机问题的批量独立遗憾界

    针对组合多臂赌博机问题中的非线性奖励函数和批处理选择，引入一种新的平滑度标准 —— 基尼加权平滑度，证明了现有算法中的线性后悔量与批大小的关系可以被该平滑度参数取代，并在概率最大覆盖问题中获得了明显的精度提高。

    May, 2019

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

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

    May, 2016

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

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

    May, 2015

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

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

    Feb, 2016

  • 多智能体多臂赌博机中的遗憾下界

    在多臂赌博机领域，多智能体多臂赌博机方法已经受到了广泛关注，但对应的遗憾下界的研究相对较少。本文在不同情景下首次全面研究了遗憾下界，并证明了它们的紧密性。当图表现出良好的连通性和奖励是随机分布时，我们证明了实例相关上界的 O（log T）下界和平均差值独立上界的 sqrt（T）下界。在对抗奖励的假设下，我们建立了连接图的 O（T^（2/3））下界，从而弥合了以前工作中下界与上界之间的差距。当图表现为不连通时，我们还展示了线性的遗憾下界。与以前的研究相比，本文全面研究了这些情景下的紧密下界。

    Aug, 2023

  • 随机多臂赌博问题的遗憾下界和拓展上置信界策略

    通过对经典多臂赌博机（Stochastic Multi-Armed Bandit）的研究，探讨了两种不同的准则下存在的遗憾下界。同时，研究了 UCB 等算法的变体，证明了这种情况下不可能设计一种自适应的策略来选择最优算法。

    Dec, 2011

  • 多种最佳臂的遗憾问题

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

    Jun, 2020

  • 随机多臂赌博机的有限遗憾

    研究解决在已知最优的选择和最小间隔值时如何制定随机化策略，以解决随机多臂赌博问题中可能发生的后悔问题，并探讨了其下界和最优解等问题。

    Feb, 2013