摘要

本系列知识点讲解基于蘑菇书EasyRL中的内容进行详细的疑难点分析！具体内容请阅读蘑菇书EasyRL！

---

对应蘑菇书EasyRL——3.4 免模型控制

---

Sarsa 算法详细推导与示例

1. Sarsa 算法简介

Sarsa（State-Action-Reward-State-Action）是一种基于时序差分（TD, Temporal Difference）的强化学习算法，用于学习最优策略。它是一种在线学习算法，使用贪心策略或ε-贪心策略进行探索，并逐步更新状态-动作值函数 $Q(s,a)$。

Sarsa 的核心思想是：

在每个时间步 $t$，基于当前状态 $S_t$ 和动作 $A_t$，计算下一步的状态 $S_{t+1}$ 和动作 $A_{t+1}$，并使用 $(S_t,A_t,R_{t+1},S_{t+1},A_{t+1})$ 这 五元组 来更新 Q 值。

---

2. Sarsa 算法推导

在强化学习中，我们希望学得最优状态-动作值函数：
$$Q^{\ast }(s,a)=\underset{\pi }{\max }{Q}^{\pi }(s,a)$$
其中：

• $Q^{\pi }(s,a)$ 是策略 $\pi$ 下的状态-动作值函数
• 我们希望找到最优策略 ${\pi }^{\ast }$，使得智能体在每个状态 $s$ 选择的动作 $a$ 最大化其未来累积奖励。

（1）Q 值的 Bellman 公式

回顾 Q 值的 Bellman 方程：
$$Q^{\pi }(s,a)=\mathbb{E}\left[R_{t+1}+\gamma Q^{\pi }(S_{t+1},A_{t+1})\mid S_t=s,A_t=a\right]$$
其中：

• $R_{t+1}$ 是采取动作 $A_t$ 后获得的即时奖励
• $\gamma$ 是折扣因子
• $Q^{\pi }(S_{t+1},A_{t+1})$ 是下一步的状态-动作值

（2）Sarsa 更新公式

Sarsa 采用时序差分（TD）学习，其核心更新公式为：
$$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha \left(R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)\right)$$
其中：

• $\alpha$ 是学习率
• $R_{t+1}+\gamma Q(S_{t+1},A_{t+1})$ 是 TD 目标（TD Target）
• $R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)$ 是 TD 误差（TD Error）

（3）Sarsa 算法的完整步骤

1. 初始化 $Q(s,a)$

   • 初始化所有状态-动作对的 Q 值（通常设为 0 或随机小值）

2. 选择初始状态 $S_0$ 和动作 $A_0$

   • 使用 ε-贪心策略 选择动作，即：
     • 以概率 $1-ϵ$ 选择 Q 值最高的动作
     • 以概率 $ϵ$ 随机选择 其他动作（探索）

3. 在环境中执行 $A_t$，观察 $R_{t+1}$ 和 $S_{t+1}$

   • 例如，执行 $A_t$ 后，环境返回奖励 $R_{t+1}$ 并进入状态 $S_{t+1}$

4. 选择下一步的动作 $A_{t+1}$

   • 仍然使用 ε-贪心策略 选择 $A_{t+1}$

5. 更新 Q 值
   $$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha \left(R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)\right)$$

6. 循环直到达到终止状态

   • 继续执行步骤 3–5，直到达到终止状态。

环境返回奖励 $R_{t+1}$ 并进入状态 $S_{t+1}$ 的过程，是由强化学习环境决定的。这个过程通常由 环境动态模型（Environment Dynamics Model） 或 交互规则 控制，具体来说，它由 马尔可夫决策过程（MDP） 定义。

2.1 环境如何确定 $S_{t+1}$ 和 $R_{t+1}$？

强化学习的环境是一个马尔可夫决策过程（MDP, Markov Decision Process），它由以下 4 个基本要素组成：

• 状态空间（State Space, $\mathcal{S}$）：所有可能的状态集合
• 动作空间（Action Space, $\mathcal{A}$）：所有可能的动作集合
• 状态转移概率 $P(S_{t+1}\mid S_t,A_t)$：决定执行动作 $A_t$ 后，环境转移到状态 $S_{t+1}$ 的概率
• 奖励函数 $R(S_t,A_t,S_{t+1})$：决定执行 $A_t$ 后，环境返回的即时奖励

在 MDP 中，环境的动态 由 状态转移函数 和 奖励函数 确定：
$$S_{t+1}\sim P(S_{t+1}\mid S_t,A_t)$$$$R_{t+1}=R(S_t,A_t,S_{t+1})$$
这意味着：

