mlsanityData to 14 Oct 2026

Saturation-Insensitive Dueling Bandits with General Function Approximation

arXiv 2609.33011 ↗First posted 26 Sep 2026cs.LGcited by 0

On the map: LLM alignment / RLHF / preference optimisation → Reward modeling and RLHF also fits: Reward hacking and misspecification

Abstract (arXiv)

We study contextual dueling bandits with general function approximation under the Bradley-Terry-Luce (BTL) preference model. A key challenge in this setting is the saturation of the preference model: when the current reward model can already distinguish two actions with high confidence, the resulting preference feedback becomes weakly informative, making it difficult to further improve reward estimation. Consequently, existing sample-complexity analyses often depend on the inverse-derivative factor 1 / σ'[Deltar^ast] which can be prohibitively large when the link function σ saturates for large reward gaps Deltar^ast. To address this issue, we introduce `SI-CDB`, an algorithm that selects opponent arms using a carefully designed heuristic for arm selection. This design enables saturation-insensitive reward learning and recovers the near-optimal dependence for linear reward classes, eliminating the unfavorable 1/σ'(·) factor. The core of our analysis is a localized Eluder dimension framework tailored to dueling bandits with general function approximation. Our theoretical results also explain why two-arm regret analysis is crucial for improving single-arm performance in dueling bandits.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Reward modeling and RLHF, one of 10 directions in LLM alignment / RLHF / preference optimisation. Builds on 7 of its 54 references that are in the map. First posted on arXiv 26 Sep 2026.

Builds on

7 of 54 references.

Closest ancestors · 2

Same direction, newest first

  1. 2024Reinforcement Learning from Human Feedback with Active Queries14 Feb
  2. 2023Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problems24 Jul

Other references · 5

  1. 2024Active Preference Learning for Large Language Modelscited by 58
  2. 2022PAC Reinforcement Learning for Predictive State Representationscited by 43
  3. 2024A Unified Confidence Sequence for Generalized Linear Models, with Applications to Banditscited by 29
  4. 2024Feel-Good Thompson Sampling for Contextual Dueling Banditscited by 27
  5. 2026Learning What to Recommend: Minimax Optimal Simple Regret in Logistic Banditscited by 2

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Neural Dueling Bandits: Preference-Based Optimization with Human Feedback
  2. 2026On the Complexity of Preference-Based Bandits
  3. 2023Kernelized Offline Contextual Dueling Bandits
  4. 2026Linear and Neural Dueling Bandits with Delayed Feedback
  5. 2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback
  6. 2026Multi-User Dueling Bandits: A Fair Approach using Nash Social Welfare
  7. 2024Linear Contextual Bandits with Hybrid Payoff: Revisited
  8. 2023Reward Learning as Doubly Nonparametric Bandits: Optimal Design and Scaling Laws