1. Learn about value-based methods.
  2. Learn about the differences between Monte Carlo and Temporal Difference Learning.
  3. Study and implement our first RL algorithm: Q-Learning.

Value-Based Methods

先给出一个例子：假设你正在玩一个走迷宫的游戏。

  • 状态 (State): 你当前在迷宫中的位置。
  • 策略 (Policy): 你决定如何走迷宫 (例如，总是选择离终点最近的方向)。
  • 价值函数 (Value Function): 对于迷宫中的每个位置，价值函数会告诉你，如果你从这个位置开始，按照你的策略走，最终到达终点的可能性有多大 (或者说，你期望获得多少奖励，例如到达终点奖励 +1，每走一步奖励 -0.1)。

Value-based methods 的目标就是学习这个价值函数。一旦你学会了价值函数，你就可以根据价值函数来选择行动，从而更快地到达终点。例如，如果你发现某个位置的价值很高，那么你就应该尽量走到那个位置。

理解它的核心是理解 Value-based method 和 Policy-based method的区别。

你先要有一个 Policy

  • Value-based 是先给出一个 Policy，我们自己定义的（比如 Greedy Policy），来学习一个价值函数。实践中，通常会使用一个Epsilon-Greedy policy，它的另一个优势是处理 探索/利用的权衡。

  • Policy-based 是直接学习一个 Policy， $\pi(a | s) = P(a | s)$，它不需要一个价值函数。所以我们不会定义Policy 的行为，是训练的过程定义的这个 Policy。

所以，value-based 是 找到一个最优的 Value Function（$ Q^* $ 或 $ V^* $，后续有这两者的不同）通过这个过程间接找到一个 最优的Policy；而 policy-based 是 finding an optimal policy Directly。

注意：

  • 如果我学习到了这个价值函数，这个价值函数与我先前的 Policy 是绑定的。也就是说如果我换一个 Policy，我需要重新训练价值函数。
  • 对于 Value-based 方法，选择一个好的 Policy (策略) 对价值函数和 Agent 最终的性能有着直接且显著的影响。
  • 一个好的 Policy 需要在探索 (Exploration) 和利用 (Exploitation) 之间取得平衡。
  • 学习到的价值函数和 Policy 一起代表了最终的目的：一个好的 Policy。
  • 在 Value-based 方法中，学习到的价值函数会反过来修改我们之前设定的 Policy。这个过程是 Value-based 方法的核心机制之一，也是强化学习能够不断改进策略的关键所在。

所以更确切的讲，“先给出一个 Policy” 只是一个初始化的 Policy。过不断地学习价值函数和改进 Policy，Agent 最终可以找到最优的 Policy。

你需要训练一个价值函数 Value function

有两种价值函数：State value function 和 Action value function。

  • State value function： calculate the value of a state St

  • Action value function： calculate the value of the state-action pair (St, At) hence the value of taking that action at that state.

这个示意图展示了这两种价值函数的不同：

价值函数的区别

这两种价值函数的输出即 expected return。

问题是：

计算状态价值的一种直接方法是，计算从当前状态开始的所有可能的未来状态序列，以及每个状态序列对应的回报。然后，对所有可能的状态序列的回报进行加权平均，得到期望回报。由于未来状态序列的数量可能非常庞大 (特别是当状态空间和动作空间很大时)，因此直接计算期望回报的总和会非常耗时，甚至不可行。

两种价值函数的计算量都很大。所以引入了 Bellman 方程。

Bellman 方程

贝尔曼方程的核心思想, 它将当前状态的价值分解为两部分：

【在当前状态下采取某个动作后，立即获得的奖励】 + 【在采取动作后，到达的下一个状态的价值。由于未来的奖励不如当前的奖励那么确定，因此我们需要对后续状态的价值进行“打折”】，这是一种递归的方式计算价值。

贝尔曼方程是 Value-based 方法的核心公式，也是强化学习能够不断改进策略的关键所在。

一般形式，以状态价值函数为例，基于策略 $\pi$）

$$ V^\pi(s) = E_\pi \left[ R(s, a) + \gamma \sum_{s’ \in S} P(s’|s, a) V^\pi(s’) \right] $$

  • $V^\pi(s)$：状态 $s$ 的价值（期望累计奖励）。
  • $R(s, a)$：即时奖励。
  • $\gamma$：折扣因子。
  • $P(s’|s, a)$：状态转移概率。即采取动作 $a$ 后转移到下一状态 $s’$ 的概率
  • $\mathbb{E}_\pi$：基于策略 $\pi$ 的期望。

