{"id":"fb3e1524-ade5-40f4-8742-c15a4ee7fb72","arxiv_id":"2411.13690","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New collaborative fixed-budget best-arm identification algorithms for stochastic linear bandits, with exponentially decaying error bounds and reduced communication on star and general networks.","lead":"Teams of agents collaboratively search for the option with the best hidden average reward from noisy linear observations within a fixed time budget. This paper proposes two algorithms for star-shaped and general communication networks and proves their error probability decays exponentially with the budget.","discovery_kind":"extension","skeptic_critique":null,"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies fixed-budget best-arm identification in stochastic linear bandits with multiple agents connected by a network. For star networks, MaLinBAI-Star divides the budget T into ⌈log K⌉ rounds, computes a G-optimal design over the current active set at the server, instructs every agent to pull each active arm in proportion to the design, aggregates the local ordinary least-squares statistics, and eliminates half the active arms by estimated expected reward; the last surviving arm is returned. For arbitrary networks, MaLinBAI-Gen partitions the graph into dominating sets, runs the star procedure inside each block, and the top-level server combines per-block outputs by majority vote with a variance-based tie-break. The main claims are the error bounds Pr[Error] ≤ 4 log K exp(−TMΔ²_min/(32d log K)) (star) and Pr[Error] ≤ 8 log K exp(−TΔ²_min/(32d log K)) (generic), communication costs O(2M log K) and O(2(M−|P|)log K + |P|), and near-optimality relative to the lower bounds of Yang-Tan [33] and the communication lower bound cited from [21]. Experiments on two synthetic settings and MovieLens 20M compare MaLinBAI-Star with OD-LinBAI, FedLinUCB, Async-LinUCB, and FALinPE in terms of error probability and communication cost.","tokens_in":15664,"tokens_out":31681,"duration_ms":309281,"significance":"The paper targets a genuine gap: fixed-budget collaborative best-arm identification in linear bandits sits between the federated fixed-confidence algorithm FALinPE [24] and the collaborative regret-minimization literature, and no previous work addresses it. The proposed combination of G-optimal designs with successive elimination is natural, and the claimed exponential decay of the error probability in the total budget TM at the single-agent rate up to log factors is the right qualitative result if the proofs can be completed. Strengths of the manuscript include explicit pseudocode for both algorithms, self-contained appendices that organize the concentration, Markov, and Kiefer-Wolfowitz arguments, and an experimental section that states the protocol, hyperparameters, and baselines for two synthetic instances and MovieLens 20M. The main theorems are, however, not established as written: three load-bearing gaps (integrality of the design-based pull counts, the formal projection argument for rank-deficient active sets, and the majority-vote tie case in Theorem 2) require new technical content, and the communication-cost claim mixes message counts with scalar counts.","major_comments":[{"comment":"Lemma 6 asserts the identity V_S = M b V(π_p), which requires every agent to pull each active arm exactly bπ_p(a_i) times in a round. Since bπ_p(a_i) is generally non-integral, the algorithm as written cannot execute these counts; any rounding changes the executed design matrix, and the Kiefer-Wolfowitz identity g(π*) = d invoked in step (B.8) then does not apply to the rounded design. This is the key step behind Lemma 1 and hence behind both Theorem 1 and Theorem 2. The paper needs a concrete pull-counting scheme (for example, randomized rounding, or deterministic rounding with a perturbation bound on ‖a‖²_{Ṽ^{-1}} relative to bV(π_p) valid when b is large compared with d²) together with the resulting condition on T or an explicit constant inflation.","section":"Algorithm 1, line 8; Lemma 6; Appendix B.1, steps (B.7)-(B.8)"},{"comment":"The projection of a rank-deficient active set is described only by the sentence 'we project the arms onto a lower dimensional space such that the matrix V_S becomes non-singular,' and no formal statement is given. The proof of Lemma 1 (steps (B.5)-(B.8)) works as if the unprojected R^d instance were non-singular and uses g(π*) = d. A complete argument must specify the projection (e.g., the orthogonal projection onto span(A_p)), show that ⟨θ*, a_1 − a_i⟩ is preserved for arms in the active set, and verify that the OLS estimator in the projected coordinates remains sub-Gaussian; the Kiefer-Wolfowitz constant then becomes the projected dimension d_p ≤ d, which is a conservative substitution. Because rank deficiency is guaranteed in later elimination rounds, this gap is load-bearing for the elimination argument.","section":"Section 2.1; Algorithm 1, lines 5-6; proof of Lemma 1"},{"comment":"The proof of Theorem 2 bounds the event {D_P > |P|/2} and claims that when a tie occurs 'it must be that strictly more than half of the blocks' fail to identify a_1. This containment is false: if |P| is even and exactly |P|/2 blocks select a suboptimal arm, the variance-based tie-break can select that suboptimal arm, so the error event is contained in {D_P ≥ |P|/2} rather than {D_P > |P|/2}. Markov's inequality applied to the ≥ event gives the same numerical bound, so Theorem 2 is recoverable, but the proof as written omits the tie case. The same issue appears in the proof of Lemma 2, where the best arm is eliminated when at least |A_p|/2 arms have strictly higher estimated reward, so the event should be {N_p ≥ |A_p|/2}.","section":"Appendix C.1 (proof of Theorem 2); Appendix B.2 (proof of Lemma 2)"},{"comment":"The reported communication cost O(2M log K) counts the number of data messages, but each agent transmits its local design matrix V_m (a d×d symmetric matrix) and vector D_m to the server, so the payload per agent per round is O(d²) scalars. Under the scalar-count measure standard in the distributed-bandit literature (and presumably in the lower bound compared in Appendix D.2), the cost is O(M d² log K), and the claimed near-optimality comparison is between incomparable metrics. The analysis can be repaired by noting that the server already knows the counts b_p(a_i) it assigned and hence can reconstruct V_m, so agents need send only per-arm reward sums; the paper should restate the cost in scalar units and adjust the comparison accordingly.","section":"Section 3, 'Communication cost'; Appendix D.2"}],"minor_comments":[{"comment":"The notation is inconsistent between the algorithm and the analysis: Equation (3.1) defines V_m and B_m, but Algorithm 1 initializes and refers to V_m and D_m, and line 14 mentions 'BS' where the surrounding text uses D_S. A single convention for the cross-covariance statistic would remove the confusion.","section":"Equations (3.1)-(3.2); Algorithm 1"},{"comment":"The displayed chain gives a denominator of 8 d ⌈log K⌉ after substituting the Kiefer-Wolfowitz bound, while (B.8) and the statement of Lemma 1 have 16 d ⌈log K⌉. The factor-of-two discrepancy does not invalidate the stated theorems (the bound with 16 is the weaker one), but the appendix arithmetic should be aligned.","section":"Appendix B.1, steps (B.6)-(B.8)"},{"comment":"The elimination step keeps the 'top K/2^p arms,' which is undefined when K/2^p is not an integer (e.g., K = 10 at round p = 2); the algorithm needs an explicit floor or ceil convention for the active-set sizes, and the halving statements in the proofs should be re-derived under that convention.","section":"Algorithm 1, lines 4 and 18"},{"comment":"The problem formulation allows R-sub-Gaussian noise with arbitrary R ≥ 0, but the noise scale R does not appear in any of the theoretical bounds; as stated, the bounds can hold only for a fixed scale such as R = 1. The statements should fix R = 1 or include R² in the exponents.","section":"Section 2; Lemma 1; Theorem 1; Theorem 2"},{"comment":"The algorithm computes a '1-approximate' G-optimal design, but the proofs invoke Kiefer-Wolfowitz (Lemma 3) with the exact value g(π*) = d; the approximation guarantee of the Frank-Wolfe procedure from [50] and its effect on the constants should be stated explicitly.","section":"Algorithm 1, line 7; Lemma 3"},{"comment":"The bound in Theorem 2 is obtained by lower-bounding every block size M_{P_i} by 1, so the number of agents M does not appear in the generic-network exponent; this loses the M-dependence of the star analysis, and the claim that MaLinBAI-Gen attains the same performance as MaLinBAI-Star should be qualified accordingly.","section":"Appendix C.1"},{"comment":"The near-optimality derivation is loose: the conversion of the [33] lower bound through H_{1,lin}(v) ≤ d/Δ²_min drops a log factor (log² d versus log d), so the claimed 'up to a factor of log d/log K' comparison should be re-derived before it is advertised.","section":"Appendix D.1"},{"comment":"The main experimental section evaluates MaLinBAI-Star only, even though MaLinBAI-Gen is one of the two headline algorithms, and the experimental regime (T = 150, d = 10, M = 15) corresponds to a theory exponent TMΔ²_min/(32d log K) of at most about 0.76 even at the largest gap, so the exponential bound is vacuous in this regime; including MaLinBAI-Gen and a high-budget regime would strengthen the empirical claims.","section":"Section 5; Appendix E.2"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a real gap and the proposed rates are plausible, but the main theorems are not proved as written; the three gaps (integrality of bπ(a_i) pulls, formal projection for rank-deficient active sets, and the ≥-event for the majority vote) all look locally fixable with standard techniques, so I recommend major revision rather than rejection. Two further points for editorial attention: the communication-cost claim needs to be restated in a unit consistent with the cited lower bounds, and the experimental regime is far from the regime where the proved bounds are non-vacuous. The self-citation [6] is contextual background and does not affect the results."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version. This is the first fixed-budget federated BAI algorithm for linear bandits that I know of, and the star-network guarantee is mostly sound. The generic-network extension has a real proof gap around ties, and the implementation has an unaddressed rounding problem, but both look fixable.\n\nThe new thing is the combination: G-optimal design plus successive elimination in a multi-agent fixed-budget setting. The paper correctly identifies that existing work covers fixed-confidence federated linear BAI (FALinPE) and fixed-budget distributed BAI for ordinary MABs, but not this mixture. Giving MaLinBAI-Star and MaLinBAI-Gen, with O(M log K) communication and exponentially decaying error bounds, is a legitimate subfield contribution.\n\nWhat I like. The high-probability argument for MaLinBAI-Star is clean: Lemma 6 relates the aggregated design matrix to the G-optimal design, Lemma 1 uses self-normalized concentration, and the elimination argument in Theorem 1 is standard. The dominating-set partition is a natural way to generalize to arbitrary graphs, and the error bound being independent of partition size is a nice property, even if the proof of it is a bit crude.\n\nWhere it gets soft. The biggest issue is integrality. Lemma 6 and step (B.7) require exactly b*pi_p(a_i) pulls per agent per round, and the code line b_p(a_i)=b*pi_p(a_i) does not make that integral. Rounding the counts changes V_S and can break the constant d from Kiefer-Wolfowitz. The paper needs an explicit rounding analysis, e.g., showing the design matrix perturbation is absorbed by constants. The projection step, when the active set does not span R^d, is also only sketched; no proof that the gap is preserved under projection. For Theorem 2, the proof claims that any error requires DP > |P|/2. That misses the event where exactly |P|/2 blocks err and the variance tie-break selects a wrong arm. Since the tie-break uses estimated variances, it is not deterministic binary, so the Markov argument should be on a different event or handle the tie explicitly. Finally, the near-optimality appendix is generous: the lower bound in [33] is single-agent, so matching it only shows the single-agent rate is preserved; that does not establish near-optimality in the collaborative setting. The communication lower bound from [21] is also for regret minimization, not pure exploration, so the matching claim is not directly supported.\n\nBottom line: this is a useful paper for the federated pure-exploration community, and it deserves a serious referee. I would send it to review and ask for a revision that fixes the tie-breaking case and the rounding analysis. If those hold up, it is a solid advance; if not, the star-network part still stands alone.","headline":"A plausible first fixed-budget federated BAI algorithm for linear bandits with a mostly sound star-network proof, but the generic-network theorem has a tie-breaking gap and the implementation leaves rounding unspecified.","tokens_in":16068,"tokens_out":3170,"would_cite":true,"duration_ms":42453,"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":"Multi-agent linear bandits can identify the best arm with error that decays exponentially in the time budget.","keywords":["fixed-budget best-arm identification","stochastic linear bandits","multi-agent collaboration","G-optimal design","successive elimination","dominating set partition","communication cost","federated pure exploration"],"falsifier":"Simulate Algorithm 1 with the actual integer pull counts used in line 8, computing the true pooled design matrix $V_S$ after one round, and compare $\\max_{a \\in A_p} \\lVert a \\rVert^2_{V_S^{-1}}$ with $(\\lceil \\log K\\rceil/(T M)) d$. If the ratio grows with $d$, $K$, or the rounding pattern, the Lemma 6 identity and the stated exponential rate fail; alternatively, a randomized-rounding variant that maintains the identity in expectation would confirm the intended mechanism.","tokens_in":15463,"feed_emoji":"🎯","tokens_out":6569,"duration_ms":65886,"temperature":0.7,"pith_summary":"This paper studies a fixed-budget collaborative best-arm identification problem: $M$ agents connected through a star network, or an arbitrary network coordinated through dominating-set blocks, must identify the best arm of a stochastic linear bandit by sharing information with a central server. The paper claims that two algorithms, MaLinBAI-Star and MaLinBAI-Gen, drive the probability of returning a wrong arm down exponentially in the total time budget $T$, at rates roughly $\\exp(-T M \\Delta_{\\min}^2/(32 d \\log K))$ for star networks and $\\exp(-T \\Delta_{\\min}^2/(32 d \\log K))$ for generic networks, with communication cost only $O(M \\log K)$ messages. The argument uses a successive-elimination schedule in which each round's arm pulls are chosen from a G-optimal design, and the aggregate design matrix across agents is shown to equal $M$ times the per-agent design. If the bounds hold, collaborative pure exploration in linear bandits can be run with very few communication rounds while the error probability improves multiplicatively with the number of agents.","feed_headline":"Best-arm error falls exponentially when agents share pulls","feed_subtitle":"A star or generic network finds the best arm with O(M log K) communication and a near-optimal error bound.","key_machinery":"The machinery is the pairing of successive elimination with G-optimal designs. In each round the server solves a 1-approximate G-optimal design $\\pi_p$ over the active arms, so by Kiefer-Wolfowitz the worst-case variance $\\lVert a \\rVert^2_{V(\\pi_p)^{-1}}$ is at most a constant $d$. The identity doing the work is Lemma 6: after aggregating $M$ agents, each of whom contributes $b$ pulls drawn from $\\pi_p$, the pooled design matrix is $b M V(\\pi_p)$, so the per-arm variance is $(\\lceil \\log K\\rceil/(T M)) \\lVert a \\rVert^2_{V(\\pi_p)^{-1}}$. That factor $1/(T M)$ is what converts a per-pull concentration inequality into the exponential $T M \\Delta^2$ bound. For generic networks, the same block-level protocol is wrapped in a dominating-set partition and a majority vote, which removes the graph size from the error bound.","core_discovery":"The central claim is that fixed-budget best-arm identification in stochastic linear bandits remains solvable in a distributed, federated model with exponentially decaying error probability. Concretely, MaLinBAI-Star runs $\\lceil \\log K \\rceil$ rounds of elimination; in each round each of $M$ agents pulls each active arm a fixed number of times prescribed by a 1-approximate G-optimal design, sends its local design and reward sums to the server, and the server eliminates the lower half of the estimated arm order. Theorem 1 states $\\mathbb{P}[\\mathrm{Error}] \\le 4 \\log K \\exp(-T M \\Delta_{\\min}^2/(32 d \\log K))$. MaLinBAI-Gen partitions an arbitrary graph into dominating sets, runs the star protocol inside every block with the dominant node as hub, and aggregates block answers by majority vote; Theorem 2 gives $\\mathbb{P}[\\mathrm{Error}] \\le 8 \\log K \\exp(-T \\Delta_{\\min}^2/(32 d \\log K))$, independent of the number of blocks. The paper further claims these rates are near-optimal against the single-agent lower bound of [33] up to a $\\log d/\\log K$ factor.","pith_inferences":["If the integrality gap in Lemma 6 is patched, say by randomized rounding that preserves the design matrix in expectation, the same proof template likely extends to any approximately optimal design because only the max-variance constant matters.","The generic-network result implies a scaling law: inserting more hubs (larger $|P|$) does not worsen the error bound but does reduce per-hub communication, so a user can trade communication for a fixed accuracy target.","A testable extension is to compare floor rounding against randomized rounding on MovieLens-style instances; the paper's reported error curves should be nearly identical if the $d$ constant survives rounding, and visibly worse otherwise.","The majority-vote tie-break by variance suggests a natural variant for heterogeneous agents: weight each block's vote by $1/\\lVert a \\rVert^2_{V^{-1}}$ instead of counting votes, which would smooth ties without changing the leading exponential factor."],"forward_implications":["Adding agents to a star network scales the exponent linearly: doubling $M$ squares the error bound at fixed budget.","MaLinBAI-Gen achieves the same order of error for arbitrary connected networks without needing a minimum dominating set, because the bound is free of $|P|$.","Communication cost is $O(M \\log K)$ messages for MaLinBAI-Star, so the price of collaboration is logarithmic in the arm count and linear in the agent count.","The error rate matches the single-agent minimax lower bound of [33] up to a $\\log d/\\log K$ factor, so the collaborative protocol does not waste the budget.","The generic algorithm works with any valid dominating-set partition, which makes it robust to the NP-hardness of minimum dominating set."],"supporting_citations":[{"why":"Supplies the single-agent minimax lower bound and the OD-LinBAI baseline that the paper extends and compares against.","marker":"[33]"},{"why":"Gives the Kiefer-Wolfowitz equivalence used to bound $\\max_a \\lVert a \\rVert^2_{V(\\pi)^{-1}}$ by the dimension $d$.","marker":"[52]"},{"why":"Provides the OLS concentration inequality behind Lemma 1 and the per-round elimination probability.","marker":"[10]"},{"why":"Is the federated fixed-confidence pure-exploration algorithm whose fixed-budget adaptation is a baseline and whose gap this paper fills.","marker":"[24]"},{"why":"Provides the asynchronous federated linear bandit baseline and the communication lower bound used in Appendix D.","marker":"[21]"},{"why":"Introduces the dominating-set partition approach for collaborative bandits over networks, adapted here to linear bandits.","marker":"[37]"},{"why":"Supplies the Frank-Wolfe algorithm used to compute the 1-approximate G-optimal design.","marker":"[50]"},{"why":"Defines dominating sets and partitions whose existence underlies the generic-network protocol.","marker":"[26]"}],"fun_headline_variants":["Exponential error decay in multi-agent linear bandits","Shared pulls make best-arm error fall exponentially","Distributed best-arm search with exponential error decay","Star-network agents identify best arm exponentially fast","Near-optimal error for distributed linear bandits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Lemma 6 treats the allocated pulls $b \\pi_p(a_i)$ as if each agent could pull each arm exactly that many times, but $b \\pi_p(a_i)$ is generally not an integer; if the algorithm rounds to integer counts, the design matrix changes and the constant $d$ in the Kiefer-Wolfowitz bound needs a separate rounding argument that the paper does not supply.","fun_headline_variants_meta":{"raw":{"variants":["Exponential error decay in multi-agent linear bandits","Shared pulls make best-arm error fall exponentially","Distributed best-arm search with exponential error decay","Star-network agents identify best arm exponentially fast","Near-optimal error for distributed linear bandits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00028,"raw_usage":{"total_tokens":1677,"prompt_tokens":979,"completion_tokens":698,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":595,"completion_tokens_details":{"reasoning_tokens":628}},"tokens_in":595,"tokens_out":698,"duration_ms":7680,"temperature":1.0,"reasoning_tokens":628,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:00:37.388618+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate Algorithm 1 with the actual integer pull counts used in line 8, computing the true pooled design matrix $V_S$ after one round, and compare $\\max_{a \\in A_p} \\lVert a \\rVert^2_{V_S^{-1}}$ with $(\\lceil \\log K\\rceil/(T M)) d$. If the ratio grows with $d$, $K$, or the rounding pattern, the Lemma 6 identity and the stated exponential rate fail; alternatively, a randomized-rounding variant that maintains the identity in expectation would confirm the intended mechanism.","supporting_citations":[{"cited_title":"CRC press, 2013","cited_arxiv_id":null,"evidence_quote":"Defines dominating sets and partitions whose existence underlies the generic-network protocol."},{"cited_title":"Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits","cited_arxiv_id":null,"evidence_quote":"Supplies the single-agent minimax lower bound and the OD-LinBAI baseline that the paper extends and compares against."},{"cited_title":"The Equivalence of Two Extremum Problems.Canadian Journal of Mathematics, 12:363–366, 1960","cited_arxiv_id":null,"evidence_quote":"Gives the Kiefer-Wolfowitz equivalence used to bound $\\max_a \\lVert a \\rVert^2_{V(\\pi)^{-1}}$ by the dimension $d$."},{"cited_title":"A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits.Advances in Neural Information Processing Systems, 35:4762–4775, 2022","cited_arxiv_id":null,"evidence_quote":"Provides the asynchronous federated linear bandit baseline and the communication lower bound used in Appendix D."},{"cited_title":"Collaborative Learning of Stochastic Bandits Over a Social Network.IEEE/ACM Transactions on Networking, 26(4):1782–1795, 2018","cited_arxiv_id":null,"evidence_quote":"Introduces the dominating-set partition approach for collaborative bandits over networks, adapted here to linear bandits."},{"cited_title":"SIAM, 2016","cited_arxiv_id":null,"evidence_quote":"Supplies the Frank-Wolfe algorithm used to compute the 1-approximate G-optimal design."}],"review_version":1}