在强化学习领域，Q-Learning是一种经典算法，它属于时序差分控制方法。这篇文章对应Sutton教材第六章和UCL课程第五讲的内容，主要探讨如何通过时序差分求解强化学习的控制问题。
1. Q-Learning算法的引入
Q-Learning是一种使用时序差分（TD）求解强化学习控制问题的方法。回顾一下控制问题的标准设定：给定强化学习的五个要素——状态集 S、动作集 A、即时奖励 R、衰减因子 γ、探索率 ε，目标是求解最优的动作价值函数 q* 和最优策略 π*。
这类问题不需要环境的状态转移模型，属于无模型的强化学习方法。和蒙特卡罗法相似，它也采用价值迭代的思路：通过更新价值函数来改进策略，再用新策略生成新的状态和奖励，进而继续更新价值函数。如此循环，直到价值函数和策略都收敛为止。
时序差分的控制问题可以分成两类。一类是**在线控制**，始终使用同一个策略来更新价值函数和选择动作，比如之前讲过的SARSA。另一类是**离线控制**，使用两个不同的策略：一个用于选择动作，另一个用于更新价值函数。Q-Learning就是后者的典型代表。
在Q-Learning中，选择新动作时仍然使用 ε-贪婪法——这部分和SARSA完全一样。但关键的区别在于：更新价值函数时，Q-Learning采用的是**贪婪法**，而不是SARSA所用的 ε-贪婪法。这正是两者最本质的不同。
2. Q-Learning算法概述
Q-Learning的算法拓扑图如下：
具体来说，先基于当前状态 S，用 ε-贪婪法选择动作 A；然后执行该动作，得到奖励 R，并进入新状态 S'。如果是SARSA，接下来会基于 S' 再用 ε-贪婪法选一个 A'，然后更新价值函数。但Q-Learning的做法完全不同——它基于 S'，直接使用**贪婪法**选择动作 A'，即选取能使 Q(S', a) 最大的那个 a 作为 A'，用来更新价值函数。数学公式如下：
对应到图中，就是在底部三个黑色圆圈动作中，选出一个使 Q(S', a) 最大的动作作为 A'。
注意：这个被选出的动作只参与价值函数的更新，并不会真正执行。更新完价值函数后，下一步要执行的动作还需要基于状态 S'，用 ε-贪婪法重新选择。这和SARSA也不同——在SARSA中，更新价值函数所用的 A' 会直接作为下一阶段的执行动作。
3. Q-Learning算法流程
下面给出完整的算法流程。
算法输入：迭代轮数 T，状态集 S，动作集 A，步长 α，衰减因子 γ，探索率 ε。
输出：所有状态-动作对的价值 Q。
1. 随机初始化所有状态-动作的 Q 值（终止状态的 Q 值设为0）。
2. for i from 1 to T，迭代：
a) 初始化 S 为当前状态的第一个状态。
b) 用 ε-贪婪法在当前状态 S 选择动作 A。
c) 在状态 S 执行动作 A，得到新状态 S' 和奖励 R。
d) 更新价值函数 Q(S, A)：
e) S = S'。
f) 如果 S' 是终止状态，则当前轮迭代结束；否则转到步骤b)。
4. Q-Learning算法实例：Windy GridWorld
还是用和SARSA一样的例子——Windy GridWorld。不了解这个问题的朋友可以回顾一下之前SARSA章节里的介绍。
代码大部分和SARSA相似，主要区别体现在 episode 函数中。
初始化差异：Q-Learning只初始化状态 S，而将动作 A 的生成放到了while循环内部。回忆一下，SARSA会同时初始化 S 和 A，然后再进入循环。下面的代码对应算法步骤2a和2b：
# play for an episode
def episode(q_value):
# track the total time steps in this episode
time = 0
# initialize state
state = START
while state != GOAL:
# choose an action based on epsilon-greedy algorithm
if np.random.binomial(1, EPSILON) == 1:
action = np.random.choice(ACTIONS)
else:
values_ = q_value[state[0], state[1], :]
action = np.random.choice([action_ for action_, value_ in enumerate(values_) if value_ == np.max(values_)])
接下来执行动作 A，得到 S'。由于奖励只有终止时才有变化（否则为-1），这里不单独计算。这部分代码和SARSA相同，对应步骤2c：
next_state = step(state, action)
def step(state, action):
i, j = state
if action == ACTION_UP:
return [max(i - 1 - WIND[j], 0), j]
elif action == ACTION_DOWN:
return [max(min(i + 1 - WIND[j], WORLD_HEIGHT - 1), 0), j]
elif action == ACTION_LEFT:
return [max(i - WIND[j], 0), max(j - 1, 0)]
elif action == ACTION_RIGHT:
return [max(i - WIND[j], 0), min(j + 1, WORLD_WIDTH - 1)]
else:
assert False
然后使用贪婪法选出最大的 Q(S', a)，并更新价值函数，最后更新当前状态。这对应算法步骤2d和2e。注意：SARSA这里是使用 ε-贪婪法，而不是贪婪法；并且SARSA会同时更新状态 S 和动作 A，而Q-Learning只更新当前状态 S：
values_ = q_value[next_state[0], next_state[1], :]
next_action = np.random.choice([action_ for action_, value_ in enumerate(values_) if value_ == np.max(values_)])
# Sarsa update （注：此处代码实际是Q-Learning的更新）
q_value[state[0], state[1], action] +=
ALPHA * (REWARD + q_value[next_state[0], next_state[1], next_action] -
q_value[state[0], state[1], action])
state = next_state
运行完整代码后，可以轻松得到该问题的最优解，以及每个格子中的最优贪婪策略。
5. SARSA vs Q-Learning
现在SARSA和Q-Learning都讲完了，作为时序差分控制的两大经典方法，它们各自有什么特点？适合什么样的场景？
Q-Learning直接学习最优策略，而SARSA在学习最优策略的同时还在进行探索。这意味着，如果使用SARSA，为了保证收敛，需要设置一个策略让 ε-贪婪法中的 ε 在迭代过程中逐渐减小。Q-Learning则没有这个顾虑。
另一个区别是，Q-Learning直接学习最优策略，但这个最优策略依赖于训练过程中产生的数据，因此受样本数据方差的影响较大，有时会干扰Q函数的收敛。深度强化学习中的Deep Q-Learning也存在类似问题。
在学习过程中，SARSA鼓励探索，收敛过程比较平滑，不会像Q-Learning那样过于激进，从而避免落入一些特殊的最优“陷阱”。例如经典的“Cliff Walk”问题就体现了这一差异。
在实际应用中，如果是在模拟环境中训练强化学习模型，推荐使用Q-Learning；如果是在线生产环境中训练模型，则推荐使用SARSA。
6. Q-Learning结语
对于小型强化学习问题，Q-Learning和SARSA这类时序差分算法非常灵活有效。但在大数据时代，状态和动作空间极其复杂，维护一个巨大的Q表会超出内存限制，限制了它们的使用场景。随着深度学习的兴起，基于深度学习的强化学习逐渐成为主流。从下一篇开始，我们将探讨深度强化学习的建模思路。