Gamma ($\gamma$) 是一个介于 0 和 1 之间的折扣因子，它决定了我们对未来奖励的重视程度。

  1. $\gamma$ 非常低, Agent 会非常重视当前的奖励，而几乎忽略未来的奖励。 Agent 可能会在一个小区域内来回移动，而无法找到出口。

  2. $\gamma$ 非常高，Agent 会完全重视未来的奖励，认为未来的奖励和当前的奖励一样重要。它可能会为了获得未来的高分而牺牲当前的分数，最终导致总分降低。

所以：

Bellman 方程并不是一个确定的方程，而是一种计算模式。它提供了一种计算状态价值的理论基础，它定义了状态价值与立即奖励和后续状态价值之间的关系。蒙特卡洛方法（Monte Carlo）和时序差分学习（Temporal Difference Learning）方法是两种不同的实现贝尔曼方程的方式。

Monte Carlo && Temporal Difference Learning（TD）

他们是两种训练价值函数的方法。都是运用经验来解决问题。

Monte Carlo 在更新学习前要应用整个Episode 的经验，它学习的是状态的价值；TD 在每一步都更新学习：

图片描述
MC和TD的对比

MC 方法

公式: $$V(s) \leftarrow V(s) + \alpha \left[ G_t - V(s) \right]$$

其中 $ G_t = R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{T-1} R_T $ 表示从时间步 $ t $ 到 Episode 结束时的实际累计回报。从当前位置到游戏结束能拿多少分。（需要完整轨迹，因为 $ G_t $ 要求直到回合结束。）

特点: 用完整轨迹的回报 $G_t$ 更新，需回合结束，无偏高方差。

MC 更新的是 State value function，即 State 的价值。MC 更新的 State 是这个Episode中出现过的状态，没有出现过的状态不更新。所以为了覆盖所有 State，MC 需要很多 Episode 学习。

MC的价值函数是一个映射，它将每个状态 $ s $ 映射到一个价值估计值 $ V(s) $。

TD 方法

公式: $$V(s_t) \leftarrow V(s_t) + \alpha \left[ R_{t+1} + \gamma V(s_{t+1}) - V(s_t) \right]$$

其中 $ R_{t+1} + \gamma V(s_{t+1}) $ 表示单步及时奖励 + 下一状态估计价值（Bootstrap）。它被称作 TD-target。（适合连续，非回合制任务，复杂实时场景（如机器人控制），可每步更新，无需完整轨迹）。

特点: 每步更新，实时，低方差但有偏。

在 TD Learning 中，目标价值是基于当前状态的立即奖励和下一个状态的价值估计来计算的。TD 是一种 Bootstrapping

注意，Value-based method 中我们的目标是学习 $V(s_t)$. 它需要被初始化为合理的值，然后根据 MC 或 TD 更新这个值。

MC 实例：

Policy： Agent 遵循一个给定的 Policy。奖励：从 s1 到 s2 获得奖励 $ r_1 $。从 s2 到 s3 获得奖励 $ r_2 $。到达 s3 (Episode 结束) 获得奖励 $r_3$。折扣因子 (gamma)： $ \gamma $。学习率 (alpha)：$\alpha$。初始价值函数： $V(s_1)$, $V(s_2)$, $V(s_3)$ (初始值可以为 0 或其他任意值)。

