Coordinating the Unknown Lipschitz Constant in Multiplayer Bandits

# Coordinating the Unknown Lipschitz Constant in Multiplayer Bandits
Source: [https://arxiv.org/html/2608.10526](https://arxiv.org/html/2608.10526)
###### Abstract

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*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\.

## IIntroduction

The multi\-armed bandit \(MAB\) problem is a central model in sequential decision\-making: an agent repeatedly chooses among actions with unknown rewards, balancing exploration and exploitation to maximize cumulative reward\. Many deployments are inherently distributed, with several decision\-makers acting concurrently and observing only part of the system feedback\. In wireless systems, multiple users opportunistically access channels whose availabilities are unknown and time\-varying, often without explicit coordination, as in cognitive radio and dynamic spectrum access\[[12](https://arxiv.org/html/2608.10526#bib.bib1),[2](https://arxiv.org/html/2608.10526#bib.bib2)\]\. Similar abstractions arise in distributed sensing and radar networks, where nodes select waveforms or frequency bands while attempting to avoid mutual interference\[[9](https://arxiv.org/html/2608.10526#bib.bib3)\]\. These settings motivate cooperative multi\-player bandits in which agents coordinate implicitly under information constraints, and the relevant information structure is dictated by what each agent can observe: actions, rewards, or both\.

To model continuously many actions we work with Lipschitz bandits, where the mean reward varies smoothly over a metric space so that nearby actions have similar rewards\. Discretization\-based methods exploit this structure, but the resolution they should use depends on the Lipschitz constantLL\. We therefore study the setting in whichLLis*not*given in advance, extending the multiplayer Lipschitz bandits of\[[7](https://arxiv.org/html/2608.10526#bib.bib6)\]\. Three forms of information asymmetry, described in Section[III\-A](https://arxiv.org/html/2608.10526#S3.SS1)and referred to as Problems A, B, and C, are treated in turn: unobserved actions with common rewards, observed actions with independent rewards, and unobserved actions with independent rewards\. Because players cannot communicate once learning begins, an unknownLLcreates a difficulty absent in the single\-agent problem: each player estimatesLLfrom its own observations, and if these estimates disagree the players build*different*grids and can no longer be regarded as playing a common discrete bandit\. Coordination, rather than estimation accuracy, is the binding constraint\.

Contributions\.We give a meta\-algorithm,mECAB, that estimates an upper confidence bound onLLby uniform exploration of a coarse grid, fixes a discretization, and runs an existing cooperative multiplayer MAB subroutine; we prove regret bounds for all three information structures, each resting on a different agreement mechanism, namely shared rewards in Problem A, signalling through observed actions in Problem B, and a dithered quantization of the estimate in Problem C, the last of which makes the agreement probability independent of the instance in a way no deterministic rounding rule can; and we report simulations comparing Lipschitz\-adaptive with non\-adaptive discretization\.

### I\-ARelated Work

The Lipschitz bandit literature originates with the continuum\-armed bandit \(CAB\) model\[[1](https://arxiv.org/html/2608.10526#bib.bib7)\], in which arms lie in a continuum and the mean reward obeys a continuity condition; sharper discretization strategies followed\[[11](https://arxiv.org/html/2608.10526#bib.bib8)\], and the zooming algorithm\[[10](https://arxiv.org/html/2608.10526#bib.bib10)\]treats general metric spaces through the covering dimension\. Closest to our starting point is\[[5](https://arxiv.org/html/2608.10526#bib.bib11)\], which removes the need to knowLLa priori by estimating it from a uniform grid; our estimator and notation follow that work\.

Multi\-player extensions introduce collisions and asymmetric feedback; see\[[4](https://arxiv.org/html/2608.10526#bib.bib17)\]for a survey\. Recent work on cooperative learning under different information structures adapts UCB\-type ideas to obtain near\-optimal guarantees\[[6](https://arxiv.org/html/2608.10526#bib.bib15),[8](https://arxiv.org/html/2608.10526#bib.bib16),[7](https://arxiv.org/html/2608.10526#bib.bib6)\], and we use those algorithms as subroutines\. To the best of our knowledge no existing multi\-player algorithm addresses Lipschitz bandits with an unknown Lipschitz constant; the closest work is\[[3](https://arxiv.org/html/2608.10526#bib.bib24)\], which assumes a maximal Lipschitz constant but does not learnLL\.

## IIPreliminaries

Consider add\-dimensional compact set of armsX=\[0,1\]dX=\[0,1\]^\{d\},d≥1d\\geq 1\. Each arm𝒙\\bm\{x\}carries a reward distributionν𝒙\\nu\_\{\\bm\{x\}\}supported on\[0,1\]\[0,1\], with mean\-payoff functionf:\[0,1\]d→\[0,1\]f:\[0,1\]^\{d\}\\to\[0,1\]\. At each roundt≥1t\\geq 1the player selects𝒙t\\bm\{x\}\_\{t\}and receivesYt∼ν𝒙tY\_\{t\}\\sim\\nu\_\{\\bm\{x\}\_\{t\}\}, drawn independently across rounds\.

Assumption\.ffis twice differentiable with Hessian uniformly bounded byNN: for all𝒙,𝒚\\bm\{x\},\\bm\{y\},\|𝒚⊤​Hf​\(𝒙\)​𝒚\|≤N​‖𝒚‖∞2\|\\bm\{y\}^\{\\top\}H\_\{f\}\(\\bm\{x\}\)\\,\\bm\{y\}\|\\leq N\\\|\\bm\{y\}\\\|\_\{\\infty\}^\{2\}\. The map‖∇f‖1\\\|\\gradient f\\\|\_\{1\}is continuous and attains its maximumLLon\[0,1\]d\[0,1\]^\{d\}, soffisLL\-Lipschitz with respect to∥⋅∥∞\\\|\\cdot\\\|\_\{\\infty\}\. WriteℱL,N\\mathcal\{F\}\_\{L,N\}for the class of mean\-payoff functions satisfying both conditions with parametersLLandNN; all suprema below are over this class, and neither parameter is known to the players\.

Withf⋆=max𝒙⁡f​\(𝒙\)f^\{\\star\}=\\max\_\{\\bm\{x\}\}f\(\\bm\{x\}\), the expected regret at horizonTTisRT=𝔼​\[T​f⋆−∑t=1Tf​\(𝒙t\)\]R\_\{T\}=\\mathbb\{E\}\[Tf^\{\\star\}\-\\sum\_\{t=1\}^\{T\}f\(\\bm\{x\}\_\{t\}\)\], the expectation being over the draws ofYtY\_\{t\}and any internal randomization\. The goal is to minimizeRTR\_\{T\}without knowingLL\.

## IIIMain Results

### III\-AExtension to the Multi\-Agent Setting

LetP1,…,PMP\_\{1\},\\dots,P\_\{M\}be players, each holding add\-dimensional set of armsAi=\[0,1\]dA\_\{i\}=\[0,1\]^\{d\}, so the joint action space is𝒜=A1×⋯×AM=\[0,1\]M​d\\mathcal\{A\}=A\_\{1\}\\times\\cdots\\times A\_\{M\}=\[0,1\]^\{Md\}, with joint arms𝒂=\(a1,…,aM​d\)\\bm\{a\}=\(a\_\{1\},\\dots,a\_\{Md\}\)\. Players may agree on a strategy, and on any shared randomness it uses, before learning begins, but cannot communicate afterwards\. At each round every player chooses𝒂ti∈\[0,1\]d\\bm\{a\}^\{i\}\_\{t\}\\in\[0,1\]^\{d\}simultaneously, forming𝒂t\\bm\{a\}\_\{t\}; withf:𝒜→\[0,1\]f:\\mathcal\{A\}\\to\[0,1\]inℱL,N\\mathcal\{F\}\_\{L,N\}, the objective is again to minimizeRTR\_\{T\}whenLLis unknown\.

Problem A: unobserved actions, common rewards\.Every player receives the same rewardYtY\_\{t\}but does not observe the actions of the others\.

Problem B: observed actions, independent rewards\.Every player observes the actions of all others, but rewards are i\.i\.d\. across players and playeriisees only its own rewardYtiY\_\{t\}^\{i\}\. The regretRTi=𝔼​\[T​f⋆−∑tf​\(𝒂t\)\]R\_\{T\}^\{i\}=\\mathbb\{E\}\[Tf^\{\\star\}\-\\sum\_\{t\}f\(\\bm\{a\}\_\{t\}\)\]does not depend onii, since the rewards are identically distributed\.

Problem C: unobserved actions, independent rewards\.The two difficulties combine: rewards are i\.i\.d\. across players and actions are unobserved\.

### III\-BThe Main Algorithm

The algorithm is motivated by\[[5](https://arxiv.org/html/2608.10526#bib.bib11)\]and follows the classical CAB template of\[[11](https://arxiv.org/html/2608.10526#bib.bib8)\]: use the Lipschitz constant to discretize the space, then run a standard MAB algorithm on the resulting finite set\. WhenLLis known this yields sublinear regret; when it is unknown we must first estimate it\.

During exploration each player splits its own action set intomdm^\{d\}bins, inducingmM​dm^\{Md\}joint bins, and estimates an upper bound onLLfrom the differences between neighboring bins\. WriteL¯m\\overline\{L\}\_\{m\}for the expectation of the estimator of\[[5](https://arxiv.org/html/2608.10526#bib.bib11)\], which approachesLLasmmgrows\.

###### Lemma 1\(Bubeck et al\.\[[5](https://arxiv.org/html/2608.10526#bib.bib11)\]\)

Form≥3m\\geq 3,L−7​Nm≤L¯m≤L\\;L\-\\frac\{7N\}\{m\}\\leq\\overline\{L\}\_\{m\}\\leq L, whereNNis the Hessian bound\.

###### Lemma 2

If each joint bin is explored withE′E^\{\\prime\}samples, then with probability at least1−δ1\-\\delta,\|L^m−L¯m\|≤m​2E′​ln⁡2​mM​dδ\\bigl\|\\widehat\{L\}\_\{m\}\-\\overline\{L\}\_\{m\}\\bigr\|\\leq m\\sqrt\{\\frac\{2\}\{E^\{\\prime\}\}\\ln\\frac\{2m^\{Md\}\}\{\\delta\}\}\.

Adding the deviation of Lemma[2](https://arxiv.org/html/2608.10526#Thmtheorem2)toL^m\\widehat\{L\}\_\{m\}produces an upper confidence boundL~\\widetilde\{L\}onL¯m\\overline\{L\}\_\{m\}, which sets the discretizationm~\\widetilde\{m\}; combining the two lemmas withδ=1/T\\delta=1/Tgives the two\-sided control used in all of the proofs\.

###### Corollary 3

Fixδ=1/T\\delta=1/Tand letE′E^\{\\prime\}denote the number of samples per joint bin available to a player, soE′=M​EE^\{\\prime\}=MEin Problem B andE′=EE^\{\\prime\}=Ein Problems A and C\. With probability at least1−1/T1\-1/T,

L¯m≤L~m≤L\+1\+2​m​2E′​ln⁡\(2​mM​d​T\),\\overline\{L\}\_\{m\}\\;\\leq\\;\\widetilde\{L\}\_\{m\}\\;\\leq\\;L\+1\+2m\\sqrt\{\\tfrac\{2\}\{E^\{\\prime\}\}\\ln\\\!\\left\(2m^\{Md\}T\\right\)\},and if in additionm≥8​N/Lm\\geq 8N/LthenL~m≥L/8−1\\widetilde\{L\}\_\{m\}\\geq L/8\-1\.

The lower bound prevents the algorithm from choosing too coarse a grid and is the only place where the Hessian boundNNenters: the conditionm≥8​N/Lm\\geq 8N/Lasks that the coarse grid already resolve the curvature offf, and it holds for all largeTTunder the choice ofmmmade in the proofs\. Any multiplayer MAB algorithm, for instance\[[6](https://arxiv.org/html/2608.10526#bib.bib15),[8](https://arxiv.org/html/2608.10526#bib.bib16)\], is then run on the discretized joint space; Algorithm[1](https://arxiv.org/html/2608.10526#algorithm1)collects the steps\.

Input:Horizon

TT, coarse bins

mm, exploration budget

EE, dimension

dd\.

1Initialize:each player divides

Ai=\[0,1\]dA\_\{i\}=\[0,1\]^\{d\}into

mdm^\{d\}bins, inducing joint bins

k¯∈\{0,…,mM​d−1\}\\underline\{k\}\\in\\\{0,\\dots,m^\{Md\}\-1\\\}\.

2Pre\-learning:players agree on an ordering of the joint bins, and in Problem C on a dither

U∼Unif​\[0,1\)U\\sim\\mathrm\{Unif\}\[0,1\)\.

3Exploration:

4for*each joint bink¯∈\{0,…,mM​d−1\}\\underline\{k\}\\in\\\{0,\\dots,m^\{Md\}\-1\\\}*do

5Each player samples

EEactions uniformly from its own bin and observes the resulting rewards\.

6Compute the empirical bin mean

μ^k¯\\widehat\{\\mu\}\_\{\\underline\{k\}\}\(resp\.

μ^k¯i\\widehat\{\\mu\}^\{\\,i\}\_\{\\underline\{k\}\}\)\.

7end for

8Form

L^\\widehat\{L\}from \([2](https://arxiv.org/html/2608.10526#S4.E2)\), \([3](https://arxiv.org/html/2608.10526#S5.E3)\), or \([4](https://arxiv.org/html/2608.10526#S6.E4)\) according to the problem, and set

L~=L^\+m​2E′​ln⁡\(2​mM​d​T\),m~=⌈L~2M​d\+2​T1M​d\+2⌉,\\widetilde\{L\}=\\widehat\{L\}\+m\\sqrt\{\\tfrac\{2\}\{E^\{\\prime\}\}\\ln\(2m^\{Md\}T\)\},\\;\\;\\widetilde\{m\}=\\bigl\\lceil\\widetilde\{L\}^\{\\frac\{2\}\{Md\+2\}\}T^\{\\frac\{1\}\{Md\+2\}\}\\bigr\\rceil,\(1\)with

E′=M​EE^\{\\prime\}=MEin Problem B and

E′=EE^\{\\prime\}=Eotherwise\.

9Exploitation:

10for*t=E​mM​d\+1t=E\\,m^\{Md\}\+1toTT*do

11Play the multiplayer MAB subroutine on the

m~M​d\\widetilde\{m\}^\{Md\}joint actions\.

12end for

Algorithm 1mECAB

## IVProblem A: Action Information Asymmetry

Here the environment produces a single common reward observed by all players, while each player does not observe the others’ actions\. Unobserved actions prevent coordination during play, and the unknown smoothness must be estimated without access to the exploration of the others\. What rescues the situation is that the reward is shared, which makes the exploration statistics shared as well once the schedule is fixed in advance\.

Concretely, the players agree on an ordering of themM​dm^\{Md\}joint bins and each samples uniformly inside the scheduled bin\. Only the bin index affects the statistic collected, not the particular arm chosen inside it, so all players obtain the same empirical meanμ^k¯=1E​∑j=1EZk¯,j\\widehat\{\\mu\}\_\{\\underline\{k\}\}=\\frac\{1\}\{E\}\\sum\_\{j=1\}^\{E\}Z\_\{\\underline\{k\},j\}for every joint bink¯\\underline\{k\}, and each is free to choose any arm within its own bin\. Consequently every player forms the same estimate

L^=m​maxk∈\[m−2\]M​d,s∈\{−1,1\}M​d⁡\|μ^k−μ^k\+s\|,\\widehat\{L\}=m\\max\_\{k\\in\[m\-2\]^\{Md\},\\;s\\in\\\{\-1,1\\\}^\{Md\}\}\\bigl\|\\widehat\{\\mu\}\_\{k\}\-\\widehat\{\\mu\}\_\{k\+s\}\\bigr\|,\(2\)hence the sameL~\\widetilde\{L\}andm~\\widetilde\{m\}, and the ordering of the coarse bins induces a consistent ordering of the finerm~\\widetilde\{m\}\-level grid that everyone can follow\.

###### Theorem 4

Letm≥8​N/Lm\\geq 8N/Land usem\-UCBof\[[6](https://arxiv.org/html/2608.10526#bib.bib15)\]withL^\\widehat\{L\}from \([2](https://arxiv.org/html/2608.10526#S4.E2)\)\. ThenmECABsatisfies

supℱL,NRT≤T\(M​d\+1\)/\(M​d\+2\)⋅\(9​LM​d/\(M​d\+2\)\+5​\(2​m​2E​ln⁡\(\(2​TM​d\+1\)\)\)M​d/\(M​d\+2\)\)\+E​mM​d\+32​T​m~M​d​log⁡T\+1\.\\sup\_\{\\mathcal\{F\}\_\{L,N\}\}R\_\{T\}\\leq T^\{\(Md\+1\)/\(Md\+2\)\}\\\\ \\cdot\\left\(9L^\{Md/\(Md\+2\)\}\+5\\left\(2m\\sqrt\{\\tfrac\{2\}\{E\}\\ln\{\\left\(2T^\{Md\+1\}\\right\)\}\}\\right\)^\{Md/\(Md\+2\)\}\\right\)\\\\ \+Em^\{Md\}\+32\\sqrt\{T\\widetilde\{m\}^\{Md\}\\log T\}\+1\.

On the event of Corollary[3](https://arxiv.org/html/2608.10526#Thmtheorem3)the subroutine term isO​\(T\(M​d\+1\)/\(M​d\+2\)​\(L\+1\)M​d/\(M​d\+2\)​log⁡T\)O\(T^\{\(Md\+1\)/\(Md\+2\)\}\(L\{\+\}1\)^\{Md/\(Md\+2\)\}\\sqrt\{\\log T\}\), matching the leading term up tolog⁡T\\sqrt\{\\log T\}; the same holds in Theorems[5](https://arxiv.org/html/2608.10526#Thmtheorem5)and[7](https://arxiv.org/html/2608.10526#Thmtheorem7)\.

In the single\-agent problem with unknownLL, discretization yields the familiar scalingT\(d\+1\)/\(d\+2\)T^\{\(d\+1\)/\(d\+2\)\}, and Problem A behaves the same way on the joint space withM​dMdin place ofdd\. The action asymmetry therefore costs nothing beyond this dimensional effect, precisely because the common reward and the pre\-agreed schedule force identical bin means, an identicalL^\\widehat\{L\}, and an identical grid\. The dependence on the size of the discretized joint set is also unavoidable, since withKKactions each the induced finite problem hasKMK^\{M\}joint arms, to which the standard finite\-armed lower bound applies\.

## VProblem B: Reward Information Asymmetry

Problem B reverses the structure: actions are observable but reward observations are not shared\. The free synchronization of Problem A breaks, since the bin meansμ^ki\\widehat\{\\mu\}^\{\\,i\}\_\{k\}may differ across players and would lead to different grids if nothing further were done\.

The remedy is to exploit action observability to share reward information implicitly\. Since every action is observed by everyone, an action can carry a signal encoding the sender’s statistics, and in a continuum this needs no departure from the action space: after collectingE−1E\-1samples from a bin, a player devotes its final action in that bin to encoding its empirical mean, which the others decode and fold into their own estimate\. Nothing analogous exists in Problem A, where actions are hidden, nor in finite\-action models, where there is no room to encode a real number without distorting the learning problem\. At a cost of one sample, each player thus gains\(M−1\)​\(E−1\)\(M\-1\)\(E\-1\)further samples for every bin, and forms

L^=m​maxk∈\[m−2\]M​d,s∈\{−1,1\}M​d⁡\|1M​∑i=1M\(μ^ki−μ^k\+si\)\|\.\\widehat\{L\}=m\\max\_\{k\\in\[m\-2\]^\{Md\},\\;s\\in\\\{\-1,1\\\}^\{Md\}\}\\left\|\\frac\{1\}\{M\}\\sum\_\{i=1\}^\{M\}\\bigl\(\\widehat\{\\mu\}\_\{k\}^\{i\}\-\\widehat\{\\mu\}\_\{k\+s\}^\{i\}\\bigr\)\\right\|\.\(3\)The effective sample size entering the concentration ofL^\\widehat\{L\}is multiplied byMM, which sharpens the estimate and improves the grid\. Problem A had perfect alignment of the bin means but no way to convey anything beyond the common scalar reward; Problem B lacks common rewards but recovers most of the benefit of centralized averaging by broadcasting estimates through actions\.

###### Theorem 5

Letm≥8​N/Lm\\geq 8N/Land use the multiplayer subroutine of\[[8](https://arxiv.org/html/2608.10526#bib.bib16)\]for Problem B\. ThenmECABsatisfies

supℱL,NRT≤T\(M​d\+1\)/\(M​d\+2\)×\(9LM​d/\(M​d\+2\)\+5\(2m2M​E​ln⁡\(\(2​TM​d\+1\)\)\)M​d/\(M​d\+2\)\)\+E​mM​d\+32​T​m~M​d​log⁡T\+1\.\\sup\_\{\\mathcal\{F\}\_\{L,N\}\}R\_\{T\}\\leq T^\{\(Md\+1\)/\(Md\+2\)\}\\\\ \\times\\Bigl\(9L^\{Md/\(Md\+2\)\}\\\\ \\qquad\+5\\Bigl\(2m\\sqrt\{\\tfrac\{2\}\{ME\}\\ln\{\(2T^\{Md\+1\}\)\}\}\\Bigr\)^\{Md/\(Md\+2\)\}\\Bigr\)\\\\ \+Em^\{Md\}\+32\\sqrt\{T\\widetilde\{m\}^\{Md\}\\log T\}\+1\.

Compared with Theorem[4](https://arxiv.org/html/2608.10526#Thmtheorem4)the sample size inside the square root improves fromEEtoM​EME, which is exactly the pooling gain from the other players’ samples\.

## VIProblem C: Reward and Action Information Asymmetry

Problem C is the hardest of the three: rewards are not shared, so the mechanism of Problem A is unavailable, and actions are not observed, so the signalling of Problem B is unavailable too\. If each player simply used \([2](https://arxiv.org/html/2608.10526#S4.E2)\) on its own data, the estimates would differ and the induced gridsm~\\widetilde\{m\}would differ with them, destroying the common discrete problem the subroutine needs\.

We restore agreement by quantizing the estimate, so that small discrepancies between players do not change the value they act on\. LetXi=m​maxk,s⁡\|μ^ki−μ^k\+si\|X^\{i\}=m\\max\_\{k,s\}\|\\widehat\{\\mu\}\_\{k\}^\{i\}\-\\widehat\{\\mu\}\_\{k\+s\}^\{i\}\|be the raw estimate of playerii, the maximum running overk∈\[m−2\]M​dk\\in\[m\-2\]^\{Md\}ands∈\{−1,1\}M​ds\\in\\\{\-1,1\\\}^\{Md\}as above\. A deterministic rounding will not do: ifL¯m\\overline\{L\}\_\{m\}sits near a rounding boundary, two players whose estimates straddle it round differently however many samples they collect, and the failure probability approaches1/21/2regardless ofEE\. The boundaries are fixed whileL¯m\\overline\{L\}\_\{m\}is a property of the instance, so no deterministic rule avoids this\. Instead the players agree in advance on a ditherU∼Unif​\[0,1\)U\\sim\\mathrm\{Unif\}\[0,1\), shared randomness requiring no communication, and set

L^i=⌊Xi\+U⌋\.\\widehat\{L\}^\{\\,i\}=\\bigl\\lfloor X^\{i\}\+U\\bigr\\rfloor\.\(4\)Randomizing the offset makes the distance fromL¯m\\overline\{L\}\_\{m\}to the nearest boundary uniform rather than instance\-dependent, so the probability of disagreement can be bounded with no reference to whereL¯m\\overline\{L\}\_\{m\}lies\.

###### Lemma 6

For anyδ\>0\\delta\>0and any playerii,

P​\(\|Xi−L¯m\|\>δ\)≤4​\(2​m\)M​d​exp⁡\(−E​δ232​m2\)\.P\\bigl\(\|X^\{i\}\-\\overline\{L\}\_\{m\}\|\>\\delta\\bigr\)\\leq 4\(2m\)^\{Md\}\\exp\\\!\\left\(\-\\frac\{E\\delta^\{2\}\}\{32m^\{2\}\}\\right\)\.Consequently, withL^i\\widehat\{L\}^\{\\,i\}as in \([4](https://arxiv.org/html/2608.10526#S6.E4)\) andA:=4​M​\(2​m\)M​dA:=4M\(2m\)^\{Md\}, the probability that theMMplayers do not all obtain the same value ofL^\\widehat\{L\}is at most17​m​ln⁡\(A\)/E17\\,m\\sqrt\{\\ln\(A\)/E\}\.

When the players do agree they share the samem~\\widetilde\{m\}, and Problem C reduces to running the same discretized strategy as before; when they do not, they may follow different grids and we pay for that event in the regret\.

###### Theorem 7

Letm≥8​N/Lm\\geq 8N/L, letA=4​M​\(2​m\)M​dA=4M\(2m\)^\{Md\}, and use the multiplayer subroutine of\[[6](https://arxiv.org/html/2608.10526#bib.bib15)\]withL^\\widehat\{L\}from \([4](https://arxiv.org/html/2608.10526#S6.E4)\)\. Then

supℱL,NRT≤T\(M​d\+1\)/\(M​d\+2\)×\(9​LM​d/\(M​d\+2\)\+5​\(2​m​2E​ln⁡\(\(2​TM​d\+1\)\)\)M​d/\(M​d\+2\)\)\+E​mM​d\+C​log⁡T​T​m~M​d\+17​T​m​ln⁡\(A\)/E\.\\sup\_\{\\mathcal\{F\}\_\{L,N\}\}R\_\{T\}\\leq T^\{\(Md\+1\)/\(Md\+2\)\}\\\\ \\times\\left\(9L^\{Md/\(Md\+2\)\}\+5\\left\(2m\\sqrt\{\\tfrac\{2\}\{E\}\\ln\{\\left\(2T^\{Md\+1\}\\right\)\}\}\\right\)^\{Md/\(Md\+2\)\}\\right\)\\\\ \+Em^\{Md\}\+C\\log T\\sqrt\{T\\widetilde\{m\}^\{Md\}\}\+17\\,Tm\\sqrt\{\\ln\(A\)/E\}\.In particular, ifE≥m2​T2/\(M​d\+2\)​ln⁡AE\\geq m^\{2\}T^\{2/\(Md\+2\)\}\\ln Athe last term is at most17​T\(M​d\+1\)/\(M​d\+2\)17\\,T^\{\(Md\+1\)/\(Md\+2\)\}\.

Problem C therefore isolates what each kind of observability buys\. Common rewards makeL^\\widehat\{L\}shared automatically and no agreement term is needed; observable actions permit pooling and sharpen the concentration, improvingEEtoM​EME; when neither is available, agreement must be built from concentration together with dithered quantization\. Its price is the final term, which is instance\-independent and, for the stated exploration budget, of the same order as the leading one, so Problem C matches Problems A and B up to constants onceEEis large enough\.

## VIIExperiments

We simulate a cooperative bandit withM=2M=2players and action dimensiond=1d=1each, soM​d=2Md=2, overT=105T=10^\{5\}rounds and1010independent trials for each configuration\. A maximizera⋆a^\{\\star\}is drawn uniformly from\[0,1\]M​d\[0,1\]^\{Md\}once in each trial and the mean reward isf​\(a\)=−L​‖a−a⋆‖∞f\(a\)=\-L\\\|a\-a^\{\\star\}\\\|\_\{\\infty\}, which isLL\-Lipschitz with respect toℓ∞\\ell\_\{\\infty\}and satisfiesf​\(a⋆\)=0f\(a^\{\\star\}\)=0; rewards are Gaussian with unit variance\. We report cumulative pseudo\-regret∑t\(f​\(a⋆\)−f​\(at\)\)\\sum\_\{t\}\(f\(a^\{\\star\}\)\-f\(a\_\{t\}\)\)averaged over trials, with±1\\pm 1standard deviation shading\.

Both algorithms discretize the joint space and run UCB on the resulting grid, differing only in how the resolution is set\.*Est\-LL*explores a coarse grid ofmmbins in each coordinate withEEuniform samples in each bin, estimatesL^b=m​max\(b,b′\)∈𝒩⁡\|μ^​\(b\)−μ^​\(b′\)\|\\widehat\{L\}\_\{b\}=m\\max\_\{\(b,b^\{\\prime\}\)\\in\\mathcal\{N\}\}\|\\widehat\{\\mu\}\(b\)\-\\widehat\{\\mu\}\(b^\{\\prime\}\)\|over neighboring bin pairs𝒩\\mathcal\{N\}, pads it as in \([1](https://arxiv.org/html/2608.10526#S3.E1)\), and setsm~\\widetilde\{m\}from the result; this phase is not aimed at collecting reward, so regret grows roughly linearly while it runs\.*No\-LL*skips exploration and takesm~=⌈T1/\(M​d\+2\)⌉\\widetilde\{m\}=\\lceil T^\{1/\(Md\+2\)\}\\rceil, avoiding the up\-front cost but risking a resolution mismatched to the smoothness offf\.

The three information structures are modelled at the level of the feedback reaching each player rather than through the signalling and quantization mechanisms themselves: Problem A supplies a common reward, Problem B pools theMMindependent rewards of a round, the idealized effect of encoding empirical means in actions, and Problem C uses a single reward stream without pooling\. This isolates the effect of feedback quality on the accuracy ofL~\\widetilde\{L\}; simulating the signalling and dithering steps directly is left to an extended version\.

Fig\.[1](https://arxiv.org/html/2608.10526#S7.F1)compares the two rules for a small \(L=1L=1\) and a large \(L=1000L=1000\) Lipschitz constant, everything else held fixed\. In all three cases the Est\-LLcurves grow linearly during coarse exploration and then bend into a visibly sublinear phase once UCB begins on the refined grid, which is the tradeoff the method makes\. WhenLLis small the two rules produce comparable resolutions and finish at similar levels; whenLLis large, fixing the resolution without reference toLLgives a grid too coarse for the variation offf, and Est\-LLovertakes it despite the initial linear segment\. The information structure modulates the gain: pooling in Problem B makesL~\\widetilde\{L\}more accurate and flattens the later slope relative to Problems A and C, while Problem C, with the weakest feedback, is the most variable\.

![Refer to caption](https://arxiv.org/html/2608.10526v1/panelA.png)

![Refer to caption](https://arxiv.org/html/2608.10526v1/panelB.png)

Figure 1:Cumulative regret averaged over trials with±1\\pm 1standard deviation shading, for a small Lipschitz constant \(L=1L\{=\}1, top\) and a large one \(L=1000L\{=\}1000, bottom\)\. Each panel overlays Problems A, B, and C under Est\-LLand No\-LLdiscretization\.
## VIIIConclusion

We extended cooperative multiplayer bandits to Lipschitz action spaces with an unknown Lipschitz constant, where the players’ estimates ofLLmust agree for a common discretization to exist\. Common rewards and observable actions each deliver that agreement for free, and when neither is present a dithered quantization delivers it at no cost in the leading order of the regret\. Natural next steps are adversarial rewards and structural assumptions beyond Lipschitz continuity\.

### \-AProof of Lemma[6](https://arxiv.org/html/2608.10526#Thmtheorem6)

###### Proof:

Fixδ\>0\\delta\>0and letf¯m​\(k\)\\overline\{f\}\_\{m\}\(k\)denote the mean offfover binkk\. By Hoeffding’s inequality, for any binkk,

P​\(\|μ^k−f¯m​\(k\)\|\>δ2​m\)≤2​exp⁡\(−E​δ232​m2\)\.P\\\!\\left\(\|\\widehat\{\\mu\}\_\{k\}\-\\overline\{f\}\_\{m\}\(k\)\|\>\\tfrac\{\\delta\}\{2m\}\\right\)\\leq 2\\exp\\\!\\left\(\-\\frac\{E\\delta^\{2\}\}\{32m^\{2\}\}\\right\)\.\(5\)For a neighboring pair\(k,k′\)\(k,k^\{\\prime\}\), the triangle inequality and \([5](https://arxiv.org/html/2608.10526#A0.E5)\) give

P​\(\|\|μ^k−μ^k′\|−\|f¯m​\(k\)−f¯m​\(k′\)\|\|\>δm\)\\displaystyle P\\\!\\left\(\\left\|\|\\widehat\{\\mu\}\_\{k\}\-\\widehat\{\\mu\}\_\{k^\{\\prime\}\}\|\-\|\\overline\{f\}\_\{m\}\(k\)\-\\overline\{f\}\_\{m\}\(k^\{\\prime\}\)\|\\right\|\>\\tfrac\{\\delta\}\{m\}\\right\)≤P​\(\|μ^k−f¯m​\(k\)\|\>δ2​m\)\+P​\(\|μ^k′−f¯m​\(k′\)\|\>δ2​m\)\\displaystyle\\quad\\leq P\\\!\\left\(\|\\widehat\{\\mu\}\_\{k\}\-\\overline\{f\}\_\{m\}\(k\)\|\>\\tfrac\{\\delta\}\{2m\}\\right\)\+P\\\!\\left\(\|\\widehat\{\\mu\}\_\{k^\{\\prime\}\}\-\\overline\{f\}\_\{m\}\(k^\{\\prime\}\)\|\>\\tfrac\{\\delta\}\{2m\}\\right\)≤4​exp⁡\(−E​δ232​m2\)\.\\displaystyle\\quad\\leq 4\\exp\\\!\\left\(\-\\frac\{E\\delta^\{2\}\}\{32m^\{2\}\}\\right\)\.There are at mostmM​d​2M​d=\(2​m\)M​dm^\{Md\}2^\{Md\}=\(2m\)^\{Md\}pairs\(k,s\)\(k,s\)in the maximum definingXiX^\{i\}, so a union bound over them and multiplication bymmyield the first claim\.

For the second, letΔU\\Delta\_\{U\}be the distance fromL¯m\+U\\overline\{L\}\_\{m\}\+Uto the nearest integer; sinceUUis uniform on\[0,1\)\[0,1\),ΔU\\Delta\_\{U\}is uniform on\[0,12\]\[0,\\tfrac\{1\}\{2\}\]\. If\|Xi−L¯m\|<ΔU\|X^\{i\}\-\\overline\{L\}\_\{m\}\|<\\Delta\_\{U\}for everyii, then all theXi\+UX^\{i\}\+Ulie in the same unit interval and every player obtains the sameL^\\widehat\{L\}\. Writinga=E/\(32​m2\)a=E/\(32m^\{2\}\)andA=4​M​\(2​m\)M​dA=4M\(2m\)^\{Md\}, a union bound over theMMplayers and the first claim give, conditionally onUU, a disagreement probability of at mostmin⁡\{1,A​e−a​ΔU2\}\\min\\\{1,Ae^\{\-a\\Delta\_\{U\}^\{2\}\}\\\}\. Letδ0=m​32​ln⁡\(A\)/E\\delta\_\{0\}=m\\sqrt\{32\\ln\(A\)/E\}, so thatA​e−a​δ02=1Ae^\{\-a\\delta\_\{0\}^\{2\}\}=1\. Averaging overUU, whose density is22on\[0,12\]\[0,\\tfrac\{1\}\{2\}\],

P​\(disagreement\)\\displaystyle P\(\\text\{disagreement\}\)≤2​δ0\+2​A​∫δ0∞e−a​δ2​𝑑δ\\displaystyle\\leq 2\\delta\_\{0\}\+2A\\\!\\int\_\{\\delta\_\{0\}\}^\{\\infty\}\\\!e^\{\-a\\delta^\{2\}\}\\,d\\delta≤2​δ0\+A​e−a​δ02a​δ0=2​δ0\+32​m2E​δ0\\displaystyle\\leq 2\\delta\_\{0\}\+\\frac\{Ae^\{\-a\\delta\_\{0\}^\{2\}\}\}\{a\\delta\_\{0\}\}=2\\delta\_\{0\}\+\\frac\{32m^\{2\}\}\{E\\delta\_\{0\}\}≤3​δ0≤17​m​ln⁡\(A\)/E,\\displaystyle\\leq 3\\delta\_\{0\}\\leq 17\\,m\\sqrt\{\\ln\(A\)/E\},where the second inequality uses∫δ0∞e−a​δ2​𝑑δ≤e−a​δ02/\(2​a​δ0\)\\int\_\{\\delta\_\{0\}\}^\{\\infty\}e^\{\-a\\delta^\{2\}\}d\\delta\\leq e^\{\-a\\delta\_\{0\}^\{2\}\}/\(2a\\delta\_\{0\}\)and the third usesln⁡A≥1\\ln A\\geq 1\. ∎

### \-BProof of Theorems[4](https://arxiv.org/html/2608.10526#Thmtheorem4),[5](https://arxiv.org/html/2608.10526#Thmtheorem5)and[7](https://arxiv.org/html/2608.10526#Thmtheorem7)

###### Proof:

We give the argument once, writingE′E^\{\\prime\}for the samples per joint bin available to a player, soE′=M​EE^\{\\prime\}=MEin Problem B andE′=EE^\{\\prime\}=Eotherwise, andℛ​\(K,T\)\\mathcal\{R\}\(K,T\)for the regret of the multiplayer subroutine onKKjoint arms\. Exploration costs at mostE​mM​dEm^\{Md\}, the discretization bias costsL​T/m~LT/\\widetilde\{m\}, and the subroutine contributesℛ​\(m~M​d,T\)\\mathcal\{R\}\(\\widetilde\{m\}^\{Md\},T\), so

supℱL,NRT≤E​mM​d\+𝔼​\[L​Tm~\+ℛ​\(m~M​d,T\)\]\+Ξ,\\sup\_\{\\mathcal\{F\}\_\{L,N\}\}R\_\{T\}\\leq Em^\{Md\}\+\\mathbb\{E\}\\\!\\left\[\\frac\{LT\}\{\\widetilde\{m\}\}\+\\mathcal\{R\}\(\\widetilde\{m\}^\{Md\},T\)\\right\]\+\\Xi,\(6\)whereΞ=0\\Xi=0in Problems A and B, since all players hold the samem~\\widetilde\{m\}by construction, andΞ=T⋅17​m​ln⁡\(A\)/E\\Xi=T\\cdot 17m\\sqrt\{\\ln\(A\)/E\}in Problem C by Lemma[6](https://arxiv.org/html/2608.10526#Thmtheorem6), bounding the regret on the disagreement event byTT\.

Writingx=L~m2/\(M​d\+2\)​T1/\(M​d\+2\)x=\\widetilde\{L\}\_\{m\}^\{2/\(Md\+2\)\}T^\{1/\(Md\+2\)\}, \([1](https://arxiv.org/html/2608.10526#S3.E1)\) givesm~≤x​\(1\+1/x\)\\widetilde\{m\}\\leq x\(1\+1/x\), and whenx≥M​dx\\geq Mdwe may use\(1\+1/x\)M​d≤e\(1\+1/x\)^\{Md\}\\leq e\. Substituting into \([6](https://arxiv.org/html/2608.10526#A0.E6)\),

supℱL,NRT≤\\displaystyle\\sup\_\{\\mathcal\{F\}\_\{L,N\}\}R\_\{T\}\\leq\\;E​mM​d\+Ξ\\displaystyle Em^\{Md\}\+\\Xi\+𝔼\[T\(M​d\+1\)/\(M​d\+2\)L\+1L~m2/\(M​d\+2\)\\displaystyle\+\\mathbb\{E\}\\bigg\[T^\{\(Md\+1\)/\(Md\+2\)\}\\frac\{L\+1\}\{\\widetilde\{L\}\_\{m\}^\{2/\(Md\+2\)\}\}\+ClogTT​e​\(T1/\(M​d\+2\)​L~m2/\(M​d\+2\)\)M​d\]\.\\displaystyle\\quad\+C\\log T\\sqrt\{Te\\bigl\(T^\{1/\(Md\+2\)\}\\widetilde\{L\}\_\{m\}^\{2/\(Md\+2\)\}\\bigr\)^\{Md\}\}\\bigg\]\.By Corollary[3](https://arxiv.org/html/2608.10526#Thmtheorem3), which applies sincem≥8​N/Lm\\geq 8N/L, with probability at least1−1/T1\-1/T,

C​log⁡T​T​e​\(T1/\(M​d\+2\)​L~m2/\(M​d\+2\)\)M​d\\displaystyle C\\log T\\sqrt\{Te\\bigl\(T^\{1/\(Md\+2\)\}\\widetilde\{L\}\_\{m\}^\{2/\(Md\+2\)\}\\bigr\)^\{Md\}\}≤C​log⁡T​e​T\(M​d\+1\)/\(M​d\+2\)\\displaystyle\\quad\\leq C\\log T\\sqrt\{e\}\\,T^\{\(Md\+1\)/\(Md\+2\)\}⋅\(\(L\+1\)M​dM​d\+2\+\(2​m​2E′​ln⁡\(2​mM​d​T\)\)M​dM​d\+2\),\\displaystyle\\qquad\\cdot\\\!\\left\(\(L\{\+\}1\)^\{\\frac\{Md\}\{Md\+2\}\}\+\\\!\\left\(2m\\sqrt\{\\tfrac\{2\}\{E^\{\\prime\}\}\\ln\(2m^\{Md\}T\)\}\\right\)^\{\\\!\\frac\{Md\}\{Md\+2\}\}\\right\)\\\!,whileL~m≥L/8−1\\widetilde\{L\}\_\{m\}\\geq L/8\-1controls the first term; on the complementary event, of probability below1/T1/T, the regret is at mostTTand contributes at most11\. BoundingmmbyTTinside the logarithm and choosingm=⌊Tα⌋m=\\lfloor T^\{\\alpha\}\\rfloorandE=m2​M​⌈T2​γ​\(M​d\+2\)/\(M​d\)⌉E=m^\{2M\}\\lceil T^\{2\\gamma\(Md\+2\)/\(Md\)\}\\rceilfor suitableα,γ\>0\\alpha,\\gamma\>0gives the stated bounds, withℛ​\(m~M​d,T\)=32​T​m~M​d​log⁡T\\mathcal\{R\}\(\\widetilde\{m\}^\{Md\},T\)=32\\sqrt\{T\\widetilde\{m\}^\{Md\}\\log T\}for Problem A by\[[6](https://arxiv.org/html/2608.10526#bib.bib15)\]and for Problem B by\[[8](https://arxiv.org/html/2608.10526#bib.bib16)\], andℛ​\(m~M​d,T\)=C​log⁡T​T​m~M​d\\mathcal\{R\}\(\\widetilde\{m\}^\{Md\},T\)=C\\log T\\sqrt\{T\\widetilde\{m\}^\{Md\}\}for Problem C by\[[6](https://arxiv.org/html/2608.10526#bib.bib15)\]\. For the final claim of Theorem[7](https://arxiv.org/html/2608.10526#Thmtheorem7),E≥m2​T2/\(M​d\+2\)​ln⁡AE\\geq m^\{2\}T^\{2/\(Md\+2\)\}\\ln Agives17​T​m​ln⁡\(A\)/E≤17​T\(M​d\+1\)/\(M​d\+2\)17Tm\\sqrt\{\\ln\(A\)/E\}\\leq 17T^\{\(Md\+1\)/\(Md\+2\)\}\. ∎

## References

- \[1\]R\. Agrawal\(1995\)The continuum\-armed bandit problem\.SIAM Journal on Control and Optimization33\(6\),pp\. 1926–1951\.Cited by:[§I\-A](https://arxiv.org/html/2608.10526#S1.SS1.p1.1)\.
- \[2\]A\. Anandkumar, N\. Michael, A\. K\. Tang, and A\. Swami\(2011\-04\)Distributed algorithms for learning and cognitive medium access with logarithmic regret\.IEEE Journal on Selected Areas in Communications29\(4\),pp\. 731–745\.Cited by:[§I](https://arxiv.org/html/2608.10526#S1.p1.1)\.
- \[3\]I\. Bistritz and N\. Bambos\(2020\)Cooperative multi\-player bandit optimization\.InAdvances in Neural Information Processing Systems 33,pp\. 697–707\.Cited by:[§I\-A](https://arxiv.org/html/2608.10526#S1.SS1.p2.1)\.
- \[4\]E\. Boursier and V\. Perchet\(2024\)A survey on multi\-player bandits\.Note:arXiv:2211\.16275Cited by:[§I\-A](https://arxiv.org/html/2608.10526#S1.SS1.p2.1)\.
- \[5\]S\. Bubeck, G\. Stoltz, and J\. Y\. Yu\(2011\)Lipschitz bandits without the lipschitz constant\.Note:arXiv:1105\.5041Cited by:[§I\-A](https://arxiv.org/html/2608.10526#S1.SS1.p1.1),[§III\-B](https://arxiv.org/html/2608.10526#S3.SS2.p1.1),[§III\-B](https://arxiv.org/html/2608.10526#S3.SS2.p2.6),[Lemma 1](https://arxiv.org/html/2608.10526#Thmtheorem1.2.2)\.
- \[6\]W\. Chang, M\. Jafarnia\-Jahromi, and R\. Jain\(2021\)Online learning for cooperative multi\-player multi\-armed bandits\.CoRRabs/2109\.03818\.Cited by:[§\-B](https://arxiv.org/html/2608.10526#A0.SS2.2.p2.19),[§I\-A](https://arxiv.org/html/2608.10526#S1.SS1.p2.1),[§III\-B](https://arxiv.org/html/2608.10526#S3.SS2.p4.5),[Theorem 4](https://arxiv.org/html/2608.10526#Thmtheorem4.p1.2.2),[Theorem 7](https://arxiv.org/html/2608.10526#Thmtheorem7.p1.3.3)\.
- \[7\]W\. Chang and A\. Kartik\(2025\)Multiplayer information asymmetric bandits in metric spaces\.Note:arXiv:2503\.08004Cited by:[§I\-A](https://arxiv.org/html/2608.10526#S1.SS1.p2.1),[§I](https://arxiv.org/html/2608.10526#S1.p2.4)\.
- \[8\]W\. Chang and Y\. Lu\(2023\)Optimal cooperative multiplayer learning bandits with noisy rewards and no communication\.arXiv preprint arXiv:2311\.06210\.Cited by:[§\-B](https://arxiv.org/html/2608.10526#A0.SS2.2.p2.19),[§I\-A](https://arxiv.org/html/2608.10526#S1.SS1.p2.1),[§III\-B](https://arxiv.org/html/2608.10526#S3.SS2.p4.5),[Theorem 5](https://arxiv.org/html/2608.10526#Thmtheorem5.p1.1.1)\.
- \[9\]W\. W\. Howard, C\. E\. Thornton, A\. F\. Martone, and R\. M\. Buehrer\(2021\)Multi\-player bandits for distributed cognitive radar\.Note:arXiv:2102\.00274Cited by:[§I](https://arxiv.org/html/2608.10526#S1.p1.1)\.
- \[10\]R\. Kleinberg, A\. Slivkins, and E\. Upfal\(2008\)Multi\-armed bandits in metric spaces\.Note:arXiv:0809\.4882Cited by:[§I\-A](https://arxiv.org/html/2608.10526#S1.SS1.p1.1)\.
- \[11\]R\. Kleinberg\(2004\)Nearly tight bounds for the continuum\-armed bandit problem\.InAdvances in Neural Information Processing Systems 17,pp\. 697–704\.Cited by:[§I\-A](https://arxiv.org/html/2608.10526#S1.SS1.p1.1),[§III\-B](https://arxiv.org/html/2608.10526#S3.SS2.p1.1)\.
- \[12\]K\. Liu and Q\. Zhao\(2010\-11\)Distributed learning in multi\-armed bandit with multiple players\.IEEE Transactions on Signal Processing58\(11\),pp\. 5667–5681\.Cited by:[§I](https://arxiv.org/html/2608.10526#S1.p1.1)\.