论通用强化学习目标的可学习性

强化学习要在未知环境中让智能体学出决策策略，传统做法是把目标写成 reward function，并据此获得高概率学到近最优策略的保证，也就是 PAC-learnability。问题在于 reward function 常常只是真实目标的不完美替代物，会引发 reward hacking，并削弱上述保证。这篇由 Cambridge Yang 在 MIT 完成、Michael Carbin 指导的博士论文，正面处理“reward 之外的一般强化学习目标能否被清晰指定、能否被学习”这一基础问题。在 reward 设计与对齐讨论越来越关注目标错配的当下，这类形式化工作值得细看。

论文的范围不是单一算法，而是按表达力递增排列的三类目标：Linear Temporal Logic（LTL）目标、computable objectives，以及 non-computable objectives。方法上，它围绕 specification 与 learnability 做形式化定义和定理证明，而不是依赖数据集或基准实验。具体地，论文先分析 LTL 目标的 PAC 可学性，再给出更一般的可学性判据，最后用 limit PAC-learnability 处理非计算目标。从给定材料看，这是一篇理论驱动的博士论文，核心产出是定义、判据和充分条件。

在 LTL 这一层，论文把传统标量 reward 扩展为对行为的时间性规格，并给出一个明确边界：只有 finitary LTL objectives 是 PAC-learnable。相对地，infinite-horizon LTL objectives 在 PAC-MDP 框架下是 inherently intractable 的。换句话说，目标是否只涉及有限时间范围，会直接改变它在既有 PAC-MDP 框架中的可学习性结论。这个结果把“时间性目标好不好学”从直觉讨论推进到可证明的分类。

进一步，论文建立了一个一般判据：一个目标如果是 continuous 且 computable，那么它是 PAC-learnable。这个判据既能用来判断已有目标类别的 PAC 可学性，也能指导设计新的、可学习的目标规格。对于 non-computable objectives，论文没有承诺直接学习，而是提出 limit PAC-learnability：用一串 computable、PAC-learnable 的目标去逼近它。论文还用 computable functions 的 nested limits 给出非计算目标的 universal representation，并给出 limit PAC-learnability 成立的充分条件。

这些结论的意义在于，目标规格不必被 reward function 锁死，时间性规格和算法可定义的目标都可以被纳入可学性分析。对实践者来说，“continuous 且 computable”可以当作设计目标规格时的一个可学性检查点，而 finitary 与 infinite-horizon 的分界提醒我们：时间范围的选择不是无关紧要的实现细节。对 reward hacking 的回应也在这里：论文不是给出一个工程补丁，而是试图说明哪些非 reward 目标在原则上可以被可靠地学习。非计算目标则被放在极限逼近的框架下，说明完全可计算性不是讨论可学性的唯一入口。

适合读这篇论文的，是关心强化学习理论、目标规格、形式化安全与对齐的研究者和高年级学生；读完可以拿到一张按表达力分层的目标可学性地图，以及 LTL、computable、non-computable 三类目标各自的条件与边界。需要说明的是，给定材料显示这篇论文以定义、定理和充分条件为主，没有提供实验评估或基准数据，因此它回答的是“原则上可不可学”，而不是“某个任务上效果如何”。另外，non-computable 部分给出的是 limit PAC-learnability 的充分条件，infinite-horizon LTL 的不可行性也是在 PAC-MDP 框架内成立；这些边界在阅读时不应被外推成对所有学习框架的绝对结论。

On the Learnability of General Reinforcement-learning Objectives by Cambridge Yang B.S, University of California, Berkeley (2017) S.M., Massachusetts Institute of Technology (2020) Submitted to the Department of Electrical Engineering and Computer Science in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY at the MASSACHUSETTS INSTITUTE OF TECHNOLOGY May 2025 © 2025 Cambridge Yang. This work is licensed under a CC BY-NC-ND 4.0 license. The author hereby grants to MIT a nonexclusive, worldwide, irrevocable, royalty-free license to exercise any and all rights under copyright, including to reproduce, preserve, distribute and publicly display copies of the thesis, or release the thesis under an open-access license. Authored by: Cambridge Yang Department of Electrical Engineering and Computer Science February 28, 2025 Certified by: Michael Carbin