深度增强学习David Silver（五）——Model-Free Control

本节课主要内容：

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

On-Policy Monte-Carlo Control

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

π′(s)=argmaxa∈ARas+Pass′V′(s′)
如果我们想知道v(s)的值，那我们总是需要求出环境的模型。而行动价值函数Q(s,a)能够让我们在不知道环境模型的情况下进行控制，Q评估各个状态的各个行为有多好。因此对于model-free的MDP，我们通过Q(s,a)改进策略：
π′(s)=argmaxa∈AQ(s,a)
但是每次总是选择最好的Q保证了exploitation，不能满足exploration，也就是没有遍历足够多的情况。因此用ϵ-Greedy来保证优化。一开始所有的m个行动以非零概率初始化，以1−ϵ的概率选择最好的情况，以ϵ的概率随机选择行动。
π(a|s)=⎧⎩⎨ϵ/m+1−ϵϵ/mif a*=argmaxa∈AQ(s,a)otherwise
以下证明ϵ-Greedy的策略π′总是能得到改进

因此，我们是使用lecture04 讲到的Monte-Carlo进行policy evaluation，用ϵ-greedy进行policy improvement。要找到最优值，就要对exploration和exploitation进行平衡，使用Greedy in the Limit with Infinite Exploration (GLIE)，即在有限状态下进行无限探索的贪婪算法，使用GLIE需要两个条件：

1. 所有的状态-行动对被无限地探索很多次。
   limk→∞Nk(s,a)=∞
2. 策略最终收敛到一个贪心算法。
   limk→∞πk(a|s)=1(a=argmaxa′∈AQk(s,a′))

举个例子，若ϵk=1k，当ϵ接近于0的时候，ϵ-greedy是GLIE。

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

1. 使用策略π采样一个episode：S1,A1,R2,...,ST∼π
2. 更新episode中的每个状态和行动：
   N(St,At)←N(St,At)+1
   Q(St,At)←Q(St,At)+1N(St,At)(Gt−Q(St,At))
3. 基于新的行动-价值函数改进策略
   ϵ←1/k
   π←ϵ−greedy(Q)

On-Policy Temporal-Difference Learning

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

Q(S,A)←Q(S,A)+α(R+γQ(S′,A′)−Q(S,A))
这称之为Sarsa方法，算法如下：

这是经过1步的Sarsa算法，和之前的TD算法类似，Sarsa也有经过n步。设经过n步的Q-return为：
q(n)t=Rt+1+γRt+2+...+γn−1Rt+n+γnQ(St+n)
Q(St,At)←Q(St,At)+α(q(n)−Q(St,At))
Sarsa(λ)分为forward-view和backward-view。
1. forward-view中的qλ使用权值将所有n步的Q-return q(n)t结合起来。
Q(St,At)←Q(St,At)+α(qλ−Q(St,At))
2. backward-view在online的算法中使用eligibility trace：

E0(s,a)=0
E0(s,a)=γλEt−1(s,a)+1(St=s,At=a)
δt=Rt+1+γQ(St+1,At+1)−V(St,At)
Q(s,a)←Q(s,a)+αδtEt(s,a)

Off-Policy Learning

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

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

那怎么选择策略呢？使用importance sampling。采用两个策略π和μ，importance weight为π/μ。

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

• 使用面向Monte-Carlo的策略μ产生的return来估计策略π
• Gπ/μt=π(At|St)μ(At+1|St+1)π(At+1|St+1)μ(At+1|St+1)...π(AT|ST)μ(AT|ST)Gt
• 更新价值：V(St)←V(St)+α(Gπ/μt−V(St))

对于off-policy TD使用importance sampling：

• 使用面向TD的策略μ产生的return来估计策略π
• 给TD的目标R+γV(S′)加权
• 更新价值：V(St)←V(St)+α(π(At|St)μ(At|St)(Rt+1+γV(St+1))−V(St))
• 比Monte-Carlo importance sampling的方差小
• 不需要每一步的策略都相同

针对off-policy的解决方案是Q-learning。off-policy的行动-价值函数Q(s,a)，它不需要importance sampling。使用行为策略At+1∼μ(⋅|St)选择下一步动作。A′∼π(⋅|St)是每个状态可选择的后继行动。

最后贴上DP和TD的关系：