Pith. sign in

REVIEW 2 major objections 6 minor 45 references

Near Optimal Best Arm Identification for Clustered Bandits

T0 review · 2 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read Two-phase successive elimination identifies every agent's best arm at near-optimal sample cost.

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

arxiv 2505.10147 v1 pith:M3GIEDJX submitted 2025-05-15 cs.LG cs.MA

Yash , Nikhil Karamchandani , Avishek Ghosh This is my paper · ORCID
classification cs.LGcs.MA
keywords bestarmidentificationclusteredbanditsfederatedsuccessiveeliminationfixed-confidencesamplecomplexityminimaxlowerboundmulti-armed
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 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.

What carries the argument

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.

What would settle it

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

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

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

Reading between the lines

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

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

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 6 minor

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.

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 (2)
  1. [Algorithm 3, line 7; Proposition 9.11; Algorithm 4, Proposition 9.19] 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.
  2. [Proposition 9.11 / Algorithm 3 line 7] 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.
minor comments (6)
  1. [Section 1.1, Theorem 4.4] 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.
  2. [Section 8 and Appendix 9.11] Several figure references appear as '??' in the text; the figures need to be correctly inserted and cited.
  3. [Algorithm 1, line 7] 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.
  4. [Appendix 9.9] 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 η = Δ.
  5. [Algorithm 4] 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.
  6. [Appendix 9.10] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: upper bounds, lower bound, and optimality comparison are derived from external SE and change-of-measure results, not from the conclusions.

full rationale

The derivation chain is self-contained. The correctness of both algorithms is proven from the successive-elimination finite-sample guarantee (Theorem 9.5), which is stated and proved in Appendix 9.2 using Hoeffding's inequality, rather than imported from the authors' prior work. Clustering and best-arm identification arguments use Assumptions 2.1 and 6.1 as stated inputs, and no parameter is fitted to data inside the theoretical analysis. Sample-complexity upper bounds are direct pull-count bounds from the SE subroutine. The lower bound in Theorem 7.1 is derived via Kaufmann et al.'s change-of-measure lemma, an external result, and the minimax comparison in Remark 7.2 juxtaposes the paper's own upper bound with that independent lower bound, which is a legitimate benchmarking step rather than circular reasoning. Self-citations such as Ghosh et al. (2021) and Gharat et al. (2024) appear only in related-work surveys and do not carry any load-bearing premise in the proofs. The boundary-gap issue noted by a reader in Proposition 9.11 (Algorithm 3 sets R = log(1/η)+1, giving ε_R = η/2, so the SE guarantee may not exclude a cross-cluster best arm whose gap is exactly η) is a potential correctness or termination gap in the δ-PC proof, not a circularity: it concerns whether the SE guarantee covers a boundary event, not whether a conclusion is assumed as an input.

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

The theory has no fitted numeric parameters: η and η1 are assumed inputs that define the problem class. In synthetic experiments they are set by construction; in real-data experiments they are computed from empirical means. The paper introduces no new physical or mathematical entities beyond the algorithmic framework. The main load-bearing input is the separability assumption, which is explicit but strong.

assumptions (4)
  • domain assumption Assumption 2.1: for any two different bandits a,b, μ_{b,k*_b} - μ_{b,k*_a} ≥ η.
    This separability condition is the main structural assumption. It ensures distinct best arms across clusters and enables clustering by comparing empirical means. It appears in Section 2 and is used throughout.
  • domain assumption Assumption 6.1: for any two bandits i,j, |μ_{i,k*_i} - μ_{j,k*_i}| ≥ η1.
    This extra assumption is needed only for BAI-Cl++; it lets the dSE procedure accept or reject a candidate best arm by comparing new pulls with stored mean estimates. Introduced in Section 6.
  • domain assumption Each agent is assigned to one of the M clusters uniformly at random.
    Used in Theorem 5.3 and Theorem 9.2 for the coupon-collector bound on the number of agents sampled in the first phase of BAI-Cl/BAI-Cl++. Remark 5.6 says it can be generalized to unequal probabilities, but the stated high-probability bounds depend on this uniform assumption.
  • standard math Standard concentration and change-of-measure results: Hoeffding's inequality for 1-subGaussian rewards and Kaufmann et al.'s change-of-measure lemma.
    Used in the correctness proofs of successive elimination (Appendix 9.2) and in the lower bound derivation (Appendix 9.9). These are accepted background results.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Near Optimal Best Arm Identification for Clustered Bandits." pith.science (2026). https://pith.science/paper/M3GIEDJX

