强化学习从基础到进阶-常见问题和面试必知必答3：表格型方法：Sarsa、Qlearning；蒙特卡洛策略、时序差分等以及Qlearning项目实战
1.核心词汇
- 概率函数和奖励函数：概率函数定量地表达状态转移的概率，其可以表现环境的随机性。但是实际上，我们经常处于一个未知的环境中，即概率函数和奖励函数是未知的。
- Q表格：其表示形式是表格，其中表格的横轴为动作（智能体的动作），纵轴为环境的状态，每一个坐标点对应某时刻智能体和环境的状态，并通过对应的奖励反馈选择被执行的动作。一般情况下，Q表格是一个已经训练好的表格，不过我们也可以每执行一步，就对Q表格进行更新，然后用下一个状态的Q值来更新当前状态的Q值（即时序差分方法）。
- 时序差分（temporal difference，TD）方法：一种Q函数（Q值）的更新方式，流程是使用下一步的Q值 $Q(s{t 1},a{t 1})$ 来更新当前步的Q值 $Q(st,a_t)$。完整的计算公式如下：$Q(s_t,a_t) leftarrow Q(s_t,a_t) alpha [r{t 1} gamma Q(s{t 1},a{t 1})-Q(s_t,a_t)]$ 。
- Sarsa算法：一种更新前一时刻状态的单步更新的强化学习算法，也是一种同策略学习算法。该算法由于每次更新Q函数时需要知道前一步的状态、动作、奖励以及当前时刻的状态、将要执行的动作，即 $s{t}$、$a{t}$、$r{t 1}$、$s{t 1}$、$a{t 1}$ 这几个值，因此被称为 Sarsa 算法。智能体每进行一次循环，都会用 $s{t}$、$a{t}$、$r{t 1}$、$s{t 1}$、$a{t 1}$ 对前一步的Q值（函数）进行一次更新。
2.常见问题汇总
2.1 构成强化学习的马尔可夫决策过程的四元组有哪些变量？
状态、动作、状态转移概率和奖励，分别对应$(S,A,P,R)$，后面有可能会加上折扣因子构成五元组。
2.2 请通俗地描述强化学习的“学习”流程。
可以将强化学习的“学习”流程类比于人类的学习流程。人类学习就是尝试每一条路，并记录尝试每一条路后的最终结果。在人类尝试的过程中，其实就可以慢慢地了解到哪一条路（对应于强化学习中的状态概念）会更好。我们用价值函数 $V(s)$ 来定量表达该状态的优劣，然后用Q函数来判断在什么状态下做什么动作能够得到最大奖励，在强化学习中我们用Q函数来表示状态-动作值。
2.3 请描述基于Sarsa算法的智能体的学习过程。
对于环境和智能体。两者每交互一次以后，智能体都会向环境输出动作，接着环境会反馈给智能体当前时刻的状态和奖励。那么智能体此时会进行两步操作：
（1）使用已经训练好的Q表格，对应环境反馈的状态和奖励选取对应的动作进行输出。
（2）我们已经拥有了$(s{t}, a{t}, r{t 1}, s{t 1}, a{t 1})$ 这几个值，并直接使用 $a{t 1}$ 更新我们的Q表格。
2.4 Q学习算法和Sarsa算法的区别是什么？
Sarsa算法是Q学习算法的改进（这句话可参考论文 “On-Line Q-Learning Using Connectionist Systems”的摘要部分），详细描述如下。
（1）首先，Q学习是异策略的时序差分学习方法，而 Sarsa 算法是同策略的时序差分学习方法。
（2）其次，Sarsa算法在更新Q表格的时候所用到的 $a'$ 是获取下一个Q值时一定会执行的动作。这个动作有可能是用 $varepsilon$-贪心方法采样出来的，也有可能是 $mathrm{max}_Q$ 对应的动作，甚至是随机动作。
（3）但是Q学习在更新Q表格的时候所用到的Q值 $Q(S',a')$ 对应的动作不一定是下一步会执行的动作，因为下一步实际会执行的动作可能是因为进一步的探索而得到的。Q学习默认的动作不是通过行为策略来选取的，它默认 $a'$ 为最佳策略对应的动作，所以Q学习算法在更新的时候，不需要传入 $a'$ ，即 $a_{t 1}$ 。
（4）更新公式的对比（区别只在目标计算部分）。
Sarsa算法的公式：$r{t 1} gamma Q(s{t 1}, a_{t 1})$ 。
Q学习算法的公式：$r{t 1} gamma underset{a}{max} Qleft(s{t 1}, aright)$ 。
总结起来，Sarsa算法实际上是用固有的策略产生 {$S,A,R,S',A'$} 这一条轨迹，然后使用 $Q(s{t 1},a{t 1})$ 更新原本的Q值 $Q(s_t,a_t)$ 。但是Q学习算法并不需要知道实际上选择的动作，它默认下一个动作就是Q值最大的那个动作。所以Sarsa算法的动作通常会更加“保守胆小”，而对应的Q学习算法的动作会更加“莽撞激进”。
2.5 同策略和异策略的区别是什么？
Sarsa算法就是一个典型的同策略算法，它只用一个 $pi$ ，为了兼顾探索和开发，它在训练的时候会显得有点儿“胆小怕事”。它在解决悬崖寻路问题的时候，会尽可能地远离悬崖边，确保哪怕自己不小心向未知区域探索了一些，也还是处在安全区域内，不至于掉入悬崖中。
Q学习算法是一个比较典型的异策略算法，它有目标策略（target policy），用 $pi$ 来表示。此外还有行为策略（behavior policy），用 $mu$ 来表示。它分离了目标策略与行为策略，使得其可以大胆地用行为策略探索得到的经验轨迹来优化目标策略。这样智能体就更有可能探索到最优的策略。
比较Q学习算法和Sarsa算法的更新公式可以发现，Sarsa算法并没有选取最大值的操作。因此，Q学习算法是非常激进的，其希望每一步都获得最大的奖励；Sarsa算法则相对来说偏保守，会选择一条相对安全的迭代路线。
3.面试必知必答
3.1 友善的面试官：同学，你能否简述同策略和异策略的区别呢？
同策略和异策略的根本区别在于生成样本的策略和参数更新时的策略是否相同。对于同策略，行为策略和要优化的策略是同一策略，更新了策略后，就用该策略的最新版本对数据进行采样；对于异策略，其使用任意行为策略来对数据进行采样，并利用其更新目标策略。例如，Q学习在计算下一状态的预期奖励时使用了最大化操作，直接选择最优动作，而当前策略并不一定能选择到最优的动作，因此这里生成样本的策略和学习时的策略不同，所以Q学习算法是异策略算法；相对应的Sarsa算法则是基于当前的策略直接执行一次动作选择，然后用动作和对应的状态更新当前的策略，因此生成样本的策略和学习时的策略相同，所以Sarsa算法为同策略算法。
3.2 友善的面试官：能否细致地讲一下Q学习算法，最好可以写出其 $Q(s,a)$ 的更新公式。另外，它是同策略还是异策略，原因是什么呢？
Q学习是通过计算最优动作价值函数来求策略的一种时序差分的学习方法，其更新公式为
$$
Q(s, a) leftarrow Q(s, a) alpha r(s,a) gamma max_{a'} Q(s', a') - Q(s, a)
$$
其是异策略的，由于Q更新使用了下一个时刻的最大值，因此其只关心哪个动作使得 $Q(s_{t 1}, a)$ 取得最大值，而实际上到底采取了哪个动作（行为策略），Q学习并不关心。这表明优化策略并没有用到行为策略的数据，所以说它是异策略的。
3.3 友善的面试官：好的，看来你对于Q学习算法很了解，那么能否讲一下与Q学习算法类似的Sarsa算法呢，最好也可以写出其对应的 $Q(s,a)$ 更新公式。另外，它是同策略还是异策略，为什么？
Sarsa算法可以算是Q学习算法的改进，其更新公式为
$$
Q(s, a) leftarrow Q(s, a) alpha r(s,a) gamma Q(s', a') - Q(s, a)
$$
其为同策略的，Sarsa算法必须执行两次动作得到 $(s,a,r,s',a')$ 才可以更新一次；而且 $a'$ 是在特定策略 $pi$ 的指导下执行的动作，因此估计出来的 $Q(s,a)$ 是在该策略 $pi$ 下的Q值，样本生成用的 $pi$ 和估计的 $pi$ 是同一个，因此是同策略。
3.4 友善的面试官：请问基于价值的方法和基于策略的方法的区别是什么？
（1）生成策略上的差异，前者确定，后者随机。基于价值的方法中动作-价值对的估计值最终会收敛（通常是不同的数，可以转化为0～1的概率），因此通常会获得一个确定的策略；基于策略的方法不会收敛到一个确定的值，另外他们会趋向于生成最佳随机策略。如果最佳策略是确定的，那么最优动作对应的值函数的值将远大于次优动作对应的值函数的值，值函数的大小代表概率的大小。
（2）动作空间是否连续，前者离散，后者连续。基于价值的方法，对于连续动作空间问题，虽然可以将动作空间离散化处理，但离散间距的选取不易确定。过大的离散间距会导致算法取不到最优动作，会在最优动作附近徘徊；过小的离散间距会使得动作的维度增大，会和高维度动作空间一样导致维度灾难，影响算法的速度。而基于策略的方法适用于连续的动作空间，在连续的动作空间中，可以不用计算每个动作的概率，而是通过正态分布选择动作。
（3）基于价值的方法，例如Q学习算法，是通过求解最优价值函数而间接地求解最优策略；基于策略的方法，例如REINFORCE等算法直接将策略参数化，通过策略搜索、策略梯度或者进化方法来更新参数以最大化回报。基于价值的方法不易扩展到连续动作空间，并且当同时采用非线性近似、自举等策略时会有收敛问题。策略梯度具有良好的收敛性。
（4）另外，对于价值迭代和策略迭代，策略迭代有两个循环，一个是在策略估计的时候，为了求当前策略的价值函数需要迭代很多次；另一个是外面的大循环，即策略评估、策略提升。价值迭代算法则是一步到位，直接估计最优价值函数，因此没有策略提升环节。
3.5 友善的面试官：请简述一下时序差分方法。
时序差分算法是使用广义策略迭代来更新Q函数的方法，核心是使用自举，即价值函数的更新使用下一个状态的价值函数来估计当前状态的价值。也就是使用下一步的Q值 $Q(s{t 1},a{t 1})$ 来更新当前步的Q值 $Q(s_t,a_t) $。完整的计算公式如下：
$$
Q(st,a_t) leftarrow Q(s_t,a_t) alpha [r{t 1} gamma Q(s{t 1},a{t 1})]
$$
3.6 友善的面试官：请问蒙特卡洛方法和时序差分方法是无偏估计吗？另外谁的方差更大呢？为什么？
蒙特卡洛方法是无偏估计，时序差分方法是有偏估计；蒙特卡洛方法的方差较大，时序差分方法的方差较小，原因在于时序差分方法中使用了自举，实现了基于平滑的效果，导致估计的价值函数的方差更小。
3.7 友善的面试官：能否简单说一下动态规划方法、蒙特卡洛方法和时序差分方法的异同点？
相同点：都用于进行价值函数的描述与更新，并且所有方法都基于对未来事件的展望计算一个回溯值。
不同点：蒙特卡洛方法和时序差分方法属于免模型方法，而动态规划属于有模型方法；时序差分方法和蒙特卡洛方法，因为都是免模型的方法，所以对于后续状态的获知也都是基于试验的方法；时序差分方法和动态规划方法的策略评估，都能基于当前状态的下一步预测情况来得到对于当前状态的价值函数的更新。
另外，时序差分方法不需要等到试验结束后才能进行当前状态的价值函数的计算与更新，而蒙特卡洛方法需要与环境交互，产生一整条马尔可夫链并直到最终状态才能进行更新。时序差分方法和动态规划方法的策略评估不同之处为免模型和有模型，动态规划方法可以凭借已知转移概率推断出后续的状态情况，而时序差分方法借助试验才能知道。
蒙特卡洛方法和时序差分方法的不同在于，蒙特卡洛方法进行了完整的采样来获取长期的回报值，因而在价值估计上会有更小的偏差，但是也正因为收集了完整的信息，所以价值的方差会更大，原因在于其基于试验的采样得到，和真实的分布有差距，不充足的交互导致较大方差。而时序差分方法则相反，因为它只考虑了前一步的回报值，其他都是基于之前的估计值，因而其价值估计相对来说具有偏差大方差小的特点。
三者的联系：对于TD($lambda$)方法，如果 $lambda = 0$ ，那么此时等价于时序差分方法，即只考虑下一个状态；如果 $lambda = 1$ ，等价于蒙特卡洛方法，即考虑 $T-1$ 个后续状态直到整个试验结束。
