Pith. sign in

REVIEW 2 major objections 5 minor 1 cited by

Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts

T0 review · 2 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read The paper establishes that a short uniform-exploration phase removes the restrictive diversity assumptions in online clustering of bandits and preserves near-optimal regret.

desk verdict A real improvement on the stochastic side, but the smoothed-adversarial claim rests on a false rotation-invariance step and should not be accepted as-is. read the letter →

arxiv 2501.00891 v1 pith:JJK3GND2 submitted 2025-01-01 cs.LG cs.AIstat.ML

Zhuohua Li , Maoli Liu , Xiangxiang Dai , John C.S. Lui This is my paper · ORCID
classification cs.LGcs.AIstat.ML
keywords contextualbanditsonlineclusteringofregretminimizationclusteridentificationuniformexplorationsmoothedanalysislinearupperconfidencebound
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

The paper is trying to establish that the restrictive 'diversity' assumptions in online clustering of bandits are not intrinsic to the problem but a side effect of insufficient exploration in UCB-style algorithms. It adds a bounded pure-exploration phase that selects arms uniformly, guaranteeing each user's design matrix is well-conditioned before cluster inference begins. Under only a minimum-eigenvalue assumption on the context distribution, UniCLUB and UniSCLUB achieve regret $O\left(\frac{ud}{\gamma^2\lambda_x}\log T + d\sqrt{mT}\log T\right)$, and PhaseUniCLUB achieves the same order with larger logarithmic factors and no prior knowledge of the cluster gap $\gamma$. The paper also introduces a smoothed adversarial setting in which Gaussian perturbation of adversarially chosen contexts replaces i.i.d. context generation, claiming the same regret form with effective diversity $c_1\sigma^2/\log K$. If correct, this resolves an open question about whether the i.i.d. and sub-Gaussian assumptions in clustering bandits can be removed.

What carries the argument

The load-bearing mechanism is a pure uniform-exploration phase that forces a lower bound on the minimum eigenvalue of each user's covariance matrix. During the first $T_0$ rounds (or the exploration subphase of each phase), arms are selected uniformly from the arm set, so a matrix Chernoff bound gives $\lambda_{\min}(S_{i,t}) \ge \lambda_x T_{i,t}/2$ once $T_{i,t}$ is large enough. This shrinks the least-squares confidence radius $f(T_{i,t})$ to $\gamma/4$, which lets the edge-deletion rule separate clusters without any sub-Gaussian assumption on $(z^TX)^2$. In the smoothed adversarial setting the same role is played by the Gaussian perturbation, giving a lower bound $\tilde{\lambda}_x = c_1\sigma^2/\log K$ on the expected minimum eigenvalue of the selected arm's outer product.

What would settle it

Compute $\lambda_{\min}(\mathbb{E}[x_{a_t}x_{a_t}^T])$ for an arm selected by the UCB rule in a two-dimensional smoothed-adversary instance where each context is a fixed vector plus coordinatewise-truncated Gaussian noise, and rotate all contexts by 45 degrees; if for some rotation this eigenvalue falls below $c_1\sigma^2/\log K$, the rotation-invariance step in Appendix E, Equation (40), fails and the smoothed regret bound collapses.

Watch

Extended reading notes

Core claim

The central claim is that explicit exploration, not cleverer exploitation, is what cluster inference needs. Under an i.i.d. context model with only the minimum-eigenvalue assumption $\lambda_{\min}(\mathbb{E}[XX^T]) = \lambda_x > 0$, the graph-based algorithm UniCLUB and the set-based algorithm UniSCLUB cluster all users correctly after a $T_0$-round uniform-exploration phase, then run linear UCB on the inferred clusters, with expected regret $O\left(\frac{ud}{\gamma^2\lambda_x}\log T + d\sqrt{mT}\log T\right)$. When the cluster gap $\gamma$ is unknown, PhaseUniCLUB alternates pure-exploration and UCB subphases in a doubling schedule, achieving $O\left(\frac{ud}{\gamma^5\lambda_x^2}\log T + \left(\frac{ud}{\lambda_x}\log T\right)^{2/3}T^{1/3} + d\sqrt{mT}\log T\right)$. In the smoothed adversarial setting, SACLUB and SASCLUB keep the UCB strategy but rely on Gaussian perturbation of adversarial contexts, with an effective diversity lower bound $\tilde{\lambda}_x = c_1\sigma^2/\log K$, yielding the same bound structure.

