第五课 无模型控制

Intro

上一篇我们讲了 MonteCarlo 和 TD 方法,他们都是用于在五模型的时候估算当前各个状态的 Value 的,即已经有了 Policy Evaluation 部分。我们还需要一个 Policy Impovement 的部分。这部分就是来解决这个问题的。在优化控制部分,我们根据是否根据已经拥有他人的经验来更新自身的控制策略,将优化控制分类下面两类:

  • Online-policy Learning 其基本思想是个体已经有一个策略,并且根据这个策略去进行采样,并根据使用了这个策略得到的一些行为的奖励,更新状态函数,最后根据更新的价值函数来优化策略得到的最有的策略。
  • Offline-policy Learning 其资本思想是个体已经有了一个策略,但是不根据这个策略进行采样,而是根据另一个策略进行采用。这个策略的来源可以是先前学习的策略,也可以是人类给出的策略。在自己的策略形成的价值函数的基础上观察别的策略产生的行为,以达到学习的目的。小帅哥说,这种事类似于“站在别人肩膀后面观察他人行为的一种方式”。

策略迭代的基本框架

根据我们之前看课程学到的内容,我们进行学习的整个思路就是在 Policy Evaluation 和 Policy Imporvement 两个操作间迭代的过程。如下图所示:

在这个部分我们需要加一个反思,什么是“不基于模型”,“不基于模型”有什么不同。不基于模型会导致以下两个问题:

  1. 模型未知的时候,我们无法知道当前状态的所有后续状态。这样无法真正“准确”、“理性”地判断当前应该采取什么行为。
  2. 承接问题 1 ,我们自然而然想到用采样的方式来学习。但是不足的采样会导致得到非最优策略,这样我们需要去尝试一些新的行为。 注:这里小帅哥讲了一个左边的门,还是右边的门的例子,来解释这种情况

Online-Policy Monte-Carlo Control

针对上面的两个问题,给出的一个解决方案如下(注意这种思想同样适用于 TD):

  1. 针对第一个问题,很直觉的思路就是,对当前策略在所有状态下,产生的所有行为的结果进行采样,并以此为基准更新 $Q(s,a)$ ,其中 $Q$ 为状态对应下的行为的价值,用于代替原有设定中状态的价值。其中更新方法为贪心算法。

    \[\pi ' (s) =argmax_{a \in A}\ Q(s,a)\]
  2. 而针对第二个问题的解决问题就有点类似 Multi-armed Bandit 问题,核心在于如何平和 Explore 和 Exploit 的比例。 于是很直觉的思路就是,给他们两个分别以 $\epsilon$ 和 $1 - \epsilon$ 的概率来让两者都能被坚固。其中 $\epsilon$ 代表探索(exploration),即在所有可能的行为中进行选择。而另一个则代表利用(Exploitation),即选取已有的最好的行为。

    \[\pi(a|s) = \left\{ \begin{array}{rcl} \epsilon / m + 1 - \epsilon & if & a^{*} = argmax_{a \in A}\ Q(s,a) \\ \epsilon /m & &otherwise \\ \end{array}\right.\]

    注1:该公式个人也没太看明白

    注2:小哥简单的对这样做来优化 q 函数进行了一些简单的推导,证明了最终新的 q 值是递增的

这样子我们把上面的第二个的思想带入回 MC 控制,得到了 MC 控制的全貌图:

到了这里我们还遇到两个问题:

  1. 我们不想丢失任何更好的信息和状态
  2. 我们希望能终止于某一个最优策略。(当前得到的算法中,是可以无限延续的)。在此基础上引入了一个新的概念 GLIE。

GLIE(Greedy in the Limit with Infinite Exploration)

这个概念为,在有限的时间内进行无限可能的探索。具体表现有以下两个特征:

  1. 对已经经历的状态行为对(state-action pair)会进行无限次的探索
  2. 随着探索的无限延伸,之前算法中的 $\epsilon$ 回趋向于 0 (这就解决了上面提到的问题)。

具体流程如下:

Online-Policy Temporal-Difference

SARSA

TD 相比 Monte-Carlo 有很多优点,那么我们是不是可以用 TD 代替 MC 呢。而这个思路诞生的算法就是 SARSA。SARSA 的名字的来源就是其训练的过程,如下图所示。

简单的复述下上图的算法流程,首先是第一个 $SA$ ,根据 $Q\ e.g., \epsilon -greedy$,得到一个动作 $A$ 。在执行完动作 $A$ ,之后我们会得到一个即时奖励 $R$,并进入状态 $S’$,之后再根据 $Q$,得到动作 $A’~$。但是这次不执行,根据公式更新 $Q$ 即可。每个步骤汇总起来就是 SARSA。

注:其中 $Q$ 是一个大表存储的,这显然不能用于规模很大的问题

SARSA (λ)

之前的 SARSA 的模型中,只考虑到了未来的一步,那么直觉的来讲,其可以考虑 n 步。于是我们可以得到 n-step SARSA。其给每一步的 $Q$ 的收获都分配一个权重,则会得到 $q^{\lambda}$ 收获。公式如下:

\[q^{\lambda}_t = (1-\lambda)\sum^{\infty}_{n=1} \lambda^{n-1} q_t^{(n)}\]

前向 SARSA 根据某一状态的 $q^{\lambda}$ 收获来更新状态行为对的 $Q$ 值:

\[Q(S_t,A_t) = Q(S_t, A_t) + \alpha(q_t^{\lambda} - Q(S_t,A_t))\]

反向 SARSA 反向 SARSA 中,引入了一个新的概念 Eligibility Trace,其针对的是一个状态行为对,体现的是一个结果与某一个状态行为对的因果关系。

\[\begin{split} E_{0}(s,a)&=0 \\ E_{t}(s,a)&= \gamma \lambda E_{t-1}(s,a) + 1(S_t=s, A_t=a) \end{split}\]

对 $Q$ 值的更新如下:

\[\begin{split} \delta_t &= R_{t+1} + \gamma Q(S_{t+1},A_{t+1}) - Q(S_t,A_t) \\ Q(s,a) &= Q(s,a) + \alpha \delta_t E_t(s,a) \end{split}\]

整体 SARSA (λ) 如下:

Off-Policy Learning

正如之前提到的,Off-Policy Learning 指的是在遵守一个策略 $\mu (a|s)$ 的同时评估另一个策略 $\pi(a|s)$ 。同时基于 MC 的学习并没有实际应用价值,所以这里就只讨论 TD 下的 Off-Policy Learning。

整个的思路就是在遵循策略 $\mu (a s)$ 的同时评估另一个策略 $\pi(a s)$ ,所以在具体的数学表示上,就体现在更新 $V(S_t)$ 上面:
\[V(S_t) = 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))\]

注:Q-Learning 指的就是学习 Q 的算法,并不是一个固定的算法。所以这里就不细说了。详细的参考大佬的博客,或者 PPT 中的算法流程都会有很详细的解释。

参考文献

  • 本文作者: Author:DeamoV
  • Github:https://github.com/VDeamoV
  • Email:vincent.duan95@outlook.com
  • 本文链接: Artical: 第五课 无模型控制
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!
  • 版权声明: 原创文章如转载,请注明出处