Multi-Agent Bandits Coordinate with Unknown Lipschitz Constants.

This paper investigates cooperative multi-agent bandit problems in environments where actions are continuous and the Lipschitz constant, a measure of function smoothness, is initially unknown. The challenge lies in enabling multiple agents to coordinate their learning and decision-making without direct communication once the learning process begins. The study considers three distinct scenarios based on how agents perceive actions and rewards.For each scenario, the researchers propose and analyze an algorithm. These algorithms first estimate the unknown Lipschitz constant. Based on this estimate, they then define a shared, discretized version of the joint action space. Finally, a cooperative bandit method is applied to this discrete problem. The core innovation is how agents achieve a consistent discretization independently, leveraging common rewards or observed actions to facilitate agreement, or through a dithered quantization strategy when these are absent. The paper provides regret guarantees, demonstrating that this coordination can be achieved without incurring significant costs in the leading order of regret.