强化学习笔记 all in one

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

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)]\)

模仿学习

缺点:

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

改进:

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

一个比较常见的算法称为 Dagger , 其流程可以写作如下:

  1. 首先使用专家演示的行为来训练一个初始策略
  2. 然后让该策略在环境中执行, 并记录下其在整个状态空间中访问过的状态-动作对
  3. 这些状态-动作对让专家进行标注, 将得到的新数据放入数据池
  4. 使用这个新的训练集, 再次训练出一个更加接近专家的策略
  5. 重复上述过程, 直到策略收敛

hw1

训练目标可以表示为以下不等式:

\[\mathbb{E}_{p_{\pi}*(s)}\pi_{\theta}(a\not=\pi^{*}(s)\mid s)={\frac{1}{T}}\sum_{t=1}^{T}\mathbb{E}_{p_{\pi}*(s_{t})}\pi_{\theta}(a_{t} \not =\pi^{*}(s_{t})\mid s_{t})\leq\varepsilon,\]

即: 给定随机专家轨迹与其状态分布, 在相同状态下训练策略产生的动作期望和专家策略产生的动作期望差值小于 \(\epsilon\) , 其中 \(p_{\pi}(s_{t})\) 表示给定 π 在时间 t 的状态分布

策略梯度

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}\]

这种方法称为 full fitted Q-iteration algorithm, 其中 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 也不保证收敛

局限

目前版本的 q 学习是一个随着时间收集数据的 on-line 方法, 除了效率问题外, 由于数据在时间上过于接近, 很可能产生过拟合问题, 类似策略梯度, 可以对其进行离线改进, 并且由于 q 学习的策略不那么重要, 可以说它很适合离线学习
另一种方法称为 replay buffers, 简单地说就是去掉收集数据的步骤, 对一个巨大的数据池，每次随机取样用来不断进行预测和模型更新, 更新若干轮后再产生一些新数据放入 buffers 池

上图展示了目前为止的 q 学习步骤, 按经验来说一般 k 设置很小, 而 n 较大, 这会带来一个问题, 即更新模型参数的周期中, 早期采样数据 "落后(lag)" 得少, 而随着训练进行就会有很多落后很久的数据, 为了避免这个问题, 使用以下的更新方式
\(\begin{array}{c c}{ {\mathrm{update}~\phi^{\prime};~\phi^{\prime}\leftarrow\tau\phi^{\prime}+(1-\tau)\phi}}&{ {\qquad\qquad\tau=0.999~\mathrm{works~well}}}\end{array}\)
为了减少上述伪梯度的影响, 对更新梯度, 我们用整体更新前的目标网络生成的 max 参数来更新临时网络参数
以上的伪代码写作单线程迭代的形式, 但其实由于目标网络在一整批数据后才更新, 上述过程可以并行进行, 也就是用于规模庞大的深度学习中, 即(DQN Deep Q-Network) 此外, 对于整个 buffer 的维护, 由于 buffer 存在上限, 那么就必然需要一个“驱逐”机制, 一个简单的思路是采用环形 buffer, 使用以上机制的一个 dpo 流程可以表示为下图:

不同的 q 学习对 3 个 process 各有侧重:

  1. online q learning: process1,2,3 have same speed
  2. DQN: process 1,3 have same speed, process 2 is slow, buffer is large
  3. fitted q-iteration: process 3 在 process 2 的内循环中, process 2 在 process1 的内循环中

改进

