RL

磨菇书

西湖大学GitHub

基本概念

一、数学知识

1）随机变量（Random Variable）

统计学中往往用字母的大小写来区分随机变量和观测值，例如X表示随机变量，x表示观测值

2）概率密度函数(Probability Density Function)

概率密度函数(Probability Density Function)有这样的性质：

3）期望（Expectation）

简单来说，对某一随机变量求期望就是在求它的平均。有微积分基础的可以理解：对于连续的随机变量可以采用求某一段积分来获得期望；而对于离散的随机变量只需求和公式即可。

期望（Expectation）有如下性质：

4）随机抽样（Random Sampling）

举个例子，对于某一随机变量X，可能X产生的值有['R', 'G', 'B']，那么随机抽样的过程就是在X可能产生的值['R', 'G', 'B']抽取的过程

二、专业术语（Terminology）

1）状态和动作（State and Action）

状态（State s）

Agent（智能体）在某一时刻t所处的状态，即为State s，常常记为$s_t$

动作（Action a）

Agent（智能体）在某一时刻t进入状态，做出相应的动作，即为Action a ，常常即为$a_t$

2）策略（Policy $\pi$）

在数学上，策略是一个概率密度函数(Probability Density Function)，在某一状态时，策略控制Agent做出动作，这里做出的动作是随机抽样得到的。

3）奖励（Reward）

Agent在某一状态中做出一个动作，就会获得一个奖励

4）状态转移（State Transition）

一个状态转移到另一个状态的过程叫做状态转移

5）智能体环境交互过程

6）强化学习中的两种随机性

策略对动作进行随机抽样，状态转移函数对状态进行随机抽样

7）强化学习的训练过程（一个trajectory）

8）回报（Return）

定义为：未来奖励的总和（Cumulative Future Reward），记作$U_t$，由于每一步我们并不知道$U_t$的大小，$U_t$因此是随机变量

由于未来奖励的不确定性，因此强化学习中往往采用折扣回报

定义为：折扣性未来奖励的总和（Cumulative Discounted Future Reward）

回报的随机性（Randomness in Returns）

由于回报取决于奖励，而奖励又是由Agent所进入的状态和做出的动作进行打分而得到的，上文已经提到了在强化学习中状态和动作均具有随机性，因此回报（Return）也具有随机性。

9）动作价值函数（Action-Value Function）

上面讲到了，$U_t$是一个随机变量，依赖于未来所有的动作A和状态S，因此为了无法评估当前形势。故引入动作价值函数，用对$U_t$求期望，用积分将随机性积掉，这样就能得到一个实数，用于评估形势。

期望的求取方法：将$U_t$当成未来所有状态A和S的一个函数，所以除了当前的动作$a_t$和状态$s_t$，其余所有的状态和动作都被积掉了，因此这里的对于策略$\pi$的动作价值函数$Q_{\pi }(s_t，a_t)$只取决于当前的动作$a_t$和状态$s_t$的观测值

最优动作价值函数（Optimal Action-Value Function）：能让动作价值函数$Q_{\pi }(s_t，a_t)$最大化的那个

$Q^{\ast }(s_t，a_t)$,这里与$\pi$无关

对于动作状态价值函数的理解

10）状态价值函数（State-Value Function）

$V_{\pi }(s_t)$可以告诉我们当前的形势的好坏

这里的$V_{\pi }$需要区分连续动作和离散动作：

对于状态价值函数的理解：

三、如何利用AI的强化学习控制智能体训练

1）价值学习（Value-Based Learning）

采用最优动作价值函数$Q^{\ast }(s,a)$

2）策略学习（Policy-Based Learning）

采用策略$\pi (a|s)$

四、总结（summary）

直接附上王树森大神的Summary的图：

强化学习的一个总体过程：

价值学习 Value-Based Learning

一、深度Q网络（Deep Q-Network DQN）

1）近似Q函数（Approximate the Q* Function）

$Q^{\ast }(s,a)$可以被看成一个先知，它可以告诉Agent如何选择一个最好的动作a，但$Q^{\ast }(s,a)$并不知道，因此这里需要近似$Q^{\ast }(s,a)$

DQN是一种价值学习的方法，利用一个神经网络（Neural Network NN）去近似一个$Q^{\ast }(s,a)$，记为$Q(s,a;w)$

对于不同问题，DQN也许不一样，以超级玛丽为例：

DQN的训练Agent的一个trajectory如下图：

2）时序差分方法（Temporal Difference Learning TD-Learning）

重要 重要 非常重要

