Technical Summary: Linear and Neural Dueling Bandits with Delayed Feedback

1. Problem Definition

The paper addresses the problem of Contextual Dueling Bandits (CDB) under Stochastic Delayed Feedback. In standard CDB settings, an agent selects a pair of arms (candidates) and receives immediate binary preference feedback (e.g., $x_1 \succ x_2$) to learn a latent reward function. However, in real-world applications such as Large Language Model (LLM) alignment, prompt optimization, and display advertising, feedback is often asynchronous.

The specific setting formalized in this work assumes:

• Stochastic Delays: Feedback for an action taken at round $s$ arrives after a random delay $D_s$.
• Hard Threshold: There is a maximum observation window $M$. If $D_s > M$, the feedback is treated as missing (censored).
• Observation Probability: The probability of feedback arriving within the window is $\rho = P(D_s \le M)$.
• Bias Challenge: Unlike linear bandits where estimators have closed-form solutions (e.g., ridge regression), dueling bandits rely on Maximum Likelihood Estimation (MLE) under the Bradley-Terry-Luce (BTL) model. This lack of closed-form solutions means that naive adaptations of standard delayed feedback techniques (such as simple imputation or ignoring missing data) introduce systematic bias that cannot be easily bounded or corrected.

2. Methodology

The authors propose two novel algorithms designed to handle these delays without heuristic imputation: Linear Dueling Bandits with Delayed Feedback (LDB-DF) and Neural Dueling Bandits with Delayed Feedback (NDB-DF).

Core Mechanism: Inverse Probability Weighting (IPW)

The central innovation is the integration of an Inverse Probability Weighting (IPW) mechanism directly into the loss function.

• Weighting Strategy: For a feedback instance $y_s$ observed at round $t$ (where $s < t$), the algorithm assigns a weight $\omega_{s,t} = \frac{1}{\rho} \cdot \mathbb{I}\{D_s \le \min(M, t-s)\}$.
• Unbiased Correction: By scaling the contribution of observed feedback by $1/\rho$, the expected gradient of the surrogate loss becomes an unbiased estimator of the true gradient, effectively neutralizing the bias introduced by the stochastic observation mechanism and missing data.

Algorithm 1: LDB-DF (Linear Setting)

• Model: Assumes a linear reward function $f(x) = \theta^\top \phi(x)$.
• Estimation: Minimizes an IPW-regularized logistic loss using only "arrived" feedback.
• Exploration: Utilizes an Upper Confidence Bound (UCB) strategy. The first arm is selected greedily based on the current estimate $\theta_t$. The second arm is selected to maximize the UCB of the preference difference relative to the first arm, incorporating a confidence radius $\beta_t$ that accounts for both stochastic noise and delay-induced uncertainty.
• Information Matrix: Updated immediately using feature vectors of selected pairs, independent of feedback latency.

Algorithm 2: NDB-DF (Neural Setting)

• Model: Approximates the non-linear reward function using a fully connected neural network $h(x; \theta)$ with ReLU activations.
• Estimation: Trains the network online using the same IPW-weighted cross-entropy loss, learning only from the subset of feedback that has arrived within the valid window.
• Theoretical Framework: Analysis is conducted in the Neural Tangent Kernel (NTK) regime. The algorithm assumes the network is sufficiently wide ($m$) such that it behaves approximately as a linear function in the gradient feature space at initialization.
• Exploration: Similar to the linear case, it employs a UCB strategy. The exploration bonus is derived from the NTK feature space, quantifying epistemic uncertainty in the preference difference.

3. Theoretical Contributions

The paper provides rigorous regret bounds for both settings, explicitly characterizing the impact of delay parameters ($M$ and $\rho$).

• Linear Regret Bound: The cumulative regret for LDB-DF is established as $\tilde{O}\left(\frac{M}{\rho \kappa_\mu} d \sqrt{T}\right)$.

  • The term $\frac{M}{\rho}$ acts as a multiplicative penalty. A smaller observation probability $\rho$ (fewer samples) and a larger threshold $M$ (longer potential delays) linearly increase the regret.
  • When $\rho=1$ and $M=1$ (no delay), the bound recovers the state-of-the-art $\tilde{O}(d\sqrt{T})$ for standard linear dueling bandits.

• Neural Regret Bound: The cumulative regret for NDB-DF is established as $\tilde{O}\left(\frac{M}{\rho \kappa_\mu} \tilde{d} \sqrt{T}\right)$, where $\tilde{d}$ is the effective dimension of the NTK matrix.

  • The proof relies on a novel "add-and-subtract" decomposition technique to separate martingale noise from systematic bias induced by delays.
  • The analysis confirms that the fundamental hardness of the problem (trade-off between observation likelihood and delay magnitude) persists even with complex non-linear function approximators.

4. Experimental Results

The authors evaluate LDB-DF and NDB-DF against baselines that either ignore delays or use heuristic imputation.

• Baselines:
  • Ignore: Uses the same model architecture but discards pending feedback until arrival without weighting.
  • Heuristic: Imputes missing feedback using the current model's predicted preference (biased proxy).
• Datasets:
  • Synthetic: Linear, Quadratic, and Cubic reward functions with stochastic geometric delays.
  • Real-world: Automated Prompt Optimization using the InstructZero benchmark (29 instruction induction tasks).
• Findings:
  • Both proposed algorithms significantly outperform baselines in terms of cumulative regret.
  • In non-linear settings, the Heuristic baseline often converges to suboptimal regions due to self-reinforcing prediction errors (hallucinations), while the Ignore baseline suffers from data sparsity.
  • LDB-DF and NDB-DF demonstrate robustness to feedback latency, effectively navigating the search space in prompt optimization tasks.

5. Significance and Claims

The paper claims to bridge a critical gap in preference-based learning by providing the first unified framework that simultaneously handles:

1. Preference Feedback (Dueling): Binary relative outcomes rather than absolute rewards.
2. Non-linear Approximation (Neural): Complex reward landscapes via neural networks.
3. Stochastic Delays/Missing Data: Realistic feedback latency and censorship.

The authors emphasize that their approach departs from heuristic imputation, offering a principled, unbiased solution via IPW. The theoretical analysis establishes the first regret bounds for this specific setting, demonstrating that the performance degradation is predictable and linearly dependent on the delay characteristics ($M/\rho$). The work is positioned as a foundational step for improving asynchronous preference learning in human-in-the-loop systems, particularly for LLM alignment and prompt optimization.