📊 statistics

Learning Kernel-Based MDPs from Episodic Preferential Feedback

本文提出了一个严格的理论框架，用于仅利用二元轨迹偏好学习基于核函数的分块马尔可夫决策过程，并建立了高概率次线性后悔界，以保证所学策略收敛至最优策略。

原作者： Nikola Pavlovic, Sattar Vakili, Qing Zhao

发布于 2026-05-25

📖 1 分钟阅读☕ 轻松阅读

原作者： Nikola Pavlovic, Sattar Vakili, Qing Zhao

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

以下是论文《从片段式偏好反馈中学习基于核的马尔可夫决策过程》的通俗解释，辅以富有创意的类比。

宏观图景：通过比较而非打分来学习

想象你正在训练一个机器人烹饪完美的一餐。在人工智能训练的旧时代，你必须扮演一位严苛的美食评论家，为机器人做的每一道菜给出一个具体的分数（例如 10 分制中的 7.5 分）。这很难，因为人类不擅长给出精确的数字。我们知道一道菜比另一道“更好”，但无法总是说出“好多少”。

这篇论文解决了一个问题，即人工智能仅通过比较来学习。人类不需要打分，只需说“我更喜欢意大利面而不是披萨”。人工智能必须仅通过倾听这些"A 与 B"的选择，来找出最佳的烹饪方式。

研究人员构建了一种新的数学方法（算法），使人工智能能够高效地学习最佳策略，即使它所处的世界极其复杂且混乱（从数学上讲，这被称为“核马尔可夫决策过程”）。

挑战：偏好的“黑箱”

这里的难点在于，人工智能获得的信息非常少。

旧方法（数值奖励）： 如果你告诉人工智能“这道披萨得了 9/10 分”，你会获得大量数据。你确切知道它有多好。
新方法（偏好）： 如果你只说“我更喜欢意大利面”，人工智能就会丢失大量信息。它不知道是因为意大利面棒极了而披萨糟糕透顶，还是因为两者都还凑合。这就像只被告知“比昨天暖和”却不知道实际温度，试图猜测房间的温度一样。

此外，人工智能必须在复杂的环境中学习，早期的一点点失误可能会毁掉整餐饭（即“轨迹”）。本文探讨了当环境复杂（使用“核”数学来处理非线性的混乱模式）且每轮反馈仅为单一的“是/否”偏好时，如何高效地学习。

解决方案：PROSTO（乐观的厨师）

作者介绍了一种名为PROSTO的算法。将 PROSTO 想象成一位非常乐观的厨师，正试图学习最佳的食谱。

以下是 PROSTO 逐步工作的过程：

“如果”游戏（探索）：
由于厨师尚未知道完美食谱，他们需要尝试新事物。但他们不能随机猜测，那样太浪费。PROSTO 使用了一种名为高斯过程扰动的数学技巧。
- 类比： 想象厨师有一个“魔法香料瓶”。每次烹饪时，他们都会在计划中撒入一点“随机不确定性”。这迫使他们尝试稍微不同的意大利面或披萨版本。这确保了他们会探索厨房的每个角落以发现隐藏的瑰宝，而不是固守已知的事物。
“信心”评分（正则化）：
厨师需要知道自己对猜测有多确定。如果非常不确定，他们应该更大胆；如果很确定，他们应该坚持计划。
- 论文使用了一种名为正则化核逻辑回归的技术。将其想象为一个“信心计”。它平衡了厨师尝试新事物的愿望与保持准确的需求。它防止厨师变得过于狂野（导致糟糕的饭菜）或过于无聊（导致错过最佳食谱）。
“比较”引擎：
在每一轮中，厨师烹饪两顿不同的饭菜（两种不同的策略），并询问人类：“你喜欢哪一个？”
- 算法利用这个单一的“是/否”答案来更新其内部的厨房地图。它不仅更新特定的那顿饭，还更新对整个烹饪过程的理解，即使对于它没有直接看到的步骤也是如此。

这篇论文为何特别（“魔法”部分）

研究人员声称解决了一个非常困难的数学难题。

