CS285学习笔记

· · 学习·文化课

概念

模仿学习(Imitation Learning)

直接对于数据集 \{(o_t,a_t)\} 采用监督学习得到 \pi_\theta(a\mid o)。

但这样的效果不好，为什么？

考虑完全观察下的固定决策情况，假设专家决策为 \pi^*，记 c(s,a)=\mathbf 1[a\ne \pi^*(s)] 为犯错成本，那么考虑 \sum_t c(s_t,a_t)。

假设 \forall s\in\mathcal D_{\text{data}},\pi_\theta(a\ne \pi^*(s)\mid s)\le \epsilon。考虑假如出现了一次错误行为，会到达一个训练数据中不存在的状态，不妨假设之后的行为都是错误的，那么 \mathbb E[\sum_t c(s_t,a_t)]\le \epsilon T+(1-\epsilon)\epsilon(T-1)+(1-\epsilon)^2\epsilon(T-2)+\dots=O(\epsilon T^2).

此处假设了如果出现一次错误，之后无法修正。事实上可以通过某些数据增强或者添加犯错和修正的数据使得决策拥有一定的鲁棒性。但这并没有解决所有问题。

DAgger 算法(Dataset Aggregation)

目的是令 p_{\text{data}}(o_t)=p_{\pi_\theta}(o_t)，其中 p(o_t) 为第 t 个时刻观察为 o_t 的情况下，之前轨迹(trajectory)的分布，下标分别表示是在训练数据中的还是在学习决策下的。这使得机器很难到达训练数据中不存在的状态以防止无法修正错误。

马尔可夫决策过程(Markov Decision Process, MDP)

马尔可夫性：s_{t+1}\mid s_t,a_t 与 s_1,\dots,s_{t-1} 独立。

那么假设 \mu_{t,i}=p(s_t=i),\xi_{t,i}=p(a_t=i)，那么 \mu_{t+1,i}=\sum_{j,k}T_{i,j,k}\mu_{t,j}\xi_{t,k}。

当不完全观察（此时决策变为 \pi_\theta(a_t\mid o_t)）时，还有：

考虑有限视野且完全观察的情况，记 p_\theta(\tau)=p_\theta(s_1,a_1,\dots,s_T,a_T)=p(s_1)\prod_{t=1}^T \pi_\theta(a_t\mid s_t)p(s_{t+1}\mid s_t,a_t)，那么我们需要优化的目标即为 \theta^*=\mathrm{argmax}_\theta J(\theta)=\mathrm{argmax}_\theta\left\{\mathbb E_{\tau\sim p_\theta(\tau)}\left[\sum_{t=1}^T r(s_t,a_t)\right]\right\}，其中 \tau 表示轨迹。

事实上马尔可夫决策的过程可以看作马尔可夫链：p((s_{t+1},a_{t+1})\mid (s_t,a_t))=p(s_{t+1}\mid s_t,a_t)\pi_\theta(a_{t+1}\mid s_{t+1})，考虑期望的线性性：

\mathbb E_{\tau\sim p_\theta(\tau)}\left[\sum_{t=1}^T r(s_t,a_t)\right]=\sum_{t=1}^T\mathbb E_{(s_t,a_t)\sim p_\theta(s_t,a_t)}\left[r(s_t,a_t)\right]

无限视野的时候设计 J(\theta)，可以考虑折现因子或者取平均。其中取平均考虑这是一个 market chain，假如无周期且连通则存在唯一稳态，在稳态上计算平均奖励即可。

一般强化学习流程

一个例子就是我们在绿色部分估算 Q^\pi，然后在蓝色部分简单地令 \pi_\theta(s_t)=\mathrm{argmax}_{a_t} Q^\pi(s_t,a_t).

策略梯度

考虑有限视野，即 J(\theta)=\mathbb E_{\tau\sim p_\theta(\tau)}\left[\sum_{t=1}^T r(s_t,a_t)\right]，我们一般不认为转移概率 p(s_{t+1}\mid s_t,a_t) 是已知的，故对 J(\theta) 估计可以考虑从 p_\theta(\tau) 中采样 N 条轨迹，即无偏估计 \frac1N\sum\limits_i\sum\limits_t r(s_{i,t},a_{i,t}).

考虑记 r(\tau)=\sum_{t=1}^T r(s_t,a_t)，那么

\begin{aligned} \nabla_\theta J(\theta)=&\int\nabla_\theta p_\theta(\tau)r(\tau)\mathrm d\tau\\ \overset{\nabla_\theta\log f=\frac{\nabla_\theta f}f}=&\int p_\theta(\tau)\left(\nabla_\theta\log p_\theta(\tau)\right)r(\tau)\mathrm d\tau\\ =&\mathbb E_{\tau\sim p_\theta(\tau)}\left[\nabla_\theta\log p_\theta(\tau)r(\tau)\right]\\ =&\mathbb E_{\tau\sim p_\theta(\tau)}\left[r(\tau)\nabla_\theta\sum_t\log \pi_\theta(a_t\mid s_t)\right] \end{aligned}

