Pith. sign in

REVIEW 4 major objections 8 minor 55 references

Multi-Agent Best Arm Identification in Stochastic Linear Bandits

T0 review · 4 major / 8 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Multi-agent linear bandits can identify the best arm with error that decays exponentially in the time budget.

desk verdict 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. read the letter →

arxiv 2411.13690 v2 pith:DLYTFQ4N submitted 2024-11-20 cs.LG

Sanjana Agrawal , Saúl A. Blanco This is my paper · ORCID
classification cs.LG
keywords fixed-budgetbest-armidentificationstochasticlinearbanditsmulti-agentcollaborationG-optimaldesignsuccessiveeliminationdominatingsetpartitioncommunicationcostfederatedpureexploration
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 8 minor

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.

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 (4)
  1. [Algorithm 1, line 8; Lemma 6; Appendix B.1, steps (B.7)-(B.8)] 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.
  2. [Section 2.1; Algorithm 1, lines 5-6; proof of Lemma 1] 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.
  3. [Appendix C.1 (proof of Theorem 2); Appendix B.2 (proof of Lemma 2)] 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}.
  4. [Section 3, 'Communication cost'; Appendix D.2] 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.
minor comments (8)
  1. [Equations (3.1)-(3.2); Algorithm 1] 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.
  2. [Appendix B.1, steps (B.6)-(B.8)] 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.
  3. [Algorithm 1, lines 4 and 18] 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.
  4. [Section 2; Lemma 1; Theorem 1; Theorem 2] 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.
  5. [Algorithm 1, line 7; Lemma 3] 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.
  6. [Appendix C.1] 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.
  7. [Appendix D.1] 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.
  8. [Section 5; Appendix E.2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the error bounds are derived from concentration inequalities, Markov's inequality, and Kiefer-Wolfowitz theory, with no fitted quantity relabeled as a prediction and no load-bearing self-citation.

full rationale

The paper's central results, Theorem 1 and Theorem 2, are derived in-paper from Lemmas 1, 2, and 6. Lemma 1 uses the concentration inequality of Lattimore and Szepesvári (Lemma 4), the algebraic identity for the aggregated design matrix (Lemma 6), and the Kiefer-Wolfowitz bound (Lemma 3); none of these inputs contains the target error bound. Lemma 6 is an exact algebraic identity given the definition bp(ai) = b pi_p(ai), and it does not presuppose the conclusion of Theorem 1. Lemma 2 applies Markov's inequality to the count of arms that beat the best arm, and Theorem 1 sums these per-round elimination probabilities over at most log K rounds while replacing Delta_min,p by the global Delta_min. This is a standard union-bound derivation, not a restatement of an assumed conclusion. Theorem 2 likewise aggregates per-block Theorem 1 bounds through a majority-vote argument, again via Markov's inequality, with no circular step. The only self-citation, reference [6], is used as contextual background in the introduction to motivate linear bandits and is not load-bearing for any theorem. The comparison to the lower bound in [33] in Appendix D is an external benchmark, not an imported uniqueness claim, and the algorithm's G-optimal design and successive-elimination structure are stated and proven within the paper. The integer-rounding issue in Lemma 6 (since b pi_p(ai) need not be integral) is a technical correctness concern about the algorithm's implementation, but it does not make the derivation circular: the claimed bound is not obtained by fitting a parameter to the desired error probability. Therefore, no circular step is present.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central bound rests on standard bandit assumptions plus three unstated implementation idealizations: exact G-optimal design, exact fractional pulls, and a lossless rank projection. No free parameters are fit to data, and no new entities are postulated.

assumptions (4)
  • domain assumption Noise is zero-mean R-sub-Gaussian and arms are fixed vectors in R^d with a unique best arm.
    Standard linear bandit assumptions stated in Section 2; all error bounds depend on them.
  • domain assumption A 1-approximate G-optimal design with g(pi) = d is available and the Kiefer-Wolfowitz bound applies.
    Proofs use Lemma 3 requiring g(pi) = d; the paper only says it uses the Frank-Wolfe algorithm from [50], without stating the approximation guarantee used in the lemmas.
  • ad hoc to paper Fractional arm-pull counts bp(ai) = b pi(ai) can be executed so that the aggregate design matrix is exactly M b V(pi).
    Algorithm 1 line 8 assigns non-integer pulls; Lemma 6 depends on this exact identity, but no rounding or integer-allocation procedure is given.
  • ad hoc to paper Rank-deficient active sets can be projected to a lower-dimensional space without changing the best-arm gap or the noise model, and the projected OLS estimate remains valid.
    Algorithm line 6 says 'Project Ap to dp dimensions' but no formal treatment of the projection or its effect on the theorems is provided.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Multi-Agent Best Arm Identification in Stochastic Linear Bandits." pith.science (2026). https://pith.science/paper/DLYTFQ4N

@misc{pith2026241113690,
  author       = {Pith},
  title        = {Pith review of: Multi-Agent Best Arm Identification in Stochastic Linear Bandits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DLYTFQ4N}},
  note         = {Machine review of arXiv:2411.13690}
}
read the original abstract

