Gaussian Process Bandits for Top-k Recommendations

Mohit Yadav, Cameron Musco, Daniel R. SheldonNeurIPS 2024 · OpenReview

TL;DR

This paper introduces GP-TopK, a novel bandit algorithm for top-k recommendations that uses Gaussian Processes and a specialized Kendall kernel. It overcomes the combinatorial challenge of recommending ranked lists by requiring only a single scalar feedback for the entire list, making it more practical for real-world scenarios and achieving sub-linear regret.

What Problem Does This Paper Address?

Recommending the "top-k" items (e.g., the top 5 products a user might like) is crucial for many online platforms. Traditional bandit algorithms, which learn from limited feedback, struggle with this task because the number of possible ordered top-k lists grows exponentially with the number of items and the desired list size (k). This combinatorial explosion forces prior work to make restrictive assumptions about how users provide feedback (e.g., rating each item individually) or about the underlying reward structure, which are often unrealistic. For instance, users might only give a single "like" or "dislike" for the entire recommended list, not for each item. This paper aims to develop a bandit algorithm that can handle this combinatorial complexity with more general feedback and without restrictive assumptions.

Methods

The core of this work is the GP-TopK algorithm, which leverages Gaussian Processes (GPs) to model the reward function. GPs are well-suited for this because they can handle complex, non-linear relationships and provide uncertainty estimates, which are crucial for bandit exploration. The key innovation lies in the use of a Kendall kernel, specifically a novel Weighted Convolutional Kendall (WCK) kernel, to measure the similarity between different top-k recommendation lists. This kernel is designed to work with the combinatorial nature of rankings and is adapted to the top-k setting. To make this computationally feasible, the authors derive efficient feature representations for these kernels, enabling faster matrix-vector multiplications and reducing the overall computational complexity. They also employ a UCB (Upper Confidence Bound) acquisition function for selecting the next recommendation, balancing exploration and exploitation.

Datasets

The paper uses the MovieLens dataset (specifically, a 1M variant) for their simulations. This dataset is commonly used in recommender system research and contains user ratings for movies. The authors train user and item embeddings using collaborative filtering on this dataset, which are then used as context embeddings for the bandit algorithms.

Key Insights and Ideas

  • Full-Bandit Feedback is Key: The paper emphasizes that real-world recommendation feedback is often a single scalar value for the entire list, not item-by-item. Their algorithm is designed to work with this more general "full-bandit" setting.
  • Kendall Kernels for Rankings: Kendall kernels are a natural fit for comparing rankings, and the authors extend them to the top-k setting with a novel WCK kernel that combines the strengths of existing variants.
  • Feature Representations for Efficiency: The combinatorial nature of top-k rankings makes direct kernel computation expensive. By deriving sparse feature representations, they significantly speed up computations, making GP-based bandits practical.
  • Sub-linear Regret is Achievable: Theoretical analysis shows that GP-TopK achieves sub-linear regret, meaning its performance improves over time and doesn't get stuck in suboptimal recommendations, even with a large number of possible recommendations.

Key Results

  • Outperforms Baselines: Empirical evaluations show that GP-TopK, especially with the WCK kernel, consistently outperforms baseline bandit algorithms (like Random, ε-greedy, and MAB-UCB) in terms of cumulative regret across various settings (contextual/non-contextual, different reward functions).
  • Scalability: The proposed feature-based approach significantly reduces computational complexity, enabling the algorithm to handle large numbers of potential recommendations (millions to billions of arms) more efficiently than naive GP methods.
  • Theoretical Guarantees: The paper provides theoretical bounds on the algorithm's regret, showing it grows sub-linearly with the number of rounds, which is a strong theoretical justification for its effectiveness.

Limitations and Future Work

  • Local Search for Arm Selection: While the WCK kernel is efficient, selecting the optimal top-k ranking still involves a local search, which is a heuristic and might not always find the global optimum. The authors acknowledge this limitation in their regret analysis.
  • Computational Complexity Dependence: While the WCK kernel computation is O(k²), the overall GP inference still has a dependence on the number of rounds (T) and the number of local search evaluations (l).
  • Future Directions: The authors suggest exploring other kernel types (like Mallow kernels), extending to different bandit settings (e.g., stochastic item availability, delayed feedback), and investigating other acquisition functions. They also highlight the need to monitor for implicit biases that might be reinforced by the recommendation system.

Summary updated

Abstract

Algorithms that utilize bandit feedback to optimize top-k recommendations are vital for online marketplaces, search engines, and content platforms. However, the combinatorial nature of this problem poses a significant challenge, as the possible number of ordered top-k recommendations from $n$ items grows exponentially with $k$. As a result, previous work often relies on restrictive assumptions about the reward or bandit feedback models, such as assuming that the feedback discloses rewards for each recommended item rather than a single scalar feedback for the entire set of top-k recommendations. We introduce a novel contextual bandit algorithm for top-k recommendations, leveraging a Gaussian process with a Kendall kernel to model the reward function.Our algorithm requires only scalar feedback from the top-k recommendations and does not impose restrictive assumptions on the reward structure. Theoretical analysis confirms that the proposed algorithm achieves sub-linear regret in relation to the number of rounds and arms. Additionally, empirical results using a bandit simulator demonstrate that the proposed algorithm outperforms other baselines across various scenarios.
BibTeX
@inproceedings{yadav2024gaussian,
  author = {Mohit Yadav and Cameron Musco and Daniel R. Sheldon},
  title = {{Gaussian Process Bandits for Top-k Recommendations}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=50nEnmVLRb},
}
Figure