• 环境不是随机的黑箱，它有内在规则，比如：
  • 在网格世界中，向左移动意味着 $S_{t+1}$ 可能是左边的格子。
  • 在自动驾驶中，刹车的 $A_t$ 可能导致 $S_{t+1}$ 的速度降低。
• 有些环境是确定性的，有些是随机的：
  • 确定性环境：$S_{t+1}$ 由 $S_t$ 和 $A_t$ 唯一决定
  • 随机环境：有多个 $S_{t+1}$ 可能的选择，每个有不同的概率

---

2.2 具体示例：网格世界（Grid World）

假设我们有一个 4×4 的网格世界，智能体可以执行 4 种动作：

• 上 (↑)，下 (↓)，左 (←)，右 (→)

状态 $S$ 由智能体的坐标 $(x,y)$ 表示，假设环境规则如下：

1. 确定性状态转移：
   • 例如，如果智能体在 $(1,1)$ 处选择 $A_t=\text{右}$，那么：
     $$S_{t+1}=(1,2)$$
2. 奖励函数：
   • 每次移动都会得到 $R_{t+1}=-1$（消耗一步）
   • 目标位置 $(4,4)$ 的奖励是 $R=+10$
   • 碰到墙壁则 $S_{t+1}=S_t$（状态不变），奖励 $R_{t+1}=-1$

示例 1：智能体在 $(1,1)$ 选择 $A_t=\text{右}$

• 当前位置 $S_t=(1,1)$
• 采取动作 $A_t=\text{右}$
• 环境规则：
  • 状态转移：$S_{t+1}=(1,2)$
  • 奖励计算：$R_{t+1}=-1$
• 代理观察到新的状态 $S_{t+1}=(1,2)$，并继续决策。

示例 2：智能体在 $(3,3)$ 选择 $A_t=\text{下}$

• 当前位置 $S_t=(3,3)$
• 采取动作 $A_t=\text{下}$
• 环境规则：
  • 状态转移：$S_{t+1}=(4,3)$
  • 奖励计算：$R_{t+1}=-1$

---

2.3 代码实现：环境如何返回 $S_{t+1}$ 和 $R_{t+1}$

在实际的强化学习代码中，环境通常由一个类 Environment 维护，我们可以使用 OpenAI Gym 这样的框架来管理环境的状态转移。以下是一个简单的网格世界环境：

import numpy as np

class GridWorld:
    def __init__(self, grid_size=(4, 4), goal=(3, 3)):
        self.grid_size = grid_size
        self.goal = goal
        self.state = (0, 0)  # 初始位置 (x, y)
        self.actions = ["up", "down", "left", "right"]

    def step(self, action):
        """执行动作并返回 S_{t+1}, R_{t+1}"""
        x, y = self.state
        if action == "up":
            x = max(0, x - 1)
        elif action == "down":
            x = min(self.grid_size[0] - 1, x + 1)
        elif action == "left":
            y = max(0, y - 1)
        elif action == "right":
            y = min(self.grid_size[1] - 1, y + 1)

        self.state = (x, y)
        reward = 10 if self.state == self.goal else -1  # 目标点奖励 +10，其他 -1
        return self.state, reward  # 返回 S_{t+1}, R_{t+1}

    def reset(self):
        """重置环境"""
        self.state = (0, 0)
        return self.state

如何与环境交互？

env = GridWorld()
state = env.reset()  # 初始化环境
print("初始状态:", state)

next_state, reward = env.step("right")  # 执行 A_t = 右
print("下一状态:", next_state, "奖励:", reward)

next_state, reward = env.step("down")  # 执行 A_t = 下
print("下一状态:", next_state, "奖励:", reward)

输出示例：

初始状态: (0, 0)
下一状态: (0, 1) 奖励: -1
下一状态: (1, 1) 奖励: -1

这说明：

• 状态转移 $S_{t+1}$ 是由环境规则 step() 函数确定的。
• 奖励 $R_{t+1}$ 也是环境定义的，例如到达目标点奖励 +10，其他 -1。

---

2.4 什么时候需要环境模型？

有些强化学习算法（如动态规划）需要完整的环境模型：

• 完全可知环境（如国际象棋）→ 可以直接查询状态转移规则
• 未知环境（如自动驾驶）→ 需要智能体通过采样学习环境模型（模型学习）

但在 强化学习（RL） 中，我们通常不需要明确知道状态转移规则，而是通过不断试错学习来估计最优策略。

---

2.5 结论

1. 环境如何确定 $S_{t+1}$ 和 $R_{t+1}$？

   • 由环境的 状态转移概率 $P(S_{t+1}\mid S_t,A_t)$ 和 奖励函数 $R(S_t,A_t,S_{t+1})$ 决定。

