arXiv cs.AI· Rohan Deb, Aadirupa Saha, Udaya Ghai, Karan Singh, Arindam Banerjee·· 2 天前AI 评分12
可复现的对决赌博机（Replicable Dueling Bandits）
Replicable Dueling Bandits
AI 导读
研究提出可复现对决赌博机问题：共享内部随机性、比较结果独立时，两次执行需以至少 1-ρ 概率每轮选出同一有序臂对。基于 Beat-the-Mean，作者设计了首批具次线性遗憾的算法：松弛随机传递性下遗憾为 Õ(γ⁸K⁴H_p/ρ²)，强随机传递性下基于同步消除改进至 Õ(K²H_p/ρ²)，线性对决赌博机下为 Õ(d³√T/(c_μρ))。合成与语言模型偏好实验验证了可复现性与次线性遗憾。
正文 · 原文
Abstract:Dueling bandits choose each comparison based on earlier noisy outcomes, so two runs on the same preferences can compare different pairs. We study replicable dueling bandits, where two executions with shared internal randomness and independent comparison outcomes must select the same ordered pair in every round with probability at least $1-\rho$. Building on Beat-the-Mean, whose scores change as arms are eliminated and need not rank the best arm highest, we design the first such algorithms with sublinear regret. Under relaxed stochastic transitivity with parameter $\gamma\ge 1$ and the stochastic triangle inequality, we design an algorithm that achieves expected regret $\widetilde{O}(\gamma^8 K^4 H_{\mathrm{p}}/\rho^2)$, where $H_{\mathrm{p}}=\sum_{i=2}^{K}(P_{1i}-1/2)^{-1}$. Under strong stochastic transitivity, we design an algorithm based on simultaneous elimination that improves the dependence on $K$ and achieves $\widetilde{O}(K^2 H_{\mathrm{p}}/\rho^2)$ regret. For linear dueling bandits, we design an algorithm that achieves regret $\widetilde{O}(d^3\sqrt{T}/(c_\mu\rho))$. Experiments on synthetic and language-model preferences show replicability, with sublinear regret.
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2610.20908 [cs.LG] |
| (or arXiv:2610.20908v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.20908 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Rohan Deb [view email]
[v1]
Wed, 14 Oct 2026 20:36:18 UTC (195 KB)
来源：arXiv cs.AI · arxiv.org