“覆盖”问题： 在复杂的数学中，要证明一个算法有效，你必须展示可以用数量可控的猜测来“覆盖”所有可能的场景。通常，当你添加“随机噪声”（如魔法香料瓶）来促使人工智能探索时，会使数学爆炸并变得无法计算。
突破： 作者找到了一种方法使数学保持“温顺”。他们证明了即使存在这种随机噪声，随着人工智能学习更多，找到最佳解决方案所需的猜测数量也会缓慢增长（次线性增长）。
结果： 他们证明了他们的算法 PROSTO 最终将找到最佳策略，并且能够高效地做到这一点，而无需数百万次的人工比较。它适用于一大类复杂环境（Matérn 核），涵盖了现实中许多事物并不完全平滑或可预测的场景。

核心结论

这篇论文提出了一种新的、数学上严谨的方法，使人工智能能够在复杂的现实情境中从人类偏好（如“我更喜欢 A 而不是 B"）中学习。

问题： 从简单的"A 与 B"选择中学习很难，因为你会丢失信息，而复杂的环境使情况更加困难。
解决方法： 一种名为 PROSTO 的算法，它利用“乐观探索”（基于不确定性尝试新事物）和细致的数学调整来保持高效。
证明： 作者从数学上证明了这种方法有效，并且随着时间的推移会越来越好，收敛到最佳可能解，而无需不可想象的计算能力。

简而言之，他们为人工智能构建了一种更聪明的方法，使其能够从我们简单的“竖起大拇指”或“竖起大拇指向下”的反馈中学习，即使任务非常复杂。

技术摘要：从片段式偏好反馈中学习基于核的马尔可夫决策过程