@misc{pith2026250510147,
  author       = {Pith},
  title        = {Pith review of: Near Optimal Best Arm Identification for Clustered Bandits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/M3GIEDJX}},
  note         = {Machine review of arXiv:2505.10147}
}
abstract

This work investigates the problem of best arm identification for multi-agent multi-armed bandits. We consider $N$ agents grouped into $M$ clusters, where each cluster solves a stochastic bandit problem. The mapping between agents and bandits is a priori unknown. Each bandit is associated with $K$ arms, and the goal is to identify the best arm for each agent under a $\delta$-probably correct ($\delta$-PC) framework, while minimizing sample complexity and communication overhead. We propose two novel algorithms: Clustering then Best Arm Identification (Cl-BAI) and Best Arm Identification then Clustering (BAI-Cl). Cl-BAI uses a two-phase approach that first clusters agents based on the bandit problems they are learning, followed by identifying the best arm for each cluster. BAI-Cl reverses the sequence by identifying the best arms first and then clustering agents accordingly. Both algorithms leverage the successive elimination framework to ensure computational efficiency and high accuracy. We establish $\delta$-PC guarantees for both methods, derive bounds on their sample complexity, and provide a lower bound for this problem class. Moreover, when $M$ is small (a constant), we show that the sample complexity of a variant of BAI-Cl is minimax optimal in an order-wise sense. Experiments on synthetic and real-world datasets (MovieLens, Yelp) demonstrate the superior performance of the proposed algorithms in terms of sample and communication efficiency, particularly in settings where $M \ll N$.

Figures

Figures reproduced from arXiv: 2505.10147 by the authors.

