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

Dec, 2023

Optimal Regret Bounds for Collaborative Learning in Bandits

Amitis Shidani, Sattar Vakili

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

Abstract

We consider regret minimization in a general collaborative multi-agent multi-armed bandit model, in which each agent faces a finite set of arms and may communicate with other agents through a central controller. The optimal arm for each agent in this model is the arm with the largest e

regret minimization collaborative multi-agent multi-armed bandit communication optimal regret bounds expected communication rounds

发现论文，激发创造

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

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

Jul, 2019

合作多智能体赌博机：优化个体懊悔并具有恒定通讯开销的分布式算法

合作多智能体多臂赌博算法中的通信策略，既实现了最优个体遗憾，又具有恒定的通信成本。

Aug, 2023

协作多智体异构多臂赌博机

研究多人合作多智能体赌博问题，提出一种新的多人合作环境，并利用分散式演算法促进代理之间的合作，推导每个代理的累积遗憾度和群体的遗憾度上下限，并证明了该算法的近似最优行为。

May, 2023

多种最佳臂的遗憾问题

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

Jun, 2020

去中心化协作随机赌博机

本文研究了多臂赌博机问题在网络上的去中心化协作，采用加速一致性过程来计算所有智能体对每个臂的平均奖励，该算法采用上置信区间来决策，能够达到更好的回归界，同时不需要过多的底层网络信息。

Oct, 2018

公平最优多智能体赌博机

研究多智能体多臂赌博学习问题，以无通信和有限奖励为前提，提出了一种分布式拍卖算法并进行样本最优匹配学习和新的拍卖决策策略，通过新颖的基于次序统计量的后悔分析带来了全新的性能，实验模拟表明性能依赖于对数时间。

Jun, 2023

多智能体赌博机的闲语插入 - 排除算法

该论文研究了多智能体多臂赌博机模型下的协作问题，提出了两个算法，通过交换信息来降低每个智能体的累计损失，理论证明通过最小的信息交互次数可以在不增加损失上极大地提高算法性能。

Jan, 2020

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

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

Jun, 2015

多智能体多臂赌博机中的社交学习

介绍了一个分布式算法来解决多臂赌博机问题，通过异步交换较少的比特数，在不进行样本交换的情况下，仅通过传递臂 ID 来维护代理之间的合作；文中提出的算法可以将每个代理的后悔最小化，并将通信复杂度降至 $O (logT)$，与不进行合作的方案相比，本算法能够显著降低每个代理的后悔。

Oct, 2019

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

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

Aug, 2023