{"id":"8bc58bc2-532c-48f9-92b7-a706c3187a3c","arxiv_id":"2505.10147","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Cl-BAI and BAI-Cl identify the best arm for each agent in clustered federated bandits with fixed-confidence guarantees, and a variant is shown order-wise minimax optimal when the number of clusters is constant.","lead":"This paper designs algorithms for identifying the best arm for every agent when agents are grouped into hidden clusters that share a bandit. It reports sample-complexity bounds, a lower bound, and tests on synthetic, MovieLens, and Yelp data.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"BAI-Cl phase-one correctness is not proven: with R=log(1/η)+1, SE has no margin for cross-cluster gaps exactly η, so S∩S_i need not be a singleton.","rationale":"The reader's weakest_assumption identifies the same off-by-one in BAI-Cl's first phase, and my re-derivation of Appendix 9.5 confirms the gap. The standard finite-round SE guarantee in Theorem 9.5 only eliminates arms whose gap exceeds 2ε_R; with R=log(1/η)+1, the separability gap η equals 2ε_R, so the invariant that S_i contains exactly the true best arm among S is not established. This is load-bearing because Algorithm 3 branches on S∩S_i being a singleton/nonempty, and a polluted S breaks the termination argument based on coupon collection. The concern is a proof gap rather than a demonstrated counterexample at the theorem level, since the survival probability of the exact-boundary arm is likely small and could be union-bounded, but the paper as written does not supply that bound. Thus the central δ-PC claim is not fully supported, and conditional acceptance pending a corrected proof is the right disposition. I do not see a second independent flaw in the lower bound or the near-optimality comparison that would change the verdict; those parts are plausible and the optimality claim is properly qualified to the N≫K, M=O(1) regime.","tokens_in":26426,"tokens_out":21194,"duration_ms":228722,"concrete_test":"Construct the two-bandit, two-arm hard instance with µ_{1,1}=µ_{2,2}=1 and µ_{1,2}=µ_{2,1}=1-η, so the cross-cluster gap is exactly η. Simulate Algorithm 3 line 7's SE call (Algorithm 2 with R=log(1/η)+1) and record the active set returned; then independently re-derive the probability that an arm with gap exactly η survives the final round, using the n_R=8 log(4KR²/γ)/ε_R² sample count. Check whether adding this survival event to the union bound in Proposition 9.11 keeps the total error at most δ. If the corrected bound fails, Theorem 5.2 is false; if it holds, the theorem needs only a repaired proof and an off-by-one fix in R.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 5.2 (Appendix 9.5, Proposition 9.11) treats the first phase of BAI-Cl as correct whenever the SE subroutine avoids its standard error event. But the finite-round guarantee in Theorem 9.5 only forces elimination of arms whose true gap is strictly larger than 2ε_R. Algorithm 3 line 7 sets R=log(1/η)+1, hence ε_R=2^{-R}=η/2, so the guarantee covers gaps strictly greater than η. Under Assumption 2.1, a best arm from another cluster can have gap exactly η to the current agent's best arm; such an arm is not guaranteed to be absent from S_i. Therefore S∩S_i can have size greater than one, or can be nonempty for an agent whose own cluster's best arm is not yet in S. Proposition 9.11 bounds only the standard SE error event; it does not bound this exact-boundary survival event. When it occurs, line 9 can select another cluster's best arm, S is polluted, and the coupon-collector while loop can exhaust A before |S|=M, so the algorithm can fail to terminate or return wrong arms. The same off-by-one appears in Algorithm 4/dSE (Proposition 9.19) and affects BAI-Cl++ correctness. This is a load-bearing gap in the central δ-PC claim, though it is repairable by choosing R so that ε_R<η/2 and adding the boundary survival event to the union bound.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies fixed-confidence best-arm identification in clustered federated multi-armed bandits. There are N agents divided into M unknown clusters, each cluster solves a K-armed stochastic bandit, and the best arms of different clusters are distinct and separated by a parameter η (Assumption 2.1). The learner must identify the best arm for every agent with probability at least 1−δ, minimizing sample and communication complexity. The paper proposes two algorithms: Cl-BAI, which clusters agents first via successive elimination and then runs BAI on one representative per cluster, and BAI-Cl, which samples agents, identifies their best arms until all M distinct best arms are collected, and then identifies each remaining agent's best arm within the candidate set. A variant BAI-Cl++ uses a distributed SE subroutine dSE under an additional assumption (Assumption 6.1). The paper claims δ-PC guarantees for both algorithms, high-probability sample-complexity bounds, a minimax lower bound E[T] ≳ max{M(K−M), N} log(1/δ)/Δ², and order-wise optimality of BAI-Cl++ when M is constant. Experiments on synthetic data, MovieLens, and Yelp are reported.","tokens_in":26664,"tokens_out":18296,"duration_ms":198536,"significance":"The problem formulation is natural and timely, and the two-phase decomposition is a sensible way to separate the clustering task from the best-arm identification task. If the guarantees are correct, the paper would provide an interesting near-optimal fixed-confidence result for clustered federated BAI, and the lower bound that isolates a per-bandit term and a per-agent term is a useful structural contribution. The Cl-BAI analysis and the minimax lower bound are largely standard and convincing, and the experimental section demonstrates the potential practical value of the methods. However, the main correctness proofs for BAI-Cl and BAI-Cl++ contain load-bearing gaps that must be repaired before the central claims can be accepted; the issues are local and repairable rather than fundamental.","major_comments":[{"comment":"Algorithm 3 line 7 calls SE with R=log(1/η)+1, which gives ε_R = 2^{-R} = η/2. The finite-round guarantee in Theorem 9.5 only forces elimination of arms whose gap to the best arm is strictly larger than 2ε_R = η. Under Assumption 2.1, a best arm of another cluster can have gap exactly η to the current agent's best arm, and such an arm may survive in S_i. Consequently S∩S_i is not proven to be the singleton {k*_{M(i)}}. If the agent comes from a cluster whose best arm is not yet in S, a nonempty S∩S_i can cause the algorithm to skip adding the true best arm, and the while loop can exhaust A before |S|=M or return a wrong Best Arm entry. Proposition 9.11 bounds only the standard SE error event and does not address this boundary survival event. The same off-by-one appears in dSE (Algorithm 4, line 3, and Proposition 9.19), where R=log(1/η)+1 means SE may return an active set of size greater than one, so the designation of a single candidate â is also undefined. This affects the proofs of Theorem 5.2 and Theorem 9.1 as written. The gap is repairable, e.g., by choosing R so that ε_R < η/2 and adding the boundary survival event to the union bound, or by strengthening Assumption 2.1 to strict separation.","section":"Algorithm 3, line 7; Proposition 9.11; Algorithm 4, Proposition 9.19"},{"comment":"The proof of Theorem 5.2 assumes in Claim 6 that each agent is assigned to a bandit uniformly at random, but Theorem 5.2 states δ-PC for every instance, and the problem definition in Section 2 does not randomize the agent-to-bandit mapping. If an instance has one very small cluster, the first phase may need to sample almost all N agents before collecting all M best arms; the union bound then involves a per-agent SE error probability γ, and with γ = δ·log(M/(M−1))/log(3M/δ) the total error bound Nγ need not be below δ. In addition, the displayed union bound in Proposition 9.11 uses a per-agent error of δ·log(M/(M−1))/(3·log(3M/δ)), which is a factor 3 smaller than the γ set in Algorithm 3 line 7, and it does not account for the second SE call at line 12 for agents whose intersection with S is empty. These discrepancies must be fixed, for example by taking γ = δ/(3N) and union-bounding over the worst-case N, or the theorem should be restricted to the uniform-assignment model.","section":"Proposition 9.11 / Algorithm 3 line 7"}],"minor_comments":[{"comment":"The algorithm names are inconsistent: the text uses CL-BAI and BAI-CL in some places and Cl-BAI and BAI-Cl in others; please standardize the notation.","section":"Section 1.1, Theorem 4.4"},{"comment":"Several figure references appear as '??' in the text; the figures need to be correctly inserted and cited.","section":"Section 8 and Appendix 9.11"},{"comment":"The line 'Best Arm[i]=S_i,[N]→[N]\\i' is malformed; please clarify what is removed from the agent set and how an agent with |S_i|=1 is treated in the subsequent graph construction.","section":"Algorithm 1, line 7"},{"comment":"The proof of Theorem 7.1 describes the hard instance using the parameter η, while the theorem statement uses Δ; please state explicitly that the hard instances satisfy Assumption 2.1 with η = Δ.","section":"Appendix 9.9"},{"comment":"The notation '(â, µhat) = SE(S, δ_k, R=...)' is inconsistent with Algorithm 2, which returns a set A_R; please define how a single candidate â is chosen when the active set has more than one element.","section":"Algorithm 4"},{"comment":"The instance-dependent lower bound uses undefined indices i and j in the KL divergences and is too terse to verify; it should be expanded or removed.","section":"Appendix 9.10"}],"recommendation":"major_revision","confidential_remarks":"The paper has a plausible central contribution, and the Cl-BAI analysis and lower bound appear to be in good shape. My recommendation is driven by two repairable but load-bearing gaps in the BAI-Cl/BAI-Cl++ correctness proofs: the exact-boundary off-by-one in the finite-round successive-elimination calls, and the mismatch between the δ-PC claim for all instances and the uniform-assignment coupon-collector assumption. Both can be fixed with local changes, so I would be willing to accept after a careful revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about arXiv:2505.10147. First, it studies a genuinely new problem: fixed-confidence best-arm identification when N agents are grouped into M unknown clusters, each solving its own stochastic bandit, and the agent-to-bandit map is hidden. Second, the main correctness theorem for the BAI-Cl algorithm has a real off-by-one error. It is fixable, but as written the delta-PC claim is not proven.\n\nThe formulation is well motivated and clearly positioned against prior clustered-bandit work, which mostly targets regret. The Cl-BAI two-phase structure and the minimax lower bound (Theorem 7.1) are plausible and follow standard arguments. The coupon-collector analysis for the first phase of BAI-Cl is a nice touch. The MovieLens and Yelp experiments are useful sanity checks, though figure references are broken (shown as \"??\") and no code or data are shipped.\n\nThe load-bearing problem is in the proof of Theorem 5.2. Algorithm 3 runs SE with R = log(1/eta)+1, so epsilon_R = eta/2. Theorem 9.5 only guarantees elimination of arms whose gap is strictly larger than 2 epsilon_R = eta. But Assumption 2.1 allows a different cluster's best arm to have gap exactly eta under the current agent's bandit. Such an arm can survive the first phase, making S intersect S_i non-singleton, or nonempty for an agent whose cluster has not appeared yet. Then line 9 can select another cluster's best arm, S gets polluted, and the while loop can fail to terminate. The same issue appears in dSE (Algorithm 4) and therefore affects BAI-Cl++. Proposition 9.11 bounds only the usual SE error event; it does not handle this exact-boundary survival event. This is a genuine off-by-one, not a stylistic nit. The fix is straightforward: choose R so epsilon_R < eta/2, for example add one extra round, and include the boundary survival event in the union bound. I do not see an obstacle to that repair.\n\nIf you work on federated or clustered bandits, this paper is worth reading for the formulation and the lower bound, but I would not rely on the BAI-Cl/BAI-Cl++ guarantees until a corrected revision appears. The Cl-BAI analysis looks like the more trustworthy half. The paper deserves a serious referee; with a fixed phase-one proof it could be a solid contribution. In its current form I would not cite it for the optimality claims.","headline":"New problem formulation worth a look, but the central delta-PC guarantee for BAI-Cl and BAI-Cl++ has an off-by-one boundary flaw that needs fixing before the results can be trusted.","tokens_in":27243,"tokens_out":2648,"would_cite":false,"duration_ms":26775,"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":"Two-phase successive elimination identifies every agent's best arm at near-optimal sample cost.","keywords":["best arm identification","clustered bandits","federated bandits","successive elimination","fixed-confidence","sample complexity","minimax lower bound","multi-armed bandits"],"falsifier":"Run BAI-Cl or BAI-Cl++ on a two-bandit, two-arm instance with $\\mu_{1,1}=1$, $\\mu_{1,2}=0$, $\\mu_{2,1}=0$, $\\mu_{2,2}=1$, so that Assumption 2.1 holds with equality at $\\eta=1$, and check whether an agent from bandit 1 ever reports arm 2 as its best arm with probability exceeding $\\delta$.","tokens_in":26169,"feed_emoji":"🎯","tokens_out":9808,"duration_ms":88424,"temperature":0.7,"pith_summary":"This paper studies a federated bandit setting in which $N$ agents are each solving one of $M$ unknown stochastic bandit problems that all share a common set of $K$ arms; the agent-to-bandit mapping is unknown. It claims that two successive-elimination algorithms, Cl-BAI and BAI-Cl, identify the best arm for every agent with probability at least $1-\\delta$, and that their sample complexity tracks a new minimax lower bound $\\max\\{M(K-M),N\\}\\log(1/\\delta)/\\Delta^2$. For a variant called BAI-Cl++, the paper shows that when the number of clusters $M$ is constant the sample complexity is order-wise minimax optimal. Because the algorithms only communicate arm indices and small summaries, they also give explicit communication-cost trade-offs, and experiments on synthetic, MovieLens, and Yelp data show large pull-count savings over a cluster-oblivious baseline.","feed_headline":"Two-phase elimination finds every cluster's best arm near-optimally","feed_subtitle":"When M clusters hide among N agents, pull counts match a new lower bound up to constants.","key_machinery":"The load-bearing object is the successive-elimination subroutine $\\mathrm{SE}(\\mathcal{A},\\gamma,R)$, which keeps an active set of arms that are within the current threshold $\\epsilon_r=2^{-r}$ of the empirical best arm and stops after $R$ rounds or when one arm remains. Its guarantees supply the high-probability event that lets Cl-BAI and BAI-Cl trust surviving arm sets. Around it the paper builds two organizing mechanisms: a graph whose edges join agents with close empirical mean vectors (Cl-BAI), and a coupon-collector sampling loop that accumulates the $M$ best arms before reducing each remaining agent to an $M$-arm identification problem (BAI-Cl). BAI-Cl++ replaces the final subroutine with a verification-based elimination routine $\\mathrm{dSE}$ that uses known separation $\\eta_1$ to skip redundant pulls.","core_discovery":"On the paper's own terms, the central claim is that best-arm identification in clustered bandits splits cleanly into two subtasks: discover the $M$ distinct best arms, and assign each agent to the bandit it is learning. Cl-BAI solves clustering first by having every agent run successive elimination and then grouping agents whose surviving empirical mean estimates agree within $\\eta/2$; BAI-Cl solves identification first by sampling agents until a coupon-collector argument guarantees every cluster is represented, then running a cheap $M$-arm identification for each remaining agent. The claimed theorem is that both schemes are $\\delta$-PC under an $\\eta$-separability condition, and that the improved BAI-Cl++ variation, which additionally uses an $\\eta_1$-gap between best-arm means across bandits, matches the lower bound order-wise when $M=\\Theta(1)$ and $N\\gg K$.","pith_inferences":["If the boundary case $\\mu_{b,k_b^*}-\\mu_{b,k_a^*}=\\eta$ is handled by a slightly larger elimination budget, the same proof structure would extend BAI-Cl's $\\delta$-PC guarantee to exact equality in Assumption 2.1 without changing the order of the sample complexity.","The max-form lower bound suggests a general principle for clustered pure exploration: the sample complexity is the maximum of the cost of discovering all cluster-specific optima and the cost of assigning agents to clusters, so algorithms can be designed by optimizing each subtask separately.","The $\\eta_1$-based verification in dSE could be replaced by an adaptive confidence-interval test, which would remove the need to know $\\eta_1$ in advance and make BAI-Cl++ applicable to settings where the separation between best-arm means is unknown."],"forward_implications":["If BAI-Cl++ is order-wise minimax optimal for constant $M$, then in the regime $N\\gg K$ the worst-case pull count for any $\\delta$-PC algorithm is $\\Theta(N\\log(1/\\delta)/\\Delta^2)$: one pays linearly in the number of agents just to certify which bandit each agent is solving.","BAI-Cl's first phase converts the per-agent cost of identifying one of $K$ arms into a shared cost of identifying $M$ best arms plus $N\\cdot M/\\eta^2$ pulls for assignment, which is favorable whenever $M\\ll K,N$.","Cl-BAI can be parallelized across agents and is robust to cluster-size skew, because it does not need to sample a representative of every cluster before clustering.","The algorithms' communication costs differ by a factor of roughly $M\\log K$ versus $K$; the optimal choice between Cl-BAI and BAI-Cl therefore depends on whether bits or pulls are the scarcer resource."],"supporting_citations":[{"why":"supplies the PAC elimination bound and subroutine that the two phases inherit.","marker":"Even-Dar et al., 2002"},{"why":"states the successive-elimination procedure whose active-set guarantees the algorithms rely on.","marker":"Zhou, 2019"},{"why":"provides the change-of-measure lemma used to prove the minimax lower bound.","marker":"Kaufmann et al., 2016"},{"why":"defines the cluster-oblivious baseline and its sample complexity that the paper compares against.","marker":"Jamieson & Nowak, 2014"},{"why":"gives coupon-collector tail bounds for unequal probabilities used to bound BAI-Cl's first phase.","marker":"Dudzic, 2009"}],"fun_headline_variants":["Clustered bandit BAI: two-phase elimination matches lower bound","When M is constant, BAI-Cl++ is order-optimal in samples","Cluster first or identify first: both near-optimal for BAI","Two-phase BAI: hidden clusters, minimax sample counts","Elimination-based BAI for clustered bandits nears lower bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that after the first-phase successive-elimination run, each sampled agent's surviving set contains exactly its own bandit's best arm and none of the other bandits' best arms; the stated number of rounds only guarantees this for gaps strictly larger than $\\eta$, so an arm whose gap equals $\\eta$ can survive.","fun_headline_variants_meta":{"raw":{"variants":["Clustered bandit BAI: two-phase elimination matches lower bound","When M is constant, BAI-Cl++ is order-optimal in samples","Cluster first or identify first: both near-optimal for BAI","Two-phase BAI: hidden clusters, minimax sample counts","Elimination-based BAI for clustered bandits nears lower bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000512,"raw_usage":{"total_tokens":2511,"prompt_tokens":990,"completion_tokens":1521,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":606,"completion_tokens_details":{"reasoning_tokens":1427}},"tokens_in":606,"tokens_out":1521,"duration_ms":12142,"temperature":1.0,"reasoning_tokens":1427,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:16:47.257843+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run BAI-Cl or BAI-Cl++ on a two-bandit, two-arm instance with $\\mu_{1,1}=1$, $\\mu_{1,2}=0$, $\\mu_{2,1}=0$, $\\mu_{2,2}=1$, so that Assumption 2.1 holds with equality at $\\eta=1$, and check whether an agent from bandit 1 ever reports arm 2 as its best arm with probability exceeding $\\delta$.","supporting_citations":[{"cited_title":"Pac bounds for multi-armed bandit and markov decision processes","cited_arxiv_id":null,"evidence_quote":"supplies the PAC elimination bound and subroutine that the two phases inherit."},{"cited_title":"Ie 498: Online learning and decision making, fall 2019 sep","cited_arxiv_id":null,"evidence_quote":"states the successive-elimination procedure whose active-set guarantees the algorithms rely on."},{"cited_title":"and Nowak, R","cited_arxiv_id":null,"evidence_quote":"defines the cluster-oblivious baseline and its sample complexity that the paper compares against."},{"cited_title":"93.16 the coupon collector's problem with unequal probabilities","cited_arxiv_id":null,"evidence_quote":"gives coupon-collector tail bounds for unequal probabilities used to bound BAI-Cl's first phase."}],"review_version":1}