🤖 machine learning

Coordinating the Unknown Lipschitz Constant in Multiplayer Bandits

This paper addresses cooperative multi-agent bandits in continuous action spaces with unknown Lipschitz constants by proposing algorithms that enable decentralized players to independently agree on a joint action discretization through various information structures, achieving optimal regret guarantees without post-learning communication.

Original authors: Ricardo Parada, Chenzhang Zhao, William Chang

Published 2026-08-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ricardo Parada, Chenzhang Zhao, William Chang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of friends trying to find the best spot in a giant, foggy park to set up a picnic. They can't talk to each other once the game starts, and they don't have a map. They only know that the "goodness" of a spot changes smoothly: if you move a tiny step away from a great spot, the next spot is probably almost as good, but if you wander far away, it might be terrible. This smoothness is a concept mathematicians call "Lipschitz continuity." The friends are also playing a game of "Multi-Armed Bandits," a fancy name for a situation where you have to balance trying new things (exploration) to learn about the park versus sticking with what you think is best (exploitation) to get the most food. The tricky part? They don't know exactly how "smooth" the park is. Is a small step a tiny change, or a huge one? Without knowing this "smoothness constant," they can't decide how closely to check the ground. If they check too sparsely, they miss the best spot; if they check too densely, they waste time. This paper tackles the chaotic scenario where multiple friends are trying to coordinate their search in this foggy park without talking, all while guessing the rules of the terrain.

The researchers, Ricardo Parada, Chenzhang Zhao, and William Chang, set out to solve a specific puzzle: How can a team of agents (like our friends) cooperate to find the best action in a continuous, smooth world when they don't know the "smoothness" of that world, and they can't talk to each other once the game begins? They explored three different ways the friends might be able to share information, or lack thereof. In the first scenario, everyone sees the same reward (like everyone tasting the same picnic basket) but can't see where the others are standing. In the second, everyone can see where the others are standing but only tastes their own food. In the third, and hardest scenario, they can't see each other's actions and only taste their own food.

The team designed a clever strategy called "mECAB." It works like a two-phase game. First, the friends do a "coarse exploration." They agree on a rough grid of spots to check beforehand. They sample these spots to estimate the "smoothness constant" (how fast the rewards change). Based on this estimate, they decide how fine their search grid should be. Then, they switch to "exploitation," using a standard algorithm to find the best spot on this newly decided grid. The magic of the paper lies in how they ensure everyone agrees on the grid size without talking.

In the first scenario (common rewards), the agreement happens naturally. Since everyone tastes the same food, their data is identical, so they all calculate the same smoothness estimate and pick the same grid. It's like if everyone at the picnic tasted the same soup; they would all agree on whether it needed more salt without saying a word.

In the second scenario (observable actions, independent rewards), the friends can't taste each other's food, but they can see where everyone is standing. The authors found a clever workaround: a player can use their final move in a specific spot to "signal" their data to the others. By slightly adjusting their position in a way that encodes a number, they can broadcast their findings. This allows the group to pool their data, making their estimate of the smoothness much sharper and more accurate than if they were working alone.

The third scenario (unobserved actions, independent rewards) is the trickiest. No one sees where the others are, and no one shares food. If everyone just guessed the smoothness based on their own limited data, they might guess slightly different numbers. One friend might decide to check every inch, while another checks every foot, and they would never meet at the same spot. To fix this, the authors introduced a "dithered quantization" trick. Before the game, the friends agree on a shared, random number (like rolling a secret die together). When they calculate their smoothness estimate, they add this random number to it before rounding it to a whole number. This random "jitter" ensures that even if their raw guesses are slightly different, the final rounded number they act on is almost always the same. It's like agreeing to round your height to the nearest inch, but first adding a random fraction of an inch to everyone's height so that you all round to the same number, even if you started with slightly different measurements.

The paper proves mathematically that in all three cases, the team can achieve a "regret" (a measure of how much better they could have done if they knew the answer from the start) that grows very slowly as the game gets longer. The simulations confirm that this adaptive approach—guessing the smoothness first and then refining the grid—outperforms a static approach where the grid size is fixed in advance. If the park is very bumpy (a high smoothness constant), a fixed grid might be too coarse to find the best spot, causing the team to miss out. The adaptive method, however, adjusts its grid to the terrain, ensuring they find the best spot efficiently, whether the park is smooth or rough. The authors show that even in the hardest scenario where they have the least information, the cost of coordinating is so small that it doesn't hurt their overall performance in the long run.

Technical Summary: Coordinating the Unknown Lipschitz Constant in Multiplayer Bandits

