1. 强化学习是什么
引用Reinforcement Learning An Introduction中的一句话：
Reinforcement learning is learning what to do—how to map situations to actions—so as to maximize a numerical reward signal.
强化学习是关于做什么，怎样构建从状态到动作的映射，来最大化数值回报信号的学习。
个人总结：强化学习的本质是学习如何做决策，这个决策实际上是状态到动作的映射，它可以最大化数值汇报信号。
最有挑战的情形：动作不仅会影响当前的回报，并且会影响下一状态，通过下一状态影响后续所有的回报。
强化学习最重要最特殊的两个特征：基于试错的探索（trial-and-error search）和延迟回报（delayed reward）
与其他学习范式的比较
与监督学习相比：
监督学习试图从一个具有标签的训练集中学习，这些标签由外部具有一定知识的导师提供。
学习的目标是希望系统能够正确的推广、泛化当前没有仔训练集中观测的数据。
但是在交互式问题中，获取这样满足条件的样本是不现实的：期望正确、具有足够表达能力的行为实例
与非监督学习相比：
非监督学习是找到未标注数据集潜在的结构。
强化学习不等于非监督学习：因为强化学习试图最大化回报信号，而不是找到潜在的数据结构（即使在某些情况下潜在的数据结构在一定方面是有帮助的）
强化学习的构成要素：
- 策略：从当前环境状态到采取动作的一个映射。策略可以表示为$\pi(s,a)$、$\pi(s)$。
- 回报：定义强化学习问题的学习目标。总体来说，回报是环境状态和选择动作的随机函数。
- 值函数：值函数刻画了长期状态下对于某个状态（状态值函数）或某个动作（动作值函数）的偏好。
- 环境模型：像是一个仿真器，给予状态与动作，返回下一个状态与当前回报。
2. 行为值方法
先估计行为值，然后根据行为值选择动作的方法
行为值的定义是某个行为的平均期望回报，因此可以使用采样均值法进行估计。
\[Q_t(a)=\frac{\sum_{i=1}^{t-1}R_i\Bbb I_{A_i=a}}{\sum_{i=1}^{t-1}\Bbb I_{A_i=a}}\tag{2-1}\]公式2-1的分母表示关于动作$a$的所用回报值的和，分子表示动作$a$执行的次数，通过求均值，获取行为值的估计值。
根据定义，先估计行为值，然后根据行为值选择方法，那么下一步，就是根据我们估计的行为值选择方法了。
有两种策略根据行为值函数选择策略：
- 选择具有最高行为值估计的行为
- 以$\epsilon$的概率随机选择动作，以$(1-\epsilon)$的概率选择具有最高行为值估计的行为，即$\epsilon-greedy$方法
第一种策略很好理解，直接利用我们估计的行为值，那么第二种呢？
我们来思考这样一个问题，我们的估计行为值的方法，是在已经存在大量的轨迹（即根据状态选择动作，然后返回回报值）的情况下，根据采样均值得到的。但是在游戏刚开始时，我们的行为值函数并没有估计，或者仅通过前几个轨迹进行行为值的估计是不准确的，按照不准确的行为值选择动作，往往总是选择一个效果不是最优的动作。
因此我们需要一定的探索，因此第二种策略就出来了，在游戏轮数无限大时，每一个动作都会被执行，最终收敛到最优的值函数$q_*(a)$。
3. 增量式评估行为值方法
公式2-1可以改写成：
\[Q_n=\frac{R_1+R_2+\cdots+R_{n-1}}{n-1} \tag{3-1}\]公式3-1表示当前的行为值等于去之前所有的均值。我们可以对公式3-1进一步改写：
\[\begin{align} Q_{n+1}&=\frac{1}{n}\sum_{i=1}^{n}R_i\\ &=\frac{1}{n}(\sum_{i=1}^{n-1}R_i+R_{n})\\ &=\frac{1}{n}((n-1)\frac{1}{n-1}\sum_{i=1}^{n-1}R_i+R_{n})\\ &=\frac{1}{n}((n-1)Q_{n}+R_{n})\\ &=Q_n+\frac{1}{n}(R_n-Q_n) \end{align} \tag{3-2}\]公式3-2即是增量式更新的推导公式，代表着缩小回报值与动作值之间的误差。其中$\frac{1}{n}(R_n-Q_n)$就是增量的内容。
我们将3-2转换成更一般的形式：
\[NewEstimate \leftarrow OldEstimate+SetpSize[Target-OldEstimate] \tag{3-3}\]公式3-3中，对应我们的算法的步长就是动作被选择的次数。Target即是回报，代表动作值的更新方向，与强化学习的目标一致。
但是步长设置成动作被选择的次数真的合理吗？假如强化学习问题是非稳态的（事实上大多数强化学习问题都是非稳态的），也就是说我们要更关注当前的回报，弱化以前的回报。
将上述思想转移到我们的公式3-3中，就是要固定步长为$\alpha$，我们来分析一下为何如此：
\[\begin{align} Q_{n+1}&=Q_n+\alpha[R_n-Q_n]\\ &=\alpha R_n+(1-\alpha)Q_N\\ &=\alpha R_n+(1-\alpha)\alpha R_{n-1}+(1-\alpha)^2Q_{n-1}\\ &=\alpha R_n+(1-\alpha)\alpha R_{n-1}+(1-\alpha)^2R_{n-2}+\ldots+(1-\alpha)^nQ_1\\ &=(1-\alpha)^nQ_1+\sum_{i=1}^n\alpha(1-\alpha)^{n-i}R_i \end{align} \tag{3-4}\]通过公式3-4的推导，可以理解常数下的步长代表着当前动作值是所有回报加权的形式，且$\alpha < 0$，因此距离当前时刻越远，权值越小，即更关注当前的回报，弱化以前的回报。
注意：对于采样均值法（公式2-1，公式3-2），动作值能够收敛；对于常数步长的增量式更新方法，不会收敛，而是不断改变回报均值以适应最近的回报。
4. UCB行为选择方式
在前面，提到了两种根据值函数选择行为的方式，分别是贪婪策略与$\epsilon -greedy$策略。
其中$\epsilon -greedy$能够进行一定的探索，但是它拥有一定的缺点，就是在随机探索时，对于所有的行为都一视同仁，这是不合理的，因为往往我们对待次优的动作肯定要比选择动作值极低的动作更倾向一些。
所以，我们要把次优策略作为我们的探索。
\[A_t=\arg\max_a[Q_t(a)+c\sqrt \frac{\ln t}{N_t(a)}] \tag{4-1}\]公式4-1中，$N_t(a)$表示$t$时刻之前行为a被选择的次数。$c$代表探索的度。最重要的是增加的开方项，他表示对于行为$a$值估计的不确定性度量，因为最终是求max操作，所以叫做upper confidence bound(UCB)方法。上置信区间行为选择。
我们来定性分析一下这个开方项，即不确定性度量：
如果一个动作被选择的次数很小，那么开方项的分母很小，所以整个开方项很大，并且若这个动作的行为值不那么“小”，这个动作就会被选中，进行一定的探索，很合理；如果当前的动作是行为值函数最大的，但是被选择的次数特别多，导致开方项很小，有可能不会被选择，相当于开方项是用来惩罚它的。
这种方法的效果比$\epsilon -greedy$略好，但是不易推广，主要体现在下面两点：
- 非稳态问题带来的挑战
- 状态空间的增大，计算量随之增大
5. 基于优势决策的方法
本文的第2-5小节都是介绍行为值方法相关的，即先估计一个值函数，然后根据值函数选择动作。
实际上，强化学习最终训练的是策略，值函数仅是为了求解策略引入的一种方式，那么有没有其他的方法呢？事实上是有的，它叫做基于优势决策的算法，主要通过判别某个行为相比于其他行为的优势，他和策略梯度方法以及Actor-Critic方法很像，但是还没有那么复杂，本文仅介绍强化学习的基础知识。
-
策略模型
我们引入一个偏好值$H_t(a)$，它代表动作a偏好值的大小，那么我们选择动作，选取偏好值最大的就行：
\[Pr(A_t=a)=\frac{e^{H_t(a)}}{\sum_{b=1}^ke^{H_t(b)}}=\pi_t(a) \tag{5-1}\]
$\pi_t(a)$表示策略，即某个动作的概率。
-
策略更新
通过公式5-1，我们知道最重要的每个动作的偏好值$H_t(a)$，那么我们的策略更新实际上也是动作的偏好值的更新。
对于当前轨迹中被选择的动作：
未被选中的动作：
\(H_{t+1}(a)=H_t(a)+\alpha(R_t-\overline R_t)\pi_t(a)\tag{5-3}\)
我们依旧来定性分析一下公式5-2和公式5-3。先看公式5-2，其中$\overline R_t$是t时刻之前的平均回报（针对某个动作的），相当于一个标准，当我们此时的回报比平均回报高时，说明我们选择的动作是有意义的，因此增加当前动作的偏好值$H_t(a)$；再看公式5-3，假如我们选择的动作高于平均值，说明不选择当前的动作$a$都能获得这么好的结果，那就将偏好值降低些吧~
至于证明是利用梯度上升算法，根据梯度推导出来的，具体的请参考《Reinforcement Learning An Introduction》2.8节。
6. 总结
本文仅针对强化学习做一些基本的介绍，并没有涉及状态，以及当前行为影响后续状态等完全强化学习问题。仅仅是一个入门中的入门讲解，主要参考《Reinforcement Learning An Introduction》一书。
虽然近几年DRL比较火，但是在学习强化学习的过程中，还是从基础入门比较好，不然看paper往往知其然不知其所以然，本文后续仍有更新，会先按照《Reinforcement Learning An Introduction》一书的大概结构进行讲解，然后会对紧近几年比较火的paper进行学习与讲解，如DQN、DDPG等。
