When to Call Your Neighbor? Strategic Communication in Cooperative Stochastic Bandits
When to Call Your Neighbor? Strategic Communication in Cooperative Stochastic Bandits
复制标题
什么时候给你的邻居打电话？
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
N. Leonard
中科院分区：
文献类型：
--
作者：
Udari Madhushani;N. Leonard
在协作盗匪（cooperative bandits）中，一个捕捉集体顺序决策基本特征的框架中，代理可以通过利用共享信息，将群体后悔最小化，从而提高绩效。然而，共享信息可能是昂贵的，这促使开发最小化群体后悔的策略，同时也减少了代理之间沟通的信息数量。现有的协作盗匪算法在agent与相邻agent在\textit{每个时间步}共享信息，即充分通信时获得最优性能。这需要$\Theta(T)$数量的消息，其中$T$是决策过程的时间范围。我们提出了\textit{ComEx}，一种新颖的具有成本效益的通信协议，在该协议中，组在仅通信$O(\log T)$消息数量的情况下实现与完全通信相同的性能顺序。我们的关键步骤是开发一种方法来识别并仅传达对实现最佳性能至关重要的信息。此外，我们为几个基准合作强盗框架提出了新的算法，并表明我们的算法获得了\textit{最}先进的性能，同时始终比现有算法产生更小的通信成本。
In cooperative bandits, a framework that captures essential features of collective sequential decision making, agents can minimize group regret, and thereby improve performance, by leveraging shared information. However, sharing information can be costly, which motivates developing policies that minimize group regret while also reducing the number of messages communicated by agents. Existing cooperative bandit algorithms obtain optimal performance when agents share information with their neighbors at \textit{every time step}, i.e., full communication. This requires $\Theta(T)$ number of messages, where $T$ is the time horizon of the decision making process. We propose \textit{ComEx}, a novel cost-effective communication protocol in which the group achieves the same order of performance as full communication while communicating only $O(\log T)$ number of messages. Our key step is developing a method to identify and only communicate the information crucial to achieving optimal performance. Further we propose novel algorithms for several benchmark cooperative bandit frameworks and show that our algorithms obtain \textit{state-of-the-art} performance while consistently incurring a significantly smaller communication cost than existing algorithms.
合作多臂强盗中的社会模仿：具有严格本地信息的基于分区的算法
DOI：
10.1109/cdc.2018.8619744
发表时间：
2018
期刊：
2018 IEEE Conference on Decision and Control
影响因子：
--
作者：
Landgren, Peter;Srivastava, Vaibhav;Ehrich Leonard, Naomi
通讯作者：
Ehrich Leonard, Naomi
DOI：
10.1109/focs.2019.00017
发表时间：
2019-04
期刊：
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
Chao Tao;Qin Zhang;Yuanshuo Zhou
通讯作者：
Chao Tao;Qin Zhang;Yuanshuo Zhou