Load-bearing premise

The smoothed-adversarial bound rests on the premise that noise which is cut off separately in each coordinate still spreads enough variance in every direction after an arbitrary rotation of the problem.

Editorial extensions

If this is right

  • UniCLUB and UniSCLUB attain regret $O\left(\frac{ud}{\gamma^2\lambda_x}\log T + d\sqrt{mT}\log T\right)$, matching the near-optimal linear-bandit regret up to the cluster-identification term.
  • PhaseUniCLUB removes the need to know the cluster gap $\gamma$, paying a larger logarithmic factor and an extra $\tilde{O}(T^{1/3})$ term while keeping the overall regret at $\tilde{O}(\sqrt{T})$.
  • In the smoothed adversarial setting, SACLUB and SASCLUB achieve the analogous regret bound, showing that i.i.d. context generation is unnecessary when contexts are randomly perturbed.
  • The uniform-exploration template applies to both graph-based and set-based clustering structures, so the relaxed assumptions cover both algorithmic families.
  • The regret bounds are independent of the number of arms $K$, and the reported experiments show no substantial regret growth as $K$ is varied.

Reading between the lines

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

  • The same explicit-exploration principle should transfer to other bandit problems with secondary statistical tasks, such as model selection or corrupted-user detection, by reserving a controlled exploration budget to feed the secondary estimator.
  • Replacing uniform arm sampling with a $D$-optimal design over the arm set could shorten the pure-exploration phase while preserving the eigenvalue lower bound, improving constants in the cluster-identification term.
  • Because the smoothed proof depends on how the noise behaves under rotation, a rotation-invariant truncation (truncating the norm rather than each coordinate) may make the smoothed bound easier to verify or even tighten it.
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 / 5 minor

Summary. The paper studies online clustering of bandits and makes two claims. First, under an i.i.d. context model, the authors propose UniCLUB, PhaseUniCLUB, and UniSCLUB, which add a uniform-exploration phase to the standard UCB-based CLUB/SCLUB framework, and claim regret bounds of order O(ud/(γ^2 λ_x) log T + d sqrt(mT) log T) under only a minimum-eigenvalue condition on the context covariance (Assumption 3), removing the conditional sub-Gaussian variance assumptions of prior work. Second, the paper introduces a smoothed adversarial context setting (Assumption 4), in which contexts are adversarially chosen means perturbed by coordinatewise-truncated Gaussian noise, and claims a similar regret bound for SACLUB/SASCLUB with λ_x replaced by eλ_x = c1 σ^2/log K. The proofs use standard UCB confidence bounds, matrix Chernoff concentration, and a phase-based doubling argument. Experiments on synthetic and three real-world datasets compare the proposed algorithms with CLUB, SCLUB, and LinUCB baselines.

Significance. If the stochastic-context analysis is correct, the paper resolves the long-standing open problem posed by Gentile et al. (2014) in the i.i.d. context case: it removes the restrictive sub-Gaussian diversity assumptions while keeping regret of the same order as prior work and improving the cluster-identification term. This is a substantial contribution, and the paper is commendably explicit about the new algorithm design and the role of pure exploration. The smoothed adversarial setting is also a valuable conceptual addition, since it moves the clustering-of-bandits problem closer to the standard adversarial-context linear bandit model. The theoretical exposition is mostly careful, with detailed proofs of the concentration arguments and an extensive experimental section. However, the smoothed-adversarial contribution currently rests on an incorrect distributional invariance claim, so that half of the paper's headline claims is not established as written. The stochastic-context results appear to be largely sound and independent of that flawed lemma, and the gaps in the stochastic proofs are local and repairable.

