强化学习从根底到进阶 - 常见问题和面试必知必答 [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(s_t,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} Q\left(s_{t+1}, a\right)$。
总结起来，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(s_t,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$ 个后续状态直到整个试验完结。
更多优质内容请关注公号：汀丶人工智能