时间差分学习

先前介绍的动态规划(Dynamic programming)的求解方法是基于模型(model-based)的，也就是当我们知道环境 $Env\{S,A,P,R\}$ 的情况下。但是现实生活中的状态空间 $S$ 和动作空间 $A$ 往往是无限的，并且我们很少知道当前状态 $s$ 与下一个状态 $s'$ 之间的转换函数 $P(s'\mid s, a)$与下一个状态的奖励 $R(s')$，我们只能从经验中进行学习推导，由此引出一种算法——“时间差分学习”来解决问题。

时间差分学习（Temporal Difference Learning，简称TD学习）是一种强化学习算法，用于通过经验来预测未来奖励或值的估计。TD学习结合了蒙特卡罗方法和动态规划的优点，在不需要模型的情况下进行学习。它通过更新当前估计值，以使其更接近于下一个时刻的估计值，从而逐步改进对价值的预测。

举个例子来方便我们理解时间差分学习算法是怎样工作的。假设你需要预测星期六的天气，并且手头上正好有相关的模型。按照一般的方法，你只有到星期六才能根据结果对你的模型进行调整。然而，当到了星期五时，你应该对星期六的天气有很好的判断。因此在星期六到来之前，你就能够调整你的模型以预测星期六的天气。

让我们回到前面所讲述的贝尔曼期望方程(Bellman equation)，这个方程的含义是在给定策略 $\pi$的情况时价值函数 $V$在策略指引下所采轨迹上的期望。在我们不知道转换函数 $P(s'\mid s, a)$的情况下，我们可以尝试很多次来对价值函数 $V$进行估计。

$$V^\pi\left(s_t\right)= \sum_a \pi\left(a_t \mid s_t\right) \sum_{s_{t+1}} p\left(s_{t+1} \mid s_t, a_t\right)\left[r_t+\gamma V^\pi\left(s_{t+1}\right)\right]\\ \begin{align} & =\mathbb{E}_{a_t, s_{t+1} \sim \pi, p}\left[r_t+\gamma V^\pi\left(s_{t+1}\right)\right] \\ & \approx \frac{1}{N} \sum_i^N r_t^i+\gamma V^\pi\left(s_{t+1}^i\right) \end{align}$$

那能不能更简单一点呢？——将 $N$假设为1带入。其中 $\{r_t + \gamma V^\pi\left(s_{t+1}^i\right) - V^\pi\left(s_t\right)\}$这一项即为更新量

$$\begin{align} V^\pi\left(s_t\right) \approx r_t  + \gamma V^\pi\left(s_{t+1}\right) = V^\pi\left(s_t\right) + r_t + \gamma V^\pi\left(s_{t+1}\right) - V^\pi\left(s_t\right) \end{align}$$

显然直接带入 $N=1$ 是不准确的估算，所以需要利用学习率 $\alpha$ 来调节更新的多少。其中 $r_t + \gamma V^\pi\left(s_{t+1}\right)$这一项就为TD target， $r_t + \gamma V^\pi\left(s_{t+1}\right) - V^\pi\left(s_t\right)$为更新量，即预测误差（prediction error）。

$$\begin{align} V^\pi\left(s_t\right) = V^\pi\left(s_t\right) + \alpha(r_t + \gamma V^\pi\left(s_{t+1}\right) - V^\pi\left(s_t\right)) \end{align}$$

推出这个公式有什么用呢？在这个公式下，我们的目标是让模型对状态 $s$ 的评估更为准确，即状态价值函数 $V$ 更准确。当agent根据策略policy选择动作 $a_t$时，环境会给出下一个状态 $s_{t+1}$与之相应的奖赏 $r_{t+1}$，利用状态价值函数计算给出当前状态 $s_{t+1}$的价值，最后计算error以此优化状态价值函数$V$ 。

对于一个强化学习的任务，我们需要agent面对状态 $s_{t}$ 做出最优的动作 $a_t$ 。当目标是训练agent在面对状态时做出更好的动作action时，我们应该利用评估动作的动作价值函数 $Q$。

下面是贝尔曼方程的动作价值函数 $Q$ 形式公式(5)，与之前的推导一致，我们获得Q learning的公式(6)。

$$\begin{align} Q^\pi\left(s_t, a_t\right)=\sum_{s_{t+1}} p\left(s_{t+1} \mid s_t, a_t\right)\left[r_t+\gamma \max _a Q^\pi\left(s_{t+1}, a\right)\right] \end{align}$$

$$\begin{align} Q^\pi\left(s_t, a_t\right)=Q^\pi\left(s_t, a_t\right)+\alpha\left(r+\gamma \max _a Q^\pi\left(s_{t+1}, a\right)-Q^\pi\left(s_t, a_t\right)\right) \end{align}$$

接下来，我们以frozen_lake为例， 结合代码完整理解Q-learning：

首先，初始化环境

seed = 1234 # 设置随机种子 
env = frozen_lake(seed=seed) # 以种子初始化冰湖   
env.reset() # 环境重制 
fig, ax = plt.subplots(1, 1, figsize=(4, 4))
env.render(ax) # 渲染

如图为渲染后的初始化的冰湖游戏，图中O为起始点，G为终点，蓝色方块为障碍物。

图1 冰湖游戏全局状态

首先建立需要用到的参数

q = np.random.randn(env.nS, env.nA) 
# 动作价值函数：代表在一个状态下做出一个动作的价值 
# 在冰湖游戏里为64个格子(长8*宽8) * 4中动作（上，下，左，右）
rng = np.random.RandomState(seed)
# 通过种子固定随机数生成器

策略policy我们就利用最简单的贪心策略，即agent在做选择时，只考虑当前选择的最优选。

def e_greedy(q, rng, env, eps):
    # epsilon greedy decision policy
    # q: 动作价值（Q值）列表或数组，表示每个可能动作的预期回报。注意虽然上述q为64*4，
    # 但在选择时，我们只对于一个状态做选择，即放入函数的q为1*4
    # rng: 随机数生成器（通常是 np.random 或者带有随机状态的生成器）。
    # env: 环境对象，应该包含动作空间的大小（env.nA 表示动作的总数）。
    # eps: epsilon 值，表示探索的概率（即选择随机动作的概率）
    
    a_max = np.argwhere(q==np.max(q)).flatten()
    # np.argwhere(q==np.max(q)) 返回一个包含最大 Q 值对应索引的数组。
    # .flatten() 将多维数组压平为一维数组。
    
    policy = np.sum([np.eye(env.nA)[i] for i in a_max], axis=0) / len(a_max)
    # 这里构建了一个策略（policy），其中每个最大的 Q 值动作被赋予相同的选择概率。
    
    # np.eye(env.nA) 创建一个大小为 env.nA 的单位矩阵，4*4
    # array([[1., 0., 0., 0.],
    #        [0., 1., 0., 0.],
    #        [0., 0., 1., 0.],
    #        [0., 0., 0., 1.]])
    # 每一行代表一个动作的 one-hot 编码。
    
    # [np.eye(env.nA)[i] for i in a_max] 选择与 a_max 中索引对应的动作，
    # 生成这些动作的 one-hot 编码。
    # np.sum(..., axis=0) / len(a_max) 对所有这些 one-hot 编码进行平均，
    # 以便将每个最大 Q 值动作的选择概率平均分配。

    if rng.rand() < 1-eps:
        a = rng.choice(env.nA, p=policy) # 按照policy的概率来选 policy为1*4的列表
    else:
        a = rng.choice(env.nA) # 随机来选
    return a 

初始策略决定好，进入Q_learning函数的编写

def Q_learning(env, alpha=.1, eps=.1, gamma=.99, max_epi=2000, 
               seed=1234, theta=1e-4, show_update=False, Q=None):
    # rng
    rng = np.random.RandomState(seed)
    # initialize Q
    if Q is None: Q = np.zeros([env.nS, env.nA])
    for epi in range(max_epi):
        s, r, done = env.reset()
        t = 0 
        q_old = Q.copy()
        G = 0
        while True:
            # sample At, observe Rt, St+1
            # 采样t时刻的action At，观察回报Rt 和 下一个状态St+1
            a = e_greedy(Q[s, :], rng, env, eps) 
            # a = rng.choice(env.A, p=pi)
            s_next, r, done = env.step(a) # move to the next step
            
            # the key step of Q learning
            # 贝尔曼方程
            Q[s, a] = Q[s, a]+ alpha*(r + gamma*(1-done)*(Q[s_next, :]).max() - Q[s, a])
            
            
            s = s_next 
            t += 1
            G += r
            
            if done:
                break 
            
            if show_update:
            #    渲染结果
                Pi = np.eye(env.nA)[np.argmax(Q, axis=1)]
                V = Q.max(1)
                fig, axs = plt.subplots(1, 3, figsize=(11, 4))
                clear_output(True)
                ax = axs[0]
                env.render(ax)
                #print(env.state, s, a)
                ax = axs[1]
                env.show_v(ax, V)
                ax = axs[2]
                env.show_pi(ax, Pi)
                time.sleep(.05)
                plt.show()
                
        if (np.abs(q_old - Q)<theta).all():
            # 采样到收敛
            break
    pi = np.eye(env.nA)[np.argmax(Q, axis=1)] 
    # 选择最优的动作
    return Q, pi

最终的结果

图2 Q learning算法在冰湖游戏中模拟的最终结果