major comments (2)
  1. [Appendix E, Lemma 10 (Eq. (40))] The step labeled 'rotation invariance of symmetrically truncated Gaussian distributions' is incorrect. Under Assumption 4, ε is a coordinatewise-truncated multivariate Gaussian: each coordinate is independent and conditioned on |ε_j| ≤ R. For an arbitrary orthogonal matrix Q, Qε does not have the same distribution as ε because the product of coordinatewise truncations is not preserved under rotations; the coordinates of Qε are generally dependent and no longer follow a product of univariate truncated Gaussians. Therefore the replacement of Qε by ε in Eq. (40) is not a valid change of variables, and the subsequent variance decomposition Var[w^T ε] = Σ_j w_j^2 Var[ε_j] cannot be applied to the rotated variable. Consequently the lower bound λ_min(E[x_{a_t} x_{a_t}^T]) ≥ c1 σ^2/log K in Lemma 10, its use in Lemma 11, and the smoothed-adversarial regret bound in Theorem 4 are not established. The stochastic-context results (Theorems 1-3) do not depend on this lemma. Note also that any repair must simultaneously handle boundedness for the matrix Chernoff argument in Lemma 11: the suggestion in Remark 3 to use an untruncated Gaussian would restore rotational invariance but would not give an almost-sure bound on λ_max(x_{aτ} x_{aτ}^T).
  2. [Appendix B, Lemma 3 (Eq. (4))] The proof that f(T_i,t) ≤ γ/4 contains an unstated condition: 'We assume λ ≤ 2 log(u/δ) + d log(1 + T_i,t L^2/(λ d)), which typically holds.' This is an assumption on an algorithm input, not a consequence of the problem setup, and λ also appears in β and in the final regret bound. The proof should either specify a concrete choice of λ, for example λ = 1/T, verify that it satisfies the displayed inequality for all t, and track the resulting dependence in T0 and Theorem 1, or it should be replaced by a fully rigorous argument. As written, the derivation of T0 has a gap, although this gap appears readily repairable and does not affect the validity of the stochastic-context results once an explicit λ is chosen.
minor comments (5)
  1. [Appendix E, Lemma 10] The citation to 'Lemma 15 and Lemma 14 in Sivakumar et al. (2020)' is ambiguous because the paper also has its own Lemma 15 in Appendix F; please cite the external lemmas with their full reference and number.
  2. [Section 4.2] SACLUB and SASCLUB are described only as 'essentially CLUB/SCLUB with λ_x replaced by eλ_x and L replaced by 1 + sqrt(d)R.' Since these algorithms are part of the paper's claimed contributions, please provide complete pseudocode or a precise pointer to the modified lines of CLUB/SCLUB.
  3. [Theorem 4 proof] The proof says that the SASCLUB bound 'requires the counterparts of Lemmas used in the proof of Theorem 2' and then skips the details; for a self-contained appendix, the needed counterparts should be stated explicitly, especially because the smoothed setting changes the covariance lower bound used in the cluster-identification argument.
  4. [Section 6, Figure 2] In the smoothed-adversarial experiments, SACLUB and SASCLUB are compared only with LinUCB variants, not with CLUB and SCLUB; adding those baselines in the same setting would make the empirical comparison more informative.
  5. [Appendix B, Lemma 3] The phrase 'which typically holds' is informal; even if the intended condition is satisfied by a standard parameter choice, it should be stated as an explicit requirement or replaced by a choice of λ.

Circularity Check

0 steps flagged · score 1.0 of 10

No material circularity: the regret bounds are derived from stated assumptions via standard concentration arguments, with parameters (gamma, lambda_x, tilde_lambda_x) treated as inputs and tilde_lambda_x imported from an external anti-concentration result.

full rationale

