Multi-Agent Lipschitz Bandits

• URL: http://arxiv.org/abs/2602.16965v1
• Date: Wed, 18 Feb 2026 23:58:36 GMT
• Title: Multi-Agent Lipschitz Bandits
• Abstract summary: We study the decentralized multi-player bandit problem over a continuous, Lipschitz-structured action space.<n>We propose a protocol that decouples the problem into $N$ independent single-player Lipschitz bandits.<n>We establish a near-optimal regret bound of $tildeO(T(d+1)/(d+2))$ plus a $T$-independent coordination cost, matching the single-player rate.
• Score: 7.465238700168576
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the decentralized multi-player stochastic bandit problem over a continuous, Lipschitz-structured action space where hard collisions yield zero reward. Our objective is to design a communication-free policy that maximizes collective reward, with coordination costs that are independent of the time horizon $T$. We propose a modular protocol that first solves the multi-agent coordination problem -- identifying and seating players on distinct high-value regions via a novel maxima-directed search -- and then decouples the problem into $N$ independent single-player Lipschitz bandits. We establish a near-optimal regret bound of $\tilde{O}(T^{(d+1)/(d+2)})$ plus a $T$-independent coordination cost, matching the single-player rate. To our knowledge, this is the first framework providing such guarantees, and it extends to general distance-threshold collision models.

Related papers

• Top-$k$ Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection [48.83076933238825]
  We consider a multi-objective bandit problem where, at each round, the agent selects a slate of $k$ arms and observes their $d$-dimensional reward vectors under semi-bandit feedback.<n>We formalize this objective through the dominated hypervolume induced by the selected subset of arms, and define an $$-approximate hypervolume regret with respect to the best size-$k$ subset achievable in hindsight.<n>We establish a gap-free regret bound $tildeO(dsqrtnkT)$ that holds on every instance, together with a gap
  arXiv  Detail & Related papers  (2026-07-28T21:10:39Z)
• Dynamic Coalition Formation and Communication Pricing in Skill-Based Agentic AI Systems [0.0]
  We model agent selection and communication as a cooperative game with task-conditioned net utility $U(Cmid x)=V(Cmid x)-sum_iin Cc_i$.<n>We propose a marginal-value activation rule and greedy router, extend the model to optimize communication edges with per-edge costs, and use estimated Shapley values to predict which agents are worth contacting before and during execution.
  arXiv  Detail & Related papers  (2026-07-24T19:25:21Z)
• Distributed Algorithms for Multi-Agent Multi-Armed Bandits with Collision [16.136111977594087]
  We study the Multiplayer Multi-Armed Bandit (MMAB) problem, where multiple players select arms to maximize their cumulative rewards.<n>We consider a distributed setting without central coordination, where each player can only observe their own actions and collision feedback.<n>We propose a distributed algorithm with an adaptive, efficient communication protocol. The algorithm achieves near-optimal group and individual regret, with a communication cost of only $mathcalO(loglog T)$.
  arXiv  Detail & Related papers  (2025-10-08T06:12:59Z)
• Batched Stochastic Matching Bandits [43.651070266360954]
  We introduce a novel bandit framework for matching based on the Multi-nomial Logit (MNL) choice model.<n>In our setting, $N$ agents on one side are assigned to $K$ arms on the other side, where each armally selects an agent from its assigned pool according to an unknown preference.<n>The objective is to minimize regret by maximizing the cumulative revenue from successful matches across all agents.
  arXiv  Detail & Related papers  (2025-09-04T13:16:32Z)
• Cooperative Multi-Agent Constrained Stochastic Linear Bandits [2.099922236065961]
  A network of $N$ agents communicate locally to minimize their collective regret while keeping their expected cost under a specified threshold $tau$. We propose a safe distributed upper confidence bound algorithm, so called textitMA-OPLB, and establish a high probability bound on its $T$-round regret. We show that our regret bound is of order $ mathcalOleft(fracdtau-c_0fraclog(NT)2sqrtNsqrtTlog (1/|lambda|)
  arXiv  Detail & Related papers  (2024-10-22T19:34:53Z)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
  This paper introduces a federated learning framework tailored for online optimization with bandit. In this setting, agents subsets of arms, observe noisy rewards for these subsets without accessing individual arm information, and can cooperate and share information at specific intervals.
  arXiv  Detail & Related papers  (2024-05-09T17:40:09Z)
• Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learning [105.7510838453122]
  We examine online safe multi-agent reinforcement learning using constrained Markov games. We develop an upper confidence reinforcement learning algorithm to solve this Lagrangian problem. Our algorithm updates the minimax decision primal variables via online mirror descent and the dual variable via projected gradient step.
  arXiv  Detail & Related papers  (2023-05-31T22:09:24Z)
• Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
  We propose an algorithm that minimizes the regret over the horizon of time $T$. The proposed algorithm is applicable to domains such as recommendation systems and transportation.
  arXiv  Detail & Related papers  (2023-01-31T03:49:00Z)
• 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 Contextual Linear Bandits with Minimax Optimal Communication Cost [48.288452411283444]
  We study distributed contextual linear bandits with contexts, where $N$ agents act cooperatively to solve a linear bandit-optimization problem with $d$-dimensional features. We propose a distributed batch elimination version of the LinUCB algorithm, DisBE-LUCB, where the agents share information among each other through a central server. We prove that over $T$ rounds ($NT$ actions in total) the communication cost of DisBE-LUCB is only $tildemathcalO(dN)$ and its regret is at most $tildemathcalO
  arXiv  Detail & Related papers  (2022-05-26T05:56:23Z)
• The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player Multi-Armed Bandits with no Communication [10.446001329147112]
  We study the multi-player multi-armed bandit problem. In this problem, $m$ players cooperate to maximize their total reward from $K > m$ arms. We ask whether it is possible to obtain optimal instance-dependent regret $tildeO (1/Delta)$ where $Delta$ is the gap between the $m$-th and $m+1$-st best arms.
  arXiv  Detail & Related papers  (2022-02-19T18:19:36Z)

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.