Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Learning from Imperfect Human Feedback: A Tale from Corruption-Robust Dueling
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.
Studies dueling bandits with continuous actions and strongly concave utilities under decaying corruption (imperfect human feedback), proving a matching Omega(d max{sqrt T, T^rho}) lower bound and an efficient gradient-based RoSMID algorithm achieving Otilde(d max{sqrt T, T^rho}) regret.
Problem
Learning from imperfect human comparative feedback where utility corruption decays over time as t^(rho-1); the goal is regret minimization in continuous-action dueling bandits with concave utilities.
Approach
Model human imperfection as a decaying utility corruption of scale t^(rho-1) in a continuous-action dueling bandit, prove a matching lower bound, and build RoSMID, a corruption-aware stochastic mirror descent with learning rate sqrt(log T)/(d T^max{0.5,rho}), analyzed via a new regret decomposition into decision regret and feedback error with iterative regret refinement.
Key results
- Proves a regret lower bound Omega(d max{sqrt T, T^rho}) for learning from rho-imperfect human feedback, even when rho is known.
- RoSMID achieves Otilde(d max{sqrt T, T^rho}) regret, matching the lower bound up to log factors.
- Simulations with d=5, T=10^5 show estimated regret slopes below rho for rho in [0.5,1), and RoSMID performs best among compared methods (with Sparring comparable, Doubler worst).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RoSMID instead of Doubler | Continuous dueling bandits with strongly concave utility and logistic link · ρ-imperfect human feedback simulations | regret | Helped |
| Use RoSMID instead of Sparring | Continuous dueling bandits with strongly concave utility and logistic link · ρ-imperfect human feedback simulations | regret | No clear effect |
| Use Doubler instead of RoSMID | Continuous dueling bandits with strongly concave utility and logistic link · ρ-imperfect human feedback simulations | regret | Hurt |
| Increase robustness using the tunable learning rate parameter α | RoSMID · No corruption | regret: \Omega\left(T^{\alpha}\right) | Hurt |
| Increase robustness using the tunable learning rate parameter α | DBGD · No corruption | regret: \Omega\left(T^{1-\alpha}\right) | Hurt |
Surprising findings
- Decaying corruption does not make learning easier: the lower bound matches the order of lower bounds for fully arbitrary adversarial corruption in dueling bandits.
- Doubler performs worst in experiments, attributed to its guarantees applying only to linear link functions.
Limitations
- Corruption is modeled as a decaying utility perturbation with known rho for the tight bound; the tight rate requires knowledge of rho.
- Experiments are limited to simulations with a quadratic utility and logistic link (d=5, T=10^5).
Experimental setup
Metrics: dueling regret
Baselines: DBGD Doubler Sparring
Builds on: NC-SMD Dueling Bandit Gradient Descent (DBGD) Sparring
Closest papers by meaning
- Neural Dueling Bandits: Preference-Based Optimization with Human Feedback (ICLR 2025 · similarity 0.89)
- Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification (NeurIPS 2024 · similarity 0.89)
- Fusing Reward and Dueling Feedback in Stochastic Bandits (ICML 2025 · similarity 0.88)
- Variance-aware Regret Bounds for Stochastic Contextual Dueling Bandits (ICLR 2024 · similarity 0.88)
- Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback (ICML 2025 · similarity 0.88)
- Robust Reinforcement Learning from Corrupted Human Feedback (NeurIPS 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.