例子：如果我想要从纽约到亚特兰大，且模型$Q(w)$预测了消耗的时间是1000分钟，这个模型一开始是随机的。

那么如何更新模型，使模型的预测值变得越来越准确？

①首先做出一个预测：q=Q(w) → q=1000

②完成这段路程得到真实值y：y=860

这时，产生了一个偏差（q-y）

我们记损失Loss为：$L=1/2(q-y{)}^2$，即L2范式，前面的1/2可以理解为方便计算梯度，线性变换并不会影响数据整体的相对值，例如，1相对于2是1/2倍的关系，0.5相对于1是1/2倍的关系。

那么，为了是预测值尽可能的逼近真实值，我们必须需要让Loss取到最小值。因此这里就引入了L对w的梯度Gradient，也可以认为是求导。使用偏微分的链式法则，我们可以推导出L对w梯度的表达式，如下图所示：

这样，我们在进行参数更新时，采用梯度下降算法（Gradient Descent）即可使参数w不断接近真实值对应的参数$w^{\ast }$。

而现在，若到达不了目的地，不获取到真实的全路程的真实值，就可以利用TD算法来更新模型参数。

假设我们从纽约想亚特兰大出发，途中经过华盛顿，而在华盛顿停住不走，那么此时的预测就不再能使用整条路的真实值来更新预测值了。

因此，这里采用TD算法

我们已知模型做出一个预测：q=Q(w) → q=1000

而从我们从纽约经过华盛顿停住不走，那么便有一个从纽约到华盛顿的真实值：y1=300

而从华盛顿到亚特兰大有一个模型预测值：q1=Q(w1)→q=600

那么此时我们定义TD target为 y=y1+q1=900,这里的TD target比原本的模型预测值1000更加可靠。

我们记损失Loss为：L=1/2*(q-y)²，定义TD error为δ=q-y=1000-900；此处也可以理解成模型对纽约到华盛顿的预测值为400，而真实值是300，δ=400-300=100

类似地，我们可以得到Loss Function关于w的一个函数，对w求梯度，得到Loss的最小值对应的w用于更新参数（采用梯度下降方法Gradient Descent）

我们必须使TD error尽可能地小，当TD error=0时，那么我们就获得了最优的模型

二、TD Learning+DQN

如何将TD算法用于学习DQN

对于上述例子，我们有了这样的方程

类似地，在深度强化学习中，有如下方程，即是用TD算法学习DQN的方程：

其中，方程左边是DQN在t时刻对状态和动作$(s_t,a_t)$进行的一次估计；等式右边是在t时刻真实观测到的奖励，以及DQN在t+1时刻对于状态和动作$(s_{t+1},a_{t+1})$进行的一次估计。

推导如下：

因此，将TD算法与DQN结合：

等式左边可以认为是模型对于时刻t关于参数w的预测值（Prediction）；右边则是真实值+模型对于时刻t+1关于参数w的预测值，和式记为TD target。

个人理解，这是一个贝尔曼方程，具体可以参照忆臻：马尔科夫决策过程之Bellman Equation（贝尔曼方程）

三、总结（Summary）

TD算法用于学习DQN的一次迭代：

多次进行迭代，最后就可以将TD error逐渐减小；换句话说，模型预测值越来越接近TD target。

策略学习 Policy-Based Learning

一、策略函数近似（Policy Function Approximation）

1）策略函数（Policy Function）

策略函数（Policy Function）$\pi (a|s)$ 是一个概率密度函数，其输入是某个状态s，输出是在该状态下可能产生的动作a的概率值。假设在状态st下，Agent可能做出的动作at可能有n个，那么$\pi (a_t|s_t)$即输出一个n维向量，其元素对应每个可能做出动作at的概率值。有了这n个概率值，Agent就会在这个向量中做一次随机抽样（Random Sampling），并做出随机抽样所得的动作$a_i$

2）策略网络（Policy Network）

策略网络（Policy Network）$\pi (a|s;\theta )$则是使用了神经网络去近似策略函数$\pi (a|s)$，其中$\theta$是神经网络中的一个可训练参数

策略网络（Policy Network）$\pi (a|s;\theta )$有着如下性质：

由于策略网络对于在动作空间A中所有可能取到的a所对应的概率之和必须等于1，因此在策略网络的最后一层必须加上一个Sotmax这个Activation Function。

二、状态价值函数近似（State-Value Function Approximation）

1）状态价值函数（Action-Value Function）

首先回顾上一章的三类函数：

