学徒学习 Apprenticeship learning via inverse reinforcement learning

2017-09-15

文章目录

1. 算法
2. 总结

学徒学习是Ng（吴恩达）和Abbeel提出来的。学徒学习是这样：Agent从专家示例中学到回报函数，使得在该回报函数下所得到的最优策略在专家示例策略附近。

回报函数$R(s)$ 假设为：$R\left(s\right)=w^T\cdot\phi\left(s\right)$，其中$\phi(s)$为映射特征的基函数，可以为多项式基底，也可以为傅里叶基底。文中是以线性函数为基底。
逆向强化学习求的就是回报函数中的系数w。

策略 $\pi$ 的值函数为：
$v_{\pi}(s) = E_{\pi}[\sum_{t=0}^{\infty}\gamma^t R(s_t)]$
将回报函数代入：
$v_{\pi}(s) = w^T E_{\pi}[\sum_{t=0}^{\infty}\gamma^t \phi(s_t)]$

将上式右半部分定义为特征期望：$\mu\left(\pi\right)=E_{\pi}[\sum_{t=0}^{\infty}\gamma^t \phi(s_t)]$。需要注意的是，特征期望跟策略 $\pi$ 有关，策略不同时，策略期望也不相同

当给定m条专家轨迹后，根据定义我们可以估计专家策略的特征期望为：
$\hat{\mu}_E=\frac{1}{m}\Sigma_{i=1}^{m}\Sigma_{t=0}^{\infty}\gamma^t\phi\left(s_{t}^{\left(i\right)}\right)$
其中，专家状态序列为专家轨迹:${ s_{0}^{(i)},s_{1}^{(i)},\cdots }_{i=1}^{m}$

逆向强化学习可以归结为如下问题：

找到一个策略，使得该策略的表现与专家策略相近。我们可以利用特征期望来表示一个策略的好坏，找到一个策略，使其表现与专家策略相近，其实就是找到一个策略 $\tilde{\pi}$ 的特征期望与专家策略的特征期望相近，即使如下不等式成立：
$\lVert\mu\left(\tilde{\pi}\right)-\mu_E\rVert_2\le\epsilon$

当该不等式成立时，对于任意的权重$\lVert w\rVert_1\le 1$，值函数满足如下不等式：
p_5

算法

p_1

其中第二行的目标函数为:

$t^{(i)}=\max_{w:\lVert w\rVert_2\le 1}\min_{j\in{0\cdots(i-1)}}w^T(\mu_E-\mu^{(j)})$

写成标准的优化形式为：
p_3
注意，在进行第二行求解时，$\mu^{\left(j\right)}$中的 $j\in{0,1,\cdots ,i-1}$是前i-1次迭代得到的最优策略。也就是说第i次求解参数时，i-1次迭代的策略是已知的。这时候的最优函数值t相当于专家策略 $\mu_E$ 与i-1个迭代策略之间的最大边际。
p_4

我们可以从支持向量机的角度去理解。专家策略为一类，其他策略为另一类，参数的求解其实就是找一条超曲面将专家策略和其他策略区分开来。这个超平面使得两类之间的边际最大。

第四行是在第二行求出参数后，便有了回报函数$R=\left(w^{\left(i\right)}\right)^T\phi$，利用该回报函数进行强化学习，从而得到该回报函数下的最优策略 $\pi^{\left(i\right)}$。

总结

学徒逆向强化学习方法分为两步:
第一步在已经迭代得到的最优策略中，利用最大边际方法求出当前的回报函数的参数值；（该计算需要用到QP(二次规划)求解器或者SVM求解器。文中也给出了一种不使用求解器的简单算法。）
第二步利用求出的回报函数的参数值进行正向强化学习方法求得当前最优的策略，然后重复第一步。

需要注意的是，$\phi(s)$ 中输入的 s 为 i 个特征：$s^1,s^2,…,s^i$，if 第 i 个特征存在，$s^i = 1$，else $s^i = 0$。又因为$\lVert w\rVert_1\le 1$，所以$R\le 1$。

ref: Abbeel, P., & Ng, A. Y. (2004). Apprenticeship learning via inverse reinforcement learning. International Conference on Machine Learning(Vol.11, pp.1). ACM.