# 第五章：基于时间差分的强化学习方法

## 5.1 基于时间差分强化学习算法理论讲解

与动态规划和蒙特卡罗方法相比，时间差分方法的主要不同在于值函数的估计。在动态规划中，值函数的计算使用了bootstrapping方法，即用后继状态的值函数估计当前值函数的。由模型公式和动作集，科技一算状态$$s$$的所有的后继状态$$s'$$(公式1)。当没有模型时，无法通过动态规划得到后继状态。由于值函数的本质是期望，通过经验平均代替期望来估计值函数便应运而生（公式2）。相比于动态规划，蒙特卡洛方法需要等到每次实验结束，导致学习速度非常慢，学习效率不高。

![](https://1340105069-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9CzxVOitMkbMmWWijk%2Fsync%2F48516b99f299d474494986f145bcd3d0f44ccba0.png?generation=1591520273696156\&alt=media)

$$
V(S\_t) \leftarrow E\_{\pi} \[R\_{t+1} + \gamma V(S\_{t+1})] = \sum\_a \pi(a|S\_t)\sum\_{s',t}p(s',r|S\_t,a)\[r+\gamma V(s')]
$$

$$
V(S\_t) \leftarrow V(S\_t) + \alpha (G\_t - V(S\_t))
$$

结合两者的优点，时间差分方法（TD）结合了蒙特卡罗的采样方法和动态规划的bootstrapping，其值函数的更新公式为：

$$
V(S\_t) \leftarrow V(S\_t) + \alpha(R\_{t+1} + \gamma V(S\_{t+1}) - V(S\_t))
$$

其中$$R\_{t+1} + \gamma V(S\_{t+1})$$称为TD目标，与蒙特卡洛方法的$$G\_t$$对应，不同之处在于TD目标使用了bootstrapping方法估计值函数。$$\delta\_t = R\_{t+1} + \gamma V(S\_{t+1}) - V(S\_t)$$称为TD偏差。

蒙特卡罗方法中的$$G\_t = R\_{t+1} + \gamma R\_{t+2}+ ... + \gamma^{T-1}R\_t$$*，由于每次都模拟到结尾，所以蒙特卡洛方法是无偏估计。但模拟的随机性很大，因此导致蒙特卡罗方法的方差很大。时间差分方法中用到的*$$V(S\_{t+1})$$使用的是估计值，因为时间差分方法是**有偏的**。但是时间差分方法只用到了一次模拟，所以随机性很小，相应的**方差也要比蒙特卡罗方法的方差小**。

时间差分方法包括同策略的Sarsa强化学习方法和Qlearning方法，与蒙特卡罗方法不同之处是他们的值函数更新方法不同。

### 同策略Sarsa强化学习方法

```
[1] 初始化Q(s,a), all s∈S, a∈A, 给定参数α，γ
[2] Repeat:
        针对初始状态s,并根据 epsilon-贪婪策略在状态s选择动作a
        Repeat (对于每一幕的每一步)
            (a) 根据epsilon-贪婪策略在状态s选择动作a，得到回报r和下一个状态s'，在状态s'根据epsilon贪婪策略得到动作a'
            (b) Q(s,a)←Q(s,a) + α[r + γ*Q(s',a')-Q(s,a)]
            (c) s=s', a=a'
        Until s是中止状态
    Until 所有的Q(s,a)收敛
[3] 输出最终策略：π(s) = argmax_a Q(s,a)
```

异策略Qlearning

```
[1] 初始化Q(s,a), all s∈S, a∈A, 给定参数α，γ
[2] Repeat:
        针对初始状态s,并根据 epsilon-贪婪策略在状态s选择动作a
        Repeat (对于每一幕的每一步)
            (a) 根据epsilon-贪婪策略在状态s[t]选择动作a[t]，得到回报r[t]和下一个状态s[t+1]
            (b) Q(s[t],a[t])←Q(s[t],a[t]) + α[r[t] + γ*max_a Q(s[t+1],a[t+1])-Q(s[t],a[t])]
            (c) s=s', a=a'
        Until s是中止状态
    Until 所有的Q(s,a)收敛
[3] 输出最终策略：π(s) = argmax_a Q(s,a)
```

当更新当前的值函数时，我们用到了下一个状态的值函数。由此可以推理，我们可以使用第二个乃至第n个状态的值函数，利用n步值函数更新当前值函数可以表示为：

$$
G\_t^n = R\_{t+1} + \gamma R\_{t+2} + ... + \gamma^{n-1}R\_{t+n} + \gamma^n V(S\_{t+n})
$$

利用n种不同步值更新当前值函数会有n种方法，很难衡量哪种值更接近真实值，但是我们可以使用加权的方法（在$$G\_t^{(n)}$$前乘以加权因子$$(1-\lambda)\lambda^n$$）融合着n个估计值，这就是**TD(λ)方法**

理解$$TD(\lambda)$$可以从前向和后向两个角度解释。

前向：通过观看将来状态的值函数来估计当前状态的值函数。

后向：从已经经历过的状态$$s\_t$$出发，更新所有需要$$s\_t$$状态出的值函数。更新流程如下：

1. 计算当前状态的TD偏差：$$\delta\_t = R\_{t+1} + \gamma V(S\_{t+1}) - V(S\_t)$$
2. 更新适合度轨，其中$$E\_t(s)$$

   $$
   E\_t(s)=
   \begin{cases}
   \gamma \lambda E\_{t-1}\&s\neq s\_t\\
   \gamma \lambda E\_{t-1} + 1\&s = s\_t
   \end{cases}
   $$
3. 对于状态空间中的每个状态s，更新值函数：$$V(s) \leftarrow V(s) + \alpha\delta\_t E\_t(s)$$

前向和后向观点的异同：

1. 前向观点需要等一次实验结束后再更新当前状态的值函数；后向观点不需要等到值函数结束后再更新值函数，而是每一部都在更新值函数，是增量方法
2. 前向观点在每一次实验结束后更新值函数时，会更新完当前装填的值函数后，此状态的值函数就不再改变。后向观点在每一步计算完当前的TD误差后，其他状态的值函数需要利用当前状态的TD误差更新
3. 在一次实验结束后，前向观点和后向观点的每个状态的值函数的更新总量是相等的，都是$$G\_t^\lambda$$

Sarsa算法

```
1. 初始化Q(s,a), for all s∈S, a∈A(s), 给定参数α, γ
2. Repeat:
    给定初始状态s, 并根据epsilon-greedy策略在状态s选择动作a, 对所有的s∈S, a∈A(s), E(s,a)=0
        Repeat (对于一幕的每一步)
            (a) 根据epsilon-greedy策略在状态s选择动作a, 得到回报r和下一个状态s', 在状态s'根据epsilon-greedy策略得到动作a
            (b) δ←r+γQ(s',a')-Q(s,a), E(s,a)←E(s,a)+1
            (c) 对所有的s∈S, a∈A(s): Q(s,a)←Q(s,a)+aδE(s,a), E(s,a)←γλE(s,a)
            (d) s=s', a=a'
        Until s是终止状态
    Until所有的Q(s,a)收敛
3. 输出最终策略：π(s) = argmax_a Q(s,a)
```

5.2 基于Python和gym的编程实例
