Abstract
We investigate the problem of online low-rank matrix completion involving $M$ users and $N$ items over $T$ interaction rounds. In each round, the algorithm recommends one item per user and receives a noisy reward based on a low-rank preference matrix. Traditional multi-armed bandit (MAB) approaches fail to exploit the correlations between users and items, leading to poor regret performance. We demonstrate that the underlying low-rank structure can be leveraged to achieve sub-linear regret with nearly optimal dependence on $M$ and $N$. We introduce a simple Explore-Then-Commit (ETC) strategy achieving $O(T^{2/3})$ regret and a more sophisticated algorithm, OCTAL (Online Collaborative filTering using iterAtive user cLustering), which achieves a nearly optimal regret of $O(T^{1/2})$ in the rank-1 setting. Our results show that collaborative filtering can significantly reduce the exploration required for effective recommendations.
Introduction
Modern recommendation systems face the daunting task of matching millions of users with millions of items. In an online setting, where preferences must be learned through sequential interactions, the efficiency of the learning process is paramount. Standard "multi-armed bandit" (MAB) algorithms treat every item as an independent arm. However, if a system has 100,000 items but only 100 rounds to make recommendations, a standard MAB approach learns almost nothing useful, resulting in "vacuous" regret.
The key to overcoming this bottleneck lies in the observation that user preferences are not independent; they are highly correlated. These correlations allow us to model the reward structure as a low-rank matrix. For instance, if two users share a preference for a specific genre, their reactions to other items in that genre are likely to be similar. Exploiting this low-rank structure in an online environment is challenging due to the non-convex nature of the low-rank manifold, which complicates real-time updates as new data arrives.
Algorithmic Frameworks
Explore-Then-Commit (ETC)
As a baseline for exploiting low-rank structure, we first consider the Explore-Then-Commit (ETC) approach. This strategy operates in two distinct phases:
- Exploration: The algorithm recommends items at random to all users for a fixed number of rounds. This data is used to construct an initial estimate of the reward matrix using standard offline matrix completion techniques.
- Commitment: For all remaining rounds, the algorithm recommends the item estimated to have the highest reward for each user.
While ETC is straightforward and achieves a regret of $O(T^{2/3})$—outperforming independent bandit models—it is inherently sub-optimal because it does not refine its estimates during the commitment phase.
OCTAL: Iterative User Clustering
To achieve better performance, we propose OCTAL (Online Collaborative filTering using iterAtive user cLustering). Specifically optimized for the rank-1 setting, OCTAL uses a phased approach where the length of each phase increases exponentially. In each phase, the algorithm performs three critical tasks:
- Matrix Refinement: It updates the estimate of the latent preference matrix using all accumulated data.
- User Clustering: Users are grouped into clusters based on their latent representations. In a rank-1 scenario, this often involves identifying users with similar polarities of preference.
- Item Elimination: Based on cluster-level feedback, the algorithm identifies and discards items that are statistically unlikely to be optimal for a given cluster.
This phased, "anytime" structure allows OCTAL to transition from exploration to exploitation more fluidly than ETC, leading to a nearly optimal minimax regret rate of $O(T^{1/2})$.
Empirical Evaluation
We evaluated our algorithms using synthetic data and three prominent real-world datasets: MovieLens 1M, Jester (joke ratings), and Book-Crossing. These datasets represent varying scales of users and items, providing a robust testbed for collaborative filtering.
Our experiments revealed several key insights:
- Regret Efficiency: OCTAL consistently outperformed both the ETC approach and the standard Upper Confidence Bound (UCB) algorithm. UCB, which ignores the low-rank structure, suffered from high regret as it attempted to explore the item space for each user individually.
- Scalability: A crucial theoretical and practical advantage of our methods is that regret depends only logarithmically on the number of items ($N$). This ensures that the algorithms remain performant even as the item catalog grows to massive scales.
- Cold Start Mitigation: By sharing information across users, OCTAL mitigates the "cold start" problem. It requires significantly fewer recommendations per user to begin providing high-quality suggestions compared to non-collaborative methods.
Conclusion and Future Work
This work demonstrates that online low-rank matrix completion is not only theoretically viable but also practically superior to independent bandit models. By utilizing iterative clustering and item elimination, the OCTAL algorithm achieves the theoretical lower bound for regret in the rank-1 setting.
Future research will focus on generalizing the phased clustering approach of OCTAL to general rank-$r$ settings. While the current version performs well on real-world data (which often features a dominant top singular value), a formal extension to higher ranks remains an open challenge. Additionally, exploring more complex noise models beyond simple additive or stochastic noise will further improve the robustness of these algorithms in non-stationary real-world environments.
Summary updated