Title: Robust Linear Dueling Bandits with Post-serving Context under Unknown Delays and Adversarial Corruptions

Abstract:

This paper investigates linear dueling bandits operating in volatile environments where post-serving contexts, delayed feedback, and adversarial corruptions coexist. The feedback mechanism is subjected to unknown delays that are either stochastic or adversarial, alongside a cumulative corruption budget denoted as $\mathcal{C}$. To tackle these complexities, we introduce e RCDP-UCB, an algorithm that incorporates a learned approximator designed to predict post-serving contexts based on pre-serving information. Additionally, it utilizes an adaptive weighting strategy that clips feature vectors to simultaneously neutralize the effects of both delayed and corrupted observations.

Under standard regularity conditions and assuming a parametric post-serving mapping, we provide a rigorous analysis demonstrating that our approach is agnostic to the delay regime. It achieves a regret upper bound of $\widetilde{\mathcal{O}}(d(\sqrt{T} + \mathcal{C} + \mathcal{D}))$, where $d$ represents the total feature dimension and $\mathcal{D}$ captures the delay complexity. A key insight from our analysis is the additive cost structure between corruption and delay, which circumvents the multiplicative performance degradation commonly observed in previous studies. Furthermore, we derive lower bounds that closely align with our upper bounds, differing only by a $\sqrt{d}$ factor in scenarios involving adversarial delays without post-serving contexts. The source code is accessible at https://github.com/youngmin0oh/rcdp-public.

Source: arXiv Generated at: 2026-06-02 00:00:00 UTC