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 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 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 C1 , the reward function μ(x) has a modest center value μ(xC1) but contains a sharp peak near its boundary, making its true maximum μ∗(C1) optimal.
Figure 2: Collision Geometries . (a) The partition model discretizes the action space 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 Bi of radius σ around r -packing centers zi , ensuring an inter-agent separation >ρ .
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Setting
T
N
Cells
T0
T1
Local grid
Seeds
1D regret
10,000
3
8
260
700
7
5
2D regret
10,000
3
4×4
520
1100
5×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 C3 and C4 ; 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 C5 and C6 , so a center-based ranking would choose those cells. In contrast, the true cell maxima are largest for C3 and C4 , 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
pK
Phase-I per-round success probability for a fixed (player, cell) pair
pK=K1(1−K1)N−1
α
Target Phase-I center-estimation radius
User-chosen coarse accuracy level
T0
Phase-I budget
It suffices that ( 15 ) holds; equivalently T0=O~(pK−1α−2) for fixed α and fixed failure budget
η
Phase-II probe-net resolution
For target final maxima accuracy ε , choose η=ε/(2L)
Pmax
Maximum number of probe points in one active cell
Pmax≤Cd(h/η)d
Nprobe
Total number of active probe triples (j,C,z)
Nprobe≤NMactPmax
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.
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.
Ricardo Parada, Chenzhang Zhao, William Chang
University of California, Riverside Riverside, CA, USA · University of California, Los Angeles Los Angeles, CA, USA
In many multi-agent applications, tasks yield rewards only when executed by a coalition meeting an unknown size threshold; otherwise, feedback is fully censored. This censorship creates an identifiability problem: agents cannot distinguish stochastic failure from insufficient coordination. We formalize this setting as the Threshold-Activated Cooperative Multi-Armed Bandit (TAC-MAB) and analyze it under both centralized and decentralized coordination. We show that a centralized algorithm (C-TAC) achieves cumulative regret O(log T), decomposed into a structural-search term that captures the cost of resolving feasibility under censored feedback and a statistical-monitoring term for value estimation. We then introduce D-TAC, a decentralized event-triggered protocol in which agents synchronize only when their structural beliefs change. Empirically, D-TAC achieves a 23x reduction in communication relative to the centralized baseline while preserving feasibility alignment under conservative belief fusion. These results characterize the coordination cost of learning under censored feedback and show that near-centralized communication efficiency is achievable without continuous synchronization.
We study how to scale distributed bandit submodular coordination under realistic communication constraints in bandwidth, data rate, and connectivity. We are motivated by multi-agent tasks of active situational awareness in unknown, partially-observable, and resource-limited environments, where the agents must coordinate through agent-to-agent communication. Our approach enables scalability by (i) limiting information relays to only one-hop communication and (ii) keeping inter-agent messages small, having each agent transmit only its own action information. Despite these information-access restrictions, our approach enables near-optimal action coordination by optimizing the agents' communication neighborhoods over time, through distributed online bandit optimization, subject to the agents' bandwidth constraints. Particularly, our approach enjoys an anytime suboptimality bound that is also strictly positive for arbitrary network topologies, even disconnected. To prove the bound, we define the Value of Coordination (VoC), an information-theoretic metric that quantifies for each agent the benefit of information access to its neighbors. We validate in simulations the scalability and near-optimality of our approach: it is observed to converge faster, outperform benchmarks for bandit submodular coordination, and can even outperform benchmarks that are privileged with a priori knowledge of the environment.
Zirui Xu, Vasileios Tzoumas
Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109 USA