Introduction
In real-world machine learning applications, agents frequently make decisions based on incomplete information, face significant delays in receiving feedback, and must withstand adversarial data corruption. This paper introduces RCDP-UCB, the first algorithm for linear dueling bandits designed to simultaneously handle "post-serving" contexts (features revealed only after a choice is made), unknown feedback delays, and adversarial corruption. By employing a novel adaptive weighting strategy, RCDP-UCB prevents these three challenges from compounding, achieving near-optimal regret bounds.
The Tripartite Challenge
Standard "dueling bandit" problems—foundational to Reinforcement Learning from Human Feedback (RLHF)—assume an agent chooses between two items and receives immediate, reliable feedback on the preference. However, real-world deployments face a tripartite challenge:
- Post-serving Context: Traditional models assume all item features are known prior to selection. In reality, utility often depends on post-serving features learned only after the fact (e.g., actual delivery time or food temperature in a delivery service).
- Unknown Delays: Feedback is rarely instantaneous. It may be delayed by minutes or days, and these delays can be stochastic (random) or adversarial (strategically timed by an attacker).
- Adversarial Corruption: Malicious actors may intentionally flip or corrupt feedback to bias the learning process.
When combined, these issues create a vicious cycle. Delays starve the model of data, making the few arriving observations disproportionately influential and thus highly susceptible to adversarial corruption.
Methodology: RCDP-UCB
To address these compounding vulnerabilities, the authors propose RCDP-UCB (Robust to Corruption, Delay, and Post-serving UCB), built on two core innovations:
- Contextual Mapping Approximator: Because post-serving features are unknown at selection time, RCDP-UCB utilizes a learned approximator (such as a neural network) to predict these latent features from available pre-serving information.
- Unified Adaptive Weighting: The algorithm employs a weighted ridge regression where each observation receives a weight based on its statistical leverage. If an observation appears to be a massive outlier or carries excessive influence—potentially due to corruption or extreme delay—the algorithm "clips" its feature vector, effectively down-weighting it.
Crucially, RCDP-UCB calculates these weights using the Full History Matrix (all contexts seen so far) rather than just the Observed History Matrix (contexts with arrived feedback). This information asymmetry anchors the estimation process to the global information manifold, ensuring stability even if an adversary manipulates feedback timing.
Experimental Validation
The researchers evaluated RCDP-UCB across both synthetic and real-world environments:
- Synthetic Environments: Tested the algorithm's robustness against various non-linear mappings (Polynomial, Sinusoidal, and Absolute functions) for post-serving contexts.
- Real-world Datasets: Utilized eight classification datasets from the UCI Machine Learning Repository and OpenML (including Magic Gamma Telescope, Statlog/Satimage, and Spambase). Features were partitioned into "visible" (pre-serving) and "latent" (post-serving) sets to simulate partial observability.
Key Findings and Theoretical Guarantees
- Theoretical Optimality: RCDP-UCB achieves a rigorous regret upper bound of $\widetilde{\mathcal{O}}(d(\sqrt{T} + \mathcal{C} + \mathcal{D}))$, where $d$ is the feature dimension, $\mathcal{C}$ is the corruption budget, and $\mathcal{D}$ encapsulates delay complexity. This demonstrates that the penalties for delay and corruption are additive rather than multiplicative. Furthermore, this bound matches the derived theoretical lower bounds within a factor of $\sqrt{d}$.
- Empirical Superiority: In experiments, RCDP-UCB consistently outperformed state-of-the-art baselines like RCDB and MaxPairUCB. The performance gap widened as the number of arms ($K$) or dimensionality ($d$) increased, highlighting its robustness in complex environments.
- Agnostic Stability: The algorithm treats adversarial corruption and invisible delayed feedback using the same unified weighting mechanism, remaining stable across varying levels of delay variance without needing to know the underlying cause of the feedback anomaly.
Limitations and Future Directions
While RCDP-UCB represents a significant step forward, the authors identify several areas for future research:
- Delayed Post-serving Contexts: The current model assumes that while preference feedback is delayed, post-serving features are revealed immediately after the action. Future work must address scenarios where these features are also delayed.
- The $\sqrt{d}$ Gap: A small gap remains between the theoretical upper and lower bounds in the adversarial delay regime, presenting an open mathematical challenge.
- Learnability Bounds: The analysis assumes the mapping from pre- to post-serving context is learnable, but tightening the bounds to explicitly account for the complexity of this specific learning task remains to be explored.
Code is available at: https://github.com/youngmin0oh/rcdp-public
Summary updated