Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Gaussian Process Bandits for Top-k Recommendations
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GP-TopK, a contextual GP-UCB bandit for top-k recommendations under full-bandit scalar feedback, using a new weighted convolutional Kendall kernel with sparse features for fast inference.
Problem
Top-k recommendation bandits face a combinatorial arm space (Θ(n^k) ordered top-k lists) and typically rely on restrictive feedback models (semi-bandit, cascade) or decomposable rewards; the paper targets full-bandit feedback with only one scalar reward per list.
Approach
Model reward with a GP whose kernel is a product of a context dot-product kernel and a novel weighted convolutional Kendall kernel over top-k rankings; derive sparse finite feature vectors so kernel MVMs cost O(k^2 t), enabling GP-UCB with local-search acquisition optimization and sub-linear regret bounds.
Key results
- WCK kernel variant of GP-TopK achieves lower cumulative regret than WK, CK, MAB-UCB, epsilon-greedy and random in all small-arm settings (n=20, k=3) across non-contextual and contextual nDCG and nDCG+diversity rewards.
- Per-round compute reduced from O(T^3) to O(k^2 t) MVMs, giving total O(k^2 c l T^2) runtime versus O(T^4) naive.
- Regret bounds improve the n-dependence over Srinivas et al. by a factor of n^{k/2-1} (Assumption 1) and n^{k-1} (Assumption 2).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GP-TopK with a Kendall ranking kernel instead of a baseline without a Kendall kernel | Top-k recommendation bandit · MovieLens, small arm space; contextual and non-contextual nDCG and nDCG + diversity | cumulative regret | Helped |
| Replace the WK kernel with the CK kernel (ablation) | GP-TopK · MovieLens, small arm space, contextual and non-contextual reward settings | cumulative regret | Helped |
| Replace the WK kernel with the WCK kernel (ablation) | GP-TopK · MovieLens, small arm space, contextual and non-contextual reward settings | cumulative regret | Helped |
| Replace the CK kernel with the WCK kernel (ablation) | GP-TopK · MovieLens, small arm space, contextual and non-contextual reward settings | cumulative regret | Helped |
| Replace the CK kernel with the WCK kernel (ablation) | GP-TopK · MovieLens, nDCG, n=50, k=3 and k=5 | cumulative regret | Helped |
Surprising findings
- The weighted Kendall kernel ranks two non-overlapping top-k lists as more similar than two lists with the same items in reversed order, a pathology the proposed WCK kernel avoids.
Limitations
- Regret analysis ignores approximation error from local search over the acquisition function.
- Experiments are simulated on MovieLens rather than online real-world deployment.
- Restricted to product kernel between contexts and top-k rankings; other acquisition functions (Thompson sampling, EI) not analyzed.
Experimental setup
Datasets: MovieLens
Benchmarks: MovieLens bandit simulation
Metrics: cumulative regret
Baselines: Random epsilon-greedy MAB-UCB GP-TopK with WK kernel GP-TopK with CK kernel
Builds on: Srinivas et al. GP-UCB Kendall kernel (Jiao et al.) convolutional Kendall kernel weighted Kendall kernel
Closest papers by meaning
- Top-k eXtreme Contextual Bandits with Arm Hierarchy (ICML 2021 · similarity 0.90)
- Gaussian Process Bandits with Aggregated Feedback (AAAI 2022 · similarity 0.89)
- Efficient Ordered Combinatorial Semi-Bandits for Whole-Page Recommendation (AAAI 2017 · similarity 0.88)
- Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency (ICML 2024 · similarity 0.87)
- Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits (NeurIPS 2025 · similarity 0.86)
- Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.