1 绪论
1.1强化学习可以解决什么问题
用一句话来概括强化学习能解决的问题就是：智能决策问题。更确切地说是序贯决策问题。
序贯决策问题：需要连续不断地做出决策，才能实现最终目标的问题
1.2 强化学习如何解决问题
监督学习解决的问题：智能感知的问题。监督学习需要感知到当前的输入是怎样，并给出对应的输出（标签）。智能感知必不可少的前提是大量长相差异化的输入以及与输入相关的标签。
监督学习解决问题的方法：输入大量带有标签的数据，让智能体从中学到输入的抽象特征并预测。
强化学习解决的问题：序贯决策问题。不关心输入长什么样，只关心当前输入下应该采用什么动作才能实现最终的目标。简单地说就是，当前采用什么动作可以使得整个任务序列达到最优。
强化学习解决问题的方法：智能体不断地与环境进行交互，不断尝试，通过动作与环境进行交互时，环境会返回给智能体一个当前的回报，智能体则根据当前的回报评估所采取的动作：有利于实现目标的动作被保留，不利于实现目标的动作被衰减。
总的来说，强化学习和监督学习都需要大量的数据进行训练，前者需要带有回报的交互数据，后者需要的则是标签数据。
1.3 强化学习的算法分类
根据强化学习算法是否依赖模型分：基于模型的强化学习算法和无模型的强化学习算法。有模型算法先利用与环境交互得到的数据学习系统或者环境模型，再基于模型进行序贯决策。无模型算法直接利用与环境交互得到的数据改善自身的行为。根据策略的更新和学习方法分：基于值函数的强化学习算法、基于直接策略搜索的强化学习计算法和AC的方法。根据环境返回的回报函数是否已知分：正向强化学习和逆向强化学习。从广义上将，强化学习是序贯决策问题。序贯决策问题既包含马尔科夫过程的决策，也包含非马尔科夫决策过程的决策。可以将强化学习纳入到马尔科夫决策过程MDP的框架之内。再根据转移概率P是否已知，可以分为基于模型的动态规划方法和基于无模型的强化学习方法。这两个类别都包括策略迭代算法、值迭代算法和策略搜索算法。另外，在无模型的强化学习方法中，每类算法又分为online和offline两种。
1.4 强化学习的发展历史及趋势
第一个关键点：1998年，Richard S. Sutton出版了Reinforcement Learning：An introduction
总结了1998年以前的各种强化学习算法的发展。
第二个关键点：DeepMind提出DQN(Deep Q Network)，将深度网络与强化学习算法结合形成深度强化学习（Deep ReinforcementLearning，DRL）。
发展趋势：与深度学习结合、理论分析更强、算法更稳定高效、与脑科学联系紧密
2 马尔科夫决策过程
2.1 马尔科夫决策过程理论讲解
第一个概念：马尔科夫性
系统的下一个状态仅与当前的状态有关，而与以前的状态无关。即：若状态是马尔科夫的，则：
第二个概念：马尔科夫过程
马尔科夫过程：一个二元组（S,P），且满足：S是有限状态集合，P是状态转移概率矩阵
第三个概念：马尔科夫决策过程
马尔科夫决策过程：一个五元组，其中S是有限状态集合，A是有限动作集合，P是状态转移概率矩阵，R是回报函数，是折扣因子，用来计算累计回报。
马尔科夫决策过程的状态转移概率（动态特性）：
有些情况下，也可以写成：
这是因为考虑到了即时回报函数也有可能是一个随机变量。
强化学习的目标是给定一个马尔科夫决策过程，寻找最优策略。
所谓策略是指状态到动作的映射，策略常用符号表示，它是指给定状态s时，动作集上的一个分布：
其含义是策略在每个状态s指定一个动作概率。
要注意，策略也可以是确定性的，即在某一种状态下采取的动作时确定的。
所谓最优策略是指得到的累计回报最大，累计回报的定义如下：
为了使用一个确定量来描述状态的价值，可以考虑使用累计回报来衡量，但其是一个随机变量，因此考虑其期望值，并作为状态值函数的定义。
（1）状态-值函数和状态-行为值函数
当智能体采用策略π时，累计回报服从一个分布，累计回报在状态s处的期望值定义为状态-值函数：
相应地，状态-行为值函数为：
（2）状态-值函数和状态-行为值函数的贝尔曼方程
对状态-值函数进行分解，得到：
即根据策略在状态s的条件下采取动作a得到的累计回报q(a,s）是当前的累计回报加上未来各种可能的状态得到的回报的加权平均。整合两个公式可以得到：
（3）最优状态值函数和最优状态状态-行为值函数的贝尔曼最优方程：
2.2 强化学习算法的形式化描述
定义一个离散时间有限范围的折扣马尔科夫决策过程,其中S为状态集，A为动作集，是转移概率，为立即回报函数，是初始状态分布，为折扣因子，T为水平范围（其实就是步数）。为一个轨迹序列，即，累计回报为,强化学习的目标是找到最优策略,使得该策略下的累计回报期望最大，即
3 基于模型的动态规划方法
基于模型的强化学习可以利用动态规划的思想来解决。利用动态规划可以解决的问题需要满足两个条件：一是整个优化问题可以分解为多个子优化问题；二是子优化问题的解可以被存储和重复利用。
由于强化学习可以归于马尔科夫决策问题的框架之下，通过上一节得到的状态-值函数贝尔曼最优方程可以看出，马尔科夫决策问题符合使用动态规划的两个条件，因此可以使用动态规划来解决基于模型的强化学习问题。
3.1 策略迭代算法
策略迭代算法包括策略评估和策略改进两个步骤。在策略评估中，给定策略，通过数值迭代算法不断计算该策略下每个状态的值函数，利用该值函数和贪婪策略得到新的策略。如此循环下去，最终得到最优策略。
3.1.1 策略评估
对于模型已知强化学习算法，我们有状态-值函数：
其中，根据模型已知，状态转移概率、即时回报、折扣因子已知，要评估的策略是指定的，故只有值函数是未知的。问题转化为关于值函数的线性方程组，其未知数的个数为状态的总数。
（1）解析解
令，则：
写成矩阵形式为：
（2）迭代解
根据上式进行迭代，最终会收敛于.
3.1.2 策略改进
利用策略评估得到的值函数，如何找到最优策略？一个自然的方法就是当已知当前策略的值函数时，在每个状态采用贪婪策略对当前策略进行改进：
3.2 值函数迭代算法
策略迭代算法中，每一次策略改进都必须要等待策略评估中值函数收敛完毕才可以进行，事实上并不需要这么做。如果我们在评估一次之后就进行策略改善，则称为值函数迭代算法。
4 基于蒙特卡洛的强化学习方法
在动态规划的方法中，值函数的计算方法如下：
而在无模型的马尔科夫决策问题中，状态转移函数是未知的，因此要想利用策略评估和策略改进的方法，必须采用其他方法评估当前策略（计算值函数）。
由于状态-值函数和状态-行为值函数都是数学期望，动态规划的方法是利用模型来计算该期望，在无模型场合下，我们可以采用蒙特卡洛的方法计算该期望，即利用随机样本估计期望。
当要评估智能体的当前策略时，可以利用策略产生很多次试验，每次试验都是从任意的初始状态开始直到终止，得到一组试验数据，然后求平均值得到状态s处的值函数。
利用蒙特卡洛方法求状态s处的值函数时，可以分为第一次访问蒙特卡洛方法和每次访问蒙特卡洛方法。前者是指只利用每次试验中第一次访问到状态s时的返回值，后者是指利用所有访问到状态s时的回报返回值。
（1）蒙特卡洛策略改善
蒙特卡洛方法利用经验平均估计策略值函数。估计出值函数以后，对于每个状态s，它通过最大化动作值函数来进行策略的改善。即：
（2）递增计算均值的方法
为了保证值函数的收敛性，充分评估策略值函数，蒙特卡罗方法需要保证每个状态都能被访问到。
方法之一就是探索性初始化，即指每个状态都有一定的概率作为初始状态，这样可以保证迭代过程中每个状态行为都能被选中。
也可以通过精心选择探索策略，来保证在初始状态不变的同时，又能保证每个状态行为都可以被访问，比如采用温和策略，即对所有的状态s和a都满足：
5 基于时间差分的强化学习方法
蒙特卡洛方法需要等到每次试验结束，所以学习速度慢，效率低。时间差分方法结合了蒙特卡洛的采样方法（即试验）和动态规划的bootstrapping（利用后继状态的值函数估计当前之前）。
用时间差分方法（Temporal-Difference, TD）将值函数的公式更新为：
与蒙特卡洛方法相比，时间差分方法只用到了一步随机状态和动作，随机性小，方差小。
时间差分方法包括同策略on-policy的Sarsa方法和异策略off-policy的Qlearning方法。
（1）Q-learning
)
（2）Sarsa
)
)
6 基于值函数逼近的强化学习算法
6.1 基于值函数逼近的理论讲解
基于动态规划的方法、基于蒙特卡洛的方法以及基于时间差分的方法，都假设状态空间和动作空间是离散的，而且状态空间和动作空间不能太大。这些强化学习方法的基本步骤是先评估值函数，然后利用值函数改善当前的策略。其中值函数的评估是关键。
这时的值函数其实是一个表格。对于状态值函数，其索引是状态；对于行为值函数，其索引是状态-行为对。值函数的迭代更新实际上就是这张表的迭代更新。因此，上述强化学习算法又称为表格型强化学习。
若状态空间的维数很大，或者状态空间为连续空间，则此时的值函数无法用一张表格来表示。这时，需要利用值函数逼近的方法表示值函数，之后利用策略迭代和值迭代的方法构建强化学习方法。从数学的角度，函数逼近方法可以分为参数逼近和非参数逼近，因此强化学习值函数估计可以分为参数化逼近和非参数化逼近。其中，参数化逼近又分为线性参数化逼近和非线性参数化逼近。
当逼近的值函数结构确定时（如线性逼近时选定了基函数，非线性逼近时选定了神经网络的结构），那么值函数的逼近就等价于参数的逼近，值函数的更新就等价于参数的更新。
函数逼近的过程是一个监督学习的过程，其数据和标签对为,其中等价于蒙特卡洛方法中的，时间差分方法中的，训练的目标函数为：
值函数更新可以分为增量式学习方法和批学习方法。
（1）增量式学习方法：随机梯度下降法
参数的随机梯度更新为：
基于蒙特卡罗方法的函数逼近的过程如下：
给定要评估的策略,产生一次试验：
值函数的更新过程实际上是一个监督学习的过程，其中监督数据集从蒙特卡罗的试验数据中得到：其数据集为：
值函数的更新如下：
基于梯度的蒙特卡洛值函数评估算法
输入：要评估的策略，一个可微逼近函数,恰当地初始化值函数权重
Repeat:
利用策略产生一幕数据
基于半梯度的TD(0)值函数评估算法
输入：要评估的策略，一个可微逼近函数,恰当地初始化值函数权重
Repeat：
初始化状态S
Repeat（对于一幕中的每一步）
选择动作a
采用动作a并观测回报R,S'
直到S'是中止状态
（2）批方法
所谓批的方法是指给定经验数据集,找到最好的拟合函数,使得最小。可以使用最小二乘法进行求解。
6.2 DQN及其变形
6.2.1 DQN方法
DQN算法的大体框架是传统强化学习中的Qlearning
Qlearning方法是异策略时间差分方法，其算法步骤如下：
)
对于Qlearning的理解：
异策略：指的是行动策略（产生数据的策略）和要评估的策略不是一个策略。在算法中，行动策略是策略，要评估和改进的策略时贪婪策略。
时间差分方法：是指利用时间差分目标来更新当前行为值函数。在算法中，时间差分目标为
DQN对Qlearning的改进体现在三个方面：
（1）DQN利用深度卷积神经网络逼近值函数
（2）DQN利用了经验回放训练强化学习的学习过程
（3）DQN独立设置了目标网络来单独处理时间差分算法中的TD偏差
（1）DQN利用深度卷积神经网络逼近值函数
DQN用神经网络逼近值函数属于参数化非线性逼近，值函数依然对应着一组参数，在神经网络里参数是每层网络的权重。更新值函数实际上是更新参数。DQN利用的网络结构是三个卷积层加两个全连接层.
（2）DQN利用了经验回放训练强化学习过程
经验回放是指在强化学习过程中，智能体将数据存储到一个数据库中，再利用均匀随机采样的方法从数据库中抽取数据，然后利用抽取的数据训练神经网络。这样可以打破数据之间的关联，从而使得训练得到的神经网络收敛且稳定。
（3）DQN独立设置了目标网络来单独处理时间差分算法中的TD偏差
在DQN算法之前，利用神经网络逼近值函数时，计算TD目标的动作值函数所用的网络参数，与梯度计算中要逼近的值函数所用的网络参数相同，这样就容易导致数据间存在关联性，从而使训练不稳定。为了解决这个问题，DQN将计算TD目标的网络表示为,计算值函数逼近的网络表示为，用于动作值函数逼近的网络每一步都更新，而用于计算TD目标的网络则是每个固定的步数更新一次。
因此，值函数的更新变为：
算法伪代码：
6.2.2 Double DQN
DQN的框架仍然是Qlearning，只是利用了卷积神经网络表示动作值函数，用经验回放和单独设立目标网络这两个技巧，但依然不能克服Qlearning本身的缺点：过估计。
Qlearning评估值函数的数学公式为：
对于表格型：
对于基于值函数逼近的方法：
可以看出值函数更新公式中都含有max操作，使得估计的值函数比值函数的真实值大。如果值函数每一点的值都被过估计了相同的幅度，即过估计量是均匀的，那么由于最优策略是贪婪策略，即找到大的值函数所对应的动作，这时候最优策略是保持不变的。也就是说，这种情况下即使值函数被过估计了，也不影响找到最优的策略。但实际情况中，过估计量并不一定是均匀的，因此过估计会影响到最优策略的选择。
为了解决值函数过估计的问题，Double Qlearning的方法被提出，即将动作的选择和动作的评估分别用不同的值函数来实现。
Double Qlearning的TD目标公式为：
将Double Qlearning的思想用到DQN中，则得到Double DQN，即Double DQN的TD目标为：
6.2.3 优先回放（Prioritized Replay）
DQN经验回放时利用均匀分布采样并不能有效利用数据，因为智能体在某些状态的学习效率比其他状态的学习效率高。优先回放的基本思想就是打破均匀采样，赋予学习效率高的状态更大的采样权重。
一种方法是，TD偏差越大，则说明该状态处的值函数与TD目标的差距越大，智能体的更新量越大，因此在此处的学习效率越高。设样本i处的TD偏差为,则该样本处的采样概率为：
其中，由偏差决定，一种方法是,一种方法是，其中由偏差的的大小顺序决定。
当我们采用优先回放时的和概率分布采样时，动作值函数的估计值是一个有偏估计。因为采样分布与动作值函数的分布是两个完全不同的分布，为了校正这个偏差，需要乘以一个重要性采样系数
6.2.4 Dueling DQN
前面几种DQN算法在值函数逼近时所用的神经网络都是卷积神经网络。Dueling DQN则是从网络结构上进行了改进。动作值函数可以分解为状态值函数和优势函数，即：
前面几种方法都是用神经网络直接逼近，而Dueling DQN则是用神经网络分别逼近和。
7.基于直接策略搜索的强化学习方法
7.1 基于策略梯度的强化学习方法
在值函数的方法中，我们迭代计算的是值函数，再根据值函数改善策略；而在策略搜索方法中，我们直接对策略进行迭代计算，也就是迭代更新策略的参数值，直到累计回报的期望最大，此时的参数所对应的策略为最优策略。
策略搜索是将策略参数化，即:利用参数化的线性函数或非线性函数（如神经网络）表示策略，寻找最优的参数,使强化学习的目标——累计回报的期望最大。
策略搜索方法按照是否利用模型可分为无模型的策略搜索方法和有模型的策略搜索方法。其中无模型的策略搜索方法根据策略是采用随机策略还是确定性策略分为随机策略搜素方法和确定性策略搜索方法。随机策略搜索方法中最先发展起来的是策略梯度方法。
下面我们从似然率的角度推导策略梯度
7.2 基于置信域策略优化的强化学习方法
根据策略梯度的方法，参数更新公式为:
策略梯度算法的难点在于更新步长的选择，当步长不合适的时候，更新的参数所对应的策略是一个更不好的策略，当利用这个更不好的策略采样学习时，再次更新参数往往会导致更差的结果。所以，合适的步长非常重要。
TRPO（Trust Region Policy Optimization）置信域策略优化可以找到新的策略使新的回报函数的值单调增长，或者单调不减。
如果觉得《《深入浅出强化学习：原理入门》学习笔记》对你有帮助，请点赞、收藏，并留下你的观点哦！
