强化学习笔记 all in one

发表于 更新于 分类于 阅读次数： 本文字数： 9.6k 阅读时长 ≈ 35 分钟

cs285

基础概念

强化学习和监督学习的区别：

  1. 强化学习输入的样本是序列数据, 监督学习的样本之间相互独立
  2. 没有明确的监督者, 通过奖励机制进行学习, 但回馈可能是长期的, 模糊的

一些强化学习的演示视频中, ai 会做一些人类看来无意义的动作, 正是这种“玄学”的回馈机制导致的

  • actor: 行为主体
    • action 则可分为离散和连续, 例如 2d 游戏中走格子迷宫就是一个典型的离散动作空间
  • observaton o /states s: 观测与状态
    • 观测到的情况 o 和现实情况（状态 s）其实有可能不同, 假设可以观察到全景, rl 则成为一个马尔科夫决策过程
  • policy π: 行为策略
    • 带有参数 θ
  • reward：反馈
    • baseline: 避免总是正值的 reward, 增加的偏置值, 例如取期望
  • episode: 一轮行动
  • trajectory τ: \(\tau=\{s_{1},a_{1},s_{2},a_{2},\cdots,s_{T},a_{T}\}\)
  • 折扣 γ: 直觉上, 最开始的训练回馈可能更重要, 越往后则训练收益越小, 所以对每步的回馈可以乘以一个 \(\gamma^{t-1}\), t 为训练次数, 这个超参数也可以用于控制训练策略偏短期还是偏长期

流程： env(s1)-> actor(a1)-> env(s2)……
$\begin{array}{l}{ {p_{\theta}(\tau)} }{ { {}=p(s_{1})p_{\theta}(a_{1}|s_{1})p(s_{2}|s_{1},a_{1})p_{\theta}(a_{2}|s_{2})p(s_{3}|s_{2},a_{2})\cdots} } \\ =p(s_{1})\prod_{t=1}^{T}p_{\theta}(a_{t}|s_{t})p(s_{t+1}|s_{t},a_{t})\end{array}$

同一轮中每对(s, a)产生一个 reward, 其期望为: \(\bar{R}_{\theta}=\sum_{\tau}R(\tau)p_{\theta}(\tau)=E_{\tau\cap P_{\theta}(\tau)}[R(\tau)]\)

策略梯度

rl 的目标就是找一个最大化期望回报的策略 π, 等价于找到最好的策略参数 θ, 可以使用和机器学习类似的梯度下降, 只不过这个梯度比较特殊，下面引用 cs285 的 ppt:

上图 1 中的 J 表示根据确定的 θ 和 π, 得到的轨迹 τ 对应回报的期望, 使用一个 trick, 将概率的梯度转为其自身和 log 梯度的乘积, 这是为了凑出数学期望的形式
再看上图 2, 其实 τ 的概率是一系列 a, s 概率的乘积, 对其 log 转为加法, 得到的项中, 终于根据 s 得到 a 的概率是和 θ 有关的(这也完全符合常识), 于是最后我们所求的梯度其实只有对 π 求微分这个计算量比较大的项
为什么我们想要数学期望的形式？ 因为对此我们可以通过大量采样的平均来估算，例如对 J 就可以用 n 个轨迹回报的均值估算, 而对 J 的梯度, 类似地有:

\[\nabla_{\theta}J(\theta)\approx\frac{1}{N}\sum_{i=1}^{N}\left(\sum_{t=1}^{T}\nabla_{\theta}\log\pi_{\theta}({\bf a}_{i,t}|{\bf s}_{i,t})\right)\left(\sum_{t=1}^{T}r({\bf s}_{i,t},{\bf a}_{i,t})\right)\]
这个式子看上去有点吓人，其实它只是单纯地用旧策略的 log 梯度乘对应的回报值, 也就是说在进行若干轮采样后, 总体上好的回报, 就加上(当然这里有一个学习率超参数)对应的好的参数, 坏的回报就减去坏的参数
再考虑一下这个梯度的数学性质, 首先很明显的是, 回报和的绝对值越大, 更新幅度就会越大, 这很符合常识, 但同时, 考虑 log 的性质, 对较小的值其导数的绝对值越大, 也就是说对一个策略 π 来说, 其不怎么倾向于采取的动作反而会得到更多的更新梯度, 这可以视为一种 exploration
此外，对部分可观测的马尔科夫假设, 这里不作具体推导, 但只要把上面的 s 换成 o 就能沿用梯度策略
和 log 函数的很多应用场景一样, 这里实际上可以理解为分类问题, 因为模型输出的动作是有限的, 策略最后产生的是动作空间中的概率分布, 稍微不同的是需要乘回报值, 并且要分很多轮训练

问题和改进

