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

1. Problem Formulation

This paper addresses a complex decision-making problem within the Linear Contextual Dueling Bandits (CDB) framework, specifically targeting volatile environments characterized by three simultaneous challenges:

1. Post-serving Contexts: Unlike standard contextual bandits where utility is determined solely by pre-action features (e.g., user demographics), the true utility here depends on latent features revealed only after the action is taken (e.g., delivery time, food temperature). The learner must estimate a mapping $\phi^*$ from pre-serving contexts $x_t$ to post-serving contexts $y_t$.
2. Unknown Feedback Delays: Feedback arrives with delays $\tau_t$ that are either stochastic (sub-Gaussian) or adversarial. The learner does not know which regime is active, nor the specific delay sequence.
3. Adversarial Corruption: An adversary can corrupt the observed preference outcomes (flipping 0 to 1 or vice versa) subject to a cumulative budget $C$.

The core difficulty lies in the multiplicative interplay of these factors. Delays reduce the effective sample size, amplifying the statistical leverage of corrupted signals. Furthermore, the learner must estimate the post-serving mapping $\phi^*$ using feedback that is already compromised by delays and corruption, creating a vicious cycle of estimation error.

The objective is to minimize cumulative regret $R_T$, defined as the utility gap between the optimal arm pair and the selected pair, while remaining agnostic to the specific delay regime and corruption presence.

2. Methodology: RCDP-UCB

The authors propose RCDP-UCB (Robust to Corruption, Delay, and Post-serving UCB), an algorithmic framework designed to handle these intertwined challenges.

Key Components:

• Context Prediction: The algorithm employs a learned approximator $\hat{\phi}_t$ (e.g., a neural network) to predict post-serving contexts $y_t$ from pre-serving contexts $x_t$ before action selection. The feature vector is constructed as $\hat{z}_t = (x_t, \hat{\phi}_t(x_t))$.
• Dual Design Matrices: The algorithm maintains two distinct matrices to decouple selection from estimation:
  • $\tilde{V}_t$: The Full History Matrix, constructed using all chronological contexts (both arrived and pending). This matrix is used for arm selection and weight calculation to ensure optimism and stability.
  • $\hat{W}_t$: The Observed History Matrix, constructed only from feedback that has actually arrived by time $t$. This is used strictly for parameter estimation ($\Theta_t$) to ensure statistical validity.
• Adaptive Weighting Strategy: A unified weighting mechanism is introduced to mitigate both corruption and delay-induced bias. For a sample $s$, the weight $\omega_s$ is defined as:
  $$\omega_s = \min\left(1, \frac{\alpha}{\|\Delta z_s\|_{\tilde{V}_{s-1}^{-1}}}\right)$$
  where $\alpha$ is a robustness parameter. This "clipping" strategy down-weights samples with high statistical leverage (large norms), effectively limiting the influence of both adversarially corrupted observations and delayed feedback that skews the information geometry.
• Regret Minimization: The algorithm selects arm pairs $(a_t, b_t)$ using an Upper Confidence Bound (UCB) strategy based on $\tilde{V}_t$ and the predicted features, balancing exploration and exploitation while accounting for the uncertainty in both the preference parameter $\Theta^*$ and the post-serving mapping $\phi^*$.

3. Key Contributions

1. Unified Analytical Framework: The paper formalizes the first linear dueling bandit setting that simultaneously incorporates post-serving contexts, unknown delays (stochastic or adversarial), and adversarial corruption.
2. Algorithm Design (RCDP-UCB): It introduces a novel algorithm that integrates contextual mapping estimation with an adaptive clipping mechanism. Crucially, the weighting scheme is delay-regime-agnostic, meaning it does not require prior knowledge of whether delays are stochastic or adversarial to function effectively.
3. Theoretical Guarantees:
   • Upper Bound: Under standard regularity conditions, the algorithm achieves a regret upper bound of $\tilde{O}(d(\sqrt{T} + C + D))$, where $d$ is the feature dimension, $T$ is the time horizon, $C$ is the corruption budget, and $D$ represents delay complexity ($D = \max(\sqrt{\Lambda}, \mu_\tau)$).
   • Lower Bound: The authors derive a minimax lower bound of $\Omega(\sqrt{dT} + dC + D')$ (where $D' = \max(\sqrt{d\Lambda}, d\mu_\tau)$) in the absence of post-serving contexts. This confirms that the overhead introduced by delays and corruption is information-theoretically unavoidable.
   • Optimality: The upper bound matches the lower bound up to a $\sqrt{d}$ factor for adversarial delays, demonstrating near-optimal efficiency.

4. Experimental Results

The authors evaluate RCDP-UCB on synthetic environments and real-world datasets (UCI and OpenML) under various conditions:

• Synthetic Settings: Experiments cover linear and non-linear post-serving mappings (Polynomial, Sinusoidal, Absolute) with varying corruption budgets ($C$) and delay regimes (Strategic/Adversarial and Stochastic).
• Baselines: The algorithm is compared against state-of-the-art methods including RCDB (robust to corruption), ColSTIM, MaxInP, and MaxPairUCB.
• Findings:
  • RCDP-UCB consistently outperforms baselines in cumulative regret across all delay regimes and corruption levels.
  • The algorithm demonstrates superior robustness in "latent" environments where post-serving contexts are critical; baselines that fail to model these contexts or lack robust weighting suffer significantly higher regret.
  • The adaptive weighting mechanism effectively neutralizes the combined noise of corruption and delay, maintaining stable performance even as context dimensionality ($d$) and the number of arms ($K$) increase.
  • Real-world dataset experiments confirm the algorithm's scalability and robustness even when the linear preference assumption is only an approximation.

5. Significance and Claims

The paper claims to be the first work to simultaneously address the joint challenges of adversarial corruptions, unknown feedback delays, and post-serving contexts within the contextual dueling bandit framework.

• Theoretical Impact: It establishes that the combined effect of these factors is fundamentally multiplicative but can be managed via a unified weighting strategy anchored to the full information geometry ($\tilde{V}_t$). The results provide "best-of-both-worlds" guarantees for delay regimes, adapting to both stochastic and adversarial settings without explicit detection.
• Practical Relevance: The work is motivated by modern interactive systems, particularly Reinforcement Learning from Human Feedback (RLHF) for Large Language Models (LLMs). In such systems, user preferences are often relative (dueling), feedback is delayed, and data can be noisy or manipulated. The proposed framework offers a path toward more reliable, robust, and accurate alignment of AI systems with human intent by accounting for latent post-action factors and data irregularities.

The authors acknowledge limitations, noting that the $\sqrt{d}$ gap in the adversarial delay lower bound remains an open problem and that extending the framework to handle delayed post-serving contexts is a direction for future research.