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

• URL: http://arxiv.org/abs/2605.01752v1
• Date: Sun, 03 May 2026 07:19:05 GMT
• Title: Robust Linear Dueling Bandits with Post-serving Context under Unknown Delays and Adversarial Corruptions
• Abstract summary: We study linear dueling bandits in volatile environments characterized by the simultaneous presence of post-serving contexts, delayed feedback, and adversarial corruption.<n>We propose term, which integrates a learned approximator that predicts post-serving contexts from pre-serving information.<n>Our analysis reveals an additive cost structure between corruption and delay, avoiding the multiplicative degradation typical of prior works.
• Score: 13.10320454140084
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 \term, 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. Crucially, our analysis reveals an additive cost structure between corruption and delay, avoiding the multiplicative degradation typical of prior works. 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.

Related papers

• Capacity-Constrained Online Convex Optimization with Delayed Feedback [58.59385794080679]
  We study delayed online convex optimization (OCO) under a hard capacity constraint.<n>We find that for first-order feedback, capacity $C = (log T)$ suffices to recover standard delayed OCO rates up to logarithmic factors.<n>For bandit feedback, the regret rates are modulated by powers of $(1 + _textmax/C)$, where $_textmax$ is the maximum number of pending observations at any time.
  arXiv  Detail & Related papers  (2026-06-10T06:37:06Z)
• Bandit and Delayed Feedback in Online Structured Prediction [25.637979150499874]
  We propose algorithms that work with less demanding feedback, bandit and delayed feedback.<n>We numerically compare the performance of these algorithms, as well as existing ones.
  arXiv  Detail & Related papers  (2025-02-26T00:00:15Z)
• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
  Learning from human feedback plays an important role in aligning generative models, such as large language models (LLM)<n>We study a model within this domain--contextual dueling bandits with adversarial feedback, where the true preference label can be flipped by an adversary.<n>We propose an algorithm namely robust contextual dueling bandits (RCDB), which is based on uncertainty-weighted maximum likelihood estimation.
  arXiv  Detail & Related papers  (2024-04-16T17:59:55Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  We study the non-asymptotic performance of approximation schemes with delayed updates under Markovian sampling. Our theoretical findings shed light on the finite-time effects of delays for a broad class of algorithms.
  arXiv  Detail & Related papers  (2024-02-19T03:08:02Z)
• Delayed Bandits: When Do Intermediate Observations Help? [19.13297969651745]
  We study a $K$-armed bandit with delayed feedback and intermediate observations. We show that the regime of the mapping of states to losses determines the complexity of the problem.
  arXiv  Detail & Related papers  (2023-05-30T13:52:23Z)
• Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes [59.61248760134937]
  We propose an efficient algorithm to achieve a regret of $tildeO(sqrtT+zeta)$. The proposed algorithm relies on the recently developed uncertainty-weighted least-squares regression from linear contextual bandit. We generalize our algorithm to the episodic MDP setting and first achieve an additive dependence on the corruption level $zeta$.
  arXiv  Detail & Related papers  (2022-12-12T15:04:56Z)
• Delayed Feedback in Generalised Linear Bandits Revisited [5.349852254138085]
  We study the phenomenon of delayed rewards in generalised linear bandits in a theoretical manner. We show that a natural adaptation of an optimistic algorithm to the delayed feedback achieves a regret bound where the penalty for the delays is independent of the horizon.
  arXiv  Detail & Related papers  (2022-07-21T23:35:01Z)
• A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits [118.22458816174144]
  We propose a novel robust elimination-type algorithm that runs in epochs, combines exploration with infrequent switching to select a small subset of actions, and plays each action for multiple time instants. Our algorithm, GP Robust Phased Elimination (RGP-PE), successfully balances robustness to corruptions with exploration and exploitation. We perform the first empirical study of robustness in the corrupted GP bandit setting, and show that our algorithm is robust against a variety of adversarial attacks.
  arXiv  Detail & Related papers  (2022-02-03T21:19:36Z)
• Adapting to Delays and Data in Adversarial Multi-Armed Bandits [7.310043452300736]
  We analyze variants of the Exp3 algorithm that tune their step-size using only information available at the time of the decisions. We obtain regret guarantees that adapt to the observed (rather than the worst-case) sequences of delays and/or losses.
  arXiv  Detail & Related papers  (2020-10-12T20:53:52Z)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  We provide two variants of a Robust Phased Elimination algorithm, one that knows $C$ and one that does not. We show that both variants attain near-optimal regret in the non-corrupted case $C = 0$, while incurring additional additive terms respectively. In a contextual setting, we show that a simple greedy algorithm is provably robust with a near-optimal additive regret term, despite performing no explicit exploration and not knowing $C$.
  arXiv  Detail & Related papers  (2020-07-07T09:00:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.