# Multi-Agent Lipschitz Bandits

arXiv: https://arxiv.org/abs/2602.16965 · HTML: https://mlsanity.com/paper/2602.16965/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 44 references that are in the map.
- First posted on arXiv 18 Feb 2026.

## Builds on (most cited first, 8 of 8)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [Distributed Cooperative Decision Making in Multi-agent Multi-armed Bandits](https://mlsanity.com/paper/2003.01312/) (2020)
- [A survey on multi-player bandits](https://mlsanity.com/paper/2211.16275/) (2022)
- [Incentivized Exploration of Non-Stationary Stochastic Bandits](https://mlsanity.com/paper/2403.10819/) (2024)
- [Multi-Agent Stochastic Bandits Robust to Adversarial Corruptions](https://mlsanity.com/paper/2411.08167/) (2024)
- [Incentivized Lipschitz Bandits](https://mlsanity.com/paper/2508.19466/) (2025)

## Built on by (most cited first, 1 of 1)

- [Learning from Local Walks on Dynamic Graphs with Bandit Feedback](https://mlsanity.com/paper/2607.10571/) (2026)

## Abstract (arXiv)

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 (tildeO(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 (tildeO(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.