Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Online Clustering of Dueling Bandits
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.
Introduces the first clustering-of-dueling-bandits algorithms (COLDB for linear and CONDB for neural rewards) that learn user clusters online from pairwise preference feedback and prove sublinear regret that improves with more users per cluster.
Problem
Contextual bandits with preference (dueling) feedback over pairs of arms do not exploit collaboration among many users, whereas clustering-of-bandits methods rely on numerical rewards.
Approach
Combine clustering of bandits with dueling bandits: maintain a dynamic user graph whose connected components estimate user clusters, pool preference data within each estimated cluster to fit a linear (COLDB) or NTK-based neural (CONDB) reward model, select a greedy first arm and a UCB-based second arm, and delete edges between users whose per-user estimates diverge.
Key results
- COLDB significantly outperforms the independent linear dueling bandit baseline LDB_IND in both synthetic and MovieLens experiments in cumulative regret.
- CONDB achieves significantly smaller cumulative regret than the independent neural dueling bandit baseline NDB_IND on synthetic square-reward and MovieLens settings.
- COLDB regret bound is O((1/kappa_mu) d sqrt(mT)) after clustering, scaling with number of clusters m rather than users u.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use COLDB instead of independent linear dueling bandits (LDB_IND) | Linear dueling bandits · Synthetic linear-reward experiment | cumulative regret | Helped |
| Use COLDB instead of independent linear dueling bandits (LDB_IND) | Linear dueling bandits · MovieLens | cumulative regret | Helped |
| Use CONDB instead of independent neural dueling bandits (NDB_IND) | Neural dueling bandits · Synthetic nonlinear square-reward experiment | cumulative regret | Helped |
| Use CONDB instead of independent neural dueling bandits (NDB_IND) | Neural dueling bandits · Real-world nonlinear square-reward experiment | cumulative regret | Helped |
| Reduce the number of clusters from m=5 to m=2 | COLDB · Synthetic linear-reward experiment | cumulative regret | Helped |
| Reduce the number of clusters from m=5 to m=2 | CONDB · Synthetic nonlinear square-reward experiment | cumulative regret | Helped |
Surprising findings
- The regret bounds carry an extra 1/kappa_mu dependency, making preference feedback provably harder than numerical feedback.
Limitations
- Experiments use only three independent trials and small settings (200 users, 20 arms, d=20).
- Theory relies on strong assumptions such as known cluster separation gap, uniform user arrival, and wide networks (NTK regime).
Experimental setup
Datasets: MovieLens
Benchmarks: MovieLens
Metrics: cumulative regret
Baselines: LDB_IND NDB_IND
Builds on: clustering of bandits linear dueling bandits neural bandits (NeuralUCB) neural tangent kernel
Closest papers by meaning
- Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts (ICLR 2025 · similarity 0.94)
- Variance-aware Regret Bounds for Stochastic Contextual Dueling Bandits (ICLR 2024 · similarity 0.89)
- Neural Dueling Bandits: Preference-Based Optimization with Human Feedback (ICLR 2025 · similarity 0.89)
- Neural Combinatorial Clustered Bandits for Recommendation Systems (AAAI 2025 · similarity 0.89)
- Direct Preference-Based Evolutionary Multi-Objective Optimization with Dueling Bandits (NeurIPS 2024 · similarity 0.87)
- Borda Regret Minimization for Generalized Linear Dueling Bandits (ICML 2024 · similarity 0.87)
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.