这里注意：式3表示离散动作的期望求法；若为连续动作，则对动作空间中的所有a进行积分。

类比State-Value Function和Approximation State-Value Function，区别在于：将策略$\pi (a|s_t)$换成了策略网络$\pi (a|s_t;\theta )$

V可以评价状态s和策略网络$\pi (a|s_t;\theta )$的好坏。若给定状态s，策略网络越好，那么V的值越大。因此，我们采用V关于$\theta$的随机梯度上升的方法更新参数$\theta$，则有以下定义：$J(\theta )$

这类方法即策略梯度上升的方法，这里我们定义策略梯度（Policy Gradient）是近似状态价值函数$V(s;\theta )$关于$\theta$的梯度。

2）策略梯度（Policy Gradient）

这里放上策略梯度的推导：

这里假设$Q_{\pi }$不依赖于$\theta$，因此能够相当于一个常数提出来。但在实际中，由于$Q_{\pi }$依赖于$\pi$，而$\pi$是由神经网络参数$\theta$所决定的，因此往往$Q_{\pi }$不能被提出。

因此，策略梯度的一种形式可以被写成如下形式：

这里，如果动作a是离散的，那么只需要对a进行连加就可以将策略梯度算出来。

然而实际应用中往往不会用这个公式来计算策略梯度，而是使用蒙特卡洛近似的方法来近似。

这里对蒙特卡洛近似推导：

这里，有必要解释一下，这里利用了log函数的求导性质，有微积分基础的应该没什么问题，如果仅有高中水平的朋友可以自己上手求一下导，正着看或许有点问题，可以反过来推导，如上图紫色字体。

至此，我们证明了这两项是相等的：

这里我们就可以使用蒙特卡洛近似，推导出如下等式：

上面提到了这个推导不严谨，原因是因为$Q_{\pi }$与策略$\pi$有关，因而与神经网络参数$\theta$有关，但事实上，最后的$Q_{\pi }$对$\theta$也求偏导，最后也能得到这个式子。

至此，我们得到了策略梯度的两种等价形式：

对于离散的动作，我们可以采用第一种形式：

由于第一种形式的使用对象的局限性，因而第二种形式比第一种形式更为常用，这里举了连续动作的一种策略梯度的例子：

显然，这里对$g(A,\theta )$关于A求期望就是策略梯度；且$\hat{a}$是根据策略$\pi$中随机抽样得到的，故$g(\hat{a},\theta )$是策略梯度的一个无偏估计。因此，我们就可以利用$g(\hat{a},\theta )$去近似策略梯度，即蒙特卡洛近似（Monte Carlo Approximation）。具体推导可以参考蒙特卡洛近似。

三、使用策略梯度更新策略网络

那么我们如何估计动作价值函数$Q_{\pi }(s_t,a_t)$？

给出了这两种方法：

REINFORCE：必须获取到一个完整的trajectory才能进行一次模型参数的更新，也就是蒙特卡罗方法（MC Method）来估计Q

Actor-Critic（AC）：使用另一个神经网络来近似$Q_{\pi }$

四、总结（Summary）

Actor-Critic Method（AC Method）

Actor-Critic方法，是策略学习和价值学习结合的一种方法。

Actor是策略网络，用来控制Agent运动，可以看做“运动员”。

Critic是价值网络，用来给动作打分，可以看做“裁判”。

一、价值网络和策略网络（Value Network and Policy Network）

首先回顾状态价值函数$V_{\pi }(s)$，它是动作状态函数$Q_{\pi }(s,a)$的数学期望，如果动作是离散的，那么它是由策略函数$\pi (a|s)$作为权重系数，和动作价值函数$Q_{\pi }(s,a)$(可以评价动作的好坏程度)相乘并对a做求和得到。如果动作是连续的，那么就要对a求积分。

**①Policy network（Actor）:**控制Agent运动，即在某一状态s做出动作a

我们利用策略网络$\pi (a|s;\theta )$来近似策略函数$\pi (a|s)$，$\theta$是一个可训练的神经网络参数。

**②Value network（Critic）:**不控制Agent运动，仅给Agent打分

我们利用价值网络$q(s,a;w)$来近似价值函数$Q_{\pi }(s,a)$，w是一个可训练的神经网络参数

1）策略网络（Policy Network）（Actor）

以超级玛丽为例：

该网络有一个输入：状态s

将超级玛丽的一帧画面传输到策略网络中，即输入一个状态s。

