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

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

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

$$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的编程实例