N1H111SM's Miniverse

RL Course Lesson (3) - Model-Free Control

字数统计: 2.2k阅读时长: 9 min
2019/08/15 Share

Preface

上一节主要内容是在没有Model的情况下如何去做Policy Evaluation,本章的重点是要没有Model的情况下去学会做决策,下一章将会介绍Value Function Approximation。学会优秀的策略需要应对以下两个问题,首先是Delayed Consequences,也就是说当前的决策可能需要在未来好几步才能够反映出好坏和价。其次就是要做到适当的Exploration,因为需要进行适当量的探索才能够发现较为优秀的策略。

对于许多的MDP模型来说,以下两种问题需要我们使用Model-free Control去解决:

  • MDP model is unknown but can be sampled.
  • MDP model is known but it is computationally infeasible to use directly, except through sampling.

On-policy learning 和 Off-policy learning是两种学习的方法,前者在和环境的交互中直接进行学习,也就是当前的policy和当前的sample是对应的;而后者能够从另一个不同的policy中去进行Evaluation和参数的更新。

Generalized Policy Iteration

首先回顾一下PI的流程(此时的PI是有真正Model的):初始化一个policy$\pi$;重复以下两步操作,首先进行Policy Evaluation,然后利用$\arg \max_{a} Q(s,a)$对当前policy进行更新($Q$值计算用到了$P$);直到拟合。在Model-free的情况下PI的流程也是一样的:重复Policy Evaluation + Policy Improvement。只是Policy Evaluation现在需要进行estimate Q来得到。

MC for On-policy Q Evalution

  • Initialize $N(s,a)=0, G(s,a)=0, Q^\pi(s,a)=0, \forall s \in S, \forall a \in A$
  • Loop
    • Using policy $\pi$ sample episode $i=s{i,1}, a{i,1},r{i,1},s{i,2}, a{i,2},r{i,2}, \dots, s_{i,T_i}$
    • $G{i,t}=r{i,t}+\gamma r{i,t+1}+ \gamma^2 r{i,t+2}+ \dots + \gamma^{Ti-1}r{i,T_i}$
    • Foreach (state,action) $(s,a)$ visited in episode $i$
      • For first or every time $t$ that $(s,a)$ is visited in episode $i$
        • $N(s,a)=N(s,a)+1, G(s,a)=G(s,a)+G_{i,t}$
        • Update estimate $Q^\pi(s,a)=G(s,a)/N(s,a)$

在此estimated Q value的基础上,我们只需要更新policy为:

这样的estimation可能会有一些问题,例如如果$\pi$是deterministic的,那么我们就没有办法计算$Q(s,a)$ for any $a \neq \pi(s)$,因为在sample时不会采样到其余的action。并且我们希望对于Q值的estimation和policy improvement能够相互穿插,而不是现在的大量的estimation的sample和更新得到一次policy的参数更新。这些内容会在下文中cover。为了平衡exploration和exploitation,一个简单的想法就是使用$\epsilon$-greedy方法。

这里可以证明:For any $\epsilon$-greedy policy $\pii$, the $\epsilon$-greedy policy w.r.t $Q^{\pi_i}$, $\pi{i+1}$ is a monotonic improvement $V^{\pi_{i+1}} \geq V^{\pi_i}$ .证明过程略去,这里放一张课程PPT的截图。

image.png

Greedy in the Limit of Infinite Exploration (GLIE)

问题在于我们知道了每一次的improvement是monotonic之后,我们能够获得什么保证(guarantee)?答案是如果你sample所有的的state-action pair无限次,你的behavior policy会最终converge到greedy policy。GLIE的定义是,所有的state-action对被访问的次数在sample次数的数量趋向于无穷时也应当趋向于无穷:

那么就有:

一个简单的GLIE strategy就是让探索的随机性系数$\epsilon$随着sample的样本改变:$\epsilon_i = 1/i$. 同时GLIE Monte-Carlo Control能够确保收敛到Optimal的state-action value function:$Q(s,a)\to Q^*(s,a)$.

Monte Carlo Online Control

结合上面的内容,在线的MC Control算法可以用以下的伪代码表示:

image.png

Temporal Difference Methods for Control

通常情况下使用TD方法进行Model-free PI的框架可以被归纳为:随机初始化策略$\pi$;重复更新策略(和使用MC方法几乎相同)Policy Evaluation + Policy Improvement。

SARSA

SARSA算法的伪代码如下图所示,和MC方法的核心变化在于TD方法不需要等一个episode完结才能够进行更新,而是根据下一个step的观察可以直接进行更新,其依据就是利用Bellman方程的estimation:

image.png

