基于拼图定理的逆最优控制与贝尔曼方程

《Communications in Nonlinear Science and Numerical Simulation》：Inverse Optimal Control and the Bellman Equation via the Collage Theorem

　　

## 摘要

本文从不动点角度处理动态规划中的反问题。折扣马尔可夫决策过程的贝尔曼最优算子在有界价值函数巴拿赫空间上是一个压缩映射，因此其唯一不动点——最优价值函数——正是拼版法在微分方程和积分方程反问题中所利用的严格意义上的正问题解。在建立了适定性（存在性、唯一性、几何价值迭代、验证定理以及可计算的括号界限）以及最优价值函数对奖励参数和折扣因子的利普希茨敏感性之后，我们提出了从观测行为中恢复未知奖励的反问题。我们证明了贝尔曼拼版定理及其匹配的反拼版界，表明将观测数据代入算子后得到的贝尔曼残差，至多乘以显式常数 1/(1???) 和 1/(1+??)，即等价于真实误差——并且关键的是，对每个候选奖励无需进行价值迭代。随后我们分析了可识别性（策略内奖励的精确恢复、策略外奖励的不等式约束，以及使仅策略恢复成为不适定问题的势整形规范自由度），以及当奖励对参数仿射时拼版泛函所继承的凸优化结构。

## 引言

动态规划建立在贝尔曼最优方程 [1] 之上：折扣马尔可夫决策过程的最优价值函数是一个压缩算子的唯一不动点，此类过程的基础理论在 [2]、[3]、[4] 中得以发展。这种压缩结构正是拼版法处理反问题所适用的场景。该方法起源于昆泽与弗尔切 [5] 对微分方程的研究——其中解是皮卡算子的不动点——并在 [6] 中得到系统发展；其核心观察是：候选算子将目标移动的距离（拼版距离）界定了目标到真实不动点的距离，因此反问题可以通过最小化这个可计算的替代量来求解。从观测到的最优行为中恢复未知奖励的问题称为逆向强化学习，由 Ng 和 Russell [7] 提出，并由 Abbeel 和 Ng [8] 扩展至学徒学习。在本文中，我们通过拼版的视角处理逆向最优控制：观测数据的贝尔曼残差扮演了拼版距离的角色，最小化它可以恢复奖励，而无需对每个候选进行价值迭代。

动机既有概念层面的也有计算层面的。在概念上，将逆向强化学习表述为拼版问题将其与微分方程和积分方程反问题的既有理论统一起来，并提供了该文献长期提供的东西：具有显式常数的严格界，认证小残差蕴含精确解，以及匹配的下界，表明拟合差时残差不可能小。在计算上，收益是决定性的。大多数逆向强化学习方法需要对每个候选奖励求解或重新求解正向动态规划；拼版表述用单个关于奖励参数仿射的贝尔曼残差替代了该内部求解过程，将恢复问题转化为一个凸二次规划。在此过程中，该框架揭示了问题的可识别性结构——策略内的精确恢复、策略外的不等式约束，以及使仅策略恢复不适定的势整形规范自由度——并表明所得估计量是无偏的且在观测价值函数的加性噪声下是稳定的。

在引言之后，第 2 节回顾折扣马尔可夫决策过程和贝尔曼算子。第 3 节处理正问题，建立存在性、唯一性、几何价值迭代、可计算的后验界以及最优价值函数对奖励和折扣因子的利普希茨敏感性。第 4 节提出反问题并证明贝尔曼拼版定理和反拼版定理。第 5 节分析可识别性和势整形规范自由度。第 6 节发展拼版泛函在仿射奖励下继承的凸最小二乘结构，包括与最小二乘时序差分学习和 Tikhonov 正则化的联系。第 7 节给出若干数值示例——包括噪声鲁棒性和 Tikhonov 正则化研究——以展示该方法，第 8 节给出结论性评论。

## 背景与记号

我们首先固定全文使用的设定和记号。设 ?? 为状态空间，?? 为动作空间，二者均为可测的。折扣马尔可夫决策过程（MDP）由转移核 p(·|s, a)（对每个 (s, a) 是 ?? 上的概率测度）、依赖于参数 ??∈Λ??? 的奖励函数 ??:??×??×Λ→?，以及折扣因子 γ∈[0, 1) 组成。

