开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 人工智能 -> 《深入浅出强化学习：原理入门》学习笔记 -> 正文阅读

[人工智能]《深入浅出强化学习：原理入门》学习笔记

1 绪论

1.1强化学习可以解决什么问题

? ? ? ? 用一句话来概括强化学习能解决的问题就是：智能决策问题。更确切地说是序贯决策问题。

????????序贯决策问题：需要连续不断地做出决策，才能实现最终目标的问题

1.2 强化学习如何解决问题

? ? ? ? 监督学习解决的问题：智能感知的问题。监督学习需要感知到当前的输入是怎样，并给出对应的输出（标签）。智能感知必不可少的前提是大量长相差异化的输入以及与输入相关的标签。

????????监督学习解决问题的方法：输入大量带有标签的数据，让智能体从中学到输入的抽象特征并预测。

? ? ? ? 强化学习解决的问题：序贯决策问题。不关心输入长什么样，只关心当前输入下应该采用什么动作才能实现最终的目标。简单地说就是，当前采用什么动作可以使得整个任务序列达到最优。

? ? ? ? 强化学习解决问题的方法：智能体不断地与环境进行交互，不断尝试，通过动作与环境进行交互时，环境会返回给智能体一个当前的回报，智能体则根据当前的回报评估所采取的动作：有利于实现目标的动作被保留，不利于实现目标的动作被衰减。

? ? ? ? 总的来说，强化学习和监督学习都需要大量的数据进行训练，前者需要带有回报的交互数据，后者需要的则是标签数据。

1.3 强化学习的算法分类

?根据强化学习算法是否依赖模型分：基于模型的强化学习算法和无模型的强化学习算法。有模型算法先利用与环境交互得到的数据学习系统或者环境模型，再基于模型进行序贯决策。无模型算法直接利用与环境交互得到的数据改善自身的行为。
根据策略的更新和学习方法分：基于值函数的强化学习算法、基于直接策略搜索的强化学习计算法和AC的方法。
根据环境返回的回报函数是否已知分：正向强化学习和逆向强化学习。

? ? ? ? 从广义上将，强化学习是序贯决策问题。序贯决策问题既包含马尔科夫过程的决策，也包含非马尔科夫决策过程的决策。可以将强化学习纳入到马尔科夫决策过程MDP的框架之内。再根据转移概率P是否已知，可以分为基于模型的动态规划方法和基于无模型的强化学习方法。这两个类别都包括策略迭代算法、值迭代算法和策略搜索算法。另外，在无模型的强化学习方法中，每类算法又分为online和offline两种。

1.4 强化学习的发展历史及趋势

? ? ? ? 第一个关键点：1998年，Richard S. Sutton出版了Reinforcement Learning：An introduction

总结了1998年以前的各种强化学习算法的发展。

? ? ? ? 第二个关键点：2013年DeepMind提出DQN(Deep Q Network)，将深度网络与强化学习算法结合形成深度强化学习（Deep Reinforcement?Learning，DRL）。

? ? ? ? 发展趋势：与深度学习结合、理论分析更强、算法更稳定高效、与脑科学联系紧密

2 马尔科夫决策过程

2.1 马尔科夫决策过程理论讲解

? ? ? ? 第一个概念：马尔科夫性

????????系统的下一个状态仅与当前的状态有关，而与以前的状态无关。即：若状态 $\small S_{t}$ 是马尔科夫的，则：

$\small P(S_{t+1}|S_{t}) = P(S_{t+1}|S_{1},\cdot \cdot \cdot ,S_{t})$

? ? ? ? 第二个概念：马尔科夫过程

? ? ? ? 马尔科夫过程：一个二元组（S,P），且满足：S是有限状态集合，P是状态转移概率矩阵

? ? ? ? 第三个概念：马尔科夫决策过程