2. 强化学习中的环境是什么？

   • 强化学习环境可以是 网格世界、自动驾驶、金融市场等，不同环境有不同的状态转移规则。

3. 如何在代码中实现环境？

   • 通过 step(action) 方法，根据 状态转移规则 计算下一个状态 $S_{t+1}$，并返回奖励 $R_{t+1}$。

---

3. Sarsa 算法示例

（1）假设的环境

我们使用一个 网格世界（Grid World） 来展示 Sarsa 的学习过程。假设：

• 代理（Agent）在 3×3 网格 中移动（上、下、左、右）
• 目标是在尽可能少的步数内到达终点
• 采取每个动作的奖励 $R=-1$（每走一步都消耗 1）
• 到达目标位置（如 $S_G$）时，奖励 $R=10$，然后 episode 结束。

---

（2）Sarsa 计算过程

假设：

• $\alpha =0.1$，学习率
• $\gamma =0.9$，折扣因子
• 代理从状态 $S_1$ 开始，随机选择动作 $A_1$（向右）

第一步

• 当前状态 $S_1$
• 选择动作 $A_1=\text{右}$
• 执行 $A_1$，环境返回：
  • 奖励 $R_2=-1$
  • 新状态 $S_2$
• 选择 $S_2$ 中的动作 $A_2$（假设是向下）
• 计算 Q 值更新：
  $$Q(S_1,A_1)\leftarrow Q(S_1,A_1)+\alpha \left(R_2+\gamma Q(S_2,A_2)-Q(S_1,A_1)\right)$$

第二步

• 代理执行 $A_2$，到达 $S_3$，获得奖励 $R_3=-1$
• 选择 $S_3$ 的动作 $A_3$，继续更新 $Q$。

最终到达终点

• 当到达目标状态 $S_G$：
  • 奖励 $R=10$
  • 终止 episode
  • 终止状态的 Q 值不再更新。

---

4. Sarsa 与 Q-learning 的对比

方法	Sarsa	Q-learning
更新方式	使用 当前策略 选择 $A_{t+1}$	使用 最大 Q 值 更新
公式	$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha \left(R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)\right)$	$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha \left(R_{t+1}+\gamma {\max }_{a}Q(S_{t+1},a)-Q(S_t,A_t)\right)$
是否遵循策略	是，在 $S_{t+1}$ 选择 $A_{t+1}$ 来更新	否，使用贪心策略计算最优值
收敛性	较稳定，但可能收敛到次优策略	收敛更快，但可能过度乐观

---

5. 结论

1. Sarsa 是一种基于时序差分（TD）方法的强化学习算法，通过五元组 $(S_t,A_t,R_{t+1},S_{t+1},A_{t+1})$ 来更新 Q 值。
2. Sarsa 遵循当前策略 进行更新，因此它是**on-policy（在线策略）**方法。
3. Sarsa 和 Q-learning 的区别：
   • Sarsa 更稳定，因为它遵循当前策略
   • Q-learning 更激进，因为它使用最大 Q 值来更新（off-policy）
4. Sarsa 适用于安全性要求较高的任务，例如：自动驾驶、机器人控制。

分隔符

Sarsa算法由于每次更新值函数时需要知道当前的状态（state）、当前的动作（action）、奖励（reward）、下一步的状态（state）、下一步的动作（action）。如果还没有运动，下一步的状态（state）、下一步的动作（action）是如何知道的呢？

1. Sarsa 需要的五元组

Sarsa 需要以下 五个变量 来进行 Q 值更新：
$$(S_t,A_t,R_{t+1},S_{t+1},A_{t+1})$$
其中：

• $S_t$：当前状态
• $A_t$：当前动作
• $R_{t+1}$：执行 $A_t$ 后，环境返回的奖励
• $S_{t+1}$：执行 $A_t$ 后，环境返回的新状态
• $A_{t+1}$：在 $S_{t+1}$ 处根据策略选择的动作

核心问题： 如果智能体还没有移动，$S_{t+1}$ 和 $A_{t+1}$ 是如何得到的呢？

---

2. Sarsa 运行流程：如何获取 $S_{t+1}$ 和 $A_{t+1}$

（1）智能体初始化

• 设定初始状态 $S_0$
• 使用ε-贪心策略选择一个初始动作 $A_0$

（2）智能体执行 $A_t$，与环境交互

1. 执行当前动作 $A_t$
   • 将 $A_t$ 传递给环境