那么对 \nabla_\theta J(\theta) 的估计也可以类似写成 \frac1N\sum\limits_{i=1}^N\left(\sum\limits_{t=1}^T\nabla_\theta\log \pi_\theta(a_{i,t}\mid s_{i,t})\right)\left(\sum\limits_{t=1}^T r(s_{i,t},a_{i,t})\right).（这看起来像是最大似然的带权版本，我们希望给价值大的部分更多的对数概率）

那么改进策略即为 \theta\leftarrow \theta +\alpha\nabla_\theta J(\theta)。

改进

考虑如下情形：r(\tau_1)=-10,r(\tau_2)=2，那么我们会增加 \tau_2 的对数概率并减少 \tau_1 的对数概率。

但如果给两者都加上一个常数 100，那么同时增加 \tau_1,\tau_2 的对数概率，并且增加的幅度接近。

如果给两者都加上一个常数 -2，那么在 \tau_2 处的梯度消失了。

这些情况使得上述梯度策略结果并不良好，我们希望做一些改进使得 \nabla_\theta J(\theta) 的估计量方差尽可能小。

考虑时刻 t 的决策并不会改变以前的奖励，我们改变估计量为 \nabla_\theta J(\theta) \approx\frac1N\sum\limits_{i=1}^N\sum\limits_{t=1}^T\nabla_\theta\log \pi_\theta(a_{i,t}\mid s_{i,t})\left(\sum\limits_{t^\prime=t}^T r(s_{i,t^\prime},a_{i,t^\prime})\right)，这仍是无偏的且方差更小。记 \hat Q_{i,t}=\sum\limits_{t^\prime=t}^T r(s_{i,t^\prime},a_{i,t^\prime}) 表示 Q-function 的单样本估计量，那么 \nabla_\theta J(\theta) \approx\frac1N\sum\limits_{i=1}^N\sum\limits_{t=1}^T\nabla_\theta\log \pi_\theta(a_{i,t}\mid s_{i,t})\hat Q_{i,t}.

同时注意到 \mathbb E_{\tau\sim p_\theta(\tau)}[\nabla_\theta \log p_\theta(\tau)]=\int \nabla_\theta p_\theta(\tau)\mathrm d\tau=0，故给所有 r(\tau) 加上一个常数对 \nabla_\theta J(\theta) 没有影响。

那么令 g(\tau)=\nabla_\theta \log p_\theta(\tau)，那么使得 g(\tau)(r(\tau)-b) 方差最小的 b 即为 b=\frac{\mathbb E[g(\tau)^2r(\tau)]}{\mathbb E[g(\tau)^2]}，此处向量乘法和除法都是逐位置操作，b 是和 \theta 同阶的向量分别表示对 i 个参数求导时使用的偏移量。

离线

上述梯度策略是在线的，因为 J(\theta) 是在 \tau\sim p_\theta(\tau) 下定义的，故 \theta 改变后原先的样本只能全部舍弃。

考虑 \mathbb E_{x\sim p(x)}[f(x)]=\mathbb E_{x\sim q(x)}\left[\frac{p(x)}{q(x)}f(x)\right]。那么

\begin{aligned} \nabla_{\theta^\prime}J(\theta^\prime)&=\mathbb E_{\tau\sim p_{\theta}(\tau)}\left[\frac{p_{\theta^\prime}(\tau)}{p_\theta(\tau)}\nabla_{\theta^\prime}\log p_{\theta^\prime}(\tau)r(\tau)\right]\\ &=\mathbb E_{\tau\sim p_{\theta}(\tau)}\left[\prod_{t=1}^T\frac{\pi_{\theta^\prime}(a_t\mid s_t)}{\pi_{\theta}(a_t\mid s_t)}\left(\sum_{t=1}^T\nabla_{\theta^\prime}\log \pi_{\theta^\prime}(a_t\mid s_t)\right)\left(\sum_{t=1}^Tr(s_t,a_t)\right)\right]\\ &=\mathbb E_{\tau\sim p_{\theta}(\tau)}\left[\sum_{t=1}^T\nabla_{\theta^\prime}\log \pi_{\theta^\prime}(a_t\mid s_t)\left(\prod_{t^\prime=1}^{t-1}\frac{\pi_{\theta^\prime}(a_{t^\prime}\mid s_{t^\prime})}{\pi_{\theta}(a_{t^\prime}\mid s_{t^\prime})}\right)\left(\sum_{{t^\prime}=t}^Tr(s_{t^\prime},a_{t^\prime})\left(\prod_{t^{\prime\prime}=t}^{t^\prime}\frac{\pi_{\theta^\prime}(a_{t^{\prime\prime}}\mid s_{t^{\prime\prime}})}{\pi_{\theta}(a_{t^{\prime\prime}}\mid s_{t^{\prime\prime}})}\right)\right)\right]\\ \end{aligned}