? ? ? ? 马尔科夫决策过程：一个五元组 $\small (S,A,P,R,\gamma )$ ，其中S是有限状态集合，A是有限动作集合，P是状态转移概率矩阵，R是回报函数， $\small \gamma$ 是折扣因子，用来计算累计回报。

? ? ? ? 马尔科夫决策过程的状态转移概率（动态特性）：

$\small P^a_{ss'}=P[S_{t+1}=s'|S_{t}=s,A_{t}=a]$

? ? ? ? 有些情况下，也可以写成：

$\small P^a_{ss'}=P[S_{t+1}=s',R_{t+1}=r|S_{t}=s,A_{t}=a]$

? ? ? ? 这是因为考虑到了即时回报函数也有可能是一个随机变量。

? ? ? ? 强化学习的目标是给定一个马尔科夫决策过程，寻找最优策略。

????????所谓策略是指状态到动作的映射，策略常用符号 $\small \pi$ 表示，它是指给定状态s时，动作集上的一个分布：

$\small \small \pi(a|s)=p[A_{t}=a|S_{t}=s]$

其含义是策略 $\small \pi$ 在每个状态s指定一个动作概率。

? ? ? ? 要注意，策略也可以是确定性的，即在某一种状态下采取的动作时确定的。

? ? ? ? 所谓最优策略是指得到的累计回报最大，累计回报的定义如下：

? ? ? ? $\small G_{t}=R_{t+1}+\gamma R_{t+2}+\cdot \cdot \cdot =\sum_{k=0}^{ \infty }\gamma^k R_{t+k+1}$

? ? ? ? 为了使用一个确定量来描述状态 $\small s_{1}$ 的价值，可以考虑使用累计回报 $\small G_{1}$ 来衡量，但其是一个随机变量，因此考虑其期望值，并作为状态值函数的定义。

? ? ? ? （1）状态-值函数和状态-行为值函数

? ? ? ? 当智能体采用策略π时，累计回报服从一个分布，累计回报在状态s处的期望值定义为状态-值函数：

? $\small \small \nu _{\pi}(s)=E_{\pi}[\sum_{k=0}^{ \infty }\gamma^k R_{t+k+1}|S_{t}=s]$ ? ? ?

? ? ? ? ?相应地，状态-行为值函数为：

? $\small q _{\pi}(s,a)=E_{\pi}[\sum_{k=0}^{ \infty }\gamma^k R_{t+k+1}|S_{t}=s,A_{t}=a]$

? ? ? ? （2）状态-值函数和状态-行为值函数的贝尔曼方程

$\small \nu(s)=E[G_{t}|S_{t}=s]=E[R_{t+1}+\gamma\nu(S_{t+1})|S_{t}=s]$

$\small q_{\pi}(s,a)=E[R_{t+1}+\gamma q(S_{t+1},A_{t+1})|S_{t}=s,A_{t}=a]$

? ? ? ? ?对状态-值函数进行分解，得到：

$\small \nu_{\pi}(s)=\sum_{a \in A}\pi(a|s)q_{\pi}(s,a)$

