A system that learns what people prefer from pairwise comparisons ("which of these two did you like better?") faces two opposite demands. People's tastes change, so the system should drop old evidence quickly once a new favorite emerges. Feedback can also be manipulated by bots, click fraud, or poisoned comparisons, so the system should be slow and skeptical and should refuse to overturn its beliefs because of a short burst of contrary votes. Existing algorithms handle one demand at a time. Drift-tracking methods forget quickly, which lets an attacker fake a "change" cheaply. Corruption-robust methods are patient, which leaves them stuck on a stale favorite after a real change. As Online robust non-stationary estimation puts it, a sudden shift looks exactly like a burst of corruptions. That paper resolves the conflict only for passive streaming regression, not for a learner that chooses which comparisons to ask for.
We propose a dueling-bandit algorithm built on one accounting principle. The learner accepts that the user's preferred item has changed only when the evidence for the change is larger than anything the remaining corruption budget could have produced on the repeated comparisons it has averaged. Every false restart, and every delayed detection of a real change, then costs the adversary a definite amount of its budget. A charging argument turns this into a regret bound in which drift and corruption contribute additively. We also argue that this is the right target, because any preference "segment" short enough for the adversary to fake is also short enough that ignoring it costs at most the attack budget anyway.
Core Claim
Some terms first. A dueling bandit is a learner that, each round, picks two of $K$ items and observes which one a user prefers. A Condorcet winner is an item preferred over every other item more than half the time. Let the winner change $S^{CW}$ times over $T$ rounds. An adversary may flip observed outcomes, subject to a total budget $C$ that the learner does not know. Dynamic regret measures the loss against whichever item is the winner at each moment. We aim for
$$ \mathrm{Reg}_{\text{dyn}}(T) = \tilde{O}\big(\sqrt{S^{CW} K T} + K\,C\big), $$
where the first term matches the uncorrupted drift lower bound $\Omega(\sqrt{S^{CW}T})$ achieved by ANACONDA up to a $\sqrt{K}$ factor. The second term matches the linear $\Omega(C)$ corruption lower bound proved in Stochastic Dueling Bandits with Adversarial Corruption, up to the $K$ factor. We will also try to prove a matching distinguishability lower bound. It would state that an adversary with budget $C$ can imitate a winner switch lasting about $C/\Delta$ rounds, where $\Delta$ is the preference gap. No algorithm can therefore avoid paying $\Omega(C)$ on such fake switches, and none needs to pay more. If the upper bound only holds with $C$ replaced by $C^2$ when $C$ is unknown, we will report that as the price of ignorance. The linear-bandit result in Stochastic Linear Bandits Robust to Adversarial Attacks shows the same $O(C)\to O(C^2)$ pattern.
What is new is a single restart rule whose threshold is set by corruption accounting. It is not a drift detector bolted onto a robust learner, and it is not a discount factor. The closest work handles one side only. Learning from Imperfect Human Feedback (RoSMID) handles corruption that decays over time but assumes a fixed utility. WIWR handles arbitrary corruption but assumes a fixed winner. DEX3.S, ANACONDA, and the window-based DETECT/MDB of Piecewise-Stationary Dueling Bandits handle drift but assume honest feedback.
Research Program
The algorithm reuses three existing mechanisms and adds one new piece.
The first mechanism comes from WIWR. The learner keeps an anchor item, the current guess at the winner, and duels it against challengers sampled in inverse proportion to their estimated gap. No item is ever permanently eliminated. This prevents the permanent-discard failure that Adversarial Bandits with Corruptions shows leads to linear regret.
The second mechanism comes from robust phased elimination (RGP-PE, RPE). Duels are run in blocks, and each chosen pair is repeated $n$ times within a block. To move the averaged outcome by $\epsilon$, the adversary must therefore spend about $n\epsilon$ budget.
The third mechanism comes from ANACONDA. A randomized replay schedule re-tests the anchor against old challengers at random times. The adversary cannot pre-position its corruptions without spending budget across all possible test times.
The new piece is the restart test. Let $\hat p_{\text{old}}$ be the anchor's averaged win rate against a challenger over the long history, and let $\hat p_{\text{new}}$ be the same rate over the most recent $n$ repeated duels. The learner restarts, discarding old statistics and promoting the challenger, only if
$$ \hat p_{\text{old}} - \hat p_{\text{new}} > 2\sqrt{\tfrac{\log(KT/\delta)}{n}} + \frac{\hat C}{n}, $$
where $\delta$ is a failure probability and $\hat C$ is the learner's current corruption estimate. The square-root term is the usual statistical deviation. The $\hat C/n$ term is the largest shift that corruption could produce in an average of $n$ duels, which is the same offset that RGP-PE adds to its confidence widths.
The analysis then charges each bad event to the budget. A false restart requires the adversary to spend at least about $\hat C$ (when $\hat C \ge C$) or about $\sqrt{n\log T}$ on a single window. A masked real change forces the adversary to spend in proportion to how long it hides the change. When $C$ is unknown, we run $\log T$ copies with geometrically spaced $\hat C$ values and select among them with a top-level learner, as in the Bandit-over-Bandit scheme of Hsieh et al.. We will measure honestly whether this costs $C$ or $C^2$.
The theory will be developed first for $K$ discrete items with a Condorcet winner in each segment. We then extend it to linear contextual comparisons, where the block-averaging argument carries over directly. Cyclic preferences without a winner are out of scope. We will state that the guarantees break there, just as they do for ANACONDA and MDB.
Baselines
The naive reference point is RUCB, a stationary, uncorrupted dueling algorithm. It shows how badly an unprotected learner fares under drift and attack together. WIWR (Stochastic Dueling Bandits with Adversarial Corruption) is the strongest corruption-only competitor. It already discards data at geometric epoch boundaries and has a recourse mechanism, so it may track slow drift by accident. ANACONDA is the strongest drift-only competitor. Its random replay could partly rescue items whose wins were suppressed, which makes it the most dangerous single baseline. DEX3.S and MDB represent drift tracking by weight mixing and by detection windows, respectively.
Two hybrids test whether simple composition is enough. The first is WIWR run over a sliding window. The second is WIWR reset by Bayesian Online Changepoint Detection.
Two ablations isolate the key ingredient. One removes the $\hat C/n$ term from the restart threshold, leaving a purely statistical restart rule. The other sets block length $n=1$, removing averaging over repeated duels.
All methods receive the same instances, attack sequences, horizon, and random seeds. Each method gets the same tuning grid of 20 configurations, covering window length, discount, mixing rate, and $\hat C$ grid. Tuning is done on held-out instances, not the test instances. Drift-budget knowledge is supplied to DEX3.S only in an oracle variant, which is labeled as such.
For empirical comparisons, no reported result was found on Lacuna for the synthetic switching dueling benchmarks. The file reports only bounds: $\tilde{O}(\sqrt{S^{CW}T})$ for ANACONDA and $\tilde{O}(\sqrt{SKT})$ for DEX3.S. We will therefore reproduce all baselines ourselves. Beating ANACONDA means two things. Under attack, we need lower dynamic regret with non-overlapping 95% intervals across 50 seeds. Without attack, we must stay within 10% of its regret. Beating WIWR means lower regret under drift at equal corruption.
Why not just…?
Why not just run a corruption-robust algorithm over a sliding window, or discount old data as NS-DPO does? A window shrinks the sample pool the adversary must corrupt. WIWR's own paper shows that elimination-style learners on small pools fail with only $O(\log T)$ corruptions. Exponential discounting $\gamma^{T-t_i-1}$, as in NS-DPO, gives the most weight to the most recent data, which is exactly where a burst attack lands. The windowed-WIWR baseline under the burst-on-new-winner attack tests this directly.
Why not just treat drift as adversarial and run EXP3-style learners? Adversarial Bandits with Corruptions proves that EXP3 suffers $\Omega(T^{1-\epsilon})$ regret against a targeted attacker with budget $O(T^{1/2+2\epsilon})$. The low-probability-arm suppression it describes is the attack we run. DEX3.S remains in the baseline set so this claim is tested, not assumed.
Why not just reset a robust learner whenever a changepoint detector fires? Detectors assume independent, identically distributed data within a regime. An adversary can trigger false alarms with transient outliers, and each alarm erases progress. The adversary can also suppress alarms, as described for MDB. Our test differs in that its threshold prices corruption explicitly. The BOCPD-reset baseline under the fake-switch attack will show whether the difference matters.
Why not just use ANACONDA, whose random replay already re-tests discarded items? This is the real threat. Replay may recover suppressed winners without any corruption accounting. However, ANACONDA restarts on purely statistical evidence, so we expect cheap fake switches to cause repeated restarts. The test is whether ANACONDA's regret grows faster than linearly in the number of fake switches the adversary can afford. If ANACONDA instead matches our method across all attacks, the contribution shrinks to the analysis alone, and we will say so.
Proposed Experiments
The first testbed is synthetic switching dueling bandits in the style of benchmark 8. It uses $K\in\{10,50\}$, $T=10^6$, $S^{CW}\in\{0,5,20\}$, and corruption budgets $C\in\{0, T^{1/4}, T^{1/2}, T^{2/3}\}$. We run four attacks. The burst attack suppresses a newly emerged winner. The fake-switch attack imitates a winner change. The masking attack hides a true change. The fourth targets only the current winner, which is WIWR's $C_1$ budget.
The decisive check is a plot of dynamic regret against $C$ at fixed $S^{CW}$, and against $S^{CW}$ at fixed $C$. Our method should show additive, roughly linear growth in each. The no-$\hat C$ ablation should show super-linear growth under fake switches.
The second testbed is semi-synthetic, built from the New Yorker Caption Contest data. It has 365 weekly contests and more than 250 million ratings, which yields realistic, non-synthetic preference matrices. We cluster captions into style arms using text embeddings and estimate a preference matrix per block of contests. The resulting sequence of matrices provides naturally occurring switches, to which we add the same attacks.
The third testbed is an online elicitation version of the UltraFeedback-RM changepoint setup. Preference criteria flip at known changepoints, and poisoned comparisons are injected. We measure post-changepoint accuracy in predicting preferences. For context, NS-DPO reports reward accuracy of 60–70% against DPO's ~50–55% after flips, and an LCWR of 8.93 against 7.29 on UltraFeedback-LM. Those are offline results without attacks. We will run NS-DPO on the poisoned version, and also NS-DPO with our restart test replacing uniform discounting, to see whether the accounting principle transfers to offline alignment.
The proposal fails if any of three things holds. ANACONDA matches us under all attacks. Our zero-attack regret exceeds ANACONDA's by more than 10%. Or the unknown-$C$ version degrades quadratically with no recoverable rate.
References
- Online robust non-stationary estimation
- ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits
- Stochastic Dueling Bandits with Adversarial Corruption
- Stochastic Linear Bandits Robust to Adversarial Attacks
- Learning from Imperfect Human Feedback: A Tale from Corruption-Robust Dueling
- Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits
- Piecewise-Stationary Dueling Bandits
- Adversarial Bandits with Corruptions: Regret Lower Bound and No-regret Algorithm
- A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits
- Robust Stochastic Linear Contextual Bandits Under Adversarial Attacks
- Bayesian Online Changepoint Detection
- Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift
- Humor in AI: Massive Scale Crowd-Sourced Preferences and Benchmarks for Cartoon Captioning