I walked the derivation chain for Theorems 1-4. The stochastic-context bounds (Theorems 1-3) are obtained by composing standard least-squares confidence arguments (Abbasi-Yadkori et al., 2011) with a matrix Chernoff bound (Tropp, 2011) and a user-arrival concentration lemma (Li & Zhang, 2018); the cluster-gap parameter gamma and context-eigenvalue lambda_x are assumed inputs, not quantities fitted from the regret target. The pure-exploration phase length T0 is chosen in terms of gamma and lambda_x, and the regret bound then directly charges that exploration cost, so there is no fitted parameter later relabeled as a prediction. PhaseUniCLUB's phase schedule is likewise constructed from the same assumed constants. For the smoothed-adversarial setting (Theorem 4), the key quantity tilde_lambda_x = c1 sigma^2 / log K is imported from Lemmas 14-15 of Sivakumar et al. (2020), an external anti-concentration result on Gaussian perturbations, not from the paper's own fitted values or from a self-citation. The paper does cite prior work by overlapping authors (e.g., Li et al., 2024; Dai et al., 2024a;b), but these citations are used only for experimental preprocessing conventions and are not load-bearing for the regret derivations. The main correctness concern, flagged by the skeptical reader, is Lemma 10's appeal to 'rotation invariance of symmetrically truncated Gaussian distributions' when replacing Q epsilon by epsilon after an arbitrary rotation; coordinatewise-truncated Gaussians are not invariant under arbitrary rotations. That is a mathematical gap in the proof of the smoothed bound, not a circularity: the claimed lower bound on the minimum eigenvalue is not being assumed as an input, and the argument does not define the target regret in terms of itself. Therefore the circularity score is low, and the appropriate finding is no significant circularity, with the Lemma 10 issue recorded as a separate technical correctness risk rather than a circular step.

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

The central results rest on the four stated assumptions about user arrival, cluster separation, context diversity, and smoothed adversarial noise, plus standard concentration inequalities taken from prior work. There are no fitted free parameters in the theory; gamma, lambda_x, and sigma are problem parameters, and the algorithms take lambda, beta, and delta as inputs. The rotation invariance premise used in Lemma 10 is an additional, unflagged assumption and is not included in the problem statement.

assumptions (7)
  • domain assumption Users arrive uniformly and independently over time (Assumption 1).
    Used in Lemma 3 and Theorem 1 to guarantee every user receives enough exploration samples by time T0.
  • domain assumption Users in different clusters have preference vectors separated by a minimum gap gamma (Assumption 2).
    Needed to separate cluster estimation error from true cluster differences; without a positive gamma, clustering is not identifiable.
  • domain assumption Contexts are drawn i.i.d. from a fixed distribution with bounded norm and E[XX^T] has minimum eigenvalue lambda_x > 0 (Assumption 3).
    The stochastic-context regret bounds depend on lambda_x; this is the main remaining diversity assumption and is stated as inevitable by the authors.
  • domain assumption Smoothed adversarial contexts: adversary chooses means, then coordinatewise truncated Gaussian noise is added (Assumption 4).
    Defines the new smoothed setting used by SACLUB and SASCLUB in Theorem 4.
  • domain assumption Reward noise is zero-mean and 1-sub-Gaussian (Section 3.1).
    Required for the self-normalized martingale concentration bounds used in Lemmas 1 and 4.
  • standard math Matrix Chernoff bound (Tropp 2011) and determinant-trace inequality (Abbasi-Yadkori et al. 2011).
    Used in Lemmas 2, 5, and 11 to control the minimum eigenvalue of user design matrices.
  • ad hoc to paper Rotation invariance of the truncated Gaussian noise distribution in Lemma 10.
    The proof of the smoothed-setting lower bound assumes that coordinatewise truncated Gaussian noise is invariant under arbitrary orthogonal rotations; this is not generally true and is the weakest point in the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts." pith.science (2026). https://pith.science/paper/JJK3GND2

@misc{pith2026250100891,
  author       = {Pith},
  title        = {Pith review of: Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JJK3GND2}},
  note         = {Machine review of arXiv:2501.00891}
}
read the original abstract

