强化学习 3.表格型方法（实验部分）

发表于 更新于

前言

从零开始学习ai文章系列计划是个人在《动手学深度学习》和《磨菇书》两本书的学习中的个人笔记，文章也会以课本中的章节分开，即每个章节一片笔记。我会尽量的把主要内容以及遇到的难点进行记录与解决，如果哪里有错误的欢迎指正。或者不清晰的可以直接查看原文部分。

《蘑菇书》原文（课本）：https://datawhalechina.github.io/easy-rl/#/

（由于有时候公式太多，可能会直接贴图片）

蘑菇书的文章结构不会跟之前《动手学深度学习》按照原文章节进行，个人会适当调节。

1.蒙特卡洛

1.1 环境

首先介绍我们测试的环境：CliffWalking-v0

这是一个 4x12 的方块环境，可以理解成状态为4x12个坐标，agent需要从左下角出发走到右下角。每走一步获得奖励-1。

动作空间为 (上, 下, 左, 右)。

接下来我们创建环境并设置需要的超参数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 创建环境
env = gym.make("CliffWalking-v0")
n_states = env.observation_space.n      # 48
n_actions = env.action_space.n          # 4 (上下左右)
# 初始化 Q 表
Q = np.zeros((n_states, n_actions))

# 访问计数，用于平均回报
returns_count = np.zeros((n_states, n_actions))

# 超参数
epsilon = 0.5         # 探索率
gamma = 1.0            # CliffWalking 通常 γ=1
num_episodes = 2000    
total_reward_list = []  # 打印总奖励用的

1.2 算法

我们使用蒙特卡洛方法和 ε-贪心探索的结合算法。

流程代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

for episode in range(num_episodes):
    state, info = env.reset()
    sar_list = []
    epsilon *= 0.9990
    # ---- 1. 采集一个 episode 的sar----
    gather_sar(state,sar_list)

    # ---- 2. 计算每一步的 G_t ----
    returns = compute_returns(sar_list, gamma)

    # ---- 3. Q表更新 （只更新我们走过的路的状态）----
    Q_update_1(sar_list)
    
    # 打印
    total_reward_list.append(sum(r for (_, _, r) in sar_list))
    if episode%50==0:
        print(f"{episode}/{num_episodes}")

1.3 轨迹链采集

首先要介绍我们使用的策略：ε-贪心探索。ε的概率随机动作，1-ε的概率选最优Q值的动作。如果当前最优动作a有多个的话就随机一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def epsilon_greedy(Q, state, n_actions, epsilon):
    """
    Q: Q-table
    state: 当前状态
    n_actions: 动作数量
    epsilon: 探索概率
    """
    def argmax_random(q_values):
        max_value = np.max(q_values)
        candidates = np.flatnonzero(q_values == max_value)  # 找到所有最大值索引
        return np.random.choice(candidates)  # 随机选一个
    
    if np.random.rand() < epsilon:
        return np.random.randint(n_actions)
    else:
        return argmax_random(Q[state])

这里要注意epison的设置，由于前期没有好策略，我们需要足够随机，由于后期策略差不多了，我们要收敛.

这里我初始设置为0.5，根据episode每次乘以0.999。

有了策略后，我们现在开始收集轨迹链，将每一步执行的 (s,a,r) 添加到列表 sar_list 中。

1
2
3
4
5
6
7
8
9
10
def gather_sar(init_state,sar_list):
    # ---- 采集一个 episode 的sar----
    state=init_state
    done = False
    while not done:
        action = epsilon_greedy(Q, state, n_actions, epsilon)
        next_state, reward, terminated, truncated, info = env.step(action)
        done = terminated or truncated
        sar_list.append((state, action, reward))
        state = next_state

1.4 计算Gt

代码中可以看出我们从后往前计算每一步的回报G。

1
2
3
4
5
6
7
8
9
10
11
12
13
def compute_returns(sar_list, gamma=1.0):
    """
    输入：[(s0,a0,r0), (s1,a1,r1), ...]
    输出：[G0, G1, ...]
    """
    G = 0
    returns = []
    # 从后往前计算累计回报
    for (_, _, r) in reversed(sar_list):
        G = r + gamma * G
        returns.append(G)
    returns.reverse()
    return returns

1.5 Q表更新

首先得说明在蒙特卡洛中，有两种更新方式：

  1. First-Visit 更新：每个状态在一条轨迹中只用第一次出现时的回报来更新一次
  2. Every-Visit 更新：每个状态在一条轨迹中每次出现都会用对应回报去更新

First-Visit 相比于Every-Visit，First-Visit 更接近独立采样的假设。

Every-Visit中，同一条轨迹里，一个状态可能贡献 多次相似的样本。

First-Visit 中，每条轨迹对一个状态只贡献一次，因此更像“独立采样”，避免了对同一条轨迹的“重复计数”，减少了相关性带来的噪声。

1
2
3
4
5
6
7
8
9
10
def Q_update_1(sar_list):
    # ---- 3. First-Visit MC 更新 ----
    visited = set()
    for i, (s, a, r) in enumerate(sar_list):
        if (s, a) not in visited:     # First-Visit 检测
            visited.add((s, a))
            G = returns[i]

            returns_count[s, a] += 1
            Q[s, a] += (G - Q[s, a]) / returns_count[s, a]   # 增量式平均
1
2
3
4
5
6
7
def Q_update_2(sar_list):
    # ---- 3. Every-Visit MC 更新 ----
    for i, (s, a, r) in enumerate(sar_list):
        G = returns[i]  # 当前位置开始的回报

        returns_count[s, a] += 1
        Q[s, a] += (G - Q[s, a]) / returns_count[s, a]  # 增量式平均

1.6 打印

我们可以将Q表中最优的结果拿出来，然后按照4x12和环境一样的表格打印出来，用来查看我们最终的结果。