Figure 1
Figure 1. Performance with varying number of agents [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. (a) Performance with varying number of agents [PITH_FULL_IMAGE:figures/full_fig_p025_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

45 extracted references · 34 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    and Bubeck, S

    Audibert, J.-Y. and Bubeck, S. Best arm identification in multi-armed bandits. In COLT-23th Conference on learning theory-2010, pp.\ 13--p, 2010

    2010

  3. [3]

    and He, J

    Ban, Y. and He, J. Local clustering in contextual multi-armed bandits. In Proceedings of the Web Conference 2021, pp.\ 2335--2346, 2021

    work page 2021

  4. [4]

    Chaudhuri, A. R. and Kalyanakrishnan, S. Pac identification of a bandit arm relative to a reward quantile. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017

    work page 2017

  5. [5]

    Chaudhuri, A. R. and Kalyanakrishnan, S. Pac identification of many good arms in stochastic multi-armed bandits. In International Conference on Machine Learning, pp.\ 991--1000. PMLR, 2019

    work page 2019

  6. [6]

    Collaborative multi-agent heterogeneous multi-armed bandits

    Chawla, R., Vial, D., Shakkottai, S., and Srikant, R. Collaborative multi-agent heterogeneous multi-armed bandits. In International Conference on Machine Learning, pp.\ 4189--4217. PMLR, 2023

    work page 2023

  7. [7]

    Y., and Chee, Y

    Chen, Z., Karthik, P., Tan, V. Y., and Chee, Y. M. Federated best arm identification with heterogeneous clients. IEEE Transactions on Information Theory, 2023

    work page 2023

  8. [8]

    Adaptive Sample Sharing for Multi Agent Linear Bandits

    Cherkaoui, H., Barlier, M., and Colin, I. Clustered multi-agent linear bandits. arXiv preprint arXiv:2309.08710, 2023

    work page Pith review arXiv 2023

Show all 45 references
  1. [9]

    and Koolen, W

    Degenne, R. and Koolen, W. M. Pure exploration with multiple correct answers. Advances in Neural Information Processing Systems, 32, 2019

    2019

  2. [10]

    93.16 the coupon collector's problem with unequal probabilities

    Dudzic, S. 93.16 the coupon collector's problem with unequal probabilities. The Mathematical Gazette, 93 0 (526): 0 126--130, 2009. ISSN 00255572. URL http://www.jstor.org/stable/40378689

    2009

  3. [11]

    Pac bounds for multi-armed bandit and markov decision processes

    Even-Dar, E., Mannor, S., and Mansour, Y. Pac bounds for multi-armed bandit and markov decision processes. In Computational Learning Theory: 15th Annual Conference on Computational Learning Theory, COLT 2002 Sydney, Australia, July 8--10, 2002 Proceedings 15, pp.\ 255--270. Sp...

    2002

  4. [12]

    and Kaufmann, E

    Garivier, A. and Kaufmann, E. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pp.\ 998--1027. PMLR, 2016

    2016

  5. [13]

    Online clustering of bandits

    Gentile, C., Li, S., and Zappella, G. Online clustering of bandits. In International conference on machine learning, pp.\ 757--765. PMLR, 2014

    2014

  6. [14]

    Representative arm identification: A fixed confidence approach to identify cluster representatives

    Gharat, S., Yadav, A., Karamchandani, N., and Nair, J. Representative arm identification: A fixed confidence approach to identify cluster representatives. arXiv preprint arXiv:2408.14195, 2024

    2024 arXiv

  7. [15]

    Collaborative learning and personalization in multi-agent stochastic linear bandits

    Ghosh, A., Sankararaman, A., and Ramchandran, K. Collaborative learning and personalization in multi-agent stochastic linear bandits. stat, 1050: 0 15, 2021

    2021

  8. [16]

    S., Koren, T., Lempel, R., and Somekh, O

    Hillel, E., Karnin, Z. S., Koren, T., Lempel, R., and Somekh, O. Distributed exploration in multi-armed bandits. Advances in Neural Information Processing Systems, 26, 2013

    2013

  9. [17]

    and Nowak, R

    Jamieson, K. and Nowak, R. Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In 2014 48th Annual Conference on Information Sciences and Systems (CISS), pp.\ 1--6. IEEE, 2014

    2014

  10. [18]

    Pac subset selection in stochastic multi-armed bandits

    Kalyanakrishnan, S., Tewari, A., Auer, P., and Stone, P. Pac subset selection in stochastic multi-armed bandits. In ICML, volume 12, pp.\ 655--662, 2012

    2012

  11. [19]

    Almost optimal exploration in multi-armed bandits

    Karnin, Z., Koren, T., and Somekh, O. Almost optimal exploration in multi-armed bandits. In International conference on machine learning, pp.\ 1238--1246. PMLR, 2013

    2013

  12. [20]

    and Zhang, Q

    Karpov, N. and Zhang, Q. Batched coarse ranking in multi-armed bandits. In Conference on Neural Information Processing Systems (NeurIPS), 2020

    2020

  13. [21]

    and Zhang, Q

    Karpov, N. and Zhang, Q. Communication-efficient collaborative best arm identification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp.\ 8203--8210, 2023

    2023

  14. [22]

    and Zhang, Q

    Karpov, N. and Zhang, Q. Parallel best arm identification in heterogeneous environments. In Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures, pp.\ 53--64, 2024

    2024

  15. [23]

    Collaborative top distribution identifications with limited interaction

    Karpov, N., Zhang, Q., and Zhou, Y. Collaborative top distribution identifications with limited interaction. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pp.\ 160--171. IEEE, 2020

    2020

  16. [24]

    On the complexity of a/b testing

    Kaufmann, E., Capp \'e , O., and Garivier, A. On the complexity of a/b testing. In Conference on Learning Theory, pp.\ 461--481. PMLR, 2014

    2014

  17. [25]

    On the complexity of best-arm identification in multi-armed bandit models

    Kaufmann, E., Capp \'e , O., and Garivier, A. On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17 0 (1): 0 1--42, 2016

    2016

  18. [26]

    Distributed clustering of linear bandits in peer to peer networks

    Korda, N., Szorenyi, B., and Li, S. Distributed clustering of linear bandits in peer to peer networks. In International conference on machine learning, pp.\ 1301--1309. PMLR, 2016

    2016

  19. [27]

    R., Karthik, P., and Tan, V

    Kota, S. R., Karthik, P., and Tan, V. Y. Almost cost-free communication in federated best arm identification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp.\ 8378--8385, 2023

    2023

  20. [28]

    Lai, T. L. and Robbins, H. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6 0 (1): 0 4--22, 1985

    1985

  21. [29]

    and Szepesv \'a ri, C

    Lattimore, T. and Szepesv \'a ri, C. Bandit algorithms. Cambridge University Press, 2020

    2020

  22. [30]

    and Song, L

    Li, T. and Song, L. Privacy-preserving communication-efficient federated multi-armed bandits. IEEE Journal on Selected Areas in Communications, 40 0 (3): 0 773--787, 2022

    2022

  23. [31]

    An optimal algorithm for the thresholding bandit problem

    Locatelli, A., Gutzeit, M., and Carpentier, A. An optimal algorithm for the thresholding bandit problem. In International Conference on Machine Learning, pp.\ 1690--1698. PMLR, 2016

    2016

  24. [32]

    Exploiting heterogeneity in robust federated best-arm identification

    Mitra, A., Hassani, H., and Pappas, G. Exploiting heterogeneity in robust federated best-arm identification. arXiv preprint arXiv:2109.05700, 2021

    2021 arXiv

  25. [33]

    S., Shanmugam, K., and Jain, P

    Pal, S., Suggala, A. S., Shanmugam, K., and Jain, P. Optimal algorithms for latent bandits with cluster structure. In International Conference on Artificial Intelligence and Statistics, pp.\ 7540--7577. PMLR, 2023

    2023

  26. [34]

    Near-optimal collaborative learning in bandits

    R \'e da, C., Vakili, S., and Kaufmann, E. Near-optimal collaborative learning in bandits. Advances in Neural Information Processing Systems, 35: 0 14183--14195, 2022

    2022

  27. [35]

    Federated multi-armed bandits under byzantine attacks

    Saday, A., Demirel, \.I ., Y ld r m, Y., and Tekin, C. Federated multi-armed bandits under byzantine attacks. arXiv preprint arXiv:2205.04134, 2022

    2022 arXiv

  28. [36]

    and Shen, C

    Shi, C. and Shen, C. Federated multi-armed bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp.\ 9603--9611, 2021

    2021

  29. [37]

    Federated multi-armed bandits with personalization

    Shi, C., Shen, C., and Yang, J. Federated multi-armed bandits with personalization. In International Conference on Artificial Intelligence and Statistics, pp.\ 2917--2925. PMLR, 2021

    2021

  30. [38]

    Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-armed bandits

    Tao, C., Zhang, Q., and Zhou, Y. Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-armed bandits. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pp.\ 126--146. IEEE, 2019

    2019

  31. [39]

    Active clustering with bandit feedback

    Thuot, V., Carpentier, A., Giraud, C., and Verzelen, N. Active clustering with bandit feedback. arXiv preprint arXiv:2406.11485, 2024

    2024 arXiv

  32. [40]

    Pure exploration in asynchronous federated bandits

    Wang, Z., Li, C., Song, C., Wang, L., Gu, Q., and Wang, H. Pure exploration in asynchronous federated bandits. arXiv preprint arXiv:2310.11015, 2023

    2023 arXiv

  33. [41]

    Yang, J., Zhong, Z., and Tan, V. Y. Optimal clustering with bandit feedback. Journal of Machine Learning Research, 25 0 (186): 0 1--54, 2024

    2024

  34. [42]

    C., Huang, Y., Tan, V

    Yavas, R. C., Huang, Y., Tan, V. Y., and Scarlett, J. A general framework for clustering and distribution matching with bandit feedback. IEEE Transactions on Information Theory, 2025

    2025

  35. [43]

    Ie 498: Online learning and decision making, fall 2019 sep

    Zhou, Y. Ie 498: Online learning and decision making, fall 2019 sep. 5th lecture 04: Pure exploration algorithms for mab problem, September 2019. Lecturer: Yuan Zhou Scribe: Juan Xu, Rahul Swamy

    2019

  36. [44]

    and Liu, J

    Zhu, J. and Liu, J. Distributed multiarmed bandits. IEEE Transactions on Automatic Control, 68 0 (5): 0 3025--3040, 2023

    2023

  37. [45]

    Federated bandit: A gossiping approach

    Zhu, Z., Zhu, J., Liu, J., and Liu, Y. Federated bandit: A gossiping approach. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5 0 (1): 0 1--29, 2021

    2021

Pith tools

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