Multi-Agent Lipschitz Bandits

Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni, Lijun Chen
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:4429-4437, 2026.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-chakraborty26b, title = { Multi-Agent Lipschitz Bandits }, author = {Chakraborty, Sourav and Rege, Amit Kiran and Monteleoni, Claire and Chen, Lijun}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {4429--4437}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/chakraborty26b/chakraborty26b.pdf}, url = {https://proceedings.mlr.press/v300/chakraborty26b.html}, 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. } }
Endnote
%0 Conference Paper %T Multi-Agent Lipschitz Bandits %A Sourav Chakraborty %A Amit Kiran Rege %A Claire Monteleoni %A Lijun Chen %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-chakraborty26b %I PMLR %P 4429--4437 %U https://proceedings.mlr.press/v300/chakraborty26b.html %V 300 %X 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.
APA
Chakraborty, S., Rege, A.K., Monteleoni, C. & Chen, L.. (2026). Multi-Agent Lipschitz Bandits . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:4429-4437 Available from https://proceedings.mlr.press/v300/chakraborty26b.html.

Related Material