同时我们也将每个episode对应的total reward打印出来，查看我们的训练变化

1
2
3
4
5
6
policy = np.argmax(Q, axis=1)

print("\n训练完成！最终策略如下（0上 1右 2下 3左）：")
print(policy.reshape(4, 12))

draw(total_reward_list)

查看结果，红线是以每个数字右下角为点，按照数字方向连起来的一条线。

接下来我们查看 First-Visit 和 Every-Visit 的效果图。

First-Visit：

Every-Visit

2. Sarsa/TD(0) 与Q学习

2.1 环境

首先介绍我们测试的环境：CliffWalking-v0

这是一个 4x12 的方块环境，可以理解成状态为4x12个坐标，agent需要从左下角出发走到右下角。每走一步获得奖励-1。

动作空间为 (上, 下, 左, 右)。

接下来我们创建环境并设置需要的超参数：

1
2
3
4
5
6
7
8
9
10
11
12
env = gym.make("CliffWalking-v0")
n_states = env.observation_space.n      # 48
n_actions = env.action_space.n          # 4 (上下左右)
# 初始化 Q 表
Q = np.zeros((n_states, n_actions))

epsilon = 0.5     # 设置 ε
alpha = 0.1       # 学习率
gamma = 0.99      # 折扣因子

total_reward_list = []
num_episodes = 5000

2.2 算法

我们使用sarsa和 ε-贪心探索的结合算法。

流程代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
for episode in range(num_episodes):
    state, info = env.reset()
    done = False
    total_reward = 0
    epsilon*=0.999

    # 1. 策略执行，与环境交互
    action = epsilon_greedy(Q, state, n_actions, epsilon)
    while not done:
        next_state, reward, terminated, truncated, info = env.step(action)
        done = terminated or truncated

        next_action = epsilon_greedy(Q, next_state, n_actions, epsilon)

        # 2.Q表更新
        Q_update(state, action, reward, next_state, next_action, done)

        state = next_state
        action = next_action
        total_reward += reward

我们能够看出，Q表的更新发生在每一步策略执行后。

我们使用的策略还是ε-贪心探索，因此使用和之前蒙特卡洛一样的函数epsilon_greedy。

2.3 Q表更新

在正常sarsa算法中，由于sarsa是同策略的算法，因此next_action也应该有当前的策略生成，代码如下：

1
2
3
4
5
def Q_update(state,action,reward,next_state,action2,done):
    # TD 更新（sarsa）
    next_q = Q[next_state][action2]

    Q[state, action] += alpha * (reward + gamma * next_q*(1-done) - Q[state, action])

但是在Q学习中，我们的next_action仅取最优的那一个，因此在这里的小幅改动就能将sarsa转换成了Q学习：

1
2
3
4
5
def Q_update(state,action,reward,next_state,action2,done):
    # TD 更新（Q-learning）
    next_q = np.max(Q[next_state])

    Q[state, action] += alpha * (reward + gamma * next_q*(1-done) - Q[state, action])

2.4 打印查看结果

和之前一样打印出我们最终的Q表和总奖励

sarsa:

Q学习：

虽然看上去更加波动了，但仔细查看。实际上q学习的总分相比之前的sarsa更加接近0。（因为Q学习学出来的是风险更高，但是收益更高的路线。）

3. sarsa(λ)

3.1 环境

首先介绍我们测试的环境：CliffWalking-v0

这是一个 4x12 的方块环境，可以理解成状态为4x12个坐标，agent需要从左下角出发走到右下角。每走一步获得奖励-1。

动作空间为 (上, 下, 左, 右)。

首先还是先创建环境以及设置超参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
env = gym.make("CliffWalking-v0")

n_states = env.observation_space.n
n_actions = env.action_space.n

# 初始化 Q
Q = np.zeros((n_states, n_actions))

# SARSA(λ) 参数
epsilon = 0.5
alpha = 0.1
gamma = 0.99
_lambda = 0.9       # λ 参数

total_reward_list = []
num_episodes = 5000

3.2 算法流程

流程和sarsa的时候一样，区别在Q表更新的时候，我们使用了新的方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
for episode in range(num_episodes):
    state, info = env.reset()
    done = False
    total_reward = 0

    # 初始化迹
    E = np.zeros_like(Q)

    # ε-贪心选择动作
    action = epsilon_greedy(Q, state, n_actions, epsilon)
    epsilon *= 0.999
    while not done:
        # 1. 策略执行，与环境交互
        next_state, reward, terminated, truncated, info = env.step(action)
        done = terminated or truncated

        # 选择下一个动作（sarsa）
        next_action = epsilon_greedy(Q, next_state, n_actions, epsilon)
        
        # 2. Q表更新
        Q_update(Q, E, state, action, reward, next_state, next_action, done)

        state = next_state
        action = next_action
        total_reward += reward

3.3 Q表更新

回忆我们理论部分，TD误差的计算公式： \[ r_{t+1}+\gamma Q(s_{t+1},a_{t+1})-Q(s_{t},a_{t}) \] 这里的下一动作 \(a_{t+1}\) 必须是实际执行的动作。因为按照原本的定义，λ-return是轨迹链中各个步数的回报加权和。

除此外，资格迹可以通过累计迹或替换迹实现，这里我们使用替换迹：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def Q_update(Q, E, state, action, reward, next_state, next_action, done):
    # TD 误差
    td_target = reward + (0 if done else gamma * Q[next_state, next_action])
    td_error = td_target - Q[state, action]

    # 资格迹递减
    E *= gamma * _lambda

    # 累积迹
    # E[state, action] += 1

    # 替换迹
    E[state, action] = 1

    # 用所有迹更新 Q
    Q += alpha * td_error * E

3.4 查看结果