设 ?(??) 为有界可测函数 ??:??→? 在 supremum 范数 ∥??∥∞=sup_{??∈??}|??(??)| 下的空间；它是一个巴拿赫空间。我们

## 正问题

在提出反问题之前，我们首先记录正问题的适定性理论以及我们需要的敏感性估计。由于最优算子是一个压缩映射，正问题以最强的意义是适定的：最优价值函数存在、唯一，且可通过价值迭代以几何收敛速率计算到任意精度。

**定理 3.1 存在性、唯一性、价值迭代** 在 (B1)–(B2) 条件下，??_λ 具有唯一不动点 ??★_λ∈?(??)，即最优价值函数，其由贝尔曼方程刻画

## 反问题与拼版定理

有了正向理论，我们便准备提出反问题并推导其核心估计。数据由动力学和折扣因子组成，以及它们所诱导的最优行为的信息；未知量为奖励。

**问题 1 逆向最优控制 / 逆向强化学习** 已知动力学 p 和折扣 γ。从观测到的专家行为——观测到的价值函数 ??_obs∈?(??)，或观测到的（假设为最优的）策略 π_obs，或两者——恢复一个奖励参数 λ，使得观测行为

## 可识别性

反问题可能以正问题没有的方式出现不适定性：不同的奖励可能诱导相同的观测行为。我们精确刻画这种歧义性；它正是正则化必须解决的唯一性问题。

**定理 5.1 从观测价值函数的可识别性** 设 ??_obs=??★_λ? 精确成立，对应某个真实奖励 r(·, ·; λ?)，关联最优策略 π?（观测到）。则对每个状态 s，策略内的奖励被精确确定：

??(s, π★(s); λ?) = ??_obs(s) ? γ(P_{π★(s)} ??_obs)(s)

而对 ?? ≠ π?(s)，仅有不等式 ??(s, ??; λ?) ≤ ??

## 从拼版定理到计算

拼版界和反拼版界将逆向最优控制简化为单个残差泛函的最小化。现在我们描述当奖励线性参数化时该残差所继承的凸结构，逆向强化学习情形中可用的闭式最小二乘解，以及解决可识别性规范自由度的 Tikhonov 正则化。

设标准线性参数化，奖励特征为 ???, …, ???:??×??→?，

??(s, ??; λ) = ∑_{??=1}^{??} ??_?? ??_??(s, ??)

## 数值示例

我们说明贝尔曼拼版法在两个有限马尔可夫决策过程上的表现。在这两个过程中，动力学 p 和折扣 γ 已知；专家最优价值函数 V_obs 和策略 π_obs 由对地面真实奖励进行价值迭代生成后交给反演。奖励是线性参数化的，??(s; λ) = ∑_?? ??_?? ??_??(s)，通过推论 6.2 的策略评估拼版最小二乘恢复，其步骤收集于算法 1。

**示例 1 链式 MDP** 第一个过程是一条包含 ??=21 个状态 ?? 的链

## 结论性评论

我们将逆向最优控制重新表述为贝尔曼算子的拼版问题。由于该算子在价值函数空间上是一个压缩映射，代入观测数据后留下的贝尔曼残差，至多乘以显式常数 1/(1?γ) 和 1/(1+γ)，即等价于到最优价值函数的真实距离——这就是动态规划的拼版定理及匹配的反拼版界。当奖励对其参数仿射时，该残差是凸二次的，因此奖励

*未引用的浮动图* 图 2，图 4。

**CRediT 作者贡献声明** H. Kunze：写作 – 审阅与编辑，写作 – 原稿撰写，形式分析。D. La Torre：写作 – 审阅与编辑，写作 – 原稿撰写，形式分析。

**利益冲突声明** 作者声明他们没有已知的竞争经济利益或个人关系可能影响本文所报告的工作。

H. Kunze | D. La Torre 圭尔夫大学数学与统计系，加拿大圭尔夫