价值网络中包含：一个卷积层，将一帧画面变成特征向量；全连接层，将特征向量转变为相对于动作空间（Action Space）中元素个数对应的向量；再采用Softmax激活函数将其转换为求和为1的值，即一策略的概率密度。

2）价值网络（Value Network）（Critic）

以超级玛丽为例：

该网络有两个输入：状态s和动作a

将超级玛丽的一帧画面传输到价值网络中，即输入一个状态s；以及策略网络（Actor）做出的一个动作a传入到价值网络中，即输入一个动作a。对于离散动作而言，这里可以采用独热编码（one-hot encoding），具体可以参考学习笔记 | 独热编码(One-Hot Encoding)，这里不再对独热编码进行过多介绍。

对于两个不同的输入，处理方法如下：

针对于状态s，采用一个卷积层，从输入中提取特征，获得一个状态特征向量

针对于动作a，采用一个全连接层，从输入中提取特征，获得一个动作特征向量

然后将两个特征向量进行拼接，得到一个更高维的特征向量，再通过一个全连接层输出一个实数$q(s,a;w)$，即Critic对于Agent处于状态s下做出动作a的评价。

值得一提的是，价值网络和策略网络中的参数是可以共享的；当然，其中的参数也可以各自独立。

同时训练价值网络和策略网络就是Actor-Critic Method（AC Method）

二、训练神经网络（Train the Neural Network）

因此，我们可以用策略网络和价值网络来近似状态价值函数。

针对于两个网络的参数$\theta$和w，我们的更新方法是不一样的：

对于$\theta$，它是策略网络的参数。我们更新参数$\theta$是为了让状态价值函数$V(s;\theta ,w)$的值增加，$V(s;\theta ,w)$是对策略$\pi$和状态s的评价。如果固定状态s，那么$V(s;\theta ,w)$越大，意味着策略$\pi$越好；同理，如果固定策略$\pi$，$V(s;\theta ,w)$越大，则状态s越好。

对于w，它是价值网络的参数。我们更新参数w是为了让价值网络对于动作的打分更精准，从而更好地估计未来奖励的总和。它相当于是裁判，一开始并没有打分能力，因此在初始阶段，Critic的打分都是瞎猜的，它会通过环境给的奖励Reward来更新w，最后Critic的打分会越来越精准。

利用如下五个步骤来对两个神经网络做一次更新：

1） 使用时序差分算法更新价值网络q（Update Value Network q Using TD）

解释一下，流程大概是这样的：

当我们使用TD算法去更新价值网络q时，要首先获取到Actor给出的t时刻和t+1时刻的状态$s_t$、$s_{t+1}$以及动作at、at+1，此时Critic网络中的参数为wt。因此我们就能得到我们的TD target：$y_t$，有了TD target和t时刻的观测值，即可写出Loss L(w)，且以L2范式形式表示，然后利用梯度下降（Gradient Descent）去更新Critic网络中的参数w，记为wt+1。需要注意的是，Agent并不会做出at+1这个动作，仅仅是用于Critic用于TD算法的参数更新

直接附图：

2）使用策略梯度更新策略网络$\pi$（Update Policy Network $\pi$ Using Policy Gradient）

首先回顾一下策略梯度：

策略梯度是对自定义函数g(A,θ)关于A求期望，由于一个g(A,θ)是对整体的g(A,θ)的一个无偏估计，因此这里用了蒙特卡洛近似。

解释一下，流程大概是这样的：

根据策略$\pi$对动作a进行一次随机抽样，然后针对该动作a进行一次随机梯度上升（Stochastic Gradient Ascent SGA），用于更新$\theta$，记为θt+1。

AC方法的整体流程和对应关系：

3）算法总结（Summary of Algorithm）

直接上图，非常清晰：

值得注意的是，在论文和教科书中，最后一步往往不适用qt，而采用的是TD error $\delta t$。使用$\delta t$叫做基线策略梯度（Policy Gradient with Baseline），其效果更好。好的baseline可以降低方差，使算法收敛更快。

Baseline：任何接近qt的数都可以是baseline，但它不能是$a_t$的函数，即不与$a_t$存在映射关系。

三、总结（Summary）

蒙特卡洛算法 Monte Carlo Algorithms

一、蒙特卡洛树搜索（Monte Carlo Tree Search）

举个例子：人类在下棋的时候，必须多看几步，做出可能的结果

因此蒙特卡洛树搜索的主要思想是：

①首先选取一个动作a（这里选取的是一个相对较好的动作）

②然后观测这个动作a能否致胜

③多次重复这个步骤

④选择最高分数的动作$a^{\ast }$

