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

Authors: Zhuohua Li, Maoli Liu, Xiangxiang Dai, John C.S. Lui
Primary area: learning theory
Keywords: clustering of bandits, linear bandits, online learning

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

Decision: accept (poster)
Reviewer scores: 6, 5, 5, 8

Reviews and discussion:
<thread>
creation date:
1729502996287

thread_type:
official_review

<thread_object>
creator: reviewer_wksx

<content>
summary:
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.

strengths:
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.

weaknesses:
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.

questions:
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]?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730668353686

thread_type:
official_review

<thread_object>
creator: reviewer_bvda

<content>
summary:
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.

strengths:
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.

weaknesses:
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.

questions:
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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731159427045

thread_type:
official_review

<thread_object>
creator: reviewer_ku8f

<content>
summary:
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).

strengths:
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.

weaknesses:
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?

questions:
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).
</content>
</thread_object>

</thread>
<thread>
creation date:
1731409762416

thread_type:
official_review

<thread_object>
creator: reviewer_sepg

<content>
summary:
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.

strengths:
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.

weaknesses:
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.

questions:
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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732446441056

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Revised Manuscript

comment:
Dear Reviewers,

We have revised our manuscript in response to your valuable comments and have uploaded the updated version for your review. All changes have been highlighted in red for your convenience. Below is a summary of the updates:

1. **Reviewer sepG:**\
(Lines 113-114) In the introduction, we emphasize the variables defined below Table 1 and refer readers to the detailed definitions in Section 3.1.

2. **Reviewer KU8f:**\
(Lines 754-755) We elaborate on the filtration definition and clarify how the self-normalized bound is applied to the first term in Equation 1.

3. **Reviewer BvdA:**\
(Line 216) We explicitly clarify which variables the expectation is taken over in the regret definition.

4. **Reviewer wksx:**\
(Lines 464-468, 1794-1847) We include additional experiments to compare our algorithms with GOB.Lin and GraphUCB, as suggested.

We hope these revisions address your comments and improve the manuscript. Please let us know if further clarification or adjustments are needed.

Thank you again for your constructive feedback.

Best regards,\
Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper aims to relax the assumption about the "stochastic/diverse" context commonly used in existing online clustering of bandits literature. The authors consider stochastic context (similar setting as Gentile, et al. (2014) with different assumptions on context diversity and cluster gap) and smoothed adversary (more relaxed setting assuming Gaussian perturbation, same as Kannan et al. (2018)), The authors proposed new algorithms for these settings and analyzed their regrets.  The reviewers recognized the following strengths:
- Relaxing the stochastic/diverse context assumption is well-motivated. The most commonly used setting of contextual/linear bandits is adversarial context. Stochastic context has been used in literature to conquer bottlenecks in theoretical analysis but is often considered too strong and hard to achieve in practice.
- Theoretical results are sound.

The reviewers mainly raised these concerns:
- Technical novelty and challenges are not clear in both settings (Reviewer sepG, KU8f)
- Contribution regarding the relaxed assumption might be misleading or overstated (Reviewer KU8f, BvdA)
- Regret bound is not tight (Reviewer sepG, BvdA)

There are other concerns regarding experiments and presentation, which are addressed during rebuttal. Overall, this is a borderline paper with mixed opinions: all reviewers agree with the importance of the problem (relaxing the assumption for online clustering of bandits) which the AC fully agrees with, but two reviewers remain negative opinions. AC evaluates each concern carefully (see below for detailed comments on each weakness) and recommends acceptance. However, careful revision is needed to clarify the novelty and contributions, avoiding concerns about misleading or overstated claims.