实际的 q 学习中, 有一个神奇的现象, q 的估计器整体性地高估 q 的值, 而不是在真实值的上下浮动
对任意两个随机变量 x1, x2, 有如下不等式:
\(E[\operatorname*{max}(X_{1},X_{2})]\geq\operatorname*{max}(E[X_{1}],E[X_{2}])\)
也就是直观地说, 取 max 的范围越大, 这个 max 倾向越大的值, 而我们在取 Q 函数的估计时，会不断用过往的最高 q 值来更新模型, 而这个过往的 q 可能来自于某个误差, 假设这个误差来自于随机高斯分布, 有正有负, 由于我们总取最大值, 那么正误差的值就会被倾向于被用来更新
如何解决这个问题？一个想法是, 将 q 的评估和更新分开, 称为 double q-learning , 其更新步骤为: \(Q_{\phi_{A}}(\mathrm{s},\mathbf{a})\leftarrow r+\gamma Q_{\phi_{B}}(\mathrm{s}^{\prime},\mathrm{arg~max}\,Q_{\phi_{A}}(\mathrm{s}^{\prime},\mathbf{a}^{\prime}))\)
实际中, 我们正好有目标网络和训练网络两个网络, 可以用作这里的 A 和 B, 当然由于这两个网络其实会经常合并, 这样理论上还有问题, 但一般来说实际中效果尚可
另一个方法称为 multi-step returns, 上面提到过 q 学习的迭代初期可能有非常糟糕的表现, 此时我们更看重采取某个动作后的回报值, 这个问题比较类似 a-c, 可以用多步的回报值解决(在 a-c 中我们用这个办法缓解策略更新的高方差), 即将更新步骤设置为: \(y_{j,t}=\sum_{l^{\prime}=t}^{t+N-1}\gamma^{t-t^{\prime}}r_{j,t^{\prime}}+\gamma^{N}\operatorname*{max}_{\Omega_{k},t+N}Q_{\phi^{\prime}}(\mathbf{s}_{j,t+N,\,\Omega_{j,t+N}})\)
此外, 这种方法会让训练必须是 on-policy 的, 因为这 n 步的策略必须是被固定的, 当然, 也可以当做这个问题不存在, 毕竟理论上 n 不大的话策略不会改变太多, 又或者实现类似之前的重要性采样

连续动作

连续动作空间的麻烦在于, 如何处理取 Qmax 的操作, 一个基于直觉的想法是梯度下降找机制, 但这样显然计算量很大
为了提高效率, 一个简单的做法是对 Q 随机取 n 个样, 选一个最大值, 这称为 stochastic optimization ; 这种方法有一些改版, 例如通过交叉熵优化采样
另一个不依赖随机的做法是, 用有数值解的函数来表示 Q 函数, 例如二次函数: \(Q_{\phi}({\bf s},{\bf a})=-\frac{1}{2}({\bf a}-\mu_{\phi}({\bf s}))^{T}P_{\phi}({\bf s})({\bf a}-\mu_{\phi}({\bf s}))+V_{\phi}({\bf s})\)
从而: \(\quad\arg\operatorname*{max}_{\mathbf{a}}Q_{\phi}(\mathbf{s},\mathbf{a})=\mu_{\phi}(\mathbf{s})\qquad\quad\operatorname*{max}_{\mathbf{a}}Q_{\phi}(\mathbf{s},\mathbf{a})=V_{\phi}(\mathbf{s})\)
这样以降低表达能力为代价, 得到了高效取 max 的方法
以及, 训练一个独立的网络来取 max, 有点类似于 a-c
m ## 最优控制 这一章的目的在于为基于模型的 rl 做铺垫, 这里先引入几个名词:

  1. 最优控制(optimal control): 即控制一个系统达到一个最优指标, 在 rl 中就是回报最大化
  2. system dynamic: 即系统根据行动其状态会怎么变化
  3. closed/open-loop 闭/开环控制: 简单地说, 闭环指的是做出行动后会得到行动后的系统状态, 用于下一次行动, 开环则相反, 做出行动后并不知道之后会发生什么; 根据定义来看, 很明显 rl 一般是闭环的, 如果不知道采取行动后的状态, 就很难进行学习
  4. 控制领域常用 x, u 表示 rl 中的 s, a, 用 c(cost)表示成本, 最小化成本而不是最大化回报

