这个笔记是用于记录学习动手强化学习这本书的时候的问题疑惑以及解答，有助于之后用时查阅。

第一章：多臂老虎机问题

1. 上置信算法

背景：在多臂老虎机问题中，在使用贪心算法的时候，如果有已经尝试过很多次的杆子，并且这个杆子的期望还比其他的高，那么就会很大的概率继续选择这个杆子，但是这个只是局部最优值，因为有可能有其他期望更高的杆子因为尝试的次数很少，所以分布不能被很好的表示。所以引用不确定性度量U(a),表示一个动作的确定程度，它会随着一个动作被尝试次数的增加而减小。

在考研概率论中有这样一个公式：

这个公式是用来衡量测量值与实际值之间的分布。

在这里引入另外一个不等式：霍夫丁不等式 X是独立同分布的随机变量，是 $\overline{x}_n$ 是已经观测到的样本均值，n是观测数量

$u$ 是均值。这个公式是用来衡量样本期望和实际期望的分布的

现在我们将霍夫丁不等式运用于多臂老虎机问题中。将 $\check{Q}(a)$ (动作a的奖励)代替 $\overline{x}_n$ ，让参数 $u=\check{U}_t(a)$

$n=N_t(a)$ ， $E(x)=Q_t(a)$ 表示a这个动作执行了的次数，公式转化为如下：

$\begin{align} P \{Q_t(a) \geq \check{Q}(a)+\check{U}_t(a)\}\leq e^{-2N_t(a)\check{U}_t^2(a)} \end{align}$

现在令 $e^{-2N_t(a)\check{U}_t^2(a)}=p$ 当 $\check{U}_t^2(a)$ 值变小时，p的值会变大，因此1-p则会变的小。然后对上面的式子进行基础变形得到：

$P \{Q_t(a)- \check{Q}(a) < \check{U}_t(a)\}> 1-p$

因为 $\check{U}_t(a)$ 会随着a的动作进行的次数增加而减少，所以可以理解为随着次数的增加，观察到的期望和实际的期望会越来越接近，即探测到了分布越真实。那么怎么鼓励多探测到其他的分布呢？当 $\check{U}_t(a)$ 减小的时候1-p则就会减小，这样的话继续使用该分布的概率就会降低，从而促进多探测其他的分布。这其实也解释了不确定性分布这个名字的含义：这个值越大，表明这个分布探测的越不确定，反之则越确定。

再将上面的式子进行变形得到：

$P \{Q_t(a) < \check{U}_t(a)+\check{Q}(a)\}> 1-p$

此处的 $\check{U}_t(a)+\check{Q}(a)$ 就是奖励上界，在多头老虎机问题中，拉动每根拉杆的期望奖励只有一个较小的概率p超过这个上界。那么怎么鼓励多探测到其他的拉杆呢？ $\check{U}_t(a)$ 会随着莫一个拉杆增加的次数而减小，但是并不完全意味着奖励上界会减小，因为 $\check{Q}(a)$ 可能会随着次数的上涨而更加准确（比如，一个拉杆的奖励期望为0.8，但是前4次都是0，此时 $\check{Q}(a)$ 为0 如果继续尝试这个拉杆之后大概率会使 $\check{Q}(a)$ 有所提升），但是如果一个拉杆已经探测了很多次了，这个时候 $\check{Q}(a)$ 会趋向于一个稳定的值，那么继续尝试这个杠杆会使 $\check{U}_t(a)+\check{Q}(a)$ 有所下降。这样就有助于多去尝试其他的拉杆。所以每次著需要选择 $\check{U}_t(a)+\check{Q}(a)$ 值最大的拉杆就能达到这一个效果。

然后将p设置为1/t（t为到此时所有拉杆尝试的总次数），为什么要这样设置呢？为了让置信区间宽度随时间 t 缓慢缩小由上面的式子可以看出当p越小时 $Q_t(a)$ 的置信区间也会越小，从而保证在长期运行中既能覆盖真实均值，又能逐渐减少不必要的探索，最终达到近似最优的“探索-利用”平衡。然后解出来下列公式：

同时，我们设定一个系数c来控制不确定性的比重，此时每次只需要这样选择a即可.