最后一个乘积我们后续会证明忽略它也能得到一个使策略改进的梯度（这并不意味着忽略它是等价的），故

\nabla_{\theta^\prime}J(\theta^\prime)=\mathbb E_{\tau\sim p_{\theta}(\tau)}\left[\sum_{t=1}^T\nabla_{\theta^\prime}\log \pi_{\theta^\prime}(a_t\mid s_t)\left(\prod_{t^\prime=1}^{t-1}\frac{\pi_{\theta^\prime}(a_{t^\prime}\mid s_{t^\prime})}{\pi_{\theta}(a_{t^\prime}\mid s_{t^\prime})}\right)\left(\sum_{{t^\prime}=t}^Tr(s_{t^\prime},a_{t^\prime})\right)\right]

那么以此我们就能在求 \theta^\prime 的梯度时使用 p_\theta(\tau) 的采样。

高阶策略

在大多数情况下，不同的参数对策略影响大小是不一样的。我们希望对策略影响小的参数学习率更大，对策略影响大的参数学习率更小

考虑 KL 散度，决策改进变为 \theta^*=\underset{D_{\mathrm{KL}}(\pi_{\theta^\prime}\| \pi_\theta)\le \epsilon}{\mathrm{argmax}}(\theta^\prime-\theta)^\top \nabla_\theta J(\theta)，其中 \epsilon 是关于 \alpha 的函数。

考虑 KL 散度二阶泰勒展开可以用费舍尔矩阵表示，即 D_{\mathrm{KL}}(\pi_{\theta^\prime}\| \pi_\theta)\approx (\theta^\prime-\theta)^\top\mathbf F(\theta^\prime-\theta),\mathbf F=\mathbb E_{\pi_\theta}\left[\nabla_\theta\pi_{\theta}(a|s)\nabla_\theta\pi_{\theta}(a|s)^\top\right].

那么最终迭代策略变为 \theta\leftarrow \theta+\alpha\mathbf F^{-1}\nabla_\theta J(\theta)

Actor-Critic Algorithm

考虑上述使用了 \hat Q_{i,t} 是一个复杂期望的单样本估计，方差比较大，考虑 Q-function Q^\pi(s_t,a_t)=\sum_{t^\prime=t}^T\mathbb E_{\pi_{\theta}}[r(s_{t^\prime},a_{t^\prime})\mid s_t,a_t]，那么改进后的估计量为 \nabla_\theta J(\theta)\approx \frac1N\sum\limits_{i=1}^N\sum\limits_{t=1}^T\nabla_\theta\log \pi_\theta(a_{i,t}\mid s_{i,t})Q^\pi(s_{i,t},a_{i,t})，这显然还是无偏的。

同时，考虑偏移，考虑 Value-function V^\pi(s_t)=\mathbb E_{a_t\sim \pi_{\theta}(a_t\mid s_t)}[Q^\pi(s_t,a_t)]，记 Advantage-function A^\pi(s_{t},a_{t})=Q^\pi(s_{t},a_{t})-V^\pi(s_{t})，那么 \nabla_\theta J(\theta)\approx \frac1N\sum\limits_{i=1}^N\sum\limits_{t=1}^T\nabla_\theta\log \pi_\theta(a_{i,t}\mid s_{i,t})A^\pi(s_{i,t},a_{i,t}) 显然也是无偏的。

考虑 Q^\pi(s_{i,t},a_{i,t})\approx r(s_{i,t},a_{i,t})+V^\pi(s_{i,t+1})，那么 A^\pi(s_{i,t},a_{i,t})\approx r(s_{i,t},a_{i,t})+V^\pi(s_{i,t+1})-V^\pi(s_{i,t}).

那么我们只需要拟合 V^\pi(s_t)，假如可以设定初始状态多次模拟，那么可以使用蒙克卡罗方法。或者以 \{(s_{i,t},\sum_{t^\prime=t}^T r(s_{i,t^\prime},a_{i,t^\prime}))\} 为数据集进行监督学习。（此处不一定无偏，但是为了减少方差我们接受一定的偏移）

此处仍能改进，因为 y_{i,t}=\sum_{t^\prime=t}^T r(s_{i,t^\prime},a_{i,t^\prime}) 并不是 V^\pi(s_{i,t}) 的目标值。考虑迭代，记上一次拟合的模型为 \hat V^\pi_\phi(s_t)，其中 \phi 是模型的参数。那么我们令 y_{i,t}=r(s_{i,t},a_{i,t})+\hat V^\pi_\phi(s_{i,t+1})，以 \{(s_{i,t},y_{i,t})\} 为数据集训练出新的模型 \hat V^\pi_{\phi^\prime}，重复迭代。

这是朴素的回归问题，损失函数可以简单设为 \mathcal L(\phi)=\frac12\sum \left(\hat V^\pi_\phi(s_i)-y_i\right)^2.