{"id":"b88fcc36-04be-4fba-b434-3d9e7082ba67","arxiv_id":"2608.10526","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Cooperative multiplayer Lipschitz bandits with an unknown Lipschitz constant achieve T^(Md+1)/(Md+2)-scale regret in three information structures, with dithering synchronizing the players' discretizations.","lead":"Multiple agents must choose continuous actions to earn rewards, but they cannot talk to each other and do not know how smoothly the rewards vary. This paper proves they can still agree on the same action grid, and that the random-offset trick used to reach agreement costs nothing to first order.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"All three theorems are stated under m >= 8N/L, a condition involving the unknown N/L ratio; Appendix B defers the necessary parameter choice to 'suitable alpha,gamma > 0', so the claimed mECAB leading-order bound is not actually demonstrated as an unconditional finite-time statement.","rationale":"The reader identified the Problem B signalling mechanism as the weakest assumption. That is a legitimate formalization gap, and it affects Theorem 5, but it is localized to one of the three information structures and can be repaired by specifying an explicit encoding/decoding map and restating E' as M(E-1) rather than ME. The concern I find more load-bearing is that all three theorems, including the headline Problem C dithered-coordination result, depend on m >= 8N/L. This condition involves the unknown parameters L and N, and the proof never supplies explicit choices of alpha and gamma that simultaneously satisfy the condition, keep exploration and disagreement terms at the claimed order, and give a finite-time threshold. The paper's own Corollary 3 acknowledges the condition is asymptotic ('for all large T'), but the theorem statements and abstract do not carry the corresponding quantifier, so the central claim overreaches what the proof demonstrates. This is a gap in the derivation rather than a contradiction: the rates are plausible, and Lemma 6's dithering argument is sound. The verdict remains CONDITIONAL because the missing explicit parameter regime and the unverified m >= 8N/L qualification should be supplied before the unconditional leading-order claim is accepted. I credit the paper for the correct high-level decomposition and for the honest statement that the experiments do not implement the signalling and dithering mechanisms.","tokens_in":7855,"tokens_out":25183,"duration_ms":251384,"concrete_test":"Re-derive Appendix B with explicit parameter choices, e.g., alpha = (Md-1)/(2(Md+2)^2) and gamma = Md/(4(Md+2)^2), so that m = floor(T^alpha) and E = m^2 M ceil(T^{2gamma(Md+2)/Md}). Compute the exploration cost Em^{Md} and the Problem C disagreement term 17Tm sqrt(ln(A)/E), and verify they are O(T^{(Md+1)/(Md+2)}). Then write the threshold T_0(L,N) beyond which m(T) >= 8N/L, and check inequality (6) for an explicit f in F_{L,N} with N/L large, such as f(x) = 10^{-6} sin(10^6 x_1) with L = 1, Md = 2, at T below T_0. If the bound fails for T < T_0, Theorems 4-7 require the qualifier 'for T >= T_0(L,N)'.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim requires Theorems 4, 5, and 7, whose proofs all begin with 'By Corollary 3, which applies since m >= 8N/L' to obtain eL_m >= L/8 - 1. That lower bound controls the discretization-bias term LT/e_m in inequality (6); without it, L/eL_m^{2/(Md+2)} is uncontrolled and the displayed regret rate is not derived. But m is an input of Algorithm 1, effectively chosen as m = floor(T^alpha) before L and N are known, and no player can verify m >= 8N/L. Corollary 3 itself says the condition holds 'for all large T under the choice of m made in the proofs', yet Appendix B never supplies explicit choices: it only says to take m = floor(T^alpha) and E = m^2 M ceil(T^{2gamma(Md+2)/Md}) 'for suitable alpha, gamma > 0'. For a fixed horizon T, the class F_{L,N} contains functions with arbitrarily large N/L, for example f(x) = epsilon sin(k x_1) with epsilon k = L and second-derivative bound N approximately epsilon k^2; for such functions, a slow-growing m can stay below 8N/L for astronomically large T. When m < 8N/L, the Corollary 3 lower bound is absent and the proof does not go through. The theorem statements quantify the regret at every T with no 'sufficiently large' qualifier, so the abstract's assertion that mECAB attains the stated order in all three information structures is not established as a finite-time statement about the algorithm.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies cooperative multi-player Lipschitz bandits on the joint action space [0,1]^Md when the Lipschitz constant L is unknown. The proposed meta-algorithm mECAB explores a coarse m^Md grid to form an upper confidence bound on L, sets a finer discretization e_m, and then runs an existing finite multi-player MAB subroutine. Three information structures are treated: common rewards with unobserved actions (Problem A), observed actions with independent rewards (Problem B), and unobserved actions with independent rewards (Problem C). The paper claims regret of order T^{(Md+1)/(Md+2)} (L+1)^{Md/(Md+2)} sqrt(log T) for all three structures, achieving agreement through shared statistics in A, action-based signalling in B, and dithered quantization in C. The appendix proves the dithering lemma and gives a regret decomposition in terms of exploration cost, discretization bias, a disagreement term, and subroutine regret.","tokens_in":8030,"tokens_out":5945,"duration_ms":54783,"significance":"If the finite-time issues identified below are repaired, the paper makes a useful conceptual contribution: it isolates coordination, rather than estimation accuracy, as the binding constraint when L is unknown, and it shows that agreement can be obtained for free in Problems A and B and with dithered randomization in Problem C without changing the leading regret order. The proof of Lemma 6 is elementary and appears correct, the reduction to existing subroutines is clean, and the paper is honest in stating that the signalling and dithering mechanisms are not simulated. The main gap is that the central theorems are not currently demonstrated as unconditional finite-time statements about mECAB as written.","major_comments":[{"comment":"The proof of Theorems 4, 5, and 7 requires Corollary 3's lower bound eL_m ≥ L/8 − 1, which is invoked under the condition m ≥ 8N/L. This condition is an input of Algorithm 1, but neither L nor N is known to the players, and no player can verify it. Appendix B states only that m = floor(T^α) and E = m^2 M ceil(T^{2γ(Md+2)/Md}) for 'suitable α,γ > 0', without giving explicit values or a condition on T. For a fixed T and slow-growing m, the class F_{L,N} contains functions with arbitrarily large N/L, for example f(x) = ε sin(k x_1) with εk = L and N approximately εk^2, so m < 8N/L is possible for astronomically large T. When m < 8N/L, the displayed regret bound in (6) is not derived. Please make the parameter choice explicit, add a 'sufficiently large T' quantifier depending on N/L, or design an adaptive choice of m, and state the theorems accordingly.","section":"Appendix B, Eq. (6); Corollary 3"},{"comment":"Problem B's signalling mechanism assumes that a player can encode its real-valued empirical bin mean exactly in a single observable in-bin action, that all other players decode it exactly, and that this costs one sample per bin without biasing the empirical means or otherwise changing the bandit feedback model. This is not formalized anywhere; Theorem 5's improvement from E to E′ = ME is precisely the pooling gain created by this assumption. The paper's own experiments do not simulate the mechanism (Section VII, final paragraph: 'simulating the signalling and dithering steps directly is left to an extended version'). Please either supply a concrete finite-precision encoding/decoding protocol with a quantization-error term in the concentration argument, or state Theorem 5 as conditional on this idealization.","section":"Section V, Eq. (3); Theorem 5"}],"minor_comments":[{"comment":"The phrase 'thesamediscretization' should read 'the same discretization'.","section":"Abstract"},{"comment":"The displayed bound uses L^{Md/(Md+2)} while the proof and the abstract use (L+1)^{Md/(Md+2)}; these are not equivalent for L < 1, so please align the statements.","section":"Theorem 4"},{"comment":"The floor brackets around X_i + U appear to be missing in the typesetting of Eq. (4); please clarify the notation.","section":"Eq. (4)"},{"comment":"After devoting one sample per bin to signalling, the empirical mean in (3) is based on E−1 samples, but Theorem 5 and Corollary 3 use E; please state that E′ = M(E−1) or explain why the convention is harmless.","section":"Section V"},{"comment":"The experiments model only the feedback type and do not implement the signalling step of Problem B or the dithering step of Problem C; the text should make explicit that the experimental curves are not full implementations of the algorithms analyzed in Theorems 5 and 7.","section":"Section VII"}],"recommendation":"major_revision","confidential_remarks":"The core dithering lemma and the regret decomposition are sound, and I believe the paper is publishable after the finite-time parameterization and the Problem B signalling formalism are fixed. The main risk is that the current statements overclaim an unconditional guarantee for mECAB; a careful statement with explicit parameter choices and a T_0(N/L) quantifier would resolve the issue."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing you should know: the paper's core technical contribution—the dithered quantization for agreement in Problem C—is correct and genuinely new. Lemma 6's proof checks out, the uniformization of the rounding boundary is neat, and the observation that deterministic rounding cannot give instance-independent agreement is a good catch. The reduction to existing multiplayer MAB subroutines is honest. If you work on cooperative bandits, this is worth reading.\n\nNow the soft spots. The main theorems are all stated as \"Let m >= 8N/L\" and then give a sup_{F_{L,N}} regret bound. Since m is an input the players choose before knowing L or N, the bound is not a statement about an implementable algorithm—it is conditional on a quantity no one can verify. The appendix says to pick m = floor(T^alpha) and E = m^2 M ceil(T^{2 gamma (Md+2)/Md}) \"for suitable alpha, gamma > 0\" and never specifies them. That means the claimed leading-order match is not demonstrated as a finite-time statement over the class. For any fixed T and m, there are smooth functions in F_{L,N} with N/L large enough to violate the condition, so the sup bound as written is not actually proven. This is not fatal if one interprets the results as asymptotic for each fixed problem, but the theorems do not say \"sufficiently large T,\" and the abstract oversells the unconditional nature.\n\nProblem B's signaling mechanism is also an idealization: a real-valued empirical mean encoded exactly in a single action, decoded perfectly, costing one sample. That is fine as a thought experiment, but it is not formalized as an encoding/decoding scheme with quantization noise, and the experiments do not implement it (nor the dithering—they model only the feedback structure). Minor: no code or data, only 10 trials.\n\nWhere I agree with your reader: the dithering lemma is solid, the regret decompositions are standard, and the reduction to [10], [11] is a reduction, not circularity. But the parameter-selection gap is real and should be fixed either by explicit choices that yield the claimed order for all large T, or by stating the bounds with the m >= 8N/L condition as an explicit assumption, likely with a \"for sufficiently large T\" qualifier.\n\nI would send this to a serious referee: the dithering idea is worth disseminating and a referee can push for the explicit parameter regime. I would cite the dithering lemma in follow-up work, but I would not cite the main theorem as an unconditional finite-time bound until the condition is resolved. For a reading group, maybe—the discussion of what counts as \"knowing L\" in decentralized settings is valuable.","headline":"The dithering lemma is correct and the coordination problem is real, but the main theorems rest on an unverifiable m >= 8N/L condition and the appendix never supplies the parameter choices that would make the bounds unconditional.","tokens_in":8747,"tokens_out":3391,"would_cite":true,"duration_ms":30989,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that mECAB coordinates multiplayer Lipschitz bandits with an unknown smoothness constant and preserves the leading-order regret in all three information structures.","keywords":["Lipschitz bandits","multiplayer bandits","unknown Lipschitz constant","information asymmetry","discretization","dithered quantization","regret bounds","cooperative learning"],"falsifier":"Run a Problem B simulation in which the encoded empirical mean is quantized to finite precision, say rounded to $1/\\log T$, before being placed in the action, and check whether the $M$-fold pooling gain in Theorem 5 survives; if regret degrades, the exact-encoding assumption carries the result. The same direct test applies to the dithered rounding in Problem C, which the paper's experiments do not simulate.","tokens_in":7428,"feed_emoji":"🎲","tokens_out":12324,"duration_ms":101706,"temperature":0.7,"pith_summary":"The paper studies cooperative multiplayer bandits on continuous, Lipschitz action spaces when the smoothness constant $L$ is not known in advance. Its central claim is that one meta-algorithm, mECAB, can estimate $L$, place all players on the same finite discretization of the joint action space, and run a cooperative bandit subroutine while keeping regret at order $T^{(Md+1)/(Md+2)}(L+1)^{Md/(Md+2)}\\sqrt{\\log T}$ in all three information structures. The contribution is to show that the coordination constraint, reaching the same grid from private data without communication, does not change the leading regret scale. A sympathetic reader should care because the unknown-$L$ setting is the natural distributed analogue of continuum-armed bandits, and the paper argues that the missing constant costs nothing in the leading order.","feed_headline":"Unknown Lipschitz constant no longer blocks cooperative bandits","feed_subtitle":"Estimate the smoothness once, get every player on the same grid, and keep the regret rate.","key_machinery":"The load-bearing object is the padded upper-confidence estimator $\\tilde L = \\hat L + m\\sqrt{(2/E')\\ln(2m^{Md}T)}$, where $\\hat L$ is the largest empirical mean difference between neighboring bins and $E'=ME$ in Problem B, $E$ otherwise. It sets the discretization level, so all players' grids agree exactly when their $\\tilde L$ values agree. In Problem C that agreement is engineered by dithered quantization: the players share $U\\sim\\mathrm{Unif}[0,1)$ and round $X_i+U$, which makes the distance to a rounding boundary uniform rather than instance-dependent, so disagreement probability is bounded by $17m\\sqrt{\\ln(4M(2m)^{Md})/E}$. In Problem B the final action of each bin carries the sender's empirical mean, multiplying the effective sample count by $M$. Corollary 3 is the proof's hinge: it keeps $\\tilde L$ between the expected raw estimate $L_m$ and $L$ plus a concentration width, preventing grids that are too coarse.","core_discovery":"The paper's central discovery is that coordination can be bought by different mechanisms depending on what players see, and in every case without sacrificing the leading regret rate. Shared rewards make each player's bin means identical, observable actions let a player encode its empirical bin mean in one sample and let teammates decode it, and when neither is available a shared random dither $U\\sim\\mathrm{Unif}[0,1)$ applied as $\\lfloor X_i+U\\rfloor$ makes the rounded estimate agree with probability independent of the instance. The same padded estimator $\\tilde L = \\hat L + m\\sqrt{(2/E')\\ln(2m^{Md}T)}$, with $E'=ME$ in Problem B and $E$ otherwise, then determines the grid, and Theorems 4, 5, and 7 give $\\sup_{\\mathcal{F}_{L,N}} R_T$ of order $T^{(Md+1)/(Md+2)}$ up to a factor $(L+1)^{Md/(Md+2)}\\sqrt{\\log T}$. The upshot is that in the worst case over $L$-Lipschitz, Hessian-bounded reward functions, unknown smoothness is as cheap as known smoothness.","pith_inferences":["Implicit extension: the dithering device transfers to any distributed problem where agents must agree on a real-valued parameter from noisy private estimates, so it could be used for step sizes, thresholds, or clock offsets, not only Lipschitz constants.","Implicit consequence: the Problem B signalling mechanism depends on the action space being continuous; in a finite-action model there is no room to encode a real number without distorting the learning problem, so the continuum assumption is doing essential work.","Gap noted by the paper's own experiments: the signalling and dithering steps are never simulated; an end-to-end test with finite-precision signalling would check whether the guarantees survive implementation details."],"forward_implications":["In all three information structures, mECAB attains $\\sup_{\\mathcal{F}_{L,N}} R_T$ of order $T^{(Md+1)/(Md+2)}(L+1)^{Md/(Md+2)}\\sqrt{\\log T}$, so an unknown $L$ does not change the leading regret scale.","Common rewards alone (Problem A) make coordination free: every player forms the same $\\hat L$ and the same grid, with no extra agreement term in the regret.","Observable actions (Problem B) coordinate the players and simultaneously sharpen the estimate, since signalling gives each bin an effective sample size of $ME$ rather than $E$.","In the hardest setting (Problem C), a shared dither makes the probability of grid mismatch instance-independent, and choosing $E\\ge m^2 T^{2/(Md+2)}\\ln A$ keeps the disagreement term at the leading order."],"supporting_citations":[{"why":"Supplies the raw Lipschitz estimator and Lemma 1, on which the padded upper-confidence bound is built.","marker":"[8]"},{"why":"Provides the cooperative multiplayer subroutine and its regret bound used in Problems A and C.","marker":"[10]"},{"why":"Provides the multiplayer subroutine and regret bound used in Problem B.","marker":"[11]"},{"why":"Gives the discretize-then-run-UCB template for continuum bandits that mECAB follows.","marker":"[6]"},{"why":"Defines the multiplayer Lipschitz bandit setting and information structures that this paper extends to unknown L.","marker":"[4]"},{"why":"The closest prior work, assuming a known Lipschitz bound; it frames the gap being closed.","marker":"[12]"}],"fun_headline_variants":["Coordination without knowing smoothness: same grid, best regret","Unknown Lipschitz? Players still find a common grid","Estimate smoothness once, coordinate all players, same regret","No Lipschitz constant? Still achieve optimal regret"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that in the observed-actions setting (Problem B) a player can encode its real-valued empirical bin mean exactly in one observable action, that teammates decode it exactly, and that spending this sample does not bias the bin estimates; the pooled $E'=ME$ concentration behind Theorem 5 and all of Problem B's improvement depend on this idealization.","fun_headline_variants_meta":{"raw":{"variants":["Coordination without knowing smoothness: same grid, best regret","Unknown Lipschitz? Players still find a common grid","Estimate smoothness once, coordinate all players, same regret","No Lipschitz constant? Still achieve optimal regret"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000644,"raw_usage":{"total_tokens":2962,"prompt_tokens":950,"completion_tokens":2012,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":566,"completion_tokens_details":{"reasoning_tokens":1953}},"tokens_in":566,"tokens_out":2012,"duration_ms":15286,"temperature":1.0,"reasoning_tokens":1953,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:22:16.050935+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a Problem B simulation in which the encoded empirical mean is quantized to finite precision, say rounded to $1/\\log T$, before being placed in the action, and check whether the $M$-fold pooling gain in Theorem 5 survives; if regret degrades, the exact-encoding assumption carries the result. The same direct test applies to the dithered rounding in Problem C, which the paper's experiments do not simulate.","supporting_citations":[{"cited_title":"Lipschitz Bandits without the Lipschitz Constant","cited_arxiv_id":"1105.5041","evidence_quote":"Supplies the raw Lipschitz estimator and Lemma 1, on which the padded upper-confidence bound is built."},{"cited_title":"Nearly tight bounds for the continuum-armed bandit problem,","cited_arxiv_id":null,"evidence_quote":"Gives the discretize-then-run-UCB template for continuum bandits that mECAB follows."},{"cited_title":"Multiplayer Information Asymmetric Bandits in Metric Spaces","cited_arxiv_id":"2503.08004","evidence_quote":"Defines the multiplayer Lipschitz bandit setting and information structures that this paper extends to unknown L."},{"cited_title":"Cooperative multi-player bandit optimization,","cited_arxiv_id":null,"evidence_quote":"The closest prior work, assuming a known Lipschitz bound; it frames the gap being closed."}],"review_version":1}