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_μρ))。合成与语言模型偏好实验验证了可复现性与次线性遗憾。
正文 · AI 翻译
摘要：对决赌博机根据先前带有噪声的结果来选择每次比较，因此基于相同偏好的两次运行可能会比较不同的臂对。我们研究可复现的对决赌博机，其中两次执行共享内部随机性且比较结果相互独立，必须在每一轮以至少 $1-\rho$ 的概率选择相同的有序臂对。基于 Beat-the-Mean（其得分会随着臂被淘汰而变化，且不一定会将最佳臂排在最高位），我们设计了首个具有次线性遗憾的此类算法。在参数为 $\gamma\ge 1$ 的松弛随机传递性和随机三角不等式下，我们设计了一种算法，其期望遗憾为 $\widetilde{O}(\gamma^8 K^4 H_{\mathrm{p}}/\rho^2)$，其中 $H_{\mathrm{p}}=\sum_{i=2}^{K}(P_{1i}-1/2)^{-1}$。在强随机传递性下，我们设计了一种基于同时淘汰的算法，改进了对 $K$ 的依赖，并达到 $\widetilde{O}(K^2 H_{\mathrm{p}}/\rho^2)$ 的遗憾。对于线性对决赌博机，我们设计了一种算法，其遗憾为 $\widetilde{O}(d^3\sqrt{T}/(c_\mu\rho))$。在合成偏好和语言模型偏好上的实验表明其具有可复现性，且遗憾为次线性。
| 主题： | 机器学习（cs.LG）；人工智能（cs.AI） |
| 引用为： | arXiv:2610.20908 [cs.LG] |
| （或 arXiv:2610.20908v1 [cs.LG] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2610.20908 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Rohan Deb [查看电子邮件]
[v1]
2026年10月14日星期三 20:36:18 UTC（195 KB）
来源：arXiv cs.AI · arxiv.org