Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts
clustering of bandits;linear bandits;online learning
Yes
No ethics review needed.
1. Could the authors explain on the novelty of the theoretical analysis?
2. What happens when $\tilde{\gamma}$ is very small but $\gamma$ is large? Can $\tilde{\gamma}$ be estimated in some ways?
1. This paper improves the practicality of the algorithms for the clustering bandit problem by relaxing the strong assumption and analyzing the adversarial context setting.
2. Experiments are abundant to validate the performance of the proposed algorithms.
The paper proposes an algorithm for the linear bandits with clustered users, relaxing assumption on the data diversity and achieving less regret incurred by mis-clustering under both stochastic and smoothed adversarial context settings. Empirical performances of the proposed algorithms shows the efficacy and practicality on the real datasets.
1. The theoretical analysis seems to have limited novelty and heavily relies on the previous theoretical results.
2. Some parts of the presentation is hard to read, i.e., variables are defined under Table 1, the regret bounds are stated before defining the variables $\tilde{\gamma}$, $u$, and etc...
3. It would be better to prove an $\tilde{O}(T^{2/3})$ lower bound to show the impossibility results when the $\tilde{\gamma}$ is unknown.
Yes
No ethics review needed.
Please see my questions above.

Additionally, could the authors provide more details on the application of the self-normalized bound from Abbasi-Yadkori et al. (2011) to the first term in Equation 1? Specifically, I would appreciate a clearer explanation of how the filtration is defined in this context, given that the summation is taken over a set of time steps corresponding to the cluster, which is itself random (cluster estimation is based on observed noisy feedback).
Relaxation of the strong context regularity assumption adopted in online clustering bandits is a well-motivated and important problem.

The paper is technically sound and easy to follow.
This paper studies online clustering of bandits, with the goal of relaxing the strong context regularity condition adopted in prior works like Gentile, et al. (2014). 
For this purpose, the authors first added a uniform exploration phase to the existing algorithms. With the additional knowledge about the gap parameter $\gamma$, an appropriate value for the uniform exploration length $T_{0}$ can be chosen to ensure accurate cluster estimation.
On a parallel direction, the authors adopted the perturbed adversary assumption as Kannan, et al. (2018), and showed that CLUB and SCLUB algorithms by Gentile, et al. (2014) and Li, et al. (2019) now incurs less regret due to failed cluster detection (the first term in regret upper bound).
1. My primary concern with this paper is its contribution, as it may overstate the extent to which it relaxes the assumptions used in prior works. I wouldn’t consider adding the gap parameter as a relaxation. With this parameter as input, we can incorporate a dedicated uniform exploration phase of sufficient duration (determined by the gap parameter) to ensure accurate cluster estimation. Gentile et al. (2014) required the additional assumption on variance precisely because they did not have access to such information. Without knowledge of the gap, it is impossible to determine the adequate amount of uniform exploration, necessitating a stronger assumption to ensure that the minimum eigenvalue of the design matrix grows rapidly enough, even under UCB exploration.

2. The use of the perturbed adversary assumption in the context of online clustering of bandits appears to be novel, and I believe it represents a meaningful contribution of this paper. However, the discussion on the technical innovation here is limited, and I would appreciate more clarity on this aspect from the authors.
For instance, since a key part of the proof involves demonstrating that the minimum eigenvalue of the design matrix grows sufficiently under the perturbed adversary assumption (as shown in Lemma 11), how does this approach differ technically from Lemma 3.2 of Kannan et al. (2018)? Could the authors elaborate on the primary differences in the proof structure when applied to online clustering of bandit algorithms as opposed to greedy algorithms?
Yes
NA
No ethics review needed.
This work provides slightly looser regret bounds for both algorithms. The reviewer conjectures that the regret bounds can be tighter by revising the existing proof techniques. 

Logarithmic regrets are known to be attainable for standard contextual bandits under some assumptions. Do the authors think that the regret bounds can be improved to logarithmic ones under some specific assumptions? If not, could we have a square root lower bound? 

It is possible that UCB-based algorithms cannot have logarithmic ones. Is it possible for other types of algorithms?

If logarithmic regret bounds are not attainable, could the authors please explain what differences between standard contextual bandits and this work make it infeasible?

L219: Could the authors please clarify with respect to which variables the expectation is taken? 

For typical adversarial setups, as contexts are not random, they cannot have expectation and variance. Could you explain more specifically about the adversarial setup that the authors suggest?
This paper is presented well so that uninitiated readers can understand the work. Also, this work removes the nonsense assumptions in the existing literature and suggests a new set of assumptions for better analysis.
This paper explores the clustering of contextual bandits in both stochastic and adversarial context settings, introducing a new set of assumptions that improve upon some unrealistic assumptions in existing work. The two proposed algorithms are modifications of existing ones, incorporating pure exploration periods. Regret bounds for these algorithms for two setups are also provided.
The statement in L54-61 should be revised as it can be misleading. This is because the iid and minimum eigenvalue assumptions are still chosen in this work. (The assumptions for adversarial setup should be separately stated.) In addition, this work adopts the bounded context ||X||\leq L, which is stronger than the subGaussian assumption for contexts. Lastly, this work has additional assumptions about the parameters, which\|\theta_i - \theta_j\|>gamma. Even though the reviewer acknowledges that the subGaussian assumption (\sigma^2 < lambda_x/8log 4K) in the existing literature does not make sense, the reviewer believes that more substantive contributions beyond introducing new assumptions with an initial pure exploration period are necessary to be sufficiently impactful.

L198-207: the indices should be corrected.

As accurate clustering is a crucial topic in this work, the authors should state the algorithm for clustering, rather than simply referring to it.
Yes
No ethics review needed.
Why didn't you test the performance of your algorithms for the synthetic data experiment against benchmarks such as  Gob.Lin [Cesa-Bianchi et al., 2013] and GraphUCB [Yang et al., 2020]?
The writing and presentation of the paper is done with a high quality. The paper highlights an interesting theoretical change w.r.t. the state-of-the-art. It can be even interesting from a practical point of view for real-world applications in large scale.
The paper provides novel algorithms to solve the online clustering of bandits problem. Their setting relies on a slightly different set of assumptions w.r.t. the state-of-the-art. They provide theoretical analysis of their algorithms and also provide a proper experimental analysis to show the performance of their approach. Their approach shows little improvement over the performance of state-of-the-art algorithms in the experiments.
I am not sure if it is a weakness of the approach, but it seems [from the experiments] that the presented algorithms do not improve upon state-of-the-art significantly. In addition, I believe the authors could test the performance of their algorithms against more benchmarks such as Gob.Lin [Cesa-Bianchi et al., 2013] and GraphUCB [Yang et al., 2020], but it is not done.
We introduce improved algorithms for online clustering of bandits by incorporating a novel exploration phase, resulting in better regret upper bound while using substantially weaker assumptions.
@inproceedings{
anonymous2024demystifying,
title={Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=421D67DY3i},
note={under review}
}
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 work, we provide two partial solutions. First, we introduce an additional exploration phase to accelerate the identification of clusters. We integrate this general strategy into both graph-based and set-based algorithms and propose two new algorithms, UniCLUB and UniSCLUB. Remarkably, our algorithms require substantially weaker assumptions and simpler theoretical analyses while achieving superior cumulative regret compared to previous studies. 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. Extensive evaluations on both synthetic and real-world datasets demonstrate that our proposed algorithms outperform existing approaches.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
clustering of bandits linear bandits online learning
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/3ab0e3698208154b280429627c1ac8f866acc871.pdf
learning theory
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/8397980511bbd2ed8580401bdc08e4040aeb4dc5.zip
Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission