贝叶斯优化
第六部分：研究前沿
EN

理论：从对决赌博机到核化偏好优化

找到最优选项需要多少次比较？一次比较提供的信息能否与一个数值相当？第 21 章介绍了对决的理论及其核化界；本章完整报告这一理论，给出每个结果的假设，并指出证明止于何处。相关理论分为四层：有限臂对决赌博机、线性与情境对决赌博机、连续凸对决优化、核化偏好赌博机。只有最后一层对应偏好贝叶斯优化本身，其结果也出现得最晚。

截至 2026 年 9 月的研究现状可以概括为三句话。一个分批算法的核化上界已与阶最优的标量贝叶斯优化同阶，但任何核化偏好问题都还没有下界。实践中使用的流程，即 Laplace 近似加 EUBO，只具有一步贝叶斯最优性与有限定义域上的一致性。可识别性与聚合理论则表明，当人与人之间存在差异，或回答依赖于隐藏情境时，成对数据是最弱的反馈形式。

注本章使用的记号
  • TT：轮数（查询次数）。KK：有限问题中臂（选项）的数目。dd：输入或特征的维度。
  • γT\gamma_T：核函数在 TT 次观测后的最大信息增益（定义 13.3、表 13.1）。
  • BB：效用在核函数的再生核 Hilbert 空间（reproducing kernel Hilbert space，RKHS）中的范数上界，衡量函数相对于核函数的粗糙程度（第 13.4.4 节、第 10.2 节）。
  • κ\kappa：链接函数在相关效用范围内最小斜率的倒数（第 29.5 节）。
  • O~\tilde O：忽略对数因子的增长阶。Ω\Omega：阶的下界。
  • 两种遗憾单位。效用遗憾累加 f(x⋆)−f(xt)f(\vx^\star) - f(\vx_t)。偏好概率遗憾累加 P(x⋆≻xt)−1/2\Prob(\vx^\star \succ \vx_t) - 1/2，并对一次查询的两个点取平均；两者为何不能互换，见第 21.4.2 节。

29.1 有限臂与线性对决赌博机 #

2017 年以前。第 21.2 节中的有限臂结果是这一理论的基石。Interleaved Filter 的期望遗憾为 O(Klog⁡T/Δmin⁡)O(K \log T / \Delta_{\min})，在强随机传递性与随机三角不等式下与其下界相匹配（Yue 等，2012）；RMED 达到了一个渐近下界，该下界用 Bernoulli 分布之间的 Kullback-Leibler 散度（第 6.2 节）表示（Komiyama 等，2015）。对决赌博机梯度下降在连续凸空间上的期望遗憾为 T3/4T^{3/4} 阶（Yue 与 Joachims，2009）；情境对决赌博机引入了 von Neumann 赢家（von Neumann winner），即选项上的一种随机选择，它以至少二分之一的概率胜过任何单个选项（Dudík 等，2015）。

2017 年及以后。González 等人的论文（González 等，2017）既没有遗憾定理，也没有收敛定理（第 26.2 节）。SelfSparring（Sui 等，2017b）假设“近似线性”（approximate linearity），即获胜概率是效用差的近似线性函数；作者称这一要求比强随机传递性更严格。其定理 1 证明独立臂版本收敛到最优臂，定理 2 给出渐近最优的无遗憾速率 O(Kln⁡(T)/Δ)O(K \ln(T)/\Delta)。核化多对决尚无分析；2018 年一篇综述称高斯过程先验能把样本复杂度从 O(K)O(K) 降到 O(d)O(d)（Sui 等，2018a），但这只是猜想（第 21.4.2 节）。Winner Stays（Chen 与 Frazier，2017）的弱遗憾（weak regret）为 O(N2)O(N^2)，与 TT 无关，其中 NN 为臂数；按弱遗憾的定义，只要所展示的两个选项中有一个是最优选项，这一轮就记为零代价。Bengs 等人（2021）的综述按各结果对成对获胜概率矩阵所作的假设，整理了遗憾结果与可能近似正确（probably approximately correct，PAC）样本复杂度结果。后来，Saha 与 Gaillard（2022）首先在以 Condorcet 赢家为基准时达到了最优的 O(∑ilog⁡T/Δi)O(\sum_i \log T / \Delta_i)。

连续凸对决。Kumagai（2017）在代价函数强凸且光滑时，用随机镜像下降得到 O(Tlog⁡T)O(\sqrt{T \log T}) 的遗憾，并借助凸优化中的下界论证该结果在对数因子以内最优；摘要没有说明对链接函数的假设。Saha 等人（2021b）给出了每对选项只产生一个带噪声比较比特时的查询复杂度，并证明了非平稳在线凸情形下的不可能性；他们 2025 年的论文处理了一般的转移函数（Saha 等，2025）。Blum 等人（2024）在单调对手下证明了 Ω(d)\Omega(d) 的下界。

线性与情境对决。在 Saha（2021）的设定中，每轮提供 KK 个带情境特征的项目，学习者从中选出大小为 qq 的子集，并观察到一个带噪声的赢家。他们给出了最优的 O~(dT)\tilde O(\sqrt{dT}) 算法与相匹配的 Ω(dT)\Omega(\sqrt{dT}) 下界，且该下界与子集大小 qq 无关：来自更大子集的赢家反馈并无帮助。随后出现了高效算法与一般链接函数的结果（Saha 与 Krishnamurthy，2022；Bengs 等，2022；Di 等，2024），Feel-Good Thompson 采样达到了接近极小极大的 O~(dT)\tilde O(d\sqrt{T})（Li 等，2024b）。Borda 遗憾（Borda regret）以一个选项对其他所有选项的平均获胜概率来衡量该选项；Wu 等人（2024）对 Borda 遗憾证明了 Ω(d2/3T2/3)\Omega(d^{2/3} T^{2/3}) 的下界与相匹配的上界。Di 等人（2025）在有 CC 个标签被对手翻转时得到 O~(κdT+κdC)\tilde O(\kappa d\sqrt{T} + \kappa dC)（该文用 κ\kappa 表示链接函数的最小斜率，即本书所用之量的倒数，因此原文的界是除以这个量），并给出几乎匹配的下界；对 sigmoid 链接，他们把 κ\kappa 从主项中去掉了。Sekhari 等人（2023）则证明，仅用比较查询即可达到与观察奖励的标准情境赌博机相当的遗憾。Saha 的 dT\sqrt{dT} 与 Feel-Good Thompson 采样的 dTd\sqrt{T} 之间的差别来自臂集合不同（前者每轮 KK 个项目，后者为大的或连续的集合），两者并不矛盾（推断）。

基于偏好的强化学习。在从轨迹偏好中学习策略的问题上（第 36.1 节），已有结果从渐近的贝叶斯无遗憾（Novoseller 等，2020）与第一个有限时间分析（Xu 等，2020a），发展到一般函数逼近（Chen 等，2022）与第一个贝叶斯简单遗憾保证（Agnihotri 等，2026）。Zhu 等人（2023）证明，在 Plackett-Luce 模型下，完整的 KK 元最大似然估计量与把排序拆成成对比较的估计量都收敛，前者渐近地更有效。

第 29.1 节引用的文献 27
  1. Yue 等人（2012）The K-armed Dueling Bandits Problem
  2. Komiyama 等人（2015）Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem
  3. Yue 与 Joachims（2009）Interactively optimizing information retrieval systems as a dueling bandits problem
  4. Dudík 等人（2015）Contextual Dueling Bandits
  5. González 等人（2017）Preferential Bayesian Optimization
  6. Sui 等人（2017b）Multi-dueling Bandits with Dependent Arms
  7. Sui 等人（2018a）Advancements in Dueling Bandits
  8. Chen 与 Frazier（2017）Dueling Bandits with Weak Regret
  9. Bengs 等人（2021）Preference-based Online Learning with Dueling Bandits: A Survey
  10. Saha 与 Gaillard（2022）Versatile Dueling Bandits: Best-of-both World Analyses for Learning from Relative Preferences
  11. Kumagai（2017）Regret Analysis for Continuous Dueling Bandit
  12. Saha 等人（2021b）Dueling Convex Optimization
  13. Saha 等人（2025）Dueling Convex Optimization with General Preferences
  14. Blum 等人（2024）Dueling Optimization with a Monotone Adversary
  15. Saha（2021）Optimal Algorithms for Stochastic Contextual Preference Bandits
  16. Saha 与 Krishnamurthy（2022）Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability
  17. Bengs 等人（2022）Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Models
  18. Di 等人（2024）Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits
  19. Li 等人（2024b）Feel-Good Thompson Sampling for Contextual Dueling Bandits
  20. Wu 等人（2024）Borda Regret Minimization for Generalized Linear Dueling Bandits
  21. Di 等人（2025）Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback
  22. Sekhari 等人（2023）Contextual Bandits and Imitation Learning with Preference-Based Active Queries
  23. Novoseller 等人（2020）Dueling Posterior Sampling for Preference-Based Reinforcement Learning
  24. Xu 等人（2020a）Preference-based Reinforcement Learning with Finite-Time Guarantees
  25. Chen 等人（2022）Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation
  26. Agnihotri 等人（2026）Best Policy Learning From Trajectory Preference Feedback
  27. Zhu 等人（2023）Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons

29.2 第一个核化结果 #

2021 年以前已有一个基于核函数的结果。Xu 等人（2020b）同时允许直接查询与对决，其 COMP-GP-UCB 在 TT 次直接查询后的简单遗憾为 O(Φ/T)O(\Phi/\sqrt{T})；其中 Φ\Phi 是在定义域的一部分上计算的信息增益，这一部分是经过比较之后仍可能包含最优点的候选区域。第一个关于累积遗憾的核化对决界由 Kirschner 与 Krause（2021）给出（第 21.3.1 节），其适用范围取决于所依赖的假设：

  1. 反馈。论文的式 2 是定量的对决反馈，dt=f(xt1)−f(xt2)+ξtd_t = f(\vx_t^1) - f(\vx_t^2) + \xi_t，其中 ξt\xi_t 是方差代理为 ρ2\rho^2 的次高斯噪声。该模型只在有界噪声属于次高斯噪声的意义上涵盖二元反馈。
  2. 函数类。ff 属于已知的 RKHS，范数至多为 BB，且 k(x,x)≤1k(\vx, \vx) \le 1。
  3. 遗憾。每次对决中两个点的效用差距之和。
  4. 定理 1。遗憾为 O(T βT,δ (γT+log⁡1/δ))O\big(\sqrt{T\, \beta_{T,\delta}\,(\gamma_T + \log 1/\delta)}\big)，对 TT 轮（论文中记作 nn）约为 γTT\gamma_T\sqrt{T}。
  5. 定理 2。在最优点唯一的有限定义域上，遗憾为 O(Δmin⁡−1β(γT+log⁡(T/δ)))O\big(\Delta_{\min}^{-1}\beta(\gamma_T + \log(T/\delta))\big)；对线性核为 O(Δmin⁡−1d2log⁡(T)2)O(\Delta_{\min}^{-1} d^2 \log(T)^2)，对径向基函数（平方指数）核为 O(Δmin⁡−1log⁡(T)2d+2)O(\Delta_{\min}^{-1} \log(T)^{2d+2})。

这一结果不涵盖 Bradley-Terry 链接或概率单位链接下的 Bernoulli 结果，也不涵盖这类链接带来的代价 κ\kappa；Bradley-Terry 链接下的核化遗憾分析始于 2024 年的 POP-BO（推断，依据定理所陈述的反馈模型）。

第 29.2 节引用的文献 2
  1. Xu 等人（2020b）Zeroth Order Non-convex optimization with Dueling-Choice Bandits
  2. Kirschner 与 Krause（2021）Bias-Robust Bayesian Optimization via Dueling Bandits

29.3 Bradley-Terry 界，2024 至 2026 年 #

有四个算法的分析针对偏好贝叶斯优化实际面临的设定：回答服从 Bernoulli 分布，其概率是效用差的逻辑函数（第 16.4 节），效用属于某个 RKHS。第 21.3.2 节已介绍过这些算法；本节给出定理本身，以及其中的常数与条件。

POP-BO。Xu 等人（2024b）假设定义域紧致，ff 属于某个 RKHS，反馈为 Bernoulli 反馈，P=sigmoid⁡(f(x)−f(x′))\Prob = \operatorname{sigmoid}(f(\vx) - f(\vx'))，即式（16.4）的逻辑函数。算法在似然比置信集内乐观地选择，并以上一轮的点为参照点。

  • 定理 5.2。效用遗憾 RT=O(βTγTT)R_T = O\big(\sqrt{\beta_T \gamma_T T}\big)，其中 βT=O(Tlog⁡(T N(Bf,1/T,∥⋅∥∞)/δ))\beta_T = O\big(\sqrt{T \log(T\, \mathcal{N}(\mathcal{B}_f, 1/T, \lVert\cdot\rVert_\infty)/\delta)}\big)，N\mathcal{N} 是函数类的覆盖数，即覆盖该函数类所需的小球个数。对线性核与径向基函数核，由此得到 T3/4T^{3/4} 乘以多对数因子（其定理 5.5）。对 Matérn 核，指数大于 3/43/4，且论文只在 ν>(d/4)(3+d+d2+14d+17)\nu > (d/4)\big(3 + d + \sqrt{d^2 + 14d + 17}\big) 时给出该界，即光滑度参数 ν\nu 须达到 d2d^2 的量级。
  • 定理 5.4。所报告解的差距为 O(βTγT/T)O\big(\sqrt{\beta_T \gamma_T}/\sqrt{T}\big)。
  • 注 5.6。作者提出，偏好反馈大约要多付出一个 T1/4T^{1/4} 因子，依据的直觉是：数值评估蕴含偏好，反之则不然。

后来的论文常把 POP-BO 的速率简写为 O~((γTT)3/4)\tilde O((\gamma_T T)^{3/4})；引用时应注明其单位是效用遗憾。

MaxMinLCB。Pásztor 等人（2024）把选择一对选项的问题表述为 Stackelberg 博弈（Stackelberg game），即一方先作出承诺、另一方随后应对的博弈，并为核化逻辑估计量构造了偏好置信序列。定理 6：以至少 1−δ1 - \delta 的概率，对所有 TT 有

RT≤C3 βTTγT=O(γTT),R_T \le C_3\, \beta_T \sqrt{T \gamma_T} = O(\gamma_T \sqrt{T}),
(29.1)

其中 βt=4LB+2L(2κ/λ)(γt+log⁡1/δ)\beta_t = 4LB + 2L\sqrt{(2\kappa/\lambda)(\gamma_t + \log 1/\delta)}，κ=sup⁡∣a∣≤B1/sigmoid⁡′(a)\kappa = \sup_{\lvert a\rvert \le B} 1/\operatorname{sigmoid}'(a)，C3=(8+2κ)/log⁡(1+4/(λκ))C_3 = (8 + 2\kappa)/\sqrt{\log(1 + 4/(\lambda\kappa))}；ss 是链接函数，LL 是其 Lipschitz 常数（斜率的上界），λ\lambda 是正则化参数。这里的遗憾是偏好概率遗憾；摘要中的“速率最优”（rate-optimal）至多在相对于 GP-UCB 类分析的意义上成立（推断；第 21.3.2 节）。Kayal 等人（2025）将其概括为 O~(γTκ2T)\tilde O(\gamma_T \kappa^2 \sqrt{T})。

MR-LPF。Kayal 等人（2025）的多轮偏好反馈学习算法假设：ff 属于已知核函数的 RKHS，范数至多为 BB；核函数以 1 为界；只采用 Bradley-Terry（逻辑）链接；候选集 X\X 有限。算法运行 R≤⌈log⁡2log⁡2T⌉+1R \le \lceil \log_2 \log_2 T\rceil + 1 轮，各轮长度为 N1=TN_1 = \sqrt{T} 与 Nr=Nr−1TN_r = \sqrt{N_{r-1} T}；每轮之内按最大核方差选择点对，每轮结束时，凡是对某个对手获胜概率的上置信界低于二分之一的点，都予以淘汰。

  • 定理 4.1。存在一个与 TT 无关的常数 T0T_0（见其附录 B），使得对所有 T≥T0T \ge T_0，以至少 1−δ1 - \delta 的概率有 RT≤2CR β(R)(δ)γ4λ(T) (T+1)R_T \le 2CR\, \beta_{(R)}(\delta) \sqrt{\gamma_{4\lambda}(T)}\,(\sqrt{T} + 1)，其中 β(r)(δ)=L(B+(κr/λ)log⁡(2R∣X∣/δ))\beta_{(r)}(\delta) = L\big(B + \sqrt{(\kappa_r/\lambda)\log(2R|\X|/\delta)}\big)，∣X∣|\X| 是候选集 X\X 的大小（论文中记作 NXN_\X），κ1=κ\kappa_1 = \kappa，当 r>1r > 1 时 κr=6\kappa_r = 6。简化后为 O~(γTTlog⁡(∣X∣/δ))\tilde O\big(\sqrt{\gamma_T T \log(|\X|/\delta)}\big)。
  • κ\kappa 的去向。它只在第一轮出现，因而不进入主项。论文指出，效用取值于 [−5,5][-5, 5] 时，κ\kappa 可以超过 22,000。
  • 推论 4.5。找到满足 P(x⋆≻x^)−1/2≤ε\Prob(\vx^\star \succ \hat\vx) - 1/2 \le \varepsilon 的解所需的比较次数，对线性核为 O~(dlog⁡(1/δ)/ε2)\tilde O(d \log(1/\delta)/\varepsilon^2)，对径向基函数核为 O~(log⁡(1/δ)/ε2)\tilde O(\log(1/\delta)/\varepsilon^2)，对 Matérn 核为 O~(log⁡(1/δ)/ε2+d/ν)\tilde O\big(\log(1/\delta)/\varepsilon^{2 + d/\nu}\big)，与标量反馈下阶最优的样本复杂度同阶。
  • 紧性。作者指出，Scarlett 等人的下界假设高斯噪声，而 Bradley-Terry 对应 Gumbel 噪声，因此两者不能严格地形式比较；他们只把这一比较作为紧性的非正式论证，并论证偏好反馈的下界应至少为标量下界的一半。

凡称 MR-LPF“与标量贝叶斯优化相匹配”，都应同时说明它与标量设定的六处不同（常见的误读见第 21.4.2 节）：遗憾单位是偏好概率；T0T_0 是否隐含对 κ\kappa 或 eBe^B 的依赖，尚无人核查；log⁡∣X∣\log |\X| 来自联合界，连续定义域因此需要离散化论证；算法是分批的，在一轮之内不自适应；最优性来自非正式的比较；每次查询涉及两个点，两者都计入遗憾。一个由机器生成评审意见的网站声称，该文定理 4.7 所用的一个 Loewner 序不等式在 λ\lambda 较小时可能不成立（Pith，2026）；这一说法未经同行评审，也未得到人类来源的证实，而 PF-TS 的论文把 MR-LPF 的速率作为正确结果加以引用。

PF-TS。Lazzaro 等人（2026）分析了偏好反馈下的 Thompson 采样：抽取两个独立的后验样本，分别相对于一个共同的锚点求最大值，得到一次查询的两个点。定理 1：以至少 1−2δ1 - 2\delta 的概率，RT=O~(βTTγT)R_T = \tilde O\big(\beta_T\sqrt{T\gamma_T}\big)，其中 βT=O(γT+log⁡(1/δ))\beta_T = O\big(\sqrt{\gamma_T + \log(1/\delta)}\big)，即以偏好概率遗憾计为 O~(γTT)\tilde O(\gamma_T\sqrt{T})；κ\kappa 通过岭项 λκ\lambda\kappa 进入 βT\beta_T 与 γT\gamma_T。论文称这个界与 Chowdhury 与 Gopalan 2017 年为标准 Thompson 采样建立的界相匹配，而后者在标量贝叶斯优化中本身并非阶最优。连续定义域必须离散化为 (BGwdT2)d(B G w d T^2)^d 个点，核函数假定已知；实验对象是一维 Ackley 函数，以及一个包含三种金属 63 种组成的催化剂数据集。在 Ackley 函数上，PF-TS 的累积遗憾低于 MR-LPF 与 POP-BO（第 21.3.2 节），但到 300 轮的时域终点时，MR-LPF 的瞬时遗憾仍有竞争力；这两篇论文有共同作者（Vakili、Shiu）。

神经对决赌博机。Verma 等人（2025）对链接函数 μ\mu 假设 κμ=inf⁡μ′(f(x)−f(x′))>0\kappa_\mu = \inf \mu'(f(\vx) - f(\vx')) > 0；只要随机传递性成立，其结果就适用于 Bradley-Terry 噪声、Thurstone 噪声与指数噪声。平均效用遗憾为 O~((deff/κμ+Bλ/κμ)Tdeff)\tilde O\big((\sqrt{d_{\text{eff}}}/\kappa_\mu + B\sqrt{\lambda/\kappa_\mu})\sqrt{T d_{\text{eff}}}\big)，其中 deffd_{\text{eff}} 是由所有成对情境差构造的有效维度；网络宽度必须是 TT 等量的多项式。作者预计这个界弱于标量神经赌博机的界。Oh 等人（2026a）给出了 O~(d∑tσt2+dT)\tilde O\big(d\sqrt{\sum_t \sigma_t^2} + \sqrt{dT}\big)，并把宽度要求降到 Ω~(T6)\tilde\Omega(T^6)。

第 29.3 节引用的文献 7
  1. Xu 等人（2024b）Principled Preferential Bayesian Optimization
  2. Pásztor 等人（2024）Bandits with Preference Feedback: A Stackelberg Game Perspective
  3. Kayal 等人（2025）Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds
  4. Pith（2026）Machine-generated review of arXiv 2505.23673 (MR-LPF)
  5. Lazzaro 等人（2026）A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedback
  6. Verma 等人（2025）Neural Dueling Bandits: Preference-Based Optimization with Human Feedback
  7. Oh 等人（2026a）Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Exploration

29.4 速率比较 #

表 29.1 汇总了连续或核化偏好优化的主要结果，并列出标量贝叶斯优化的参照：GP-UCB 类与 GP-TS 类分析的 O∗(TγT)O^*(\sqrt{T}\gamma_T)（Chowdhury 与 Gopalan，2017）；分批纯探索（BPE）在 O(log⁡log⁡T)O(\log\log T) 批之内达到 O∗(TγT)O^*(\sqrt{T\gamma_T})，对若干种核函数接近最优（Li 与 Scarlett，2022）；对 Matérn 核，累积遗憾的下界 Ω(T(ν+d)/(2ν+d))\Omega(T^{(\nu + d)/(2\nu + d)}) 与简单遗憾样本复杂度的下界 Ω((1/ε)2+d/ν)\Omega((1/\varepsilon)^{2 + d/\nu})（Scarlett 等，2017）。这里的 O∗O^* 与 O~\tilde O 一样隐去对数因子。

表 29.1 连续与核化偏好优化的速率：反馈、遗憾单位、假设及对应的标量结果。
结果 反馈与链接函数 遗憾 主要假设 速率 主项中是否含 κ\kappa 对应的标量结果
SelfSparring（Sui 等，2017b） 多对决；近似线性链接 有限臂强遗憾 独立臂 渐近 O(Kln⁡T/Δ)O(K\ln T/\Delta)；核版本没有界 不适用 与有限臂赌博机渐近同阶
Kumagai（Kumagai，2017） 带噪声的比较；强凸光滑代价 对决遗憾 强凸、光滑 O(Tlog⁡T)O(\sqrt{T\log T}) 摘要未说明 在凸优化下界的意义上，于对数因子以内最优
Xu 等（Xu 等，2020b） 对决加直接查询 简单遗憾 RKHS O(Φ/T)O(\Phi/\sqrt{T}) 不适用 GP-UCB 类，信息增益在基于比较的约束集上计算
Kirschner 与 Krause（Kirschner 与 Krause，2021） 效用差加次高斯噪声（线性链接） 两个点效用差距之和 范数 ≤B\le B O(TβT(γT+log⁡1/δ))O(\sqrt{T\beta_T(\gamma_T + \log 1/\delta)})，约为 γTT\gamma_T\sqrt{T} 否 与 GP-UCB 形式相同
POP-BO（Xu 等，2024b） 逻辑 效用；参照点为上一个点 紧致定义域；Matérn 核要求 ν\nu 达到 d2d^2 量级 O(βTγTT)O(\sqrt{\beta_T\gamma_T T})，约为 T3/4T^{3/4} 乘以多对数因子 通过置信集 弱于 GP-UCB
MaxMinLCB（Pásztor 等，2024） 逻辑；一处脚注称分析可能推广到其他对称递增链接 偏好概率 范数 ≤B\le B O(γTT)O(\gamma_T\sqrt{T}) 是（约为 κ2\kappa^2） 与 GP-UCB 同阶
神经对决赌博机（Verma 等，2025） 一般链接 平均效用 网络宽度为多项式 O~((deff/κμ)Tdeff)\tilde O((\sqrt{d_{\text{eff}}}/\kappa_\mu)\sqrt{Td_{\text{eff}}}) 及其他项 是 作者预计弱于 NeuralUCB
MR-LPF（Kayal 等，2025） 逻辑 偏好概率 有限 X\X；T≥T0T \ge T_0；分批 $\tilde O(\sqrt{\gamma_T T\log \X })$
PF-TS（Lazzaro 等，2026） 逻辑 偏好概率 连续定义域需离散化；核函数已知 O~(γTT)\tilde O(\gamma_T\sqrt{T}) 通过 βT\beta_T 与 γT\gamma_T 与 GP-TS 同阶
qEUBO（Astudillo 等，2023） 逻辑或常数似然 贝叶斯简单遗憾 有限 X\X；q=2q = 2；差距条件或常数似然条件 o(1/n)o(1/n) 不适用 贝叶斯的有限定义域结果，不能与频率派速率相比较

偏好理论几乎逐项重现了标量贝叶斯优化的结果：乐观算法与 Thompson 采样达到 γTT\gamma_T\sqrt{T}，分批淘汰达到 γTT\sqrt{\gamma_T T}（推断；第 21.4 节）。完全序贯的偏好算法能否达到 γTT\sqrt{\gamma_T T}，仍是未解决的问题。标量设定中有一个相关问题，于 COLT 2021 提出（Vakili 等，2021b）：GP-UCB 本身能否达到这一速率。更精巧的标量算法已经达到（Salgia 等，2021）；Whitehouse 等人（2023）部分解决了这一问题，给出了 Matérn 核下 GP-UCB 的次线性界，在对数因子以内为 T(ν+2d)/(2ν+2d)T^{(\nu + 2d)/(2\nu + 2d)} 阶，仍高于下界；Matérn 核信息增益的改进速率来自 Vakili 等人（2021a），成立条件为 ν>1/2\nu > 1/2。两类算法相差的因子 γT\sqrt{\gamma_T} 有多重要，取决于 γT\gamma_T 增长的快慢，而后者又取决于核函数（表 13.1）；图 29.1 直观地展示了这一点。

一维上的界的形状，常数均取 1（示意）1101001k1101001000轮数 TγT √T：MaxMinLCB、PF-TST：不学习√(γT T)：MR-LPF差距 ×√γT = 6.5T = 1000 时的贪心 γT：42.6Ta 的指数 a 随维度 d 的变化（渐近，忽略对数因子）0.50.7511.251.512345678910维度 d高于 1：增长快于 TγT √T：MaxMinLCB、PF-TS√(γT T)：MR-LPF对 Matérn 核，√(γT T) 的指数等于标量下界的指数。POP-BO 的 Matérn 结果在 d = 1 时要求光滑度高于 2.41，维度越高要求越高；此核（光滑度 2.5）只在 d 不超过 1 时满足。
一维上的界的形状，常数取 1（示意）1101001k1101001000轮数 TT：不学习γT √T：MaxMinLCB、PF-TS√(γT T)：MR-LPF差距 ×√γT = 6.5T = 1000 时的贪心 γT：42.6Ta 的指数 a 与维度 d（渐近）0.50.7511.251.513579维度 d高于 1：增长快于 TγT √T：MaxMinLCB、PF-TS√(γT T)：MR-LPF对 Matérn 核，√(γT T) 的指数等于标量下界的指数。POP-BO的 Matérn 结果在 d = 1 时要求光滑度高于 2.41，维度越高要求越高；此核（光滑度 2.5）只在 d 不超过 1 时满足。
图 29.1 核化速率并列比较，即第 21.4 节中的图。上图：一维定义域上各个界的形状，其中 γT\gamma_T 由第 13.4.2 节的贪心规则在 300 个输入的网格上计算，正则化为 0.25，所有常数与链接因子 κ\kappa 均取 1；曲线高度仅作示意，各界单位也不同，只有增长趋势可以比较。虚线 TT 表示从不改进的学习者的增长。下图：TaT^a 中的指数 aa 随维度的变化，由我们根据已发表的 γT\gamma_T 阶（表 13.1）算出，忽略对数因子；该阶的成立条件是 ν>1/2\nu > 1/2（Vakili 等，2021a），选择 Matérn 1/2 时是在边界上套用同一公式。

可以尝试以下几点：

  • 默认设置（Matérn 5/2，T=1000T = 1000）。右侧的括号标出 γTT\gamma_T\sqrt{T} 与 γTT\sqrt{\gamma_T T} 之间相差的因子 γT\sqrt{\gamma_T}。所有常数取 1 时，在这一时域内 γTT\gamma_T\sqrt{T} 仍高于直线 TT，而 γTT\sqrt{\gamma_T T} 远低于它：即使不计常数，多出的 γT\sqrt{\gamma_T} 也决定了一个界是否具有实际意义。
  • 切换到平方指数核。γT\gamma_T 按 log⁡T\log T 的幂增长，两类算法在渐近意义上只差多对数因子；POP-BO 的 T3/4T^{3/4} 也随之出现。渐近地看，它是三者中增长最快的，但在图示的时域内，它低于 γTT\gamma_T\sqrt{T}，接近 γTT\sqrt{\gamma_T T}：增长的阶与实际时域内的大小可能并不一致。
  • 切换到 Matérn 1/2，并加大长度尺度。核函数粗糙时，γT\gamma_T 在一维中的增长几乎与 T\sqrt{T} 相当，因此 γTT\gamma_T\sqrt{T} 的指数在 d=1d = 1 时已经为 1。加大长度尺度会在固定时域内降低 γT\gamma_T，但不改变指数。
  • 选 Matérn 5/2 查看下图。γTT\gamma_T\sqrt{T} 的指数为 1/2+d/(5+d)1/2 + d/(5 + d)，在 d=5d = 5 时达到 1；γTT\sqrt{\gamma_T T} 的指数为 (2.5+d)/(5+d)(2.5 + d)/(5 + d)，在所有维度上都低于 1（习题 21.3）。POP-BO 的 Matérn 结果即使在 d=1d = 1 时也要求 ν>2.41\nu > 2.41，因此对 Matérn 5/2 只适用于一维。
第 29.4 节引用的文献 17
  1. Chowdhury 与 Gopalan（2017）On Kernelized Multi-armed Bandits
  2. Li 与 Scarlett（2022）Gaussian Process Bandit Optimization with Few Batches
  3. Scarlett 等人（2017）Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
  4. Sui 等人（2017b）Multi-dueling Bandits with Dependent Arms
  5. Kumagai（2017）Regret Analysis for Continuous Dueling Bandit
  6. Xu 等人（2020b）Zeroth Order Non-convex optimization with Dueling-Choice Bandits
  7. Kirschner 与 Krause（2021）Bias-Robust Bayesian Optimization via Dueling Bandits
  8. Xu 等人（2024b）Principled Preferential Bayesian Optimization
  9. Pásztor 等人（2024）Bandits with Preference Feedback: A Stackelberg Game Perspective
  10. Verma 等人（2025）Neural Dueling Bandits: Preference-Based Optimization with Human Feedback
  11. Kayal 等人（2025）Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds
  12. Lazzaro 等人（2026）A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedback
  13. Astudillo 等人（2023）qEUBO: A Decision-Theoretic Acquisition Function for Preferential Bayesian Optimization
  14. Vakili 等人（2021b）Open Problem: Tight Online Confidence Intervals for RKHS Elements
  15. Salgia 等人（2021）A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance
  16. Whitehouse 等人（2023）On the Sublinear Regret of GP-UCB
  17. Vakili 等人（2021a）On Information Gain and Regret Bounds in Gaussian Process Bandits

常数 κ\kappa 是链接函数在分析所允许的效用差范围内最小斜率的倒数。对逻辑链接，它随这一范围指数增长，因为逻辑曲线在远离零处几乎是平的：MR-LPF 的作者指出，效用取值于 [−5,5][-5, 5] 时，它可以超过 22,000（习题 21.4）。第 21.4.1 节介绍了标量逻辑赌博机如何把 κ\kappa 移出主项（Faury 等，2020；Abeille 等，2021）；第 21.4.2 节说明了效用遗憾与偏好概率遗憾为何只在差距较小时成比例，比例因子为 1/41/4（习题 29.2）。这里补充两点。其一，在对决问题中，Di 等人（2025）（针对 sigmoid 链接）与 MR-LPF（针对核函数）把 κ\kappa 从主项中去掉了，而 MaxMinLCB、PF-TS 与神经对决赌博机仍把它保留在主项的常数中；除神经方法的 κμ\kappa_\mu 外，没有任何核化结果针对一般的非逻辑链接给出显式的斜率依赖，MaxMinLCB 也只在一处脚注中提到其分析可能推广到其他对称递增的链接。其二，POP-BO 在 2024 年提出的直觉，即偏好要多付出 T1/4T^{1/4} 的因子，在上界层面已被 MR-LPF 否定：这一差距来自 POP-BO 基于覆盖数的置信宽度，而非偏好反馈本身（推断）。

第 29.5 节引用的文献 3
  1. Faury 等人（2020）Improved Optimistic Algorithms for Logistic Bandits
  2. Abeille 等人（2021）Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits
  3. Di 等人（2025）Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback

29.6 决策论结果 #

qEUBO（Astudillo 等，2023）是偏好贝叶斯优化中主要的贝叶斯决策论结果。查询 X=(x1,…,xq)X = (\vx_1, \dots, \vx_q) 的一步贝叶斯最优值（one-step Bayes optimal value）为 Vn(X)=En[max⁡xEn+1[f(x)]−max⁡xEn[f(x)]∣Xn+1=X]V_n(X) = \E_n\big[\max_{\vx} \E_{n+1}[f(\vx)] - \max_{\vx}\E_n[f(\vx)] \mid X_{n+1} = X\big]，即对 XX 再获得一个回答，预期能使最好的后验均值提高多少；停止于 NN 时，推荐点为 arg max⁡xEN[f(x)]\argmax_{\vx} \E_N[f(\vx)]；带噪声的似然为 Li(f(X);λ)=exp⁡(f(xi)/λ)/∑jexp⁡(f(xj)/λ)L_i(f(X); \lambda) = \exp(f(\vx_i)/\lambda) / \sum_j \exp(f(\vx_j)/\lambda)，λ=0\lambda = 0 表示回答无噪声。四个定理及其条件见第 28.2 节。对这些定理有三点解读（推断）：

  • o(1/n)o(1/n) 为何这么快。这些条件把问题变成了几乎必然存在正效用差距的有限识别问题。这一结果不涉及连续定义域，也没有说明速率如何依赖于选项数或维度，并且不能与 T−1/2T^{-1/2} 阶的频率派简单遗憾相比较。
  • 充分条件排除了什么。几乎必然成立的差距界排除了边际分布连续的普通高斯过程先验；而效用不同时获胜概率恒等于常数 a>1/2a > 1/2 的似然，也不是实践中使用的概率单位似然或逻辑似然。这一结果最好理解为 qEUBO 具有一致性的证据与 qEI 不具一致性的证明，而不是实际偏好贝叶斯优化的速率。
  • 与 2026 年的批评并不矛盾。一步最优性不蕴含多步最优性或渐近最优性，因此与两篇预印本报告的过度利用和病态问题并不冲突（第 28.4 节）；在连续定义域上，qEUBO 既没有这类结果，也没有频率派遗憾界。
要点理论分析的算法并非实践中的流程

理论论文分析的是建立在频率派核估计量之上的淘汰算法、乐观算法或 Thompson 采样算法。实践中使用的则是 Laplace 近似下的高斯过程后验加 EUBO 类采集函数，这一流程只具有一步贝叶斯最优性与有限定义域上的一致性。没有论文分析过这一实践流程的频率派遗憾，我们也没有找到连续定义域上高斯过程偏好采集的贝叶斯遗憾界（例如基于信息比的界）（推断）。需要理论保证的实践者必须运行经过分析的算法；使用默认设置时，应当把理论理解为对问题本身的陈述，而不是对所用方法的陈述。

第 29.6 节引用的文献 1
  1. Astudillo 等人（2023）qEUBO: A Decision-Theoretic Acquisition Function for Preferential Bayesian Optimization

29.7 下界 #

下界刻画的是：对一类问题，任何算法都必须在其中某个问题上承受多少遗憾（第 13.3 节）。没有下界，就不能称一个上界是最优的。

已确立阶最优性的情形。对有限臂对决赌博机，Saha 与 Gaillard（2022）达到了实例相关的 ∑ilog⁡T/Δi\sum_i \log T/\Delta_i，RMED 则渐近地达到这一下界（Komiyama 等，2015）。对抗、分批与弱遗憾等变体，以及 Condorcet 赢家与 Copeland 赢家的识别，也都有下界（Saha 等，2021a；Saha 与 Gaillard，2021；Agarwal 等，2022；Saad 等，2024；Haddenhorst 等，2021a；Bengs 等，2024）；线性与情境情形则有第 29.1 节中的 Ω(dT)\Omega(\sqrt{dT}) 下界、Borda 下界与污染下界。

一次查询携带多少信息。第 20.1.2 节报告了 Plackett-Luce 模型下有限臂情形的答案：对 nn 条臂，来自 kk 元子集的赢家反馈的最优样本复杂度为 O((n/ε2)ln⁡(1/δ))O((n/\varepsilon^2)\ln(1/\delta))，与成对比较相同，而 top-mm 排序反馈能使之降为原来的 mm 分之一（Saha 与 Gopalan，2019b）。同一批作者还给出了相匹配的实例相关界（Saha 与 Gopalan，2020），以及 top-mm 反馈下 O((n/m)ln⁡T)O((n/m)\ln T)、完整排序下 O((n/k)ln⁡T)O((n/k)\ln T) 的阶最优遗憾（Saha 与 Gopalan，2019a）。在符号反馈的凸优化中，mm 路 argmin 反馈带来的增益为 min⁡{log⁡m,d}\min\{\log m, d\} 阶（Saha 等，2024）；对线性 Plackett-Luce 模型，Lee 等人（2025a）得到 O~((d/T)∑t1/∣St∣)\tilde O\big((d/T)\sqrt{\sum_t 1/\lvert S_t\rvert}\big)，其中 StS_t 是第 tt 轮展示的子集，由此可以证明更大的子集有帮助；而如果反馈只按过去的经验表现给臂排序，就不可能得到对数阶的实例相关遗憾（Maran 等，2024）。“来自更大子集的赢家反馈没有帮助”与“更大的子集有帮助”看似矛盾，区别在于反馈类型：每轮要获得更多信息，反馈就不能只有赢家。对偏好贝叶斯优化而言，这预示着：请人“从 KK 个中选一个”的界面，在最坏情况的阶上并不优于成对对决，而排序界面可以更好；这一预测在核化偏好贝叶斯优化中尚未检验（推断）。

核化情形：没有下界。在我们的检索范围内（PMLR 2017 至 2025 年、NeurIPS 2017 至 2024 年，以及对 2025 与 2026 年文献的浏览），我们没有找到 Bradley-Terry 链接或概率单位链接下核化偏好反馈的与算法无关的下界；有针对性的检索只找到了标量核函数下界与有限臂对决下界。MR-LPF 的近似最优性依赖于与 Scarlett 等人高斯噪声下界的非正式比较。任何偏好下界都须与标量核函数下界（Scarlett 等，2017；Cai 与 Scarlett，2021）以及 Iwazaki 与 Takeno（2025）的时变核函数下界相比较。第 21.5 节列出了缺失的三类下界，并讨论了这一缺失对“比较是否比数值更昂贵”这一问题意味着什么；在核函数情形中，唯一确定的结论是：在带预热期的分批、有限定义域设定中，比较至多多付出常数因子与对数因子（推断）。

第 29.7 节引用的文献 17
  1. Saha 与 Gaillard（2022）Versatile Dueling Bandits: Best-of-both World Analyses for Learning from Relative Preferences
  2. Komiyama 等人（2015）Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem
  3. Saha 等人（2021a）Adversarial Dueling Bandits
  4. Saha 与 Gaillard（2021）Dueling Bandits with Adversarial Sleeping
  5. Agarwal 等人（2022）Batched Dueling Bandits
  6. Saad 等人（2024）On Weak Regret Analysis for Dueling Bandits
  7. Haddenhorst 等人（2021a）Identification of the Generalized Condorcet Winner in Multi-dueling Bandits
  8. Bengs 等人（2024）Identifying Copeland Winners in Dueling Bandits with Indifferences
  9. Saha 与 Gopalan（2019b）PAC Battling Bandits in the Plackett-Luce Model
  10. Saha 与 Gopalan（2020）From PAC to Instance-Optimal Sample Complexity in the Plackett-Luce Model
  11. Saha 与 Gopalan（2019a）Combinatorial Bandits with Relative Feedback
  12. Saha 等人（2024）Faster Convergence with MultiWay Preferences
  13. Lee 等人（2025a）Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options
  14. Maran 等人（2024）Bandits with Ranking Feedback
  15. Scarlett 等人（2017）Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
  16. Cai 与 Scarlett（2021）On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization
  17. Iwazaki 与 Takeno（2025）Near-Optimal Algorithm for Non-Stationary Kernelized Bandits

29.8 观测模型的理论 #

偏斜高斯过程定理及其出处。Benavoli、Azzimonti 与 Piga 的三篇论文需要区分：第一篇是分类论文，发表于 Machine Learning 第 109 卷（2020 年），引入了偏斜高斯过程（Benavoli 等，2020）；第二篇是 GECCO 2021 Companion 论文（arXiv 2008.06677），包含偏好贝叶斯优化的后验定理（Benavoli 等，2021c）；第三篇发表于 Machine Learning 第 110 卷（2021 年），证明了与正态似然、仿射概率单位似然及其乘积的共轭性（Benavoli 等，2021a）。因此，把偏好后验定理归于“Machine Learning 2020”是错误的，“Machine Learning 2021”也只适用于一般的共轭性结论。

统一偏斜正态（unified skew-normal，SUN）分布是多元高斯分布的推广：将多元高斯密度乘以一个正态分布函数，使其倾斜（见第 17.6 节）。下述定理中，Φm\Phi_m 是 mm 个独立标准正态变量的分布函数；Ω=DΩΩˉDΩ\Omega = D_\Omega \bar\Omega D_\Omega 把协方差矩阵分解为由标准差构成的对角矩阵 DΩD_\Omega 与相关矩阵 Ωˉ\bar\Omega。

定理 29.1 偏好后验是偏斜高斯过程（Benavoli、Azzimonti 与 Piga，GECCO 2021 Companion）

设 f∼GP(ξ,Ω)f \sim \GP(\xi, \Omega)，关于 nn 个输入处的取值 f(X)f(X) 有 mm 个观测，其似然为仿射概率单位似然 p(W∣f(X))=Φm(Wf(X))p(W \mid f(X)) = \Phi_m(W f(X))，其中 WW 是 m×nm \times n 的数据矩阵。

  1. （定理 1。）f(X)f(X) 的后验是统一偏斜正态分布 SUNn,m\mathrm{SUN}_{n,m}，其偏斜参数为 Δ=ΩˉDΩW⊤\Delta = \bar\Omega D_\Omega W^\T、γ=Wξ\gamma = W\xi 与 Γ=WΩW⊤+Im\Gamma = W\Omega W^\T + I_m。
  2. （定理 2。）ff 的后验是偏斜高斯过程，均值函数为 ξ\xi，协方差函数为 Ω\Omega，偏斜函数为 Δ(x,X)=Ω(x,X)W⊤\Delta(\vx, X) = \Omega(\vx, X) W^\T。
  3. （推论 1。）对 Chu 与 Ghahramani 的似然 ∏kΦ((f(vk)−f(uk))/(2 σ))\prod_k \Phi\big((f(\mathbf{v}_k) - f(\mathbf{u}_k))/(\sqrt2\,\sigma)\big)，为保证可识别性取 σ2=1/2\sigma^2 = 1/2，令 Wij=Vij−UijW_{ij} = V_{ij} - U_{ij} 即得后验；其中 VV 与 UU 分别标记每次比较中被偏好与被拒绝的输入。

对参数化的概率单位回归，Durante（2019）此前已证明其与统一偏斜正态分布的共轭性。该定理给出的是概率单位模型的精确贝叶斯推断，而不是一致性结果或速率结果。它解释了 Laplace 近似与期望传播为何会误报对决概率，这一点对依赖预测获胜概率的采集函数很重要（第 27.4 节）；该定理不适用于逻辑链接（推断）。Wu 与 Gardner（2026）的扩展偏斜正态前瞻后验正是以此为基础。

后验一致性。后验一致性（posterior consistency）指后验随数据积累而集中到真实函数上；收缩速率（contraction rate）刻画集中的快慢。对于 Chu-Ghahramani 类型的高斯过程偏好模型，我们没有找到这类定理。最接近的结果有：POP-BO、MaxMinLCB 与 MR-LPF 中核化逻辑估计量的频率派置信集；qEUBO 在有限定义域上的贝叶斯一致性；SelfSparring 独立臂版本的渐近收敛。

随机传递性。上述遗憾定理对获胜概率所作的正则性假设各不相同，其定义见第 21.1.2 节：强、中等与弱随机传递性，以及随机三角不等式；强传递性并不蕴含随机三角不等式（Bengs 等，2021）。Yue 等人（2012）需要强随机传递性与三角不等式；SelfSparring 的近似线性比强随机传递性更严格；神经对决的结果只要随机传递性成立即成立；Suk 与 Agarwal（2023）的跟踪结果需要强随机传递性与三角不等式的交集。任何“效用加单调链接”的模型，无论是 Bradley-Terry 模型还是概率单位模型，在每一时刻都同时满足这两个条件（推断，由定义推出；习题 29.3）。Chau 等人（2022）对可排序性假设提出了质疑；他们的猜想适用范围有多大，见第 27.2 节。

第 29.8 节引用的文献 9
  1. Benavoli 等人（2020）Skew Gaussian processes for classification
  2. Benavoli 等人（2021c）Preferential Bayesian optimisation with skew gaussian processes
  3. Benavoli 等人（2021a）A unified framework for closed-form nonparametric regression, classification, preference and mixed problems with Skew Gaussian Processes
  4. Durante（2019）Conjugate Bayes for probit regression via unified skew-normal distributions
  5. Wu 与 Gardner（2026）Knowledge Gradient for Preference Learning
  6. Bengs 等人（2021）Preference-based Online Learning with Dueling Bandits: A Survey
  7. Yue 等人（2012）The K-armed Dueling Bandits Problem
  8. Suk 与 Agarwal（2023）When Can We Track Significant Preference Shifts in Dueling Bandits?
  9. Chau 等人（2022）Learning Inconsistent Preferences with Gaussian Processes

29.9 可识别性与聚合 #

若一个量的不同取值产生不同的数据分布，从而在原则上足够多的数据能将它们区分开，就称这个量是可识别的（identifiable）。一组结果表明，当回答依赖于模型观测不到的因素时，成对数据是最弱的反馈。

隐藏情境。Siththaranjan 等人（2024）研究的设定是：有限个选项、无限多数据、均匀抽取的点对、L2 正则化的 Bradley-Terry 损失；每个回答都可能依赖于模型观测不到的隐藏情境（hidden context），即回答者是谁、处于何种状态：

  • 定理 3.1。Bradley-Terry 偏好学习按 Borda 计数（Borda count）隐式地聚合隐藏情境：学到的效用满足 u^(a)>u^(b)\hat u(a) > \hat u(b) 当且仅当 BC(a)>BC(b)\mathrm{BC}(a) > \mathrm{BC}(b)，其中 BC(a)\mathrm{BC}(a) 是 aa 胜过一个随机对手的平均概率。
  • 定理 3.2。若隐藏情境噪声在各选项之间独立同分布，且其差值的支撑集包含零的某个邻域，则学到的顺序与期望效用的顺序相同。
  • 命题 3.3。多数偏好可以与期望效用一致，而 Bradley-Terry 却不一致。
  • 定理 3.4。任何使用无限比较数据的确定性方法，都不能总是恢复期望效用，即使只要求在相差一个单调变换的意义下恢复也不行。

作者指出，标注者因此有虚报偏好的动机。An 等人（2026）（预印本）也指出，Bradley-Terry-Luce 损失对应于 Borda 计数。对单用户的偏好贝叶斯优化而言，这意味着：若一个人的回答依赖于未建模的情境，如疲劳、表述框架或顺序，高斯过程效用恢复出的就是一种 Borda 型聚合，而不是平均效用（推断；算例见习题 29.1）。

异质人群。Chidambaram 等人（2026）（AISTATS 2026；arXiv 2405.15065 与 2510.15716 是同名的不同版本）针对随机系数 logit（random-coefficient logit）模型证明了三个结果。在该模型中，每个用户都有各自的偏好权重 β\beta：

  • 引理 4.1。若每个用户只做一次二元比较，则即使用户无限多，类型分布也不可识别：β\beta 与 −β-\beta 各占一半的混合在任何位置都给出概率 0.5。
  • 定理 4.2（重述 Fox 等人 2012 年的结果）。若各阶矩满足 Carleman 条件，特征的支撑集包含零附近的一个开集，β\beta 与特征独立，且至少有 3 个选项，则类型分布非参数可识别，即使数据只是三个选项的不完备排序也是如此。
  • 引理 4.3。特征差矩阵满秩时，同一用户所做的大量多样的二元比较可以识别该用户的 β\beta。

环、偏序与情境效应。Liu 等人（2026e）证明了三点：偏好能用奖励模型表示，当且仅当不存在 Condorcet 环（即按多数意见 aa 胜过 bb、bb 胜过 cc、cc 又胜过 aa 的情形）；在 Luce 模型下，Condorcet 环出现的概率以指数速度趋于 1；Nash 人类反馈学习得到混合策略，当且仅当没有哪个回答被多数认为优于其他所有回答。Drago 等人（2025）证明，构造与偏好偏序相容且维度最小的多目标效用是 NP 困难的。De Peuter 等人（2024）的出发点是一种带情境效应的偏好选择认知模型；他们使用该模型的易处理替代形式，在大规模人类数据上的推断优于 Bradley-Terry 的各种变体。Cao 等人（2026）则针对 Plackett-Luce 子集选择模型证明，仅从查询中学习会遇到平移不变性障碍，需要赌博机反馈作为锚。

综合来看（推断）：以单个固定效用上的遗憾衡量，成对比较在阶上并不天然比数值更昂贵；但在识别异质群体、在隐藏情境下恢复期望效用、处理成环的偏好这些问题上，成对数据是最弱的反馈，排序反馈优于只给出赢家的反馈。所有偏好贝叶斯优化遗憾界都以单一效用为前提，这一假设受到双重质疑：一是 Chau 等人的经验猜想，二是 Liu 等人的渐近结果。这对查询设计意味着什么，见第 20.5.3 节与第 20.5 节。

第 29.9 节引用的文献 7
  1. Siththaranjan 等人（2024）Distributional Preference Learning: Understanding and Accounting for Hidden Context in RLHF
  2. An 等人（2026）Differential Voting: Loss Functions For Axiomatically Diverse Aggregation of Heterogeneous Preferences
  3. Chidambaram 等人（2026）Direct Preference Optimization with Unobserved Preference Heterogeneity: The Necessity of Ternary Preferences
  4. Liu 等人（2026e）Statistical Impossibility and Possibility of Aligning LLMs with Human Preferences: From Condorcet Paradox to Nash Equilibrium
  5. Drago 等人（2025）Towards Theoretical Understanding of Sequential Decision Making with Preference Feedback
  6. De Peuter 等人（2024）Preference Learning of Latent Decision Utilities with a Human-like Model of Preferential Choice
  7. Cao 等人（2026）Provably Efficient Personalized Multi-Objective Bandits with Proactive Conversational Queries

29.10 漂移、污染、反应时与停止 #

真实的人有四个特点：偏好会改变，回答会出错，作答需要时间，会话必须结束。每一点都已有一些理论，但大多不在核化设定之内。

漂移。有限臂情形的理论已经成熟。Saha 与 Gupta（2022）针对对抗性的偏好序列给出了 O(KT)O(\sqrt{KT}) 的静态遗憾，对 SS 次有效切换给出了 O~(SKT)\tilde O(\sqrt{SKT}) 的动态遗憾，对连续变化量 VTV_T 给出了 O~(VT1/3K1/3T2/3)\tilde O(V_T^{1/3}K^{1/3}T^{2/3}) 的动态遗憾，且都有相匹配的下界；ANACONDA（Kleine Buening 与 Saha，2023）能适应未知的切换次数；平稳分段（Kolpaczki 等，2022）（预印本）与高维 Bradley-Terry 模型中的变点（Li 等，2022）也各有结果。Suk 与 Agarwal（2023）证明，在 Condorcet 类或强随机传递性类下，不可能以 O(KLT)O(\sqrt{KLT}) 的速率适应“显著变化”（significant shifts，LL 为显著变化的次数）；在常见的类中，使之可行的最大一类是强随机传递性与三角不等式的交集。Liu 等人（2026c）证明，若反馈按瞬时效用排序，次线性外部遗憾一般不可能实现，而当效用序列的总变差为次线性时则成为可能；Son 等人（2025）给出了未知漂移下直接偏好优化的界。对于标量核函数，Iwazaki 与 Takeno（2025）给出了非平稳核化赌博机的第一个与算法无关的下界；Bogunovic 等人（2016）的定理 4.1 表明，在其 Markov 模型中，若每步变化量 ε\varepsilon 固定，任何算法的累积遗憾都是 Ω(Tε)\Omega(T\varepsilon)。由于“效用加链接”的模型在每一时刻都满足强随机传递性与三角不等式，在核化偏好贝叶斯优化中跟踪漂移的障碍是技术性的，即缺少核函数加链接函数情形的动态遗憾分析，而非已知的不可能性（推断）；偏好贝叶斯优化中也没有漂移效用的模型（第 27.2 节），因而没有动态遗憾保证。

污染与偏差。Agarwal 等人（2021）给出的遗憾与涉及 Condorcet 赢家的被污染比较个数呈线性关系，并证明这种线性依赖是必要的；Saha 与 Gaillard（2022）在被污染的 Condorcet 设定中只多付出加性的 2C2C。在线性情形中，Di 等人（2025）给出了 O~(κdT+κdC)\tilde O(\kappa d\sqrt{T} + \kappa dC)，其中 κ\kappa 乘在污染项上；Oh（2026）给出了 O~(d(T+C+D))\tilde O(d(\sqrt{T} + C + D))，其中 DD 度量延迟。已知或未知的评价者偏差（Tang 等，2025），以及基于人类反馈的强化学习中被污染的点对（Bukharin 等，2024；Mandal 等，2025），也都已有研究。在核函数情形中，唯一的稳健性结果仍是 Kirschner 与 Krause 2021 年的线性链接偏差模型；标量参照是 Bogunovic 等人（2020）。Siththaranjan 等人的结果意味着标注者有理由虚报，因此引出真实反馈的机制也很重要；一篇 AISTATS 2026 论文用 Vickrey-Clarke-Groves 机制实现了这一点（Landolt 等，2026），我们只核实了其题名与发表会议。

反应时。在人类信号通道中，只有反应时有理论分析，且仅针对线性效用。Li 等人（2024a）使用 EZ 扩散模型，即描述选择过程中证据如何累积的一种简化漂移扩散模型（第 39.3 节），并从理论与实验两方面表明，对于偏好强烈的查询，反应时能补充选择所含的信息。Benkert 等人（2026）（工作论文，2026 年版本）证明，二元选择频率只能识别潜在偏好分布上的一个点，加上单调的反应时函数后则能在多个点上识别。Shvartsman 等人（2024）的高斯过程反应时模型没有理论保证。

停止。与偏好贝叶斯优化中带保证的停止规则最接近的结果如下。Haddenhorst 等人（2021b）把识别 Condorcet 赢家与检验其是否存在结合起来，使学习者可以停止并拒绝作答，同时给出了期望样本复杂度的下界和一个在对数因子以内最优的算法。Shukla 与 Basu（2024）针对由锥确定顺序的向量奖励，给出了一个下界与相匹配的偏好感知 Track-and-Stop 算法。固定置信度的识别也有各自的停止规则（Bengs 等，2024；Saha 与 Gopalan，2019b；Saha 与 Gopalan，2020）。Bıyık 等人的参数化规则，以及尚未移植到成对似然上的标量规则，见第 30.7 节。

第 29.10 节引用的文献 26
  1. Saha 与 Gupta（2022）Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits
  2. Kleine Buening 与 Saha（2023）ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits
  3. Kolpaczki 等人（2022）Non-Stationary Dueling Bandits
  4. Li 等人（2022）Detecting Abrupt Changes in Sequential Pairwise Comparison Data
  5. Suk 与 Agarwal（2023）When Can We Track Significant Preference Shifts in Dueling Bandits?
  6. Liu 等人（2026c）Online Learning and Equilibrium Computation with Ranking Feedback
  7. Son 等人（2025）Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift
  8. Iwazaki 与 Takeno（2025）Near-Optimal Algorithm for Non-Stationary Kernelized Bandits
  9. Bogunovic 等人（2016）Time-Varying Gaussian Process Bandit Optimization
  10. Agarwal 等人（2021）Stochastic Dueling Bandits with Adversarial Corruption
  11. Saha 与 Gaillard（2022）Versatile Dueling Bandits: Best-of-both World Analyses for Learning from Relative Preferences
  12. Di 等人（2025）Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback
  13. Oh（2026）Robust Linear Dueling Bandits with Post-serving Context under Unknown Delays and Adversarial Corruptions
  14. Tang 等人（2025）Tackling Biased Evaluators in Dueling Bandits
  15. Bukharin 等人（2024）Robust Reinforcement Learning from Corrupted Human Feedback
  16. Mandal 等人（2025）Corruption Robust Offline Reinforcement Learning with Human Feedback
  17. Bogunovic 等人（2020）Corruption-Tolerant Gaussian Process Bandit Optimization
  18. Landolt 等人（2026）Eliciting Truthful Feedback for Preference-Based Learning via the VCG Mechanism
  19. Li 等人（2024a）Enhancing Preference-based Linear Bandits via Human Response Time
  20. Benkert 等人（2026）Time is Knowledge: What Response Times Reveal
  21. Shvartsman 等人（2024）Response Time Improves Gaussian Process Models for Perception and Preferences
  22. Haddenhorst 等人（2021b）Testification of Condorcet Winners in dueling bandits
  23. Shukla 与 Basu（2024）Preference-based Pure Exploration
  24. Bengs 等人（2024）Identifying Copeland Winners in Dueling Bandits with Indifferences
  25. Saha 与 Gopalan（2019b）PAC Battling Bandits in the Plackett-Luce Model
  26. Saha 与 Gopalan（2020）From PAC to Instance-Optimal Sample Complexity in the Plackett-Luce Model

29.11 已定、有争议与缺失 #

研究现状已定、有争议与缺失

已定。有限臂对决赌博机的实例最优对数遗憾及相匹配的下界（Komiyama 等，2015；Saha 与 Gaillard，2022）。线性与情境对决在链接常数与对数因子以内的极小极大速率（Saha，2021；Li 等，2024b）。2024 年以前的形式化保证：SelfSparring（2017 年）、Kumagai（2017 年）、Xu 等人（2020 年）、Kirschner 与 Krause（2021 年）、qEUBO（2023 年）。Kirschner 与 Krause 2021 年的结果是第一个关于累积遗憾的核化对决界，采用“差加噪声”模型。Bradley-Terry 链接下的核化上界：POP-BO 约为 T3/4T^{3/4}（效用遗憾）；MaxMinLCB 与 PF-TS 为 γTT\gamma_T\sqrt{T}；MR-LPF 为 γTT\sqrt{\gamma_T T}（分批、有限定义域、有预热期）；后三者以偏好概率遗憾计。概率单位偏好后验是偏斜高斯过程（Benavoli 等，2021c）。来自更大子集的赢家反馈在阶上没有增益，top-mm 排序带来 mm 倍增益（有限臂与线性模型）（Saha 与 Gopalan，2019b；Saha，2021）。

有争议。MR-LPF 的最优性：作者自己称紧性论证是非正式的，一份未经证实的机器评审也质疑了其定理 4.7 中的一个不等式。“比较与数值一样样本高效”：这是分批、有限定义域、逻辑链接设定中上界阶的相等，而非信息量的相等，且尚无定论。序贯与分批：MR-LPF 阶最优但分批，MaxMinLCB 与 PF-TS 序贯但损失 γT\sqrt{\gamma_T} 因子，两类结果并存；唯一的直接比较来自 PF-TS 的论文，该文与 MR-LPF 有共同作者，且实验是低维的。

缺失，按对偏好贝叶斯优化理论的限制程度排列（推断）：Bradley-Terry 链接或概率单位链接下、显式给出 κ\kappa 依赖的核化下界；阶最优的完全序贯算法；核化界中的排序似然或多选项似然；对实践中所用近似后验（Laplace 近似、期望传播）的分析，而非对精确估计量或频率派估计量的分析；核函数情形中漂移、污染与反应时的理论；连续定义域上 qEUBO 类规则的贝叶斯遗憾；把贝叶斯推荐 arg max⁡xENf(x)\argmax_{\vx}\E_N f(\vx) 与某种保证联系起来的停止规则；高斯过程偏好模型的后验一致性；以及对决 Thompson 采样（DTS）与幻觉信念的遗憾界、KernelSelfSparring 为无遗憾算法的证明。

第 29.11 节引用的文献 6
  1. Komiyama 等人（2015）Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem
  2. Saha 与 Gaillard（2022）Versatile Dueling Bandits: Best-of-both World Analyses for Learning from Relative Preferences
  3. Saha（2021）Optimal Algorithms for Stochastic Contextual Preference Bandits
  4. Li 等人（2024b）Feel-Good Thompson Sampling for Contextual Dueling Bandits
  5. Benavoli 等人（2021c）Preferential Bayesian optimisation with skew gaussian processes
  6. Saha 与 Gopalan（2019b）PAC Battling Bandits in the Plackett-Luce Model

29.12 习题 #

习题 29.1

回答某个成对问题的人中，一半属于类型 1，对选项 (a,b,c)(a, b, c) 的效用为 (10,1,0)(10, 1, 0)；另一半属于类型 2，效用为 (0,2,1)(0, 2, 1)。每个人都按自己的效用确定性地作答，模型不知道回答者是谁。（a）计算每个选项的期望效用，以及每个选项胜过其他每个选项的概率。（b）计算 Borda 计数，即一个选项胜过均匀选取的另一选项的平均概率。（c）按第 29.9 节所述 Siththaranjan 等人的定理 3.1，Bradley-Terry 学习恢复出什么顺序？它与期望效用一致吗？

解答

（a）期望效用分别为：aa 为 55，bb 为 1.51.5，cc 为 0.50.5，故 a≻b≻ca \succ b \succ c。类型 1 偏好 aa 甚于 bb，类型 2 偏好 bb 甚于 aa，故 P(a≻b)=1/2\Prob(a \succ b) = 1/2；同理 P(a≻c)=1/2\Prob(a \succ c) = 1/2；两种类型都偏好 bb 甚于 cc，故 P(b≻c)=1\Prob(b \succ c) = 1。（b）BC(a)=(1/2+1/2)/2=0.5\mathrm{BC}(a) = (1/2 + 1/2)/2 = 0.5，BC(b)=(1/2+1)/2=0.75\mathrm{BC}(b) = (1/2 + 1)/2 = 0.75，BC(c)=(1/2+0)/2=0.25\mathrm{BC}(c) = (1/2 + 0)/2 = 0.25。（c）学到的效用按 Borda 计数给选项排序，即 b≻a≻cb \succ a \succ c，而期望效用把 aa 排在首位：类型 1 从 aa 获得的巨大收益从不在二元回答中显现，因为二元回答只记录偏好的方向。这些概率已是无限数据下的极限，再做更多同样的比较也不会改变学到的顺序；这正是定理 3.4 所描述的情形。在一个人的会话中，这些“类型”可以是情绪、表述框架或疲劳状态（推断）。

习题 29.2

在逻辑链接下，设某个查询与最优点的效用差距为 gg，比较两种遗憾单位：效用遗憾 gg 与偏好概率遗憾 sigmoid⁡(g)−1/2\operatorname{sigmoid}(g) - 1/2。分别计算 g=0.1g = 0.1 与 g=4g = 4 时的两者。在什么条件下，可以放心地把以一种单位给出的速率与以另一种单位给出的速率相比较？

解答

当 g=0.1g = 0.1 时：sigmoid⁡(0.1)−1/2≈0.0250\operatorname{sigmoid}(0.1) - 1/2 \approx 0.0250，接近 g/4=0.025g/4 = 0.025，因为 sigmoid⁡\operatorname{sigmoid} 在零处的斜率是 1/41/4。当 g=4g = 4 时：sigmoid⁡(4)−1/2≈0.482\operatorname{sigmoid}(4) - 1/2 \approx 0.482，而 g/4=1g/4 = 1；偏好概率遗憾在 1/21/2 处饱和，此时按比例换算的值约为它的 2 倍，即大差距被低估；gg 越大，低估越严重。只有当求和中起主导作用的差距较小时，两种单位才成比例；因此，一种单位下的速率只有在这一近似下、以因子 1/41/4 换算，才能转为另一种单位，跨论文比较时应当说明这一点。

习题 29.3

设效用为 uu，链接 FF 严格递增，满足 F(0)=1/2F(0) = 1/2 与 F(−a)=1−F(a)F(-a) = 1 - F(a)，且 P(i≻j)=F(ui−uj)\Prob(i \succ j) = F(u_i - u_j)。证明强随机传递性成立。再证明：若 FF 在 [0,∞)[0, \infty) 上是凹函数，则随机三角不等式也成立。

解答

记 a=ui−uja = u_i - u_j，b=uj−ukb = u_j - u_k。若 Δij≥0\Delta_{ij} \ge 0 且 Δjk≥0\Delta_{jk} \ge 0，则由于 FF 递增且 F(0)=1/2F(0) = 1/2，有 a,b≥0a, b \ge 0。于是 ui−uk=a+b≥max⁡{a,b}u_i - u_k = a + b \ge \max\{a, b\}，又因为 FF 递增，Δik=F(a+b)−1/2≥max⁡{F(a),F(b)}−1/2\Delta_{ik} = F(a + b) - 1/2 \ge \max\{F(a), F(b)\} - 1/2，这就是强随机传递性。对三角不等式，令 G(x)=F(x)−1/2G(x) = F(x) - 1/2，则 G(0)=0G(0) = 0，且 GG 在 [0,∞)[0, \infty) 上是凹的。满足 G(0)=0G(0) = 0 的凹函数在该区间上是次可加的：在 00 与 a+ba + b 之间应用凹性，得 G(a)≥aa+bG(a+b)G(a) \ge \tfrac{a}{a + b}G(a + b) 与 G(b)≥ba+bG(a+b)G(b) \ge \tfrac{b}{a + b}G(a + b)，两式相加得 G(a)+G(b)≥G(a+b)G(a) + G(b) \ge G(a + b)，即 Δik≤Δij+Δjk\Delta_{ik} \le \Delta_{ij} + \Delta_{jk}。逻辑链接与概率单位链接都递增、对称，且在 [0,∞)[0, \infty) 上为凹，因此本书的模型在每一时刻都满足这两个条件；第 29.10 节中的推断即以此为依据。

延伸阅读 #

参考文献

  1. Abeille, M., Faury, L., and Calauzènes, C. (2021). Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits. International Conference on Artificial Intelligence and Statistics. 引用于 §29.5
  2. Agarwal, A., Agarwal, S., and Patil, P. (2021). Stochastic Dueling Bandits with Adversarial Corruption. Algorithmic Learning Theory. 引用于 §29.10
  3. Agarwal, A., Ghuge, R., and Nagarajan, V. (2022). Batched Dueling Bandits. International Conference on Machine Learning. 引用于 §29.7
  4. Agnihotri, A., Jain, R., Ramachandran, D., and Wen, Z. (2026). Best Policy Learning From Trajectory Preference Feedback. International Conference on Artificial Intelligence and Statistics. 引用于 §29.1
  5. An, Z., Nakshbandi, D., and Du, W. (2026). Differential Voting: Loss Functions For Axiomatically Diverse Aggregation of Heterogeneous Preferences. arXiv. 预印本引用于 §29.9
  6. Astudillo, R., Lin, Z. J., Bakshy, E., and Frazier, P. (2023). qEUBO: A Decision-Theoretic Acquisition Function for Preferential Bayesian Optimization. International Conference on Artificial Intelligence and Statistics. 引用于 §29.4 §29.6
  7. Benavoli, A., Azzimonti, D., and Piga, D. (2020). Skew Gaussian processes for classification. Machine Learning. 引用于 §29.8
  8. Benavoli, A., Azzimonti, D., and Piga, D. (2021a). A unified framework for closed-form nonparametric regression, classification, preference and mixed problems with Skew Gaussian Processes. Machine Learning. 引用于 §29.8
  9. Benavoli, A., Azzimonti, D., and Piga, D. (2021c). Preferential Bayesian optimisation with skew gaussian processes. Proceedings of the Genetic and Evolutionary Computation Conference Companion. 引用于 §29.8 §29.11
  10. Bengs, V., Busa-Fekete, R., El Mesaoudi-Paul, A., and Hüllermeier, E. (2021). Preference-based Online Learning with Dueling Bandits: A Survey. Journal of Machine Learning Research. 引用于 §29.1 §29.8
  11. Bengs, V., Saha, A., and Hüllermeier, E. (2022). Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Models. International Conference on Machine Learning. 引用于 §29.1
  12. Bengs, V., Haddenhorst, B., and Hüllermeier, E. (2024). Identifying Copeland Winners in Dueling Bandits with Indifferences. International Conference on Artificial Intelligence and Statistics. 引用于 §29.7 §29.10
  13. Benkert, J.-M., Liu, S., and Netzer, N. (2026). Time is Knowledge: What Response Times Reveal. working paper (arXiv). 工作论文引用于 §29.10
  14. Blum, A., Gupta, M., Li, G., Manoj, N. S., Saha, A., and Yang, Y. (2024). Dueling Optimization with a Monotone Adversary. International Conference on Algorithmic Learning Theory. 引用于 §29.1
  15. Bogunovic, I., Scarlett, J., and Cevher, V. (2016). Time-Varying Gaussian Process Bandit Optimization. AISTATS 2016. 引用于 §29.10
  16. Bogunovic, I., Krause, A., and Scarlett, J. (2020). Corruption-Tolerant Gaussian Process Bandit Optimization. International Conference on Artificial Intelligence and Statistics. 引用于 §29.10
  17. Bukharin, A., Hong, I., Jiang, H., Li, Z., Zhang, Q., Zhang, Z., and Zhao, T. (2024). Robust Reinforcement Learning from Corrupted Human Feedback. Advances in Neural Information Processing Systems. 引用于 §29.10
  18. Cai, X., and Scarlett, J. (2021). On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization. International Conference on Machine Learning. 引用于 §29.7
  19. Cao, L., Shi, M., and Shroff, N. B. (2026). Provably Efficient Personalized Multi-Objective Bandits with Proactive Conversational Queries. UAI 2026. 引用于 §29.9
  20. Chau, S. L., González, J., and Sejdinovic, D. (2022). Learning Inconsistent Preferences with Gaussian Processes. International Conference on Artificial Intelligence and Statistics. 引用于 §29.8
  21. Chen, B., and Frazier, P. I. (2017). Dueling Bandits with Weak Regret. International Conference on Machine Learning. 引用于 §29.1
  22. Chen, X., Zhong, H., Yang, Z., Wang, Z., and Wang, L. (2022). Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation. International Conference on Machine Learning. 引用于 §29.1
  23. Chidambaram, K., Seetharaman, K. V., and Syrgkanis, V. (2026). Direct Preference Optimization with Unobserved Preference Heterogeneity: The Necessity of Ternary Preferences. International Conference on Artificial Intelligence and Statistics. 引用于 §29.9
  24. Chowdhury, S. R., and Gopalan, A. (2017). On Kernelized Multi-armed Bandits. International Conference on Machine Learning. 引用于 §29.4
  25. De Peuter, S., Zhu, S., Guo, Y., Howes, A., and Kaski, S. (2024). Preference Learning of Latent Decision Utilities with a Human-like Model of Preferential Choice. Advances in Neural Information Processing Systems. 引用于 §29.9
  26. Di, Q., Jin, T., Wu, Y., Zhao, H., Farnoud, F., and Gu, Q. (2024). Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits. International Conference on Learning Representations. 引用于 §29.1
  27. Di, Q., He, J., and Gu, Q. (2025). Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback. International Conference on Machine Learning. 引用于 §29.1 §29.5 §29.10
  28. Drago, S., Mussi, M., and Metelli, A. M. (2025). Towards Theoretical Understanding of Sequential Decision Making with Preference Feedback. International Conference on Machine Learning. 引用于 §29.9
  29. Dudík, M., Hofmann, K., Schapire, R. E., Slivkins, A., and Zoghi, M. (2015). Contextual Dueling Bandits. Conference on Learning Theory. 引用于 §29.1
  30. Durante, D. (2019). Conjugate Bayes for probit regression via unified skew-normal distributions. Biometrika. 引用于 §29.8
  31. Faury, L., Abeille, M., Calauzènes, C., and Fercoq, O. (2020). Improved Optimistic Algorithms for Logistic Bandits. International Conference on Machine Learning. 引用于 §29.5
  32. González, J., Dai, Z., Damianou, A., and Lawrence, N. D. (2017). Preferential Bayesian Optimization. International Conference on Machine Learning. 引用于 §29.1
  33. Haddenhorst, B., Bengs, V., and Hüllermeier, E. (2021a). Identification of the Generalized Condorcet Winner in Multi-dueling Bandits. Advances in Neural Information Processing Systems. 引用于 §29.7
  34. Haddenhorst, B., Bengs, V., Brandt, J., and Hüllermeier, E. (2021b). Testification of Condorcet Winners in dueling bandits. Uncertainty in Artificial Intelligence. 引用于 §29.10
  35. Iwazaki, S., and Takeno, S. (2025). Near-Optimal Algorithm for Non-Stationary Kernelized Bandits. International Conference on Artificial Intelligence and Statistics. 引用于 §29.7 §29.10
  36. Kayal, A., Vakili, S., Toni, L., Shiu, D.-S., and Bernacchia, A. (2025). Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds. International Conference on Machine Learning. 引用于 §29.3 §29.4
  37. Kirschner, J., and Krause, A. (2021). Bias-Robust Bayesian Optimization via Dueling Bandits. International Conference on Machine Learning. 引用于 §29.2 §29.4
  38. Kleine Buening, T., and Saha, A. (2023). ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits. International Conference on Artificial Intelligence and Statistics. 引用于 §29.10
  39. Kolpaczki, P., Bengs, V., and Hüllermeier, E. (2022). Non-Stationary Dueling Bandits. arXiv. 预印本引用于 §29.10
  40. Komiyama, J., Honda, J., Kashima, H., and Nakagawa, H. (2015). Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem. Conference on Learning Theory. 引用于 §29.1 §29.7 §29.11
  41. Kumagai, W. (2017). Regret Analysis for Continuous Dueling Bandit. Advances in Neural Information Processing Systems. 引用于 §29.1 §29.4
  42. Landolt, L., Maddux, A. M., Schlaginhaufen, A., Vaishampayan, S., and Kamgarpour, M. (2026). Eliciting Truthful Feedback for Preference-Based Learning via the VCG Mechanism. International Conference on Artificial Intelligence and Statistics. 引用于 §29.10
  43. Lazzaro, J., Buffelli, D., Shiu, D.-s., and Vakili, S. (2026). A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedback. International Conference on Artificial Intelligence and Statistics. 引用于 §29.3 §29.4
  44. Lee, J., Yi, S.-w., and Oh, M.-h. (2025a). Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options. NeurIPS 2025. 引用于 §29.7
  45. Li, Z., and Scarlett, J. (2022). Gaussian Process Bandit Optimization with Few Batches. International Conference on Artificial Intelligence and Statistics. 引用于 §29.4
  46. Li, W., Rinaldo, A., and Wang, D. (2022). Detecting Abrupt Changes in Sequential Pairwise Comparison Data. Advances in Neural Information Processing Systems. 引用于 §29.10
  47. Li, S., Zhang, Y., Ren, Z., Liang, C., Li, N., and Shah, J. A. (2024a). Enhancing Preference-based Linear Bandits via Human Response Time. Advances in Neural Information Processing Systems. 引用于 §29.10
  48. Li, X., Zhao, H., and Gu, Q. (2024b). Feel-Good Thompson Sampling for Contextual Dueling Bandits. International Conference on Machine Learning. 引用于 §29.1 §29.11
  49. Liu, M., Chen, Y., Fan, Z., Farina, G., Ozdaglar, A., and Zhang, K. (2026c). Online Learning and Equilibrium Computation with Ranking Feedback. ICLR 2026. 引用于 §29.10
  50. Liu, K., Long, Q., Shi, Z., Su, W. J., and Xiao, J. (2026e). Statistical Impossibility and Possibility of Aligning LLMs with Human Preferences: From Condorcet Paradox to Nash Equilibrium. The Annals of Statistics. doi:10.1214/26-aos2643. 引用于 §29.9
  51. Mandal, D., Nika, A., Kamalaruban, P., Singla, A., and Radanovic, G. (2025). Corruption Robust Offline Reinforcement Learning with Human Feedback. International Conference on Artificial Intelligence and Statistics. 引用于 §29.10
  52. Maran, D., Bacchiocchi, F., Stradi, F. E., Castiglioni, M., Gatti, N., and Restelli, M. (2024). Bandits with Ranking Feedback. Advances in Neural Information Processing Systems. 引用于 §29.7
  53. Novoseller, E., Wei, Y., Sui, Y., Yue, Y., and Burdick, J. (2020). Dueling Posterior Sampling for Preference-Based Reinforcement Learning. Conference on Uncertainty in Artificial Intelligence. 引用于 §29.1
  54. Oh, Y. (2026). Robust Linear Dueling Bandits with Post-serving Context under Unknown Delays and Adversarial Corruptions. ICML 2026. 引用于 §29.10
  55. Oh, Y., Park, J., and Paik, T. (2026a). Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Exploration. International Conference on Artificial Intelligence and Statistics. 引用于 §29.3
  56. Pásztor, B., Kassraie, P., and Krause, A. (2024). Bandits with Preference Feedback: A Stackelberg Game Perspective. Advances in Neural Information Processing Systems. doi:10.52202/079017-0383. 引用于 §29.3 §29.4
  57. Pith (2026). Machine-generated review of arXiv 2505.23673 (MR-LPF). pith.science. 非同行评审引用于 §29.3
  58. Saad, E. M., Carpentier, A., Kocák, T., and Verzelen, N. (2024). On Weak Regret Analysis for Dueling Bandits. Advances in Neural Information Processing Systems. 引用于 §29.7
  59. Saha, A. (2021). Optimal Algorithms for Stochastic Contextual Preference Bandits. Advances in Neural Information Processing Systems. 引用于 §29.1 §29.11
  60. Saha, A., and Gaillard, P. (2021). Dueling Bandits with Adversarial Sleeping. Advances in Neural Information Processing Systems. 引用于 §29.7
  61. Saha, A., and Gaillard, P. (2022). Versatile Dueling Bandits: Best-of-both World Analyses for Learning from Relative Preferences. International Conference on Machine Learning. 引用于 §29.1 §29.7 §29.10 §29.11
  62. Saha, A., and Gopalan, A. (2019a). Combinatorial Bandits with Relative Feedback. Advances in Neural Information Processing Systems. 引用于 §29.7
  63. Saha, A., and Gopalan, A. (2019b). PAC Battling Bandits in the Plackett-Luce Model. Algorithmic Learning Theory. 引用于 §29.7 §29.10 §29.11
  64. Saha, A., and Gopalan, A. (2020). From PAC to Instance-Optimal Sample Complexity in the Plackett-Luce Model. International Conference on Machine Learning. 引用于 §29.7 §29.10
  65. Saha, A., and Gupta, S. (2022). Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits. International Conference on Machine Learning. 引用于 §29.10
  66. Saha, A., and Krishnamurthy, A. (2022). Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability. International Conference on Algorithmic Learning Theory. 引用于 §29.1
  67. Saha, A., Koren, T., and Mansour, Y. (2021a). Adversarial Dueling Bandits. International Conference on Machine Learning. 引用于 §29.7
  68. Saha, A., Koren, T., and Mansour, Y. (2021b). Dueling Convex Optimization. International Conference on Machine Learning. 引用于 §29.1
  69. Saha, A., Feldman, V., Mansour, Y., and Koren, T. (2024). Faster Convergence with MultiWay Preferences. International Conference on Artificial Intelligence and Statistics. 引用于 §29.7
  70. Saha, A., Koren, T., and Mansour, Y. (2025). Dueling Convex Optimization with General Preferences. International Conference on Machine Learning. 引用于 §29.1
  71. Salgia, S., Vakili, S., and Zhao, Q. (2021). A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance. Advances in Neural Information Processing Systems. 引用于 §29.4
  72. Scarlett, J., Bogunovic, I., and Cevher, V. (2017). Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization. Conference on Learning Theory. 引用于 §29.4 §29.7
  73. Sekhari, A., Sridharan, K., Sun, W., and Wu, R. (2023). Contextual Bandits and Imitation Learning with Preference-Based Active Queries. Advances in Neural Information Processing Systems. 引用于 §29.1
  74. Shukla, A., and Basu, D. (2024). Preference-based Pure Exploration. Advances in Neural Information Processing Systems. 引用于 §29.10
  75. Shvartsman, M., Letham, B., Bakshy, E., and Keeley, S. (2024). Response Time Improves Gaussian Process Models for Perception and Preferences. Uncertainty in Artificial Intelligence. 引用于 §29.10
  76. Siththaranjan, A., Laidlaw, C., and Hadfield-Menell, D. (2024). Distributional Preference Learning: Understanding and Accounting for Hidden Context in RLHF. ICLR 2024. 引用于 §29.9
  77. Son, S., Bankes, W., Chowdhury, S. R., Paige, B., and Bogunovic, I. (2025). Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift. International Conference on Machine Learning. 引用于 §29.10
  78. Sui, Y., Zhuang, V., Burdick, J. W., and Yue, Y. (2017b). Multi-dueling Bandits with Dependent Arms. UAI 2017. 引用于 §29.1 §29.4
  79. Sui, Y., Zoghi, M., Hofmann, K., and Yue, Y. (2018a). Advancements in Dueling Bandits. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. doi:10.24963/ijcai.2018/776. 引用于 §29.1
  80. Suk, J., and Agarwal, A. (2023). When Can We Track Significant Preference Shifts in Dueling Bandits? Advances in Neural Information Processing Systems. 引用于 §29.8 §29.10
  81. Tang, M., Zhou, Y., and Huang, C. (2025). Tackling Biased Evaluators in Dueling Bandits. Advances in Neural Information Processing Systems 38. doi:10.52202/085713-2520. 引用于 §29.10
  82. Vakili, S., Khezeli, K., and Picheny, V. (2021a). On Information Gain and Regret Bounds in Gaussian Process Bandits. International Conference on Artificial Intelligence and Statistics. 引用于 §29.4
  83. Vakili, S., Scarlett, J., and Javidi, T. (2021b). Open Problem: Tight Online Confidence Intervals for RKHS Elements. Conference on Learning Theory. 引用于 §29.4
  84. Verma, A., Dai, Z., Lin, X., Jaillet, P., and Low, B. K. H. (2025). Neural Dueling Bandits: Preference-Based Optimization with Human Feedback. International Conference on Learning Representations. 引用于 §29.3 §29.4
  85. Whitehouse, J., Ramdas, A., and Wu, S. (2023). On the Sublinear Regret of GP-UCB. Advances in Neural Information Processing Systems. 引用于 §29.4
  86. Wu, K., and Gardner, J. R. (2026). Knowledge Gradient for Preference Learning. arXiv. 预印本引用于 §29.8
  87. Wu, Y., Jin, T., Di, Q., Lou, H., Farnoud, F., and Gu, Q. (2024). Borda Regret Minimization for Generalized Linear Dueling Bandits. International Conference on Machine Learning. 引用于 §29.1
  88. Xu, Y., Wang, R., Yang, L., Singh, A., and Dubrawski, A. (2020a). Preference-based Reinforcement Learning with Finite-Time Guarantees. Advances in Neural Information Processing Systems. 引用于 §29.1
  89. Xu, Y., Joshi, A., Singh, A., and Dubrawski, A. (2020b). Zeroth Order Non-convex optimization with Dueling-Choice Bandits. Conference on Uncertainty in Artificial Intelligence. 引用于 §29.2 §29.4
  90. Xu, W., Wang, W., Jiang, Y., Svetozarevic, B., and Jones, C. (2024b). Principled Preferential Bayesian Optimization. International Conference on Machine Learning. 引用于 §29.3 §29.4
  91. Yue, Y., and Joachims, T. (2009). Interactively optimizing information retrieval systems as a dueling bandits problem. Proceedings of the 26th Annual International Conference on Machine Learning. 引用于 §29.1
  92. Yue, Y., Broder, J., Kleinberg, R., and Joachims, T. (2012). The K-armed Dueling Bandits Problem. Journal of Computer and System Sciences. 引用于 §29.1 §29.8
  93. Zhu, B., Jordan, M., and Jiao, J. (2023). Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons. International Conference on Machine Learning. 引用于 §29.1