最大因果熵逆向强化学习

发表于

最大因果熵逆向强化学习

  1. 马尔科夫决策过程 Markov decision process (MDP)

定义1： 马尔可夫决策过程定义为一个元组\(M = \left( S,A,P_{T},R,P_{0},S_{\phi} \right)\)

\(S\)：有限或无限状态集合

\(A\)：有限或无限的动作集合

\(P_{T}\)：状态转移概率分布，\(P_{T}(S_{j}|A_{i},S_{i})\)表示智能体在状态\(S_{i}\)采取动作\(A_{i}\)后转移到状态\(S_{j}\)的概率

\(R\)：\(R(S,A)\)表示立即奖励函数

\(S_{\phi}\)：最终状态集合

  1. 强化学习 Reinforcement Learning（RL）

在RL中，其目标在于学习到一个策略\(\pi\)，从而指导智能体的MDP，其目的在于最大化累计奖励函数，为了用公式表达这个过程，我们需要定义状态值函数以及状态-动作值函数：

定义2： 状态值函数，表示从某一状态开始，采用策略\(\pi\)获得的未来预期奖励。在离散且符合MDP的情况下，可以定义为以下迭代公式：

\[\begin{matrix} V_{\pi}(S) = \sum_{A \in \mathcal{A}}^{}\left\lbrack \pi\left( A \middle| S \right)\left\lbrack R(S,A) + \sum_{\begin{matrix} S^{'} \in S \\ \ \\ \end{matrix}}^{}{P_{T}\left( S^{'} \middle| A,S \right)V_{\pi}\left( S^{'} \right)} \right\rbrack \right\rbrack \tag{1} \\ \end{matrix}\]

定义3： Q函数，也被称作动作-状态值函数,包含依据策略\(\pi\)在状态\(s\)采用动作\(a\)后获得的未来预期奖励。在离散且符合MDP的情况下，可以定义为以下公式：

\[\begin{matrix} Q_{\pi} = \ R(S,A) + \sum_{\begin{matrix} S^{'} \in S \\ \ \\ \end{matrix}}^{}{P_{T}\left( S^{'} \middle| A,S \right)V_{\pi}\left( S^{'} \right)} \tag{2} \\ \end{matrix}\]

(2)式的第一项为在状态\(s\)采取动作\(a\)后的立即奖励，第二项为转移到状态\(s^{'}\)后的未来预期奖励。由此，可对式（1）进行重写为如下格式

\[\begin{matrix} V_{\pi}(S) = \sum_{A \in \mathcal{A}}^{}{\pi\left( A \middle| S \right)Q_{\pi}(S,A)} \tag{3} \\ \end{matrix}\]

定义4： 最优确定性策略表示为Q函数取最大值时的动作\(a\)，定义为如下公式：

\[\begin{matrix} {\overline{\pi}}^{*}(S) = \underset{A \in \mathcal{A}}{argmax}Q_{\pi}(S,A) \tag{4} \\ \end{matrix}\]

马尔科夫决策过程可以映射为agent在一个grid world中通过强化学习来抵达目的地，其目标是：学习一个最优策略，找到当前状态下采取哪个动作能够获得最大的奖励值，以此类推形成一组最优动作序列。当该动作有助于抵达目标状态则指定一个正向的奖励值，否则是负向的惩罚值，最后确保累计得到的奖励值是最大化的。但是，当agent在完成比较复杂的任务时，这个过程中的奖励函数是很难指定，例如行人的出行决策，可能受到多种因素的影响，无法显示给定，因此我们希望找到一种方法可以推导从观测到的行人出行序列中推到出这个奖励函数，由此引出逆向强化学习。

  1. 逆向强化学习 Inverse Reinforcement Learning（IRL）

逆向强化学习假设输入元组为\(MDP/R\)，也就是\(MDP\)中没有奖励函数\(R\)。相反我们拥有一系列观测轨迹（序列、行为）：\(\mathcal{B = \{}B_{1},B_{2},\ldots,B_{n}\}\)，其中\(\mathcal{B \ni}B = \left( \left( S_{1},A_{1} \right),\ldots,\left( S_{mB},A_{mB} \right) \right) \in (S \times A)^{mB}\)。逆向强化学习的目的在于通过已知观测轨迹，学习到激励agent产生如此轨迹的奖励函数。

特征匹配IRL算法

\(f_{s,a}:S \times A\)为给定观测轨迹元组的特征函数,通过多条已知观测轨迹，我们可以计算出经验特征值\(f_{\mathcal{B}} = \frac{1}{\left| \mathcal{B} \right|}\sum_{B\mathcal{\in B}}^{}f_{B}\)，其中\(f_{B} = \frac{1}{|B|}\sum_{(S \times A) \in B}^{}f_{S,A}\)。假设IRL学得了一个奖励函数\(\widehat{R}\)，同时RL算法通过\(MDP/R \cup \widehat{R}\)学到了策略函数\(\widehat{\pi}\)，那么我们可以假设IRL满足以下约束：

\[\begin{matrix} E\left\lbrack f_{s,a} \middle| \widehat{\pi} \right\rbrack = f_{\mathcal{B}} \tag{5} \\ \end{matrix}\]

因此，特征匹配IRL算法（学徒算法、最大边际效应算法等）会通过以下两步进行学习直至收敛：

  1. 利用RL算法，通过当前奖励函数\(\widehat{R}\)学习到策略函数\(\widehat{\pi}\)

  2. 通过衡量当前策略函数\(\widehat{\pi}\)生成的轨迹与已知轨迹的损失值来更新奖励函数\(\widehat{R}\)

最大因果熵逆向强化学习 Maximum Causal Entropy Inverse Reinforcement Learning(MaxCausalEnt IRL)

特征匹配的IRL算法是病态的算法，对于同一系列轨迹可能存在多种不同可解释的奖励函数，为了解决奖励函数与观测轨迹之间的模糊性，MaxCausalEnt通过引入最大熵原理来解决这一问题。举例来说，对于观测轨迹中没有出现过的状态，MaxCausalEnt IRL算法对于未知动作的分配应当是等可能的。

对于因果熵，我们首先考虑因果策略模型 \(\pi(A_{t}|S_{1:t},\mathcal{A}_{1:t - 1})\) 和标准策略模型 \(\pi(A_{t}|S_{t})\),区别在于因果策略模型认为某一动作的选择与之前所有的动作和状态均有关而标准策略模型认为只和当前状态有关。然而，尽管因果假设更加强大，在IRL中完全应用因果条件会破坏Markovian假设，从而导致求解问题更加复杂。综上，我们可以将继承因果模型的思想，提出如下约束:

\[\begin{matrix}\pi\left( A_{t} \middle| S_{1:t},\mathcal{A}_{1:t - 1} \right) = \pi\left( A_{t} \middle| S_{t} \right) \tag{6} \\ \end{matrix}\]

接下来对该问题的基础参数进行建模：

\[\begin{matrix} R_{\theta}(S,A) = \theta^{T}f_{S,A} \tag{7} \\ \end{matrix}\]

\[\begin{matrix} V_{\pi\theta}^{soft}\left( S_{t} \right) = log\sum_{A_{t}\mathcal{\in A}}^{}e^{Q_{\pi\theta}^{soft}\left( A_{t},S_{t} \right)} \tag{8} \\ \end{matrix}\]

\[\begin{matrix} Q_{\pi\theta}^{soft}\left( A_{t},S_{t} \right) = R_{\theta}\left( S_{t},A_{t} \right) + \sum_{S^{'} \in S}^{}{P_{T}(S^{'}|A_{t},S_{t})V_{\pi\theta}^{soft}\left( S^{'} \right)} \tag{9} \\ \end{matrix}\]

\[\begin{matrix} \pi_{\theta}\left( A_{t} \middle| S_{t} \right) = e^{Q_{\pi\theta}^{soft}\left( A_{t},S_{t} \right) - V_{\pi\theta}^{soft}\left( S^{'} \right)} \tag{10} \\ \end{matrix}\]

\[\begin{matrix} \mu(\pi) = E\left\lbrack \sum_{t = 0}^{\infty}{\gamma^{'}f_{S_{t},A_{t}}|\pi} \right\rbrack \tag{11} \\ \end{matrix}\]

当给定m条观测轨迹时，依据式（11）观测轨迹的特征期望为：

\[\begin{matrix} \widehat{\mu_{E}} = \frac{1}{m}\sum_{i = 1}^{m}{\sum_{t = 0}^{\infty}{\gamma^{'}f_{S_{t},A_{t}}^{i}}} \tag{12} \\ \end{matrix}\]

从概率的角度理解该问题，可认为存在一个潜在的概率分布，在该分布下产生了观测专家轨迹，结合最大熵原理，可以写出如下的约束模型：

\[\max{\ - plogp}\]

\[s.t.\ \sum_{Path\ B}^{}{P(B)\mu(B) = \widehat{\mu_{E}}}\]

\[\begin{matrix} \sum_{}^{}P = 1 \tag{12} \\ \end{matrix}\]

利用拉格朗日法，该最优化问题可以转化为：

\[\begin{matrix} \min L = \sum_{B}^{}{plogp} - \sum_{j = 1}^{n}{\theta_{j}\left( p\mu_{j} - \widehat{\mu_{E}} \right) - \theta_{0}\left( \sum_{}^{}p - 1 \right)} \tag{14} \\ \end{matrix}\]

其中，拉格朗日函数的参数\(\lambda\)恰好是奖励函数的参数\(\theta\)。此外对于MDP问题来说，这个问题是凸函数，因此其最优解可以通过梯度优化的方式得到，但利用最大似然法求解式（14）中的参数时，会遇到未知的配分函数\(e^{(1 - \lambda_{0})}\)，因此改为次梯度的方法求解:

\[{ \nabla L_{Dual}(\theta) = f_{\mathcal{B}} - E\left\lbrack f(S,A) \middle| {\widehat{\pi}}_{\theta} \right\rbrack }{\begin{matrix} = f_{\mathcal{B}} - \sum_{(S,A)}^{}{P(S){\widehat{\pi}}_{\theta}\left( A \middle| S \right)f_{S,A}} \\ \end{matrix} }\begin{matrix} = f_{\mathcal{B}} - \sum_{(S,A)}^{}{D_{S}{\widehat{\pi}}_{\theta}\left( A \middle| S \right)f_{S,A}} (16) \\ \end{matrix}\]

次梯度为观测轨迹与生成轨迹的经验特征期望的差值,其中\(D_{S}\)为状态\(S\)的访问频次，以此来替代状态访问频率\(P(S)\)。同过式（16）我们可以知道，为了计算次梯度，我们首先需要计算两个变量\(D_{S}\)和\({\widehat{\pi}}_{\theta}\)，因此MaxCausalEnt IRL算法的顶层设计伪代码如下：

Figure1 顶层设计伪代码

  1. 最大熵逆向强化学习算法框架

最大熵逆向强化学习的输入为：

  1. \(MDP/R\)（状态空间\(S\)，动作空间\(A\)，状态转移概率\(P_{T}\),最初状态分配\(P_{0}\),最终状态集合\(S_{\phi}\)）

  2. \(\mathcal{B}\)(可观测轨迹、序列)

  3. \(\mathcal{F =}\forall_{(S,A) \in S \times A}f_{S,A}\)(状态动作对的特征函数)

首先我们要进行梯度下降的计算，为了标记的简化，我们对式（16）进行如下简化定义：

\[\begin{matrix} \nabla_{\theta}F(S,A) = D_{S}{\widehat{\pi}}_{\theta}\left( A \middle| S \right)f_{S,A} \tag{17} \\ \end{matrix}\]

我们接下来定义梯度下降算法作为算法1的详细版本，其伪代码版本如下：

Figure2 梯度下降算法

在这个算法中，我们引入了两个超参数：

  1. \(\lambda\)-学习速率，通过交叉验证选择

  2. \(t\)-学习速率衰减，算法第10行说明随着迭代次数的增加，学习速率不断衰减，可以使得算法更易收敛

在算法4-10行中，我们通过每一状态和动作对的加和来计算梯度，如果状态和动作空间不离散，或者空间过大难以迭代时，我们可以采取小批量随机梯度下降的算法，虽然每次迭代收敛会变慢，但整体算法时间会缩短。

在算法中，我们并不知道\(\nabla_{\theta}F(S,A)\)是如何计算的，其中涉及到\(D\)和\({\widehat{\pi}}_{\theta}\)两个参数，在式（8）（9）（10）中可以看出，如果我们知道了\(V_{ {\widehat{\pi} }_{\theta}}^{soft}\)，我们就可以计算\({\widehat{\pi}}_{\theta}\)，接下来我们介绍计算状态值函数\(V_{ {\widehat{\pi} }_{\theta} }^{soft}\)的算法3，在此之前首先给出softmax的定义公式：

\[\begin{matrix} soft\max(x,y) = \log\left( e^{x} + e^{y} \right) = \max(x,y) + \log\left( 1 + e^{\max(x,y) - \min(x,y)} \right) \tag{18} \\ \end{matrix}\]

Figure3 状态值函数计算

在上述算法中，我们引入了一个新的超参数\(\phi\)-表示种植状态的奖励函数，对于拥有一系列\(S_{\phi}\),\(\phi\)可以被定义为如下公式：

\[\begin{matrix} \phi(S) = \left\{ \begin{matrix} - \infty,\ \ \ \ \ \ \ \ if\ S \notin \mathcal{S}_{\phi} \\ 0,\ \ \ \ \ \ \ \ \ othterwise\ \\ \end{matrix} \right.\ \tag{19} \\ \end{matrix}\]

结合式（19）和算法8-12行，我们对该算法核心关键要素进行总结，即从最终状态开始迭代，不断为每个状态进行赋值，直至算法收敛。由于非最终状态的初始值设置为\(- \infty\)，因此在每一次迭代中，只有通过潜在动作与有值的状态相接的状态才会更新状态值，通过不断迭代，寻找每一状态的值函数，当值函数的变化小于临界值时，算法结束。

在算法三结束后，我们通过式子（8）-（10）的计算，可以得到\({\widehat{\pi}}_{\theta}\)的计算值，为了计算式（17），我们还需要通过\({\widehat{\pi}}_{\theta}\)计算状态访问频次，由此引出算法4，其伪代码如下：

Figure4 状态访问频次计算

  1. 最大熵深度逆向强化学习

在算法2-4中，我们利用全部状态和动作进行循环，求得\(\nabla F,D_{S},V(S)\)等参数值，从这样的算法流程我们可以看出传统IRL在表征能力上具有一定的局限性，只能够应用在规模小、离散的任务上，而深度神经网络可以针对这个问题进行很好的改进。由于深度神经网络对高层非线性函数具有较好的表征能力，利用深度神经网络近似回报函数，可以通过神经元分层结构中的许多非线性结果的组合，使得其更贴近真实的奖励函数，从而提高IRL的非线性表征能力，同时深度神经网络对于大规模数据具有良好的算法处理能力，解决了IRL只能应用在小规模、离散任务的缺点。

  1. 总结

最大熵逆向强化学习是建模序列化行为的重要工具，以马尔可夫决策过程为基准同时通过观测轨迹（序列、行为）学习奖励函数，进而对未来的轨迹进行预测，同时引入最大熵原理以解决多奖励函数均可解释可观测轨迹的两义性问题。

参考文献

[1] Heim E. A Practitioner's Guide to Maximum Causal Entropy Inverse Reinforcement Learning, Starting from Markov Decision Processes[Z].CARNEGIE-MELLON UNIV PITTSBURGH PA PITTSBURGH United States, 2019.

[2] 陈希亮, 曹雷, 何明, 等. 深度逆向强化学习研究综述[J].计算机工程与应用, 2018,54(05):24-35.