强化学习基础篇（二十五）n步时序差分预测

1、n步时序差分方法

之前在《强化学习基础篇（十七）时间差分预测》所介绍的是 $TD(0)$ 算法，其更新过程仅仅依赖于当前状态向下走一步的情况，将走一步走后的状态价值用于bootstrap更新。而蒙特卡洛方法是根据当前状态开始到终止状态的整个收益序列进行状态价值的更新。这节介绍的n步时序差分(n-step TD)是基于 $TD(0$ )的一步更新与MC对整个序列进行更新的两个极端之间的算法。从n步时序差分方法的回溯图中，我们可以看到每个n步方法都考虑了从当前状态向下走n步的情况。

image.png

2、n步回报

如果我们考虑如下的n取值下的回报（ $n=1,2,...,\infty$ ）
$\begin{equation} \begin{array}{rl} n=1 & (T D) \quad G_{t}^{(1)}=R_{t+1}+\gamma V\left(S_{t+1}\right) \\ n=2 &(T D) \quad G_{t}^{(2)}=R_{t+1}+\gamma R_{t+2}+\gamma^{2} V\left(S_{t+2}\right) \\ \vdots & \vdots \\ n=\infty & (M C) \quad G_{t}^{(\infty)}=R_{t+1}+\gamma R_{t+2}+\ldots+\gamma^{T-1} R_{T} \end{array} \end{equation}$
那么我们可以进行泛化定义n步回报为：
$\begin{equation} G_{t}^{(n)}=R_{t+1}+\gamma R_{t+2}+\ldots+\gamma^{n-1} R_{t+n}+\gamma^{n} V\left(S_{t+n}\right) \end{equation}$
根据n步回报修改 $TD(0$ 的更新方法为：
$\begin{equation} V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left(G_{t}^{(n)}-V\left(S_{t}\right)\right) \end{equation}$
这样我们就可以得到如下的n步时序差分算法。

image.png

3、n步时序差分方法在随机游走上的应用

在《强化学习基础篇（十九）TD与MC在随机游走问题应用》我们实现了随机游走的问题。这里我们将原问题的6个状态调整为19个状态，下面看看通过n步回报的方法效果如何。

导入库函数定义超参数

import numpy as np
import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt
from tqdm import tqdm

# 共19个状态
N_STATES = 19

# 定义折扣因子
GAMMA = 1

# 定义状态空间
STATES = np.arange(1, N_STATES + 1)

# 起始状态为第10个状态
START_STATE = 10

# 一共两个terminal状态
# 左边界的状态的回报为-1，右边界的状态的回报为+1
END_STATES = [0, N_STATES + 1]

# 设定真实价值（true value）
TRUE_VALUE = np.arange(-20, 22, 2) / 20.0
TRUE_VALUE[0] = TRUE_VALUE[-1] = 0

n-steps TD算法实现

# n-steps TD 算法实现
# value: 输入状态价值函数
# n: 输入n步的值
# alpha: 定义步长
def temporal_difference(value, n, alpha):
    # 初始化状态位置
    state = START_STATE

    # 定义一个列表存储states和rewards
    states = [state]
    rewards = [0]

    # 进行时间跟踪
    time = 0

    # 是定时间初始为无限
    T = float('inf')
    while True:
        # 进一个时间步
        time += 1

        if time < T:
            # 通过一个二项分布，随机选择一个动作，并按照动作更新状态
            if np.random.binomial(1, 0.5) == 1:
                next_state = state + 1
            else:
                next_state = state - 1
           # 按照问题定义，处理计算奖励。
            if next_state == 0:
                reward = -1
            elif next_state == 20:
                reward = 1
            else:
                reward = 0

            # 存储下一步状态与奖励
            states.append(next_state)
            rewards.append(reward)
        
            if next_state in END_STATES:
                T = time

        # get the time of the state to update
        update_time = time - n
        if update_time >= 0:
            returns = 0.0
            # 计算n步奖励
            for t in range(update_time + 1, min(T, update_time + n) + 1):
                returns += pow(GAMMA, t - update_time - 1) * rewards[t]
            # 将n步奖励增加到总回报中
            if update_time + n <= T:
                returns += pow(GAMMA, n) * value[states[(update_time + n)]]
            state_to_update = states[update_time]
            # 更新状态值函数
            if not state_to_update in END_STATES:
                value[state_to_update] += alpha * (returns - value[state_to_update])
        if update_time == T - 1:
            break
        state = next_state

实验运行与绘制结果

def figure7_2():
    # 这里要比较的n步包含了1,2,4,8..512
    steps = np.power(2, np.arange(0, 10))

    # 这里比较了三个步长
    alphas = np.arange(0, 1.1, 0.1)

    # 每次运行10个episodes
    episodes = 10

    # 实验总次数（因为结果要对这些100次取平均）
    runs = 100

    # track the errors for each (step, alpha) combination
    errors = np.zeros((len(steps), len(alphas)))
    for run in tqdm(range(0, runs)):
        for step_ind, step in enumerate(steps):
            for alpha_ind, alpha in enumerate(alphas):
                # print('run:', run, 'step:', step, 'alpha:', alpha)
                value = np.zeros(N_STATES + 2)
                for ep in range(0, episodes):
                    temporal_difference(value, step, alpha)
                    # 计算均方根误差（RMS error）
                    errors[step_ind, alpha_ind] += np.sqrt(np.sum(np.power(value - TRUE_VALUE, 2)) / N_STATES)
    # 对结果取平均
    errors /= episodes * runs

    for i in range(0, len(steps)):
        plt.plot(alphas, errors[i, :], label='n = %d' % (steps[i]))
    plt.xlabel('alpha')
    plt.ylabel('RMS error')
    plt.ylim([0.25, 0.55])
    plt.legend()

    plt.savefig('./figure_7_2.png')
    plt.close()

if __name__ == '__main__':
    figure7_2()

测试结果

结果展示了在不同的 $n$ 与 $\alpha$ 情况下n步方法的性能。不同情况下的性能测试指标是最后19个状态在每个episode终止时的价值函数的估计值和真实值的均方误差的平均值的开方，图中展示的是最开始10个episode，并重复100次的平均结果。从图中可以看出，n取中间大小的值效果最好，这也证明了将单步时序差分方法和蒙特卡洛方法推广到n步时序差分方法可能得到更好的结果。

image.png