第二章：马尔可夫决策

1.马尔可夫决策：

首先明确强化学习所需要的东西，由下图所示：强化学习需要状态 $S_t$ ，奖励 $R_t$ ，动作 $A_t$ ,环境MDP。

现在先考虑没有动作的马尔可夫决策，其中状态为 $S$ 组成，奖励 $r(s)$ 表示转移到状态s的奖励，例如下图中从S1->S2的奖励为-2.环境MDP为状态之间的转换路径以及其概率，使用 $P$ 表示状态矩阵。

7845c3baf772f51a2af468d290029fc1

现在已经有了强化学习所需要的状态和环境了，此时奖励 $r(s)$ 不等于强化学习所需要的奖励 $R_t$ ，因为 $S(t)$ 仅仅只表示转移到状态s的奖励，并不能表示实际的奖励期望，因为奖励 $R_t$ 往往不仅仅只考虑下一步的奖励，还考虑之后的步骤。在一个马尔可夫奖励过程中，从第时刻状态开始，直到终止状态时，所有奖励的衰减之和称为回报 $G_t$ （Return)，公式如下：其中为什么要加上 $R_t$ 本身呢，因为G_t是计算的是其他状态转化到莫个状态的期望，那么理所应当需要把转到的这个状态也加上，所以 $G_t$ 表示的是转到某个状态的奖励。

现在想要获得奖励函数 $R_t$ ，这里奖励可以用每一个状态的期望进行代替，此处可以使用递归树的方式计算，要计算 $V(S_1)$ = $r(S_1)$ + $r(0.1*V(S_2)+0.9*V(S_1))$ 然后 $V(S_2)$ 也可以像这样继续展开，写成笼统的公式为：

也可以写成：

然后根据这个式子可以得到解析解：

此时就能得到每一个节点的奖励，其中表示如果转到这个节点的话的期望奖励。

上面的马尔可夫决策没有加入强化学习所需要的动作，现在将动作也加入到这一个过程中，同时奖励也将发生改变。下图是一个具体的例子：

8e7bf0addda01cb63a517f2c63c69389

某一个状态可能对应着几个不同的动作，具体选择哪个动作，这个在深度学习中是交给Agent做的，当Agent做出了一个动作之后，状态的改变可能也不是固定的，也可以以不同的概率转到不同的状态，例如上图概率前往的动作，并不只会转到某一个特定的状态中，而是分别以0.2，0.4，0.4的概率转到 $S_2,S_3,S_4$ .

那么在状态 $s$ 执行完某一个动作 $a$ 的奖励值应该为：

例如概率前往这个动作的奖励期望就是： $1+r(0.2*V(S_2)+0.4*V(S_3)+0.4*V(S_4))$

其中的 $V(s)$ 和没有加入动作时的计算方式并不一样，计算公式为：

这里不同于没有添加动作（MRP）的有所区别，为了使用MRP的解析解，需要做一下的处理：

这两个将动作给边缘化，通俗来说就是提前计算所有动作的可能性，将之添加到奖励中和环境中。

2.占用量

不同的策略产生的路径可能会不同，因此动作和状态的访问会有所不同，比如有的策略会偏向于执行某一个策略或者跳转到某一个状态，为了评估每一个状态和动作的使用度量，给出状态访问分布和占用度量的公式：

状态访问分布：表示的是每一个状态被访问次数的分布，例如： $v^\pi(s_1)=0.5$ 表示在策略 π 下，从长远来看，智能体大约有 50% 的折扣加权访问时间 在状态 $S_1$ 。

其中 $P_t^\pi(s)$ 表示在示采取策略 $\pi$ 使得智能体在t时刻状态s为的概率。

占用度量：表示的是每一个动作-状态被访问次数的分布

并且这两个可以进行相互转化：

第三章：时序差分算法

1.无模型强化学习

有模型强化学习是知道与agent交互的环境的，并且知道执行动作的奖励和状态转移函数的例如：

无模型的强化学习算法不需要事先知道环境的奖励函数和状态转移函数，但是仍然知道每个状态下可以选择的所有动作，具体选择哪个动作由策略决定。这样更加符合实际情况。如下图所示：