SARSA for finite-state & finite-action MDPs 在以下两个条件成立时能够保证收敛到最优的action-value:

  • 策略序列$\pi_{t}(a | s)$满足上面所提及的GLIE条件
  • 步长$\alpha_t$满足Robbins-Munro序列要求:
    • $\sum{t=1}^{\infty} \alpha{t}=\infty$ 并且 $\sum{t=1}^{\infty} \alpha{t}^{2}<\infty$

在实践中我们的步长一般不遵从这里的限制,通常使用的是逐级递减的步长就可以。这里提到了SARSA采用的更新策略是实际sample出的下一个step的情况,这种方式对比Q-Learning来说是“相对客观”的。Q-Learning会过分乐观(因为更新策略中拿到的是max value),但是SARSA算法在Sutton and Barto的cliff walk example中表现会更好。关于这个问题,我们会在这章最后简单用代码实现一下。但是很多的问题都不会具有这样的性质。

Q-Learning

Q-Learning也是一个Temporal Difference的方法,和SARSA相比,Q-Leaning不需要从policy当中sample出确切的action,而是更新时采用当前时间步最大期望的action-state值进行更新。虽然理论上Q-Learning能够确保收敛到和SARSA一样的最优值,但初始化的状态也依旧会产生一些影响。总体来说,optimistic initialization会比较有帮助。以下是两种算法的更新函数的比较。

  • SARSA:$Q\left(s{t}, a{t}\right) \leftarrow Q\left(s{t}, a{t}\right)+\alpha\left(\left(r{t}+\gamma Q\left(s{t+1}, a{t+1}\right)\right)-Q\left(s{t}, a_{t}\right)\right)$
  • Q-Learning:$Q\left(s{t}, a{t}\right) \leftarrow Q\left(s{t}, a{t}\right)+\alpha\left(\left(r{t}+\gamma \max {a^{\prime}} Q\left(s{t+1}, a^{\prime}\right)\right)-Q\left(s{t}, a_{t}\right)\right)$

image.png

Maximization Bias

在以下的简单设置中,只有单一的state,action space为2,两个action给出的reward遵从以0为中心的正态分布。关于两个state-action的EV都是无偏估计,但是只要是有限的sample,就会导致最终的策略是有偏的。

image.png

解决方法是采用Double Q-Learning。简单来说就是采用一个Q-function来进行estimation,另一个Q-function进行action sampling。以下为Double Q-Learning的完整伪代码:

image.png

这里是我不是非常理解的地方,就是为什么Double Q-Learning能够maximization bias,课程中的解释是这种方法使用了independent samples to estimate the value。而在现实中使用该算法时,可以以0.5的概率对这两个Q function进行交替的estimate和sample。Double Q-Learning只增加了内存开销,不会产生更大的计算开销,而且能够达到非常好的效果。以下的实验结果告诉我们Q-Learning在前期非常可能suffer在不是最优的策略中,但Double Q-Learning却能够很好地解决这个问题。

image.png

这篇博客对这个问题进行了一些阐述,最主要的观点是Q-Learning中的max函数导致了过于乐观的估计。如果Reward带上了随机性(例如遵从一个EV为负的分布),那么sample前期的正向结果都会导致模型得到错误的估计,估计导致策略向这个错误的方向偏移,会使得模型在未来的一段时间内都得出不好的结果。

What is happening here is that, if an action’s value was overestimated, it will be chosen as the best action, and it’s overestimated value is used as the target. Instead, we can have two different action-value estimates as mentioned in the above equation, and the “best” action can be chosen based on the values of the first action-value estimate and the target can be decided by the second action-value estimate. How do we train though?

Divide the samples into two halves. For the first half, we can use the above equation to train, and for the second half swap the “1” with the “2” in the equation. In practice, data keeps coming into the agent, and thus a coin is flipped to decide if the above equation should be used or the swapped one. How does this help?

Since the samples are stochastic, it is less likely that both the halves of the samples are overestimating the same action. The above method separates two crucial parts of the algorithm, choosing the best action and using the estimate of that action, and hence works well.

虽然我们仅仅是在非常简单的场景当中阐述了可能产生maximization bias的可能情况,也有研究者指出在Atari这样复杂的游戏中也会产生这样的问题。而同时,如果所有的action-values都受到了overestimation的影响,那么对于最终学习到的策略不会有任何影响;相反,如果不同的state所受到的影响不同(例如有些state的reward是恒定的),那么对最终的optimal policy会产生影响。

CATALOG
  1. 1. Preface
  2. 2. Generalized Policy Iteration
  3. 3. Monte Carlo Online Control
  4. 4. Temporal Difference Methods for Control
    1. 4.1. SARSA
    2. 4.2. Q-Learning
  5. 5. Maximization Bias