Linear and Neural Dueling Bandits with Delayed Feedback

• URL: http://arxiv.org/abs/2605.26554v1
• Date: Tue, 26 May 2026 05:07:25 GMT
• Title: Linear and Neural Dueling Bandits with Delayed Feedback
• Abstract summary: Contextual dueling bandits form a cornerstone of preference-based decision-making.<n>Standard algorithms rely on the idealized assumption of immediate feedback.<n>We propose two novel algorithms: Linear (LDB-DF) and Neural (NDB-DF) Dueling Bandits with Delayed Feedback.
• Score: 21.304131079137093
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Contextual dueling bandits form a cornerstone of preference-based decision-making, with critical applications in recommender systems and large language model alignment. However, standard algorithms rely on the idealized assumption of immediate feedback, a condition frequently violated in real-world scenarios such as prompt optimization. This setting introduces a unique theoretical challenge: unlike linear bandits, dueling bandit estimators lack closed-form solutions, rendering naive adaptations of standard weighting techniques biased. To address this, we formalize the problem of Contextual Dueling Bandits with Stochastic Delayed Feedback and propose two novel algorithms: Linear (LDB-DF) and Neural (NDB-DF) Dueling Bandits with Delayed Feedback. Central to our approach is a novel estimator that integrates an Inverse Probability Weighting (IPW) mechanism directly into the loss function, ensuring unbiased correction for delayed or missing feedback. We provide comprehensive theoretical analysis, establishing an O(d*sqrt(T)) regret bound for the linear setting and sub-linear guarantees for the neural setting. Extensive experiments on both simulated and real-world datasets demonstrate the effectiveness of our propose.

Related papers

• Unbiased Alignment for Large Language Models with Noisy Preferences [74.69408994904965]
  We present a theoretical framework for unbiased alignment, introducing the Unbiased Reward Model (URM) loss and the Unbiased Direct Preference Optimization (UDPO) loss.<n>By mathematically correcting the distortion induced by preference noise, our novel objectives enable unbiased model training directly from noisy datasets.
  arXiv  Detail & Related papers  (2026-07-03T12:04:43Z)
• Non-Parametric Rehearsal Learning via Conditional Mean Embeddings [88.89267783967263]
  We propose a non-parametric rehearsal learning approach for textitavoiding undesired future (AUF) problems.<n>Specifically, we use kernel machinery to reformulate the AUF objective into a unified representation that disentangles desirability modeling from action-induced distributional changes.
  arXiv  Detail & Related papers  (2026-05-09T15:30:52Z)
• Score-Guided Proximal Projection: A Unified Geometric Framework for Rectified Flow Editing [1.0312968200748118]
  Rectified Flow models achieve state-of-the-art generation quality, yet controlling them for precise tasks remains a challenge.<n>Current approaches bifurcate into inversion-based guidance, which suffers from "geometric locking"<n>We propose Score-Guided Proximal Projection, a unified framework that bridges the gap between deterministic optimization and contraction sampling.
  arXiv  Detail & Related papers  (2026-03-05T23:44:45Z)
• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [70.38810219913593]
  We study the generalized linear bandit (GLB) problem, a contextual multi-armed bandit framework that extends the classical linear model by incorporating a non-linear link function.<n>GLBs are widely applicable to real-world scenarios, but their non-linear nature introduces significant challenges in achieving both computational and statistical efficiency.<n>We propose a jointly efficient algorithm that attains a nearly optimal regret bound with $mathcalO(1)$ time and space complexities per round.
  arXiv  Detail & Related papers  (2025-07-16T02:24:21Z)
• Active Human Feedback Collection via Neural Contextual Dueling Bandits [84.7608942821423]
  We propose Neural-ADB, an algorithm for collecting human preference feedback when the underlying latent reward function is non-linear.<n>We show that when preference feedback follows the Bradley-Terry-Luce model, the worst sub-optimality gap of the policy learned by Neural-ADB decreases at a sub-linear rate as the preference dataset increases.
  arXiv  Detail & Related papers  (2025-04-16T12:16:10Z)
• Neural Dueling Bandits: Preference-Based Optimization with Human Feedback [58.90189511247936]
  We use a neural network to estimate the reward function using preference feedback for the previously selected arms.<n>We also extend our theoretical results to contextual bandit problems with binary feedback, which is in itself a non-trivial contribution.
  arXiv  Detail & Related papers  (2024-07-24T09:23:22Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Online Statistical Inference in Decision-Making with Matrix Context [5.2071564436846245]
  We propose an online procedure to conduct statistical inference with adaptively collected data.<n>Standard low-rank estimators are biased and cannot be obtained in a sequential manner.<n>Existing approaches in sequential decision-making algorithms fail to account for the low-rankness and are also biased.
  arXiv  Detail & Related papers  (2022-12-21T22:03:06Z)
• Hypothesis Transfer in Bandits by Weighted Models [8.759884299087835]
  We consider the problem of contextual multi-armed bandits in the setting of hypothesis transfer learning. We show a re-weighting scheme for which we show a reduction in the regret over the classic Linear UCB when transfer is desired. We further extend this method to an arbitrary amount of source models, where the algorithm decides which model is preferred at each time step.
  arXiv  Detail & Related papers  (2022-11-14T14:13:02Z)
• Optimal Regularized Online Allocation by Adaptive Re-Solving [16.873430173722994]
  This paper introduces a dual-based algorithm framework for solving the regularized online resource allocation problems. Under a strategy of adaptively updating the resource constraints, the proposed framework only requests approximate solutions to the empirical dual problems up to a certain accuracy. Surprisingly, a delicate analysis of the dual objective function enables us to eliminate the notorious log-log factor in regret bound.
  arXiv  Detail & Related papers  (2022-09-01T12:23:26Z)
• On Kernelized Multi-Armed Bandits with Constraints [16.102401271318012]
  We study a bandit problem with a general unknown reward function and a general unknown constraint function. We propose a general framework for both algorithm performance analysis. We demonstrate the superior performance of our proposed algorithms via numerical experiments.
  arXiv  Detail & Related papers  (2022-03-29T14:02:03Z)
• Bias-Robust Bayesian Optimization via Dueling Bandit [57.82422045437126]
  We consider Bayesian optimization in settings where observations can be adversarially biased. We propose a novel approach for dueling bandits based on information-directed sampling (IDS) Thereby, we obtain the first efficient kernelized algorithm for dueling bandits that comes with cumulative regret guarantees.
  arXiv  Detail & Related papers  (2021-05-25T10:08:41Z)
• Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination [29.85468294601847]
  We revisit two classic high-dimensional online learning problems, namely linear regression and contextual bandits. We show that our algorithms succeed where conventional methods fail.
  arXiv  Detail & Related papers  (2020-10-08T17:59:05Z)

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.