1. Introduction

上一节我们学习了如何使用MC和TD在Model-free的 MDP 中去估计state value，然而这不是我们的终极目标，我们真正想要的是去做优化。正如之前的Policy Iteration一样，我们评估完value（prediction），下一步就是利用评估的value做优化（control）。现实生活中，有很多问题都可以看做MDP：

然而这些问题的MDP要么是不完全可知的（不知道状态转移概率和reward），或者MDP可知但过于复杂，考虑全部的状态转移来求期望的计算复杂度太高。以上两种困境都可以转换为Model-free的方法来解决——不需要考虑完整的状态转移，只需要一些sample即可。

对于Model-free Control，还可以下分为两种：

On-policy Learning：即有一个现成的Policy，我们基于这一个Policy来采样一些episode，然后优化同一个Policy
Off-policy Learning：我们根据一些类似任务或参考范例来采样episode去学习优化一个新的Policy，这里的范例可以看做是一个执行的Polciy，例如使用人类Policy进行sample来指导优化机器人的Policy，也就是说用于学习的Policy和实际优化的Policy不是一致的。

2. On-Policy Monte-Carlo Control

2.1 Generalised Policy Iteration

回顾之前的Policy Iteration，其过程是先通过Policy evaluation来估计 $v_{\pi}$ ，然后采用贪心策略来优化 $\pi$ ，然后如此往复，通过证明可知，这种方式最终可以收敛到最优Policy。

如果我们使用Monte-Carlo Evaluation，其处理过程也是一样的，但是这样有一个问题：MC估计的是state value，我们在使用贪婪策略更新policy时按照下式进行：

