Research map / Bandits and online learning / Multi-armed bandits
Bandits with Ranking Feedback
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 bandits with ranking feedback, where the learner only observes rankings of arms' empirical means, and gives instance-dependent and instance-independent regret bounds (DREE, R-LPE) plus impossibility results.
Problem
Multi-armed bandits where the learner observes only a ranking over arms' empirical means rather than numerical rewards; the question is whether sublinear (and logarithmic) regret is achievable.
Approach
Replaces numerical reward feedback with ranking feedback over empirical means and shows a fundamental gap: no algorithm achieves logarithmic instance-dependent regret, DREE matches a superlogarithmic instance-dependent bound, R-LPE achieves roughly sqrt(T) for Gaussian rewards, and a trade-off forbids optimality in both regimes.
Key results
- Instance-dependent lower bound: no policy achieves logarithmic regret in the ranking-feedback bandit; DREE achieves superlogarithmic instance-dependent regret matching this lower bound.
- R-LPE achieves regret O~(n^4 log(T)^2 T^{1/2}) under Gaussian rewards, breaking the O(T^{2/3}) barrier of explore-then-commit.
- Trade-off theorem: any policy with instance-dependent T^alpha and instance-independent T^beta regret must satisfy 2alpha + beta >= 1, so no algorithm is optimal in both regimes.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use DREE with superlogarithmic exploration in place of a policy aiming for logarithmic instance-dependent regret | Stochastic bandits with ranking feedback · Stochastic bandits with ranking feedback (instance-dependent) | expected cumulative regret | Mixed |
| use R-LPE instead of Explore-then-Commit | Stochastic bandits with ranking feedback · Stochastic Gaussian bandits with ranking feedback (instance-independent) | expected cumulative regret: O(T^{2/3}) -> e\tilde{O}(\sqrt{T}) | Helped |
| provide ranking feedback rather than numerical reward feedback | Bandit algorithms · Adversarial bandits | regret | Hurt |
Surprising findings
- No algorithm can achieve logarithmic instance-dependent regret under ranking feedback, unlike standard bandits.
- In the adversarial setting, no algorithm can achieve sublinear regret with ranking feedback.
Limitations
- R-LPE's sqrt(T) guarantee is proved only for Gaussian rewards.
- R-LPE requires knowledge of the horizon T and has a large polynomial dependence on the number of arms n^4.
- Instance-dependent algorithm DREE has constants C(f, Delta) that grow exponentially as delta shrinks.
Experimental setup
Metrics: cumulative regret
Baselines: explore-then-commit
Builds on: explore-then-commit dueling bandits Brownian motion discretization
Closest papers by meaning
- Fusing Reward and Dueling Feedback in Stochastic Bandits (ICML 2025 · similarity 0.91)
- Multi-Armed Bandits With Best-Action Queries (NeurIPS 2026 · similarity 0.91)
- Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.90)
- Neural Dueling Bandits: Preference-Based Optimization with Human Feedback (ICLR 2025 · similarity 0.90)
- Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits (NeurIPS 2025 · similarity 0.90)
- Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback (NeurIPS 2025 · similarity 0.89)
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.