2. 环境返回新的状态 $S_{t+1}$ 和奖励 $R_{t+1}$
   • 由环境的 状态转移规则 计算 $S_{t+1}$
   • 由环境的 奖励函数 计算 $R_{t+1}$
3. 在新状态 $S_{t+1}$ 选择新动作 $A_{t+1}$
   • 使用ε-贪心策略 选择 $A_{t+1}$
4. 更新 Q 值
   $$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha \left(R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)\right)$$
5. 继续下一个时间步
   • 设定 $S_t\leftarrow S_{t+1}$
   • 设定 $A_t\leftarrow A_{t+1}$
   • 继续执行步骤 2-5，直到终止状态。

---

3. 具体示例

我们来看一个 网格世界（Grid World） 任务：

• 初始位置：$S_0=(0,0)$
• 目标位置：$S_G=(2,2)$
• 允许的动作：上（↑）、下（↓）、左（←）、右（→）
• 奖励规则：
  • 移动一步：$R=-1$
  • 到达终点：$R=10$
  • 撞墙：$R=-1$, 状态不变

---

Sarsa 运行示例

假设智能体在网格 左上角，即：

• 初始状态： $S_0=(0,0)$
• ε-贪心选择初始动作： $A_0=\text{右}$

第一步：执行 $A_0$，获取 $S_1$ 和 $R_1$

• 执行动作：$A_0=\text{右}$
• 环境返回：
  • 新状态：$S_1=(0,1)$
  • 奖励：$R_1=-1$
• 在 $S_1$ 选择新动作 $A_1$（用 ε-贪心策略）
  • 例如： 选择 $A_1=\text{下}$
• 计算 Q 值更新：
  $$Q(S_0,A_0)\leftarrow Q(S_0,A_0)+\alpha \left(R_1+\gamma Q(S_1,A_1)-Q(S_0,A_0)\right)$$

第二步：执行 $A_1$，获取 $S_2$ 和 $R_2$

• 执行 $A_1=\text{下}$
• 环境返回：
  • 新状态：$S_2=(1,1)$
  • 奖励：$R_2=-1$
• 选择 $A_2=\text{右}$
• 计算：
  $$Q(S_1,A_1)\leftarrow Q(S_1,A_1)+\alpha \left(R_2+\gamma Q(S_2,A_2)-Q(S_1,A_1)\right)$$

---

4. 代码实现

在 Python 代码中，我们使用 环境（environment） 来管理状态转移：

import numpy as np

class GridWorld:
    def __init__(self, grid_size=(3,3), goal=(2,2)):
        self.grid_size = grid_size
        self.goal = goal
        self.state = (0, 0)
        self.actions = ["up", "down", "left", "right"]

    def step(self, action):
        """执行动作，返回 S_{t+1} 和 R_{t+1}"""
        x, y = self.state
        if action == "up":
            x = max(0, x - 1)
        elif action == "down":
            x = min(self.grid_size[0] - 1, x + 1)
        elif action == "left":
            y = max(0, y - 1)
        elif action == "right":
            y = min(self.grid_size[1] - 1, y + 1)

        self.state = (x, y)
        reward = 10 if self.state == self.goal else -1
        return self.state, reward

    def reset(self):
        """重置环境"""
        self.state = (0, 0)
        return self.state

def epsilon_greedy(Q, state, epsilon=0.1):
    """ε-贪心策略"""
    if np.random.rand() < epsilon:
        return np.random.choice(["up", "down", "left", "right"])
    else:
        return max(Q[state], key=Q[state].get)

# 初始化环境
env = GridWorld()
Q = { (i,j): { a: 0 for a in ["up", "down", "left", "right"] } for i in range(3) for j in range(3) }

# Sarsa 训练
alpha = 0.1
gamma = 0.9
epsilon = 0.1

state = env.reset()
action = epsilon_greedy(Q, state, epsilon)

for _ in range(100):
    next_state, reward = env.step(action)
    next_action = epsilon_greedy(Q, next_state, epsilon)

    Q[state][action] += alpha * (reward + gamma * Q[next_state][next_action] - Q[state][action])

    state, action = next_state, next_action

---

5. 总结

1. Sarsa 不是在一开始就知道 $S_{t+1}$ 和 $A_{t+1}$，而是在交互过程中获取的！

   • 先执行动作 $A_t$ 与环境交互
   • 通过环境 返回新的状态 $S_{t+1}$ 和奖励 $R_{t+1}$
   • 在 $S_{t+1}$ 选择新动作 $A_{t+1}$
   • 进行 Q 值更新。

2. 智能体需要环境的支持，环境定义了状态转移和奖励函数。

3. ε-贪心策略 确保了在每个状态选择一个合理的动作，支持探索。

---