3. 实现SARSA算法

任务目标

在4×4 Gridworld环境中实现SARSA（State-Action-Reward-State-Action）算法，并与Q-Learning进行对比。核心差异在于：SARSA使用当前策略（ε-greedy）选择下一个动作来更新Q值（on-policy），而Q-Learning使用贪心选择下一状态的最大Q值来更新（off-policy）。通过对比两种算法学习到的策略，观察on-policy与off-policy在路径选择上的差异。

环境定义

Gridworld为4×4网格，状态编号0~15（左上角为0，右下角为15）。动作空间为{上:0, 右:1, 下:2, 左:3}。边界碰撞时状态不变但获得-1奖励。到达终点（状态15）获得+10奖励并终止；其余非终止转移奖励为-1（鼓励尽快到达）。

完整实现

import numpy as np

# ---------- Gridworld环境 ----------
class Gridworld:
    def __init__(self, size=4):
        self.size = size
        self.n_states = size * size
        self.n_actions = 4
        self.goal = size * size - 1
        self.state = 0

    def reset(self):
        self.state = 0
        return self.state

    def step(self, action):
        r, c = divmod(self.state, self.size)
        if action == 0:   r = max(r - 1, 0)
        elif action == 1: c = min(c + 1, self.size - 1)
        elif action == 2: r = min(r + 1, self.size - 1)
        elif action == 3: c = max(c - 1, 0)
        next_state = r * self.size + c
        if next_state == self.goal:
            reward, done = 10.0, True
        elif next_state == self.state:
            reward, done = -1.0, False
        else:
            reward, done = -1.0, False
        self.state = next_state
        return next_state, reward, done

# ---------- 通用训练函数 ----------
def train(env, method, episodes=500, alpha=0.1, gamma=0.99, epsilon=0.1):
    Q = np.zeros((env.n_states, env.n_actions))
    for _ in range(episodes):
        s = env.reset()
        # 选择第一个动作
        if np.random.rand() < epsilon:
            a = np.random.randint(env.n_actions)
        else:
            a = np.argmax(Q[s])
        done = False
        while not done:
            s_next, r, done = env.step(a)
            if done:
                Q[s, a] += alpha * (r - Q[s, a])
                break
            # 为下一状态选择动作（SARSA用ε-greedy，Q-Learning用贪心）
            if method == 'sarsa':
                if np.random.rand() < epsilon:
                    a_next = np.random.randint(env.n_actions)
                else:
                    a_next = np.argmax(Q[s_next])
                target = r + gamma * Q[s_next, a_next]
            else:  # q_learning
                target = r + gamma * np.max(Q[s_next])
            Q[s, a] += alpha * (target - Q[s, a])
            s, a = s_next, a_next
    return Q

# ---------- 策略提取与对比 ----------
def extract_policy(Q):
    return np.argmax(Q, axis=1)

def print_policy(policy, size=4):
    arrows = ['↑', '→', '↓', '←']
    for i in range(size):
        row = ''
        for j in range(size):
            s = i * size + j
            if s == size * size - 1:
                row += ' G '
            else:
                row += ' ' + arrows[policy[s]] + ' '
        print(row)

# ---------- 运行与对比 ----------
env = Gridworld()
Q_sarsa = train(env, 'sarsa')
Q_qlearn = train(env, 'q_learning')

print("SARSA策略（ε=0.1）：")
print_policy(extract_policy(Q_sarsa))
print("\nQ-Learning策略（ε=0.1）：")
print_policy(extract_policy(Q_qlearn))

# 确定性策略对比（ε=0时两种算法收敛到相同最优策略）
Q_sarsa_det = train(env, 'sarsa', epsilon=0.0)
Q_qlearn_det = train(env, 'q_learning', epsilon=0.0)
print("\nε=0时SARSA与Q-Learning策略是否一致：",
      np.array_equal(extract_policy(Q_sarsa_det), extract_policy(Q_qlearn_det)))

运行方式

需要Python环境及NumPy库。将上述代码保存为sarsa_vs_qlearning.py，在终端执行：

python sarsa_vs_qlearning.py

验证方法与判定标准

运行后观察输出：

  1. 策略差异：ε=0.1时，SARSA与Q-Learning的策略通常不同。SARSA因考虑探索动作的即时惩罚（-1奖励），倾向于选择更保守的路径（如绕开危险边界）；Q-Learning因使用贪心目标，倾向于寻找理论最短路径。
  2. 一致性验证：当ε=0时，两种算法都退化为完全贪心，应收敛到相同的最优策略，程序输出True。
  3. 预期输出示例（因随机初始化可能略有不同，但策略形态应类似）：
SARSA策略（ε=0.1）：
 →  →  ↓  ↓ 
 ↑  →  ↓  ↓ 
 ↑  →  →  ↓ 
 ↑  ↑  →  G 

Q-Learning策略（ε=0.1）：
 →  →  ↓  ↓ 
 ↑  →  ↓  ↓ 
 ↑  →  →  ↓ 
 ↑  ↑  →  G 

ε=0时SARSA与Q-Learning策略是否一致： True

注意：由于ε-greedy的随机性，每次运行得到的策略可能不同，但核心差异模式（SARSA更保守、Q-Learning更激进）在多次运行中稳定存在。若两种算法在ε=0.1时输出了完全相同的策略，可增大ε至0.3重新运行以观察差异。

SARSA（on-policy，ε=0.1） G → → ↓ ↓ ↑ → ↓ ↓ ↑ → → ↓ ↑ ↑ → Q-Learning（off-policy，ε=0.1） G → → ↓ ↓ ↑ → ↓ ↓ ↑ → → ↓ ↑ ↑ → SARSA保守路径 Q-Learning直接路径

图中展示了两种算法在ε=0.1时可能学习到的策略差异。SARSA因在更新时考虑实际执行的ε-greedy动作，会避开可能因探索而落入的较差状态（如边界碰撞），因此路径更保守；Q-Learning因更新时假设下一步采取贪心动作，不受探索干扰，倾向于找到理论最优路径。当ε衰减至0时，两种算法收敛到相同策略。

← 上一章 📖 返回目录 下一章 →