Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Adaptively Learning to Select-Rank in Online Platforms
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 Upper Confidence Ranking (UCR), a contextual ranking bandit with GLM user responses and position-dependent item effects, solved via maximum weight bipartite matching, with O(d√(NKT)) regret.
Problem
Adaptively ranking and retrieving K of N items for heterogeneous users to maximize cumulative user satisfaction, where existing ranking bandits assume homogeneous position effects and the joint action space is combinatorially large.
Approach
Model item-wise responses with a GLM whose linear predictor includes an item-specific position effect times rank plus a context-item term; use UCB-adjusted predicted satisfaction and reduce the exponential ranking search to a maximum weight imperfect bipartite matching solved by the Hungarian algorithm.
Key results
- Theorem gives regret scaling O(d√(NKT)) (with M1, c̄, σ̄, κ constants), with corollary for N=K giving a √T dependence.
- In simulations (N=7,K=5; N=10,K=5; N=K=5) UCR yields lower average cumulative regret than G-MLE across reasonable upper confidence parameters ξ.
- On the real-world simulator-based experiment, UCR's average relative regret is lower than G-MLE across hyperparameters ξ, though small ξ (e.g., 0.5) is comparable to G-MLE at large iteration counts.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use UCR instead of G-MLE | Ranking algorithms · Simulated environments (N=7, K=5; N=10, K=5; N=K=5) | average cumulative regret | Helped |
| Use UCR instead of G-MLE | Ranking algorithms · Real-world product recommendation dataset | average relative regret | Helped |
| Set UCR's confidence parameter ξ to 0.5 | UCR · Real-world product recommendation dataset, large iterations | average relative regret | No clear effect |
| Increase UCR's confidence parameter ξ | UCR · Real-world product recommendation dataset | average relative regret | Helped |
| Choose a poor confidence parameter ξ | UCR · Simulated and real-world environments | regret | Hurt |
Surprising findings
- Poor choice of the upper confidence parameter ξ can erase UCR's advantage over the greedy G-MLE baseline.
Limitations
- Real-world evaluation relies on a learned simulator from logged data rather than live deployment.
- Regret bound depends on assumptions such as GLM response models, sub-Gaussian noise, and random initialization for context variation.
- Performance is sensitive to the upper confidence parameter ξ.
Experimental setup
Datasets: simulated environment proprietary e-commerce click dataset (13,717 samples, 436 items)
Benchmarks: simulated ranking environment real-world e-commerce click dataset (simulator-based)
Metrics: cumulative regret average relative regret
Baselines: G-MLE
Builds on: UCB GLM bandits cascade model position-based model
Closest papers by meaning
- Learning from Ranking Feedback: Improved Regret Bounds via Independence Preserving Rank Breaking (NeurIPS 2026 · similarity 0.88)
- TopRank: A practical algorithm for online stochastic ranking (NeurIPS 2018 · similarity 0.88)
- UniRank: Unimodal Bandit Algorithms for Online Ranking (ICML 2022 · similarity 0.86)
- DCM Bandits: Learning to Rank with Multiple Clicks (ICML 2016 · similarity 0.86)
- On the Convergence of No-Regret Dynamics in Information Retrieval Games with Proportional Ranking Functions (ICLR 2025 · similarity 0.85)
- Bandits with Ranking Feedback (NeurIPS 2024 · similarity 0.85)
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.