蒙特卡洛树搜索的每次模拟都包含这四步：

**①选择Selection：**Agent做出一个动作a（这个动作是一个假想的动作，并不会让Agent实际做出动作）

**②拓展Expansion：**对手会根据策略$\pi$做出一个动作，随后状态更新（同样也是一个假想的动作，且动作是由策略网络$\pi (s,a;\theta )$所决定的）

**③评估Evaluation：**价值网络会对这个状态和动作进行打分，记作v。同时，完成一个trajectory后（即完成一次对局）获得的奖励（Reward）记作r。对该动作a进行标记分数$(v+r)/2$

**④更新Backup:**用步骤③中标记动作分数的值来更新动作分数

具体步骤如下：

二、应用一：计算$\pi$（Application 1：Calculating $\pi$）

在开始正式的蒙特卡洛方法开始前，先使用蒙特卡洛方法去计算圆周率$\pi$作为引子。

实际上，我们已经知道了$\pi$≈3.141592653589...但我们能否使用随机数生成器去近似获取圆周率$\pi$呢？

接下来我们使用蒙特卡洛方法去近似生成$\pi$：

给定一个正方形，中心为原点，边长为2。因此其中包含了一个单位圆。学过概率论的朋友会通过古典概型得知：这个概率显然是用圆的面积去除以正方形的面积。

这里假设是在正方形中进行n次随机抽样，那么对于这n次抽样，我们知道它的期望是$P\times n=\pi \times n/4$，这是由于n次独立的随机抽样而得到的。

我们均匀的随机抽样m个点，如果n是一个很大的数，那么m也就越来越接近π*n/4。通过移项，就可以得到$\pi$。

利用大数定律，可以知道当n趋于无穷时，4m/n也趋于$\pi$。

结论如下：

三、应用二：蒲丰投针（Buffon's Needle Problem）

可以参考这篇文章【概率论】蒲丰投针问题，具体不再过多赘述。

四、应用三：阴影面积估计（Area of A Region Estimation）

与应用一类似：在正方形中随机采样n个点，那么就能将落在阴影区域内的期望求出来。我们实际观测到了m个点在这个阴影区域。如果n很大，那么m就近似等于它的期望。通过移项，将阴影区域的面积A2算出来。

五、应用四：求积分（Integration）

蒙特卡洛方法近似求积分在工程上有十分重要的应用，例如对于某个函数f(x)的积分，就可以采用如下的蒙特卡洛方法。

① 一元函数的定积分

② 多元函数的定积分

六、应用五：期望估计（Estimate of Expectation）

非常重要

SARSA算法

一、推导TD Target（Derive TD Target）

首先回顾一下折扣回报（Discounted Return），其中$\gamma$是折扣率

当我们提取出一个$\gamma$，会发现有如下等式，且括号内部的是下一步的折扣回报$(U_t+1)$

由此，我们得到了一个等式，来反映相邻两个回报之间的关系

我们通常认为，奖励$R_t$取决于当前的状态$s_t$，当前的动作at以及下一状态$s_{t+1}$

根据定义，我们可以得到$Q_{\pi }(s_t,a_t)$是回报Ut的条件期望，这里利用上述公式代换掉Ut，那么就可以得到如下式子：

也许会有问题，博主在看的时候也有这个问题。对Ut+1求期望不已经是$Q_{\pi }(S_{t+1},A_{t+1})$了么，但实际上是这样的：$Q_{\pi }(S_{t+1},A_{t+1})$ 是期望，期望是对 $s_{t+2},a_{t+2},s_{t+3},a_{t+3},\cdots$ 这些变量求的，所以 $Q_{\pi }(S_{t+1},A_{t+1})$ 跟这些变量无关。$Q_{\pi }(S_{t+1},A_{t+1})$ 还依赖于变量$S_{t+1},A_{t+1}$。$E[Q_{\pi }(S_{t+1},A_{t+1})]$ 进一步消掉 $S_{t+1},A_{t+1}$ 这两个变量。

因此我们可以得到这样的等式：

近似方法如下：

因此，TD learning就是让$Q_{\pi }(s_t,a_t)$不断接近我们的TD target $y_t$

二、表格形式的Sarsa（Sarsa：Tabular Version）

如果我们想学习动作价值函数$Q_{\pi }(s,a)$，我们可以使用一个如果输入的状态和动作是有限的，那么我们就可以画一个表格：一行对应一个状态$s_i$，一列对应一个动作$a_j$，那么表中的每个元素则对应着在该状态和该动作下的动作价值$Q_{\pi }(s_i,a_i)$。我们要做的就是用Sarsa算法去更新表格，每次更新一个元素。

