强化学习笔记 all in one

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

基础概念

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

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

取梯度

$$ \begin{align*}{r l}{\nabla{\bar{R} }_{\theta} \\ =\sum_{\tau}R(\tau)\nabla p_{\theta}(\tau)}&{\\ =\sum_{\tau}R(\tau)p_{\theta}(\tau){\frac{\nabla p_{\theta}(\tau)}{p_{\theta}(\tau)} } } \\ &=\sum_{\tau}R(\tau)p_{\theta}(\tau){\nabla}l o g p_{\theta}(\tau) \\ &=E_{\tau \sim p_{\theta}(\tau)}[R(\tau)\nabla l o g p_{\theta}(\tau)]\approx\frac{1}{N}\sum_{n=1}^{N}R(\tau^{n})\nabla \log p_{\theta}(\tau^{n}) \\ &={\frac{1}{N} }\sum_{n=1}^{N}\sum_{t=1}^{T_n}R(\tau^{n})\nabla l o g p_{\theta}(a_{t}^{n}|s_{t}^{n}) \end{align*} $$

虽然回报值一般是很难预测的，但是就梯度下降来说这只是个常数，这里取出一个log的微分形式，由于轨迹的概率可以用采样估算，接下来只需要处理log，这个轨迹概率 $ {P(|)=} {p(s_{1})p(a_{1}|s_{1},)p(r_{1},s_{2}|s_{1},a_{1})p(a_{2}|s_{2},)p(r_{2},s_{3}|s_{2},a_{2})} $ 事实上就是轨迹初始状态的概率与一连串的条件概率相乘，对其取微分，忽略与θ无关的项，可以将积转化为和，得到最后这个式子
类似于机器学习的梯度下降，我们通过梯度计算寻找最大化reward的参数，也就是总回报为正时让相关行动的概率增加，为负时相反
这里会用到log的微分，考虑其性质就知道，这会概率，也就是用来估算的采样到的频率，较低的极端值影响，如果运气不好没有采样到某个动作，还会让其他动作相对更高，因此可以考虑将总回报减去一个baseline（因为这里控制倾向性的其实是回报的正负以及大小
和log函数的很多应用场景一样，这里实际上可以理解为分类问题，因为模型输出的动作是有限的，策略最后产生的是动作空间中的概率分布，稍微不同的是需要乘回报值，并且要分很多轮训练

马尔可夫过程

马尔可夫过程中，对一个特定状态则有一个特定的未来状态概率分布（可以理解为策略），很容易算出之后的期望回报
即，如果我们希望知道一个特定状态是好是坏，可以定义状态价值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的访问次数，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) \]

理论问题

模型

可以简单地讲选择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根据这个奖励函数进行学习