Multi-Agent Lipschitz Bandits

Sourav Chakraborty; Amit Kiran Rege; Claire Monteleoni; Lijun Chen

cs.LGFeb 18, 2026

Multi-Agent Lipschitz Bandits

Authors: Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni, Lijun Chen

Organizations: University of Colorado Boulder · INRIA Paris

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, while separating coordination costs from learning costs. We propose a modular protocol that first solves the multi-agent coordination problem by 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. In the consensus regime, we obtain an end-to-end regret bound whose dominant learning term is $\tilde{O}(T^{(d+1)/(d+2)})$ , matching the single-player Lipschitz rate; the upfront coordination cost is horizon-independent at fixed confidence and only polylogarithmic in $T$ in the expected-regret form. Under an additional public coverage/scheduling assumption for the epochic extension, we also obtain a gap-free $\tilde{O}(T^{(d+1)/(d+2)})$ guarantee. We further derive a matching lower bound for the dominant learning term and extend the framework to general distance-threshold collision models.

Figures & tables

Figure 1: The center-vs-maximum pathology in 1D . In cell $C_{1}$ , the reward function $\mu(x)$ has a modest center value $\mu(x_{C_{1}})$ but contains a sharp peak near its boundary, making its true maximum $\mu^{*}(C_{1})$ optimal.

Figure 2: Collision Geometries . (a) The partition model discretizes the action space $\mathcal{X}$ into $K$ disjoint hypercubic cells; collisions occur when multiple players occupy the same cell. (b) The distance-threshold model manages interference by seating players within safe balls $B_{i}$ of radius $\sigma$ around $r$ -packing centers $z_{i}$ , ensuring an inter-agent separation $>\rho$ .

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Setting	$T$	$N$	Cells	$T_{0}$	$T_{1}$	Local grid	Seeds
1D regret	$10{,}000$	$3$	$8$	$260$	$700$	$7$	$5$
2D regret	$10{,}000$	$3$	$4\times 4$	$520$	$1100$	$5\times 5$	$5$
Pathology illustration	–	$2$	$6$	–	$9$ probes/cell	–	deterministic

Appendix

Table 1: Synthetic environments and algorithmic settings. “Local grid” denotes the number of candidate points per cell used by the within-cell UCB routine in Phase III.

Figure 3: Cumulative regret in simple synthetic instances. We compare the proposed protocol against the independent single-agent baseline in 1D and 2D. Curves are averaged over $5$ random seeds and shaded bands denote $95\%$ confidence intervals. The baseline exhibits near-linear regret because players continue to collide on the same high-value cells, whereas the proposed protocol incurs a short coordination cost and then grows much more slowly.

Setting	Our protocol	Independent baseline	Mean seating rounds
1D at $T=10{,}000$	$2326.2$	$26432.4$	$3.6$
2D at $T=10{,}000$	$7102.4$	$25306.4$	$2.2$

Appendix

Table 2: Final regret summary. Values are mean cumulative regret at the final horizon in Figure 3 . The last column reports the average number of rounds spent in the seating stage by the proposed protocol.

Figure 4: Collision traces in 1D and 2D. Dotted vertical lines mark the ends of Phase I and Phase II. The proposed protocol localizes collisions to the short upfront coordination stage, while the independent baseline continues to collide almost all the time.

Figure 5: Boundary-peak pathology. Left: a one-dimensional reward function in which the largest peak lies near the boundary between $C_{3}$ and $C_{4}$ ; orange markers denote the cell centers. Right: orange bars are center values, green bars are local-peek scores, and purple bars are true cell maxima. The center values are largest for $C_{5}$ and $C_{6}$ , so a center-based ranking would choose those cells. In contrast, the true cell maxima are largest for $C_{3}$ and $C_{4}$ , and the local-peek scores recover exactly that ordering. This is the geometric failure mode that motivates Phase II.

Quantity	Meaning	Sufficient choice / scaling used in the analysis
$p_{K}$	Phase-I per-round success probability for a fixed (player, cell) pair	$p_{K}=\frac{1}{K}\left(1-\frac{1}{K}\right)^{N-1}$
$\alpha$	Target Phase-I center-estimation radius	User-chosen coarse accuracy level
$T_{0}$	Phase-I budget	It suffices that ( 15 ) holds; equivalently $T_{0}=\tilde{O}(p_{K}^{-1}\alpha^{-2})$ for fixed $\alpha$ and fixed failure budget
$\eta$	Phase-II probe-net resolution	For target final maxima accuracy $\varepsilon$ , choose $\eta=\varepsilon/(2L)$
$P_{\max}$	Maximum number of probe points in one active cell	$P_{\max}\leq C_{d}(h/\eta)^{d}$
$N_{\text{probe}}$	Total number of active probe triples $(j,C,z)$	$N_{\text{probe}}\leq NM_{act}P_{\max}$

Appendix

Table 3: Summary of the main design parameters and sufficient choices. The displayed bounds are sufficient choices used in the proofs, not optimized minima.

Explore similar work

Coordinating the Unknown Lipschitz Constant in Multiplayer Bandits
Aug 11, 2026Ricardo Parada, Chenzhang Zhao, William ChangMulti-Armed Bandits Multi-Agent Coordination
University of California, Riverside Riverside, CA, USA · University of California, Los Angeles Los Angeles, CA, USA
Cost of Structural Learning Under Censored Feedback: A Threshold-Bandit Approach
May 26, 2026Michael Ledford, William RegliMulti-Armed Bandits Multi-Agent Coordination
University of Maryland, College Park
Self-Configurable Mesh-Networks for Scalable Distributed Submodular Bandit Optimization
Feb 22, 2026Zirui Xu, Vasileios TzoumasMulti-Agent Coordination Submodular Optimization
Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109 USA

Aug 11, 2026J/K move · Enter open · S save

Coordinating the Unknown Lipschitz Constant in Multiplayer Bandits

Ricardo Parada, Chenzhang Zhao, William Chang

University of California, Riverside Riverside, CA, USA · University of California, Los Angeles Los Angeles, CA, USA

Multi-Armed Bandits Multi-Agent Coordination Decentralized MARL

Open paper AskPDF arXiv

Motivated by decentralized applications, we study cooperative multi-agent bandits in continuous (Lipschitz) action spaces when the Lipschitz constant is unknown. We consider three information structures: (A)~unobserved actions with common rewards, (B)~observed actions with independent rewards, and (C)~unobserved actions with independent rewards. In each case we design and analyze an algorithm that estimates the Lipschitz constant, chooses a discretization of the joint action space, and applies a cooperative bandit method to the induced discrete problem. Players never communicate once learning starts, so the central difficulty is that they must reach the same discretization from their own data. We prove regret guarantees showing that common rewards and observable actions each supply this agreement for free, and that in their absence agreement can still be bought, through a dithered quantization of the estimate, at no cost in the leading order of the regret.

Abstract

Explore similar work

Coordinating the Unknown Lipschitz Constant in Multiplayer Bandits

Cost of Structural Learning Under Censored Feedback: A Threshold-Bandit Approach

Self-Configurable Mesh-Networks for Scalable Distributed Submodular Bandit Optimization