$$
\pi'(s) = \arg\max_{a \in \mathcal{A}} \mathcal{R}_s^a + \mathcal{P}_{ss'}^a V(s')

因此，我们需要知道状态转移概率，这在Model-free的情景下是无法获取的，所以，我们应该使用MC来估计action value，然后使用action value就可以无需转移概率就可以优化policy了。

2.2 $\epsilon $-Greedy Exploration

考虑下面的开门问题，我们如果采用贪心策略来指导Policy的更新，可能会形成这样一个局面：

第一次我们进左边的门，获得0的reward
根据贪心策略，我们选择可能会更好的右门，得到1的reward
继续根据贪心策略，由于左边value是0，右边value是1，所以右边更好，继续选右边门，此时获得了3的reward。
再根据贪心策略，此时左边value还是0，右边value是2（MC方法是将多次Episode的结果取平均，即3+1取平均），继续选右边，获得2的reward
根据贪心策略，还是会选右边，如果右边一直是正reward，那么就永远不会选择左边门。
但是一定是右边是最优的吗？这并不一定。

上面的例子告诉我们，使用粗暴的贪心很可能会陷入局部最优解，因此我们需要重新设计贪心策略来尽可能规避它，最直观的办法就是$\epsilon $-Greedy Exploration：以 $1-\epsilon$ 的概率采取贪心策略选择action，以 $\epsilon$ 的概率随机选取一个action，概率表示为，$m$ 表述所有可选的action数量：

$$
\pi(a|s) =
\begin{cases}
\frac{\epsilon}{m} + 1 – \epsilon & \text{if } a^* = \arg\max\limits_{a \in \mathcal{A}} Q(s, a) \\
\frac{\epsilon}{m} & \text{otherwise}
\end{cases}

下面给出了证明，表面采用 $\epsilon $-Greedy 策略更新Policy，至少会得到一个比原来的Policy不差的Policy。

2.3 GLIE

$\epsilon $-Greedy Exploration策略使得我们可以按照下图左的形式去优化Policy并收敛。但我们知道，其实并不需要完整的Policy evaluation，就可以得到正确的趋势实现优化，即下图右所示的趋势，这样可以加速学习过程。

但上述的思想也有一个需要解决的问题：即如何确定当前的Policy evaluation可以得到最优的policy？

首先我们给出 Greedy in the Limit with Infinite Exploration (GLIE)的定义：

即满足以下两个条件的策略就称为GLIE：

所有的state-pair都会被无限次探索
Policy最后会收敛到一个贪心Policy

举例来说，$\epsilon_k = \frac{1}{k}$ 时，随着 $k$ 增加， $\epsilon$ 约接近0，也就是说随着时间的增加，探索的力度会变小，最终策略会变成贪心策略，而在早期阶段，所有的state-pair都会被探索，因此这就属于GLIE。

具体来说，GLIE的MC Control就是在迭代地进行下面的步骤：

3. On-Policy Temporal-Difference Learning

3.1 Sarsa

除了MC，也可以使用TD来进行Model-free Control，一个最自然的想法就是使用TD去估计 $Q(S,A)$ 然后利用$\epsilon $-Greedy Policy Improvement去进行更新。使用TD的好处是，在每个step都可以进行更新。这种TD更新Action-Value的方法也成为Sarsa：

从 S 根据一个确定的 A 转移到 $S^{\prime}$ ，同时获得一个 R，并通过bootstrapping得到 $Q(S^{\prime},A^{\prime})$ ，由此可以获得 $Q(S,A)$ 的更新，将所有涉及到的字母组合起来，就变成了SARSA.

具体的伪代码流程如下：

下面的理论确定了 Sarsa可以收敛到最优 action-value function的必要条件：

3.2 n-Step Sarsa

类似地，我们也可以将 n-step return的概念用在Sarsa中，得到新的value-state评估和更新方法，称为n-step Sarsa，可以看到相比于n-step TD，区别只是把$V$换成了$Q$，即从state-value变成了action-value：

3.3 Sarsa($\lambda$)

既然有n-Step Sarsa，自然也少不了 Sarsa($\lambda$)，同样可以从前向和后向两个角度去介绍这个算法——前向用于理解算法的本质和原理，后向用于实际的计算。

3.3.1 Forward View Sarsa($\lambda$)

如果理解了 TD($\lambda$)，这个也就很好理解了，区别仅仅是TD估计的是state-value，Sarsa估计的是action-value。action-value衡量的是一个状态下确定的一个动作的好坏，所以下面图示中开始就是一个黑点，表示一个确定的state-action pair，获得对应的reward，然后转移到下一个state，然后获得下一个state-action pair以及对应的reward，在最末端借助bootstrapping获得最后一个后继状态的action-value，以此评估action value。

3.3.2 Backward View Sarsa($\lambda$)

同样，引入eligibility traces 后我们就可以后向视角进行 Sarsa($\lambda$) 的更新了，只不过相比TD，action-value多了一个action的限制， eligibility trace 也会多一个维度：

$$
\begin{array}{l}
E_{0}(s, a)=0 \\
E_{t}(s, a)=\gamma \lambda E_{t-1}(s, a)+\mathbf{1}\left(S_{t}=s, A_{t}=a\right)
\end{array}
$$

后面的更新都是一样的：

$$
\begin{array}{l}
\delta_{t}=R_{t+1}+\gamma Q\left(S_{t+1}, A_{t+1}\right)-Q\left(S_{t}, A_{t}\right) \\
Q(s, a) \leftarrow Q(s, a)+\alpha \delta_{t} E_{t}(s, a)
\end{array}
$$

伪代码如下：

需要注意的是，在计算得到 Sarsa error后，我们会更新所有的action-value，同时对eligibility traces进行衰减。

下面给出使用 Sarsa($\lambda$) 的好处，下图左是一条可能的路径，视为一个Episode，只有达到终点才会获得一个reward=1：

如果使用one-step Sarsa，在这一个Episode遍历完后，只有倒数第二个状态的value会发生实际的更新，如下图中间，这是因为即使我们是step by step地去更新，但是由于只看临近的一个step，所以除了最靠近终止状态的状态有reward导致的数值变化，其他由于初始为0，每一个action的reward也是0，所以更新后还是0；
如果使用Sarsa($\lambda$) ，由于我们会综合考虑不同n-step，每个step会更新全部action-value，由于 eligibility trace 的加权，导致随着时间的变化，每个state-action的value会衰减，如下图右。

4. Off-Policy Learning

所谓Off-Policy Learning就是去Evaluate一个目标Policy $\pi(a|s)$ 去计算value function，然后优化我们的行为函数 $\mu(a|s)$ ，这里的行为函数是agent真正使用的Policy。这样做的好处在于：

可以通过观察其他Agent或者人类进行学习
可以重复使用目标Policy生成的Episode
这种方法使代理在遵循探索性策略的同时，仍然能够学习到最优策略，这对于平衡探索和利用之间的关系非常关键。
可以在只遵循一个行为策略的情况下，同时学习多个策略。

首先，介绍一个概念Importance Sampling，它可以借助来自其他分布的sample来估计某个分布的期望，式子如下：

$$
\mathbb{E}_{X \sim P}[f(X)] = \sum P(X) f(X) \\
= \sum Q(X) \frac{P(X)}{Q(X)} f(X) \\
= \mathbb{E}_{X \sim Q} \left[ \frac{P(X)}{Q(X)} f(X) \right]
$$

上式表示，我们要计算 $f(X)$ 在分布 $P(X)$ 下的期望，可以计算$\frac{P(X)}{Q(X)} f(X)$ 在分布 $Q(X)$ 下的期望作为替代。

4.1 Off-Policy Monte-Carlo

下面是使用Importance Sampling将MC用于Off-Policy的方式：我们要做的就是从Polciy $\mu$ 采样获得return，然后去evaluate Policy $\pi$ ，这两个Policy可以看成两个不同的分布，因此我们可以使用 Importance Sampling 将来自 $\mu$ 的Return 转换成 $\pi$ 的return，剩下就和原来的MC一样了。由于MC是一下子考虑整个采样序列，所以中间要乘很多次Importance Sampling的参数，导致方差会变的很大，训练不稳定且效率低。所以，更推荐使用TD。

4.2 Off-Policy TD

类似的，将TD用在off-policy就只要在每次把 估计的Return 转换一下就行。所谓估计的Return就是当前获得的reward+后继状态value。从下面的式子可以看到，我们只需要进行一次Importance Sampling转换，自然方差会更小。

4.3 Q-Learning

前面两个我们实际上只考虑了使用MC和TD在off-policy场景中对state value进行估计，但我们知道如果要进行policy的优化，在model-free的设定下，需要使用action value，即$Q(s,a)$ ，于是便有了Q-learning，更为厉害的是Q-leraning不需要 importance sampling。其做法是使用 $\mu$ 来获取下一步的Action，但同时考虑 $\pi$ 的下一步Action作为可选的后继动作，然后使用可选动作的value来更新 $\mu$ 的action value：

4.3.1 Off-Policy Control with Q-Learning

下面我们使用Q-learning进行 Off-Policy的Control：我们同时对behaviour policy（agent自身实际的policy）和target policy（用于学习采样的policy）进行优化，其中 target policy直接采用贪心策略，而 behaviour policy采用$\epsilon $-Greedy

具体来说，可以用下面的图表示：其实就是Sarsa的变体——Sarsa只要求evaluate不需要优化，Control加入优化的目标，所以Q-learning中就在Sarsa的基础上加入了max的限制条件。并且，有理论可以证明Q-leraning最终可以收敛到最优Policy。

Q-learning伪代码，流程都是类似，看一下就好了：

5. Summary

Model-Free 和 Model-Based 方法比较。