步骤：

  1. Episode 开始： Agent 从初始状态 s1 开始，根据 Policy 与环境交互，直到 Episode 结束。
  2. 收集 Episode 数据： 假设 Agent 按照 s1 -> s2 -> s3 的顺序访问了这三个 State，并获得了相应的奖励 $ r_1 $, $ r_2 $, $r_3$。
  3. 计算回报 (Return)： 从 Episode 的最后一个 State 开始，反向计算每个 State 的回报：
    • $G(s_3)$： 从 s3 开始的回报 = $r_3$
    • $G(s_2)$： 从 s2 开始的回报 = $ r_2 $ + $ \gamma $ * $G(s_3)$ = $ r_2 $ + $ \gamma $ * $r_3$
    • $G(s_1)$： 从 s1 开始的回报 = $ r_1 $ + $ \gamma $ * $G(s_2)$ = $ r_1 $ + $ \gamma $ * ($ r_2 $ + $ \gamma $ * $r_3$) = $ r_1 $ + $ \gamma $ * $ r_2 $ + $ \gamma^2 $ * $r_3$
  4. 更新价值函数： 使用计算得到的回报来更新每个 State 的价值：
    • $V(s_3)$： $V(s_3)$ = $V(s_3)$ + $\alpha$ * ($G(s_3)$ - $V(s_3)$) = $V(s_3)$ + $\alpha$ * ($r_3$ - $V(s_3)$)
    • $V(s_2)$： $V(s_2)$ = $V(s_2)$ + $\alpha$ * ($G(s_2)$ - $V(s_2)$) = $V(s_2)$ + $\alpha$ * ($ r_2 $ + $ \gamma $ * $r_3$ - $V(s_2)$)
    • $V(s_1)$： $V(s_1)$ = $V(s_1)$ + $\alpha$ * ($G(s_1)$ - $V(s_1)$) = $V(s_1)$ + $\alpha$ * ($ r_1 $ + $ \gamma $ * $ r_2 $ + $ \gamma^2 $ * $r_3$ - $V(s_1)$)

KAQ：每个state的回报为什么反向计算？

答：因为公式中的 reward 其实是 cumulative reward，即从当前状态到最终状态的累计reward，同时为了避免重复计算，所以反向计算G(s)。

TD 实例

假设：

状态空间： S = {s1, s2, s3}
动作空间： 为了简化，我们不考虑动作，假设 Agent 只能被动地从一个 State 转移到另一个 State。
奖励：
    从 s1 到 s2 获得奖励 r1 = 1。
    从 s2 到 s3 获得奖励 r2 = 2。
    到达 s3 (Episode 结束) 获得奖励 r3 = 0 (Episode 结束时没有额外奖励)。
折扣因子 (gamma)： γ = 0.9。
学习率 (alpha)： α = 0.1。
初始价值函数： V(s1) = 0, V(s2) = 0, V(s3) = 0。
Episode： 假设 Agent 经历了一个 Episode：s1 -> s2 -> s3。

步骤：

  1. 初始化：

    • V(s1) = 0
    • V(s2) = 0
    • V(s3) = 0

  2. Step 1：从 s1 到 s2

    • S = s1
    • R = r1 = 1
    • S’ = s2
    • TD Target = R + γ * V(S’) = 1 + 0.9 * 0 = 1
    • TD Error = TD Target - V(S) = 1 - 0 = 1
    • V(s1) = V(s1) + α * TD Error = 0 + 0.1 * 1 = 0.1

  3. Step 2：从 s2 到 s3

    • S = s2
    • R = r2 = 2
    • S’ = s3
    • TD Target = R + γ * V(S’) = 2 + 0.9 * 0 = 2
    • TD Error = TD Target - V(S) = 2 - 0 = 2
    • V(s2) = V(s2) + α * TD Error = 0 + 0.1 * 2 = 0.2

  4. Step 3：到达 s3 (Episode 结束)

    • S = s3
    • R = r3 = 0
    • S’ = None (Episode 结束，没有下一个状态)
    • TD Target = R + γ * 0 = 0 + 0.9 * 0 = 0 (通常 Episode 结束时，下一个状态的价值为 0)
    • TD Error = TD Target - V(S) = 0 - 0 = 0
    • V(s3) = V(s3) + α * TD Error = 0 + 0.1 * 0 = 0

  5. 更新后的价值函数：

    • V(s1) = 0.1
    • V(s2) = 0.2
    • V(s3) = 0

总结

在value-based methods ，我们不是学习Policy，而是手动定义Policy并学习一个价值函数。如果我们有一个最优的价值函数，那么我们将得到一个最优的Policy（目的也是学习一个Policy，只不过不是直接的）。

图片描述
间接得到最优的 policy

补充

on-policy

on-policy: agent 使用相同的策略来选择动作（与环境交互）和评估/改进该策略。 即，agent 使用当前的策略来生成经验，并使用这些经验来改进相同的策略。

实现：actor-critic，SARSA

off-policy

off-policy: agent 可以使用一个策略（行为策略）来生成经验，然后使用这些经验来学习另一个策略（目标策略）。

实现有 Q-learning、DQN，

比如 Q-learning 直接学习最优 Q 函数 (Q*(s, a))，而不依赖于 agent 当前的策略。