当我们观测到一个四元组$(s_t,a_t,r_t,s_{t+1})$，这样的一个四元组被称为transition。然后采用策略函数$\pi$去采样一个$a_{t+1}$，接着计算TD target $y_t$。这里假设$s_{t+1}$为$s_2$，$a_{t+1}$经过采样为$a_3$，那么我们经过查表获取到了对应的$Q_{\pi }(S_{t+1},A_{t+1})$。

同时我们也能计算出TD error δt

然后利用δt更新$Q_{\pi }(s_t,a_t)$，其中α是学习率

三、神经网络形式的Sarsa（Sarsa:Neural Network Version）

我们可以采用价值网络来近似$Q_{\pi }(s,a)$，记为$q(s,a;w)$。注意，动作价值函数$Q_{\pi }$和价值网络q都与策略$\pi$有关，策略$\pi$的好坏会影响这两个函数。

神经网络$q(s,a;w)$被称为价值网络，它的输入是一个状态s，输出是状态s下对应动作的价值。如果有n个动作，那么价值网络q就会输出一个n维向量，向量元素对应在状态s下，各动作a的价值。

TD target，记作$y_t$，是实际观测的奖励rt与折扣价值网络的预测值$\gamma q(S_{t+1},A_{t+1};w)$之和

TD error，记作δt，是价值网络对当前状态和动作的估计$q(s_t,a_t;w)$与TD target之差，我们希望它越小越好

Loss，记作L，以1/2倍δt的L2范式作为Loss，我们希望通过更新价值网络的参数w来减小Loss

Gradient，Loss对w求梯度，利用梯度下降来获取到Loss的局部最小值

Gradient descent，梯度下降算法，用于更新价值网络参数w

四、总结（Summary）

我们采用Sarsa算法主要是用于学习动作价值函数$Q_{\pi }(s,a)$

这里有两种形式：

①表格形式（直接学习$Q_{\pi }$）

这种形式对于有限个状态和动作且数量不大。通过一张表格记录每种状态和动作对应的$Q_{\pi }(s,a)$的值，通过采用TD算法更新表中每个$Q_{\pi }(s,a)$的值。

②神经网络形式（采用函数近似）

这种形式并不是直接获取$Q_{\pi }(s,a)$，而是通过价值网络$q(s,a;w)$来近似动作价值函数$Q_{\pi }(s,a)$。它实际上TD算法来更新价值网络参数w，使价值网络$q(s,a;w)$更好。应用有学习笔记4的AC算法中的Critic网络。

Q-Learning算法

一、Sarsa算法与Q-Learning算法对比

1）Sarsa算法

①Sarsa算法目的是为了训练动作价值函数$Q_{\pi }(s,a)$

②TD Target记作yt，它是当前观测到的奖励rt和动作价值函数对于下一状态和下一动作的预测值乘以折扣因子γ之和

③我们使用Sarsa算法来更新价值网络，即AC算法中的Critic网络。

2）Q-Learning算法

①Q-Learning是用于学习最优动作价值函数$Q^{\ast }(s,a)$

②TD Target记作yt，是当前观测到的奖励rt与价值函数对于下一步状态下最优动作的预测值乘以折扣因子γ之和

③我们用Q-Learning算法来更新DQN

二、推导TD Target（DeriveTD Target）

我们已经知道对于所有的π，已经有了如下的等式：

如果这里的π是最优策略π*，那么就会有如下的等式:

我们往往采用$Q^{\ast }$去替换Q_π*，因此有了如下的等式：

我们推导一下这个式子，由于$Q^{\ast }(S_{t+1},A_{t+1})$是对下一步状态下最优动作的动作价值函数，因此，这里的$A_{t+1}$必然要选择使$Q^{\ast }(S_{t+1},A_{t+1})$最大化的动作$a^{\ast }$，因此有了如下的结论：

代入上面的等式，就可以得到如下等式：

然而，直接求式子中的期望十分困难，因此这里采用蒙特卡洛近似：

将Rt近似为观测到的rt，用观测到的下一状态$s_{t+1}$去近似$S_{t+1}$，因此蒙特卡洛近似后的式子如下：

至此，我们得到了TD Target yt

三、表格形式的Q-Learning（Q-Learning：Tabular Version）

具体步骤如下

①观测到一个四元组$(s_t,a_t,r_t,s_{t+1})$，这里称之为一个transition

