Aug, 2023

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

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

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

    May, 2016

  • 合作非随机多臂老虎机中的个体遗憾

    研究通过交换信息在底层网络上通信的代理，以优化共同的非随机多臂赌博问题中各自的遗憾。我们推导出遗憾最小化算法，其中保证每个代理 v 的期望遗憾都是（1+K/|N (v)|)^T 的平方根量级。

    Jul, 2019

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

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

    Feb, 2013

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

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

    Dec, 2011

  • 批处理赌博机的遗憾界

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

    Oct, 2019

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

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

    Jun, 2015

  • 具有异构奖励的分散随机分布的多智能体多臂赌博机

    研究了去中心化多智能体多臂赌博问题，使用随机图来优化整个系统的综合悔恨度，引入了新的算法框架，其中包含加权技巧和上置信边界方法，算法具有较好的鲁棒性，并且考虑了图随机性，同时给出了不同命题下的悔恨度的上限。

    Jun, 2023

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

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

    Feb, 2016

  • 带专家建议的强盗问题的改进遗憾界限

    通过受限反馈模型，本研究提供了关于 “专家建议问题” 的最坏情况后悔度的新的下界和上界，其中下界为 O (sqrt (KT ln (N/K)))，上界与之相匹配，并改进了现有最佳下界 sqrt (KT (ln N) / (ln K))。同时，对于标准反馈模型，本研究提供了一种新的基于实例的上界，该上界取决于专家之间的一致性，并相比之前的结果提供了对数级的改进。

    Jun, 2024

  • 博弈中协作学习的最优遗憾界

    我们研究了在一个通用的协作多智能体多臂老虎机模型中的遗憾最小化问题，在该模型中，每个智能体面临一个有限的臂集，并可以通过一个中央控制器与其他智能体进行通信。该模型中每个智能体的最优臂是具有最大期望混合奖励的臂，其中每个臂的混合奖励是其在所有智能体之间的奖励的加权平均，这使得智能体之间的通信至关重要。尽管在这个协作模型下已知最优臂识别的近似复杂度，但最优遗憾问题仍然是开放的。在这项工作中，我们解决了这个问题，并提出了第一个在这个协作老虎机模型下具有最优遗憾界限的算法。此外，我们还展示了只需要一个小的常数期望通信轮数。

    Dec, 2023