问题表述
本工作解决了在片段式马尔可夫决策过程（MDP）设置下的基于人类反馈的强化学习（RLHF）问题。与智能体接收标量奖励的标准强化学习不同，这里的学习者仅接收二元偏好反馈。在每个片段 $k$ 中，学习者从共同起始状态部署两个策略 $\pi$ 和 $\pi'$ ，以生成两条轨迹 $\tau_k$ 和 $\tau'_k$ 。反馈由单个二元标签 $y_k \in \{0, 1\}$ 组成，指示哪条轨迹更受偏好。该偏好通过 Bradley–Terry–Luce（BTL）链接函数建模，应用于累积（未观测）奖励的差值：
$y_k \sim \text{Ber}\left(\sigma\left(\sum_{h=1}^H r_h(z^k_h) - \sum_{h=1}^H r_h(z'^k_h)\right)\right)$
其中 $\sigma$ 为 sigmoid 函数。目标是学习一个策略，使其最大化价值函数 $V^\pi_1$ ，同时最小化累积遗憾，定义为最优值与已部署策略的平均值之间的差值。

该设置假设了一个核 MDP结构，其中奖励函数 $r_h$ 和转移算子 $P_h$ 是由已知核 $k$ 诱导的再生核希尔伯特空间（RKHS） $\mathcal{H}_k$ 中的元素。具体而言，作者聚焦于Matérn 核族，该族能够捕捉非线性结构，且其范数等价于索伯列夫空间（Sobolev spaces），从而提供了超越线性 MDP 的泛化能力。

方法论：PROSTO 算法
作者提出了PROSTO（基于采样的轨迹诱导乐观性的偏好正则化优化）。该算法按片段运行，并采用了一种针对偏好反馈和核函数近似进行调整的值迭代方法。

通过正则化核逻辑回归（KLRR）进行奖励估计：
由于反馈是轨迹级且二元的，奖励向量 $\theta$ 使用带有范数加权惩罚的最大似然估计进行估算。估计量 $\hat{\theta}_k$ 最小化观测偏好的负对数似然加上正则化项 $\tau \|\theta\|^2_{\mathcal{H}_k}$ 。该回归的协变量为轨迹差异特征 $\phi_i = \sum_{h=1}^H \phi(z^i_h) - \phi(z'^i_h)$ 。
通过随机高斯过程扰动进行探索：
为了在不预先知晓转移动态（这阻止了确定性椭圆奖励的使用）的情况下确保轨迹层面的充分探索，PROSTO 采用随机探索。探索噪声向量 $\epsilon_k$ 从高斯过程（GP）中采样，其协方差结构依赖于轨迹差异的经验协方差。该噪声被添加到奖励估计中以诱导乐观性。
通过核岭回归（KRR）进行价值函数估计：
价值函数通过递归方式估计。下一状态的期望值使用标准核岭回归在转移样本上进行近似。最终的 Q 函数估计 $\hat{Q}^k_h$ 结合了奖励估计（KLRR + GP 噪声）和转移估计（KRR），并受截断约束以确保有界性。
策略执行：
学习者选择两个策略 $\pi$ 和 $\pi'$ ，它们分别对其各自的乐观 Q 函数估计是贪婪的。执行这些策略以生成下一个片段的轨迹和偏好反馈。

关键技术贡献与挑战
本文确定了将核 MDP 与轨迹级偏好反馈相结合所特有的三个主要技术挑战，并提供了新颖的解决方案：

控制对数覆盖数： 在核 MDP 中，价值函数类的对数覆盖数随覆盖网格 $\epsilon$ 的倒数呈多项式增长，并依赖于估计量的 RKHS 范数。与覆盖数随片段数量呈对数增长的线性 MDP 不同，核设置可能导致如果估计量范数增长过大，遗憾界将变得毫无意义。
- 解决方案： 作者仔细调整 KLRR 中的正则化参数 $\tau$ ，以显式控制奖励估计量的 RKHS 范数。这使得诱导函数类的覆盖数保持较小，从而能够得出有意义的置信界。
具有非平滑噪声的轨迹级探索： 标准的探索奖励（椭圆奖励）需要完整的轨迹信息，这在决策时刻是不可用的。通过 GP 采样的随机探索被使用，但来自 Matérn 核的 GP 样本路径通常不属于相应的 RKHS（它们平滑度较低）。这使得标准的覆盖界不再适用。
- 解决方案： 作者推导了针对后验 GP 样本路径的新高概率高斯覆盖界。他们利用 van der Vaart 和 van Zanten [2008] 的结果表明，虽然 GP 路径位于 RKHS 球之外，但它们以高概率位于一个适当扩大的 RKHS 球的 $\epsilon$ 邻域内（在 $\ell_\infty$ 范数下）。这使得推导遗憾分析所需的覆盖界成为可能。
平衡正则化与覆盖参数： 调整正则化参数（奖励的 $\tau$ ，转移的 $\lambda$ ）和覆盖网格 $\epsilon$ 并非易事。较小的 $\epsilon$ 减少了误设误差，但增大了覆盖数；较大的 $\epsilon$ 则反之。
- 解决方案： 作者将 $\tau$ 、 $\lambda$ 和 $\epsilon$ 联合优化为片段数量 $K$ 和核平滑参数 $\beta_p$ 的函数。这种平衡确保了置信宽度足够紧密以实现次线性遗憾，同时控制了函数类的复杂度。

结果与遗憾界
本文证明了 PROSTO 对于 Matérn 族中的所有核都能实现次线性累积遗憾界。具体而言，遗憾 $R(K)$ 的规模为：
$R(K) \leq \tilde{O}\left( \kappa_Z \max\left( H^{2.5} K^{1 - \frac{(\beta_p-1)^2}{2\beta_p(\beta_p+1)}}, H^3 K^{1 - \frac{\beta_p-1}{2(\beta_p+1)}} \right) \right)$
其中 $\beta_p > 1$ 是核的特征值衰减参数， $H$ 是视界， $\kappa_Z$ 是最大逆链接梯度。 $K$ 的指数严格小于 1，意味着随着 $K \to \infty$ ，策略收敛至最优策略。

此外，该算法在计算上是高效的，其运行时间关于片段数量 $K$ 是多项式级的。这使其区别于先前关于具有标准奖励的核 MDP 的工作（例如 Maran 等人 [2024b]），后者虽然实现了次线性遗憾，但依赖于域划分或优化预言机，而在一般核设置下，这些方法尚未被证明在多项式时间内是可计算的。

意义与主张
作者声称，这项工作提供了首个针对核 MDP 中基于偏好的 RL 的算法，该算法在计算高效的同时，为整个 Matérn 核族实现了可证明的次线性遗憾。

理论新颖性： 这项工作弥合了基于偏好的 RL（通常处理表格或线性设置）与基于核的函数近似（处理非线性设置）之间的差距。它引入了在值迭代背景下处理 GP 探索噪声缺乏平滑性的新技术。
计算效率： 与先前针对平滑 MDP 的无遗憾算法（可能需要不可行的优化）不同，PROSTO 提供了多项式时间的实现。
局限性： 作者承认，遗憾界可能不是阶最优的。他们指出，域划分方法目前在某些核设置下提供阶最优界，但由于转移的随机性阻碍了局部贝尔曼算子的估计，这些方法与轨迹级反馈不兼容。

本文结论认为，虽然推导出的遗憾界是次线性的，但实现阶最优界仍然是一个未解决的问题，可能需要超越当前域划分或均匀覆盖方法的根本不同的技术。