先前介绍的动态规划(Dynamic programming)的求解方法是基于模型(model-based)的，也就是当我们知道环境 E n v { S , A , P , R } Env\{S,A,P,R\} E n v { S , A , P , R } S S S A A A s s s s ′ s' s ′ P ( s ′ ∣ s , a ) P(s'\mid s, a) P ( s ′ ∣ s , a ) R ( s ′ ) R(s') R ( s ′ )
时间差分学习（Temporal Difference Learning，简称TD学习）是一种强化学习算法，用于通过经验来预测未来奖励或值的估计。TD学习结合了蒙特卡罗方法和动态规划的优点，在不需要模型的情况下进行学习。它通过更新当前估计值，以使其更接近于下一个时刻的估计值，从而逐步改进对价值的预测。
举个例子来方便我们理解时间差分学习算法是怎样工作的。假设你需要预测星期六的天气，并且手头上正好有相关的模型。按照一般的方法，你只有到星期六才能根据结果对你的模型进行调整。然而，当到了星期五时，你应该对星期六的天气有很好的判断。因此在星期六到来之前，你就能够调整你的模型以预测星期六的天气。
让我们回到前面所讲述的贝尔曼期望方程(Bellman equation)，这个方程的含义是在给定策略 π \pi π V V V P ( s ′ ∣ s , a ) P(s'\mid s, a) P ( s ′ ∣ s , a ) V V V
V π ( s t ) = ∑ a π ( a t ∣ s t ) ∑ s t + 1 p ( s t + 1 ∣ s t , a t ) [ r t + γ V π ( s t + 1 ) ] = E a t , s t + 1 ∼ π , p [ r t + γ V π ( s t + 1 ) ] ≈ 1 N ∑ i N r t i + γ V π ( s t + 1 i ) 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} V π ( s t ) = a ∑ π ( a t ∣ s t ) s t + 1 ∑ p ( s t + 1 ∣ s t , a t ) [ r t + γ V π ( s t + 1 ) ] = E a t , s t + 1 ∼ π , p [ r t + γ V π ( s t + 1 ) ] ≈ N 1 i ∑ N r t i + γ V π ( s t + 1 i ) 那能不能更简单一点呢？——将 N N N { r t + γ V π ( s t + 1 i ) − V π ( s t ) } \{r_t + \gamma V^\pi\left(s_{t+1}^i\right) - V^\pi\left(s_t\right)\} { r t + γ V π ( s t + 1 i ) − V π ( s t ) }
V π ( s t ) ≈ r t + γ V π ( s t + 1 ) = V π ( s t ) + r t + γ V π ( s t + 1 ) − V π ( s t ) \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} V π ( s t ) ≈ r t + γ V π ( s t + 1 ) = V π ( s t ) + r t + γ V π ( s t + 1 ) − V π ( s t ) 显然直接带入 N = 1 N=1 N = 1 α \alpha α r t + γ V π ( s t + 1 ) r_t + \gamma V^\pi\left(s_{t+1}\right) r t + γ V π ( s t + 1 ) r t + γ V π ( s t + 1 ) − V π ( s t ) r_t + \gamma V^\pi\left(s_{t+1}\right) - V^\pi\left(s_t\right) r t + γ V π ( s t + 1 ) − V π ( s t )
V π ( s t ) = V π ( s t ) + α ( r t + γ V π ( s t + 1 ) − V π ( s t ) ) \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} V π ( s t ) = V π ( s t ) + α ( r t + γ V π ( s t + 1 ) − V π ( s t ) ) 推出这个公式有什么用呢？在这个公式下，我们的目标是让模型对状态 s s s V V V a t a_t a t s t + 1 s_{t+1} s t + 1 r t + 1 r_{t+1} r t + 1 s t + 1 s_{t+1} s t + 1 V V V
对于一个强化学习的任务，我们需要agent面对状态 s t s_{t} s t a t a_t a t Q Q Q
下面是贝尔曼方程的动作价值函数 Q Q Q
Q π ( s t , a t ) = ∑ s t + 1 p ( s t + 1 ∣ s t , a t ) [ r t + γ max a Q π ( s t + 1 , a ) ] \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} Q π ( s t , a t ) = s t + 1 ∑ p ( s t + 1 ∣ s t , a t ) [ r t + γ a max Q π ( s t + 1 , a ) ] Q π ( s t , a t ) = Q π ( s t , a t ) + α ( r + γ max a Q π ( s t + 1 , a ) − Q π ( s t , a t ) ) \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} Q π ( s t , a t ) = Q π ( s t , a t ) + α ( r + γ a max Q π ( s t + 1 , a ) − Q π ( s t , a t ) ) 接下来，我们以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为终点，蓝色方块为障碍物。
首先建立需要用到的参数
复制 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 最终的结果