②我们在上一节已经推导出TD Target。实际上，这里的Q是一张表格，我们要找到对应的状态$s_{t+1}$并找到最大的动作价值函数$Q(s_{t+1},a^{\ast })$,用于计算TD Target yt。

③接下来，我们计算TD error δt

④最后，我们利用如下公式来更新表格中的Q*(st,at)

四、神经网络形式的Q-Learning（Q-Learning：DQN Version）

我们采用DQN $Q(s,a;w)$来近似最优动作价值函数$Q^{\ast }(s,a)$

DQN采用如下公式来控制Agent，而我们就是帮助DQN来学习到更好的神经网络参数w

具体步骤如下：

①

观测到一个四元组$(s_t,a_t,r_t,s_{t+1})$，这里称之为一个transition

②TD Target yt，与上一小节类似，这里只是将表格中的Q(st+1,a)换成了Q(st+1,a*;w)

③TD error δt类似

④最后，我们采用梯度下降来更新神经网络参数w

五、总结（Summary）

这里要注意Q-Learning与Sarsa的区别：Sarsa算法是学习动作价值函数Qπ；而Q-Learning是学习最优动作价值函数Q*。一个是随机取一个动作$a_{t+1}$，一个是取最大Q的$a_{t+1}$,但其目的都是让Agent获得到更高的分数。

Multi-Step TD Target

一、Sarsa算法与Q-Learning算法（Sarsa versus Q-Learning）

1）Sarsa

①Sarsa算法目的是为了训练动作价值函数$Q_{\pi }(s,a)$

②TD Target记作yt，它是当前观测到的奖励rt和动作价值函数对于下一状态和下一动作的预测值乘以折扣因子γ之和

③我们使用Sarsa算法来更新价值网络，即AC算法中的Critic网络。

2）Q-Learning

①Q-Learning是用于学习最优动作价值函数$Q^{\ast }(s,a)$

②TD Target记作yt，是当前观测到的奖励rt与价值函数对于下一步状态下最优动作的预测值乘以折扣因子γ之和

③我们用Q-Learning算法来更新DQN。

不管是Sarsa还是Q-Learning，它们都只使用一个奖励rt，即只使用一个transition中的奖励rt，下一次使用另个transition来更新动作价值Qπ，这种方式算出来的TD Target叫做One-Step TD Target。

二、多步TD Target（Multi-Step TD Target）

其实，我们可以使用多个奖励，如rt,rt+1，即使用多个transition中的奖励去更新动作价值Qπ，这种方法计算出来的TD Target叫做Multi-Step TD Target，

1）推导多步回报（Derive Mutil-Step Return）

我们已经知道的Ut与Ut+1的关系，然后再进行一次递归，将Ut+1用Ut+2表示，经过多步迭代，因而产生了Ut与Ut+m的关系，这个公式我们就称之为多步回报（Mutil-Step Return）

2）Sarsa算法中的多步TD Target（m-Step TD Target for Sarsa）

①多步TD target

②若$m=1$，即单步TD target，也就是经典的TD算法

需要注意的是，这种单步的TD Target的训练效果往往不如多步的TD Target的训练效果

3）Q-Learning算法中的多步TD Target（m-Step TD Target for Q-Learning）

①多步TD target

②若$m=1$，即单步TD target，也就是经典的TD算法

需要注意的是，这种单步的TD Target的训练效果往往不如多步的TD Target的训练效果

三、单步TD Target与多步TD Target对比（Comparison of One-step TD target and Multi-step TD target）

Multi-Step TD target的表现更好，更接近真实数据，偏差更小，结果也更稳定；而单步是多步的特例。

经验回放 Experience Replay

一、回顾深度Q网络和时序差分算法（Revisiting DQN and TD Learning）

1）Deep Q Network（DQN）

DQN采用价值网络$Q(s,a;w)$来近似最优动作价值函数$Q^{\ast }(s,a)$

2）TD Learning

我们通常使用TD算法来训练DQN，这里我们回顾一下TD算法的步骤：

①Agent在t时刻观测到一个状态st并做出动作at

②Agent与环境交互获得了一个新的状态$s_{t+1}$并且获得了一个奖励rt

③此时，我们得到了TD Target yt

④继而写出TD error δt

我们的目标是让qt接近yt，即使TD error δt尽量的小

因此TD算法就是寻找一个神经网络参数w使损失函数（Loss Function）L(w)尽可能的小

⑤采用梯度下降来使wt不断逼近$w^{\ast }$