本章中, 我们假设 s-d 完全已知, 无论状态转移是确定还是基于概率的, 目标都是最大化回报, 基于概率的情况下需要最大化的是期望回报
最简单的做法是之前提到过的随机取 k 个样本取其中的最佳, 对其的改进是 Cross-Entropy Method(cem), cem 让每次的 k 个取样服从一个分布例如高斯分布, 使用最大似然来拟合分布, 让分布去拟合那些有更高值的数据
基于采样的方法在工程上很实用, 但一旦遇到比较多的维度即比较复杂的情况, 效果就不行了
另一个常见方法是蒙特卡洛(Monte Carlo tree search (MCTS)), 也就是状态为节点, 动作与其对应回报作为边的树, 根据这个树先选择一个状态, 然后选择一个行动进行, 一路记录回报来更新树, 如此迭代
具体策略上有很多选择, 这里暂且略过
选定一个初始的(x, u)对, 最小化之后的 cost, 这称为 shotting method(s-m), 下面引入一个经典场景: 线性的状态转移与二次的 c 函数
\[f(\mathbf{x}_{t},\mathbf{u}_{t})=\mathbf{F}_{t}\left[\begin{array}{l}{ {\mathbf{x}_{t}}}\\ { {\mathbf{u}_{t}}}\end{array}\right]+\mathbf{f}_{t}\]
\[c({\bf x}_{t},{\bf u}_{t})={\frac{1}{2}}\left[\begin{array}{c}{ { {\bf x}_{t}}}\\ { { {\bf u}_{t}}}\end{array}\right]^{T}{\bf C}_{t}\left[\begin{array}{c}{ { {\bf x}_{t}}}\\ { { {\bf u}_{t}}}\end{array}\right]+\left[\begin{array}{c}{ { {\bf x}_{t}}}\\ { { {\bf u}_{t}}}\end{array}\right]^{T}{\bf c}_{t}\]
目标表示为 \[\operatorname*{min}_{\mathbf{u}_{1},\ldots,\mathbf{u}_{T}} c({\bf x}_{1},{\bf u}_{1})+c(f({\bf x}_{1},{\bf u}_{1}),{\bf u}_{2}){ {+\;\cdot\;\cdot\;+\;c}}(f(f(\cdot\cdot\cdot)\;\cdot\;\cdot\;\cdot),\,{\bf u}_{T})\]

\[c_T = \left[\begin{array}{l}{ {\mathbf{c_{x_{T}}}}}\\ { {\mathbf{c_{u_{T}}}}}\end{array}\right]\]
\[C_T= \begin {pmatrix} C_{X_T,X_T} & C_{X_T,U_T} \\ C_{U_T,X_T} & C_{U_T,U_T} \end{pmatrix}\] \[Q({\bf x}_{T},{\bf u}_{T})=\mathrm{const}+\frac{1}{2}\left[\begin{array}{c}{ { {\bf x}_{T}}}\\ { { {\bf u}_{T}}}\end{array}\right]^{T}{\bf C}_{T}\left[\begin{array}{c}{ { {\bf x}_{T}}}\\ { { {\bf u}_{T}}}\end{array}\right]+\left[\begin{array}{c}{ { {\bf x}_{T}}}\\ { { {\bf u}_{T}}}\end{array}\right]^{T}{\bf c}_{T}\]

通过对 u 求导, 很容易能算出这个二次函数的极值, 也就是最优动作, 省略这些让人头疼的推导, 我们需要知道的是, 这个最佳的 u 依赖我们不知道的 x
将这个最佳的 u 代入, 则可以消除 u， 得到对一个特定 x 的 V 值
在以上这些推导后, 我们会得到一个用 T 时刻的(u, x)及其 Q, V 推导 T-1 时刻的(u, x)的 Q, V 的方式, 从而可以不断进行迭代
在基于概率的情况, 例如状态转移服从一个均值为确定性转移的高斯分布的情况下, 此时的 u 最优解其实保持不变, 从而可以进行类似确定情况的迭代
在 LQR(iLQR)方法中, 通过泰勒展开式局部展开来估计状态转移, 也就是:
\[f({\bf x}_{t},{\bf u}_{t})\approx f({\hat{\bf x}}_{t},{\hat{\bf u}}_{t})+\nabla_{ {\bf x}_{t},{\bf u}_{t}}f({\hat{\bf x}}_{t},{\hat{\bf u}}_{t})\left[\begin{array}{c}{ {\delta{\bf x}_{t}}}\\ { {\delta{\bf u}_{t}}}\end{array}\right]\] 著名的牛顿法也是类似的原理, 只不过多展开了一项二次项

model-based rl

