• Q表格
  • 免模型预测
    • 蒙特卡罗策略评估
    • 时序差分
    • 动态规划、蒙特卡罗以及时序差分
  • 免模型控制
    • 探索性初始化蒙特卡罗法
    • $\varepsilon$-贪心蒙特卡罗算法
    • Sarsa：同策略时序差分控制
    • Q-learning：异策略时序差分控制
    • 同策略 vs 异策略
  • 总结

Q表格

上一章的马尔可夫决策过程说的是有模型情况下的预测和控制。这一章节的Q表格则是介绍了免模型情况下的预测和控制方法。

免模型预测

免模型说的是，不对环境的转移概率和奖励函数进行学习。

蒙特卡罗策略评估

上一章也简单介绍了蒙特卡罗策略评估的方法。简单来说就是对轨迹采样取平均作为期望值。下面会具体介绍。

一条轨迹的回报：

$$G_t = R_{t + 1} + \gamma R_{t + 2} + \gamma^2 R_{t + 3} + ...$$

状态价值是s状态以后的轨迹回报的期望：

$$v^T(s) = E_{\tau \sim \pi}[G_t|s_t = s]$$

增量式蒙特卡罗

均值可以写成增量形式的：

$$\begin{equation} \begin{aligned} \mu_n &= \frac{1}{n}\sum\limits_{j = 1}^n x_j\\ &= \frac{1}{n}(x_n + \sum\limits_{j = 1}^{n - 1} x_j)\\ &= \frac{1}{n}(x_n + (n - 1)\mu_{n - 1})\\ &= \mu_{n - 1} + \frac{1}{n}(x_n - \mu_{n -1}) \end{aligned} \end{equation}$$

因此蒙特卡罗也可写成增量形式：

$N(S_t)$ 表示计算$S_t$的价值采样的轨迹数量。

$$\begin{equation} \begin{aligned} N(S_t) &\leftarrow N(S_t) + 1\\ v(S_t) &\leftarrow v(S_t) + \frac{1}{N(S_t)}(G_t - v(S_t)) \end{aligned} \end{equation}$$

将$\frac{1}{N(S_t)}$ 换成$\alpha$ 作为学习率。因此最终的蒙特卡罗更新公式：

$$\begin{equation} \begin{aligned} v(S_t) &\leftarrow v(S_t) + \alpha(G_t - v(S_t)) \end{aligned} \end{equation}$$

时序差分

前面也提到过时序差分的方法，它结合了蒙特卡罗和动态规划的方法。在这一小节，会具体介绍它的工作方式。

时序差分的方法也是免模型的，不需要马尔可夫决策过程的状态转移概率和奖励函数。

