Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
This work addresses clustering in sequential decision-making settings with limited feedback, offering theoretical guarantees for applications like recommendation systems, but it is incremental as it builds on existing bandit and clustering methods.
The paper tackles the problem of clustering items with high-dimensional features using bandit feedback, where the learner sequentially selects items and features to observe noisy evaluations, aiming to recover the correct partition with minimal observations. They propose an algorithm based on Sequential Halving, achieving accurate recovery with high probability and providing tight upper and lower bounds on the required budget.
We study the problem of clustering a set of items based on bandit feedback. Each of the $n$ items is characterized by a feature vector, with a possibly large dimension $d$. The items are partitioned into two unknown groups such that items within the same group share the same feature vector. We consider a sequential and adaptive setting in which, at each round, the learner selects one item and one feature, then observes a noisy evaluation of the item's feature. The learner's objective is to recover the correct partition of the items, while keeping the number of observations as small as possible. We provide an algorithm which relies on finding a relevant feature for the clustering task, leveraging the Sequential Halving algorithm. With probability at least $1-δ$, we obtain an accurate recovery of the partition and derive an upper bound on the budget required. Furthermore, we derive an instance-dependent lower bound, which is tight in some relevant cases.