动机. 现在已经有了离散时间，连续空间和行动的动态系统，其中动态规律已知，还有二次代价函数：
$$ x_{t+1} = f(x_t,u_t)$$
$$ V(x_1,\cdots,x_N)
= \sum_{t=0}^{H} x_t^{\intercal} Q x_t + u_t^{\intercal} R u_t$$
通常假设代价/奖励函数已知的，如在 AlphaGo 中：很多时间的代价是 $0$，在比赛结束时才会出现 $-1$ 和 $+1$. 然而，在很多情况下，关于代价函数自然的表达是非常难的，可能需要从数据中学习。从观测的行为中学习代价/奖励函数的问题被称为 inverse RL.
关键的假设是真实的奖励函数可以用一个已知特征的线性组合表示.
在直升机例子中，我们可以将代价矩阵 $Q$ 和 $R$ 看做是对角矩阵：
$$ Q=\begin{bmatrix}
q_1 & 0 & \ldots & 0\\
0 & q_2 & \ldots & 0\\
\vdots & \vdots & \ddots & \vdots\\
0 & 0 &\ldots & q_n
\end{bmatrix},R=\begin{bmatrix}
r_1 & 0 & \ldots & 0\\
0 & r_2 & \ldots & 0\\
\vdots & \vdots & \ddots & \vdots\\
0 & 0 &\ldots & r_n
\end{bmatrix}$$
设计代价矩阵 $ Q$ 和 $ R$ 就成了权衡不同的状态和行动变量的系数选择问题. 代价函数定义如下：
$$ x^{\intercal} Q x + u^{\intercal} R u = w^{*} \cdot \phi(x,u)~\mathrm{where}~w^{*} =\begin{bmatrix}q_1 \\
\vdots\\
q_n\\
r_1\\
\vdots\\
r_m\\
\end{bmatrix} \in \mathbb{R}^{m+n}$$
未知向量 $w^*$ 制定了不同的考量因素之间的相对权重.
学习目标. 策略 $\pi$ 的期望值可以写成：
$$
\begin{align}
\mathbb{E}_{x_0 \sim I}[V^\pi(x_0)] &=\mathbb{E} \Bigg[\sum\limits_{t=0}^{H}\mathcal{R}(x_t,u_t) \Bigg]=\mathbb{E}\Bigg[\sum_{t=0}^{H} w \cdot \phi(x_t, u_t) \Bigg] \\&=w \cdot \mathbb{E}\Bigg[\sum_{t=0}^{H} \phi(x_t,u_t) \Bigg]=w \cdot \mu(\pi)\end{align}$$
其中 $$ \mu(\pi) = \mathbb{E}[\sum_{t=0}^{H}\phi(x_t,u_t)]$$ 被称为特征期望. 因此值函数可以简洁地表示成 $ w$ 和策略特征期望的内积.
我们使用一些专家的策略 $ \pi_E$ 的演示来学习参数 $ w$，其中的特征期望为 $ \mu_E = \mu(\pi_E)$. 假设受限参数 $ w\in \mathbb{R}^k$ 满足 $ ||w||_1\leq 1$，则目标是找到策略 $ \tilde{\pi}$ 使得 $ ||\mu(\tilde{\pi})-\mu_E||_2\leq \epsilon$，因为这样的策略 $ \tilde{\pi}$ 会保证：
$$ \Bigg|\mathbb{E}\Bigg[\sum\limits_{t=0}^{H}\mathcal{R}(x_t,u_t)|\tilde{\pi}\Bigg]-\mathbb{E}\Bigg[\sum\limits_{t=0}^{H}\mathcal{R}(x_t,u_t)|\tilde{\pi_E}\Bigg]\Bigg| = |w^\intercal\mu(\tilde{\pi})-w^\intercal\mu_E|\leq ||w||_2||\mu(\tilde{\pi})-\mu_E||_2\leq 1\cdot \epsilon = \epsilon$$
Inverse RL 算法. 算法主要过程如下：
- 初始化：随机选择某个策略 $\pi_0$，计算（或者通过 Monte Carlo 近似）$\mu_0 = \mu(\pi_0)$
- 主要循环：
- 对每个 $i\geq 1$，计算
$$t_i = \max_{w:||w||_2\leq 1} \min_{j\in{0,\cdots,i-1}} w^{\intercal}(\mu_E - \mu_j)$$
令 $w_i$ 为达到最大值的 $w$ 的值 - 如果 $t_i \leq \epsilon$，终止
- 否则，使用某个 RL 算法来计算最优策略 $\pi_i$ 使用奖励 $\mathcal{R} = w_i^{\intercal} \phi$
- 计算（或者估计）$\mu_i = \mu(\pi_i)$
- 设置 $i = i + 1$，回到 step 1
- 对每个 $i\geq 1$，计算
注意到在 Step 1 中的优化等价于 SVM 的优化问题：
$$
\begin{aligned}
& \underset{t,w}{\text{minimize}}
& & t \\
& \text{s.t.}
& & w^{\intercal} \mu_E \geq w^{\intercal} \mu_j + t, \; j = 1, \ldots, i-1\\
& & & ||w||_2\leq 1
\end{aligned}
$$
假设算法在 $n$ 步之后终止，$t_{n+1} \leq \epsilon$，那么根据上面这个优化问题，我们有：
$$\forall w\;\mathrm{with}\;||w||_2 \leq 1\; \exists i\;\mathrm{s.t.} w^{\intercal}\mu_i \geq w^{\intercal} \mu_E - \epsilon$$
特别地，因为 $||w^{*}||_2 \leq ||w^{*}||_1 \leq 1$，这意味着在 $\{\pi_0, \pi_1, \dots, \pi_n\}$ 中存在至少一个策略其性能在 $\mathcal{R}$ 下至少和专家性能减去 $\epsilon$ 一样好.
分析. 算法保证在 $n = O(\frac{k}{\epsilon^2} \log\frac{k}{\epsilon})$ 次迭代后终止，其中 $k$ 是特征映射 $\phi$ 的维度. 最后，尽管算法在专家特征期望 $\pi_E$ 上进行优化.
这个量常常是未知的，因此 $m$ 个不同的专家轨迹的 Monte Carlo 样本需要拿来产生 $\pi_E$ 的估计 $\hat{\pi}_E$（$m$ 个估计的经验均值）. 1 中的定理 2 给出需要保证算法高概率正确的专家轨迹的充分数目. 参考 1 更详细的表述和证明.
1 P. Abbeel and A. Y. Ng. Apprenticeship learning via inverse reinforcement learning. In International Conference on Machine Learning (ICML), 2004.