$$\begin{equation} \begin{aligned} V(s) &= E[G_t|S_t = s]\\ &= E[R_{t+1} + \gamma R_{t + 2} + \gamma^2 R_{t + 3}...|S_t = s]\\ &= E[R_{t + 1} + \gamma (R_{t + 2} + \gamma R_{t + 3} + ..)|S_t = s]\\ &= E[R_{t + 1} + \gamma V_{t + 1}(s')|S_t = s] \end{aligned} \end{equation}$$

因此时序差分用$R_{t + 1} + \gamma V_{t + 1}(s')$ 来表示$G_t$:

$$G_t = R_{t + 1} + \gamma V_{t + 1}(s')$$

代入到蒙特卡罗的更新公式中得到：

$$v(S_t) \leftarrow v(S_t) + \alpha (R_{t + 1} + \gamma v(S_{t + 1}) - v(S_t))$$

也就是，实际上它的更新类似于蒙特卡罗，都是采样多条轨迹一次次更新，只是$G_t$的计算和蒙特卡罗不一样。

但是对比两种计算$G_t$ 的方式：

$$\begin{equation} \begin{aligned} &MC: G_t = R_{t + 1} + \gamma R_{t + 2} + \gamma^2 R_{t + 3} + ...\\ &TD: G_t = R_{t + 1} + \gamma V(S_{t + 1}) \end{aligned} \end{equation}$$

可以观察到蒙特卡罗的方法必须等到一个trace完成才能计算回报，从而更新状态价值。而时序差分的方法则在第二步就可以更新之前的状态价值。

前面介绍的TD方法给出的是TD(1)的方法，也就是一步之后更新。但是几步是可以选择的

$$\begin{equation} \begin{aligned} TD(1): G_t^1 &= R_{t + 1} + \gamma V(S_{t + 1})\\ TD(2): G_t^2 &= R_{t + 1} + \gamma R_{t + 2} + \gamma^2 V(S_{t + 2})\\ TD(3): G_t^3 &= R_{t + 1} + \gamma R_{t + 2} + \gamma^2 R_{t + 3} + \gamma^3 V(S_{t + 3})\\ ....\\ TD(\infty): G_t^{\infty} &= R_{t + 1} + \gamma R_{t + 2} + \gamma^2 R_{t + 3} + ... \end{aligned} \end{equation}$$

更新仍然采用：$v(S_t) \leftarrow v(S_t) + \alpha(G_t^n - v(S_t))$

可见$TD(\infty)$ 退化成蒙特卡罗方法。也可以理解为蒙特卡罗方法是TD方法的特例。

动态规划、蒙特卡罗以及时序差分

自举：指的是在更新中采用了估计。

动态规划和时序差分都采用了自举，因为它们都是用了v函数的值，这是一个估计值。蒙塔克罗没有，它是直接利用真实回报计算的。

蒙特卡罗和时序差分都采用了采样。而动态规划没有。

动态规划是有模型方法，而蒙特卡罗和时序差分方法不是。

上图从左到右分别展示了动态规划，蒙特卡罗和时序差分的方法。

动态规划会考虑每一种情况将它们的估计值加和。

蒙特卡罗则是走完一条轨迹用真实的reward更新价值函数。

时序差分则是只走一步，用一步的reward和估计值来更新。

时序差分如果考虑了所有可能的下一步state（也就是广度）它就变成了动态规划问题。

时序差分如果无穷步后更新（也就是考虑了深度），它就变成了蒙特卡罗方法。

免模型控制

在这里将介绍能够兼容蒙特卡罗和时序差分方法的广义策略迭代。

在上一章的动态规划部分也介绍了策略迭代的方法。回顾动态规划有两种控制方法：策略迭代和值迭代。策略迭代是先评估后更新，评估采用动态规划的迭代的方法得到v函数。更新是选择当前状态下使得q函数最大的action。更新后再评估，再更新。。。值迭代是直接找到最好的v函数，再找到对应v函数的策略。

但是在这一章免模型的控制，我们只介绍了免模型下的策略迭代方法。

免模型的广义策略迭代同样包含两个步骤：

1. 给当前的策略做评估，得到价值函数。
2. 根据价值函数，通过贪心的方法改进策略。

之前的动态规划的策略迭代可以通过如下的方式进行：

$$\begin{equation} \begin{aligned} q_{\pi}(s, a) = R(s, a) + \gamma \sum\limits_{s' \in S} P(s'|s, a)v_{\pi_i}(s')\\ \pi_{i + i}(s) = \arg\max\limits_{a}q_{\pi_i}(s, a) \end{aligned} \end{equation}$$

但是由于是无模型的方法，我们不知道$R(s, a)$ 和$P(s'|s, a)$，因此我们要对评估的方式进行修改。也就是找到得到q函数的方式。

探索性初始化蒙特卡罗法

首先我们将介绍一种采用蒙特卡罗方法探索性初始化的估计q函数的方法：

它的算法如下：

其中:

1. $G_t = R_{t + 1} + \gamma R_{t + 2} + \gamma^2 R_{t + 3} + .. = R_{t + 1} + \gamma G_{t + 1}$, 而$G_T = 0$，因此G的更新如算法中所示
2. q函数是（s, a）的gain的期望，因此这里用均值来估计它。
3. 用q函数找策略的方式和动态规划保持一致
4. 总的来说，这里做的就是用MC来估计q函数。

$\varepsilon$-贪心蒙特卡罗算法

接下来介绍一种改进方法：$\varepsilon$-贪心的蒙特卡罗算法

和上一种方法的主要不同在于。它的策略的选择以$1 - \varepsilon$的概率采用Q函数的最优action。以$\varepsilon$的概率采用随机的action。通过这种方式，这个算法可以有更强的探索性。

其中$\varepsilon$的值随着迭代的次数逐渐减小。因为后期的q函数选择的action更加可靠。

前面介绍的两种方式都是基于蒙特卡罗方法的，而相比起蒙特卡罗方法，时序差分的方法能够在线学习，能从不完整的序列中学习。因此可以将时序差分的方法也放到控制循环中。

Sarsa：同策略时序差分控制

同策略是指：策略评估和策略提升采用了相同的策略

异策略是指：策略评估和策略提升不一定采用相同的策略。比如之前的$\varepsilon$-贪婪算法

Sarsa实际上只是对时序差分控制的V换成了Q。

推导方式和V类似，结果：

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R_{t + 1} + \gamma Q(S_{t + 1}, A_{t + 1}) - Q(S_t, A_t)]$$

Sarsa 就是用这个方式评估得到Q函数，再用这个Q函数找到当前的最优策略。用这个策略重新评估，重新找最优策略。。。

Q-learning：异策略时序差分控制

异策略在策略评估和策略提升时候采用不同的策略。因此异策略有两种不同的策略：目标策略和行为策略。

目标策略是我们要学习的策略。它的目的是不需要和环境交互就可以选择合适的策略。

行为策略是探索环境的策略。它的目的是从环境中学习到经验教给目标策略学习。

目标策略

策略直接在q函数上使用贪心的方法，取q值最大的action。

$$\pi(S_{t + 1}) = \arg \max\limits_{a'}Q(S_{t + 1}, a')$$

行为策略

行为策略采用$\varepsilon$-贪心策略。有一定的随机性，从而可以做出探索。

由于目标策略是贪心策略，行为策略是$\varepsilon$-贪心策略，因此两者得到的策略不一定相同，也就是异策略的。

Q的更新采用了时序差分的方法。

完整过程：

Q-learning 与Sarsa唯一不同在于第二个红线处。sarsa在更新时候必须提前知道下一步的action，而q-learning由于选择的action不依赖于行为策略，因此可以直接计算。

同策略 vs 异策略

同策略算法用一个策略兼顾探索和利用，因此表现的比较胆小稳重。

异策略可以大胆利用行为策略去探索，再用目标策略选择最优策略，因此表现得比较激进。

总结