作业 · Q-learning 房间导航实验

Views: --
#机器学习 #AI #作业

这篇按作业目录中现存的 try.py 还原实验。源目录没有单独的题目说明或报告，因此以下任务定义来自程序本身：智能体在 A～H 八个状态之间移动，目标是到达 D，并通过 Q-learning 学出每个状态的最佳下一步。

关于算法原理可先看第七讲 · 强化学习与 Q-learning。这里重点看一次具体实验怎样从奖励矩阵变成路径。

环境与奖励

Q-learning 八状态导航图

合法连接如下：

  • A ↔ E；
  • B ↔ C，B ↔ F；
  • C ↔ G，C → D；
  • E ↔ F；
  • F ↔ G；
  • G ↔ H。

程序用一个 8×88\times8 奖励矩阵 RR 表示环境：

  • 无连接的动作奖励为 −1-1，同时不允许被采样；
  • 普通合法转移奖励为 00；
  • C → D 的奖励为 100100；
  • 奖励矩阵还保留 D → C 的普通合法转移，但程序把 D 当作终止状态，不从 D 开始，进入 D 后也立即结束，因此这一步不会被执行。

按 A～H 排列，矩阵是：

R=[−1−1−1−10−1−1−1−1−10−1−10−1−1−10−1100−1−10−1−1−10−1−1−1−1−10−1−1−1−10−1−1−10−1−10−10−1−1−10−1−10−10−1−1−1−1−1−10−1]R=\begin{bmatrix} -1&-1&-1&-1&0&-1&-1&-1\\ -1&-1&0&-1&-1&0&-1&-1\\ -1&0&-1&100&-1&-1&0&-1\\ -1&-1&0&-1&-1&-1&-1&-1\\ 0&-1&-1&-1&-1&0&-1&-1\\ -1&0&-1&-1&0&-1&0&-1\\ -1&-1&0&-1&-1&0&-1&0\\ -1&-1&-1&-1&-1&-1&0&-1 \end{bmatrix}

注意，矩阵中的 −1-1 在这份实现里主要充当“不合法”标记。训练只从 R[s,a]≥0R[s,a]\ge0 的动作中随机采样，所以智能体不会真的执行非法动作并获得 −1-1。

Q-learning 更新

程序把 Q 表初始化为全 0，使用：

Q(s,a)←Q(s,a)+α[r+γmax⁡a′Q(s′,a′)−Q(s,a)]Q(s,a)\leftarrow Q(s,a)+\alpha \left[ r+\gamma\max_{a'}Q(s',a')-Q(s,a) \right]

参数为：

参数值含义
α\alpha0.8新估计写入 Q 表的速度
γ\gamma0.95未来奖励的折扣因子
episodes1000随机起点训练轮数

每轮从任意状态随机开始，在当前状态所有合法动作中均匀随机选一个，更新 Q 值，直到到达 D。这里没有使用 ϵ\epsilon-greedy：训练阶段一直随机探索；贪心选择只用于训练后的路径展示。

一次更新怎样传播终点奖励

假设首次经历 C → D。因为 D 没有后续价值，更新为：

Q(C,D)=0+0.8(100−0)=80Q(C,D)=0+0.8(100-0)=80

再次经历时：

Q(C,D)=80+0.8(100−80)=96Q(C,D)=80+0.8(100-80)=96

它会逐渐逼近 100。随后若经历 B → C，C 的最大 Q 值已经接近 100：

Q(B,C)→0+0.95×100=95Q(B,C)\to 0+0.95\times100=95

距离终点再远一步的动作趋近 0.952×100=90.250.95^2\times100=90.25。终点奖励就这样从 C 逐层向外传播。

运行结果

直接运行现有程序后，各状态打印出的最佳动作及其 Q 值为：

当前状态最佳动作Q 值
AE81.45
BC95.00
CD100.00
D无0.00
EF85.74
FB90.25
GC95.00
HG90.25

这些数值与理论距离正好对应：

Q∗(s,a)=100×0.95d(s′,D)Q^*(s,a)=100\times0.95^{d(s',D)}

其中 d(s′,D)d(s',D) 是执行动作后，从新状态 s′s' 到 D 还需多少次转移。例如 A → E 后还需 E → F → B → C → D，共 4 次转移，因而：

Q(A,E)=100×0.954≈81.45Q(A,E)=100\times0.95^4\approx81.45

程序给出的各起点路径是：

起点贪心路径
AA → E → F → B → C → D
BB → C → D
CC → D
DD
EE → F → B → C → D
FF → B → C → D
GG → C → D
HH → G → C → D

F → B 与 F → G 都能以相同步数到达 D，所以两者的最优 Q 值理论上相同。程序使用 argmax，并列时返回下标更小的 B，因此展示 F → B；这不代表 F → G 是错误路径。

代码结构的关键点

这份实现的流程可以压缩为：

for _ in range(1000):
    state = random_state()
    while state != goal:
        action = random_valid_action(state)
        td_target = reward[state, action] + gamma * max(q[action])
        q[state, action] += alpha * (td_target - q[state, action])
        state = action

这里把“动作编号”和“到达的新状态编号”设为同一个值，因此 q[action] 就是下一状态整行 Q 值。对这个房间跳转任务很简洁，但更一般的环境应由 step(action) 显式返回 next_state，两者不能默认相等。

可以怎样改进实验

  • 固定随机种子并报告多次运行，确认结果稳定；
  • 对并列最优动作随机选择，展示所有等价最短路径；
  • 加入每轮最大步数，避免环境改变后出现无穷循环；
  • 把非法动作完全移出动作集合，而不只用 −1-1 标记；
  • 记录 Q 表误差或成功率随 episode 的变化，画出学习曲线；
  • 若允许负步长奖励，可比较“最短路径偏好”如何变化。

实验结论

Q-learning 不需要预先知道最佳路径，只需要状态转移产生的奖励。通过时序差分更新，C → D 的即时奖励逐步传播到更远状态，最终每一行 Q 表都编码了“从这里走哪一步最有价值”。本实验环境是确定性的，合法边奖励简单且训练遍历充分，所以学出的贪心策略与最短路径一致。

评论