Q 学习

Q 学习从经验估计在某状态采取某动作的价值。每次转移只更新一个 Q 表项，使用观察到的奖励与下一状态的最大估计价值。多次访问让延迟奖励影响前面的选择，不需要预先知道环境转移模型。

像每个路口的路牌：到达奖励出口后，先改最后一个箭头；下次经过前一个路口，它才能读到改善的估计。奖励不会一次重写整条路线。本课比较下一步的 +1 与三步后的 +5，地图虽对读者可见，更新器只用实际走过的经验。

一次经验改变一个估计

状态是位置，动作是合法移动，环境返回即时奖励与下一状态。Q(s,a) 估计采取 a 后、继续按最优策略行动的折扣回报，训练早期可能很不准。它不是动作概率。

回合从起点到出口。新回合重置位置，保留 Q 表。对观察 (s,a,r,s')：

future = max over legal a' of Q(s', a')
target = r + gamma * future
Q(s, a) <- Q(s, a) + alpha * (target - Q(s, a))

奖励 r 已观察，future 仍是估计。target − Q(s,a) 是时序差分误差。本课 alpha = 0.5，向目标移动一半；目标较低也会把 Q 拉低。终止状态 future 为零，出口奖励已经包含在 r 中，不能重复计算。其他表项不动。

折扣与探索

折扣 gamma 每次转移计一次。第三步获得 5，对起点回报贡献 gamma² × 5；gamma = 0.9 得 4.05，第一步的 1 不折扣。gamma = 0 只看即时奖励。改 gamma 是改目标，不只是改学习速度。

epsilon-greedy 以 epsilon 概率均匀随机选合法动作，否则选当前最大 Q。随机也可能选到同一个最优动作，所以“探索”描述抽样方式，不代表动作一定较差。

Q 学习是离策略：目标使用下一状态最大值，即使行为策略随后选了别的动作。SARSA 则用实际采样的下一动作构造在策略目标，两种规则回答不同策略的问题。

逐步演示

默认两行三列：

S 合法动作按顺序为上、右；A 为右、左；B 为上、左。进入任一出口拿奖励并终止，其他移动奖励零。墙和边界使动作不可用，显示破折号，不是零估计。

合法 Q 全零，alpha = 0.5、epsilon = 0.35、gamma = 0.9，八回合，随机种子 947。贪心同分按上述动作顺序，所以起点最初选上。每回合最多八次转移，默认最长五次，截断不影响默认轨迹。

回合 1：S 向上拿 1，终止未来为零，目标一，Q(S,上) = 0 + 0.5×(1−0) = 0.5，向右仍零。

回合 2：探索向右到 A，奖励和 A 的估计都零，起点向右不变；A 到 B 的目标也零；B 向上到目标才拿 5，Q(B,上) = 2.5。前两次更新已经发生，不会回头自动改写。

回合 3：S 到 A 时目标仍零。随后 A 到 B 读到 Q(B,上) = 2.5，目标 0.9×2.5 = 2.25，Q(A,右) = 1.125。再次到目标让 B 向上从 2.5 升至 3.75。

回合 4：探索从 S 向右，读 A 最佳估计 1.125，目标 1.0125，使 Q(S,右) = 0.50625，刚超过向上 0.5，贪心箭头改向右，随后到达目标。

每个路牌在对应动作再次被尝试时才改善。首次到达目标之前，S、A 已用零目标更新完，需后续访问才读到新值。

回合 5：路径 S → A → B → A → B → 目标。首次 A 到 B 时，B 向上 4.375、向左零，Q 学习目标 3.9375，使 A 向右从 2.25 升至 3.09375。随后探索却从 B 向左。目标使用最佳后续，而行为绕路；若改用此时采样的左动作，目标会为零，A 向右变 1.125。

回合 6–8：重复直接路线，最后 S 向右约 3.27480、向上仍 0.5。选择改善，但估计未全精确。

最后冻结表、取消探索，走 S → A → B → 目标，实际折扣回报 4.05。这是执行所得回报，与学得估计 3.27480 不同。有限演示说明价值传播，不证明收敛。

何时适合用表

状态与合法动作可枚举、可反复访问时，表方法易检查。更新需要转移经验，不需要“正确动作”标签。若已知转移和奖励，可直接规划，应比较规划与采集经验的成本。

epsilon 控制采集经验，gamma 定义延迟奖励的权重。为了让结果看起来更快而降 gamma，是解另一个问题。探索训练与冻结后的贪心评估应分开，随机绕路不等于学得策略偏好。

复杂度

S 个状态、每状态最多 A 个合法动作，空间 O(SA)。线性扫描做贪心选择或下一状态最大值是 O(A)，写一项 O(1)，T 次经验总计 O(TA)。本图三个非终止状态、各两动作，所以每步为常量成本。

发现奖励需要多少经验是另一问题，可能远比写表昂贵。动画快照另占内存，不属于算法基本成本。连续或海量状态不能实用地各存一项，函数近似可共享信息，也增加本课未涉及的训练难题。

边界情况

• 无探索：epsilon 零、gamma 0.9，在零初始化和同分规则下八次都走小出口。S 向上约 0.99609、向右零；未试动作没有证据。
• 只看即时：gamma 零、epsilon 0.35，即使遇到大目标，A 向右和 S 向右仍零，最后 S 向上 0.9375。偏好上符合当前目标。
• 总探索：epsilon 一让行为全随机，目标仍取最大值，最后评估仍贪心。八回合不保证收集足够经验。
• 终止与截断：出口令未来为零；八步上限不改变环境状态的非终止性，最后转移仍 bootstrap。冻结确定性执行若重复状态，报告策略循环。
• 同分：固定动作序便于复现，随机破同分会产生其他经验。

常见错误

• 把 Q 当最后即时奖励，漏掉未来估计。
• 奖励一到就更新所有前序状态；单步 Q 学习只改当前经验对，前序需再访问。
• 在 r 与终止 bootstrap 中重复加出口奖励。
• 对不可用动作取最大值。破折号不能参加 argmax，即使所有合法值为负。
• 把探索轨迹当冻结贪心策略。
• 用八个成功回合宣称最优。经典收敛结果需充分重复采样与合适学习率条件，固定 alpha 的短轨迹不满足证明，见 Watkins 与 Dayan 原论文。

模型范围

确定性网格、状态相关合法动作、表估计、固定学习率、挑选的随机种子与短预算。随机转移、大状态空间、深度 Q 学习的函数近似、经验回放和目标网络均未建模。读者看到地图，学习规则仍只读转移样本，不使用已知模型规划。