虽然我们之前并没有讲模型方法, 但其实这和 ml 很像, ml 中代理努力去拟合专家的数据, 在神经网络的典型任务例如回归、分类中, 网络也努力地拟合训练数据, 因此在 rl 常常面临的场景下, 如果训练一个预测状态转移的模型, 这会产生类似的问题, 也就是实际场景中概率分布会和训练数据时的不同, 这个问题的原因之前也遇到过, 就是因为不同的策略会产生不同的状态分布
如果以之前的思路, 可以用一个 buffer 来缓解这个问题, 也就是现实应用中每执行一次或者一轮动作, 将数据放入 buffer, 定期重新学习, 这和 dagger 几乎完全一样
这个过程中错误数据也是很重要的, 因此事实上, 每个学习周期中下图的第 3. 步经常执行很多次

很微妙的是, 在伯克利的实验中, m-b(model-based)方法效果比无模型方法差很多, 其可能的主要原因是, 由于模型很难彻底拟合 rl 场景中的状态转移(例如一些变化很陡峭的情况), 对风险很大的一部分, 模型都会悲观地估计它, 举个例子来说, 例如在悬崖边有很高的回报, m-b 方法在掉下去一次后, 很难找到一个悬崖边得到高回报但不会掉下去的状态, 只会悲观地把周边一大片都给出一个较低的价值
如果有足够的数据, 可能最终模型还是能收敛到一个较好的表现, 因此我们可能需要一个 explore 机制
很显然对大部分 rl 场景中的不确定因素, 不能用标准正态分布这样简单的想法来看待, 那么如何处理呢？ 例如我们上文中曾经提过基于交叉熵优化采样的方法?
基于熵的优化是行不通的, 这是因为熵只能用于估计不确定性, 不能用于估计不确定性的类型, 例如如果我们将不确定性用高斯分布建模, 均值和方差的选取就是个难题, 很可能有过拟合的现象出现
另一个思路是, 既然不知道环境的不确定性, 那么就去关注模型的不确定性, 也就是说, 一般来说假设 \(\operatorname{arg\,max\,log}p(\theta|D)=\operatorname{arg\,max\,log}p(D|\theta)\) , 如果这个假设不对, 怎么得到 \(p(\theta|D)\) 的估计
常见的方法有: 边缘概率乘积, 估计高斯分布等
此外有一种称为 bootstrap ensembles 的方法: 直观地说, 即训练很多个模型, 用它们的均值减少不确定性

基于图像的任务

基于图像的 rl 的难点在于, 观察和状态是分开的, 知道观察(图像)并不能知道状态, 当然可能直接用观察也能训练, 但就马尔科夫假设来说, 应当是状态转移到新的状态, 而不是观察
也就是说这种任务满足部分可观察的马尔科夫假设, 将其状态空间称为(latent space 潜空间)
这种情况下将问题分解为求观察-状态, 状态转移， 状态动作-回报， 三对关系:
\[\begin{array}{c}{ {p(\mathbf{O}_{t}|\mathbf{S}_{t})}}\\ { {p(\mathbf{S}_{t+1}|\mathbf{S}_{t},\mathbf{a}_{t})}}\\ { {p(r_{t}|\mathbf{s}_{t},\mathbf{a}_{t})}}\end{array}\]

基于策略的 m-b rl

这章中提及的 1.5 版方法, 其实就是控制论中的 MPC(model predictive control 模型预测控制), 也就是不断预测未来状态并以此优化控制问题
此前我们通过对状态转移的局部估计来不断迭代选择最佳动作, 从而作为策略, 那么有没有办法让模型直接生成策略呢？
这看上去应该很简单, 我们先训练状态转移预测模型, 然后用这个模型跑数据, 不断反向传播来优化一个基于模型的策略 πθ
类似 shooting method(不断从前往后确定一个决策), 这样的问题是前面的决策会有更大的重要性和敏感性, 于是就会产生神经网络的常见问题, 要么梯度爆炸, 要么梯度消失
如果用二阶优化器来解决这种不对称, 又会造成时间序列性的消失, 此外也会有更大的计算量
那么在神经网络里如何解决这种问题呢？常见的思路是使用 LSTM, 但由于 rl 中状态转移是由外部环境决定的, LSTM 以及大部分深度学习的 trick 则一般自己选择“状态”的转化, 所以也不是那么方便
因此, 放弃反向传播, 改用基于采样的策略梯度:

下一个问题依然是, 如何处理这种理论最优和实际情况的差距, 换句话说, 我们训练的是一个在给定状态转移模型下最优的策略, 而这个状态转移模型也是拟合出来而不是真实的, 因此真实情况下这个策略模型也会不断积累错误
事实上, 这种实际情况下的误差是随着时间快速增长的, 但由于 rl 的场景限制, 不可能缩短 horizon, 这样会让一些后期状态无法被学习, 因此我们找一个折中的方法:
收集一些真实环境下的轨迹, 随机选择这些轨迹中的随机状态, 从随机状态开始执行较短的迭代并更新策略梯度, 这样的好处是能兼顾不同时间步下的数据, 且避免误差随着时间无法抑制地增长
显然, 如果更新策略, 之前的轨迹数据就和当前不符合了, 类似之前的 Q 学习或者 a-c, 实际中我们一般在一定范围内忽略这种策略更新带来的误差

将这种方法用到之前的基于 buffer 的方法上, 就能得到:

相比之前方法的改进是: 用真实数据训练模型, 再将模型生成的数据也作为数据池用来 Q 学习

探索

多臂老虎机

教授举了一个很有趣的例子, 多臂老虎机问题就是 rl 中的果蝇, 是非常经典的示例问题
所谓的多臂老虎机, 就是一个有多个可选拉杆的老虎机, 也就是说它的性质是: 离散有限的动作空间且没有状态
在探索这个问题中, 定义遗憾值(regert)为理论最佳策略期望收益与实际策略期望收益的差值
最简单地策略就是一直选取平均收益较高的动作, 如果想兼顾一些探索, 则可以加上一个带权重的收益标准差： \(a=\arg\operatorname*{max}{\hat{\mu}}_{a}+C\sigma_{a}\) 因为可以认为标准差高的动作有较大的不确定性, 需要更多探索
还有一个问题是什么时候终止探索, 这应该有两个参数: 随着时间探索的权重应该减少；且随着次数增加探索也应该减少: \(a=\operatorname{arg\,max}{\hat{\mu}}_{a}+{\sqrt{\frac{2\ln T}{N(a)}}}\) (UCB)这种方法理论上能将遗憾控制在 O(logT)
第三种方法是, 定义 \({\mathrm I G}(z,y|a)=E_{y}[{\mathcal H}({\hat{p}}(z))-\mathcal A({\hat{p}}(z)|y)|a]\) 其中 IG( information gain)指的是从给定 y 中得到的额外信息, H 则是概率分布的熵
例如, \(\Delta(a)=E[r(a^{\star})-r(a)]-expected~suboptimality~of~a\) \(y=r_{a},\;z=\theta_{a}\)(θ 为模型参数), 从而选择的 a 满足 \({\frac{\Delta(a)^{2}}{g(a)}}\)
当然, 也有基于概率(分类器)的方法, 也就是训练一个模型, 或者使用某种启发式方法, 估计一个状态是否是值得探索的
这个模型可以不那么精确, 从而用模型与实际奖励的误差值作为 novel(新颖)程度
还有类似之前的贪婪 \(\epsilon\) 的方法, 也就是使用一个不同的 Q 函数 buffer, 每次采样一批, 将其视为正确的, 进行探索来得到一些数据, 再放入池子, 这么做的问题在于, 每次的一批数据可能不够让模型学到一些长期决策的方法
模型参数 θ 也可以作为 IG(信息增益)的计算对象, 也就是选择那些能让模型参数变化较大的数据进行探索, 这实际上可以用给定模型更新条件前后的 θ 分布之间的 KL 散度来衡量

基于信息论的情况

首先引入一些信息论的概念: \[{\mathcal{p}}{(}\mathbf{x}{\big)}\qquad{\mathrm{distribution~}}\left(\operatorname{e.g.,~over~oloservations~x}\right)\]
\[{\mathcal{H}}(p(\mathbf{x}))=-E_{\mathbf{x}\sim p(\mathbf{x})}[\log p(\mathbf{x})]\]
直观地说, 熵 H 可以衡量一个概率分布的“宽度”, 熵越大, 分布越宽, 不确定性越大
\[\begin{array}{r l}{\mathbb{I}(\mathbf{x};\mathbf{y})=D_{\mathrm{KL}}(p(\mathbf{x},\mathbf{y})||p(\mathbf{x})p(\mathbf{y}))}\\ {=E_{(\mathbf{x},\mathbf{y})\sim p(\mathbf{x},\mathbf{y})}\left[\log{\frac{p(\mathbf{x},\mathbf{y})}{p(\mathbf{x})p(y)}}\right]}\\ {=\ H(p(\mathbf{y}))-H(p(\mathbf{y}|\mathbf{x}))}\end{array}\]