2.时序差分方法

这个方法是为了在无模型强化学习中计算每个状态的价值估计，使用到了蒙特卡洛和动态规划，其中通过多次经过同一个状态然后再估计价值是使用了蒙特卡洛的估计方式，将问题分成子问题运用到动态规划。

具体更新的公式为：这里使用的是增量式更新（即每一次都能直接更新状态的价值，不用使用一个值记录总价值然后等遍历完再计算平均值。）然后 $\alpha$ 表示更新步长，有点类似于学习率。

公式中的 $V(S_{t+1})$ 表示下一个状态的估计价值，那么既然不知道动作前往的下一个动作是什么，怎么知道下一个状态是什么呢？

通过于环境交互，在某一个状态的时候可以根据当前的策略选择某一个动作，然后执行这个动作，然后环境给的反馈值，同理，环境也会给出奖励值，所以每次要更新一个节点，需要执行完下一个动作才能进行更新。

通过大量样本的学习之后，就能得到每个状态的估计价值。但是想要得到具体的最优策略的话，只使用每个状态的价值并不够，因为无模型中不知道状态转移函数，不能够通过下列函数计算出动作的价值：

没有动作的价值函数就很难根据贪婪策略得到具体的策略，所以引出Sarsa算法估算动作的价值函数。

3.Sarsa

类似于上面的计算状态价值，通过与环境交互获得下一个状态是什么，以及获得的奖励来更新自己的状态，动作的价值也可以使用同样的时序差分进行估算。

执行完一个动作 $Q(S_t,a_t)$ 之后，环境会给出奖励 $r_t$ 和下一个状态 $S_{t+1}$ 然后在 $S_{t+1}$ 根据 $\epsilon-$ 贪婪策略会选出下一个动作 $a_{t+1}$ 然后就能得 $Q(s_{t+1},a_{t+1})$ 。这里直接使用 $r_t,Q(s_{t+1},a_{t+1})$ 来表示当前时间步动作的价值估计，其中 $r_t$ 是环境给出的准确值，但是 $Q(s_{t+1},a_{t+1})$ 也是一个估计值，使用估计值来估计值可能会造成收敛很慢，这个时候可以想到，多使用准确值不就能提高估计准确度嘛，所以引出多步Sarsa。

上面的每次只使用一步真实值，多步Sarsa使用多步的真实值，具体而言就是：

考虑了多步的奖励，使得收敛速度更加快。

单步的结果图：

多步的结果图：

4.Q-learning算法

Q-learning算法和Sarsa算法一样都是来估算动作的价值函数的，只不过更新函数不一样，Q-learning函数的更新方式为：

其中下一个状态 $S_{t+1}$ 的动作并不由 $\epsilon-$ 贪婪策略选出，这是和Sarsa的区别。

Q-learning的执行过程为:

其中只是在更新时用到了，但是在实际的选择动作往下进行的时候仍然是使用 $\epsilon-$ 贪婪策略。举一个具体的例子，此时要更新 $Q(S_1,a_1)$ ，首先要根据 $\epsilon-$ 贪婪策略在状态 $S_1$ 选出 $a_1$ ,然后执行这个动作得到奖励 $r$ 和下一个状态 $s_2$ ，然后找到 $s_2$ 状态下所有能执行的动作中价值最高的那一个按照上面公式尽心更新 $Q(s_1,a_1)$ ,这个是和Saras的区别。更新完之后转到状态 $s_2$ 然后再根据 $\epsilon-$ 贪婪策略选出动作（此处并没有选择动作中价值最高的执行，所以只有在更新价值的时候才会选择价值最高的动作，实际执行的时候仍然使用的是 $\epsilon-$ 贪婪策略)。

因为价值的更新和策略并不一样，所以动作的价值逼近的值并不是原有策略的动作价值。Q-learning算法学习到的是最优策略下的动作价值。这样的算法称作离线策略，表示行为策略和目标策略不是同一个策略。

Sarsa学习到的是当前执行的策略，这样的策略称作在线策略表示行为策略和目标策略是同一个策略。