$(s_t,a_t,r_t,s_{t+1})$是一个四元组，这是一个transition，可以认为是一条训练数据，传统算法在使用完该训练数据后就把它丢掉，不再使用，这种对于DQN的训练效果并不好。

二、为什么要使用经验回放（Why use the Experience Replay）

其实，关于讨论为什么要使用经验回放，其实就是在讨论不使用经验回放会有什么缺点，以及使用了经验回放有什么有点。

1）缺点一：浪费经验（Shortcoming 1：Watse of Experience）

传统的TD算法每次仅使用一个transition，使用完后就丢掉，不再使用，这会造成浪费

2）缺点二：关联性更新（Shortcoming 2：Correlated Updates）

传统TD算法会按照顺序使用transition$(s_t,a_t,r_t,s_{t+1})$，前后两条transition之间有很强的关联性，即st和$s_{t+1}$非常接近，实验表明这并不利于把DQN训练的很好。

三、经验回放（Experience Replay）

1）回放缓冲区（Replay Buffer）

我们在使用完一个transition时，会把一个transition放入一个队列里，这个队列被称之为回放缓冲区（Replay Buffer），它的容量是一个超参数（Hyper Parameter）n，Replay Buffer可以存储n条transitions。

如果Replay Buffer满了，那么新来的transition会替代老的transition

2）TD算法中经验回放（TD with Experience Replay）

我们通过找到神经网络参数w来最小化损失函数Loss Function。

我们是用随机梯度下降（Stochastic Gradient Descent SGD）来最小化损失函数Loss Function：从buffer中随机抽取一个transition（si,ai,ri,si+1）,然后计算TD error δi，再算出随机梯度（Stochastic Gradient）gi，使用随机梯度下降(SGD)来调整神经网络参数w。

值得一提的是，实践中，通常使用mini-batch SGD,即每次抽取多个transitions，算出多个随机梯度，利用这多个随机梯度的平均来更新神经网络参数w。

3）经验回放的优势（Benefits of Experience Replay）

①打破了经验的相关性

②重复利用过去的经验

四、优先经验回放（Prioritized Experience Replay）

1）基础思想（Basic Idea）

对于Agent而言，并不是所有的transition都是同等重要的。例如在超级玛丽游戏中，左侧的普通关卡和右侧的boss关卡，它们的重要性就不一样：普通关卡很常见，而boss关卡需要通过很多普通关卡后才能进行。因此，我们必须让Agent珍惜数量更少的boss关卡，即让Agent充分利用boss关卡的这一经验。

实际训练中，我们怎么样让Agent知道哪个transition是重要的呢？

可以使用TD error的L1范式，即|δt|来判断它的重要。|δt|越大，就说明transition就越重要，应该给这个transition更高的优先级。

解释一下：训练出的DQN对于数量较少的场景不熟悉，所以预测就会偏离TD Target，因此产生的TD error就比较大，即|δt|就大。正因为DQN不熟悉数量较少的场景，所以要让DQN给这些场景更高的优先级，让它更好的应对这样的场景。

2）核心想法（Core Idea）

优先经验回放（Prioritized Experience Replay）的核心在于：使用非均匀抽样代替均匀抽样。这里有两种抽样方式：

①抽样概率pt正比于|δt|+ε

其中，ε是一个很小的数，避免抽样概率pt等于0

②对|δt|排序

|δt|越大越靠前，|δt|越小越靠后

两种方法的原理都是一样的：|δt|越大，就抽样概率pt就越大。

3）调整学习率（Scaling Learning Rate）

TD算法采用SGD来更新神经网络参数w，α是学习率。

如果做均匀抽样，那么所有的transitions的学习率α都相同；如果做非均匀抽样，那么就要根据每个transition的重要性来调整学习率。

如果一个transition有一个较大的抽样概率pt，那么对这个transition的学习率就应该调小，可以采用如下圈出的方法来自适应调整学习率的因子：如果pt很大，那么学习率就会变小

4）更新TD Error（Update TD Error）

为了做优先经验回放（PER），我们要对每一个transition标记上TD error δt。δt决定了这条transition的重要性，决定了它被抽样的概率。

如果一个transition刚刚被收集到，我们并不知道它的δt，那么我们就直接把它的δt设置为最大值，让它有最高的优先级。

每次从buffer中抽取一个transition，都要对它的δt进行一次更新

五、总结（Summary）

相比于传统的经验回放（ER），优先经验回放（PER）在每个transition中标注了δt，并根据δt的不同来确定不同的抽样概率和学习率，从而达到非均匀抽样的效果。