Clustered Multi-Agent Linear Bandits

• URL: http://arxiv.org/abs/2309.08710v2
• Date: Mon, 30 Oct 2023 17:41:56 GMT
• Title: Clustered Multi-Agent Linear Bandits
• Authors: Hamza Cherkaoui and Merwan Barlier and Igor Colin
• Abstract summary: 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.
• Score: 5.893124686141782
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We address in this paper a particular instance of the multi-agent linear stochastic bandit problem, called clustered multi-agent linear bandits. In this setting, we propose a novel algorithm leveraging an efficient collaboration between the agents in order to accelerate the overall optimization problem. In this contribution, a network controller is responsible for estimating the underlying cluster structure of the network and optimizing the experiences sharing among agents within the same groups. We provide a theoretical analysis for both the regret minimization problem and the clustering quality. Through empirical evaluation against state-of-the-art algorithms on both synthetic and real data, we demonstrate the effectiveness of our approach: our algorithm significantly improves regret minimization while managing to recover the true underlying cluster partitioning.

Related papers

• Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts [27.62165569135504]
  A line of research, known as online clustering of bandits, extends contextual MAB by grouping similar users into clusters. Existing algorithms, which rely on the upper confidence bound (UCB) strategy, struggle to gather adequate statistical information to accurately identify unknown user clusters. We propose two novel algorithms, UniCLUB and PhaseUniCLUB, which incorporate enhanced exploration mechanisms to accelerate cluster identification.
  arXiv  Detail & Related papers  (2025-01-01T16:38:29Z)
• Multi-Agent Best Arm Identification in Stochastic Linear Bandits [0.7673339435080443]
  We study the problem of collaborative best-arm identification in linear bandits under a fixed-budget scenario. In our learning model, we consider multiple agents connected through a star network or a generic network, interacting with a linear bandit instance in parallel. We devise the algorithms MaLinBAI-Star and MaLinBAI-Gen for star networks and generic networks respectively.
  arXiv  Detail & Related papers  (2024-11-20T20:09:44Z)
• Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
  We study multi-agent reinforcement learning (MARL) for the general-sum Markov Games (MGs) under the general function approximation. We introduce a novel complexity measure called the Multi-Agent Decoupling Coefficient (MADC) for general-sum MGs. We show that our algorithm provides comparable sublinear regret to the existing works.
  arXiv  Detail & Related papers  (2023-10-10T01:39:04Z)
• Federated Multi-Level Optimization over Decentralized Networks [55.776919718214224]
  We study the problem of distributed multi-level optimization over a network, where agents can only communicate with their immediate neighbors. We propose a novel gossip-based distributed multi-level optimization algorithm that enables networked agents to solve optimization problems at different levels in a single timescale. Our algorithm achieves optimal sample complexity, scaling linearly with the network size, and demonstrates state-of-the-art performance on various applications.
  arXiv  Detail & Related papers  (2023-10-10T00:21:10Z)
• 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)
• Rethinking Clustering-Based Pseudo-Labeling for Unsupervised Meta-Learning [146.11600461034746]
  Method for unsupervised meta-learning, CACTUs, is a clustering-based approach with pseudo-labeling. This approach is model-agnostic and can be combined with supervised algorithms to learn from unlabeled data. We prove that the core reason for this is lack of a clustering-friendly property in the embedding space.
  arXiv  Detail & Related papers  (2022-09-27T19:04:36Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  Bilevel optimization has been applied to a wide variety of machine learning models. Most existing algorithms restrict their single-machine setting so that they are incapable of handling distributed data. We develop novel decentralized bilevel optimization algorithms based on a gradient tracking communication mechanism and two different gradients.
  arXiv  Detail & Related papers  (2022-06-30T05:29:52Z)
• On Accelerating Distributed Convex Optimizations [0.0]
  This paper studies a distributed multi-agent convex optimization problem. We show that the proposed algorithm converges linearly with an improved rate of convergence than the traditional and adaptive gradient-descent methods. We demonstrate our algorithm's superior performance compared to prominent distributed algorithms for solving real logistic regression problems.
  arXiv  Detail & Related papers  (2021-08-19T13:19:54Z)
• Harnessing Heterogeneity: Learning from Decomposed Feedback in Bayesian Modeling [68.69431580852535]
  We introduce a novel GP regression to incorporate the subgroup feedback. Our modified regression has provably lower variance -- and thus a more accurate posterior -- compared to previous approaches. We execute our algorithm on two disparate social problems.
  arXiv  Detail & Related papers  (2021-07-07T03:57:22Z)
• A black-box adversarial attack for poisoning clustering [78.19784577498031]
  We propose a black-box adversarial attack for crafting adversarial samples to test the robustness of clustering algorithms. We show that our attacks are transferable even against supervised algorithms such as SVMs, random forests, and neural networks.
  arXiv  Detail & Related papers  (2020-09-09T18:19:31Z)
• Kernel Methods for Cooperative Multi-Agent Contextual Bandits [15.609414012418043]
  Cooperative multi-agent decision making involves a group of agents cooperatively solving learning problems while communicating over a network with delays. We consider the kernelised contextual bandit problem, where the reward obtained by an agent is an arbitrary linear function of the contexts' images in the related kernel reproducing Hilbert space (RKHS) We propose textscCoop- KernelUCB, an algorithm that provides near-optimal bounds on the per-agent regret.
  arXiv  Detail & Related papers  (2020-08-14T07:37:44Z)

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.