Collaborative Multi-Agent Heterogeneous Multi-Armed Bandits

• URL: http://arxiv.org/abs/2305.18784v2
• Date: Tue, 2 Jul 2024 23:21:45 GMT
• Title: Collaborative Multi-Agent Heterogeneous Multi-Armed Bandits
• Authors: Ronshee Chawla, Daniel Vial, Sanjay Shakkottai, R. Srikant,
• Abstract summary: We study a new collaborative setting, consisting of $N$ agents such that each agent is learning one of $M$ multi-armed bandits. We develop algorithms which facilitate collaboration between the agents under two scenarios.
• Score: 24.590517939890788
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The study of collaborative multi-agent bandits has attracted significant attention recently. In light of this, we initiate the study of a new collaborative setting, consisting of $N$ agents such that each agent is learning one of $M$ stochastic multi-armed bandits to minimize their group cumulative regret. We develop decentralized algorithms which facilitate collaboration between the agents under two scenarios. We characterize the performance of these algorithms by deriving the per agent cumulative regret and group regret upper bounds. We also prove lower bounds for the group regret in this setting, which demonstrates the near-optimal behavior of the proposed algorithms.

Related papers

• Multi-Agent Stochastic Bandits Robust to Adversarial Corruptions [6.234292942334148]
  We propose a multi-agent cooperative learning algorithm that is robust to adversarial corruptions. As a side-product, our algorithm also improves the state-of-the-art regret bounds when reducing to both the single-agent and homogeneous multi-agent scenarios.
  arXiv  Detail & Related papers  (2024-11-12T20:20:26Z)
• Best Arm Identification with Minimal Regret [55.831935724659175]
  Best arm identification problem elegantly amalgamates regret minimization and BAI. Agent's goal is to identify the best arm with a prescribed confidence level. Double KL-UCB algorithm achieves optimality as the confidence level tends to zero.
  arXiv  Detail & Related papers  (2024-09-27T16:46:02Z)
• Clustered Multi-Agent Linear Bandits [5.893124686141782]
  We address a particular instance of the multi-agent linear bandit problem, called clustered multi-agent linear bandits. We propose a novel algorithm leveraging an efficient collaboration between the agents in order to accelerate the overall optimization problem.
  arXiv  Detail & Related papers  (2023-09-15T19:01:42Z)
• On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring [105.13668993076801]
  A central problem in the theory of multi-agent reinforcement learning (MARL) is to understand what structural conditions and algorithmic principles lead to sample-efficient learning guarantees. We study this question in a general framework for interactive decision making with multiple agents. We show that characterizing the statistical complexity for multi-agent decision making is equivalent to characterizing the statistical complexity of single-agent decision making.
  arXiv  Detail & Related papers  (2023-05-01T06:46:22Z)
• Learning Reward Machines in Cooperative Multi-Agent Tasks [75.79805204646428]
  This paper presents a novel approach to Multi-Agent Reinforcement Learning (MARL) It combines cooperative task decomposition with the learning of reward machines (RMs) encoding the structure of the sub-tasks. The proposed method helps deal with the non-Markovian nature of the rewards in partially observable environments.
  arXiv  Detail & Related papers  (2023-03-24T15:12:28Z)
• On Regret-optimal Cooperative Nonstochastic Multi-armed Bandits [7.23389716633927]
  We show that a collaborative multi-agent emphfollow-the-regularized-leader (FTRL) algorithm has an individual regret upper bound that matches the lower bound up to a constant factor. We also show that an FTRL algorithm with a suitable regularizer is regret optimal with respect to the scaling with the edge-delay parameter.
  arXiv  Detail & Related papers  (2022-11-30T16:46:41Z)
• Multi-agent Deep Covering Skill Discovery [50.812414209206054]
  We propose Multi-agent Deep Covering Option Discovery, which constructs the multi-agent options through minimizing the expected cover time of the multiple agents' joint state space. Also, we propose a novel framework to adopt the multi-agent options in the MARL process. We show that the proposed algorithm can effectively capture the agent interactions with the attention mechanism, successfully identify multi-agent options, and significantly outperforms prior works using single-agent options or no options.
  arXiv  Detail & Related papers  (2022-10-07T00:40:59Z)
• Distributed Bandits with Heterogeneous Agents [38.90376765616447]
  This paper tackles a multi-agent bandit setting where $M$ agents cooperate together to solve the same instance of a $K$-armed bandit problem. We propose two learning algorithms, ucbo and AAE. We prove that both algorithms achieve order-optimal regret, which is $Oleft(sum_i:tildeDelta_i>0 log T/tildeDelta_iright)$, where $tildeDelta_i$ is the minimum suboptimality gap between the reward mean of
  arXiv  Detail & Related papers  (2022-01-23T20:04:15Z)
• Max-Min Grouped Bandits [48.62520520818357]
  We introduce a multi-armed bandit problem termed max-min grouped bandits. The goal is to find a group whose worst arm has the highest mean reward. This problem is of interest to applications such as recommendation systems.
  arXiv  Detail & Related papers  (2021-11-17T01:59:15Z)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  We consider the Multi-Armed Bandit (MAB) problem, where an agent sequentially chooses actions and observes rewards for the actions it took. While the majority of algorithms try to minimize the regret, i.e., the cumulative difference between the reward of the best action and the agent's action, this criterion might lead to undesirable results. We suggest a new, more lenient, regret criterion that ignores suboptimality gaps smaller than some $epsilon$.
  arXiv  Detail & Related papers  (2020-08-10T08:30:52Z)
• The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits [20.259428328004738]
  We consider a decentralized multi-agent Multi Armed Bandit (MAB) setup consisting of $N$ agents. In our model, agents collaborate by exchanging messages through pairwise gossip style communications on an arbitrary connected graph.
  arXiv  Detail & Related papers  (2020-01-15T17:49:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.