设计Q-learning算法解决悬崖行走问题

题目

设计Q-learning算法解决悬崖行走问题

信息

• 类型：问答
• 难度：⭐⭐

考点

Q-learning原理, 环境建模, 超参数调整, 探索-利用权衡

快速回答

解决悬崖行走问题的Q-learning实现要点：

• 定义4x12网格环境，设置悬崖区域和终止状态
• 使用Q-table存储状态-动作值，初始化为零
• 实现ε-greedy策略平衡探索与利用
• 更新规则：Q(s,a) = Q(s,a) + α[r + γmaxa'Q(s',a') - Q(s,a)]
• 关键参数：学习率α=0.1，折扣因子γ=0.9，探索率ε=0.1
• 终止条件：到达目标或跌入悬崖（负奖励）

问题描述

悬崖行走是一个4x12网格世界：

• 起点(0,0)，目标(3,11)
• 底部一行(3,1)到(3,10)是悬崖（跌入得-100奖励）
• 每次移动奖励-1，到达目标奖励+10
• 动作空间：上/下/左/右（碰到边界保持原位）

Q-learning原理

时序差分算法：

• 更新公式：Q(s,a) ← Q(s,a) + α[r + γmaxa'Q(s',a') - Q(s,a)]
• γ（折扣因子）：平衡当前与未来奖励，建议0.9
• α（学习率）：控制更新步长，建议0.1-0.5
• ε-greedy：以ε概率随机探索，否则选择最优动作

Python实现示例

import numpy as np

# 环境参数
GRID_HEIGHT, GRID_WIDTH = 4, 12
START, GOAL = (0, 0), (3, 11)
CLIFF = [(3, i) for i in range(1, 11)]

# Q-learning参数
alpha = 0.1  # 学习率
gamma = 0.9  # 折扣因子
epsilon = 0.1  # 探索率

# 初始化Q-table
q_table = np.zeros((GRID_HEIGHT, GRID_WIDTH, 4))  # 4个动作

# 动作映射（上:0, 右:1, 下:2, 左:3）
actions = [(-1,0), (0,1), (1,0), (0,-1)]

# 训练循环
for episode in range(500):
    state = START
    while state != GOAL and state not in CLIFF:
        # ε-greedy选择动作
        if np.random.random() < epsilon:
            action = np.random.randint(4)
        else:
            action = np.argmax(q_table[state])

        # 执行动作
        dy, dx = actions[action]
        next_state = (max(0, min(state[0]+dy, GRID_HEIGHT-1)), 
                      max(0, min(state[1]+dx, GRID_WIDTH-1)))

        # 计算奖励
        if next_state in CLIFF:
            reward = -100
        elif next_state == GOAL:
            reward = 10
        else:
            reward = -1

        # Q-table更新
        current_q = q_table[state][action]
        next_max_q = np.max(q_table[next_state])
        new_q = current_q + alpha * (reward + gamma * next_max_q - current_q)
        q_table[state][action] = new_q

        state = next_state if reward != -100 else START  # 跌崖重置

最佳实践

• 参数调优：通过网格搜索调整α/γ/ε
• 探索策略：使用ε衰减（如ε=1/episode）提升后期稳定性
• 性能监控：记录每轮步数和奖励评估收敛性
• 可视化：绘制学习曲线和最终路径

常见错误

• Q值不收敛：学习率过高导致振荡，应减小α或增加衰减
• 陷入局部最优：探索率ε过低，尝试动态调整策略
• 悬崖边缘徘徊：γ过高使智能体过度关注远期奖励，可降低至0.6-0.8
• 更新公式错误：忘记折扣因子γ或误用当前动作值

扩展知识

• 改进方案：使用SARSA更安全（避免悬崖边缘最优路径风险）
• 高级方法：DQN处理更大状态空间，优先经验回放提升效率
• 收敛证明：Q-learning在有限MDP中能以概率1收敛到最优策略
• 实际应用：机器人路径规划、游戏AI（如AlphaGo的蒙特卡洛树搜索）