The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits

• URL: http://arxiv.org/abs/2001.05452v4
• Date: Tue, 2 Jul 2024 23:36:25 GMT
• Title: The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits
• Authors: Ronshee Chawla, Abishek Sankararaman, Ayalvadi Ganesh, Sanjay Shakkottai,
• Abstract summary: 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.
• Score: 20.259428328004738
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a decentralized multi-agent Multi Armed Bandit (MAB) setup consisting of $N$ agents, solving the same MAB instance to minimize individual cumulative regret. In our model, agents collaborate by exchanging messages through pairwise gossip style communications on an arbitrary connected graph. We develop two novel algorithms, where each agent only plays from a subset of all the arms. Agents use the communication medium to recommend only arm-IDs (not samples), and thus update the set of arms from which they play. We establish that, if agents communicate $\Omega(\log(T))$ times through any connected pairwise gossip mechanism, then every agent's regret is a factor of order $N$ smaller compared to the case of no collaborations. Furthermore, we show that the communication constraints only have a second order effect on the regret of our algorithm. We then analyze this second order term of the regret to derive bounds on the regret-communication tradeoffs. Finally, we empirically evaluate our algorithm and conclude that the insights are fundamental and not artifacts of our bounds. We also show a lower bound which gives that the regret scaling obtained by our algorithm cannot be improved even in the absence of any communication constraints. Our results thus demonstrate that even a minimal level of collaboration among agents greatly reduces regret for all agents.

Related papers

• 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)
• Multi-Armed Bandits with Abstention [62.749500564313834]
  We introduce a novel extension of the canonical multi-armed bandit problem that incorporates an additional strategic element: abstention. In this enhanced framework, the agent is not only tasked with selecting an arm at each time step, but also has the option to abstain from accepting the instantaneous reward before observing it.
  arXiv  Detail & Related papers  (2024-02-23T06:27:12Z)
• Collaborative Multi-Agent Heterogeneous Multi-Armed Bandits [24.590517939890788]
  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.
  arXiv  Detail & Related papers  (2023-05-30T06:35:49Z)
• 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)
• Doubly Adversarial Federated Bandits [7.23389716633927]
  We study a new non-stochastic federated multi-armed bandit problem with multiple agents collaborating via a communication network. Our algorithm gives a positive answer to an open question proposed in Cesa-Bianchi et al.
  arXiv  Detail & Related papers  (2023-01-22T22:36:43Z)
• 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)
• A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits [77.09836892653176]
  We study federated contextual linear bandits, where $M$ agents cooperate with each other to solve a global contextual linear bandit problem with the help of a central server. We consider the asynchronous setting, where all agents work independently and the communication between one agent and the server will not trigger other agents' communication. We prove that the regret of textttFedLinUCB is bounded by $tildeO(dsqrtsum_m=1M T_m)$ and the communication complexity is $tildeO(dM
  arXiv  Detail & Related papers  (2022-07-07T06:16:19Z)
• Multi-Agent Neural Rewriter for Vehicle Routing with Limited Disclosure of Costs [65.23158435596518]
  Solving the multi-vehicle routing problem as a team Markov game with partially observable costs. Our multi-agent reinforcement learning approach, the so-called multi-agent Neural Rewriter, builds on the single-agent Neural Rewriter to solve the problem by iteratively rewriting solutions.
  arXiv  Detail & Related papers  (2022-06-13T09:17:40Z)
• 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)
• 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)
• Robust Multi-Agent Multi-Armed Bandits [26.26185074977412]
  Recent works have shown that agents facing independent instances of a $K$-armed bandit can collaborate to decrease regret. We show that collaboration indeed decreases regret for this algorithm, assuming $m$ is small compared to $K$ but without assumptions on malicious agents' behavior.
  arXiv  Detail & Related papers  (2020-07-07T22:27:30Z)

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.