Online Clustering with Bandit Information
This work addresses clustering challenges in sequential decision-making for applications like recommendation systems, though it is incremental as it builds on existing bandit and clustering methods.
The paper tackles the problem of online clustering in a multi-armed bandit setting, where arms have unknown Gaussian means and must be grouped into clusters with minimal samples while bounding error probability; it introduces algorithms like ATBOC and LUCBBOC, proving ATBOC is order-optimal with an expected sample complexity within a factor of 2 of a lower bound as error probability approaches zero.
We study the problem of online clustering within the multi-armed bandit framework under the fixed confidence setting. In this multi-armed bandit problem, we have $M$ arms, each providing i.i.d. samples that follow a multivariate Gaussian distribution with an {\em unknown} mean and a known unit covariance. The arms are grouped into $K$ clusters based on the distance between their means using the Single Linkage (SLINK) clustering algorithm on the means of the arms. Since the true means are unknown, the objective is to obtain the above clustering of the arms with the minimum number of samples drawn from the arms, subject to an upper bound on the error probability. We introduce a novel algorithm, Average Tracking Bandit Online Clustering (ATBOC), and prove that this algorithm is order optimal, meaning that the upper bound on its expected sample complexity for given error probability $δ$ is within a factor of 2 of an instance-dependent lower bound as $δ\rightarrow 0$. Furthermore, we propose a computationally more efficient algorithm, Lower and Upper Confidence Bound-based Bandit Online Clustering (LUCBBOC), inspired by the LUCB algorithm for best arm identification. Simulation results demonstrate that the performance of LUCBBOC is comparable to that of ATBOC. We numerically assess the effectiveness of the proposed algorithms through numerical experiments on both synthetic datasets and the real-world MovieLens dataset. To the best of our knowledge, this is the first work on bandit online clustering that allows arms with different means in a cluster and $K$ greater than 2.