The contextual multi-armed bandit (MAB) problem is crucial in sequential decision-making. A line of research, known as online clustering of bandits, extends contextual MAB by grouping similar users into clusters, utilizing shared features to improve learning efficiency. However, existing algorithms, which rely on the upper confidence bound (UCB) strategy, struggle to gather adequate statistical information to accurately identify unknown user clusters. As a result, their theoretical analyses require several strong assumptions about the "diversity" of contexts generated by the environment, leading to impractical settings, complicated analyses, and poor practical performance. Removing these assumptions has been a long-standing open problem in the clustering of bandits literature. In this paper, we provide two solutions to this open problem. First, following the i.i.d. context generation setting in existing studies, we propose two novel algorithms, UniCLUB and PhaseUniCLUB, which incorporate enhanced exploration mechanisms to accelerate cluster identification. Remarkably, our algorithms require substantially weaker assumptions while achieving regret bounds comparable to prior work. Second, inspired by the smoothed analysis framework, we propose a more practical setting that eliminates the requirement for i.i.d. context generation used in previous studies, thus enhancing the performance of existing algorithms for online clustering of bandits. Our technique can be applied to both graph-based and set-based clustering of bandits frameworks. Extensive evaluations on both synthetic and real-world datasets demonstrate that our proposed algorithms consistently outperform existing approaches.

Figures

Figures reproduced from arXiv: 2501.00891 by the authors.

