深入浅出强化学习：原理入门（待更新）

之前看强化学习的一些教学视频，发现自己对一些强化学习中符号的定义理解不太透彻，例如 $Q_{target}$,$Q值$, $Q估计$，$Q现实$，$Q预测$， 现在发现郭宪老师的书，试读了一下里边的内容，发现老师讲解的很透彻，并且原理解释的很清楚，因此做此笔记。一是为了监督自己的学习进度，让自己能够在阅读的过程中，能够更深入的理解。二是做一份自己的笔记，方便后期查阅。
文章内容较长，建议开启右下角的侧边栏按钮，食用。

强化学习中常见符号说明：

$agent$：智能体

$environment$：环境

$s/state$：某个状态

$S$：所有状态的集合，状态空间

$a/action$：某个动作，行为

$A$：所有动作的集合，动作空间

$A(s)$：在状态$s$下的动作集合

$r/reward$：智能体执行某个动作后到达某个状态的回报

$R$：所有奖励集合

$t$：第$t$步，$S_t=s$：第$t$步的状态是状态$s$

$S_t$：第$t$步的状态

$A_t$：第$t$步的动作

$R_t$：第$t$步的奖励

$G_t$：第$t$步的长期回报，强化学习的目标1：求最大长期回报

$\alpha$：学习速率，learning rate

$\gamma$：未来回报的折扣率(discount rate) $\gamma \in [0,1]$

$\lambda$：$\lambda-return$中的比例参数 $\lambda \in [0,1]$

$\varepsilon$：在$\varepsilon-greedy$策略中，采用随机动作的概率，$\varepsilon \in [0,1]$

$\pi$：策略policy，策略规定了在状态$s$时，应该选择动作$a$，强化学习的目标2：找到最优策略

$\pi(s)$：策略$\pi$在状态$s$下，选择的行动

$\pi^*$：最优策略

$r(s,a)$：在状态$s$下，选择动作a的奖赏

