Paper deep dive
Coordinating the Unknown Lipschitz Constant in Multiplayer Bandits
Ricardo Parada, Chenzhang Zhao, William Chang
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 8/16/2026, 2:45:23 AM
Summary
This paper addresses cooperative multi-agent bandits in continuous Lipschitz action spaces where the Lipschitz constant (L) is unknown. The authors propose the mECAB algorithm, which estimates L, discretizes the joint action space, and applies a cooperative bandit subroutine. They analyze three information structures: (A) unobserved actions with common rewards, (B) observed actions with independent rewards, and (C) unobserved actions with independent rewards. The study proves that common rewards and observable actions allow players to implicitly agree on the discretization without communication, while a dithered quantization method ensures agreement in the absence of both, maintaining optimal regret bounds.
Entities (8)
Relation Signals (8)
mECAB → handles → Problem A
confidence 95% · In each case we design and analyze an algorithm... Problem A: unobserved actions with common rewards
mECAB → handles → Problem B
confidence 95% · In each case we design and analyze an algorithm... Problem B: observed actions with independent rewards
mECAB → handles → Problem C
confidence 95% · In each case we design and analyze an algorithm... Problem C: unobserved actions with independent rewards
mECAB → solves → Multiplayer Bandits
confidence 95% · We study cooperative multi-agent bandits... We give a meta-algorithm, mECAB
Dithered Quantization → enables → Implicit Agreement
confidence 93% · in their absence agreement can still be bought, through a dithered quantization of the estimate
Common Rewards → enables → Implicit Agreement
confidence 92% · common rewards and observable actions each supply this agreement for free
Observable Actions → enables → Implicit Agreement
confidence 92% · common rewards and observable actions each supply this agreement for free
mECAB → uses → Dithered Quantization
confidence 90% · in Problem C... set L^i = floor(X^i + U)... dithered quantization
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 \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.
Tags
Links
- Source: https://arxiv.org/abs/2608.10526v1
- Canonical: https://arxiv.org/abs/2608.10526v1
Trouble viewing inline? Open PDF directly →
Full Text
29,763 characters extracted from source content.
Expand or collapse full text
Coordinating the Unknown Lipschitz Constant in Multiplayer Bandits Ricardo Parada Chenzhang Zhao William Chang 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. I Introduction 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, 2]. Similar abstractions arise in distributed sensing and radar networks, where nodes select waveforms or frequency bands while attempting to avoid mutual interference [9]. 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 constant L. We therefore study the setting in which L is not given in advance, extending the multiplayer Lipschitz bandits of [7]. Three forms of information asymmetry, described in Section I-A 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 unknown L creates a difficulty absent in the single-agent problem: each player estimates L from 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 on L by 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-A Related Work The Lipschitz bandit literature originates with the continuum-armed bandit (CAB) model [1], in which arms lie in a continuum and the mean reward obeys a continuity condition; sharper discretization strategies followed [11], and the zooming algorithm [10] treats general metric spaces through the covering dimension. Closest to our starting point is [5], which removes the need to know L a 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] for a survey. Recent work on cooperative learning under different information structures adapts UCB-type ideas to obtain near-optimal guarantees [6, 8, 7], 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], which assumes a maximal Lipschitz constant but does not learn L. I Preliminaries Consider a d-dimensional compact set of arms X=[0,1]dX=[0,1]^d, d≥1d≥ 1. Each arm x carries a reward distribution ν _ x supported on [0,1][0,1], with mean-payoff function f:[0,1]d→[0,1]f:[0,1]^d→[0,1]. At each round t≥1t≥ 1 the player selects t x_t and receives Yt∼νtY_t _ x_t, drawn independently across rounds. Assumption. f is twice differentiable with Hessian uniformly bounded by N: for all , x, y, |⊤Hf()|≤N‖∞2| y H_f( x)\, y|≤ N\| y\|_∞^2. The map ‖∇f‖1\| f\|_1 is continuous and attains its maximum L on [0,1]d[0,1]^d, so f is L-Lipschitz with respect to ∥⋅∥∞\|·\|_∞. Write ℱL,NF_L,N for the class of mean-payoff functions satisfying both conditions with parameters L and N; all suprema below are over this class, and neither parameter is known to the players. With f⋆=maxf()f = _ xf( x), the expected regret at horizon T is RT=[Tf⋆−∑t=1Tf(t)]R_T=E[Tf - _t=1^Tf( x_t)], the expectation being over the draws of YtY_t and any internal randomization. The goal is to minimize RTR_T without knowing L. I Main Results I-A Extension to the Multi-Agent Setting Let P1,…,PMP_1,…,P_M be players, each holding a d-dimensional set of arms Ai=[0,1]dA_i=[0,1]^d, so the joint action space is =A1×⋯×AM=[0,1]MdA=A_1×·s× A_M=[0,1]^Md, with joint arms =(a1,…,aMd) a=(a_1,…,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 a^i_t∈[0,1]^d simultaneously, forming t a_t; with f:→[0,1]f:A→[0,1] in ℱL,NF_L,N, the objective is again to minimize RTR_T when L is unknown. Problem A: unobserved actions, common rewards. Every player receives the same reward YtY_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 player i sees only its own reward YtiY_t^i. The regret RTi=[Tf⋆−∑tf(t)]R_T^i=E[Tf - _tf( a_t)] does not depend on i, 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. I-B The Main Algorithm The algorithm is motivated by [5] and follows the classical CAB template of [11]: use the Lipschitz constant to discretize the space, then run a standard MAB algorithm on the resulting finite set. When L is known this yields sublinear regret; when it is unknown we must first estimate it. During exploration each player splits its own action set into mdm^d bins, inducing mMdm^Md joint bins, and estimates an upper bound on L from the differences between neighboring bins. Write L¯m L_m for the expectation of the estimator of [5], which approaches L as m grows. Lemma 1 (Bubeck et al. [5]) For m≥3m≥ 3, L−7Nm≤L¯m≤L\;L- 7Nm≤ L_m≤ L, where N is the Hessian bound. Lemma 2 If each joint bin is explored with E′E samples, then with probability at least 1−δ1-δ, |L^m−L¯m|≤m2E′ln2mMdδ | L_m- L_m |≤ m 2E 2m^Mdδ. Adding the deviation of Lemma 2 to L^m L_m produces an upper confidence bound L~ L on L¯m L_m, which sets the discretization m~ m; combining the two lemmas with δ=1/Tδ=1/T gives the two-sided control used in all of the proofs. Corollary 3 Fix δ=1/Tδ=1/T and let E′E denote the number of samples per joint bin available to a player, so E′=ME =ME in Problem B and E′=E =E in Problems A and C. With probability at least 1−1/T1-1/T, L¯m≤L~m≤L+1+2m2E′ln(2mMdT), L_m\;≤\; L_m\;≤\;L+1+2m 2E \! (2m^MdT ), and if in addition m≥8N/Lm≥ 8N/L then L~m≥L/8−1 L_m≥ L/8-1. The lower bound prevents the algorithm from choosing too coarse a grid and is the only place where the Hessian bound N enters: the condition m≥8N/Lm≥ 8N/L asks that the coarse grid already resolve the curvature of f, and it holds for all large T under the choice of m made in the proofs. Any multiplayer MAB algorithm, for instance [6, 8], is then run on the discretized joint space; Algorithm 1 collects the steps. Input: Horizon T, coarse bins m, exploration budget E, dimension d. 1 Initialize: each player divides Ai=[0,1]dA_i=[0,1]^d into mdm^d bins, inducing joint bins k¯∈0,…,mMd−1 k∈\0,…,m^Md-1\. 2 Pre-learning: players agree on an ordering of the joint bins, and in Problem C on a dither U∼Unif[0,1)U [0,1). 3 Exploration: 4 for each joint bin k¯∈0,…,mMd−1 k∈\0,…,m^Md-1\ do 5 Each player samples E actions uniformly from its own bin and observes the resulting rewards. 6 Compute the empirical bin mean μ^k¯ μ_ k (resp. μ^k¯i μ^\,i_ k). 7 end for 8Form L L from (2), (3), or (4) according to the problem, and set L~=L^+m2E′ln(2mMdT),m~=⌈L~2Md+2T1Md+2⌉, L= L+m 2E (2m^MdT),\;\; m= L 2Md+2T 1Md+2 , (1) with E′=ME =ME in Problem B and E′=E =E otherwise. 9 Exploitation: 10 for t=EmMd+1t=E\,m^Md+1 to T do 11 Play the multiplayer MAB subroutine on the m~Md m^Md joint actions. 12 end for Algorithm 1 mECAB IV Problem 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 the mMdm^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 μ_ k= 1E _j=1^EZ_ k,j for every joint bin k¯ k, and each is free to choose any arm within its own bin. Consequently every player forms the same estimate L^=mmaxk∈[m−2]Md,s∈−1,1Md|μ^k−μ^k+s|, L=m _k∈[m-2]^Md,\;s∈\-1,1\^Md | μ_k- μ_k+s |, (2) hence the same L~ L and m~ m, and the ordering of the coarse bins induces a consistent ordering of the finer m~ m-level grid that everyone can follow. Theorem 4 Let m≥8N/Lm≥ 8N/L and use m-UCB of [6] with L L from (2). Then mECAB satisfies supℱL,NRT≤T(Md+1)/(Md+2)⋅(9LMd/(Md+2)+5(2m2Eln((2TMd+1)))Md/(Md+2))+EmMd+32Tm~MdlogT+1. _F_L,NR_T≤ T^(Md+1)/(Md+2)\\ · (9L^Md/(Md+2)+5 (2m 2E (2T^Md+1 ) )^Md/(Md+2) )\\ +Em^Md+32 T m^Md T+1. On the event of Corollary 3 the subroutine term is O(T(Md+1)/(Md+2)(L+1)Md/(Md+2)logT)O(T^(Md+1)/(Md+2)(L+1)^Md/(Md+2) T), matching the leading term up to logT T; the same holds in Theorems 5 and 7. In the single-agent problem with unknown L, discretization yields the familiar scaling T(d+1)/(d+2)T^(d+1)/(d+2), and Problem A behaves the same way on the joint space with MdMd in place of d. 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 identical L L, and an identical grid. The dependence on the size of the discretized joint set is also unavoidable, since with K actions each the induced finite problem has KMK^M joint arms, to which the standard finite-armed lower bound applies. V Problem 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 μ^\,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 collecting E−1E-1 samples 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^=mmaxk∈[m−2]Md,s∈−1,1Md|1M∑i=1M(μ^ki−μ^k+si)|. L=m _k∈[m-2]^Md,\;s∈\-1,1\^Md | 1M _i=1^M ( μ_k^i- μ_k+s^i ) |. (3) The effective sample size entering the concentration of L L is multiplied by M, 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 Let m≥8N/Lm≥ 8N/L and use the multiplayer subroutine of [8] for Problem B. Then mECAB satisfies supℱL,NRT≤T(Md+1)/(Md+2)×(9LMd/(Md+2)+5(2m2MEln((2TMd+1)))Md/(Md+2))+EmMd+32Tm~MdlogT+1. _F_L,NR_T≤ T^(Md+1)/(Md+2)\\ × (9L^Md/(Md+2)\\ +5 (2m 2ME (2T^Md+1) )^Md/(Md+2) )\\ +Em^Md+32 T m^Md T+1. Compared with Theorem 4 the sample size inside the square root improves from E to MEME, which is exactly the pooling gain from the other players’ samples. VI Problem 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) on its own data, the estimates would differ and the induced grids m~ 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. Let Xi=mmaxk,s|μ^ki−μ^k+si|X^i=m _k,s| μ_k^i- μ_k+s^i| be the raw estimate of player i, the maximum running over k∈[m−2]Mdk∈[m-2]^Md and s∈−1,1Mds∈\-1,1\^Md as above. A deterministic rounding will not do: if L¯m L_m sits near a rounding boundary, two players whose estimates straddle it round differently however many samples they collect, and the failure probability approaches 1/21/2 regardless of E. The boundaries are fixed while L¯m L_m is a property of the instance, so no deterministic rule avoids this. Instead the players agree in advance on a dither U∼Unif[0,1)U [0,1), shared randomness requiring no communication, and set L^i=⌊Xi+U⌋. L^\,i= X^i+U . (4) Randomizing the offset makes the distance from L¯m L_m to the nearest boundary uniform rather than instance-dependent, so the probability of disagreement can be bounded with no reference to where L¯m L_m lies. Lemma 6 For any δ>0δ>0 and any player i, P(|Xi−L¯m|>δ)≤4(2m)Mdexp(−Eδ232m2).P (|X^i- L_m|>δ )≤ 4(2m)^Md \! (- Eδ^232m^2 ). Consequently, with L^i L^\,i as in (4) and A:=4M(2m)MdA:=4M(2m)^Md, the probability that the M players do not all obtain the same value of L L is at most 17mln(A)/E17\,m (A)/E. When the players do agree they share the same m~ 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 Let m≥8N/Lm≥ 8N/L, let A=4M(2m)MdA=4M(2m)^Md, and use the multiplayer subroutine of [6] with L L from (4). Then supℱL,NRT≤T(Md+1)/(Md+2)×(9LMd/(Md+2)+5(2m2Eln((2TMd+1)))Md/(Md+2))+EmMd+ClogTTm~Md+17Tmln(A)/E. _F_L,NR_T≤ T^(Md+1)/(Md+2)\\ × (9L^Md/(Md+2)+5 (2m 2E (2T^Md+1 ) )^Md/(Md+2) )\\ +Em^Md+C T T m^Md+17\,Tm (A)/E. In particular, if E≥m2T2/(Md+2)lnAE≥ m^2T^2/(Md+2) A the last term is at most 17T(Md+1)/(Md+2)17\,T^(Md+1)/(Md+2). Problem C therefore isolates what each kind of observability buys. Common rewards make L L shared automatically and no agreement term is needed; observable actions permit pooling and sharpen the concentration, improving E to MEME; 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 once E is large enough. VII Experiments We simulate a cooperative bandit with M=2M=2 players and action dimension d=1d=1 each, so Md=2Md=2, over T=105T=10^5 rounds and 1010 independent trials for each configuration. A maximizer a⋆a is drawn uniformly from [0,1]Md[0,1]^Md once in each trial and the mean reward is f(a)=−L‖a−a⋆‖∞f(a)=-L\|a-a \|_∞, which is L-Lipschitz with respect to ℓ∞ _∞ and satisfies f(a⋆)=0f(a )=0; rewards are Gaussian with unit variance. We report cumulative pseudo-regret ∑t(f(a⋆)−f(at)) _t(f(a )-f(a_t)) averaged over trials, with ±1± 1 standard deviation shading. Both algorithms discretize the joint space and run UCB on the resulting grid, differing only in how the resolution is set. Est-L explores a coarse grid of m bins in each coordinate with E uniform samples in each bin, estimates L^b=mmax(b,b′)∈|μ^(b)−μ^(b′)| L_b=m _(b,b ) | μ(b)- μ(b )| over neighboring bin pairs N, pads it as in (1), and sets m~ m from the result; this phase is not aimed at collecting reward, so regret grows roughly linearly while it runs. No-L skips exploration and takes m~=⌈T1/(Md+2)⌉ m= T^1/(Md+2) , avoiding the up-front cost but risking a resolution mismatched to the smoothness of f. 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 the M independent 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 of L~ L; simulating the signalling and dithering steps directly is left to an extended version. Fig. 1 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-L curves 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. When L is small the two rules produce comparable resolutions and finish at similar levels; when L is large, fixing the resolution without reference to L gives a grid too coarse for the variation of f, and Est-L overtakes it despite the initial linear segment. The information structure modulates the gain: pooling in Problem B makes L~ 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. Figure 1: Cumulative regret averaged over trials with ±1± 1 standard 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-L and No-L discretization. VIII Conclusion We extended cooperative multiplayer bandits to Lipschitz action spaces with an unknown Lipschitz constant, where the players’ estimates of L must 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. -A Proof of Lemma 6 Proof: Fix δ>0δ>0 and let f¯m(k) f_m(k) denote the mean of f over bin k. By Hoeffding’s inequality, for any bin k, P(|μ^k−f¯m(k)|>δ2m)≤2exp(−Eδ232m2).P\! (| μ_k- f_m(k)|> δ2m )≤ 2 \! (- Eδ^232m^2 ). (5) For a neighboring pair (k,k′)(k,k ), the triangle inequality and (5) give P(||μ^k−μ^k′|−|f¯m(k)−f¯m(k′)||>δm) P\! ( || μ_k- μ_k |-| f_m(k)- f_m(k )| |> δm ) ≤P(|μ^k−f¯m(k)|>δ2m)+P(|μ^k′−f¯m(k′)|>δ2m) ≤ P\! (| μ_k- f_m(k)|> δ2m )+P\! (| μ_k - f_m(k )|> δ2m ) ≤4exp(−Eδ232m2). ≤ 4 \! (- Eδ^232m^2 ). There are at most mMd2Md=(2m)Mdm^Md2^Md=(2m)^Md pairs (k,s)(k,s) in the maximum defining XiX^i, so a union bound over them and multiplication by m yield the first claim. For the second, let ΔU _U be the distance from L¯m+U L_m+U to the nearest integer; since U is uniform on [0,1)[0,1), ΔU _U is uniform on [0,12][0, 12]. If |Xi−L¯m|<ΔU|X^i- L_m|< _U for every i, then all the Xi+UX^i+U lie in the same unit interval and every player obtains the same L L. Writing a=E/(32m2)a=E/(32m^2) and A=4M(2m)MdA=4M(2m)^Md, a union bound over the M players and the first claim give, conditionally on U, a disagreement probability of at most min1,Ae−aΔU2 \1,Ae^-a _U^2\. Let δ0=m32ln(A)/E _0=m 32 (A)/E, so that Ae−aδ02=1Ae^-a _0^2=1. Averaging over U, whose density is 22 on [0,12][0, 12], P(disagreement) P(disagreement) ≤2δ0+2A∫δ0∞e−aδ2δ ≤ 2 _0+2A\! _ _0^∞\!e^-aδ^2\,dδ ≤2δ0+Ae−aδ02aδ0=2δ0+32m2Eδ0 ≤ 2 _0+ Ae^-a _0^2a _0=2 _0+ 32m^2E _0 ≤3δ0≤17mln(A)/E, ≤ 3 _0≤ 17\,m (A)/E, where the second inequality uses ∫δ0∞e−aδ2δ≤e−aδ02/(2aδ0) _ _0^∞e^-aδ^2dδ≤ e^-a _0^2/(2a _0) and the third uses lnA≥1 A≥ 1. ∎ -B Proof of Theorems 4, 5 and 7 Proof: We give the argument once, writing E′E for the samples per joint bin available to a player, so E′=ME =ME in Problem B and E′=E =E otherwise, and ℛ(K,T)R(K,T) for the regret of the multiplayer subroutine on K joint arms. Exploration costs at most EmMdEm^Md, the discretization bias costs LT/m~LT/ m, and the subroutine contributes ℛ(m~Md,T)R( m^Md,T), so supℱL,NRT≤EmMd+[LTm~+ℛ(m~Md,T)]+Ξ, _F_L,NR_T≤ Em^Md+E\! [ LT m+R( m^Md,T) ]+ , (6) where Ξ=0 =0 in Problems A and B, since all players hold the same m~ m by construction, and Ξ=T⋅17mln(A)/E =T· 17m (A)/E in Problem C by Lemma 6, bounding the regret on the disagreement event by T. Writing x=L~m2/(Md+2)T1/(Md+2)x= L_m^2/(Md+2)T^1/(Md+2), (1) gives m~≤x(1+1/x) m≤ x(1+1/x), and when x≥Mdx≥ Md we may use (1+1/x)Md≤e(1+1/x)^Md≤ e. Substituting into (6), supℱL,NRT≤ _F_L,NR_T≤\; EmMd+Ξ Em^Md+ +[T(Md+1)/(Md+2)L+1L~m2/(Md+2) +E [T^(Md+1)/(Md+2) L+1 L_m^2/(Md+2) +ClogTTe(T1/(Md+2)L~m2/(Md+2))Md]. +C T Te (T^1/(Md+2) L_m^2/(Md+2) )^Md ]. By Corollary 3, which applies since m≥8N/Lm≥ 8N/L, with probability at least 1−1/T1-1/T, ClogTTe(T1/(Md+2)L~m2/(Md+2))Md C T Te (T^1/(Md+2) L_m^2/(Md+2) )^Md ≤ClogTeT(Md+1)/(Md+2) ≤ C T e\,T^(Md+1)/(Md+2) ⋅((L+1)MdMd+2+(2m2E′ln(2mMdT))MdMd+2), ·\! ((L+1) MdMd+2+\! (2m 2E (2m^MdT) )^\! MdMd+2 )\!, while L~m≥L/8−1 L_m≥ L/8-1 controls the first term; on the complementary event, of probability below 1/T1/T, the regret is at most T and contributes at most 11. Bounding m by T inside the logarithm and choosing m=⌊Tα⌋m= T^α and E=m2M⌈T2γ(Md+2)/(Md)⌉E=m^2M T^2γ(Md+2)/(Md) for suitable α,γ>0α,γ>0 gives the stated bounds, with ℛ(m~Md,T)=32Tm~MdlogTR( m^Md,T)=32 T m^Md T for Problem A by [6] and for Problem B by [8], and ℛ(m~Md,T)=ClogTTm~MdR( m^Md,T)=C T T m^Md for Problem C by [6]. For the final claim of Theorem 7, E≥m2T2/(Md+2)lnAE≥ m^2T^2/(Md+2) A gives 17Tmln(A)/E≤17T(Md+1)/(Md+2)17Tm (A)/E≤ 17T^(Md+1)/(Md+2). ∎ References [1] R. Agrawal (1995) The continuum-armed bandit problem. SIAM Journal on Control and Optimization 33 (6), p. 1926–1951. Cited by: §I-A. [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 Communications 29 (4), p. 731–745. Cited by: §I. [3] I. Bistritz and N. Bambos (2020) Cooperative multi-player bandit optimization. In Advances in Neural Information Processing Systems 33, p. 697–707. Cited by: §I-A. [4] E. Boursier and V. Perchet (2024) A survey on multi-player bandits. Note: arXiv:2211.16275 Cited by: §I-A. [5] S. Bubeck, G. Stoltz, and J. Y. Yu (2011) Lipschitz bandits without the lipschitz constant. Note: arXiv:1105.5041 Cited by: §I-A, §I-B, §I-B, Lemma 1. [6] W. Chang, M. Jafarnia-Jahromi, and R. Jain (2021) Online learning for cooperative multi-player multi-armed bandits. CoRR abs/2109.03818. Cited by: §-B, §I-A, §I-B, Theorem 4, Theorem 7. [7] W. Chang and A. Kartik (2025) Multiplayer information asymmetric bandits in metric spaces. Note: arXiv:2503.08004 Cited by: §I-A, §I. [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, §I-A, §I-B, Theorem 5. [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.00274 Cited by: §I. [10] R. Kleinberg, A. Slivkins, and E. Upfal (2008) Multi-armed bandits in metric spaces. Note: arXiv:0809.4882 Cited by: §I-A. [11] R. Kleinberg (2004) Nearly tight bounds for the continuum-armed bandit problem. In Advances in Neural Information Processing Systems 17, p. 697–704. Cited by: §I-A, §I-B. [12] K. Liu and Q. Zhao (2010-11) Distributed learning in multi-armed bandit with multiple players. IEEE Transactions on Signal Processing 58 (11), p. 5667–5681. Cited by: §I.