Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial 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.
Proposes RCDB, an uncertainty-weighted MLE algorithm for linear contextual dueling bandits under strong adversarial label flipping, achieving near-optimal regret, plus a sigmoid-specific variant RCDB-S that removes kappa from the leading term.
Problem
Preference-based learning (e.g., RLHF) is vulnerable to adversaries who flip preference labels; the goal is regret-optimal contextual dueling bandits when up to C feedback labels can be flipped by a strong adversary who sees the chosen actions.
Approach
Weights each preference observation by min{1, alpha/||phi_i||_{Sigma_i^{-1}}} inside the MLE so uncertain (likely corrupted) feedback has less influence; for sigmoid links, uses an optimistic local-derivative estimate v_i = max{kappa, sigma_dot(Delta_i)} in the covariance to remove kappa from the leading term.
Key results
- RCDB achieves regret Õ(d√T/κ + dC/κ) under known C, matched by a lower bound Ω((d√T+dC)/κ), making it nearly optimal.
- RCDB-S for sigmoid link achieves Õ(dB^1.5√T + dBC/κ), removing κ from the leading term and reducing exponential B dependence to polynomial.
- Experiments on synthetic data show RCDB outperforms state-of-the-art dueling bandit algorithms under adversarial feedback.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use uncertainty-weighted MLE for adversarial preference feedback | RCDB · Contextual Dueling Bandits with adversarial feedback (known C) | regret: $\tilde O\big({d\sqrt{T}}/{\kappa} + {dC}/{\kappa}\big)$ | Helped |
| Add local-derivative estimation instead of using the uniform lower bound $\kappa$ (ablation) | RCDB-S · Contextual Dueling Bandits with sigmoid link function | regret: $\tilde O\big({dB^{1.5}\sqrt{T}} + {dBC}/{\kappa} + d^{2}B^{2}(1/\kappa^2 + B/\kappa)\big)$ | Helped |
| Set the tolerance threshold below the actual adversarial feedback count | RCDB with unknown C · Contextual Dueling Bandits with adversarial feedback | regret: $O(T)$ | Hurt |
Surprising findings
- Any algorithm cannot be simultaneously near-optimal when uncorrupted and sublinear under corruption C=Ω(√T), so the unknown-C case forces a trade-off.
Limitations
- Assumes linear reward with known feature map
- Computing the MLE every round is costly; authors note need for more efficient algorithms
- Kappa dependence persists in warm-up and corruption term for sigmoid case
Experimental setup
Datasets: synthetic simulated dueling bandit environments
Benchmarks: synthetic dueling bandit experiments
Metrics: cumulative regret
Baselines: MaxInP WIWR Versatile-DB
Builds on: CW-OFUL linear dueling bandits COBE
Closest papers by meaning
- Neural Dueling Bandits: Preference-Based Optimization with Human Feedback (ICLR 2025 · similarity 0.92)
- Variance-aware Regret Bounds for Stochastic Contextual Dueling Bandits (ICLR 2024 · similarity 0.92)
- Feel-Good Thompson Sampling for Contextual Dueling Bandits (ICML 2024 · similarity 0.90)
- Borda Regret Minimization for Generalized Linear Dueling Bandits (ICML 2024 · similarity 0.89)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.89)
- An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction (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.