Reinforcement Learning with Pairwise Preferences in Long-Term Decision Problems

技术摘要：长程决策问题中的成对偏好强化学习

问题定义
传统的强化学习（RL）将目标表述为在马尔可夫决策过程（MDP）中最大化标量奖励函数的期望值。然而，在许多应用场景中（例如大语言模型（LLM）的微调），指定成对偏好（例如“轨迹 A 比轨迹 B 更好”）通常比定义一个标量奖励更自然且可行。现有的处理成对偏好强化学习的方法通常通过推断奖励函数或直接针对偏好进行优化，但存在两个关键局限性：

1. 它们依赖于有限且固定的时间范围，这对于不以固定步数终止的长期决策问题而言是不切实际的。
2. 它们缺乏关于平稳马尔可夫策略相对于历史相关策略具有最优性的理论保证，而这是标准 MDP 理论的基石。

此外，标准方法往往无法捕捉非传递性偏好（例如孔多塞悖论），即一组或多特征评估的聚合偏好并不形成传递性的排序。

方法论：马尔可夫决策竞赛 (MDC)
作者提出了一种名为马尔可夫决策竞赛 (MDC) 的新问题模型来填补这些空白。一个 MDC 由有限环境 $(S, A, P, \mu)$ 和马尔可夫偏好边际 $M: (S \times A) \times (S \times A) \to \mathbb{R}$ 定义。其目标是找到一个策略 $\pi$，使其在面对任何其他策略 $\pi'$ 时，最大化平均偏好边际，该目标被公式化为一个零和博弈：
$$\max_{\pi} \min_{\pi'} \sum_{s,a} \sum_{s',a'} x_\pi(s,a) x_{\pi'}(s',a') M((s,a), (s',a'))$$
其中 $x_\pi$ 代表极限平均状态-动作频率（占用度量）。

为了确保在无限时界设置下的理论可处理性，作者假设转移概率函数是**单链（unichain）且非周期（aperiodic）**的。在这些条件下，他们证明了历史相关策略的占用度量集合等价于平稳确定性策略占用度的凸包。

核心贡献

1. 平稳策略的最优性： 本文证明了在有限单链 MDC 中，平稳随机策略在所有历史相关策略中都是最优的。这证明了将搜索空间限制在马尔可夫策略中的合理性，弥合了偏好强化学习中理论与实践之间的鸿沟。
2. 计算复杂度： 作者展示了求解精确 MDC 的复杂度属于 P（多项式时间）。具体而言，他们构建了一个包含 $|S||A| + |S| + 1$ 个变量和 $2|S||A| + |S| + 1$ 个约束条件的线性规划。尽管 MDC 是支持非传递性偏好的更严格的泛化，但其复杂度与标准的平均奖励 MDP 相当。
3. 对冲策略迭代 (HPI)： 引入了一种近似迭代算法——对冲策略迭代 (HPI)。它利用 Hedge 算法，根据“边际价值”（累积偏好边际）来更新决策规则。
   • 收敛性： HPI 以 $O(1/\sqrt{K})$ 的次线性速率（其中 $K$ 为迭代次数）收敛到最优策略。
   • 可扩展性： 作者推导出了 HPI 的策略梯度形式及其深度学习实现（算法 3），该实现利用缓冲区和价值函数近似，使其适用于高维环境。

实验结果
作者在 13 个具有长时界（2048 步）的高维任务（使用 Mujoco-v5 套件）中，将 HPI 及其剪切变体（HPI-Clip）与自我博弈偏好优化 (SPPO) (Swamy et al., 2024) 进行了对比评估。

• 设置： 任务包括标准的连续控制问题（其偏好由奖励差异推导而来）以及具有显式非传递性偏好边际的“Mujoco-NT”任务（例如“三选二”规则）。
• 性能： 在 13 个任务中的 12 个任务中，HPI 和 HPI-Clip 表现出显著更高的学习效率（以回合回报的曲线下面积或反转最优性差距来衡量）相比于 SPPO。
• 消融实验： 即使偏好模型是从离线数据中学习的，这些结果依然成立。

意义与主张
本文声称，长程决策问题中的成对偏好强化学习比此前认为的更具可处理性。通过引入 MDC 模型，作者提供了一个框架，在该框架下：

• 平稳策略在理论上是充分的，从而无需复杂的历史相关策略。
• 即使存在非传递性偏好，该问题在计算上仍然是高效的（属于 P）。
• 实用的算法 (HPI) 可以扩展到高维、长时界的复杂问题，并优于现有的最先进方法。

作者指出，虽然这些结果对于 LLM 在长时界任务中的应用前景广阔，但仍需进一步研究以确定何时“偏好边际学习”优于“奖励学习”，以及这些方法在实践中如何有效地对齐语言模型。这项工作旨在将成对偏好强化学习的理论与实践紧密结合。