本节课主要内容：

• On-Policy Monte-Carlo Control
• On-Policy Temporal-Difference Learning
• Off-Policy Learning

On-Policy Monte-Carlo Control

上节课讲了model-free的预测，这节课讲优化控制。
回忆一下之前的内容，lecture03讲到对于给定模型的MDP，通过V(s)改进策略：

$\pi'(s)=\mathop{argmax}_{a \in \cal{A}}\cal{R}_s^a+\cal{P}_{ss'}^aV'(s')$
如果我们想知道v(s)的值，那我们总是需要求出环境的模型。而行动价值函数 $Q(s,a)$能够让我们在不知道环境模型的情况下进行控制，Q评估各个状态的各个行为有多好。因此对于model-free的MDP，我们通过 $Q(s,a)$改进策略：
$\pi'(s)=\mathop{argmax}_{a \in \cal{A}}Q(s,a)$
但是每次总是选择最好的Q保证了exploitation，不能满足exploration，也就是没有遍历足够多的情况。因此用 $\epsilon$-Greedy来保证优化。一开始所有的m个行动以非零概率初始化，以 $1-\epsilon$的概率选择最好的情况，以 $\epsilon$的概率随机选择行动。
$\pi(a|s)=\begin{cases}\epsilon/m+1-\epsilon&\text{if a*=$\mathop{argmax}_{a \in \cal{A}}Q(s,a)$}\\ \epsilon/m&\text{otherwise}\end{cases}$
以下证明 $\epsilon$-Greedy的策略 $\pi'$总是能得到改进
$$\begin{align} q_{\pi}(s,\pi'(s))&=\sum_{a \in \cal{A}}\pi'(a|s)q_\pi(s,a)\\ &=\epsilon/m \sum_{a \in \cal{A}}q_\pi(s,a)+(1-\epsilon)\max_{a \in \cal{A}}q_\pi(s,a)\\ &\ge \epsilon/m \sum_{a \in \cal{A}}q_\pi(s,a)+(1-\epsilon)\sum_{a \in \cal{A}}\frac{\pi(a|s)-\epsilon/m}{1-\epsilon}q_\pi(s,a)\\ &=\sum_{a \in \cal{A}}\pi(a|s)q_\pi(s,a)=v_\pi(s) \end{align}$$
因此，我们是使用 lecture04 讲到的Monte-Carlo进行policy evaluation，用 $\epsilon$-greedy进行policy improvement。要找到最优值，就要对exploration和exploitation进行平衡，使用Greedy in the Limit with Infinite Exploration (GLIE)，即在有限状态下进行无限探索的贪婪算法，使用GLIE需要两个条件：

1. 所有的状态-行动对被无限地探索很多次。
   $\mathop{lim}_{k \rightarrow \infty}N_k(s,a)=\infty$
2. 策略最终收敛到一个贪心算法。
   $\mathop{lim}_{k \rightarrow \infty}\pi_k(a|s)=1(a=\mathop{argmax}_{a' \in \cal{A}}Q_k(s,a'))$

举个例子，若$\epsilon_k=\frac{1}{k}$，当$\epsilon$接近于0的时候，$\epsilon$-greedy是GLIE。

现在我们有了一个完整的未知环境MDP的解决方案：GLIE Monte-Carlo Control。

1. 使用策略$\pi$采样一个episode：${S_1,A_1,R_2,...,S_T}\sim \pi$
2. 更新episode中的每个状态和行动：
   $N(S_t,A_t)\leftarrow N(S_t,A_t)+1$
   $Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\frac{1}{N(S_t,A_t)}(G_t-Q(S_t,A_t))$
3. 基于新的行动-价值函数改进策略
   $\epsilon \leftarrow 1/k$
   $\pi \leftarrow \epsilon-greedy(Q)$

On-Policy Temporal-Difference Learning

TD相对于MC有很多优点，比如低方差、online、不完整的序列，因此考虑在控制优化使用TD而不是MC：将TD应用到$Q(S,A)$：

$Q(S,A) \leftarrow Q(S,A)+\alpha (R+\gamma Q(S',A')-Q(S,A))$
这称之为Sarsa方法，算法如下：

这是经过1步的Sarsa算法，和之前的TD算法类似，Sarsa也有经过n步。设经过n步的Q-return为：
$q_t^{(n)}=R_{t+1}+\gamma R_{t+2}+...+\gamma^{n-1}R_{t+n}+\gamma^nQ(S_{t+n})$
$Q(S_t,A_t) \leftarrow Q(S_t,A_t)+\alpha (q^{(n)}-Q(S_t,A_t))$
$Sarsa(\lambda)$分为forward-view和backward-view。
1. forward-view中的 $q^\lambda$使用权值将所有n步的Q-return $q_t^{(n)}$结合起来。
$Q(S_t,A_t) \leftarrow Q(S_t,A_t)+\alpha (q^{\lambda}-Q(S_t,A_t))$
2. backward-view在online的算法中使用eligibility trace：

$E_0(s,a) = 0$
$E_0(s,a) =\gamma \lambda E_{t-1}(s,a)+1(S_t=s,A_t=a)$
$\delta_t=R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-V(S_t,A_t)$
$Q(s,a)\leftarrow Q(s,a)+\alpha \delta_t E_t(s,a)$

Off-Policy Learning

前面讨论的都是建立在已知策略的基础上的，所用的策略就是正在学习的策略，但是有一些情况，我们想学习别的策略，比如我们想学习行为策略$\mu(a|s)$，从环境中选择我们的行动。
为什么要关心未知策略的学习呢？

1. 通过观察周围的环境和周围人的行为来学习。
2. 二次使用旧的策略。
3. 在exporation的时候能够学习到最优策略。
4. 在exploitation的时候能够学习到多个策略。

那怎么选择策略呢？使用importance sampling。采用两个策略$\pi$和$\mu$，importance weight为$\pi / \mu$。

对于off-policy Monte-Carlo使用importance sampling：

• 使用面向Monte-Carlo的策略$\mu$产生的return来估计策略$\pi$
• $G_t^{\pi / \mu}=\frac{\pi(A_t|S_t)}{\mu(A_{t+1}|S_{t+1})} \frac{\pi(A_{t+1}|S_{t+1})}{\mu(A_{t+1}|S_{t+1})} ... \frac{\pi(A_T|S_T)}{\mu(A_T|S_T)}G_t$
• 更新价值：$V(S_t)\leftarrow V(S_t)+\alpha (G_t^{\pi / \mu}-V(S_t))$

对于off-policy TD使用importance sampling：

• 使用面向TD的策略$\mu$产生的return来估计策略$\pi$
• 给TD的目标$R+\gamma V(S')$加权
• 更新价值：$V(S_t)\leftarrow V(S_t)+\alpha (\frac{\pi(A_t|S_t)}{\mu(A_t|S_t)}(R_{t+1}+\gamma V(S_{t+1}))-V(S_t))$
• 比Monte-Carlo importance sampling的方差小
• 不需要每一步的策略都相同

针对off-policy的解决方案是Q-learning。off-policy的行动-价值函数$Q(s,a)$，它不需要importance sampling。使用行为策略$A_{t+1} \sim \mu(\cdot|S_t)$选择下一步动作。$A' \sim \pi(\cdot|S_t)$是每个状态可选择的后继行动。

最后贴上DP和TD的关系：