Metraipolis › archive › dc_4dcaaf7ff233

Saturation-Insensitive Dueling Bandits with General Function Approximation — arXiv:2609.33011

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.33011
License (as archived): CC0-1.0
Archived: 2026-10-07T22:37:04.936Z
SHA-256 of the archived text: 2829984afe5e3c8749018e6a42e577d43eac0548d4f71c17ce5faa93b6f32070
Stable URL of this page: https://metraipolis.com/documento/dc_4dcaaf7ff233

How to cite

Saturation-Insensitive Dueling Bandits with General Function Approximation — arXiv:2609.33011 — arXiv (en), https://arxiv.org/abs/2609.33011 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4dcaaf7ff233 (Metraipolis archive dc_4dcaaf7ff233, sha256 2829984afe5e3c8749018e6a42e577d43eac0548d4f71c17ce5faa93b6f32070)

BibTeX

@misc{dc4dcaaf7ff233,
  title = {Saturation-Insensitive Dueling Bandits with General Function Approximation — arXiv:2609.33011},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.33011},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4dcaaf7ff233; sha256 2829984afe5e3c8749018e6a42e577d43eac0548d4f71c17ce5faa93b6f32070},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.33011. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 / \sigma'[\Delta_{r^\ast}]$ which can be prohibitively large when the link function $\sigma$ saturates for large reward gaps $\Delta_{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/\sigma'(\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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-29 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.33011 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T22:14:27.838Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).