【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.免模型学习
在现实的强化学习任务中，环境的转移概率、奖赏函数往往很难得知，甚至很难知道环境中一共有多少状态。若学习算法不依赖于环境建模，则称为“免模型学习”（model-free learning），这比有模型学习要困难得多。
2.蒙特卡罗强化学习
在免模型情形下，策略迭代算法首先遇到的问题是策略无法评估，这是由于模型未知而导致无法做全概率展开。此时，只能通过在环境中执行选择的动作，来观察转移的状态和得到的奖赏。受K摇臂赌博机的启发，一种直接的策略评估替代方法是多次“采样”，然后求取平均累积奖赏来作为期望累积奖赏的近似，这称为蒙特卡罗强化学习。由于采样必须为有限次数，因此该方法更适合于使用$T$步累积奖赏的强化学习任务。
另一方面，策略迭代算法估计的是状态值函数$V$，而最终的策略是通过状态-动作值函数$Q$来获得。当模型已知时，从$V$到$Q$有很简单的转换方法（个人注解：参见这里的式(6)），而当模型未知时，这也会出现困难。于是，我们将估计对象从$V$转变为$Q$，即估计每一对“状态-动作”的值函数。
此外，在模型未知的情形下，机器只能是从一个起始状态（或起始状态集合）开始探索环境，而策略迭代算法由于需对每个状态分别进行估计，因此在这种情形下无法实现。例如探索种瓜的过程只能从播下种子开始，而不能任意选择种植过程中的一个状态开始。因此，我们只能在探索的过程中逐渐发现各个状态并估计各状态-动作对的值函数。
综合起来，在模型未知的情形下，我们从起始状态出发，使用某种策略进行采样，执行该策略$T$步并获得轨迹：
\[<x_0,a_0,r_1,x_1,a_1,r_2,...,x_{T-1},a_{T-1},r_T,x_T>\]然后，对轨迹中出现的每一对状态-动作，记录其后的奖赏之和，作为该状态-动作对的一次累积奖赏采样值。多次采样得到多条轨迹后，将每个状态-动作对的累积奖赏采样值进行平均，即得到状态-动作值函数的估计。
可以看出，欲较好地获得值函数的估计，就需要多条不同的采样轨迹。然而，我们的策略有可能是确定性的，即对于某个状态只会输出一个动作，若使用这样的策略进行采样，则只能得到多条相同的轨迹。这与K摇臂赌博机的“仅利用”法面临相同的问题，因此可借鉴探索与利用折中的办法，例如使用$\epsilon$-贪心法，以$\epsilon$的概率从所有动作中均匀随机选取一个，以$1-\epsilon$的概率选取当前最优动作。我们将确定性的策略$\pi$称为“原始策略”，在原始策略上使用$\epsilon$-贪心法的策略记为：
\[\pi ^{\epsilon} (x) = \begin{cases} \pi (x), & \text{以概率$1-\epsilon$}; \\ \text{$A$中以均匀概率选取的动作}, & \text{以概率$\epsilon$}. \end{cases} \tag{1}\]对于最大化值函数的原始策略$\pi = \text{arg max}_a Q(x,a)$，其$\epsilon$-贪心策略$\pi ^{\epsilon}$中，当前最优动作被选中的概率是$1 - \epsilon + \frac{\epsilon}{\lvert A \rvert}$，而每个非最优动作被选中的概率是$\frac{\epsilon}{\lvert A \rvert}$。于是，每个动作都有可能被选取，而多次采样将会产生不同的采样轨迹。
假定只有一个最优动作。
个人注解：蒙特卡罗方法只能等整个策略执行完后，才能知道最终奖励。该方法一开始也不知道哪个动作是最优的，需要在多次尝试后，根据已经收集到的奖励数据，估计出来一个当前最优的动作。假设有“上”、“下”、“左”、“右”四个动作可以选择，$\epsilon = 0.1$，假设“右”是最优动作，根据式(1)的第一个式子，有$1-0.1=0.9$的概率选择最优动作“右”，此外，根据式(1)的第二个式子，还有0.1的概率从“上”、“下”、“左”、“右”中任选一个，此时每个动作被选到的概率就是$\frac{0.1}{4}=0.025$，那么综合起来，动作“右”被选到的概率就是$1 - \epsilon + \frac{\epsilon}{\lvert A \rvert} = 0.9 + 0.025 = 0.925$，剩余三个动作被选到的概率均为$\frac{\epsilon}{\lvert A \rvert} = 0.025$。
与策略迭代算法类似，使用蒙特卡罗方法进行策略评估后，同样要对策略进行改进。前面在讨论策略改进时利用了此处式(12)揭示的单调性，通过换入当前最优动作来改进策略。对于任意原始策略$\pi$，其$\epsilon$-贪心策略$\pi^{\epsilon}$仅是将$\epsilon$的概率均匀分配给所有动作，因此对于最大化值函数的原始策略$\pi ‘$，同样有$Q^{\pi}(x, \pi’ (x)) \geqslant V^{\pi} (x)$，于是此处式(12)仍成立，即可以使用同样方法来进行策略改进。
图16.10给出了上述过程的算法描述，这里被评估与被改进的是同一个策略，因此称为“同策略”（on-policy）蒙特卡罗强化学习算法。算法中奖赏均值采用增量式计算，每采样出一条轨迹，就根据该轨迹涉及的所有“状态-动作”对来对值函数进行更新。
- 第1步：默认均匀概率选取动作。
- 第2步：采样第$s$条轨迹。
- 第4步：对每一个状态-动作对。
- 第5步：计算轨迹中的累积奖赏。
- 第6步：此处式(2)更新平均奖赏。
- 第9步：根据值函数得到策略。
同策略蒙特卡罗强化学习算法最终产生的是$\epsilon$-贪心策略。然而，引入$\epsilon$-贪心是为了便于策略评估，在使用策略时并不需要$\epsilon$-贪心；实际上我们希望改进的是原始（非$\epsilon$-贪心）策略。那么，能否仅在策略评估时引入$\epsilon$-贪心，而在策略改进时却改进原始策略呢？
这其实是可行的。不妨用两个不同的策略$\pi$和$\pi ‘$来产生采样轨迹，两者的区别在于每个“状态-动作对”被采样的概率不同。一般的，函数$f$在概率分布$p$下的期望可表达为：
\[\mathbb{E} [f] = \int _x p(x) f(x) dx \tag{2}\]可通过从概率分布$p$上的采样$\{ x_1,x_2,…,x_m \}$来估计$f$的期望，即：
\[\hat{\mathbb{E}} [f] = \frac{1}{m} \sum_{i=1}^m f(x) \tag{3}\]若引入另一个分布$q$，则函数$f$在概率分布$p$下的期望也可等价地写为：
\[\mathbb{E} [f] = \int _x q(x) \frac{p(x)}{q(x)} f(x) dx \tag{4}\]上式可看作$\frac{p(x)}{q(x)} f(x)$在分布$q$下的期望，因此通过在$q$上的采样$\{ x’_1,x’_2,…,x’_m \}$可估计为：
\[\hat{\mathbb{E}} [f] = \frac{1}{m} \sum_{i=1}^m \frac{p(x_i')}{q(x'_i)} f(x_i') \tag{5}\]这样基于一个分布的采样来估计另一个分布下的期望，称为重要性采样（importance sampling）。
回到我们的问题上来，使用策略$\pi$的采样轨迹来评估策略$\pi$，实际上就是对累积奖赏估计期望：
\[Q(x,a) = \frac{1}{m} \sum_{i=1}^m r_i \tag{6}\]若改用策略$\pi ‘$的采样轨迹来评估策略$\pi$，则仅需对累积奖赏加权，即：
\[Q(x,a) = \frac{1}{m} \sum_{i=1}^m \frac{P_i^{\pi}}{P_i^{\pi '}} r_i \tag{7}\]其中$P_i^{\pi}$和$P_i^{\pi ‘}$分别表示两个策略产生第$i$条轨迹的概率。对于给定的一条轨迹$<x_0,a_0,r_1,…,x_{T-1},a_{T-1},r_T,x_T>$，策略$\pi$产生该轨迹的概率为：
\[P^{\pi} = \prod_{i=0}^{T-1} \pi (x_i,a_i) P_{x_i \to x_{i+1}}^{a_i} \tag{8}\]虽然这里用到了环境的转移概率$P_{x_i \to x_{i+1}}^{a_i}$，但式(5)中实际只需两个策略概率的比值：
\[\frac{P^{\pi}}{P^{\pi '}} = \prod _{i=0}^{T-1} \frac{\pi (x_i,a_i)}{\pi' (x_i ,a_i)} \tag{9}\]若$\pi$为确定性策略而$\pi’$是$\pi$的$\epsilon$-贪心策略，则$\pi (x_i,a_i)$始终为1，$\pi’(x_i,a_i)$为$\frac{\epsilon}{\lvert A \rvert}$或$1-\epsilon+\frac{\epsilon}{\lvert A \rvert}$，于是就能对策略$\pi$进行评估了。图16.11给出了“异策略”（off-policy）蒙特卡罗强化学习算法的描述。
- 第1步：默认均匀概率选取动作。
- 第2步：采样第$s$条轨迹。
- 第4步：重要性采样系数。
- 第6步：计算修正的累积奖赏。参考式(7)和式(9)。
- 第7步：利用这里的式(2)更新平均奖赏。
- 第10步：根据值函数得到策略。图16.10中的第9步和图16.11中的第10步就是同策略蒙特卡罗和异策略蒙特卡罗最核心的区别。
3.时序差分学习
蒙特卡罗强化学习算法通过考虑采样轨迹，克服了模型未知给策略估计造成的困难。此类算法需在完成一个采样轨迹后再更新策略的值估计，而前面介绍的基于动态规划的策略迭代和值迭代算法在每执行一步策略后就进行值函数更新。两者相比，蒙特卡罗强化学习算法的效率低得多，这里的主要问题是蒙特卡罗强化学习算法没有充分利用强化学习任务的MDP结构。时序差分（Temporal Difference，简称TD）学习则结合了动态规划与蒙特卡罗方法的思想，能做到更高效的免模型学习。
蒙特卡罗强化学习算法的本质，是通过多次尝试后求平均来作为期望累积奖赏的近似，但它在求平均时是“批处理式”进行的，即在一个完整的采样轨迹完成后再对所有的状态-动作对进行更新。实际上这个更新过程能增量式进行。对于状态-动作对$(x,a)$，不妨假定基于$t$个采样已估计出值函数$Q_t^{\pi} (x,a) = \frac{1}{t} \sum_{i=1}^t r_i$，则在得到第$t+1$个采样$r_{t+1}$时，类似这里的式(3)，有：
\[Q_{t+1}^{\pi} (x,a) = Q_t^{\pi} (x,a) + \frac{1}{t+1} (r_{t+1} - Q_t^{\pi} (x,a)) \tag{10}\]显然，只需给$Q_t^{\pi} (x,a)$加上增量$\frac{1}{t+1} (r_{t+1} - Q_t^{\pi} (x,a))$即可。更一般的，将$\frac{1}{t+1}$替换为系数$\alpha_{t+1}$，则可将增量项写作$\alpha_{t+1} (r_{t+1} - Q_t^{\pi} (x,a))$。在实践中通常令$\alpha_t$为一个较小的正数值$\alpha$，若将$Q_t^{\pi} (x,a)$展开为每步累积奖赏之和，则可看出系数之和为1，即令$\alpha_t = \alpha$不会影响$Q_t$是累积奖赏之和这一性质（个人注解：系数之和依旧是1）。更新步长$\alpha$越大，则越靠后的累积奖赏越重要。
以$\gamma$折扣累积奖赏为例，利用动态规划方法且考虑到模型未知时使用状态-动作值函数更方便，由这里的式(6)有：
\[\begin{align*} Q^{\pi} (x,a) &= \sum_{x' \in X} P_{x \to x'}^a (R_{x \to x'}^a + \gamma V^{\pi} (x')) \\&= \sum_{x' \in X} P_{x \to x'} ^a (R_{x \to x'}^a + \gamma \sum_{a' \in A} \pi (x',a') Q^{\pi} (x',a')) \end{align*} \tag{11}\]个人注解：策略$\pi$其实就是在每个状态下，按照不同的概率选择动作。$V^{\pi}(x)$是期望奖赏值，不是某一次依据$\pi$采样轨迹得到的奖赏值。
通过增量求和可得：
\[Q_{t+1}^{\pi} (x,a) = Q_{t}^{\pi} (x,a) + \alpha (R_{x \to x'}^a + \gamma Q_t^{\pi} (x',a') - Q_t^{\pi} (x,a)) \tag{12}\]个人注解：这里的$t$不是时间步，而指的是迭代次数，用于优化同一个状态动作对的价值估计。
其中$x’$是前一次在状态$x$执行动作$a$后转移到的状态，$a’$是策略$\pi$在$x’$上选择的动作。
使用式(12)，每执行一步策略就更新一次值函数估计，于是得到图16.12的算法。该算法由于每次更新值函数需知道前一步的状态（state）、前一步的动作（action）、奖赏值（reward）、当前状态（state）、将要执行的动作（action），由此得名为Sarsa算法（将这几个英文单词的首字母连起来）。显然，Sarsa是一个同策略算法，算法中评估（第6行）、执行（第5行）的均为$\epsilon$-贪心策略。
- 第1步：默认均匀概率选取动作。
- 第4步：单步执行策略。
- 第5步：原始策略的$\epsilon$-贪心策略。
- 第6步：式(12)更新值函数。
将Sarsa修改为异策略算法，则得到图16.13描述的Q-学习（Q-learning）算法，该算法评估（第6行）的是$\epsilon$-贪心策略，而执行（第5行）的是原始策略。
- 第1步：默认均匀概率选取动作。
- 第4步：单步执行策略。
- 第5步：原始策略。
- 第6步：式(12)更新值函数。
3.1.Sarsa算法和Q-学习算法的区别
本部分为个人理解。
对于Sarsa算法，假设从状态$x$，执行动作$a$，来到状态$x’$，获得奖励$r$。到达$x’$后，当前策略实际选择了动作$a’$，那么Sarsa使用$r + \gamma Q(x’,a’)$作为更新目标。也就是说，Sarsa会把智能体当前策略中的探索行为也考虑进去。例如当前采用带探索的策略：90%概率选择最优动作；10%概率随机选择动作。那么到达$x’$后，智能体有可能随机选到一个较差的动作。Sarsa会根据这个实际被选中的动作更新。因此Sarsa学习的是：按照当前这套策略，包括其中的随机探索，我最终能获得多少奖励。这叫作同策略学习，on-policy。
对于Q-learning算法，其到达状态$x’$后，虽然实际可能选择了动作$a’$，但更新时并不使用$Q(x’,a’)$。它会查看状态$x’$下所有动作的价值：$Q(x’,a_1),Q(x’,a_2),Q(x’,a_3),…$，然后取最大值：$\underset{a^{‘’}}{\text{max}}Q(x’,a^{‘’})$作为更新目标。也就是说，它认为：虽然我训练时可能因为探索而随机选择了一个较差动作，但在计算当前动作的价值时，我假设未来会选择最优动作。这叫作异策略学习，off-policy。因此，当最终的实际策略仍包含随机探索时，Q-learning估计的回报可能高于实际回报。
举个实际的例子，假设执行动作$a$后，获得奖励$r=2$，到达新状态$x’$，折扣因子$\gamma = 0.9$。在状态$x’$下有三个动作：$Q(x’,a_1)=10, Q(x’,a_2)=6,Q(x’,a_3)=2$。由于当前策略还在探索，这次实际随机选择了$a_3$。对于Sarsa算法，因为实际选择的是$a_3$，所以：$r+\gamma Q(x’,a_3) = 2 + 0.9 \times 2 = 3.8$，Sarsa认为当前动作$a$后续价值只有3.8。对于Q-learning算法，Q-learning不管实际选择的是$a_3$，它直接使用最大的价值：$r + \gamma \underset{a^{‘’}}{\text{max}}Q(x’,a^{‘’}) = 2 + 0.9 \times 10 = 11$，因此Q-learning认为，只要以后选择最优动作$a_1$，当前动作$a$的后续价值就是11。