We study the problem of collaborative best-arm identification in stochastic linear bandits under a fixed-budget scenario. In our learning model, we first consider multiple agents connected through a star network, interacting with a linear bandit instance in parallel. We then extend our analysis to arbitrary network topologies. The objective of the agents is to collaboratively identify the best arm of the given bandit instance with the help of a central server while minimizing the probability of error in best arm estimation. To this end, we propose two algorithms, MaLinBAI-Star and MaLinBAI-Gen for star networks and networks with arbitrary structure, respectively. Both algorithms utilize the technique of G-optimal design along with the successive elimination based strategy where agents share their knowledge through a central server at each communication round. We demonstrate, both theoretically and empirically, that our algorithms achieve exponentially decaying probability of error in the allocated time budget. Furthermore, experimental results on both synthetic and real-world data validate the effectiveness of our algorithms over the state-of-the art existing multi-agent algorithms.

Figures

Figures reproduced from arXiv: 2411.13690 by the authors.

Figure 1
Figure 1. Illustration of two-tier star network It is important to note that this upper bound on error probability is independent of the size of the domi￾nating set partition of the underlying graph. This highlights the fact that our algorithm MaLinBAI-Gen does not require finding a minimum dominating set partition of the given graph—a problem known to be NP-Hard. The proof of Theorem 2 primarily builds upon an application of… view at source ↗
Figure 2
Figure 2. Experimental results for synthetic data. [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Communication cost experimental results for synthetic data. [PITH_FULL_IMAGE:figures/full_fig_p017_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Experimental results for MovieLens data. [PITH_FULL_IMAGE:figures/full_fig_p018_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

55 extracted references · 51 canonical work pages

  1. [33]

    Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits

    Junwen Yang and Vincent Tan. Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits. Advances in Neural Information Processing Systems, 35:12253–12266, 2022

    work page 2022

  2. [21]

    A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits.Advances in Neural Information Processing Systems, 35:4762–4775, 2022

    Jiafan He, Tianhao Wang, Yifei Min, and Quanquan Gu. A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits.Advances in Neural Information Processing Systems, 35:4762–4775, 2022

    work page 2022

  3. [24]

    Pure Exploration in Asynchronous Federated Bandits.arXiv preprint arXiv:2310.11015, 2023

    Zichen Wang, Chuanhao Li, Chenyu Song, Lianghui Wang, Quanquan Gu, and Huazheng Wang. Pure Exploration in Asynchronous Federated Bandits.arXiv preprint arXiv:2310.11015, 2023

    arXiv 2023

  4. [1]

    Online Clustering of Bandits

    Claudio Gentile, Shuai Li, and Giovanni Zappella. Online Clustering of Bandits. InInternational Conference on Machine Learning, pages 757–765. PMLR, 2014

    work page 2014

  5. [2]

    A Contextual-Bandit Approach to Personalized News Article Recommendation

    Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A Contextual-Bandit Approach to Personalized News Article Recommendation. InProceedings of the 19th International Conference on World Wide Web, pages 661–670, 2010

    work page 2010

  6. [3]

    Collaborative Filtering Bandits

    Shuai Li, Alexandros Karatzoglou, and Claudio Gentile. Collaborative Filtering Bandits. In Proceedings of the 39th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 539–548, 2016. 9

    work page 2016

  7. [4]

    Contextual Bandits for Adapting Treatment in a Mouse Model of de Novo Carcinogenesis

    Audrey Durand, Charis Achilleos, Demetris Iacovides, Katerina Strati, Georgios D Mitsis, and Joelle Pineau. Contextual Bandits for Adapting Treatment in a Mouse Model of de Novo Carcinogenesis. In Machine Learning for Healthcare Conference, pages 67–82. PMLR, 2018

    work page 2018

  8. [5]

    Sequential Allocation in Clinical Trials.Communications in Statistics-Theory and Methods, 20(3):791–805, 1991

    You-Gan Wang. Sequential Allocation in Clinical Trials.Communications in Statistics-Theory and Methods, 20(3):791–805, 1991

    work page 1991

Show all 55 references
  1. [6]

    Blanco, and Yuan Zhou

    Chao Tao, Saúl A. Blanco, and Yuan Zhou. Best Arm Identification in Linear Bandits with Linear Dimension Dependency. InInternational Conference on Machine Learning, pages 4877–4886. PMLR, 2018

    2018

  2. [7]

    Online Linear Optimization and Adaptive Routing.Journal of Computer and System Sciences, 74(1):97–114, 2008

    Baruch Awerbuch and Robert Kleinberg. Online Linear Optimization and Adaptive Routing.Journal of Computer and System Sciences, 74(1):97–114, 2008

    2008

  3. [8]

    Regret Analysis of Stochastic and Nonstochastic Multi-Armed Bandit Problems.Foundations and Trends® in Machine Learning, 5(1):1–122, 2012

    Sébastien Bubeck, Nicolo Cesa-Bianchi, et al. Regret Analysis of Stochastic and Nonstochastic Multi-Armed Bandit Problems.Foundations and Trends® in Machine Learning, 5(1):1–122, 2012

    2012

  4. [9]

    A Gang of Bandits.Advances in Neural Information Processing Systems, 26, 2013

    Nicolo Cesa-Bianchi, Claudio Gentile, and Giovanni Zappella. A Gang of Bandits.Advances in Neural Information Processing Systems, 26, 2013

    2013

  5. [10]

    Cambridge University Press, 2020

    Tor Lattimore and Csaba Szepesvári.Bandit Algorithms. Cambridge University Press, 2020

    2020

  6. [11]

    Best Arm Identification in Multi-Armed Bandits

    Jean-Yves Audibert and Sébastien Bubeck. Best Arm Identification in Multi-Armed Bandits. In COLT-23th Conference on Learning Theory-2010, 2010

    2010

  7. [12]

    Pure Exploration in Multi-Armed Bandits Problems

    Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure Exploration in Multi-Armed Bandits Problems. In Algorithmic Learning Theory: 20th International Conference, ALT 2009, Porto, Portugal, October 3-5, 2009. Proceedings 20, pages 23–37. Springer, 2009

    2009

  8. [13]

    Almost Optimal Exploration in Multi-Armed Bandits

    Zohar Karnin, Tomer Koren, and Oren Somekh. Almost Optimal Exploration in Multi-Armed Bandits. In International Conference on Machine Learning, pages 1238–1246. PMLR, 2013

    2013

  9. [14]

    Towards Instance Optimal Bounds for Best Arm Identification

    Lijie Chen, Jian Li, and Mingda Qiao. Towards Instance Optimal Bounds for Best Arm Identification. In Conference on Learning Theory, pages 535–592. PMLR, 2017

    2017

  10. [15]

    Optimal Best Arm Identification with Fixed Confidence

    Aurélien Garivier and Emilie Kaufmann. Optimal Best Arm Identification with Fixed Confidence. In Conference on Learning Theory, pages 998–1027. PMLR, 2016

    2016

  11. [16]

    The Sample Complexity of Exploration in the Multi-Armed Bandit Problem

    Shie Mannor and John N Tsitsiklis. The Sample Complexity of Exploration in the Multi-Armed Bandit Problem. Journal of Machine Learning Research, 5(Jun):623–648, 2004

    2004

  12. [17]

    Improved Algorithms for Linear Stochastic Bandits

    Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved Algorithms for Linear Stochastic Bandits. Advances in Neural Information Processing Systems, 24, 2011

    2011

  13. [18]

    Using Confidence Bounds for Exploitation-Exploration Trade-Offs.Journal of Machine Learning Research, 3(Nov):397–422, 2002

    Peter Auer. Using Confidence Bounds for Exploitation-Exploration Trade-Offs.Journal of Machine Learning Research, 3(Nov):397–422, 2002

    2002

  14. [19]

    Multi-Agent Learning with Heterogeneous Linear Contextual Bandits

    Anh Do, Thanh Nguyen-Tang, and Raman Arora. Multi-Agent Learning with Heterogeneous Linear Contextual Bandits. Advances in Neural Information Processing Systems, 36:78768–78790, 2023

    2023

  15. [20]

    Multi-Agent Heterogeneous Stochastic Linear Bandits

    Avishek Ghosh, Abishek Sankararaman, and Kannan Ramchandran. Multi-Agent Heterogeneous Stochastic Linear Bandits. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 300–316. Springer, 2022

    2022

  16. [22]

    Collaborative Learning for Deep Neural Networks

    Guocong Song and Wei Chai. Collaborative Learning for Deep Neural Networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors,Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018

    2018

  17. [23]

    Multi-head Collaborative Learning for Graph Neural Networks.Neurocomputing, 499:47–53, 2022

    Haiyun Xu, Bo Jiang, Lili Huang, Jin Tang, and Shaojie Zhang. Multi-head Collaborative Learning for Graph Neural Networks.Neurocomputing, 499:47–53, 2022. 10

    2022

  18. [25]

    Multi-Armed Bandits in Multi-Agent Networks

    Shahin Shahrampour, Alexander Rakhlin, and Ali Jadbabaie. Multi-Armed Bandits in Multi-Agent Networks. In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2786–2790. IEEE, 2017

    2017

  19. [26]

    CRC press, 2013

    Teresa W Haynes, Stephen Hedetniemi, and Peter Slater.Fundamentals of Domination in Graphs. CRC press, 2013

    2013

  20. [27]

    Constant-Time Distributed Dominating Set Approximation

    Fabian Kuhn and Rogert Wattenhofer. Constant-Time Distributed Dominating Set Approximation. In Proceedings of the twenty-second annual symposium on Principles of distributed computing, pages 25–32, 2003

    2003

  21. [28]

    On the Domination Number of a Random Graph.The Electronic Journal of Combinatorics, R37, 2001

    Ben Wieland and Anant P Godbole. On the Domination Number of a Random Graph.The Electronic Journal of Combinatorics, R37, 2001

    2001

  22. [29]

    Robust Pure Exploration in Linear Bandits with Limited Budget

    Ayya Alieva, Ashok Cutkosky, and Abhimanyu Das. Robust Pure Exploration in Linear Bandits with Limited Budget. InInternational Conference on Machine Learning, pages 187–195. PMLR, 2021

    2021

  23. [30]

    On Correlation and Budget Constraints in Model-Based Bandit Optimization with Application to Automatic Machine Learning

    Matthew Hoffman, Bobak Shahriari, and Nando Freitas. On Correlation and Budget Constraints in Model-Based Bandit Optimization with Application to Automatic Machine Learning. InArtificial Intelligence and Statistics, pages 365–374. PMLR, 2014

    2014

  24. [31]

    An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits.Advances in Neural Information Processing Systems, 33:10371–10382, 2020

    Julian Katz-Samuels, Lalit Jain, Kevin G Jamieson, et al. An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits.Advances in Neural Information Processing Systems, 33:10371–10382, 2020

    2020

  25. [32]

    Fixed-Budget Best-Arm Identification in Structured Bandits.arXiv preprint arXiv:2106.04763, 2021

    Mohammad Javad Azizi, Branislav Kveton, and Mohammad Ghavamzadeh. Fixed-Budget Best-Arm Identification in Structured Bandits.arXiv preprint arXiv:2106.04763, 2021

    2021 arXiv

  26. [34]

    Contextual Bandits in a Collaborative Environment

    Qingyun Wu, Huazheng Wang, Quanquan Gu, and Hongning Wang. Contextual Bandits in a Collaborative Environment. InProceedings of the 39th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 529–538, 2016

    2016

  27. [35]

    Collaborative Pure Exploration in Kernel Bandit

    Yihan Du, Wei Chen, Yuko Kuroki, and Longbo Huang. Collaborative Pure Exploration in Kernel Bandit. arXiv preprint arXiv:2110.15771, 2021

    2021 arXiv

  28. [36]

    Communication-Efficient Collaborative Regret Minimization in Multi-Armed Bandits

    Nikolai Karpov and Qin Zhang. Communication-Efficient Collaborative Regret Minimization in Multi-Armed Bandits. InProceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 13076–13084, 2024

    2024

  29. [37]

    Collaborative Learning of Stochastic Bandits Over a Social Network.IEEE/ACM Transactions on Networking, 26(4):1782–1795, 2018

    Ravi Kumar Kolla, Krishna Jagannathan, and Aditya Gopalan. Collaborative Learning of Stochastic Bandits Over a Social Network.IEEE/ACM Transactions on Networking, 26(4):1782–1795, 2018

    2018

  30. [38]

    Distributed Learning in Multi-Armed Bandit with Multiple Players.IEEE Transactions on Signal Processing, 58(11):5667–5681, 2010

    Keqin Liu and Qing Zhao. Distributed Learning in Multi-Armed Bandit with Multiple Players.IEEE Transactions on Signal Processing, 58(11):5667–5681, 2010

    2010

  31. [39]

    Gossip-Based Distributed Stochastic Bandit Algorithms

    Balazs Szorenyi, Róbert Busa-Fekete, István Hegedus, Róbert Ormándi, Márk Jelasity, and Balázs Kégl. Gossip-Based Distributed Stochastic Bandit Algorithms. In International Conference on Machine Learning, pages 19–27. PMLR, 2013

    2013

  32. [40]

    Distributed Multi-Armed Bandits.IEEE Transactions on Automatic Control, 2023

    Jingxuan Zhu and Ji Liu. Distributed Multi-Armed Bandits.IEEE Transactions on Automatic Control, 2023

    2023

  33. [41]

    Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost

    Sanae Amani, Tor Lattimore, András György, and Lin Yang. Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost. InInternational Conference on Machine Learning, pages 691–717. PMLR, 2023

    2023

  34. [42]

    Multiagent Low-dimensional Linear Bandits

    Ronshee Chawla, Abishek Sankararaman, and Sanjay Shakkottai. Multiagent Low-dimensional Linear Bandits. IEEE Transactions on Automatic Control, 68(5):2667–2682, 2022. 11

    2022

  35. [43]

    Differentially-Private Federated Linear Bandits

    Abhimanyu Dubey and AlexSandy’ Pentland. Differentially-Private Federated Linear Bandits. Advances in Neural Information Processing Systems, 33:6003–6014, 2020

    2020

  36. [44]

    Federated Linear Contextual Bandits

    Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shen. Federated Linear Contextual Bandits. Advances in Neural Information Processing Systems, 34:27057–27068, 2021

    2021

  37. [45]

    Asynchronous Upper Confidence Bound Algorithms for Federated Linear Bandits

    Chuanhao Li and Hongning Wang. Asynchronous Upper Confidence Bound Algorithms for Federated Linear Bandits. InInternational Conference on Artificial Intelligence and Statistics, pages 6529–6553. PMLR, 2022

    2022

  38. [46]

    Distributed Bandit Learning: Near- Optimal Regret with Efficient Communication.arXiv preprint arXiv:1904.06309, 2019

    Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed Bandit Learning: Near- Optimal Regret with Efficient Communication.arXiv preprint arXiv:1904.06309, 2019

    1904 arXiv

  39. [47]

    Collaborative Multi- Agent Stochastic Linear Bandits

    Ahmadreza Moradipari, Mohammad Ghavamzadeh, and Mahnoosh Alizadeh. Collaborative Multi- Agent Stochastic Linear Bandits. In2022 American Control Conference (ACC), pages 2761–2766. IEEE, 2022

    2022

  40. [48]

    Collaborative Best Arm Identification in Multi-Armed Bandits

    Amit Anand Jha, Nazal Mohamed, and Krishna Jagannathan. Collaborative Best Arm Identification in Multi-Armed Bandits. In2022 14th International Conference on COMmunication Systems & NETworkS (COMSNETS), pages 335–343. IEEE, 2022

    2022

  41. [49]

    SIAM, 2006

    Friedrich Pukelsheim.Optimal Design of Experiments. SIAM, 2006

    2006

  42. [50]

    SIAM, 2016

    Michael J Todd.Minimum-Volume Ellipsoids: Theory and Algorithms. SIAM, 2016

    2016

  43. [51]

    The MovieLens Datasets: History and Context.ACM Transactions on Interactive Intelligent Systems, 5(4):1–19, 2015

    F Maxwell Harper and Joseph A Konstan. The MovieLens Datasets: History and Context.ACM Transactions on Interactive Intelligent Systems, 5(4):1–19, 2015

    2015

  44. [52]

    The Equivalence of Two Extremum Problems.Canadian Journal of Mathematics, 12:363–366, 1960

    Jack Kiefer and Jacob Wolfowitz. The Equivalence of Two Extremum Problems.Canadian Journal of Mathematics, 12:363–366, 1960. 12 A Notations and Technical Lemmas Notation: If n is a positive integer,[n] denotes the set{1, 2, . . . , n}. Furthermore, ifx ∈ Rd, then ∥x∥2 denotes ...

    1960

  45. [53]

    π∗ is a minimizer ofg,

  46. [54]

    π∗ is a maximizer off (π) = log detV (π), and

  47. [55]

    Where g(π) = max a∈A ∥a∥2 V (π)−1 , with V (π) = X a∈A π(a)aa⊤ Furthermore, there exists a minimiserπ∗ of g such that |Supp(π∗)| ≤d(d + 1)/2

    g(π∗) = d. Where g(π) = max a∈A ∥a∥2 V (π)−1 , with V (π) = X a∈A π(a)aa⊤ Furthermore, there exists a minimiserπ∗ of g such that |Supp(π∗)| ≤d(d + 1)/2. Lemma 4 (Lattimore and Szepesvári[10]). Suppose a bandit algorithm has chosen actionsA1, A2, ..., At ∈ Rd and received the r...

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.