Problem Statement
This paper addresses the challenge of cooperative multi-player multi-armed bandits (MAB) in continuous action spaces where the mean reward function is Lipschitz continuous, but the Lipschitz constant $L$ is unknown. In decentralized settings (e.g., wireless channel access, distributed sensing), multiple agents must coordinate to maximize cumulative reward without explicit communication once learning begins.

The core difficulty arises from the need to discretize the continuous joint action space to apply standard discrete bandit algorithms. The optimal resolution of this discretization depends on $L$ . Since agents cannot communicate during learning, they must independently estimate $L$ from their own observations. If these estimates diverge, agents will construct different grids, breaking the assumption of a common discrete problem required for cooperative coordination. The paper investigates three specific information structures regarding what agents can observe:

Problem A: Unobserved actions, common rewards.
Problem B: Observed actions, independent rewards.
Problem C: Unobserved actions, independent rewards.

Methodology
The authors propose a meta-algorithm, mECAB, which operates in two phases:

Exploration: Agents uniformly explore a coarse grid of $m$ bins per dimension. They estimate an upper confidence bound on $L$ (denoted $\hat{L}$ ) based on the differences in empirical mean rewards between neighboring bins.
Exploitation: Using the estimated $\hat{L}$ , the agents determine a finer discretization level ( $\hat{m}$ ) and run a standard cooperative multiplayer MAB subroutine (e.g., m-UCB) on the resulting finite set of joint actions.

The critical innovation lies in the agreement mechanism used to ensure all agents derive the same $\hat{L}$ and thus the same grid, despite having different information structures:

In Problem A: Since rewards are common and the exploration schedule is pre-agreed, all agents observe identical empirical means for each bin. Consequently, they naturally compute the identical $\hat{L}$ without additional coordination.
In Problem B: While rewards are independent, actions are observable. Agents use the final sample of each bin to "signal" their empirical mean to others. This allows agents to pool data, effectively increasing the sample size per bin by a factor of $M$ (the number of players), leading to a sharper estimate of $L$ .
In Problem C: This is the most difficult case, as neither rewards nor actions are shared. To prevent estimation divergence, the authors introduce dithered quantization. Agents agree on a shared random variable (dither) $U \sim \text{Unif}[0, 1)$ beforehand. They quantize their raw estimates by rounding $X_i + U$ to the nearest integer. This randomization ensures that the probability of two agents disagreeing on the quantized value is independent of the true instance $L$ , allowing the disagreement probability to be bounded and controlled.

Key Results and Regret Bounds
The paper provides regret guarantees for all three information structures. Let $T$ be the time horizon, $d$ the dimension of the action space, and $M$ the number of players. The joint action space dimension is $Md$.

Problem A (Common Rewards): The regret scales as $O(T^{(Md+1)/(Md+2)})$ . The common reward structure forces identical bin means, ensuring perfect grid alignment. The action asymmetry incurs no additional cost beyond the dimensional scaling.
Problem B (Observed Actions): The regret also scales as $O(T^{(Md+1)/(Md+2)})$ . The ability to signal through actions allows for data pooling, which improves the concentration of the Lipschitz estimate (replacing the sample size $E$ with $ME$ in the error bounds), resulting in a tighter constant compared to Problem A.
Problem C (No Shared Info): The regret bound includes an additional term related to the probability of grid disagreement. However, with a sufficiently large exploration budget, this term is of the same order as the leading term. Specifically, the dithered quantization ensures that the "cost" of coordination does not appear in the leading order of the regret, matching the performance of Problems A and B up to constants.

Significance and Claims
The paper claims to be the first to address Lipschitz bandits with an unknown Lipschitz constant in a multi-player setting. Its primary contribution is demonstrating that coordination (agreement on the discretization grid) can be achieved under severe information constraints:

Free Agreement: In the presence of common rewards (Problem A) or observable actions (Problem B), the necessary agreement for a shared grid is achieved "for free" or through efficient signaling.
Cost-Free Coordination in the Worst Case: Even in the absence of both (Problem C), the authors show that agreement can be "bought" via dithered quantization at no cost to the leading order of the regret. This resolves the fundamental tension between decentralized estimation and the need for a shared discrete structure.

The work extends the single-agent Lipschitz bandit literature (specifically the estimator from [8]) to the multi-agent domain, highlighting that the binding constraint shifts from estimation accuracy to the synchronization of the discretization strategy. Simulations confirm that adaptive discretization (Est-L) outperforms non-adaptive methods (No-L), particularly when the true Lipschitz constant is large, and that the information structure significantly impacts the variance and convergence of the regret.

Technical Summary: Coordinating the Unknown Lipschitz Constant in Multiplayer Bandits

More like this