上图是Sarsa和Q-learning算法的比较，离线学习算法有一个优势是可以重复利用过往的训练样本，为什么呢？

首先解释一下训练样本是什么，一个旧样本，也可以称之为经验，可能是由**(s,a,r,s′,a′)**这个几个部分组成的，分别为当前状态s，当前动作a，以及动作a产生的价值r，和下一个动作s’，和下一个动作a’。

在书中第一章中详细介绍了 $\epsilon-$ 贪婪策略，其中的 $\epsilon$ 并不是一直不变的，随着对各个动作的奖励估计越来越准确， $\epsilon$ 的值是会减小的以达到获取更大的奖励。现在解释为什么Sarsa不能重复使用训练样本，假设一开始 $\epsilon$ 为0.1，此时采样了100条经验，随后 $\epsilon$ 会逐渐减小到0.05，这个如果重复使用前面的100条经验就会出现错误，因为Sarsa属于在线策略，动作的价值必须逼近的是当前的策略下的价值，也就是当 $\epsilon=0.05$ 的时候使用 $\epsilon=0.1$ 的经验的话，动作价值函数会逼近 $\epsilon=0.1$ 的动作价值，这就违背了初衷。

那为什么Q-learning可以重复利用呢，因为行为策略和目标策略不是同一个策略。意味着无论用 $\epsilon=0.05$ 下产生的经验还是 $\epsilon=0.1$ 下产生的经验，动作价值都是逼近最优的策略的价值，与使用的经验分布并没有关系，只要经验是在同一个环境下产生的就能很好的训练动作价值函数。

第四章：DQN算法

1.DQN算法

前面的算法都是使用的是离散的状态和动作，无法对于连续的状态进行处理，所以这里引入DQN算法，DQN算法能够在连续的状态和离散的动作下估算动作的价值Q。

前面的算法都是使用一个矩阵来表示所有动作的Q值，但是到连续的情况下并不能够很好的表示出所有的Q值，所以需要使用函数估计Q值，将连续的状态做为输入，输出为动作的Q值，这里估计函数的方法可以使用神经网络来实现，设计神经网络的方式有两种：1.输入为状态和动作，输出的为该动作的价值。2.输入为状态，输出所有动作的价值，例如：

此处使用的是上述的方式2，获得了所有动作的Q值之后就可以根据输出的Q值大小进行选择对应的动作。

其中的计算过程为：先根据当前状态 $s$ 经过神经网络得到 $Q(s,a)$ 然后执行动作 $a$ ,之后得到环境返回的 $s'$ ,然后再将状态 $s'$ 送入神经网络中得到 $Q(s',a')$ 。所以说更新一次参数需要经过两次神经网络。

但是现在有一个问题，这个神经网络的作用是让 $Q(s,a)$ 逼近于 $r+\gamma \max _{a'} Q_w(s',a')$ 但是从上面得知$ Q_w(s’,a’)$并不是一个固定的值，而是一个经过神经网络之后的出来的值，随着神经网络参数的改变，这个值是会变动的。这个问题就好像追一个不断移动的靶子，这样势必会很难。这会导致神经网络训练的不稳定性。

怎么解决这个问题呢？将靶子暂时固定就好了。将要逼近的目标 $\gamma \max _{a'} Q_w(s',a')$ 暂时固定下来，具体来说就是复制一个同样神经网络，参数为 $w'$ ,将之叫做目标网络。在训练的时候先不不改变 $\gamma \max _{a'} Q_{w'}(s',a')$ 中神经网络的参数,这样在一定的时间内，只要 $s'$ 相同，神经网络输出的动作价值也一样，这样就实现了将靶子固定住。让后只需要将靶子隔一段时间移动到一个更好的位置就能很好的训练，具体就是将$w’= w $,然后继续训练直到网络稳定。

对于原来的训练网络，将 $r+ \gamma \max _{a'} Q_w(s',a')$ 作为训练的目标，每次按照正常的训练步骤训练网络就可以，loss函数整体写成：其中同使用了两个神经网络计算loss。

$loss=1/2[Q_w(s,a)-(r+\gamma \max _{a'} Q_{w'}(s',a'))]$

动手强化学习笔记