Search papers, labs, and topics across Lattice.
This paper investigates cooperative multi-agent bandits in continuous action spaces where the Lipschitz constant is unknown, addressing three distinct information structures. The authors develop algorithms that estimate the Lipschitz constant, discretize the joint action space, and implement a cooperative bandit method, all without communication among players post-learning. Key results demonstrate that common rewards and observable actions facilitate agreement on discretization, while a dithered quantization approach allows for agreement even in their absence without increasing leading-order regret.
Players can achieve coordination in unknown Lipschitz environments without communication by leveraging a clever dithered quantization strategy.
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 \emph{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.