Figure 1
Figure 1. Comparison of cumulative regrets in the stochastic context setting. [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Comparison of cumulative regrets under the smoothed adversarial context setting. [PITH_FULL_IMAGE:figures/full_fig_p033_2.png] view at source ↗
Figure 3
Figure 3. Comparison of cumulative regrets with different arm set sizes. [PITH_FULL_IMAGE:figures/full_fig_p034_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Comparison of cumulative regrets with different numbers of users. [PITH_FULL_IMAGE:figures/full_fig_p034_4.png]
Figure 5
Figure 5. Figure 5: Comparison of cumulative regrets with more baselines. [PITH_FULL_IMAGE:figures/full_fig_p035_5.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Heterogeneous Multi-agent Multi-armed Bandits on Stochastic Block Models

    cs.LG 2025-02 conditional novelty 6.0 of 10

    A cluster-aware multi-agent bandit algorithm achieves O((C/M) log T) regret by aggregating information within clusters and communicating only between clusters, improving on the O(M^2 log T) bound of fully heterogeneou...

Reference graph

Works this paper leans on

40 extracted references · 35 canonical work pages · cited by 1 Pith paper

  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]

    Improved algorithms for linear stochastic bandits

    Yasin Abbasi-Yadkori, D\' a vid P\' a l, and Csaba Szepesv\' a ri. Improved algorithms for linear stochastic bandits. In Proceedings of the 24th International Conference on Neural Information Processing Systems, NIPS'11, pp.\ 2312–2320, 2011

    work page 2011

  3. [3]

    Linear stochastic bandits under safety constraints

    Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Linear stochastic bandits under safety constraints. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019

    work page 2019

  4. [4]

    Local clustering in contextual multi-armed bandits

    Yikun Ban and Jingrui He. Local clustering in contextual multi-armed bandits. In Proceedings of the Web Conference 2021, WWW '21, pp.\ 2335–2346, 2021. ISBN 9781450383127

    work page 2021

  5. [5]

    Mostly exploration-free algorithms for contextual bandits

    Hamsa Bastani, Mohsen Bayati, and Khashayar Khosravi. Mostly exploration-free algorithms for contextual bandits. Management Science, 67 0 (3): 0 1329–1349, March 2021. ISSN 1526-5501

    work page 2021

  6. [6]

    Second workshop on information heterogeneity and fusion in recommender systems (hetrec2011)

    Ivan Cantador, Peter Brusilovsky, and Tsvi Kuflik. Second workshop on information heterogeneity and fusion in recommender systems (hetrec2011). In Proceedings of the Fifth ACM Conference on Recommender Systems, RecSys '11, pp.\ 387–388, 2011

    work page 2011

  7. [7]

    A gang of bandits

    Nicol\` o Cesa-Bianchi, Claudio Gentile, and Giovanni Zappella. A gang of bandits. In Advances in Neural Information Processing Systems, volume 26, 2013

    work page 2013

  8. [8]

    Osom: A simultaneously optimal algorithm for multi-armed and linear contextual bandits

    Niladri Chatterji, Vidya Muthukumar, and Peter Bartlett. Osom: A simultaneously optimal algorithm for multi-armed and linear contextual bandits. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp.\ 1844--1854. PMLR, 26--28 Aug 2020

    work page 2020

Show all 40 references
  1. [9]

    Contextual bandits with linear payoff functions

    Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp.\ 208--214, 2011

    2011

  2. [10]

    Xiangxiang Dai, Zhiyong Wang, Jize Xie, Xutong Liu, and John C.S. Lui. Conversational recommendation with online learning and clustering on misspecified users. IEEE Transactions on Knowledge and Data Engineering, pp.\ 1--14, 2024 a

    2024

  3. [11]

    Online learning and detecting corrupted users for conversational recommendation systems

    Xiangxiang Dai, Zhiyong Wang, Jize Xie, Tong Yu, and John CS Lui. Online learning and detecting corrupted users for conversational recommendation systems. IEEE Transactions on Knowledge and Data Engineering, 2024 b

    2024

  4. [12]

    Online clustering of bandits

    Claudio Gentile, Shuai Li, and Giovanni Zappella. Online clustering of bandits. In Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pp.\ 757--765. PMLR, 22--24 Jun 2014

    2014

  5. [13]

    On context-dependent clustering of bandits

    Claudio Gentile, Shuai Li, Purushottam Kar, Alexandros Karatzoglou, Giovanni Zappella, and Evans Etrue. On context-dependent clustering of bandits. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, p...

    2017

  6. [14]

    Breaking the T barrier: Instance-independent logarithmic regret in stochastic contextual linear bandits

    Avishek Ghosh and Abishek Sankararaman. Breaking the T barrier: Instance-independent logarithmic regret in stochastic contextual linear bandits. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp....

    2022

  7. [15]

    Problem-complexity adaptive model selection for stochastic linear bandits

    Avishek Ghosh, Abishek Sankararaman, and Ramchandran Kannan. Problem-complexity adaptive model selection for stochastic linear bandits. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning ...

    2021

  8. [16]

    Collaborative learning and personalization in multi-agent stochastic linear bandits

    Avishek Ghosh, Abishek Sankararaman, and Kannan Ramchandran. Collaborative learning and personalization in multi-agent stochastic linear bandits. stat, 1050: 0 15, 2021 b

    2021

  9. [17]

    Adaptive exploration in linear contextual bandit

    Botao Hao, Tor Lattimore, and Csaba Szepesvari. Adaptive exploration in linear contextual bandit. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp.\ 3536--3545. PML...

    2020

  10. [18]

    Maxwell Harper and Joseph A

    F. Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst., 5 0 (4), dec 2015

    2015

  11. [19]

    A smoothed analysis of the greedy algorithm for the linear contextual bandit problem

    Sampath Kannan, Jamie Morgenstern, Aaron Roth, Bo Waggoner, and Zhiwei Steven Wu. A smoothed analysis of the greedy algorithm for the linear contextual bandit problem. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS'18, pp.\ 2...

    2018

  12. [20]

    Schapire

    Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th International Conference on World Wide Web, WWW '10, pp.\ 661–670, 2010

    2010

  13. [21]

    Online clustering of contextual cascading bandits

    Shuai Li and Shengyu Zhang. Online clustering of contextual cascading bandits. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Ad...

    2018

  14. [22]

    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, SIGIR '16, pp.\ 539–548, 2016. ISBN 9781450340694

    2016

  15. [23]

    Improved algorithm on online clustering of bandits

    Shuai Li, Wei Chen, Shuai Li, and Kwong-Sak Leung. Improved algorithm on online clustering of bandits. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19 , pp.\ 2923--2929. International Joint Conferences on Artificial Intel...

    2019

  16. [24]

    Zhuohua Li, Maoli Liu, and John C.S. Lui. Fedconpe: Efficient federated conversational bandits with heterogeneous clients. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI-24 . International Joint Conferences on Artificial Int...

    2024

  17. [25]

    Federated online clustering of bandits

    Xutong Liu, Haoru Zhao, Tong Yu, Shuai Li, and John Lui. Federated online clustering of bandits. In The 38th Conference on Uncertainty in Artificial Intelligence, 2022

    2022

  18. [26]

    Greedy algorithm almost dominates in smoothed contextual bandits

    Manish Raghavan, Aleksandrs Slivkins, Jennifer Wortman Vaughan, and Zhiwei Steven Wu. Greedy algorithm almost dominates in smoothed contextual bandits. SIAM Journal on Computing, 52 0 (2): 0 487--524, 2023

    2023

  19. [27]

    Structured linear contextual bandits: A sharp and geometric smoothed analysis

    Vidyashankar Sivakumar, Steven Wu, and Arindam Banerjee. Structured linear contextual bandits: A sharp and geometric smoothed analysis. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp.\ 9026--9...

    2020

  20. [28]

    Smoothed adversarial linear contextual bandits with knapsacks

    Vidyashankar Sivakumar, Shiliang Zuo, and Arindam Banerjee. Smoothed adversarial linear contextual bandits with knapsacks. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on...

    2022

  21. [29]

    Spielman and Shang-Hua Teng

    Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM, 51 0 (3): 0 385–463, may 2004. ISSN 0004-5411

    2004

  22. [30]

    Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12 0 (4): 0 389–434, August 2011. ISSN 1615-3383

    2011

  23. [31]

    Zhiyong Wang, Jize Xie, Xutong Liu, Shuai Li, and John C.S. Lui. Online clustering of bandits with misspecified user models. In Thirty-seventh Conference on Neural Information Processing Systems, 2023 a

    2023

  24. [32]

    Zhiyong Wang, Jize Xie, Tong Yu, Shuai Li, and John C.S. Lui. Online corrupted user detection and regret minimization. In Thirty-seventh Conference on Neural Information Processing Systems, 2023 b

    2023

  25. [33]

    Stochastic linear contextual bandits with diverse contexts

    Weiqiang Wu, Jing Yang, and Cong Shen. Stochastic linear contextual bandits with diverse contexts. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp.\ 2392--2401. PM...

    2020

  26. [34]

    Hantao Yang, Xutong Liu, Zhiyong Wang, Hong Xie, John C. S. Lui, Defu Lian, and Enhong Chen. Federated contextual cascading bandits with asynchronous communication and heterogeneous users. Proceedings of the AAAI Conference on Artificial Intelligence, 38 0 (18): 0 20596--20603...

    2024

  27. [35]

    Laplacian-regularized graph bandits: Algorithms and theoretical analysis

    Kaige Yang, Laura Toni, and Xiaowen Dong. Laplacian-regularized graph bandits: Algorithms and theoretical analysis. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp...

    2020

  28. [36]

    Y elp D ataset --- yelp.com

    Yelp. Y elp D ataset --- yelp.com. https://www.yelp.com/dataset, 2023. [Accessed 21-05-2024]

    2023

  29. [37]

    Xiaoying Zhang, Hong Xie, Hang Li, and John C.S. Lui. Conversational contextual bandit: Algorithm and application. In Proceedings of The Web Conference 2020, WWW '20, pp.\ 662–672, 2020

    2020

  30. [38]

    @esa (Ref

    \@ifxundefined[1] #1\@undefined \@firstoftwo \@secondoftwo \@ifnum[1] #1 \@firstoftwo \@secondoftwo \@ifx[1] #1 \@firstoftwo \@secondoftwo [2] @ #1 \@temptokena #2 #1 @ \@temptokena \@ifclassloaded agu2001 natbib The agu2001 class already includes natbib coding, so you should ...

  31. [39]

    \@lbibitem[] @bibitem@first@sw\@secondoftwo \@lbibitem[#1]#2 \@extra@b@citeb \@ifundefined br@#2\@extra@b@citeb \@namedef br@#2 \@nameuse br@#2\@extra@b@citeb \@ifundefined b@#2\@extra@b@citeb @num @parse #2 @tmp #1 NAT@b@open@#2 NAT@b@shut@#2 \@ifnum @merge>\@ne @bibitem@firs...

  32. [40]

    Since all algorithms achieve similar regret bounds, we focus on comparing the regret incurred by clustering

    @open @close @open @close and [1] URL: #1 \@ifundefined chapter * \@mkboth \@ifxundefined @sectionbib * \@mkboth * \@mkboth\@gobbletwo \@ifclassloaded amsart * \@ifclassloaded amsbook * \@ifxundefined @heading @heading NAT@ctr thebibliography [1] @ \@biblabel @NAT@ctr \@bibset...

    2014

Pith tools

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