那么在强化学习中变量分布的熵及其互信息有什么用呢, 举一个例子, 以下的互信息被称为 empowerment(赋能):

\[\mathcal{I}(\mathbf{s}_{t+1};\mathbf{a}_{t})=\mathcal{H}(\mathbf{s}_{t+1}){-}\mathcal{H}(\mathbf{s}_{t+1}|a_{t})\]

直观地说, 它衡量了在状态 s 下, 采取不同动作 a 能让下一个状态 s′的熵(混乱程度)变化多少, 而在 rl 中, 一个理想的状态是: 这个状态有很多种选择, 也就是熵比较大; 但采取不同的动作能极大地限制未来状态的分布, 从而互信息较大的(s, a)对就是理想的

生成式

在探索问题中, 生成模型可以用来产生新的训练数据, 一般来说我们使用最大似然估计, 也就是让生成的数据分布和真实数据分布尽可能接近, 产生真实数据的概率最大, 但为了探索, 我们希望生成一些和真实数据分布不太一样的数据, 也就是让生成数据的熵更大一些, 这可以通过将最大似然估计改为加权似然估计来实现, 也就是对生成真实数据的概率加权, 如果是一个熟悉的状态, 则降低其权重, 反之增加权重

intrinsic motivation

简单地说就是一些小窍门, 例如将奖励设为: \(\tilde{r}(\mathbf{s})=r(\mathbf{s})-\log p_{\pi}(\mathbf{s})\)
这样的好处是, 能均匀地探索所有状态空间, 而且实现也相对简单
那么, 为什么要探索整个状态空间, 这样是正确的吗？ 事实上有一个符合常识的定理: 如果你想最大化代理在最糟糕情况下的表现, 那么你就必须探索所有可能的状态空间

off-policy rl

课程此前提到过的 off-policyrl, 例如 Q 学习实质上依旧依赖一个数据 buffer, 执行有偏的策略或者 Q 函数更新, 因此必须每隔一段时间更新数据或者让一个子进程来不断更新 buffer
而对所谓互联网规模的模型, 例如 cv, nlp 领域中, 那些性能强大的大模型往往是直接用互联网上的极大规模数据来训练的, 那么对于需要和环境互动得到 reward 的 rl 来说, 能否通过彻底的 off-policy 方法实现完全基于数据的学习呢?
首先明确 o-p 的定义, 上图的 d 指的是给定策略和初始状态的状态边缘分布
o-p rl 的目标是, 给定一个数据集 D, 只用这个数据集来学习, 用于得到数据集的策略和要学习的策略 π 完全无关, 找到一个策略 π 最优化 J 函数, 也就是初始状态的期望总回报
由于学习策略无法与环境互动, 按直觉想, 其策略空间，或者说策略参数 θ 的空间大小取决于数据集, 于是这个最佳策略的定义也会取决于给定数据集
由此产生了一个问题, 是否学习策略最好的情况就是等于数据集里最佳的策略呢?
事实上, o-p 理想的情况下比较像裁缝, 能把不同数据中局部的最优策略学过来, 因此理论上能超越数据集中的最佳策略
先不论理论最优的情况, 由于 o-p 情况下策略无法在实际情况下被验证并修复错误, 很可能会非常糟糕地错误估计某些情况, 从而表现很差
这种糟糕地表现往往来自于数据集中一些特定情况下数据的缺失, 也就是所谓的 "out-of-distribution" actions , 而问题在于, 想增强模型的泛化能力就必须假设模型理解了这些动作, 但如果模型没有真正理解, 则可能出现灾难性后果

马尔可夫过程

马尔可夫过程中, 对一个特定状态则有一个特定的未来状态概率分布（可以理解为策略）, 很容易算出之后的期望回报
即, 如果我们希望知道一个特定状态是好是坏, 可以定义状态价值 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 根据这个奖励函数进行学习