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

We study linear dueling bandits in volatile environments characterized by the simultaneous presence of post-serving contexts, delayed feedback, and adversarial corruption. Feedback is subject to unknown stochastic or adversarial delays and a cumulative corruption budget $\mathcal{C}$. To address these challenges, we propose RCDP-UCB, which integrates a learned approximator that predicts post-serving contexts from pre-serving information. It further employs an adaptive weighting strategy that clips feature vectors to mitigate the impact of corrupted and delayed observations simultaneously. Under standard regularity conditions and a parametric post-serving mapping, we rigorously establish that our algorithm is delay-regime-agnostic, achieving a regret upper bound of $\widetilde{\mathcal{O}}(d(\sqrt{T} + \mathcal{C} + \mathcal{D}))$, where $d$ is the total feature dimension and $\mathcal{D}$ encapsulates the delay complexity, scaling with $\sqrt{\Lambda}$ under adversarial delays or $\mu_{\tau}$ under stochastic delays ($\Lambda$: cumulative delay budget; $\mu_{\tau}$: mean of sub-Gaussian delays). We further establish lower bounds that nearly match our upper bounds up to a $\sqrt{d}$ factor for adversarial delays in the absence of post-serving contexts. Code is available at \url{https://github.com/youngmin0oh/rcdp-public}.

Many online systems $-$ recommender systems, A/B testing platforms, ad auctions, clinical trial designs $-$ repeatedly choose between options based on user feedback and then learn which choice was better. Three things make this hard in practice. First, some of the information that explains why one option was better only becomes visible after the choice has been made (for example, how long a user actually engaged with a recommended item). Second, feedback often arrives late, in an unpredictable order, and sometimes never. Third, a small fraction of the feedback may be deliberately tampered with by an adversary or simply corrupted by noisy logging. We design a learning algorithm that copes with all three problems at once. It predicts the hidden after-the-fact information from what is available before each choice, and it automatically down-weights data points that look unreliable $-$ whether they are unreliable because they arrived late or because they were corrupted. We prove that, even in this hostile setting, the algorithm’s performance degrades only mildly compared with the ideal case where everything is observed cleanly and immediately, and we show with simulations that it outperforms previous methods that were designed to handle only one of the three problems in isolation. The result is a single, principled procedure that practitioners can use when their feedback pipelines are messy in more than one way at the same time.