基于策略梯度的训练方式非常直观，但相应地也有问题, 即它结果会非常不稳定
我们寻找的策略会不断往最高的回报前进, 这取决于我们每轮采样的回报, 这里我们其实是希望得到相对最优的一个目标, 但如果假设我们得到回报的相对倾向性较稳定, 但不同采样的绝对差距较大, 就会导致虽然以最优化策略为目标，最后得到的参数却相差非常大(方差大)的情况

  1. 因果关系: 这基于一个永恒的真理, 未来不会影响过去, 在 rl 中也就是说： 时间 t'之后得到的回报无论是好是坏都不该影响 t'之前的策略，对应在之前的方法中, 就是让回报总和一项从 t 开始计算:
    这听起来有点绕, 举个例子, 打对战游戏的前 t 把都输了, 于是 t+1 把转变思路赢了游戏, 假如按未改进的版本, 由于前 t 把输得太多，最后所有 t+1 局游戏的回报还是负的, 因此第 t+1 把的思路也是错的, 但是 t+1 把的思路的回报是正的, 也就是说这时的思路是正确的, 对游戏策略理应有正确影响，按改进后的方法, 我们认为 t+1 局的游戏思路期望回报为正

\[\nabla_{\theta}J(\theta)\approx\frac{1}{N}\sum_{i=1}^{N}\left(\sum_{t=1}^{T}\nabla_{\theta}\log\pi_{\theta}({\bf a}_{i,t}|{\bf s}_{i,t})\right)\left(\sum_{t'=t}^{T}r({\bf s}_{i,t'},{\bf a}_{i,t'})\right)\]

由于这里我们减少了回报的绝对值大小，因此其 θ 最后的方差必然会缩减, 但这么做对期望是无偏的(对策略梯度加减任何常数偏移值， 都会保持无偏), 也就是不会改变更新梯度，相当于只改变了其系数(回报和)的大小

  1. baseline

我们的目的是找到最优化的策略参数, 实际上只要回报为正, 就会加上对应参数的梯度, 这种更新策略其实是“找到回报为正的参数”, 还是拿打游戏举例子, 如果目标是打到全国第一, 那么和低水平对手的对局, 就算赢了这局的思路也不值得学习
因此可以考虑将总回报减去一个 baseline, 简称为 b, b 一般取回报的平均值
事实上，这对梯度的期望是无偏的， 即减去 b 和不减去两者的梯度一致, 但会减少方差, 最优的 b 可以通过对方差算关于 b 的极值求出来, 由于不太常用省去过程, 最优 b 为:

\[b={\frac{E[g(\tau)^{2}r(\tau)]}{E[g(\tau)^{2}]}}\]

重要性采样

策略梯度是 on-policy 的, 也就是每次需要收集数据才能更新, 数据与策略是绑定的, 这样的缺点是更新很慢，效率低
如果想用 off-policy, 则需要重要性采样

暂时忽略被划掉的一项(这是因为我们不想让这种指数级别的项增大方差) 尽可能简单地说明为什么要用这种采样方法: 不谈证明, 但是重要性采样有个性质是不会改变采样的均值(期望), 只会改变方差, 一般来说会将其用于改进采样的方差, 和名字一样, 可以理解为用不同的重要性对一个分布采样, 也就是分布不变，只改变采样方式, 来获得符合要求的采样数据
但在策略梯度中, 问题在于我们改进过程中策略的分布和原始数据时的分布是不同的， 想实现 off-policy, 就需要用来自不同策略的数据来改进当前策略, 所以我们需要重要性采样这样的技巧, 不太严谨地说， 将不同策略的数据转化为当前策略的数据并用于训练， 又或者理解为用不同策略的数据计算对当前策略的更新梯度

此外对策略梯度还有的问题是, 对不同的参数 θ, 其梯度的数量级可能完全不同，需要进行一定约束, 例如约束 θ 分布前后的散度, 从而平衡不同方向的更新速率
这方面具体实现上比较复杂，暂时只需要知道大概原理即可

actor-critic

由类似我们前文提到的baseline思想, 定义A(advantage)=Q-V, 也就是状态动作对的期望奖励-状态的期望奖励, 这个标准能评估对当前状态来说, 采取的动作是好是坏
我们可以将A替代掉之前的期望回报, 但需要注意的是, 由于实际中很多时候A是估算的, 这会带来方差的优化，但很可能让更新梯度有偏; 尽管如此, 一般我们还是认为拿大量减少方差换一些偏见是划算的
Q可以写为当前(s,a)的回报加上基于未来状态分布的V的期望, 可以用直接的 \(s_{t+1}\) 近似这个期望, 写成 \(Q^{\pi}(\mathbf{s}_{t},\mathbf{a}_{t})\approx r(\mathbf{s}_{t},\mathbf{a}_{t})+V^{\pi}(\mathbf{s}_{t+1})\) , 于是:
\[A^{\pi}(\mathbf{s}_{t},\mathbf{a}_{t})\approx r(\mathbf{s}_{t},\mathbf{a}_{t})+V^{\pi}(\mathbf{s}_{t+1})-V^{\pi}(\mathbf{s}_{t})\] \[\nabla_{\theta}J(\theta)\approx\frac{1}{N}\nabla_{i=1}^{N}\sum_{t=1}^{T}\Sigma_{\theta}\log\pi_{\theta}({\bf a}_{i,t}|{\bf s}_{i,t})A^{\pi}({\bf s}_{i,t},{\bf a}_{i,t})\] 这种近似的好处是, 相比涉及动作空间的Q, V更好计算, 近似后我们唯一需要算的就是V了, 而之前的term:J, 可以视为根据初始状态s1分布的 V(s1)的期望; 此外, 由于只用一个样本估算, 也能减少方差
对V来说最方便的估算就是使用蒙特卡洛方法, 尤其在模拟环境或者电子游戏之类的场景下, 可以大量采样 \(V^{\pi}(\mathbf{s}_{t})\approx\sum_{t^{\prime}=t}^{T}r(\mathbf{s}_{t^{\prime}},\mathbf{a}_{t^{\prime}})\)
但也可以使用一个估算函数, 即function approximation, 这是个典型的监督回归问题, 可以用神经网络解决, 数据集为n轮训练中的 \(s_{i,t}\) 与其对应的从t开始的回报和 \(\left\{\left({\bf s}_{i,t},r({\bf s}_{i,t},{\bf a}_{i,t})+\hat{V}_{\phi}^{\pi}({\bf s}_{i,t+1})\right)\right\}\) , loss设置为平方误差和 \(\mathcal{L(\phi)}=\frac{1}{2}\sum_{i}\left|\left|\hat{V}_{\phi}^{\pi}(\mathbf{s}_{i})-y_{i}\right|\right|^{2}\)
基于神经网络的方法的好处是, 网络能一定程度上捕获数据间的关系, 由一定的泛化能力, 也就是可能能够平滑化输出的结果, 即类似的状态应该有类似的期望回报, 从而减少方差;缺点则是不能保证是无偏的

以上我们提到的方法就是标题里的a-c, 如果我们再引入一个折扣因子，就可以表述为以下的流程:

这个版本的a-c其实非常好理解, 它就是用一个单独的神经网络预测V，用于帮助另一个训练策略π的网络
但问题在于这两个网络只有输入是相同的(s), 其特征是完全分开的, 这可能让它的性能受限, 一种改进是共享网络, 即用一个网络接受s，同时生成V和π
目前的这个版本是on-line的, 这就意味着, 每次只能用一个数据来更新网络, 如果想实现batch， 则需要并行化, 具体来说可以分为同步异步两种情况
如上图, 同步的情况很好理解, 就是每次让一群线程获取行动后的数据, 每次都同步更新
异步的情况下, 不同线程可能有不同的运行速度, 并各自用收集到的数据更新网络参数, 这样的效率更好, 但缺点是, 较慢的线程更新时可能遇上新版本的actor, 也就是说会有这种用非当前actor的数据更新它的问题, 当然一般来说因为线程之间的速度不会有特别大的差别, 影响相对不大

off-policy a-c

在off-policy情况下, 存储之前的状态转移数据为 replay buffer, 这些数据可能来自于很久之前的策略, 这会带来两个问题:

  1. 批评家对V的评估是基于旧策略的
  2. 策略更新时使用的策略梯度也是来自于旧策略的

对此, 我们可以把V给扔掉, 转向Q函数, \({ Q}^{\pi}(\mathrm{s}_{t}, a_t)\stackrel{\_}{=}\sum_{t^{\prime}=t}^T E_{\pi_{\theta}}\ [r(\mathrm{s}_{t^{\prime}},a_{t^{\prime}})]\mathrm{s}_{t}, a_{t}]\) 那么为什么要这么做? 考虑一下现在我们有什么数据, 即来自旧策略下的V函数, V函数的意义是, 各个状态的期望回报, 也就是我们知道各个状态的价值, 而这些价值相对来说不会随着策略变动而改变
新策略相比旧策略改动的只有给定s条件下a的分布, 也就是说给定旧策略的s, 可以查到在新策略在相同给定状态s下产生的动作概率分布, 从而算出新策略对应的Q函数
于是off-line方法可以写成:

其中, \(a_{i}'\) 与 \(a_{i}^{\pi}\) 是根据 \(s_{i}'\) 从新策略中产生的动作
实际中一般用Q代替之前的A，这是因为这种方法能提供大量样本, 从而弥补方差的问题
那么offline是毫无损失的方法吗? 其实并不是, 因为对来自旧策略的旧状态s我们无能为力, 这必然会产生一些偏差, 但基本来说处于可以接受的范围内

更好的baseline

上面提到, 基于神经网络的评论家能实现有偏下的低方差, 策略梯度则是无偏的高方差, 那么有办法得到无偏的低方差更新梯度吗?
下图展示一种估计策略梯度的方法, 它基于一个原理, 对梯度乘以任何一个值依赖状态而不依赖动作的函数，都能保持无偏, 选取价值函数作为baseline, 由于我们希望估计的就是V的期望，选择价值函数作为baseline应当能大量减少方差

那么如果用Q函数作为基线呢? 如果这样的话, 理论上讲我们要求的A会在0的上下浮动, 这样不是能让方差达到理想情况吗? 但问题在于, 由于这样不无偏, 那就需要加上一个误差修正项, 我们将得到一个吓人的式子:

\[\nabla_{\theta}J(\theta)\approx\frac{1}{N}\sum_{i=1}^{N}\sum_{t=1}^{T}\nabla_{\theta}\log\pi_{\theta}({\bf a}_{i,t}|{\bf s}_{i,t})\left(\hat{Q}_{i,t}-Q_{\phi}^{\pi}({\bf s}_{i,t},{\bf a}_{i,t})\right) +\frac{1}{N}\sum_{i=1}^{N}\sum_{t=1}^{T}\nabla_{\theta}E_{\mathrm{a}\sim\pi_{\theta}({\bf a}_{t}|{\bf s}_{i,t})}\left[Q_{\phi}^{\pi}({\bf s}_{i,t},{\bf a}_{t})\right]\]
这个式子看起来似乎根本用不了, 但其实也有技巧能用成本可控的方式估计误差修正项

还有一种比较常见的思路是取n步的回报，由于越往后数据越可能发散, 这样也能降低方差, 这里不多介绍

基于价值的方法

最直观的说, 策略就是从动作空间中选一个最佳的动作, 这个最佳一般用Q函数表示, 而Q依赖于V, 从Q或者V的角度出发, 强化学习的问题就是选择一个最佳的Q与其对应的A, 再有足够样本的情况下, 估算Q可以用V矩阵实现, 因此这称为基于价值的方法(value-based v-b)
很明显, 现实中经常有很大或者无穷的动作空间, 因此基于表格的V-B不现实, 类似之前的a-c, 可以训练一个估计Q函数的网络, 定义其loss为: \(\mathcal{L}(\phi)=\frac{1}{2}\left|\left|V_{\phi}(\mathbf{s})-\operatorname*{max}Q^{\pi}(\mathbf{s},\mathbf{a})\right|\right|^{2}\)
但是如果我们想迭代Q, 还有一个严峻的问题： 状态转移的概率很难得到, 因为Q由本轮回报与之后的根据未来状态分布的V(s')的期望相加组成, 而未来状态的分布, 也就是根据策略π采取行动后的s'我们是不知道的, 于是我们用其他的(a, s',a')样本来估计未来的Q期望, 也就是：
\(Q^{\pi}({\bf s},{\bf a})\leftarrow r({\bf s},{\bf a})+\gamma E_{ {\bf s}^{\prime}\sim p({\bf s}^{\prime}|{\bf s},{\bf a})}[Q^{\pi}({\bf s}^{\prime},\pi({\bf s}^{\prime}))]\)
为什么可以这么做? 或者说, 为什么策略的变化在这样的学习中似乎不重要? 这是因为在这种方法下策略就是选取最大化Q的动作, 也就是说策略由Q来定义, 而不是Q受策略影响, 不严谨地说, 可以认为Q的地位高于策略

稍微总结一下训练步骤, 对V来说:

\[\begin{array}{l}{ {1.\;\;\mathrm{set}\;{\bf{y}}_{i}\:\leftarrow\;\mathrm{max_{a_{i}}}(r({\bf{s}}_{i},{\bf{a}}_{i})+\gamma E[V_{\phi}({\bf{s}}_{i}^{\prime})])}}\\ { {2.\;\;\mathrm{set}\;\phi\:\leftarrow\;\mathrm{arg~min}_{\phi}\:\frac{1}{2}\:\sum_{i}\|V_{\phi}({\bf{s}}_{i})-{\bf{y}}_{i}\|^{2}}}\end{array}\]

于是对Q的计算:

\[\begin{array}{l}{ {1.\;\;\mathrm{set}\;\:{\mathrm{y}}_{i}\:\leftarrow\:r(\mathrm{s}_{i},{\bf a}_{i})+\gamma{ E}[V_{\phi}(\mathrm{s}_{i}^{\prime})]}}\\ { {2.\;\;\mathrm{set}\;\:\phi\:\leftarrow\:\mathrm{arg\,min}_{\phi}\:\frac{1}{2}\:\sum_{i}||{\cal Q}_{\phi}(\mathrm{s}_{i},{\bf a}_{i})-{\bf y}_{i}||^{2}}}\end{array}\]

也就是说, 由于我们定义策略为选择Q最大的A, 那么相应的状态s的动作空间中最佳的Q就是状态s的期望价值
由于没有麻烦的策略梯度, 以上的v-b有较小的方差, 但还有一个问题是, 对神经网络的方法它不保证收敛性

对训练Q的神经网络来说, 应用上述的用Q估算V的思想, 步骤为:

\[\begin{array}{l} {\mathrm{1.~collect~dataset~\{(s_{i},{\bf a}_{i},{\bf s}_{i}^{\prime},r_{i})\}~u{\mathrm{sing~some~policy}}}} \\ { {2.~\mathrm{set~yi}\leftarrow r({\bf s}_{i},{\bf a}_{i})+\gamma\mathrm{max_{a^{\prime}}}\,Q_{\phi}({\bf s}_{i}^{\prime},{\bf a}_{i}^{\prime})}} \\ { {3.~\mathrm{set~}\phi\leftarrow\mathrm{arg\,min}_{\phi}\ {\frac{1}{2}} { \Sigma_{i}|\vert{\cal Q}_{\phi}({\bf s}_{i},{\bf a}_{i})-{\bf y}_{i}}}\vert\vert^{2}}\end{array}\]

其中2.3.可以执行k次确保其更好地迭代

以上这个简单的方法就是最基础的off-policy on-line 的Q学习, 这个方法有一个非常明显的问题, 由于它的策略不包括任何概率, 是完全决定性的, 而迭代过程是贪心的, 因此在迭代中如果有一些错误或者不好的数据集，很容易就会陷入一个表现较差且无法进一步迭代的循环里
因此, 尤其是对最开始的一批数据, 我们希望能增加一些随机性, 最简单的方法就是对原来的策略加一层随机, 称为 \(\epsilon\) 贪心:

\[\pi({\bf a}_{t}|{\bf s}_{t})=\left\{\begin{array}{l}{ {1-\epsilon\mathrm{~if~}{\bf a}_{t}=\arg\mathrm{max}_{ {\bf a}_{t}}Q_{\phi}({\bf s}_{t},{\bf a}_{t})}}\\ { {\epsilon/(|A|-1)\mathrm{~otherwise}}}\end{array}\right.\]

另一种常见方法称为Boltzmann exploration（波尔兹曼探索), 即 \(\pi({\bf a}_{t}|{\bf s}_{t})\propto\exp(Q_{\phi}({\bf s}_{t},{\bf a}_{t}))\) 这种策略的好处是能根据Q的好坏加权策略, 如果是Q都比较高的行动, 概率不会相差太大, 而Q很低的行动则几乎不会被采取

收敛性

接下来尝试证明V-B方法是否收敛

首先问题定义如图, B(back-up)操作用于根据给定V找到一个最好的动作, V则是一个最终的最优解, 也就是其回报与转移状态的价值期望之和在所有动作中最大
也就是说, 如果用B操作不断迭代, 能到达V状态, 就说明v-b是收敛的
直观地, 我们有以下性质:
\[{\mathrm{for~any~}}V{\mathrm{~and~}}{\bar{V}},{\mathrm{~we~have~}}||B V-B{\bar{V}}||\infty\leq\gamma||V-{\bar{V}}||\infty\]
于是:
\[\|B V-V^{*}\|_{\infty}\leq\gamma\|V-V^{*}\|_{\infty}\]

这样的证明省略了很多东西, 但对cs来说已经足够了, 事实上, 基于不断取最大值这个操作, 基于表格(矩阵/向量)的v-b收敛是很符合直觉的
那么对基于神经网络回归的v-b呢? 这个问题稍微有点麻烦, 将nn能产出的价值全集定义为 \(\Omega\), 事实上由于基于线性拟合与目前这个损失函数, nn做的其实是个最小二乘法, 实际产生的V'是理想V在Ω上的一个投影
对任意两个点a,b对一条直线的投影点c,d, ab,cd直接的距离l1,l2来说, 始终有l1≥l2, 我们可以简单地构建一个直角三角形证明这点, 对ab不与直线平行的情况, ab是斜边, cd是直角边
我们将投影操作定义为π, 则有 \[\|\Pi V-\Pi{\bar{V}}\|^{2}\leq\|V-{\bar{V}}\|^{2}\]
而现在的问题是, π和B都有我们很想要的收缩性质, 但如果同时存在这两种操作, 就不保证收缩了
上图给出了一个很形象的例子, 由此我们证明基于nn的v-b不一定收敛
对于Q学习, 实际上也差不多
这有点像所谓的合成谬误, 我们有能让策略变好的贪心方法, 还有最小二乘法与梯度下降, 为什么加到一起后结果却不一定变好?
事实上, 我们训练的这个回归网络并不是真正地使用了梯度下降, 见下图
对同样和参数有关的yi, 我们并没有计算梯度, 当然也可以计算(Residual Gradient), 但由于计算量太大, 这么做在工程上很不实用
还有一个悲伤的消息是, 之前的a-c也不保证收敛

马尔可夫过程

马尔可夫过程中, 对一个特定状态则有一个特定的未来状态概率分布（可以理解为策略）, 很容易算出之后的期望回报
即, 如果我们希望知道一个特定状态是好是坏, 可以定义状态价值 V 为其回报的期望, 即从这个状态开始, 折扣 γ 的指数与之后回报乘积的和, V 与回报 G 的区别是, V 绑定一个特定的状态 s, 即某个 s 开始的之后获取的回报的期望
t 时刻后的回报为：
\[G_{t}=r_{t+1}+\gamma r_{t+2}+\gamma^{2}r_{t+3}+\gamma^{3}r_{t+4}+\ldots+\gamma^{T-t-1}r_{T}\] 状态 s 的价值为：
\[\begin{array}{l}{ {V^{t}(s)=\mathbb{E}\left[G_{t}\mid s_{t}=s\right]} }\\ { {\ } }\\ { {=\mathbb{E}\left[r_{t+1}+\gamma r_{t+2}+\gamma^{2}r_{t+3}+.\cdot.+\gamma^{T-t-1}r_{T}\mid s_{t}=s\right]} }\end{array}\]
即给定 \(s_t = s\) 这个条件后的 Gt 期望
实际训练中概率没法直接看出来, 符合常识的想法是靠采样估算, 也就是可以对采样的多组数据取平均值, 这称为 蒙特卡洛(Monte Carlo,MC)采样
另一种方法是贝尔曼方程, 这一方程常用于动态规划, 使用下个状态的价值来更新之前状态, 写作：
\[ V(s)=R(s) + \gamma\sum_{s^{\prime}\in S}p\left(s^{\prime}\mid s\right)V\left(s^{\prime}\right) \] s′ 可以看成未来的某个状态, p(s′|s) 是指从当前状态转移到未来状态的概率。V (s′) 代表的是未来某一个状态的价值, R(s) 为 s 的奖励组成的向量
贝尔曼方程的证明：
$$\begin{array}{l}{ {V(s)=\mathbb{E}\left[G_{t}\mid s_{t}=s\right]} }\\ { {=\mathbb{E}\left[r_{t+1}+\gamma r_{t+2}+\gamma^{2}r_{t+3}+...\mid s_{t}=s\right]} }\\ { {=\mathbb{E}\left[r_{t+1}\right|s_{t}=s]+\gamma\mathbb{E}\left[r_{t+2}+\gamma r_{t+3}+\gamma^{2}r_{t+4}+\dots\mid s_{t}=s\right]} }\\ { {=R(s)+\gamma\mathbb{E}[G_{t+1}\left|s_{t}=s\right]} }\end{array}$$ 下面证明: \(\mathbb{E}[V(s_{t+1})|s_{t}]=\mathbb{E}[\mathbb{E}[G_{t+1}|s_{t+1}]|s_{t}]=\mathbb{E}[G_{t+1}|s_{t}]\)

条件期望的定义为：
\[\operatorname{\mathbb{E} }[X\mid Y=y]=\sum_{x}x p(X=x\mid Y=y)\]

具体证明：

代入之前的等式, 得：

\[\begin{array}{c}{ {V(s)=R(s)+\gamma\mathbb{E}[V(s_{t+1})|s_{t}=s]} }\\ { {=R(s)+\gamma{\sum\limits_{s^{\prime}\in S} } p\left(s^{\prime}\mid s\right)V\left(s^{\prime}\right)} }\end{array}\]

对单个 s 来说, 贝尔曼方程就是一个向量乘积加上偏移值, 所有的 s 可以写成一个矩阵乘法加上奖励向量的形式:

\[\begin{array}{c}{ {V=R+\gamma P V} }\\ { {E V=R+\gamma P V} }\\ { {(E-\gamma P)V=R} }\\ { {V=(I-\gamma P)^{-1}R} }\end{array}\]

这个解析解看着很美好, 但涉及到逆矩阵求解, 这是个复杂度 \(O(N^3)\) 的问题(单论常用算法), 因此对较大的模型并不实用

得到 V 的两种方法：

  • 最简单直接的蒙特卡洛方法, 只需要对某个初始状态采样大量轨迹, 然后取平均值, 既可作为其价值
  • 不断迭代贝尔曼方程, 直到结果趋向收敛, 这个收敛值即可以作为价值, 即“自举”（Bootstrapping）(利用当前的估计或状态值来更新和改进自身的学习过程)

决策

单纯的马尔可夫过程没有策略的空间, 也就是同时根据当前的状态和动作决定之后的状态分布, 策略可以基于概率或者直接产生特定输出, 如果策略已知, 依然可以通过计算 \(\sum_{a\in A}\pi(a\mid s)p\left(s^{\prime}\mid s,a\right)\) 获取状态转移的概率
也就是说, 通过采样行动, 我们可以得到使用特定策略的特定状态的价值 由于引进了决策, 定义一个 Q 函数, 也被称为动作价值函数(action-value function)。Q 函数定义的是在某一个状态采取某一个动作, 它有可能得到的回报的一个期望 \[V_{\pi}(s)=\sum_{a\in A}\pi(a\mid s)Q_{\pi}(s,a)\]

\[\begin{array}{r l} {Q(s,a)} &=\mathbb{E}\left[G_{t}\mid s_{t}=s,a_{t}=a\right] \\ &=\mathbb{E}\left[r_{t+1}+\gamma r_{t+2}+\gamma^{2}r_{t+3}+\ldots\mid s_{t}=s,a_{t}=a\right]\\ &{=R(s,a)+\gamma\mathbb{E}[G_{t+1}|s_{t}=s,a_{t}=a]}\\ &{=R(s,a)+\gamma\mathbb{E}[V(s_{t+1})|s_{t}=s,a_{t}=a]}\\ &{=R(s,a)+\gamma\displaystyle\sum_{s^{\prime}\in S}p(s^{\prime}\mid s,a)\,V\left(s^{\prime}\right)} \end{array}\]

可以把状态价值函数和 Q 函数拆解成两个部分: 即时奖励和后续状态的折扣价值, 这样分解后得到一个类似于之前马尔可夫奖励过程的贝尔曼方程——贝尔曼期望方程(Bellman expectation equation):

\[V_{\pi}(s)=\mathbb{E}_{\pi}\left[r_{t+1}+\gamma V_{\pi}\left(s_{t+1}\right)\mid s_{t}=s\right]\] \[Q_{\pi}(s,a)=\mathbb{E}_{\pi}\left[r_{t+1}+\gamma Q_{\pi}\left(s_{t+1},a_{t+1}\right)\right.\mid s_{t}=s,a_{t}=a]\]

备份图

以上我们得到了状态和动作的价值, 对某一个 s, 它可能对应多种 a, 确定一个 a 后得到下一个 state, 这其实是一种树状的关系, 因此可以用树形图表示 V 的演变, 称为备份(回溯)图

如图, 每一个空心圆圈代表一个状态, 每一个实心圆圈代表一个状态-动作对
从叶节点开始向上回溯, 可以得到叶节点上一层的 Q, 然后继续递推, 得到 a 上一层 s 的 V, 这样逐层计算就能得出整张图的状态与动作价值

可视化学习过程

迭代

策略迭代

现在我们有 V 和 Q 这两个工具, 那么假设初始状态, 随便选定一套参数作为策略, 接下来随着训练过程, 不断更新轨迹中各个状态的价值, 由此再得到 Q 函数, 利用 Q 函数更新策略参数, 如此循环, 就可以让策略收敛到较优的性能
优化过程, 简单地说就是先找到所有状态的 V, 然后根据采样结果以及 V 的分布算出对于各个动作 a 的 Q, 那么对于一个特定的 s, 应该采取的策略需要让价值最高的动作有最高的概率, 如果当做分类问题做, 就可以以交叉熵为 loss 函数做梯度下降
这样的优化后, 理论上, 各个状态的 V 以及策略产生的 Q 都会更高, 而作为表现指标的初始状态的 V 也会更好
收敛后, 取让 Q 函数值最大化的动作, Q 函数就会直接变成价值函数, 这称为 贝尔曼最优方程（Bellman optimality equation）: \(V_{\pi}(s)=\operatorname*{max}_{a\in A}Q_{\pi}(s,a)\)
满足贝尔曼方程就说明, 这个策略对一个状态, 即使采取理论上的最佳行动, 也不会有更好的效果

价值迭代

最优性原理定理（principle of optimality theorem）: 策略在状态 s 达到最优价值, 当且仅当对 s 可达的任何 s', 都已经达到了最优价值, 如果我们找到了初始状态 s 的最优价值, 那么自然就得到了最佳策略
其过程为：

  1. 初始化: 对所有状态, 设置其价值为 0
  2. 循环直至收敛(k 为迭代次数)：
    1. 对所有 s : \(Q_{k+1}(s,a)=R(s,a)+\gamma\sum_{s^{\prime}\in S}p\left(s^{\prime}\mid s,a\right)V_{k}\left(s^{\prime}\right)\)
    2. \(V_{k+1}(s)=\operatorname*{max}_{a}Q_{k+1}(s,a)\)
  3. 最优策略 \(\pi(s)=\arg\operatorname*{max}_{a}\left[R(s,a)+\gamma\sum_{s^{\prime}\in S}p\left(s^{\prime}\mid s,a\right)V_{H+1}\left(s^{\prime}\right)\right]\)

这可以单纯视为一个规划问题, 有点类似于计网中路由器网络寻找最短跳数, 由于每个状态的最优解都依赖于能到达它的其他状态是否最优, 而我们不知道具体迭代几次所有状态都能到达最优, 所以对每个状态, 不断地计算其能采取的行动的价值, 找到一个最优的 Q 作为其 V, 如果网络中存在没有达到最优的节点, 那么在某轮迭代中它就会被优化, 直到一轮中没有任何优化发生, 才算抵达了最优解
设想一个类似“终点”的最优状态 s, s 有全局最佳的 V, 只要到达 s 就可以宣告游戏结束, 例如一个跑酷游戏的终点。那么对离 s 一步之遥的 s', 迭代到它后, s'更新自己的价值为 迈出最后一步(action)的回报+s的价值(为了容易说明, 这里假设迈出这步到达 s 的概率是 1), 如果总共只有这两种状态, 由于 s 不会更好了, s'达到 s 也没有更好的路径, 继续迭代也不会更新, 问题解决了
再复杂化一点, 假设有若干个状态, 其中 s 是 "终点", 到达 s 的行为会得到一个及其巨大的回报, 那么每次迭代, 可以通过行动到达 s 的 s'就能达到最优解, 这样依次递推, 直到离 s 最远的状态也找到了耗费最少的到达 s 的路径
当然, 实际上, 很可能不存在这么一个方便的终点, 各个状态间会是互相传递更优解的情况, 但这种迭代的思路不会变化

免模型方法

蒙特卡洛

实际情况中有很多不满足马尔科夫条件, 过程中回报难以获得, 或者 action 连续值无法取最佳之类的问题, 也就是说很难做出系统的理论, 因此需要不通过模型进行 rl 的方法。

  • Q表格: 以采样并记录的方法, 使用平均奖励估算每个状态下每个动作的价值
  • 蒙特卡洛方法: 简单地说, 就是大量采样估算状态价值, 简单地列式可得到 \(\mu_t=\mu_{t-1}+{\frac{1}{t}}\left(x_{t}-\mu_{t-1}\right)\) 其中 \(\mu\) 是到 t 时刻为止的平均值 \(x_{t}-\mu_{t-1}\) 称为残差
    • 增量式蒙特卡洛 （incremental MC） : 用增量的方法更新数据 , \(\begin{array}{l}{ {N\left(s_{t}\right)\leftarrow N\left(s_{t}\right)+1}}\\ { {V\left(s_{t}\right)\leftarrow V\left(s_{t}\right)+\frac{1}{N(s_{t})}\left(G_{t}-V\left(s_{t}\right)\right)} }\end{array}\) 其中 N 为状态 s 的访问次数

时序差分

时序差分是免模型的在线算法

\[ V\left(s_{t}\right)\leftarrow V\left(s_{t}\right)+\alpha\left(r_{t+1}+\gamma V\left(s_{t+1}\right)-V\left(s_{t}\right)\right) \]

其中 \(r_{t+1}+\gamma V(s_{t+1})\) 是称为时序差分目标(TD target)

时序差分误差（TD error）写作:

\[V\left(s_{t}\right)\leftarrow V\left(s_{t}\right)+\alpha\left(G_{i,t}-V\left(s_{t}\right)\right)\]

时序差分可以更改步数(走几步更新)

理论问题

模型

可以简单地讲选择 action 理解为分类问题, 损失函数使用交叉熵, 对不同的 s, 我们可能对执行的 action 有不同的期待, 因此可以设置一个损失函数的系数用于控制倾向性
那么如何定义 reward 呢?最直接的即时 reward 肯定不是最优解, 因此设置一个 Gn 表示 an 行为之后的所有回报和, 但对之后的回报要乘上一个惩罚系数 γ, 其次数逐渐增加; 此外, 可以使用将 G 减去一个 baseline 的值来产生不同行为的倾向性
rl, 准确地说是 on-policy 的 rl 与常见监督学习不同的是, 其训练资料在更新完一次模型后就无用了, 需要再次与环境互动收集资料
off-policy 则有所不同, 它让训练模型和互动的模型分开, 从而让经验可复用, 例如 Proximal Policy Optimization(PPO)

Critic actor: 我们希望有一个跟模型参数以及当前状态有关的函数 $ V^(s) $ 表示这种情况下的'价值', 可以理解为某个状态的预期回报
为了得到这个价值函数, 可以怎么做呢:

  • Monte-Carlo(MC): 较为直观的做法, 先训练大量的 s 及其 G 值, 然后用这些资料预测 V
  • Temporal-difference (TD): V 函数有以下性质:

\[\begin{array}{l}{ {V^{\theta}(s_{t})=r_{t}+\gamma r_{t+1}+\gamma^{2}r_{t+2}\ldots} }\\ { {V^{\theta}(s_{t+1})=r_{t+1}+\gamma r_{t+2}+\ldots} }\\ { {V^{\theta}(s_{t})=\gamma V^{\theta}(s_{t+1})+r_{t} } }\end{array}\]
那么 \[V^{\theta}(s_{t})-\gamma V^{\theta}(s_{t+1})\leftrightarrow r_{t}\]
通过这种关系就可以训练

现在我们有了 G 和 V, 两者区别是 G 有一个确定的 a, V 则假定 a 是随机的, 那么可以对每个 \(\{s_{t},a_{t}\}\) 对, 可以定义一个 \(\mathrm{A}_{t}\,=\,G_{t}^{\prime}-V^{\theta}(s_{t})\) , 用于表示这个行为的 "表现"
也可以用 $r_{t}+V^{}(s_{t+1}) $ 代替上式的 $ G^{'}_t $ , 此式相当于采取行为 \(a_t\) 后获得一个特定 \(r_t\) 后的预期收益, 这称为 Advantage Actor-Critic

Reward Shaping: 对回馈比较模糊或者非常慢的场景来说, 想要好的表现就需要人为规定一些回报机制, 例如对游戏 ai 来说, 就需要惩罚什么都不做的行为(否则机器为了回报不为负就可能消极游戏); 其中一种机制称为 Curiosity, 也就是奖励机器发现新信息的情况

现实中不是所有情况都可以定义 reward, 此时只能通过人类提供示范来让机器学习, 这样当然会有很多问题, 比如数据集里没有错误示范等, 因此, 可能的思路是通过机器学习来找到 reward 再进行学习
Inverse Reinforcement Learning: 假设老师行为是最优的, 在每次迭代中:

  1. actor 与环境互动
  2. 定义一个奖励函数, 满足老师的奖励更优这个条件
  3. actor 根据这个奖励函数进行学习

模仿学习

缺点:

  1. 人类演示数据可能有很多模式, 不确定性较强, 且很可能不符合马尔科夫假设
  2. 演示数据往往更多倾向于成功的情况, 令模型没有从错误恢复的能力, 导致错误逐渐积累, 最终效果极差

改进:

  1. 使用 rnn, lstm 等方法，通过上下文学习专家演示数据； 这样的缺点是, 由于 rl 很多场景都有较强的因果特征, 这种情况很可能会错误地归因
  2. 对于人类的复杂行为模式，可以使用多个高斯分布模拟，或者使用潜空间捕获特征(例如标准流); 以及 autoregressive discretization(自回归离散化)