$\small q_{\pi}(s,a)=R_{s}^a+\gamma\sum_{s'\in S}P_{ss'}^a\nu_{\pi}(s')$

????????即根据策略在状态s的条件下采取动作a得到的累计回报q(a,s）是当前的累计回报 $\small R_{s}^a$ 加上未来各种可能的状态得到的回报的加权平均。整合两个公式可以得到：

$\small \small q_{\pi}(s,a)=R_{s}^a+\gamma\sum_{s'\in S}P_{ss'}^a\sum_{a'\in A}\pi(a'|s')q_{\pi}(s',a')$

? ? ? ? （3）最优状态值函数和最优状态状态-行为值函数的贝尔曼最优方程：

$\small \nu^*(s)=\max_{a}R_{s}^a+\gamma\sum_{s' \in S}P_{ss'}^a\nu^*(s)$

$\small q^*(s,a)=R_{s}^a+\gamma\sum_{s' \in S}P_{ss'}^a\max_{a'}q^*(s',a')$

?2.2 强化学习算法的形式化描述

? ? ? ? 定义一个离散时间有限范围的折扣马尔科夫决策过程 $\small M=(S,A,P,r,\rho _{0},\gamma,T)$ ,其中S为状态集，A为动作集， $\small P:S\times A\times S\rightarrow R$ 是转移概率， $\small r:S\times\rightarrow A[-R_{max},R_{max}]$ 为立即回报函数， $\small \rho_{0} :S\times A\rightarrow R$ 是初始状态分布， $\small \gamma\sqsupset \in [0,1]$ 为折扣因子，T为水平范围（其实就是步数）。 $\small \tau$ 为一个轨迹序列，即 $\small \tau=(s_{0},a_{0},s_{1},a_{1},\cdot \cdot \cdot )$ ，累计回报为 $\small R=\sum_{t=0}^{T}\gamma ^tr_{t}$ ,强化学习的目标是找到最优策略 $\small \pi$ ,使得该策略下的累计回报期望最大，即 $\small max\int R(\tau)p_{\pi}(\tau)d\tau$

?3 基于模型的动态规划方法

? ? ? ? 基于模型的强化学习可以利用动态规划的思想来解决。利用动态规划可以解决的问题需要满足两个条件：一是整个优化问题可以分解为多个子优化问题；二是子优化问题的解可以被存储和重复利用。

? ? ? ? 由于强化学习可以归于马尔科夫决策问题的框架之下，通过上一节得到的状态-值函数贝尔曼最优方程可以看出，马尔科夫决策问题符合使用动态规划的两个条件，因此可以使用动态规划来解决基于模型的强化学习问题。? ? ?

3.1 策略迭代算法

? ? ? ? 策略迭代算法包括策略评估和策略改进两个步骤。在策略评估中，给定策略，通过数值迭代算法不断计算该策略下每个状态的值函数，利用该值函数和贪婪策略得到新的策略。如此循环下去，最终得到最优策略。

3.1.1 策略评估

? ? 对于模型已知强化学习算法，我们有状态-值函数：

$\small \nu_{\pi}(s)=\sum_{a \in A}\pi(a|s)(R_{s}^a+\gamma\sum_{s'\in S}P_{ss'}^a\nu_{\pi}(s'))$

其中，根据模型已知，状态转移概率 $\small P_{ss'}^a$ 、即时回报 $\small R_{s}^a$ 、折扣因子 $\small \gamma$ 已知，要评估的策略 $\small \pi(a|s)$ 是指定的，故只有值函数是未知的。问题转化为关于值函数的线性方程组，其未知数的个数为状态的总数。

? ? ? ? （1）解析解

???????? $\small \nu_{\pi}(s)=\sum_{a \in A}\pi(a|s)R_{s}^a+\gamma\sum_{s'\in S}\sum_{a \in A}\pi(a|s)P_{ss'}^a\nu_{\pi}(s'))$

$\small \sum_{a \in A}\pi(a|s)R_{s}^a\doteq r_{\pi}(s),\sum_{a \in A}\pi(a|s)P_{ss'}^a\doteq P_{\pi}(s,s')$

令 $\small s_{i}=s,s_{j}=s'$ ，则：

$\small \nu_{\pi}(s_{i})=r_{\pi}(s_{i})+\gamma\sum_{j=1}^{|s|}P_{\pi}(s_{i},s_{j})\nu_{\pi}(s_{j})$

写成矩阵形式为：

$\small \nu_{\pi}=r_{\pi}+\gamma P_{\pi}\nu_{\pi}$

$\small \nu_{\pi}=(I-\gamma P_{\pi})^{-1}r_{\pi}$

? ? ? ? （2）迭代解

$\small \small \nu_{k+1}(s)=\sum_{a \in A}\pi(a|s)(R_{s}^a+\gamma\sum_{s'\in S}P_{ss'}^a\nu_{k}(s'))$

根据上式进行迭代，最终会收敛于 $\small \nu_{\pi}$ .

3.1.2 策略改进

? ? ? ? 利用策略评估得到的值函数，如何找到最优策略？一个自然的方法就是当已知当前策略的值函数时，在每个状态采用贪婪策略对当前策略进行改进：

$\small \pi_{l+1}(s) =\arg\max_{a}q^{\pi_{l}}(s,a)$

3.2 值函数迭代算法

? ? ? ? 策略迭代算法中，每一次策略改进都必须要等待策略评估中值函数收敛完毕才可以进行，事实上并不需要这么做。如果我们在评估一次之后就进行策略改善，则称为值函数迭代算法。

?4 基于蒙特卡洛的强化学习方法

? ? ? ? 在动态规划的方法中，值函数的计算方法如下：

$\small \nu_{\pi}(s)=\sum_{a \in A}\pi(a|s)(R_{s}^a+\gamma\sum_{s'\in S}P_{ss'}^a\nu_{\pi}(s'))$

? ? ? ? 而在无模型的马尔科夫决策问题中，状态转移函数是未知的，因此要想利用策略评估和策略改进的方法，必须采用其他方法评估当前策略（计算值函数）。

? ? ? ?由于状态-值函数和状态-行为值函数都是数学期望，动态规划的方法是利用模型来计算该期望，在无模型场合下，我们可以采用蒙特卡洛的方法计算该期望，即利用随机样本估计期望。

? ? ? ? 当要评估智能体的当前策略 $\small \pi$ 时，可以利用策略 $\small \pi$ 产生很多次试验，每次试验都是从任意的初始状态开始直到终止，得到一组试验数据，然后求平均值得到状态s处的值函数。

? ? ? ? 利用蒙特卡洛方法求状态s处的值函数时，可以分为第一次访问蒙特卡洛方法和每次访问蒙特卡洛方法。前者是指只利用每次试验中第一次访问到状态s时的返回值，后者是指利用所有访问到状态s时的回报返回值。

? ? ? ? （1）蒙特卡洛策略改善

? ? ? ? 蒙特卡洛方法利用经验平均估计策略值函数。估计出值函数以后，对于每个状态s，它通过最大化动作值函数来进行策略的改善。即：

$\small \pi(s)=\arg\max_{a}q(s,a)$

? ? ? ? （2）递增计算均值的方法

???????? $\small \nu_{k}(s)=\frac{1}{k}\sum_{j=1}^{k}G_{j}(s) =\frac{1}{k}(G_{k}(s)+\sum_{j=1}^{k-1}G_{j}(s)) =\frac{1}{k}(G_{k}(s)+(k-1)\nu_{k-1}(s)) =\nu_{k-1}(s)+\frac{1}{k}(G_{k}(s)+\nu_{k-1}(s))$

? ? ? ?

????????为了保证值函数的收敛性，充分评估策略值函数，蒙特卡罗方法需要保证每个状态都能被访问到。

????????方法之一就是探索性初始化，即指每个状态都有一定的概率作为初始状态，这样可以保证迭代过程中每个状态行为都能被选中。

? ? ? ? 也可以通过精心选择探索策略，来保证在初始状态不变的同时，又能保证每个状态行为都可以被访问，比如采用温和策略，即对所有的状态s和a都满足： $\small \pi(a|s)>0$

5 基于时间差分的强化学习方法

? ? ? ? 蒙特卡洛方法需要等到每次试验结束，所以学习速度慢，效率低。时间差分方法结合了蒙特卡洛的采样方法（即试验）和动态规划的bootstrapping（利用后继状态的值函数估计当前之前）。

? ? ? ? 用时间差分方法（Temporal-Difference, TD）将值函数的公式更新为：

???????? $\small V(S_{t})\leftarrow V(S_{t})+\alpha(R_{t+1}+\gamma V(S_{t+1})-V(S_{t}))$

? ? ? ? 与蒙特卡洛方法相比，时间差分方法只用到了一步随机状态和动作，随机性小，方差小。

? ? ? ? 时间差分方法包括同策略on-policy的Sarsa方法和异策略off-policy的Qlearning方法。

（1）Q-learning

$\small Initialize \,\,\,Q(s,a) \,\,\,arbitrarily$

$\small Repeat(for \, each \,episode):$

? ? ? ? $\small Initialize \ s$

? ? ? ? $\small Repeat(for \: each \: step \: of \: episode):$

? ? ? ? ? ? ? ? $\small choose\, a\, from\, s\, using\, policy \,derived \,from\, Q(e.g.$ ? $\small \epsilon-greedy$ )

? ? ? ? ? ? ? ? $\small Take \,action \,a, observe \,r, s'$

? ? ? ? ? ? ? ?? $\small Q(s,a)\leftarrow Q(s,a)+\alpha[r + \gamma \max_{a'}Q(s',a')-Q(s,a)]$

???????????????? $\small s\leftarrow s'$

? ? ? ? ? ? ? ?? $\small until\,s\,is\,terminal$

（2）Sarsa

$\small Initialize \,\,\,Q(s,a) \,\,\,arbitrarily$

$\small Repeat(for \, each \,episode):$

? ? ? ? $\small Initialize \ s$

????????? $\small choose\, a\, from\, s\, using\, policy \,derived \,from\, Q(e.g.$ ? $\small \epsilon-greedy$ )

? ? ? ? $\small Repeat(for \: each \: step \: of \: episode):$

? ? ? ? ? ? ? ? $\small Take \,action \,a, observe \,r, s'$

???????????????? $\small \small choose\, a'\, from\, s'\, using\, policy \,derived \,from\, Q(e.g.$ ? $\small \epsilon-greedy$ )

? ? ? ? ? ? ? ?? $\small \small Q(s,a)\leftarrow Q(s,a)+\alpha[r + \gamma Q(s',a')-Q(s,a)]$

???????????????? $\small \small s\leftarrow s';a \leftarrow a'$

? ? ? ? ? ? ? ?? $\small until\,s\,is\,terminal$

6 基于值函数逼近的强化学习算法

6.1 基于值函数逼近的理论讲解

? ? ? ? 基于动态规划的方法、基于蒙特卡洛的方法以及基于时间差分的方法，都假设状态空间和动作空间是离散的，而且状态空间和动作空间不能太大。这些强化学习方法的基本步骤是先评估值函数，然后利用值函数改善当前的策略。其中值函数的评估是关键。

? ? ? ? 这时的值函数其实是一个表格。对于状态值函数，其索引是状态；对于行为值函数，其索引是状态-行为对。值函数的迭代更新实际上就是这张表的迭代更新。因此，上述强化学习算法又称为表格型强化学习。

? ? ? ? 若状态空间的维数很大，或者状态空间为连续空间，则此时的值函数无法用一张表格来表示。这时，需要利用值函数逼近的方法表示值函数，之后利用策略迭代和值迭代的方法构建强化学习方法。从数学的角度，函数逼近方法可以分为参数逼近和非参数逼近，因此强化学习值函数估计可以分为参数化逼近和非参数化逼近。其中，参数化逼近又分为线性参数化逼近和非线性参数化逼近。

? ? ? ? 当逼近的值函数结构确定时（如线性逼近时选定了基函数，非线性逼近时选定了神经网络的结构），那么值函数的逼近就等价于参数的逼近，值函数的更新就等价于参数的更新。

? ? ? ? 函数逼近 $\small \hat{v}(s,\theta)$ 的过程是一个监督学习的过程，其数据和标签对为 $\small (S_{t},U_{t})$ ,其中 $\small U_{t}$ 等价于蒙特卡洛方法中的 $\small G_{t}$ ，时间差分方法中 $\small r+\gamma Q(s',a')$ 的，训练的目标函数为：