$r(s,a,s')$：在状态$s$下，选择动作$a$，变成状态$s'$的奖赏

$p(s'|s,a)$：在状态$s$下，选择动作$a$，变成状态$s'$的概率，状态转移函数

$v_\pi(s)$：状态价值函数，使用策略$\pi$，状态$s$下的长期奖励$G_t$，与策略$\pi$是绑定的。

$q_\pi (s,a)$：状态动作价值函数，或叫动作值函数，使用策略$\pi$，状态$s$下，选择动作$a$的长期奖励$G_t$，

$v^*(s)$：最优状态价值函数

$q^*(s,a)$：最优状态动作价值函数，强化学习的目标3：找到最优状态价值函数，或者最优状态动作价值函数

$V(s)$：状态值函数$v_\pi(s)$的集合

$Q(s,a)$：状态动作价值函数$q_\pi (s,a)$的集合

$\hat{v}(s,\theta)$：状态近似值函数

$\hat{q}(s,a,\theta)$：状态动作近似值函数，强化学习的目标4：找到最优的状态近似值函数，或者最优的状态动作近似值函数

$\theta$：近似值函数的权重向量(梯度下降求解的参数)，强化学习的目标5：求解$\theta$，求解近似值函数

$\phi (s)$：状态近似值函数的特征函数，是一个将状态$s$转换成计算向量的方法，和$\theta$组成状态近似值函数$\hat{v}(s,\theta)=\theta ^T \phi (s)$

$\phi(s,a)$：状态动作近似值函数的特征函数，是一个将状态s，动作a转化成计算向量的方法，和$\theta$组成状态动作近似值函数$\hat{q}(s,a,\theta)=\theta ^T \phi (s,a)$

1. 绪论

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

一句话概述强化学习所能解决的问题：智能决策问题。更确切地说是序贯决策问题(什么是序贯决策问题呢？就是
需要连续不断地做出决策，才能实现最终目标的问题。)。

1.3 强化学习如何解决问题

在回答强化学习如何解决序贯决策问题之前，我们先看看监督学习是如何解决问题的。从解决问题的角度来看，监督学习解决的是智能感知的问题。
我们依然用一个图来表示。如图1.2所示，监督学习最典型的例子是数字手写体识别，当给出一个手写数字时，监督学习需要判别出该数字是多少。也就是说，监督学习需要感知到当前的输入到底长什么样，当智能体感知到输入长什么样时，智能体就可以对它进行分类了。如图1.2所示，输入手写体长得像4，所以智能体就可以判断它是4了。智能感知其实就是在学习“输入”长得像什么(特征)，以及与该长相一一对应的是什么(标签)。所以，智能感知必不可少的前提是需要大量长相差异化的输入以及与输入相关的标签。因此，监督学习解决问题的方法就是输入大量带有标签的数据，让智能体从中学到输入的抽象特征并分类。

强化学习则不同，强化学习要解决的是序贯决策问题，它不关心输入长什么样，只关心当前输入下应该采用什么动作才能实现最终的目标。再次强调，当前采用什么动作与最终的目标有关。也就是说当前采用什么动作，可以使得整个任务序列达到最优。如何使整个任务序列达到最优呢?这就需要智能体不断地与环境交互，不断尝试，因为智能体刚开始也不知道在当前状态下哪个动作有利于实现目标。强化学习解决问题的框架可用图1.3表示。智能体通过动作与环境进行交互时，环境会返给智能体一个当前的回报，智能体则根据当前的回报评估所采取的动作:有利于实现目标的动作被保留，不利于实现目标的动作被衰减。

强化学习和监督学习的共同点是两者都需要大量的数据进行训练，但是两者所需要的数据类型不同。监督学习需要的是多样化的标签数据，强化学习需要的是带有回报的交互数据。

1.4 强化学习算法分类以及发展趋势

(1)根据强化学习算法是否依赖模型可以分为基于模型的强化学习算法和无模型的强化学习算法。这两类算法的共同点是通过与环境交互获得数据，不同点是利用数据的方式不同。基于模型的强化学习算法利用与环境交互得到的数据学习系统或者环境模型，再基于模型进行序贯决策。无模型的强化学习算法则是直接利用与环境交互获得的数据改善自身的行为。两类方法各有优缺点，一般来讲基于模型的强化学习算法效率要比无模型的强化学习算法效率更高，因为智能体在探索环境时可以利用模型信息。但是，有些根本无法建立模型的任务只能利用无模型的强化学习算法。由于无模型的强化学习算法不需要建模，所以和基于模型的强化学习算法相比，更具有通用性。

(2)根据策略的更新和学习方法，强化学习算法可分为基于值函数的强化学习算法、基于直接策略搜索的强化学习算法以及AC的方法。所谓基于值函数的强化学习方法是指学习值函数，最终的策略根据值函数贪婪得到。也就是说，任意状态下，值函数最大的动作为当前最优策略。基于直接策略搜索的强化学习算法，一般是将策略参数化，学习实现目标的最优参数。基于AC的方法则是联合使用值函数和直接策略搜索。

(3)根据环境返回的回报函数是否已知，强化学习算法可以分为正向强化学习和逆向强化学习。在强化学习中，回报函数是人为指定的，回报函数指定的强化学习算法称为正向强化学习。很多时候，回报无法人为指定，如无人机的特效表演，这时可以通过机器学习的方法由函数自己学出来回报。

1.5 强化学习仿真环境构建

这里就跳过了，

1.5.2 深入剖析gym环境构建

• reset()函数详解，reset()为重新初始化函数，它有什么作用呢？
  在强化学习算法中，智能体需要一次次地尝试并累积经验，然后从经验中学到好的动作。每一次尝试我们称之为一条轨迹或一个episode，每次尝试都要到达终止状态。一次尝试结束后，智能体需要从头开始，这就需要智能体具有重新初始化的功能。函数reset()就是用来做这个的。

• render()函数详解，render()函数用来渲染环境

  render()函数在这里扮演图像引擎的角色。我们知道一个仿真环境必不可少的两部分是物理引擎和图像引擎。物理引擎模拟环境中物体的运动规律;图像引擎用来显示环境中的物体图像，其实对于强化学习算法而言，可以没有render()函数，但是，为了便于直观显示当前环境中物体的状态，图像引擎还是有必要的。另外，加入图像引擎可以方便我们调试代码。

• step()函数详解

  本函数在仿真器中扮演物理引擎的角色。其输入是动作a，输出是:下一步状态、立即回报、是否终止、调试项。它描述了智能体与环境交互的所有信息，是环境文件中最重要的函数。在本函数中，一般利用智能体的运动学模型和动力学模型计算下一步的状态和立即回报，并判断是否达到终止状态。

1.6 本书主要内容及安排

强化学习算法解决的是序贯决策问题，而一般的序贯决策问题可以利用马尔科夫决策过程的框架来表述，因此在第2章中我们介绍了马尔科夫决策过程，即MDP。马尔科夫决策过程能够用数学的形式将要解决的问题描述清楚，这也是为什么在介绍强化学习时首先要讲MDP的原因。

利用MDP将问题形式化后，就需要找到解决MDP问题的方法。对于模型已知的MDP问题，动态规划是一个不错的解。因此在第3章我们会介绍基于动态规划的强化学习算法，并由此引出广义策略迭代的方法。广义策略迭代方法不仅适用于基于模型的方法，也适用于无模型的方法，是基于值函数强化学习算法的基本框架。因此，第3章是第4章基于蒙特卡罗方法、第5章基于时间差分方法和第6章基于值函数逼近方法的基础。

强化学习算法的核心是计算值函数的期望。值函数是个随机变量，其期望的计算可通过蒙特卡罗的方法得到。因此，第4章我们介绍了基于蒙特卡罗的强化学习算法。

基于蒙特卡罗的强化学习算法通过蒙特卡罗模拟计算期望，该方法需要等到每次试验结束后再对值函数进行估计，收敛速度慢。时间差分的方法则只需要一步便更新，效率高、收敛速度快。因此第5章我们对时间差分方法进行了详细介绍。

第4章到第5章介绍的是表格型强化学习。所谓表格型强化学习是指状态空间和动作空间都是有限集，动作值函数可用一个表格来描述，表格的索引分别为状态量和动作量。但是，当状态空间和动作空间很大，甚至两个空间都是连续空间时，动作值函数已经无法使用一个表格来描述，这时可以用函数逼近理论对值函数进行逼近。本书第6章详细介绍了基于值函数逼近的强化学习算法。

强化学习算法的第二大类是直接策略搜索方法。所谓直接策略搜索方法是指将策略进行参数化，然后在参数空间直接搜索最优策略。直接策略搜索方法中，最简单最直接的方法是策略梯度的方法。在第7章，我们详细介绍了策略梯度理论。

基于策略梯度方法最具挑战性的是更新步长的确定，若是更新步长太大，算法容易发散;更新步长太小，收敛速度又很慢。TRPO 的方法通过理论分析得到单调非递减的策略更新方法。第8章我们对TRPO进行了详细推导和介绍。当动作空间维数很高时，智能体的探索效率会很低，利用确定性策略可免除对动作空间的探索，提升算法的收敛速度，第9章对确定性策略搜索进行了详细介绍。

第7章到第9章，我们介绍的是无模型的直接策略搜索方法。对于机器人等复杂系统，无模型的方法随机初始化很难找到成功的解，因此算法难以收敛。这时，可以利用传统控制器来引导策略进行搜索。因此第10章介绍了基于引导策略搜索的强化学习算法。在很多实际问题中，往往不知道回报函数。为了学习回报函数，第11章介绍了逆向强化学习的算法。

从第12章开始，我们介绍了最近发展出来的强化学习算法，分别是第12章的组合策略梯度和值函数方法，第13章的值迭代网络和第14章的PILCO方法及其扩展。

第一篇：强化学习基础

2. 马尔可夫决策过程

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

强化学习的基本原理：智能体在完成某项任务时，首先通过动作A与周围环境进行交互，在动作A和环境的作用下，智能体会产生新的状态，同时环境会给出一个立即回报。如此循环下去，智能体与环境不断地交互从而产生很多数据。强化学习算法利用产生的数据修改自身的动作策略，再与环境交互，产生新的数据，并利用新的数据进一步改善自身的行为，经过数次迭代学习后，智能体能最终学到完成相应任务的最优动作(最优策略)。

2.1.1 强化学习与监督学习和非监督学习的区别：

在监督学习和非监督学习中，数据是静态的、不需要与环境进行交互，比如图像识别，只要给出足够的差异样本，将数据输入深度网络中进行训练即可。然而，强化学习的学习过程是动态的、不断交互的过程，所需要的数据也是通过与环境不断交互所产生的。所以，与监督学习和非监督学习相比，强化学习涉及的对象更多，比如动作，环境，状态转移概率和回报函数等。强化学习更像是人的学习过程:人类通过与周围环境交互，学会了走路，奔跑，劳动;人类与大自然，与宇宙的交互创造了现代文明。另外，深度学习如图像识别和语音识别解决的是感知的问题，强化学习解决的是决策的问题。人工智能的终极目的是通过感知进行智能决策。

2.1.2 第一个概念是马尔科夫性

马尔科夫性是指系统的下一个状态 $s_{t+1}$ 仅与当前状态 $s_t$ 有关，而与以前的状态无关。

定义:状态 $s_t$ 是马尔科夫的，当且仅当 $P[s_{t+1} |s_t ]=P[s_{t+1} |s_1,..., s_t]$ 。

定义中可以看到，当前状态 $s_t$ 其实是蕴含了所有相关的历史信息 $s_1.,. ... s_t$ ，一旦当前状态已知，历史信息将会被抛弃。马尔科夫性描述的是每个状态的性质，但真正有用的是如何描述一个状态序列。数学中用来描述随机变量序列的学科叫随机过程。所谓随机过程就是指随机变量序列。若随机变量序列中的每个状态都是马尔科夫的，则称此随机过程为马尔科夫随机过程。

2.1.3 第二个概念是马尔科夫过程

马尔科夫过程的定义:马尔科夫过程是一个二元组(S,P)，且满足:S是有限状态集合，P是状态转移概率。状态转移概率矩阵为:

$$P= \begin{bmatrix} P_{11}&\cdots&P_{1n}\\ \vdots&\ddots&\vdots\\ P_{n1}&\cdots&P_{nn} \end{bmatrix}$$

下面我们以一个例子来进行阐述。如图2.2所示为一个学生的7种状态{娱乐，课程1，课程2，课程3，考过，睡觉，论文}，每种状态之间的转换概率如图所示。则该生从课程1开始一天可能的状态序列为:

• 课1-课2-课3-考过-睡觉

• 课1-课2-睡觉

以上状态序列称为马尔科夫链。当给定状态转移概率时，从某个状态出发存在多条马尔科夫链。对于游戏或者机器人，马尔科夫过程不足以描述其特点，因为不管是游戏还是机器人，他们都是通过动作与环境进行交互，并从环境中获得奖励，而马尔科夫过程中不存在动作和奖励。将动作(策略)和回报考虑在内的马尔科夫过程称为马尔科夫决策过程。

2.1.4 第三个概念是马尔科夫决策过程

马尔科夫决策过程由元组 $(S,A,P,R, \gamma)$ 描述，其中:

$S$ 为有限的状态集

$A$ 为有限的动作集

$P$ 为状态转移概率

$R$ 为回报函数

$\gamma$ 为折扣因子，用来计算累计回报。跟马尔科夫过程不同的是，马尔科夫决策过程的状态转移概率是包含动作的,即 $P_{ss'}^a=P\,[S_{t+1}=s'|S_t=s,A_t=a\,]$

举个例子如图2.3所示。

图2.3为马尔科夫决策过程的示例图，图2.3与图2.2对应。在图2.3中，学生有五个状态，状态集为 $S=\{s1,s2,s3,s4,s5\}$ ，动作集为 $A=\{玩，退出，学习，发表，睡觉\}$，在图2.3中立即回报用 $R$ 标记。强化学习的目标是给定一个马尔科夫决策过程，寻找最优策略。所谓策略是指状态到动作的映射，策略常用符号 $\pi$ 表示，它是指给定状态s时，动作集上的一个分布，即

$$\pi(a|s)=p[A_t=a|S_t=s] \tag{2.1}$$

这个公式是什么意思呢?策略的定义是用条件概率分布给出的。公式(2.1)的含义是：策略 $\pi$ 在每个状态 $s$ 指定一个动作概率。如果给出的策略 $\pi$ 是确定性的，那么策略 $\pi$ 在每个状态 $s$ 指定一个确定的动作。

例如其中一个学生的策略为 $\pi_1(玩|s_1 )=0.8$，是指该学生在状态 $s_1$ 时玩的概率为 0.8，不玩的概率是 0.2，显然这个学生更喜欢玩。另外一个学生的策略为 $\pi_2(玩|s_1 )=0.3$，是指该学生在状态 $s_1$ 时玩的概率是 0.3，显然这个学生不爱玩。依此类推，每个学生都有自己的策略。强化学习是找到最优的策略，这里的最优是指得到的总回报最大。

当给定一个策略 $\pi$ 时，我们就可以计算累计回报了。首先定义累计回报:

$$G_t=R_{t+1}+\gamma R_{t+2}+\cdots=\sum_{k=0}^{\infty}\gamma^kR_{t+k+1} \tag{2.2}$$

当给定策略 $π$ 时，假设从状态 $s_1$ 出发，学生状态序列可能为

$s_1\rightarrow s_2\rightarrow s_3 \rightarrow s_4 \rightarrow s_5$

$s_1\rightarrow s_2\rightarrow s_3\rightarrow s_5$

$\vdots$

此时，在策略 $\pi$ 下，利用(2.2)式可以计算累计回报 $G_1$ ，此时 $G_1$ 有多个可能值。由于策略 $\pi$ 是随机的，因此累计回报也是随机的。为了评价状态 $s_1$ 的价值，我们需要定义一个确定量来描述状态 $s_1$ 的价值，很自然的想法是利用累计回报来衡量状态 $s_1$ 的价值。然而，累计回报 $G_1$ 是个随机变量，不是一个确定值，因此无法描述，但其期望是个确定值，可以作为状态值函数的定义。(数学期望(mean)是试验中每次可能结果的概率乘以其结果的总和)

(1)状态-值函数与状态-行为值函数。

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

$$v_\pi(s)=E_\pi[\,\sum_{k=0}^{\infty}\gamma^k R_{t+k+1}|S_t=s\,] \tag{2.3}$$

注意：状态-值函数是与策略 $\pi$ 相对应的，这是因为策略 $\pi$ 决定了累计回报 $G$ 的状态分布。

图2.4是与图2.3相对应的状态-值函数图。图中空心圆圈中的数值为该状态下的值函数。即：$υ_\pi(s_1)=-2.3$，$υ_\pi(s_2)=-1.3$，$υ_\pi(s_3)=2.7$，$υ_\pi(s_4)=7.4$，$υ_\pi(s_5)=0$

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

$$q_\pi(s,a)=E_\pi[\sum_{k=0}^{\infty}\gamma^k R_{t+k+1}|S_t=s,A_t=a] \tag{2.4}$$

(2.3)式和(2.4)式分别给出了状态-值函数和状态-行为值函数的定义计算式，但在实际真正计算和编程的时候并不会按照定义式编程。接下来我们会从不同的方面对定义式进行解读。

(2)状态-值函数与状态-行为值函数的贝尔曼方程。

由状态-值函数的定义式(2.3)以及定义式(2.2)可以得到状态-值函数的贝尔曼方程：

$$\begin{array}{l} v(s)=E[G_t|S_t=s]\\ =E[R_{t+1}+\gamma R_{t+2}+\cdots|S_t=s]\\ =E[R_{t+1}+\gamma (R_{t+2}+\gamma R_{t+3}+\cdots)|S_t=s]\\ =E[R_{t+1}+\gamma G_{t+1}|S_t=s]\\ =E[R_{t+1}+\gamma v(S_{t+1})|S_t=s]\\ \end{array} \tag{2.5}$$

这里需要注意的是对哪些变量求期望。同样我们可以得到状态-动作值函数的贝尔曼方程：

$$q_\pi(s,a)=E_\pi[R_{t+1}+\gamma q(S_{t+1},A_{t+1})|S_t=s,A_t=a] \tag{2.6}$$

状态值函数与状态-行为值函数的具体推导过程如下。图2.5和图2.6分别为状态值函数和行为值函数的具体计算过程。其中空心圆圈表示状态，实心圆圈表示状态-行为对。

图2.5为值函数的计算分解示意图，图2.5(B)计算公式为

$$v_\pi(s)=\sum_{a\in A}\pi(a|s)q_\pi(s,a) \tag{2.7}$$

状态-值函数，是采取每个行为的概率乘以该行为对应的状态-行为价值的累加。

图2.5(B)给出了状态值函数与状态-行为值函数的关系。图2.5(C)计算状态-行为值函数为

$$q_\pi(s,a)=R_s^a+\gamma \sum_{s'}P_{ss'}^a v_\pi(s') \tag{2.8}$$

状态-行为值函数，是当前状态 $s$ 采取行为 $a$ 所获得的即时回报，加状态 $s$ 采取行为 $a$ 到达下一个状态 $s'$ 的概率乘以下一个状态 $s'$ 的状态价值的累加。

将2.8式代入到2.7式得到：

$$v_\pi(s)=\sum_{a\in A}\pi(a|s) \left( R_s^a+\gamma \sum_{s'\in S}P_{ss'}^a v_\pi(s') \right) \tag{2.9}$$

在图2.6(C)中，

$$v_\pi(s')=\sum_{a'\in A}\pi(a'|s')q_\pi(s',a') \tag{2.10}$$

下一个状态 $s'$ 的状态-值函数 $v_\pi(s')$ 就等于在状态 $s'$ 下采取每个行为 $a'$ 的概率乘以该行为 $a'$ 对应的状态-行为价值的累加。将(2.10)代入(2.8)中，得到状态-行为值函数：

$$q_\pi(s,a)=R_s^a+\gamma \sum_{s'}P_{ss'}^a \sum_{a'\in A}\pi(a'|s')q_\pi(s',a') \tag{2.11}$$

公式(2.9)可以在图2.4中进行验证。选择状态 $s_4$处。由图2.4知道 $υ(s_4)=7.4$，由公式(2.9)得

$$v(s_4)=0.5*(1+0.2*(-1.3)+0.4*2.7+0.4*7.4)+0.5*10=7.39$$

保留一位小数为7.4。

计算状态-值函数的目的是为了构建学习算法从数据中得到最优策略。每个策略对应着一个状态值函数，最优策略自然对应着最优状态-值函数。

定义：

• 最优状态-值函数 $υ^*(s)$ 为在所有策略中值最大的值函数，即 $v^*(s)=\underset{\pi}{max}v_\pi(s) $，
• 最优状态-行为值函数$q^*(s，a)$ 为在所有策略中最大的状态-行为值函数，即 $q^*(s，a)=\underset{\pi}{max}q_\pi(s,a) $

我们由(2.9)式和(2.11)式分别得到最优状态值函数和最优状态-行动值函数的贝尔曼最优方程：

$$v^*(s)=\underset{a}{max} R_s^a+\gamma \sum_{s' \in S} P_{ss'}^a v^*(s') \tag{2.12}$$

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

若已知最优状态-动作值函数，最优策略可通过直接最大化 $q^*(s，a)$ 来决定。

$$\pi ^*(a|s)=\begin{cases} 1, & \text {if $a$ =$\underset{a \in A}{argmax}q^*(s,a)$} \\ 0, & \text{otherwise} \end{cases}$$

如图2.7所示为最优状态值函数示意图，图中虚线箭头所示的动作为最优策略。

图2.7 最优值函数和最优策略至此，我们将强化学习的基本理论即马尔科夫决策过程介绍完毕。现在该对强化学习算法进行形式化描述了。

我们定义一个离散时间有限范围的折扣马尔科夫决策过程 $M=(S，A，P，r，ρ_0，γ，T)$，其中 $S$ 为状态集，$A$ 为动作集，$P：S×A×S→R$ 是转移概率，$r：S×A→[-R_{max}，R_{max}]$ 为立即回报函数，$ρ_0：S→R$ 是初始状态分布，$\gamma∈[0，1]$ 为折扣因子，$T$ 为水平范围(其实就是步数)。$τ$ 为一个轨迹序列，即 $τ=(s_0,a_0,s_1,a_1,...)$，累计回报为 $R=\sum_{t=0}^{T} \gamma^tr_t$ ，强化学习的目标是找到最优策略 $π$ ，使得该策略下的累计回报期望最大，即 $\underset{\pi}{max}\int R(\tau)p_\pi(\tau)d\tau$ 。

2.2 MDP中的概率学基础讲解

本节解释公式(2.1)随机策略的定义。在强化学习算法中，随机策略得到广泛应用，因为随机策略耦合了探索。后面要介绍的很多强化学习算法的策略都采用随机策略，所以，很有必要理解什么是随机策略。随机策略常用符号 $\pi$ 表示，它是指给定状态 $s$ 时动作集上的一个分布。要理解分布首先要理解随机变量。

(1)随机变量。随机变量是指可以随机地取不同值的变量，常用小写字母表示。在MDP中随机变量指的是当前的动作，用字母 $a$ 表示。在图2.3的例子中，随机变量可取的值为“玩”、“退出”、“学习”、“发表”和“睡觉”。随机变量可以是离散的也可以是非离散的，在该例子中随机变量是离散的。有了随机变量，我们就可以描述概率分布了。

(2)概率分布。概率分布用来描述随机变量在每个可能取到的值处的可能性大小。离散型随机变量的概率分布常用概率质量函数来描述，即随机变量在离散点处的概率。连续型随机变量的概率分布则用概率密度函数来描述。在图 2.3的例子中，指定一个策略 $\pi$ 就是指定取每个动作的概率。

(3)条件概率。策略 $π(a|s)$ 是条件概率。条件概率是指在其他事件发生时，我们所关心的事件所发生的概率。在我们的例子中 $π(a|s)$ 是指在当前状态处，采取某个动作的概率。当给定随机变量后，状态处的累计回报也是随机变量，而且其分布由随机策略决定。状态-值函数定义为该累计回报的期望。下面我们再看看期望和方差的概念

(4)期望和方差。函数 $f(x)$ 关于某分布 $P(x)$ 的期望是指，当 $x$ 由分布 $P(x)$ 产生、$f$ 作用于 $x$ 时，$f(x)$ 的平均值。对于离散型随机变量，期望公式为：(概率乘以值)的累加

$$E_{x\backsim P}[\,f(x)\,]=\sum_x P(x)f(x)$$

对于连续型随机变量，期望通过积分求得：

$$E_{x\backsim P}[\,f(x)\,]=\int p(x)f(x)dx$$

期望的运算是线性的，即：

$$E_x[\alpha f(x)+\beta g(x)]=\alpha E_x[f(x)]+\beta E_x[g(x)]$$

期望的线性运算在后面的很多推导中都会用到。

(5)方差。方差是衡量利用当前概率分布采样时，采样值差异的大小，可用如下公式得到：

$$Var(f(x))=E[(f(x)-E[f(x)])^2]$$

从定义我们可以看到，方差越小，采样值离均值越近，不确定性越小。尤其是方差很小时，采样值都集中在均值附近，因此不确定性很小(这时，你猜测采样值是均值，那么该猜测离实际采样点很近)。方差的平方根被称为标准差。有了均值和方差，我们现在就可以谈一谈在强化学习中最常用的概率分布了。

最常用的概率分布也就是最常用的随机策略。

(1)贪婪策略。

$$\pi^*(a|s)= \begin{cases} 1,& \text{if $a$ = $\underset{a\in A}{arg max}\,q^*(s,a)$}\\ 0,&\text{otherwise} \end{cases}$$

贪婪策略是一个确定性策略，即只有在使得状态-动作值函数 $q^*(s,a)$ 最大的动作处取概率1，选其他动作的概率为0。

(2)ε-greedy策略。

$$\pi(a|s)= \begin{cases} 1-\varepsilon+\frac{\varepsilon}{|A(s)|},& \text{if $a$ = $arg max_a\,Q(s,a)$}\\ \frac{\varepsilon}{|A(s)|},&\text{otherwise} \end{cases}$$

ε-greedy策略是强化学习最基本最常用随机策略。其含义是选取使得动作值函数最大的动作的概率为 $1-\varepsilon+\frac{\varepsilon}{|A(s)|}$ ，而其他动作的概率为等概率，都为 $\frac{\varepsilon}{|A(s)|}$ 。ε-greedy平衡了利用(exploitation)和探索(exploration)，其中选取动作值函数最大的部分为利用，其他非最优动作仍有概率为探索部分。

(3)高斯策略。一般高斯策略可以写成 $\pi_\theta=\mu_\theta+\varepsilon,\,\varepsilon \backsim N(0,\sigma^2)$ 。其中 $\mu_\theta$ 为确定性部分，$\varepsilon$ 为零均值的高斯随机噪声。高斯策略也平衡了利用和探索，其中利用由确定性部分完成，探索由 $\varepsilon$ 完成。高斯策略在连续系统的强化学习中应用广泛。

(4)玻尔兹曼分布。对于动作空间是是离散的或者动作空间并不大的情况，可采用玻尔兹曼分布作为随机策略，即

$$\pi(a|s,\theta)=\frac{\text{exp}(Q(s,a,\theta))}{\sum_b \text{exp}(h(s,b,\theta))}$$

其中 $Q(s,a,\theta)$ 为动作值函数。该策略的含义是，动作值函数大的动作被选中的概率大，动作值函数小的动作被选中的概率小。

2.3 基于gym的MDP实例讲解

略过。

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

3.1 基于模型的动态规划方法理论(回头补策略迭代，值迭代)

从广义上讲，强化学习是序贯决策问题。但序贯决策问题包含的内容更丰富。它不仅包含马尔科夫过程的决策，而且包括非马尔科夫过程的决策。在上一节，我们已经将强化学习纳入到马尔科夫决策过程MDP的框架之内。马尔科夫决策过程可以利用元组 $(S，A，P，r，γ)$ 来描述，根据转移概率 $P$ 是否已知，可以分为基于模型的动态规划方法和基于无模型的强化学习方法，如图3.2所示。两种类别都包括策略迭代算法，值迭代算法和策略搜索算法。不同的是，在无模型的强化学习方法中，每类算法又分为 online 和 offline 两种。online 和 offline 的具体含义，我们会在下一章中详细介绍。

基于模型的强化学习可以利用动态规划的思想来解决。顾名思义，动态规划中的“动态”蕴含着序列和状态的变化；“规划”蕴含着优化，如线性优化，二次优化或者非线性优化。利用动态规划可以解决的问题需要满足两个条件：一是整个优化问题可以分解为多个子优化问题；二是子优化问题的解可以被存储和重复利用。前面已经讲过，强化学习可以利用马尔科夫决策过程来描述，利用贝尔曼最优性原理得到贝尔曼最优化方程：

$$v^*(s)=\underset{a}{max} R_s^a+\gamma \sum_{s' \in S} P_{ss'}^a v^*(s')\\ q^*(s,a)=R_s^a+\gamma \sum_{s'\in S}P_{ss'}^a max_{a'} q^*(s',a') \tag{3.1}$$

从方程(3.1)中可以看到，马尔科夫决策问题符合使用动态规划的两个条件，因此可以利用动态规划解决马尔科夫决策过程的问题。贝尔曼方程(3.1)指出，动态规划的核心是找到最优值函数。那么，第一个问题是：给定一个策略 $π$ ，如何计算在策略 $π$ 下的值函数？其实上章已经讲过，具体看这：如何计算在策略 $π$ 下的值函数 2.1.4 : (2)

这里再重复一下公式 2.9：

$$v_\pi(s)=\sum_{a\in A}\pi(a|s) \left( R_s^a+\gamma \sum_{s'\in S}P_{ss'}^a v_\pi(s') \right) \tag{3.4}$$

状态 $s$ 处的值函数 $υ_π(s)$，可以利用后继状态的值函数 $υ_π(s′)$ 来表示。可是有人会说，后继状态的值函数 $υ_π(s′)$ 也是未知的，那么怎么计算当前状态的值函数，这不是自己抬自己吗？没错，这正是bootstrapping算法(自举算法)！

如何求解(3.4)的方程？首先，我们从数学的角度去解释方程(3.4)。对于模型已知的强化学习算法，方程(3.4)中的 $P_{ss'}^a$ ，$γ$ 和 $R_s^a$ 都是已知数，$\pi(a|s)$ 为要评估的策略是指定的，也是已知值。方程(3.4)中唯一的未知数是值函数，从这个角度理解方程(3.4)可知，方程(3.4)是关于值函数的线性方程组，其未知数的个数为状态的总数，用 $|S|$ 来表示。

此处，我们使用高斯-赛德尔迭代算法进行求解。即：

$$v_{k+1}(s)=\sum_{a\in A}\pi(a|s) \left( R_s^a+\gamma \sum_{s'\in S}P_{ss'}^a v_\pi(s') \right) \tag{3.5}$$

高斯-赛德尔迭代法的讲解请参看 原书3.2 节。这里以及后边的就略了，重点在后边。

策略迭代，值迭代算法具体看之前周老师的学习笔记：https://www.cnblogs.com/52dxer/p/14309014.html

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

4.1 基于蒙特卡罗方法的理论

本章我们学习无模型的强化学习算法。

强化学习算法的精髓之一是解决无模型的⻢尔科夫决策问题。如图4.1所示，无模型的强化学习算法主要包括蒙特卡罗方法和时间差分方法。本章我们阐述蒙特卡罗方法。

学习蒙特卡罗方法之前，我们先梳理强化学习的研究思路。首先，强化学习问题可以纳入马尔科夫决策过程中，这方面的知识已在第2章阐述。在已知模型的情况下，可以利用动态规划的方法(动态规划的思想是无模型强化学习研究的根源，因此重点阐述)解决马尔科夫决策过程。第3章，阐述了两种动态规划的方法：策略迭代和值迭代。这两种方法可以用广义策略迭代方法统一：即先进行策略评估，也就是计算当前策略所对应的值函数，再利用值函数改进当前策略。无模型的强化学习基本思想也是如此，即：策略评估(用策略计算值函数)和策略改善(用值函数改善策略)。

$$v_\pi(s)=\sum_{a\in A}\pi(a|s)\left(R_s^a+\gamma \sum_{s'\in S} \color{red}{P_{ss'}^a}v_\pi(s')\right)\tag{4.1}$$

动态规划方法计算状态处的值函数时利用了模型 $P_{ss'}^a$ ，而在无模型强化学习中，模型 $P_{ss'}^a$ 是未知的。无模型的强化学习算法要想利用策略评估和策略改善的框架，必须采用其他的方法评估当前策略(计算值函数)。

$$v_\pi(s)=E_\pi[G_t|S_t=s]=E_\pi[\,\sum_{k=0}^{\infty}\gamma^k R_{t+k+1}|S_t=s\,] \tag{4.2}$$

$$q_\pi(s,a)=E_\pi[\sum_{k=0}^{\infty}\gamma^k R_{t+k+1}|S_t=s,A_t=a] \tag{4.3}$$

4.1.1 蒙特卡洛方法里的策略评估方法

状态值函数和行为值函数的计算实际上是计算返回值的期望(参见图4.2)，动态规划的方法是利用模型计算该期望。在没有模型时，我们可以采用蒙特卡罗的方法计算该期望，即利用随机样本估计期望。在计算值函数时，蒙特卡罗方法是利用经验平均代替随机变量的期望。此处，我们要理解两个词：经验和平均。

首先来看下什么是“经验”。当要评估智能体的当前策略时，我们可以利用策略产生很多次试验，每次试验都是从任意的初始状态开始直到终止，比如一次试验(an episode)为 $S_1,A_1,R_2,\cdots,S_T$， 计算一次试验中状态处的折扣回报返回值为 $G_t(s)=R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{T-1}R_T$，

那么“经验”就是指利用该策略做很多次试验，产生很多幕数据(这里的一幕是一次试验的意思)，如图4.3所示。

再来看什么是“平均”。这个概念很简单，平均就是求均值。不过，利用蒙特卡罗方法求状态处的值函数时，又可以分为第一次访问蒙特卡罗方法和每次访问蒙特卡罗方法。

first visit 蒙特卡罗方法是指在计算状态 $s$ 处的值函数时，只利用每次试验中第一次访问到状态 $s$ 时得到的回报求均值。如图4.3中第一次试验所示，计算状态 $s$ 处的均值时只利用 $G_{11}$ ，因此第一次访问蒙特卡罗方法的计算公式为

$$v(s)=\frac{G_{11}(s)+G_{21}(s)+\cdots}{N(s)}$$

every visit 蒙特卡罗方法是指在计算状态处的值函数时，利用所有访问到状态时的回报返回值，即，

$$v(s)=\frac{G_{11}(s)+G_{12}(s)+\cdots+G_{21}(s)+\cdots}{N(s)}$$

根据大数定律：$v(s)\to v_\pi(s)\,as\,N(s)\to \infty$。

由于智能体与环境交互的模型是未知的，蒙特卡罗方法是利用经验平均来估计值函数，而能否得到正确的值函数，则取决于经验——因此，如何获得充足的经验是无模型强化学习的核心所在。

在动态规划方法中，为了保证值函数的收敛性，算法会逐个扫描状态空间中的状态。无模型的方法充分评估策略值函数的前提是每个状态都能被访问到，因此，在蒙特卡洛方法中必须采用一定的方法保证每个状态都能被访问到，方法之一是探索性初始化。

4.1.2 蒙特卡洛方法里的策略改善方法

探索性初始化是指每个状态都有一定的几率作为初始状态。在学习基于探索性初始化的蒙特卡罗方法前，我们还需要先了解策略改善方法，以及便于进行迭代计算的平均方法。下面我们分别介绍蒙特卡罗策略改善方法和可递增计算均值的方法。

(1)蒙特卡罗策略改善。

蒙特卡罗方法利用经验平均估计策略值函数。估计出值函数后，对于每个状态，它通过最大化动作值函数来进行策略的改善。即 $\pi(s)=argmax_a q(s,a)$

(2)递增计算均值的方法如(4.4)式所示。

$$\begin{align*} v_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)v_{k-1}(s)]\\ &=v_{k-1}(s)+\frac{1}{k}[G_k(s)+v_{k-1}(s)]\\ \end{align*} \tag{4.4}$$

如图4.4所示是探索性初始化蒙特卡罗方法的伪代码，需要注意的是：

• 第一，第2步中，每次试验的初始状态和动作都是随机的，以保证每个状态行为对都有机会作为初始状态。在评估状态行为值函数时，需要对每次试验中所有的状态行为对进行估计；
• 第二，第3步完成策略评估，第4步完成策略改善。

我们再来讨论一下探索性初始化。探索性初始化在迭代每一幕时，初始状态是随机分配的，这样可以保证迭代过程中每个状态-行为对都能被选中。它蕴含着一个假设：假设所有的动作都被无限频繁选中。对于这个假设，有时很难成立，或无法完全保证。我们会问，如何保证在初始状态不变的同时，又能保证每个状态行为对可以被访问到？答：精心设计你的探索策略，以保证每个状态都能被访问到。可是如何精心地设计探索策略？符合要求的探索策略应该是什么样的？答：策略必须是温和的，即对所有的状态 $s$ 和 $a$ 满足：$\pi(a|s)>0$ 。也就是说，温和的探索策略是指在任意状态下，采用动作集中每个动作的概率都大于零。典型的温和策略是 $\varepsilon-soft$ 策略也就是 $\varepsilon-greedy$ 策略 ：

$$\pi(a|s)= \begin{cases} 1-\varepsilon+\frac{\varepsilon}{|A(s)|},& \text{if $a$ = $arg max_a\,Q(s,a)$}\\ \frac{\varepsilon}{|A(s)|},&\text{otherwise} \end{cases} \tag{4.5}$$

4.1.3 on policy和off policy

根据探索策略(行动策略)和评估的策略是否为同一个策略，蒙特卡罗方法又分为 on-policy 和 off-policy。若行动策略和评估及改善的策略是同一个策略，我们称为 on-policy，可翻译为同策略。若行动策略和评估及改善的策略是不同的策略，我们称为off-policy，可翻译为异策略。接下来我们重点理解这 on-policy 方法和 off-policy 方法。

(1)同策略。

同策略(on-policy)是指产生数据的策略与评估和要改善的策略是同一个策略。比如，要产生数据的策略和评估及要改善的策略都是 $\varepsilon-soft$ 策略。其伪代码如图4.5所示。

(2)异策略。异策略(off-policy)是指产生数据的策略与评估和改善的策略不是同一个策略。我们用 $\pi$ 表示用来评估和改善的策略，用 $\mu$ 表示产生样本数据的策略。

异策略可以保证充分的探索性。例如用来评估和改善的策略 $\pi$ 是贪婪策略，用于产生数据的探索性策略 $ \mu$ 为探索性策略，如 $\varepsilon-soft$ 策略。

用于异策略的目标策略和行动策略并非任意选择的，而是必须满足一定的条件。这个条件是覆盖性条件，即行动策略 $\mu$ 产生的行为覆盖或包含目标策略 $\pi$ 产生的行为。利用式子表示：满足 $\pi(a|s)>0$ 的任何 $(s,a)$ 均满足 $\mu(a|s)>0$。

利用行为策略产生的数据评估目标策略需要利用重要性采样方法。下面，我们介绍重要性采样。我们用图4.6描述重要性采样的原理。重要性采样来源于求期望，如图4.6所示：

如图4.6所示，当随机变量 $z$ 的分布非常复杂时，无法利用解析的方法产生用于逼近期望的样本，这时，我们可以选用一个概率分布很简单，很容易产生样本的概率分布 $q(z)$ ，比如正态分布。原来的期望可变为

$$\begin{align*} E[f] &=\int f(z)p(z)dz\\ &=\int f(z)\frac{p(z)}{q(z)}q(z)dz\\ &\approx\frac{1}{N}\sum_n\frac{p(z^n)}{q(z^n)}f(z^n),z^n\backsim q(z) \end{align*} \tag{4.7}$$

定义重要性权重：$\omega^n=p(z^n)/q(z^n)$，

普通的重要性采样求积分如方程(4.7)所示为

$$E[f]=\frac{1}{N}\sum_n\omega^nf(z^n)\tag{4.8}$$

由式(4.7)可知，基于重要性采样的积分估计为无偏估计，即估计的期望值等于真实的期望。但是，基于重要性采样的积分估计的方差无穷大。这是因为原来的被积函数乘了一个重要性权重，改变了被积函数的形状及分布。尽管被积函数的均值没有发生变化，但方差明显发生改变。

在重要性采样中，使用的采样概率分布与原概率分布越接近，方差越小。然而，被积函数的概率分布往往很难求得、或很奇怪，因此没有与之相似的简单采样概率分布，如果使用分布差别很大的采样概率对原概率分布进行采样，方差会趋近于无穷大。一种减小重要性采样积分方差的方法是采用加权重要性采样：

先略了，太难了，数学公式搞得头大，具体内容看书。

on policy和off policy的优劣之分：5.1章节在时间差分强化学习方法中再次比较了on policy和off policy

来源：https://www.zhihu.com/question/56561878/answer/149892732

理想情况下，强化学习应该直奔最优策略而去--确定性的“状态-最优行为选择”。我们称之为target policy。
这是on-policy的目标，但在实施时，会遭遇探索-利用的矛盾：光利用目前已知的最优选择，可能学不到最优解，收敛到局部最优；而加入探索又降低了学习效率。$\varepsilon-greedy$ 算法是这种矛盾下的折中 。
为避免on policy的问题，off policy索性把问题一分为二，采取了从行为策略来学习目标策略的办法，两者可以互不干扰。具体来说：先产生某概率分布下的大量行为数据(behavior policy)，意在探索。从这些偏离(off)最优策略的数据中寻求target policy。当然这么做是需要满足数学条件的：假設 $π$ 是目标策略, $\mu$ 是行为策略，那么从 $\mu$ 学到 $\pi$ 的条件是：$π(a|s) > 0$ 必然有 $\mu(a|s) > 0$成立。
两种学习策略的关系是：on-policy是off-policy 的特殊情形，其target policy 和behavior policy是一个。
on-policy优点是直接了当，速度快，劣势是不一定找到最优策略。
off-policy劣势是曲折，收敛慢，但优势是更为强大和通用。其强大是因为它确保了数据全面性，所有行为都能覆盖。甚至其数据来源可以多样，自行产生、或者外来数据均可。

总结一下：本节重点讲解了如何利用MC的方法估计值函数。与基于动态规划的方法相比，基于MC的方法只是在值函数估计上有所不同，在整个框架上则是相同的，即评估当前策略，再利用学到的值函数进行策略改善。本节需要重点理解on-policy 和off-policy的概念，并学会利用重要性采样来评估目标策略的值函数。

4.2 统计学基础知识

联系我们关于强化学习算法的概念：强化学习是智能体通过与环境交互产生数据，并把从中学到的知识内化为自身行为的过程。学习的过程其实就是数据的处理和加工过程。尤其是值函数的估计，更是利用数据估计真实值的过程，涉及样本均值，方差，有偏估计等，这些都是统计学的术语。下面做些简单介绍。

总体：包含所研究的全部数据的集合。

样本：从总体中抽取的一部分元素的集合。在 episode 强化学习中，一个样本是指一幕数据。

统计量：用来描述样本特征的概括性数字度量。如样本均值，样本方差，样本标准差等。在强化学习中，我们用样本均值衡量状态值函数。

样本均值：设 $X_1,X_2,X_3,\cdots,X_n$ 为样本容量为 n 的随机样本，它们是独立同分布的随机变量，则样本均值为 $\bar{X}=\frac{X_1+X_2+\cdots+X_n}{n}$ ，样本均值也是随机变量。

样本方差：设 $X_1,X_2,X_3,\cdots,X_n$ 为样本容量为n的随机样本，它们是独立同分布的随机变量，则样本方差为 $\hat{S^2}=\frac{(X_1-\bar{X})^2+(X_2-\bar{X})^2+\cdots+(X_n-\bar{X})^2}{n}$

无偏估计：若样本的统计量等于总体的统计量，则称该样本的统计量所对应的值为无偏估计。如总体的均值和方差分别为 $\mu$ 和 $\sigma^2$ 时，若 $E(\bar{X})=\mu$ ，$E(\hat{S^2})=\sigma^2$ ，则 $\bar{X}$ 和 $\hat{S^2}$ 称为无偏估计。

略，看原文内容

4.3 基于Python的编程实例

蒙特卡罗方法解决的是无模型的强化学习问题，基本思想是利用经验平均代替随机变量的期望。因此，利用蒙特卡罗方法评估策略应该包括两个过程：模拟和平均。模拟就是产生采样数据，平均则是根据数据得到值函数。下面我们以利用蒙特卡罗方法估计随机策略的值函数为例做详细说明。

4.3.1 随机策略的样本产生：

模拟图4.10为蒙特卡罗方法的采样过程。该采样函数包括两个大循环，第一个大循环表示采样多个样本序列，第二个循环表示产生具体的每个样本序列。需要注意的是，每个样本序列的初始状态都是随机的。因为评估的是随机均匀分布的策略，所以在采样的时候，动作都是根据随机函数产生的。每个样本序列包括状态序列，动作序列和回报序列。

# 蒙特卡洛样本采集(随机初始化状态，随机选择动作，随机产生多条轨迹，保存轨迹)
def gen_randompi_sample(self,num):
    state_sample = [ ]
    action_sample = [ ]
    reward_sample = [ ]
    for i in range(num):
        s_tmp = [ ]
        a_tmp = [ ]
        r_tmp = [ ]
        s=self.states[int(random.random()*len(self.states))]    # 随机初始化每回合的初始状态
        done=False
        while t==False:    #产生一条轨迹，如s1->s2->s3->s7轨迹
            a=self.actions[int(random.random()*len(self.actions))]
            done,s_next,r = self.transform(s,a)
            s_tmp.append(s)
            a_tmp.append(a)
            r_tmp.append(r)
            s=s_next
        state_sample.append(s_tmp)	#样本包含多个状态样例
        action_sample.append(a_tmp)
        reward_sample.append(r_tmp)
    return state_sample,action_sample,reward_sample

第一处：对于每条轨迹逆向计算该轨迹的初始状态处的累计回报，也就是说从轨迹的最后一个状态开始往前依次计算，最终得到初始状态处的累计回报为 $G$，计算公式为 $G_t=R_{t+1}+\gamma G_{t+1}$

第二处：正向计算每个状态所对应的累计函数，计算公式为 $G_{t+1}=(G_t-R_{t+1})/\gamma$ 。

第三处：求均值，即累计和对该状态出现的次数求均值。相应于第1节中的每次访问蒙特卡罗方法。

下面，我们实现基于蒙特卡罗的强化学习算法。蒙特卡罗强化学习每次迭代评估的都是ε-greedy策略。

# 蒙特卡洛评估
def mc(gamma,state_sample,action_sample,reward_sample):
    vfunc = dict ()     # v(s) 状态值
    nfunc = dict ()     # 次数
    # 初始化，每个状态值为0，经过的次数为0
    for s in states:
        vfunc[s]=0.0
        nfunc[s]=0.0
 
    for iter1 in range(len(state_sample)):
        G=0.0
        # 第一处：逆向计算初始状态的累计回报
        for step in range(len(state_sample[iter1])-1,-1,-1):
            G*=gamma
            G+=reward_sample[iter1][step]
        # 第二处：正向计算每个状态处的累计回报
        for step in range(len(state_sample[iter1])):
            s=state_sample[iter1][step]
            vfunc[s]+=G
            nfunc[s]+=1.0
            G-=reward_sample[iter1][step]
            G/=gamma
    # 第三处：每个状态处求经验平均
    for s in states:
        if nfunc[s] > 0.000001:
            vfunc[s]/=nfunc[s]
            
    return vfunc

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

5.1 基于时间差分强化学习算法理论讲解

第4章我们已经阐述了无模型强化学习最基本的方法蒙特卡罗方法。本章我们阐述另外一个无模型的方法：时间差分方法。

时间差分(Temporal-Difference，简称TD)方法(如图5.1所示)是另一种无模型强化学习方法，也是强化学习理论中最核心的内容。与动态规划的方法和蒙特卡罗的方法相比，时间差分方法的主要不同在于值函数的估计。

如图5.2所示为用动态规划的方法计算值函数。

下面的式(5.1)是值函数估计的计算公式，从中可以看到，用动态规划方法(DP)计算值函数时用到了当前状态 $s$ 的所有后继状态 $s’$ 处的值函数。值函数的计算用到了bootstrapping的方法。所谓 bootstrapping本意是指自举，此处是指当前值函数的计算用到了后继状态的值函数。即用后继状态的值函数估计当前值函数。要特别注意的是，此处后继的状态是由模型公式 $p(s',r|S_t,a)$ 计算得到的。由模型公式和动作集，可以计算状态 $s$ 所有的后继状态 $s’$ 。当没有模型时，后继状态无法全部得到，只能通过试验和采样的方法每次试验得到一个后继状态 $s’$ 。

$$V(S_t)\leftarrow E_\pi[R_{t+1}+\gamma V(S_{t+1})]=\sum_a \pi(a|S_t)\sum_{s',r}p(s',r|S_t,a)[r+\gamma \color{red}{V(s')}] \tag{5.1}$$

无模型时，我们可以采用蒙特卡罗的方法利用经验平均来估计当前状态的值函数，用它计算值函数的过程如图5.3所示。

蒙特卡罗方法利用经验平均估计状态的值函数。此处的经验是指一次试验，而一次试验要等到终止状态出现才结束(参见图5.3)。公式(5.2)中的 $G_t$ 是状态处 $S_t$ 的折扣累积回报值。

$$V(S_t) \leftarrow V(S_t)+\alpha(G_t-V(S_t)) \tag{5.2}$$

相比于动态规划的方法，蒙特卡罗的方法需要等到每次试验结束，所以学习速度慢，学习效率不高。通过对两者的比较，我们很自然地会想到：能不能借鉴动态规划中bootstrapping的方法，在试验未结束时就估计当前的值函数呢？

答案是肯定的，这是时间差分方法的精髓。时间差分方法结合了蒙特卡罗的采样方法(即做试验)和动态规划方法的bootstrapping(利用后继状态的值函数估计当前值函数)，它的计算过程如图5.4所示。

用时间差分方法(TD)将值函数的公式更新为

$$V(S_t)\leftarrow V(S_t)+\alpha (R_{t+1}+\gamma V(S_{t+1})-V(S_t)) \tag{5.3}$$

其中 $R_{t+1}+\gamma V(S_{t+1})$ 称为 TD 目标，与(5.2)中的 $G_t$ 相对应，两者不同之处是TD目标利用了bootstrapping方法估计当前值函数。$\delta_t= R_{t+1}+\gamma V(S_{t+1})-V(S_t)$ 称为TD偏差。

下面我们从原始公式出发，了解动态规划(DP)、蒙特卡罗方法(MC)和时间差分方法(TD)的不同之处。

下面公式是用三种方法估计值函数的异同点。

DP：期望值由模型来提供，但是利用真值的当前估计值 $V(S_{t+1})$ 。

MC：利用采样平均回报逼近期望

TD：联合了MC和DP，采样期望值，并利用真值的当前估计值 $V(S_{t+1})$ 。

$$\begin{align*}{} v_\pi(s) &=E_\pi[G_t|S_t=s]\\ &=E_\pi[\sum_{k=0}^{\infty}\gamma^k R_{t+k+1}|S_t=s]\\ &=E[R_{t+1}+\gamma \sum_{k=0}^{\infty}\gamma^k R_{t+k+2}|S_t=s]\\ &=E[R_{t+1}+\gamma v_\pi(S_{t+1})|S_t=s]\\ \end{align*}$$

从中可以看到，蒙特卡罗的方法使用的是值函数最原始的定义，该方法利用所有回报的累积和估计值函数；动态规划方法和时间差分方法则利用一步预测方法计算当前状态值函数，它俩的共同点是利用了bootstrapping 方法；不同的是，动态规划方法利用模型计算后继状态，时间差分方法利用试验得到后继状态。

从统计学的角来看，蒙特卡罗方法(MC)和时间差分方法(TD)都是利用样本估计值函数的方法，哪种更好呢？

既然都是统计方法，我们就可以从期望和方差两个指标对比两种方法。

首先我们先看看蒙特卡罗方法。蒙特卡罗方法中的返回值 $G_t=R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{T-1}R_t$ ，其期望便是值函数的定义，因此蒙特卡罗方法是无偏估计。但是，蒙特卡罗方法每次得到的值要等到最终状态出现，在这个过程中会经历很多随机的状态和动作，每次得到的随机性很大，因此尽管期望等于真值，但方差无穷大。

我们再来看下时间差分方法。时间差分方法的TD目标为 $R_{t+1}+\gamma V(S_{t+1})$ ，若 $V(S_{t+1})$ 采用真实值，则TD估计也是无偏估计，然而在试验中 $V(S_{t+1})$ 用的也是估计值，因此时间差分估计方法属于有偏估计。与蒙特卡罗方法相比，时间差分方法只用到了一步随机状态和动作，因此TD目标的随机性比蒙特卡罗方法中的要小，相应的方差也比蒙特卡罗方法中的方差小。

时间差分方法包括同策略的 Sarsa 方法和异策略的 Q-learning 方法。如图5.6所示为同策略 Sarsa 强化学习算法，需要注意的是方框中代码表示同策略中的行动策略和评估的策略都是 $ε-greedy$ 策略。与蒙特卡罗方法不同的是，它的值函数更新不同。

如图5.7所示为异策略的 Q-learning 方法。与 Sarsa 方法的不同之处在于，Q-learning 方法是异策略的方法。即行动策略采用 $ε-greedy$ 策略，而目标策略为贪婪策略。

这里跟Sarsa算法很大不同的是：对第二个action的采样，在Sarsa中我们要根据target policy进行两次对action的采样。在Q-learning中第一个采样我们是用 $\varepsilon-greedy$ 采样出来的，第二个action的采样，我们是用贪婪策略采样出来的，是在Q table中取一个收益max的action。然后我们对Q table进行更新，然后当前的状态进入到下一个状态。

• On-policy Learning就是我们的目的是学到最佳策略，在学习过程中我们只利用一种策略，既利用这个策略进行轨迹的采集，也进一步进行策略的优化，都是用的同一个策略。例子：$ \varepsilon−greedy$
• Off-poilcy Learning就是我们在策略的学习过程中保留两种不同的策略。第一个策略是我们进行优化的策略，是希望学到最佳的策略。另外一个策略是我们用来探索的策略，因为是用来探索的策略，所以我们可以让这个策略更加的激进对环境进行探索。所以我们学习的是 target policy：π ，但是我们利用的数据，采集到的轨迹是用第二个策略 behavior policy：μ 产生。

Off-policy Learning的好处：

• 因为可以利用一个更加激进的behavior policy，所以我们可以学到一个更加优化的策略。
• 可以从其他的数据中进行学习，因为这些轨迹可能是人，或者其他agent产生的，那么就可以进行一个模仿学习。
• 我们可以反复利用一些老的策略产生的轨迹。因为探索轨迹的过程中，我们要用到很多的计算机资源，如果我们之前产生的轨迹，对于我们现在优化的轨迹不能利用的话，这样就浪费了很多资源。

$TD(\lambda)$ 算法具体看之前写的文章：https://www.cnblogs.com/52dxer/p/14400336.html

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

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

前面已经介绍了强化学习的基本方法：基于动态规划的方法，基于蒙特卡罗的方法和基于时间差分的方法。这些方法有一个基本的前提条件：状态空间和动作空间是离散的，而且状态空间和动作空间不能太大。

这些强化学习方法的基本步骤是先评估值函数，再利用值函数改善当前的策略。其中值函数的评估是关键。

对于模型已知的系统，可以利用动态规划的方法得到值函数；对于模型未知的系统，可以利用蒙特卡罗的方法或时间差分的方法得到值函数。

注意，这时的值函数其实是一个表格。对于状态值函数，其索引是状态；对于行为值函数，其索引是状态-行为对。值函数的迭代更新实际上就是这张表的迭代更新。因此，之前讲的强化学习算法又称为表格型强化学习。对于状态值函数，其表格的维数为状态的个数 $|S|$ ，其中 $S$ 为状态空间。若状态空间的维数很大，或者状态空间为连续空间，此时值函数无法用一张表格来表示。这时，我们需要利用函数逼近的方法表示值函数，如图6.1所示。当值函数利用函数逼近的方法表示后，可以利用策略迭代和值迭代方法构建强化学习算法。

在表格型强化学习中，值函数对应着一张表。在值函数逼近方法中，值函数对应着一个逼近函数 $\hat{v}(s)$ 。从数学角度来看，函数逼近方法可以分为参数逼近和非参数逼近，因此强化学习值函数估计可以分为参数化逼近和非参数化逼近。其中参数化逼近又分为线性参数化逼近和非线性化参数逼近。

本节我们主要介绍参数化逼近。所谓参数化逼近，是指值函数可以由一组参数 $θ$ 来近似。我们将逼近的值函数写为 $\hat{v}(s,\theta)$ 。

当逼近的值函数结构确定时(如线性逼近时选定了基函数，非线性逼近时选定了神经网络的结构)，那么值函数的逼近就等价于参数的逼近。值函数的更新也就等价于参数的更新。也就是说，我们需要利用试验数据来更新参数值。那么，如何利用数据更新参数值呢，也就是说如何从数据中学到参数值呢？

我们回顾一下表格型强化学习值函数更新的公式，以便从中得到启发。

蒙特卡罗方法，值函数更新公式为：

$$Q(s,a)\leftarrow Q(s,a)+\alpha(\color{red}{G_t}-Q(s,a)) \tag{6.1}$$

TD方法值函数更新公式为：

$$Q(s,a)\leftarrow Q(s,a)+\alpha[\color{red}{r+\gamma Q(s',a')}-Q(s,a)] \tag{6.2}$$

$TD(\lambda)$ 方法值函数更新公式为：

$$Q(s,a)\leftarrow Q(s,a)+\alpha(\color{red}{G_t^\lambda}-Q(s,a)) \tag{6.3}$$

从(6.1)〜(6.3)式值函数的更新过程可以看出，值函数更新过程是向着目标值函数靠近。如图6.2所示为TD方法更新值函数的过程。

从表格型值函数的更新过程，可以看出无论是蒙特卡罗方法还是时间差分方法，都是朝着一个目标值更新的，这个目标值在蒙特卡罗方法中是 $\color{red}{G_t}$ ，在时间差分方法中是 $\color{red}{r+\gamma Q(s',a')}$ ，在 $TD(\lambda)$ 中是 $\color{red}{G_t^\lambda}$。

将表格型强化学习值函数的更新过程推广到值函数逼近过程，有如下形式。

函数逼近 $\hat{v}(s,\theta)$ 的过程是一个监督学习的过程，其数据和标签对为 $(S_t,U_t)$ ，其中 $U_t$ 等价于蒙特卡罗方法中的，时间差分方法中的 $\color{red}{r+\gamma Q(s',a')}$ ，以及 $TD(\lambda)$ 中的 $\color{red}{G_t^\lambda}$。

训练的目标函数为

$$arg\,\underset{\theta}{min}(q(s,a)-\hat{q}(s,a,\theta))^2 \tag{6.4}$$

下面我们比较总结一下表格型强化学习和函数逼近方法的强化学习值函数更新时的异同点。

(1)表格型强化学习在更新值函数时，只有当前状态 $S_t$ 处的值函数改变，其他地方的值函数不改变。

(2)值函数逼近方法更新值函数时，更新的是参数 $\theta$ ，而估计的值函数为 $\hat{v}(s,\theta)$ ，所以当参数 $\theta$ 发生改变，任意状态处的值函数都会发生改变。

值函数更新可分为增量式学习方法和批学习方法。我们先介绍增量式学习方法，其中随机梯度下降法是最常用的增量式学习方法。

1.增量式学习方法：随机梯度下降法

由(6.4)式我们得到参数的随机梯度更新为

$$\theta_{t+1}=\theta_t+\alpha[U_t-\hat{v}(S_t,\theta_t)]\nabla_\theta \hat{v}(S_t,\theta) \tag{6.5}$$

基于蒙特卡罗方法的函数逼近，具体过程如下。

给定要评估的策略 $\pi$ ，产生一次试验：

值函数的更新过程实际是一个监督学习的过程，其中监督数据集从蒙特卡罗的试验中得到，其数据集为 $<s_1,G_1>,<s_2,G_2>,\cdots,<s_T,G_T>$ 。

值函数的更新如下。

$$\Delta \theta=\color{red}{\alpha }(G_t-\hat{v}(S_t,\theta))\nabla_\theta \hat{v}(S_t,\theta) \tag{6.6}$$

其中 $\alpha$ 值比较小。在随机梯度下降法中，似乎并不清楚为什么每一步采用很小的更新。难道我们不能在梯度的方向上移动很大的距离甚至完全消除误差吗？在很多情况下确实可以这样做，但是通常这并不是我们想要的。请记住，我们的目的并不是在所有的状态找到精确的值函数，而是一个能平衡所有不同状态误差的值函数逼近。如果我们在一步中完全纠正了偏差，那么我们就无法找到这样的一个平衡了。因此较小的 $\alpha$ 值可以维持这种平衡。

如图6.3所示为基于梯度的蒙特卡罗值函数逼近更新过程。蒙特卡罗方法的目标值函数使用一次试验的整个回报返回值。

我们再看时间差分方法。根据方程(6.5)，TD(0)方法中目标值函数为 $U_t=R_{t+1}+\gamma \hat{v}(S_{t+1},\theta)$，即目标值函数用到了bootstrapping的方法。

我们注意到此时要更新的参数 $\theta$ 不仅出现在要估计的值函数 $\hat{v}(S_t,\theta)$ 中，还出现在目标值函数 $U_t$ 中。若只考虑参数 $\theta$ 对估计值函数 $\hat{v}(S_t,\theta)$ 的影响而忽略对目标值函数 $U_t$ 的影响，这种方法就不是完全的梯度法(只有部分梯度)，因此也称为基于半梯度的 $TD(0)$ 值函数评估算法，如图6.4所示。

$$\theta_{t+1}=\theta_t+\alpha [R+\gamma \hat{v}(S',\theta)-\hat{v}(S_t,\theta_t)]\nabla \hat{v}(S_t,\theta_t) \tag{6.7}$$

如图 6.5 所示为基于半梯度的 Sarsa 算法。与表格型强化学习相比，值函数逼近方法中把对值函数的更新换成了对参数的更新，参数的学习过程为监督学习。

到目前为止，我们还没有讨论要逼近的值函数的形式。值函数可以采用线性逼近也可采用非线性逼近。非线性逼近常用的是神经网络。

下面我们仅讨论线性逼近的值函数：$\hat{v}(s,\theta)=\theta ^T \phi (s)$，值函数由一组参数 $\theta$ 来近似。

相比于非线性逼近，线性逼近的好处是只有一个最优值，因此可以收敛到全局最优。其中$\phi(s)$ 为状态 $s$ 处的特征函数，或者称为基函数。

常用的基函数的类型如下。

多项式基函数，如 $(1,s_1,s_2,s_1s_2,s_1^2,s_2^2,\cdots)$ 。

傅里叶基函数：$\phi _i(s)=cos(i\pi s),s\in[0,1]$

径向基函数：$\phi_i(s)=exp(-\frac{||s-c_i||^2}{2\sigma_i^2})$

将线性逼近值函数代入随机梯度下降法和半梯度下降法中，可以得到参数的更新公式，不同强化学习方法的参数更新公式如下。

蒙特卡罗方法值函数方法的参数更新公式：

$$\begin{align*}{} \Delta \theta &=\alpha[\color{red}{U_t(s)}-\hat{v}(S_t,\theta_t)]\nabla \hat{v}(S_t,\theta_t)\\ &=\alpha [G_t-\theta ^T \phi]\phi \end{align*}$$

TD(0)线性逼近值函数方法的参数更新公式：

$$\begin{align*}{} \Delta \theta &=\alpha[\color{red}{R+\gamma \theta^T \phi(s')}-\theta^T\phi(s)]\phi (s)\\ &=\alpha \delta \phi(s) \end{align*}$$

正向视角的参数更新公式：

$$\Delta \theta =\alpha(G_t^\lambda -\theta ^T\phi) \phi$$

后向视角的参数更新公式：

$$\begin{align*}{} \delta_t &=R_{t+1}+\gamma \theta^T \phi(s')-\theta ^T\phi (s)\\ E_t&=\gamma \lambda E_{t-1}+\phi(s)\\ \Delta \theta&=\alpha \delta_t E_t \end{align*}$$

前面讨论的是增量式方法更新。增量式方法参数更新过程随机性比较大，尽管计算简单，但样本数据的利用效率并不高。

我们再来看下批的方法，尽管它计算复杂，但计算效率高。

所谓批的方法是指给定经验数据集 $D=\{<s_1,v_1^\pi>,<s_2,v_2^\pi>,\cdots,<s_T,v_T^\pi>\}$ ，找到最好的拟合函数 $\hat{v}(s,\theta)$ ，使得 $Loss(\theta)=\sum_{t=1}^{T}(v_t^\pi-\hat{v}_t^\pi(s_t,\theta))$ 最小。

可利用线性最小二乘逼近：

$$\Delta \theta=\alpha \sum_{t=1}^{T}[v_t^\pi-\theta^T\phi(s_t)]\phi(s_t)=0$$

最小二乘蒙特卡罗方法参数为

最小二乘差分方法为

最小二乘方法为

略。。。(看原书内容)

6.2 DQN及其变种

6.2.1 DQN方法

本节主要讲解 DQN，也就是 DeepMind 发表在 Nature 上的第一篇论文，名字是 Human-level Control through Deep ReinforcementLearning。

平心而论，这篇论文只有两个创新点，即经验回放和设立单独的目标网络，后面我们会详细介绍。算法的大体框架是传统强化学习中的Q-learning。我们已经在第5章时间差分方法中阐述了。为了前后理解方便，我们再重新梳理下。Q-learning方法是异策略时间差分方法。其伪代码如图6.6所示。

行动策略采用 $\varepsilon-greedy$策略，评估策略采用贪婪策略。

掌握 Q-learning 方法一定要明白两个概念——异策略和时间差分，以及这两个概念在Q-learning算法是中如何体现的。下面我们一一介绍。

异策略，是指行动策略(产生数据的策略)和要评估的策略不是一个策略。在图6.6 的Q-learning 伪代码中，行动策略(产生数据的策略)是第5行的 $ε-greedy$ 策略，而要评估和改进的策略是第6行的贪婪策略(每个状态取值函数最大的那个动作)。

时间差分方法，是指利用时间差分目标来更新当前行为值函数。在图6.6 的Q-learning伪代码中，时间差分目标为 $r_t+\gamma \underset{a}{max}Q(s_{t+1},a)$ 。

Q-learning算法是1989年由Watkins提出来的，2015年Nature论文提到的DQN就是在Q-learning的基础上修改得到的。DQN对Q-learning的修改主要体现在以下三个方面。

(1)DQN利用深度卷积神经网络逼近值函数；

(2)DQN利用了经验回放训练强化学习的学习过程；

(3)DQN独立设置了目标网络来单独处理时间差分算法中的TD偏差。

下面，我们对这三个方面做简要介绍。

(1)DQN 利用卷积神经网络逼近行为值函数。如图6.7所示为 DQN 的行为值函数逼近网络。我们在6.1节已经介绍了值函数的逼近。只不过6.1节中讲的是线性逼近，即值函数由一组基函数和一组与之对应的参数相乘得到，值函数是参数的线性函数。而 DQN 的行为值函数利用神经网络逼近，属于非线性逼近。虽然逼近方法不同，但都属于参数逼近。请记住，此处的值函数对应着一组参数，在神经网络里参数是每层网络的权重，我们用 $\theta$ 表示。用公式表示的话值函数为 $Q(s,a;\color{red}{\theta})$。请留意，此时更新值函数时其实是更新参数 $\theta$ ，当网络结构确定时，$\theta$ 就代表值函数。DQN所用的网络结构是三个卷积层加两个全连接层，整体框架如图6.7所示。

利用神经网络逼近值函数的做法在强化学习领域早就存在了，可以追溯到上个世纪 90 年代。当时学者们发现利用神经网络，尤其是深度神经网络逼近值函数不太靠谱，因为常常出现不稳定不收敛的情况，所以在这个方向上一直没有突破，直到DeepMind的出现。

我们要问，DeepMind到底做了什么？

别忘了DeepMind的创始人Hassabis是神经科学的博士。早在2005年，Hassabis就开始琢磨如何利用人的学习过程提升游戏的智能水平，为此他去伦敦大学开始攻读认知神经科学方向的博士，并很快有了突出成就，在Science、Nature等顶级期刊狂发论文。他当时的研究方向是海马体——那么，什么是海马体？为什么要选海马体？

海马体是人类大脑中负责记忆和学习的主要部分，从Hassabis学习认知神经科学的目的来看，他选海马体作为研究方向就是水到渠成的事儿了。现在我们就可以回答，DeepMind到底做了什么？他们将认识神经科学的成果应用到了深度神经网络的训练之中！

(2)DQN利用经验回放训练强化学习过程。我们睡觉的时候，海马体会把一天的记忆重放给大脑皮层。利用这个启发机制，DeepMind团队的研究人员构造了一种神经网络的训练方法：经验回放。通过经验回放为什么可以令神经网络的训练收敛且稳定？原因是：训练神经网络时，存在的假设是训练数据是独立同分布的，但是通过强化学习采集的数据之间存在着关联性，利用这些数据进行顺序训练，神经网络当然不稳定。经验回放可以打破数据间的关联，如图6.8所示。

在强化学习过程中，智能体将数据存储到一个数据库中，再利用均匀随机采样的方法从数据库中抽取数据，然后利用抽取的数据训练神经网络。这种经验回放的技巧可以打破数据之间的关联性，该技巧在2013年的NIPS已经发布了，2015 年的 Nature 论文则进一步提出了目标网络的概念，以进一步降低数据间的关联性。(3)DQN设置了目标网络来单独处理时间差分算法中的TD偏差。与表格型的Q-learning算法(图6.6)不同的是，利用神经网络对值函数进行逼近时，值函数的更新步更新的是参数(如图 6.9 所示)，DQN 利用了卷积神经网络。其更新方法是梯度下降法。因此图6.6中第6行值函数更新实际上变成了监督学习的一次更新过程，其梯度下降法为

$$\theta_{t+1}=\theta_t+\alpha[r+\gamma\underset{a'}{max}Q(s',a';\color{blue}{\theta})-Q(s,a;\color{red}{\theta})]\nabla Q(s',a';\theta)$$

其中，$r+\gamma\underset{a'}{max}Q(s',a';\color{blue}{\theta})$ 为 $TD$ 目标，在计算 $\underset{a'}{max}Q(s',a';\color{blue}{\theta})$ 值时用到的网络参数为 $\color{blue}\theta$ 。

我们称计算 $TD$ 目标时所用的网络为 $TD$ 网络。在DQN算法出现之前，利用神经网络逼近值函数时，计算 $TD$ 目标的动作值函数所用的网络参数 $\color{blue}\theta$，与梯度计算中要逼近的值函数所用的网络参数 $\color{red}\theta$ 相同，这样就容易导致数据间存在关联性，从而使训练不稳定。为了解决此问题，DeepMind提出计算 $TD$ 目标的网络表示为 $\color{green}{\theta^-}$；计算值函数逼近的网络表示为 $\color{red}\theta$ ；用于动作值函数逼近的网络每一步都更新，而用于计算 $TD$ 目标的网络则是每个固定的步数更新一次。因此值函数的更新变为

$$\theta_{t+1}=\theta_t+\alpha[r+\gamma \underset{a'}{max}Q(s',a';\color{green}{\theta^-})-Q(s,a;\color{red}{\theta})]\nabla Q(s,a'\color{red}{\theta})$$

最后我们给出DQN的伪代码，如图6.10a所示。

下面我们对DQN的伪代码逐行说明。

第[1]行，初始化回放记忆池 $D$，可容纳的数据条数为$N$；

第[2]行，随机初始化动作值函数 $Q$ 的参数 $\color{red}\theta$；

第[3]行，用随机权值 $\color{red}\theta$ 初始化计算 $TD$ 目标的动作值函数 $\hat{Q}$ 的参数 $\color{green}{\theta^-}$ ，令 $\color{green}{\theta^-}=\color{red}{\theta}$ ；

第[4]行，循环每条轨迹；

第[5]行，初始化轨迹的第一个状态$s_1=\{x_1\}$，通过预处理得到状态对应的特征输入 $\phi_1=\phi(s_1)$；

第[6]行，循环每条轨迹的每一步；

第[7]行，利用 $\varepsilon-greedy$ 策略，一定概率随机选一个动作 $a_t$；(探索)

第[8]行，若小概率事件没发生，则用贪婪策略选择当前值函数最大的那个动作 $a_t=arg\underset{a}{max} Q(\phi(s_t),a;\theta)$ (利用)

注意：这里选最大动作时用到的值函数网络与逼近值函数所用的网络是一个网络，都对应。

注意：第[7]行和第[8]行是行动策略，即 $ε-greedy$ 策略。

第[9]行，在仿真器中执行动作 $a_t$ ，观测回报 $r_t$ 以及图像 $x_{t+1}$ ；

第[10]行，设置 $s_{t+1}=s_t,a_t,x_{t+1}$ ，预处理 $\phi_{t+1}=\phi(s_{t+1})$ ；

第[11]行，将轨迹 $(\phi_t,a_t,r_t,\phi_{t+1})$ 储存在回放记忆池 $D$ 中；

第[12]行，从回放记忆 $D$ 中均匀随机采样一条轨迹样本数据，用 $(\phi_j,a_j,r_j,\phi_{j+1})$ 表示；

第[13]行，如果 $step_{j+1}$ 是一条轨迹的终止状态，则 $TD$ 目标值为 $y_j=r_j$，否则利用 $TD$ 目标网络 $\color{green}{\theta^-}$ 计算 $TD$ 目标值为 $y_j=r_j+\gamma\underset{a'}{max}Q(s',a';\color{green}{\theta^-})$；

第[14]行，执行一次梯度下降算法 $\Delta \theta =\alpha[r+\gamma\underset{a'}{max}Q(s',a';\color{green}{\theta^-})-Q(s,a;\color{red}{\theta})]\nabla Q(s,a;\color{red}{\theta})$ ；

第[15]行，更新动作值函数逼近的网络参数 $\color{red}{\theta}=\color{red}{\theta}+\Delta\theta$ ；

第[16]行，每隔 $C$ 步更新一次 $TD$ 目标网络权值，即令 $\color{green}{\theta^-}=\color{red}{\theta}$ ；

第[17]行，结束每条轨迹内循环；

第[18]行，结束轨迹间循环。

我们可以看到，在第[12]行利用了经验回放；在第[13]行利用了独立的目标网络；第[15]行更新动作值函数逼近网络参数 $\color{red}{\theta}$ ；第[17]行更新目标网络参数 $\color{green}{\theta^-}$ 。

6.2.2 Double DQN

上一节我们讲了第一个深度强化学习方法DQN，DQN的框架仍然是Q-learning。DQN 只是利用了卷积神经网络表示动作值函数，并利用了经验回放和单独设立目标网络这两个技巧。DQN无法克服Q-learning 本身所固有的缺点——过估计。

那么什么是过估计？Q-learning为何具有过估计的缺点呢？

过估计是指估计的值函数比真实值函数要大。一般来说，Q-learning之所以存在过估计的问题，根源在于Q-learning中的最大化操作。Q-learning评估值函数的数学公式如下有两类。

• 对于表格型，值函数评估的更新公式为

$$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha\left[r_t+\gamma \underset{a}{max} Q(s_{t+1},a)-Q(s_t,a_t)\right]$$

●对于基于函数逼近的方法的值函数更新公式为

$$\theta_{t+1}=\theta_t+\alpha\left[R_{t+1}+\gamma \underset{a}{max} Q(S_{t+1},a;\theta_t)-Q(S_t,A_t;\theta_t) \right] \nabla_{\theta_t} Q(S_t,A_t;\theta_t)$$

从以上两个式子我们知道，不管是表格型还是基于函数逼近的方法，值函数的更新公式中都有max操作。max操作使得估计的值函数比值函数的真实值大。如果值函数每一点的值都被过估计了相同的幅度，即过估计量是均匀的，那么由于最优策略是贪婪策略，即找到最大的值函数所对应的动作，这时候最优策略是保持不变的。也就是说，在这种情况下，即使值函数被过估计了，也不影响最优的策略。强化学习的目标是找到最优的策略，而不是要得到值函数，所以这时候就算是值函数被过估计了，最终也不影响我们解决问题。

然而，在实际情况中，过估计量并非是均匀的，因此值函数的过估计会影响最终的策略决策，从而导致最终的策略并非最优，而只是次优。为了解决值函数过估计的问题，Hasselt 提出了 Double Q-learning 的方法。所谓Double Q-learning 是将动作的选择和动作的评估分别用不同的值函数来实现。那么，什么是动作的选择？什么是动作的评估？我们做些简要的说明。

• 动作选择 在Q-learning的值函数更新中，TD目标为

$$Y_t^Q=R_{t+1}+\gamma \underset{a}{max}Q(S_{t+1},a;\theta_t)$$

在求TD目标 $Y_t^Q$ 的时候，我们首先需要选择一个动作即 $a^*$ ，该动作 $a^*$ 应该满足在状态 $S_{t+1}$ 处 $Q(S_{t+1},a)$ 最大，这就是动作选择。

• 动作评估 动作评估是指选出 $a^*$ 后，利用 $a^*$ 处的动作值函数构造TD目标。一般Q-learning利用同一个参数 $\theta_t$ 来选择和评估动作。Double Q-learning分别用不同的行为值函数选择和评估动作。Double Q-learning的TD目标公式为

  $$Y_t^{DoubleQ}=R_{t+1}+\gamma Q\left[S_{t+1},\underset{a}{argmax}Q(S_{t+1},a;\theta_t);\theta_t'\right]$$

• 从该公式我们看到，动作的选择所用的动作值函数为 $\underset{a}{argmax}Q(S_{t+1},a;\theta_t)$ ，这时动作值函数网络的参数为 $\theta_t$ 。当选出最大的动作 $a^*$ 后，动作评估的公式为：

  $$Y_t^{DoubleQ}=R_{t+1}+\gamma Q(S_{t+1},a^*;\theta_t')$$

• 动作评估所用的动作值函数网络参数为 $\theta_t'$ 。将Double Q-learning的思想应用到DQN中，则得到Double DQN即DDQN，其TD目标为

  $$Y_t^{DoubleQ}=R_{t+1}+\gamma Q\left[S_{t+1},\underset{a}{argmax}Q(S_{t+1},a;\theta_t^-)\right]$$

参考：

on policy和off policy的优劣之分：https://www.zhihu.com/question/56561878/answer/149892732

强化学习的数学符号：https://www.jianshu.com/p/a7ed0c301ff2