Saturation-insensitive method improves learning in preference comparisons
Saturation-Insensitive Dueling Bandits with General Function Approximation
Machine Learning
Summary
Sometimes computers learn which choices are better by comparing pairs and seeing which one is preferred. But when they become very sure about which option is better, the feedback becomes less helpful for learning more. The authors propose a new method that avoids this problem by carefully picking which choices to compare, helping the computer learn more efficiently. Their approach works with many types of models and improves learning without getting stuck by this issue.
What this means in practice
- •For online recommendation teams: Improve recommendation quality by better identifying user preferences through more effective pairwise comparisons even with strong initial confidence.
- •For automated a/b testing developers: Design more efficient experiments that avoid wasting comparisons when preference signals are saturated, improving product feature evaluation.
Authors
Chenggong Zhang, Xuheng Li, Qiwei Di, Weitong Zhang, Quanquan Gu
Abstract
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 / σ'[Δ_{r^\ast}]$ which can be prohibitively large when the link function $σ$ saturates for large reward gaps $Δ_{r^\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/σ'(\cdot)$ 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.