Offline Clustering of Linear Bandits: The Power of Clusters under Limited Data
This work addresses the offline clustering problem in bandits for applications like advertising, offering a solution to leverage widely available offline data, though it is incremental by extending online clustering methods to the offline setting.
The paper tackles the problem of clustering users in contextual multi-armed bandits using offline data, where limited data poses a challenge for confident clustering, and proposes algorithms that outperform existing methods under data scarcity and nearly match lower bounds with sufficient data.
Contextual multi-armed bandit is a fundamental learning framework for making a sequence of decisions, e.g., advertising recommendations for a sequence of arriving users. Recent works have shown that clustering these users based on the similarity of their learned preferences can accelerate the learning. However, prior work has primarily focused on the online setting, which requires continually collecting user data, ignoring the offline data widely available in many applications. To tackle these limitations, we study the offline clustering of bandits (Off-ClusBand) problem, which studies how to use the offline dataset to learn cluster properties and improve decision-making. The key challenge in Off-ClusBand arises from data insufficiency for users: unlike the online case where we continually learn from online data, in the offline case, we have a fixed, limited dataset to work from and thus must determine whether we have enough data to confidently cluster users together. To address this challenge, we propose two algorithms: Off-C2LUB, which we show analytically and experimentally outperforms existing methods under limited offline user data, and Off-CLUB, which may incur bias when data is sparse but performs well and nearly matches the lower bound when data is sufficient. We experimentally validate these results on both real and synthetic datasets.