强化学习基础知识 - MiniMind 学习笔记

速通强化学习

在进入强化学习在 LLM 中的应用之前，我想先用一节内容串讲并总结一下强化学习的基础知识。这部分基本可以看作是对西湖大学赵世玉老师强化学习课程的学习整理。我非常推荐这门课程，赵老师在 B 站和 GitHub 上都公开了相关资料：

https://github.com/MathFoundationRL/Book-Mathematical-Foundation-of-Reinforcement-Learning

当然，这篇笔记不应该被视为一门完整的强化学习课程；这显然也不是一篇笔记能够完成的事情。我希望在这一节中主要完成两件事。

第一，把强化学习中重要且基础的概念、定义和公式梳理清楚。RL 本身是一个概念密度很高、符号也比较容易混乱的领域，先把这些基础记号统一下来，后面再讨论具体算法时就不容易迷路。

第二，尽量简单梳理不同算法之间的思路演变和基本逻辑关系。这里不会追求覆盖所有细节，而是希望先建立一条主线：这些算法分别想解决什么问题，以及它们之间大致是如何连接起来的。

基本概念,以及问题的定义

基本记号

在强化学习中，我们首先需要区分“随机变量”和“随机变量的一次具体取值”。后面所有公式都尽量沿用这一套记号。强化学习的问题定义里面,随机变量的个数有一些多.所以请时刻牢记随机变量和随机变量取值的区别.否则很多公式会变得非常的混乱.

$S_t$：时刻 $t$ 的状态，是随机变量。
$A_t$：时刻 $t$ 在状态 $S_t$ 下采取的动作，是随机变量。
$R_{t+1}$：执行动作 $A_t$ 之后得到的奖励，是随机变量。
$S_{t+1}$：执行动作 $A_t$ 之后转移到的下一个状态，是随机变量。
$s,a,r,s^{\prime}$：分别表示状态、动作、奖励、下一个状态的具体取值。
$\mathcal{S}$：状态空间。
$\mathcal{A}(s)$：状态 $s$ 下可选动作的集合。
$\gamma \in [0,1)$：折扣因子，用来控制未来奖励在当前价值中的权重。

一个单步交互可以写成：

\[ S_t \xrightarrow{A_t} R_{t+1}, S_{t+1} \]

也就是说，智能体在状态 $S_t$ 下选择动作 $A_t$，环境返回奖励 $R_{t+1}$，并转移到新状态 $S_{t+1}$。

这里有一个需要注意的点.奖励的角标是t+1,而不是状态的t.

MDP: 强化学习问题的数学对象

强化学习中最常用的问题建模方式是 Markov Decision Process，简称 MDP。一个 MDP 可以写成：

\[ \mathcal{M} = (\mathcal{S}, \mathcal{A}, p, r, \gamma) \]

其中：

$\mathcal{S}$ 是状态空间。
$\mathcal{A}$ 是动作空间；如果动作集合依赖于状态，也写作 $\mathcal{A}(s)$。
$p$ 是环境的动态模型。
$r$ 是奖励函数。
$\gamma$ 是折扣因子。

更严谨地说，环境的单步随机性可以用联合分布表示：

\[ p(s^{\prime}, r \mid s, a)=\Pr(S_{t+1}=s^{\prime}, R_{t+1}=r \mid S_t=s, A_t=a) \]

这个式子表示：当智能体在状态 $s$ 下采取动作 $a$ 时，环境转移到状态 $s^{\prime}$ 并给出奖励 $r$ 的概率。

有时也会把状态转移概率和奖励概率分开写：

\[ p(s^{\prime} \mid s,a)=\Pr(S_{t+1}=s^{\prime} \mid S_t=s,A_t=a) \]

\[p(r \mid s,a)=\Pr(R_{t+1}=r \mid S_t=s,A_t=a) \]

但在一般情况下，$S_{t+1}$ 和 $R_{t+1}$ 可能不是独立的，所以用 $p(s^{\prime},r\mid s,a)$ 作为统一记号会更严谨。

Markov 性质指的是：给定当前状态和当前动作之后，未来只依赖当前，而不依赖更早的历史。也就是：

$\Pr(S_{t+1}=s^{\prime}, R_{t+1}=r \mid S_0,A_0,R_1,\dots,S_t,A_t) = p(s^{\prime},r \mid S_t,A_t)$

策略与轨迹

MDP定义了强化学习的环境.智能体在这个环境中通过交互来学习一个策略(policy),使得它能够在这个环境中获得更多的奖励.Policy 描述智能体在每个状态下如何选择动作。随机策略写作：

$\pi(a \mid s) = \Pr(A_t=a \mid S_t=s)$

其中：

$\pi$ 表示策略。
$\pi(a\mid s)$ 表示在状态 $s$ 下选择动作 $a$ 的概率。

那么从某个初始状态出发，智能体与环境交互会生成一条随机轨迹 trajectory：

$\tau = (S_0,A_0,R_1,S_1,A_1,R_2,S_2,\dots)$

对于有限长度 $T$ 的轨迹，也可以写成：

$\tau_{0:T} = (S_0,A_0,R_1,S_1,A_1,R_2,\dots,S_T)$

在给定初始状态分布 $\rho_0(s_0)$、策略 $\pi$、环境动态 $p$ 的情况下，一条有限轨迹的概率可以写成：

$\Pr(\tau_{0:T}) = \rho_0(s_0) \prod_{t=0}^{T-1} \pi(a_t\mid s_t) p(s_{t+1},r_{t+1}\mid s_t,a_t)$

这个公式把强化学习中的两类随机性都写了出来：

$\pi(a_t\mid s_t)$：智能体选择动作的随机性。
$p(s_{t+1},r_{t+1}\mid s_t,a_t)$：环境反馈的随机性。

Return

Return的意义是定义智能体的表现的好与坏.从时刻 $t$ 开始，智能体未来能够获得的折扣奖励和称为 return，记作 $G_t$。

伽马是一个衰减系数.这个定义非常的直观.我越未来的得到的奖励,其重要性就在下降.

$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots$

也可以写成求和形式：

$G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$

其中：

$G_t$ 是从时刻 $t$ 开始的回报。
$R_{t+k+1}$ 是未来第 $k+1$ 步得到的奖励。
$\gamma^k$ 是这个奖励对应的折扣权重。

Return 还有一个非常重要的递推形式：

$G_t = R_{t+1} + \gamma G_{t+1}$

因为：

$G_{t+1} = R_{t+2} + \gamma R_{t+3} + \gamma^2 R_{t+4} + \cdots$

所以：

$R_{t+1}+\gamma G_{t+1} = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots = G_t$

State value

至此,我们获得了强化学习中最重要的一个概念:我们希望关注每一个state上,它能获得的return是多少.这就是State value的定义.由于return又是一个随机变量.所以我们用期望来衡量对于每一个state的整体的return.

State value function 描述的是：在策略 $\pi$ 下，从状态 $s$ 出发，未来能得到的期望 return。

它定义为：

$v_\pi(s) = \mathbb{E}_\pi[G_t \mid S_t=s]$

其中：

$v_\pi(s)$ 是状态 $s$ 在策略 $\pi$ 下的 state value。
$G_t$ 是从时刻 $t$ 开始的 return。
条件 $S_t=s$ 表示当前状态固定为 $s$。
下标 $\pi$ 表示期望是沿着策略 $\pi$ 与环境交互产生的轨迹分布计算的。(我个人更喜欢把它看作随机变量$G_t$的期望)

更直接地说，state value 是“从某个状态出发，在策略 $\pi$ 下所有可能 return 的平均值”。如果策略和环境都是确定性的，那么从 $s$ 出发只会产生一条轨迹，此时 $v_\pi(s)$ 就等于这条轨迹的 return。只要策略或者环境中有随机性，$G_t$ 就是随机变量.

Q value / Action value

Action value function，也常被称为 Q value，描述的是：在策略 $\pi$ 下，从状态 $s$ 出发，先采取动作 $a$，之后继续按照策略 $\pi$ 行动，未来能得到的期望 return。

Q value 的直观理解是从状态出发,每个可能的action未来会获得的return的期望.

它定义为：

$q_\pi(s,a) = \mathbb{E}_\pi[G_t \mid S_t=s,A_t=a]$

其中：

$q_\pi(s,a)$ 是状态-动作对 $(s,a)$ 在策略 $\pi$ 下的 action value。
条件 $S_t=s,A_t=a$ 表示当前状态和当前动作都已经固定。
从下一步开始，后续动作仍然由策略 $\pi$ 产生。

State value 和 Q value 的区别在于条件不同：

$v_\pi(s) = \mathbb{E}_\pi[G_t \mid S_t=s]$ $q_\pi(s,a) = \mathbb{E}_\pi[G_t \mid S_t=s,A_t=a]$

前者只固定当前状态，动作仍然按照策略 $\pi(a\mid s)$ 抽样；后者同时固定当前状态和当前动作。因此，Q value 更适合用来比较“在同一个状态下，哪个动作更好”。

关于这部分的证明,我强烈推荐使用全期望公式进行，也就是 probability 里面的 law of total expectation。一般形式可以写成：

$\mathbb{E}[X] = \mathbb{E}_{Y} \left[ \mathbb{E}[X \mid Y] \right]$ $\mathbb{E}[X\mid Y] = \mathbb{E}_{Z\mid Y} \left[ \mathbb{E}[X\mid Y,Z] \right]$

在这里令 $X=G_t$，$Y=(S_t=s)$，$Z=A_t$。那么：

$v_\pi(s) = \mathbb{E}_\pi[G_t\mid S_t=s] = \mathbb{E}_{A_t\sim\pi(\cdot\mid s)} \left[ \mathbb{E}_\pi[G_t\mid S_t=s,A_t] \right]$

而根据 Q value 的定义：

$q_\pi(s,a) = \mathbb{E}_\pi[G_t\mid S_t=s,A_t=a]$

所以：

$v_\pi(s) = \sum_{a\in\mathcal{A}(s)} \pi(a\mid s)q_\pi(s,a)$

也可以写成期望形式：

$v_\pi(s) = \mathbb{E}_{A_t\sim\pi(\cdot\mid s)} \left[ q_\pi(s,A_t) \right]$

这个关系的含义是：状态价值等于在该状态下按照策略选择动作后，所有动作价值的加权平均。也就是说，$v_\pi(s)$ 是“先固定状态，再按照策略平均动作”；$q_\pi(s,a)$ 则是“同时固定状态和动作”。

一些其他的概念

Bellman Equation

Bellman equation 是强化学习里面最核心的公式之一。它的作用是把“一个状态的价值”写成“一步奖励”和“下一个状态价值”的关系。这个公式本质上来自 return 的递推定义：

$G_t = R_{t+1} + \gamma G_{t+1}$

如果说 state value 是对 return 取期望，那么 Bellman equation 就是在这个递推关系的基础上继续取期望。

Bellman 方程的展开形式

先回顾 state value 的定义：

$v_\pi(s) = \mathbb{E}_\pi[G_t\mid S_t=s]$

把 return 的递推形式代入：

$v_\pi(s) = \mathbb{E}_\pi[R_{t+1}+\gamma G_{t+1}\mid S_t=s]$

再把当前动作 $A_t$、下一状态 $S_{t+1}$ 和奖励 $R_{t+1}$ 全部展开，就得到 Bellman expectation equation 的展开形式：

$v_\pi(s) = \sum_{a\in\mathcal{A}(s)} \pi(a\mid s) \sum_{s^{\prime}\in\mathcal{S}} \sum_{r\in\mathcal{R}} p(s^{\prime},r\mid s,a) \left[ r+\gamma v_\pi(s^{\prime}) \right]$

这里每一层求和都有明确含义：

$\sum_a \pi(a\mid s)$：在状态 $s$ 下，策略可能选择不同动作。
$\sum_{s^{\prime}}\sum_r p(s^{\prime},r\mid s,a)$：给定状态和动作后，环境可能返回不同的下一状态和奖励。
$r+\gamma v_\pi(s^{\prime})$：当前一步奖励，加上下一个状态的折扣价值。

如果先定义 Q value：

$q_\pi(s,a) = \sum_{s^{\prime}\in\mathcal{S}} \sum_{r\in\mathcal{R}} p(s^{\prime},r\mid s,a) \left[ r+\gamma v_\pi(s^{\prime}) \right]$

那么 Bellman equation 也可以写得更紧凑：

$v_\pi(s) = \sum_{a\in\mathcal{A}(s)} \pi(a\mid s)q_\pi(s,a)$

这个写法和上一节的全期望公式是一致的，只是这里进一步把 $q_\pi(s,a)$ 里面的一步环境转移也展开了。

Bellman 方程的矩阵形式

如果状态空间是有限的，并且可以写成：

$\mathcal{S}=\{s_1,s_2,\dots,s_n\}$

那么可以把所有状态的 value 放进一个向量：

$\mathbf{v}_\pi = \begin{bmatrix} v_\pi(s_1)\\ v_\pi(s_2)\\ \vdots\\ v_\pi(s_n) \end{bmatrix} \in \mathbb{R}^n$

接下来定义策略 $\pi$ 下的平均即时奖励：

$r_\pi(s) = \sum_{a\in\mathcal{A}(s)} \pi(a\mid s) \sum_{s^{\prime}\in\mathcal{S}} \sum_{r\in\mathcal{R}} p(s^{\prime},r\mid s,a)r$

把所有 $r_\pi(s_i)$ 放进向量：

$\mathbf{r}_\pi = \begin{bmatrix} r_\pi(s_1)\\ r_\pi(s_2)\\ \vdots\\ r_\pi(s_n) \end{bmatrix}$

再定义策略 $\pi$ 诱导出来的状态转移矩阵 $\mathbf{P}_\pi\in\mathbb{R}^{n\times n}$。它的第 $i,j$ 个元素是：

$[\mathbf{P}_\pi]_{ij} = p_\pi(s_j\mid s_i) = \sum_{a\in\mathcal{A}(s_i)} \pi(a\mid s_i) \sum_{r\in\mathcal{R}} p(s_j,r\mid s_i,a)$

于是，Bellman equation 可以写成非常简洁的矩阵形式：

$\mathbf{v}_\pi = \mathbf{r}_\pi + \gamma \mathbf{P}_\pi \mathbf{v}_\pi$

把含有 $\mathbf{v}_\pi$ 的项移到左边：

$(\mathbf{I}-\gamma\mathbf{P}_\pi)\mathbf{v}_\pi = \mathbf{r}_\pi$

如果 $\mathbf{I}-\gamma\mathbf{P}_\pi$ 可逆，就有闭式解：

$\mathbf{v}_\pi = (\mathbf{I}-\gamma\mathbf{P}_\pi)^{-1} \mathbf{r}_\pi$

这个矩阵形式很重要，因为它说明：在给定策略 $\pi$ 的情况下，求 state value 本质上是在解一个线性方程组。这个问题也被称为 policy evaluation。

Bellman 最优方程与最优策略

前面的 Bellman equation 都是在“给定策略 $\pi$”的前提下讨论的。接下来的问题是：什么样的策略是最优策略？

我们可以先定义策略之间的偏序关系。如果对任意状态 $s\in\mathcal{S}$，都有：

$v_{\pi_1}(s) \ge v_{\pi_2}(s)$

那么就说策略 $\pi_1$ 不差于策略 $\pi_2$，记作：

$\pi_1 \succeq \pi_2$

如果一个策略 $\pi^*$ 对任意其他策略 $\pi$ 都满足：

$v_{\pi^*}(s) \ge v_\pi(s), \quad \forall s\in\mathcal{S}$

那么 $\pi^*$ 就是一个最优策略。对应的最优 state value 定义为：

$v^*(s) = \max_\pi v_\pi(s)$

最优策略的关键在于：如果已经知道每个动作带来的未来价值，那么在每个状态下都应该选择价值最大的动作。因此 Bellman expectation equation 中的“按照策略加权平均”，在最优情况下会变成“对动作取最大值”：

$v^*(s) = \max_{a\in\mathcal{A}(s)} \sum_{s^{\prime}\in\mathcal{S}} \sum_{r\in\mathcal{R}} p(s^{\prime},r\mid s,a) \left[ r+\gamma v^*(s^{\prime}) \right]$

这就是 Bellman optimality equation。

Bellman optimality equation 的解的存在性和唯一性

这里有一个非常重要的问题：这个方程一定有解吗？如果有解，解是不是唯一的？

在有限状态、有限动作，并且折扣因子满足 $0\le \gamma < 1$ 的 discounted MDP 中，Bellman optimality equation 的最优 state value $v^*$ 一定存在，并且是唯一的。

原因可以从 Bellman optimality operator 的角度理解。定义：

$(\mathcal{T}v)(s) = \max_{a\in\mathcal{A}(s)} \sum_{s^{\prime}\in\mathcal{S}} \sum_{r\in\mathcal{R}} p(s^{\prime},r\mid s,a) \left[ r+\gamma v(s^{\prime}) \right]$

如果写成矩阵形式，可以把它理解为：下一步Bellman状态更新的时候,选择让每个状态最大的动作,然后用这个策略对应的状态值作为当前能获得的最优状态值:

$\mathcal{T}\mathbf{v} = \max_{\pi} \left( \mathbf{r}_{\pi} + \gamma \mathbf{P}_{\pi}\mathbf{v} \right)$

这里的 $\max_\pi$ 不是对整个向量取一个标量最大值，而是对每个状态分别选择能让该状态右侧取到最大值的动作或策略。换句话说，Bellman optimality operator 做的事情就是：给定当前价值估计 $\mathbf{v}$，在每个状态上做一次 greedy 的 Bellman backup。

那么 Bellman optimality equation 就是：

$v = \mathcal{T}v$

当 $0\le \gamma < 1$ 时，$\mathcal{T}$ 是一个 contraction mapping。因此根据 contraction mapping theorem，它有唯一的不动点。这个唯一不动点就是最优 state value $v^*$。

需要注意的是，唯一的是最优价值函数 $v^* $，不一定是最优策略 $\pi^* $。如果在某个状态下有多个动作同时达到最大的 action value，那么这些动作都可以构成最优策略。因此最优策略可能不唯一。

对应地，最优 Q value 满足：

$q^*(s,a) = \sum_{s^{\prime}\in\mathcal{S}} \sum_{r\in\mathcal{R}} p(s^{\prime},r\mid s,a) \left[ r+\gamma \max_{a^{\prime}\in\mathcal{A}(s^{\prime})}q^*(s^{\prime},a^{\prime}) \right]$

当 $q^*(s,a)$ 已知时，一个确定性的 greedy policy 可以写成：

$\pi^*(s) \in \arg\max_{a\in\mathcal{A}(s)} q^*(s,a)$

如果用随机策略的形式表达，则可以写成：

$\pi^*(a\mid s) = \begin{cases} 1, & a \in \arg\max_{a^{\prime}\in\mathcal{A}(s)} q^*(s,a^{\prime})\\ 0, & \text{otherwise} \end{cases}$

如果有多个动作同时达到最大值，那么最优策略不一定唯一；可以固定选择其中一个动作，也可以在这些最优动作之间随机选择。

更多的概念和算法

这一节主要对应课程第 4 节到第 8 节，以及第 10 节中的内容。这部分更多是在介绍传统强化学习算法的发展脉络，和大模型中的强化学习应用关系没有那么直接。

如果我们的主要目标是理解 LLM 中的 RLHF、PPO、GRPO 这一类方法，那么这部分内容并不需要逐个公式深入推导。更重要的是掌握它们试图解决什么问题、属于哪一类方法，以及它们引入了哪些后来仍然会反复出现的概念。

所以这一节会尽量采用 QA 的形式组织：每个小节主要回答“这个算法是什么”“它在解决什么问题”“它和其他算法的关系是什么”,(算法的定义和目标).证明细节和复杂推导会尽量省略。

Value iteration 和 Policy iteration

Q: Value iteration 是什么？

Value iteration 是一种求解 Bellman optimality equation 的动态规划算法。它的目标是直接逼近最优价值函数 $v^*$，然后根据最优价值函数得到最优策略。

Bellman optimality equation 可以看成一个 fixed point equation。定义 Bellman optimality operator $\mathcal{T}$：

$(\mathcal{T}v)(s) = \max_{a\in\mathcal{A}(s)} \sum_{s^{\prime}\in\mathcal{S}} \sum_{r\in\mathcal{R}} p(s^{\prime},r\mid s,a) \left[ r+\gamma v(s^{\prime}) \right]$

那么 Bellman optimality equation 可以写成：

$v^* = \mathcal{T}v^*$

Value iteration 就是不断做下面这个更新：

$v_{k+1}(s) = (\mathcal{T}v_k)(s)$

也就是：

$v_{k+1}(s) = \max_{a\in\mathcal{A}(s)} \sum_{s^{\prime}\in\mathcal{S}} \sum_{r\in\mathcal{R}} p(s^{\prime},r\mid s,a) \left[ r+\gamma v_k(s^{\prime}) \right]$

直观上，它每一步都在问：如果我现在对下一状态的价值估计是 $v_k$，那么当前状态下最好的动作会带来多少价值？反复更新之后，$v_k$ 会逐渐逼近 $v^*$。

Value iteration 的前提是 model 已知，也就是我们知道环境动态 $p(s^{\prime},r\mid s,a)$。如果不知道环境模型，就无法直接把所有可能的 $s^{\prime}$ 和 $r$ 都枚举出来求期望。

Q: Policy iteration 是什么？

Policy iteration 是另一种经典动态规划算法。它不是直接迭代最优价值函数，而是在“评估当前策略”和“改进当前策略”之间交替进行。

和 value iteration 一样，policy iteration 也要求 model 已知。因为 policy evaluation 需要构造 $\mathbf{r}{\pi_k}$ 和 $\mathbf{P}{\pi_k}$，policy improvement 也需要根据模型计算每个动作的一步期望回报。

它包含两个步骤：

Policy evaluation：给定当前策略 $\pi_k$，计算它对应的价值函数 $v_{\pi_k}$。
Policy improvement：根据 $v_{\pi_k}$ 构造一个更好的策略 $\pi_{k+1}$。

Policy evaluation 解的是普通 Bellman equation：

$\mathbf{v}_{\pi_k} = \mathbf{r}_{\pi_k} + \gamma \mathbf{P}_{\pi_k}\mathbf{v}_{\pi_k}$

Policy improvement 则是在每个状态上选择 greedy action：

$\pi_{k+1}(s) \in \arg\max_{a\in\mathcal{A}(s)} q_{\pi_k}(s,a)$

所以 policy iteration 的核心结构是：

$\pi_0 \xrightarrow{\text{policy evaluation}} v_{\pi_0} \xrightarrow{\text{policy improvement}} \pi_1 \xrightarrow{\text{policy evaluation}} v_{\pi_1} \xrightarrow{\text{policy improvement}} \cdots$

它的直观含义是：先认真评估当前策略到底有多好，然后根据这个评估结果改进策略。

Q: Value iteration 和 Policy iteration 有什么区别？

二者都需要环境模型，因此都属于 model-based 的动态规划方法。区别在于它们“评估策略”的程度不同。

Policy iteration 在每次改进策略之前，会尽量把当前策略 $\pi_k$ 的价值 $v_{\pi_k}$ 评估清楚。它的 policy evaluation 可能需要解线性方程组，或者进行多次迭代。

Value iteration 则更急。它不会完整评估某一个策略，而是每轮只做一次 Bellman optimality update，然后马上继续改进价值估计。可以把它理解成“边评估，边改进”，而不是“评估充分之后再改进”。

从这个角度看：

Policy iteration：每一步更重，通常迭代次数更少。
Value iteration：每一步更轻，通常需要更多轮迭代。

Q: Truncated policy iteration 是什么？

Truncated policy iteration 介于 value iteration 和 policy iteration 之间。

Policy iteration 的 policy evaluation 如果完整做完，可能很贵；value iteration 又只做一步 evaluation。Truncated policy iteration 的想法是：在 policy evaluation 里只做有限步迭代，然后就进行 policy improvement。

所以它可以看成一个连续谱：

Value iteration：policy evaluation 只做一步。
Truncated policy iteration：policy evaluation 做有限步。
Policy iteration：policy evaluation 做到充分收敛。

这个视角很重要，因为它说明很多 RL 算法并不是完全割裂的，而是在“评估多少”和“改进多快”之间做不同折中。

Monte Carlo Learning

Q: Monte Carlo 方法在 RL 里面做什么？

Monte Carlo 方法的核心思想是用采样平均来估计期望。RL 里面的 state value 和 action value 本来就是期望：

$v_\pi(s) = \mathbb{E}_\pi[G_t\mid S_t=s]$ $q_\pi(s,a) = \mathbb{E}_\pi[G_t\mid S_t=s,A_t=a]$

如果环境模型未知，我们无法通过 $p(s^{\prime},r\mid s,a)$ 直接计算这个期望。但我们可以让智能体真实地跑很多条轨迹，得到很多 return 样本，然后用平均 return 估计 value。

所以 Monte Carlo learning 是一种 model-free 方法：它不需要知道环境的转移概率，只需要能和环境交互并采样轨迹。

Q: MC Basic 是什么？

MC Basic 可以看作 policy iteration 的 model-free 版本。

在 model-based policy iteration 中，policy evaluation 通过 Bellman equation 计算 $q_{\pi_k}(s,a)$。但在 model-free 场景下，我们不知道环境模型，所以改用采样估计：

$q_{\pi_k}(s,a) = \mathbb{E}_{\pi_k}[G_t\mid S_t=s,A_t=a] \approx \frac{1}{N} \sum_{i=1}^{N} g^{(i)}(s,a)$

其中 $g^{(i)}(s,a)$ 表示从 $(s,a)$ 出发、之后按照 $\pi_k$ 行动得到的一次 return 样本。

估计出 $q_{\pi_k}(s,a)$ 之后，再做 greedy policy improvement：

$\pi_{k+1}(s) \in \arg\max_{a} q_{\pi_k}(s,a)$

它的核心问题是效率比较低，因为为了估计每个 $(s,a)$，可能需要从大量 state-action pair 分别出发采样。

完整的 Monte Carlo control 循环大致是：

初始化 $q(s,a)$，并初始化一个策略 $\pi$。
按照当前策略 $\pi$ 采样一条完整 episode。
从 episode 末尾往前计算每个时间步对应的 return。
对 episode 中访问到的 state-action pair $(s_t,a_t)$，用对应的 return 更新 $q(s_t,a_t)$。常见做法是对多次访问得到的 return 取平均。
根据新的 $q$ 改进策略，例如令 $\pi$ 变成 greedy policy 或 ε-greedy policy。
重复采样新的 episode，并持续更新 $q$ 和 $\pi$。

所以 MC control 的循环是“采样完整轨迹 -> 用完整 return 更新 action value -> 根据 action value 改进策略”。它和 TD 最大的差别是：MC 必须等 return 完整出现，而 TD 可以在每一步之后立刻更新。

Q: Exploring Starts 是什么？

Exploring Starts 是 Monte Carlo 方法中的一个理论条件。它要求每个 state-action pair $(s,a)$ 都有机会作为 episode 的起点。

为什么需要这个条件？因为如果某个动作从来没有被采样过，我们就无法估计它的 $q_\pi(s,a)$。而一个从未被尝试的动作，理论上可能恰好是最优动作。

所以 exploring starts 的作用是保证探索充分。但在真实任务里，它经常不现实。很多环境并不允许我们任意指定初始状态和初始动作。

Q: ε-greedy MC 是什么？

ε-greedy MC 的目标是去掉 exploring starts 这个很强的假设。它通过使用 soft policy 来保证每个动作都有非零概率被选中。

ε-greedy policy 的典型形式是：

$\pi(a\mid s) = \begin{cases} 1-\epsilon+\frac{\epsilon}{|\mathcal{A}(s)|}, & a=a^*(s)\\ \frac{\epsilon}{|\mathcal{A}(s)|}, & a\ne a^*(s) \end{cases}$

其中 $a^*(s)$ 是当前估计下的 greedy action。

ε-greedy 的意义是平衡 exploration 和 exploitation：

exploitation：大概率选择当前看起来最好的动作。
exploration：小概率尝试其他动作，避免过早错过潜在好动作。

Temporal-Difference Learning

Q: TD learning 是什么？

Temporal-Difference learning，简称 TD learning，是强化学习里非常核心的一类 model-free 算法。它的目标是在不需要环境模型的情况下，从经验样本中估计 value。

最基础的 TD state value update 是：

$v_{t+1}(s_t) = v_t(s_t) + \alpha_t \left[ r_{t+1} + \gamma v_t(s_{t+1}) - v_t(s_t) \right]$

其中：

$r_{t+1}+\gamma v_t(s_{t+1})$ 称为 TD target。
$r_{t+1}+\gamma v_t(s_{t+1})-v_t(s_t)$ 称为 TD error。

TD 的关键特征是 bootstrapping：它用当前估计出来的 $v_t(s_{t+1})$ 作为目标的一部分。因此 TD 并不需要等一整条 episode 结束才能更新。

从形式上看，TD learning 使用的正是后文 Robbins-Monro / Stochastic Approximation 的思想：用一个带噪声的采样目标不断修正当前估计。更具体地说，TD target $r_{t+1}+\gamma v_t(s_{t+1})$ 可以看作 Bellman expectation target 的一次采样近似。关于这个 general 视角，可以参考后文 Robbins-Monro / Stochastic Approximation 是什么？。

Q: TD 和 MC 的区别是什么？

MC 和 TD 都是 model-free 方法，但它们使用经验数据的方式不同。

MC 使用完整 return：

$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots$

TD 使用一步 TD target：

$R_{t+1} + \gamma v_t(S_{t+1})$

所以 MC 的特点是：

必须等 episode 结束之后才能计算 return。
不 bootstrapping。
方差通常更大，但 bias 相对更小。

TD 的特点是：

每走一步就可以更新。
bootstrapping。
可以处理 continuing task。
方差通常更小，但会引入来自当前估计的 bias。

Q: On-policy 和 Off-policy 是什么？

在 TD control 算法里，理解 Sarsa 和 Q-learning 的关键是区分 behavior policy 和 target policy。

Behavior policy：实际和环境交互、产生样本的策略。
Target policy：算法真正想评估或优化的策略。

如果 behavior policy 和 target policy 是同一个策略，那么算法是 on-policy：

$\beta = \pi$

如果 behavior policy 和 target policy 可以不同，那么算法是 off-policy：

$\beta \ne \pi$

这里的 $\beta$ 表示 behavior policy，$\pi$ 表示 target policy。

这个定义放在 Sarsa 和 Q-learning 前面非常重要，因为二者的核心差别不只是 TD target 长得不一样，而是它们学习的目标策略不同。

Q: Sarsa 是什么？

Sarsa 是 TD learning 在 action value 上的版本。它估计的是当前策略 $\pi$ 下的 $q_\pi(s,a)$。

它的名字来自一次更新需要用到的五元组：

$(S_t,A_t,R_{t+1},S_{t+1},A_{t+1})$

Sarsa 的更新形式是：

$q_{t+1}(s_t,a_t) = q_t(s_t,a_t) + \alpha_t \left[ r_{t+1} + \gamma q_t(s_{t+1},a_{t+1}) - q_t(s_t,a_t) \right]$

因为 $a_{t+1}$ 是按照当前策略 $\pi$ 采样出来的，所以 Sarsa 是 on-policy 算法。

完整的 Sarsa control 循环大致是：

初始化 $q(s,a)$，并根据 $q$ 构造一个策略 $\pi$，例如 ε-greedy policy。
在当前状态 $s_t$ 下，按照当前策略 $\pi$ 采样动作 $a_t$。
执行动作 $a_t$，环境返回奖励 $r_{t+1}$ 和下一个状态 $s_{t+1}$。
在新状态 $s_{t+1}$ 下，继续按照同一个当前策略 $\pi$ 采样动作 $a_{t+1}$。
用五元组 $(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$ 更新 $q(s_t,a_t)$。
根据新的 $q$ 改进策略，例如重新令 $\pi$ 成为关于 $q$ 的 ε-greedy policy。
令 $s_t\leftarrow s_{t+1}$，$a_t\leftarrow a_{t+1}$，继续下一步交互。

这里最关键的点是：Sarsa 用当前策略采样 $a_{t+1}$，也用这个 $a_{t+1}$ 构造 TD target。因此它学习的是当前策略自己的 action value，并在这个基础上逐步改进当前策略。

从 on/off-policy 的角度看，Sarsa 的 behavior policy 和 target policy 是同一个策略。它怎么采样，就怎么学习；它学习的正是当前正在执行的策略。因此 Sarsa 是 on-policy。

Q: n-step Sarsa 是什么？

n-step Sarsa 介于 one-step Sarsa 和 Monte Carlo 之间。它不用只看一步 TD target，也不一定等到完整 episode 结束，而是看未来 $n$ 步的奖励，再接上第 $n$ 步后的 value 估计。

它的 target 可以写成：

$R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1}R_{t+n} + \gamma^n q_t(S_{t+n},A_{t+n})$

当 $n=1$ 时，它就是普通 Sarsa；当 $n$ 趋近于 episode 长度时，它就接近 Monte Carlo。

所以 n-step 方法可以看成在 bias 和 variance 之间调节：

$n$ 小：更像 TD，更新快，方差小，但 bootstrapping bias 更强。
$n$ 大：更像 MC，bias 小，但方差更大。

Q: Q-learning 是什么？

Q-learning 是一种直接估计最优 action value $q^*(s,a)$ 的 TD 算法。它的更新是：

$q_{t+1}(s_t,a_t) = q_t(s_t,a_t) + \alpha_t \left[ r_{t+1} + \gamma \max_{a\in\mathcal{A}(s_{t+1})}q_t(s_{t+1},a) - q_t(s_t,a_t) \right]$

和 Sarsa 的区别在于 target：

Sarsa 使用实际采样到的 $a_{t+1}$。
Q-learning 使用下一状态下的最大 action value。

因此 Q-learning 的目标策略是 greedy policy，但行为策略可以是别的探索策略。所以 Q-learning 是 off-policy 算法。

完整的 Q-learning control 循环大致是：

初始化 $q(s,a)$，并设置一个 behavior policy $\beta$，例如 ε-greedy policy。
在当前状态 $s_t$ 下，按照 $\beta$ 采样动作 $a_t$。
执行动作 $a_t$，环境返回奖励 $r_{t+1}$ 和下一个状态 $s_{t+1}$。
用 $r_{t+1}+\gamma\max_a q(s_{t+1},a)$ 更新 $q(s_t,a_t)$。
根据新的 $q$ 更新 target policy，例如令 target policy 在每个状态下选择 $\arg\max_a q(s,a)$。
Behavior policy 可以继续保持 ε-greedy，以便继续探索。
令 $s_t\leftarrow s_{t+1}$，继续采样下一步。

这里最关键的点是：采样动作 $a_t$ 可以来自带探索的 behavior policy，但更新目标里面使用的是 $\max_a q(s_{t+1},a)$，也就是 greedy target policy。因此 Q-learning 可以一边探索，一边学习 greedy 最优策略。

从 on/off-policy 的角度看，Q-learning 的 behavior policy 可以是 ε-greedy 这类探索策略，但 target policy 是 greedy policy。采样策略和学习目标不必相同，因此 Q-learning 是 off-policy。

Q: TD 算法属于 general algorithm 还是 RL 算法？

TD learning 本身是 RL 算法。它的对象是 value function，它的样本来自 agent 和 environment 的交互，它要解决的是 Bellman equation 或 Bellman optimality equation。

但是，TD learning 可以从 stochastic approximation 的角度理解。也就是说，它在数学形式上像 Robbins-Monro 这一类随机近似算法：

$\text{new estimate} = \text{old estimate} + \alpha \left[ \text{target} - \text{old estimate} \right]$

所以更准确地说：TD 是 RL 算法，但它的理论解释可以借助 general stochastic approximation。

Value Function Methods

Q: 为什么需要 value function approximation？

前面讨论的很多算法默认 value function 可以用表格存储。例如每个状态 $s$ 都有一个 $v(s)$，每个 state-action pair $(s,a)$ 都有一个 $q(s,a)$。

这在小规模离散环境中是可行的，但如果状态空间很大，甚至是连续的，表格方法就会遇到两个问题：

存储困难：状态太多，无法给每个状态单独存一个值。
泛化能力弱：表格只记住见过的状态，不能自然泛化到相似但没见过的状态。

Value function approximation 的想法是用一个参数化函数近似 value：

$\hat{v}(s,w) \approx v_\pi(s)$

或者：

$\hat{q}(s,a,w) \approx q_\pi(s,a)$

其中 $w$ 是参数，可以是线性模型的权重，也可以是神经网络参数。

Q: 从 tabular value 到 function approximation 发生了什么变化？

在 tabular 方法中，更新一个状态的 value 只会改变表格中的一个 entry。

而在 function approximation 中，更新的是参数 $w$。因为多个状态共享同一组参数，所以一次更新可能同时影响很多状态的 value 估计。

这带来了两个结果：

好处：模型可以把一个状态上学到的信息泛化到相似状态。
风险：更新一个状态时，也可能破坏其他状态上的估计。

这也是为什么 function approximation 之后，优化稳定性会变得更重要。

Q: Sarsa with function approximation 是什么？

Sarsa with function approximation 是把 Sarsa 中的表格 $q(s,a)$ 换成参数化函数 $\hat{q}(s,a,w)$。

这里先解释一下 TD target 是什么。我们希望 $\hat{q}(s_t,a_t,w)$ 能逼近真实的 $q_\pi(s_t,a_t)$。而根据 Bellman expectation equation，真实的 $q_\pi(s_t,a_t)$ 应该满足：

$q_\pi(s_t,a_t) = \mathbb{E}_\pi \left[ R_{t+1} + \gamma q_\pi(S_{t+1},A_{t+1}) \mid S_t=s_t,A_t=a_t \right]$

但是在 model-free 场景下，我们无法直接计算这个期望，只能拿到一次真实采样：

$(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$

于是就用这一次采样得到的“一步奖励 + 下一步估计价值”作为当前 $q(s_t,a_t)$ 应该靠近的目标。这个目标就叫 TD target。

就是用一步采样的样本近似上面的期望, $q(s_t,a_t) \approx r_{t+1}+\gamma \hat{q}(s_{t+1},a_{t+1}) $

回到普通 Sarsa。对于一次经验样本：

$(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$

TD target 写作：

$y_t = r_{t+1} + \gamma \hat{q}(s_{t+1},a_{t+1},w_t)$

这里的 $y_t$ 不是一个新的真实标签，而是由当前样本和当前 value estimate 构造出来的训练目标。它之所以是“TD”的，是因为它只向前看一步，然后用 $\hat{q}(s_{t+1},a_{t+1},w_t)$ 进行 bootstrapping。

在 tabular Sarsa 中，我们可以直接更新表格里的 $q(s_t,a_t)$。但是在 function approximation 中，$q(s_t,a_t)$ 是函数输出：

$\hat{q}(s_t,a_t,w)$

所以我们不能直接“改一个表格 entry”，而是要调整参数 $w$，让函数输出更接近 TD target。

因此定义 TD error：

$\delta_t = y_t - \hat{q}(s_t,a_t,w_t)$

也就是：

$\delta_t = r_{t+1} + \gamma \hat{q}(s_{t+1},a_{t+1},w_t) - \hat{q}(s_t,a_t,w_t)$

既然我们希望 TD error 越小越好，一个自然做法是构造平方损失：

$L(w) = \frac{1}{2} \left[ y_t - \hat{q}(s_t,a_t,w) \right]^2 = \frac{1}{2}\delta_t^2$

构造这个 loss 之后，就可以使用梯度下降来更新参数：

$w \leftarrow w - \alpha \nabla_w L(w)$

所以 Sarsa with function approximation 的训练过程可以理解为：不断采样 $(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$，用 Sarsa 的 TD target 构造监督信号，再用梯度下降训练 $\hat{q}(s,a,w)$。

它仍然是 on-policy，因为下一步动作 $a_{t+1}$ 来自当前策略。Function approximation 只是把表格 $q(s,a)$ 换成 $\hat{q}(s,a,w)$，不改变 on/off-policy 的分类。

完整流程大致是：

初始化参数 $w$，并根据 $\hat{q}(s,a,w)$ 构造一个策略 $\pi$，例如 ε-greedy policy。
在当前状态 $s_t$ 下，按照 $\pi$ 采样动作 $a_t$。
执行动作 $a_t$，环境返回 $r_{t+1}$ 和 $s_{t+1}$。
在 $s_{t+1}$ 下继续按照 $\pi$ 采样 $a_{t+1}$。
构造 TD target：

$r_{t+1} + \gamma \hat{q}(s_{t+1},a_{t+1},w_t)$

用 TD error 对平方损失做梯度下降，更新参数 $w$。
根据新的 $\hat{q}$ 更新策略，例如重新构造 ε-greedy policy。
令 $s_t\leftarrow s_{t+1}$，$a_t\leftarrow a_{t+1}$，继续下一步。

这里和表格 Sarsa 的循环完全一致，区别只是更新对象从表格 entry 变成了函数参数 $w$。

Q: Q-learning with function approximation 是什么？

Q-learning with function approximation 是把 Q-learning 中的表格 $q(s,a)$ 换成参数化函数 $\hat{q}(s,a,w)$。

和 tabular Q-learning 一样，它想逼近的是最优 action value $q^*(s,a)$。这个最优值满足 action-value 形式的 Bellman optimality equation：

$q^*(s_t,a_t) = \mathbb{E} \left[ R_{t+1} + \gamma \max_{a\in\mathcal{A}(S_{t+1})} q^*(S_{t+1},a) \mid S_t=s_t,A_t=a_t \right]$

但在 model-free 场景下，我们不能直接计算这个期望，只能用一次采样 $(s_t,a_t,r_{t+1},s_{t+1})$ 来构造一步 bootstrap 的样本目标。再把未知的 $q^*$ 用当前估计 $\hat{q}(\cdot,\cdot,w_t)$ 替换，就得到 Q-learning with function approximation 的 TD target：

$y_t = r_{t+1} + \gamma \max_{a\in\mathcal{A}(s_{t+1})} \hat{q}(s_{t+1},a,w_t)$

这个方法是 DQN 的前身。它仍然是 off-policy，因为它可以用探索策略采样数据，但 TD target 使用的是 greedy target。它的核心风险是：Q-learning 本来就是 off-policy，再叠加 function approximation 和 bootstrapping，训练可能变得不稳定。

完整流程大致是：

初始化参数 $w$，并设置一个 behavior policy $\beta$，例如 ε-greedy policy。
在当前状态 $s_t$ 下，按照 $\beta$ 采样动作 $a_t$。
执行动作 $a_t$，环境返回 $r_{t+1}$ 和 $s_{t+1}$。
用一步 bootstrap 样本近似 Bellman optimality equation 中的期望，构造 greedy TD target：

$y_t = r_{t+1} + \gamma \max_{a\in\mathcal{A}(s_{t+1})} \hat{q}(s_{t+1},a,w_t)$

用 TD error 更新参数 $w$。如果用平方误差作为损失，可以写成：

$\left[ r_{t+1} + \gamma \max_{a\in\mathcal{A}(s_{t+1})} \hat{q}(s_{t+1},a,w_t) - \hat{q}(s_t,a_t,w_t) \right]^2$

根据新的 $\hat{q}$ 更新 target policy，例如令 target policy 在每个状态下选择 $\arg\max_a \hat{q}(s,a,w)$。
Behavior policy 可以继续保持 ε-greedy，以便继续探索。
令 $s_t\leftarrow s_{t+1}$，继续下一步采样。

这里和表格 Q-learning 的循环也一致，区别同样只是更新对象从表格 entry 变成了函数参数 $w$。

Q: Deep Q-learning / DQN 是什么？

DQN 可以理解为用深度神经网络表示 Q function 的 Q-learning。它仍然是在学习最优 action value $q^*(s,a)$，只是把表格 $q(s,a)$ 换成了神经网络：

$\hat{q}(s,a,w) \approx q^*(s,a)$

其中 $w$ 是主网络，也就是 online network 的参数。给定状态 $s$，网络可以输出每个动作的 Q value；策略通常取 greedy 或 ε-greedy：

$a \in \arg\max_{a^{\prime}\in\mathcal{A}(s)} \hat{q}(s,a^{\prime},w)$

DQN 的更新仍然来自 Bellman optimality equation。最优 action value 满足：

$q^*(s_t,a_t) = \mathbb{E} \left[ R_{t+1} + \gamma \max_{a\in\mathcal{A}(S_{t+1})} q^*(S_{t+1},a) \mid S_t=s_t,A_t=a_t \right]$

这个式子说明：$q^*(s_t,a_t)$ 是“一步奖励 + 下一状态最优 Q value”的条件期望。DQN 在 model-free 场景下无法直接计算这个期望，所以用一次经验样本：

$(s_t,a_t,r_{t+1},s_{t+1})$

来构造一步 bootstrap 的样本目标。DQN 通常用 target network $\hat{q}(\cdot,\cdot,w^{-})$ 估计下一状态的 Q value，因此 TD target 写作：

$y_t = r_{t+1} + \gamma \max_{a\in\mathcal{A}(s_{t+1})} \hat{q}(s_{t+1},a,w^{-})$

主网络当前对 $(s_t,a_t)$ 的预测是 $\hat{q}(s_t,a_t,w)$。因此 TD error 定义为：

$\delta_t = y_t - \hat{q}(s_t,a_t,w)$

展开就是：

$\delta_t = r_{t+1} + \gamma \max_{a\in\mathcal{A}(s_{t+1})} \hat{q}(s_{t+1},a,w^{-}) - \hat{q}(s_t,a_t,w)$

这里 $w^{-}$ 表示 target network 的参数。因为我们希望 TD error 越小越好，所以构造平方损失：

$L(w) = \frac{1}{2} \left[ y_t - \hat{q}(s_t,a_t,w) \right]^2 = \frac{1}{2}\delta_t^2$

然后用梯度下降或者深度学习优化器更新主网络参数：

$w \leftarrow w - \alpha \nabla_w L(w)$

所以 DQN 的训练过程可以理解为：不断采样经验 $(s_t,a_t,r_{t+1},s_{t+1})$，用 Q-learning 的 TD target 构造监督信号，再用梯度下降训练主网络，让 $\hat{q}(s,a,w)$ 逐渐接近最优 Q function。

DQN 中两个非常重要的工程技巧是：

Experience replay：把历史经验存到 replay buffer 中，训练时随机采样 mini-batch。
Target network：用一个更新较慢的网络计算 TD target，减少训练目标剧烈变化。

Q: DQN 为什么需要两个网络？

从概念上说，完全可以把 DQN 看成普通的 Q-learning with function approximation：只用一个神经网络 $\hat{q}(s,a,w)$ 表示 Q value，然后也用这个网络构造 TD target：

$y_t = r_{t+1} + \gamma \max_{a\in\mathcal{A}(s_{t+1})} \hat{q}(s_{t+1},a,w)$

问题在于，这样 target 和 prediction 都依赖同一组参数 $w$。一边用梯度下降更新 $w$，一边又用同一个 $w$ 生成学习目标，等于让网络追逐一个不断移动的目标。在深度神经网络中，这种 bootstrapping + function approximation + off-policy 的组合很容易导致训练振荡甚至发散。

因此 DQN 引入 target network：

$\hat{q}(s,a,w^{-})$

它和主网络结构相同，也表示 Q value，但参数 $w^{-}$ 暂时固定，只用来计算 TD target：

$y_t = r_{t+1} + \gamma \max_{a\in\mathcal{A}(s_{t+1})} \hat{q}(s_{t+1},a,w^{-})$

主网络 $\hat{q}(s,a,w)$ 负责被梯度下降更新，target network $\hat{q}(s,a,w^{-})$ 负责提供相对稳定的学习目标。每隔一段时间，再把主网络参数复制给 target network：

$w^{-} \leftarrow w$

所以这两个网络不是在学习两个不同的价值函数。它们本质上都是对 $q^*(s,a)$ 的近似；区别只是主网络是正在学习的估计，target network 是延迟更新的估计。

Policy Gradient 和 Actor-Critic Methods

Q: 为什么 Actor-Critic 需要先理解 policy gradient？

Value-based 方法的基本思路是先学价值函数，然后从价值函数导出策略。Policy gradient 方法则直接把策略写成参数化函数：

$\pi(a\mid s,\theta)$

然后定义一个标量目标 $J(\theta)$，用梯度上升优化策略参数：

$\theta_{t+1} = \theta_t + \alpha \nabla_\theta J(\theta_t)$

Actor-Critic 本质上仍然是 policy gradient 方法，只是它用一个 critic 来估计 value，从而帮助 actor 更新策略。

Q: Actor-Critic 是什么？

Actor-Critic 是一种把 policy-based 和 value-based 结合起来的框架。

Actor：负责表示和更新策略 $\pi(a\mid s,\theta)$。
Critic：负责估计 value，例如 $v(s,w)$ 或 $q(s,a,w)$，用来评价 actor 当前动作的好坏。

最简单地说，actor 决定怎么行动，critic 负责给 actor 的行动打分。

Q: Q Actor-Critic 是什么？

Q Actor-Critic，简称 QAC，是最直接的 Actor-Critic 形式。Actor 用 policy gradient 更新策略，Critic 估计 action value $q(s,a,w)$。

策略更新大致形如：

$\theta_{t+1} = \theta_t + \alpha_\theta \nabla_\theta \log \pi(a_t\mid s_t,\theta_t) q(s_t,a_t,w_t)$

Critic 则可以用类似 Sarsa + function approximation 的方式更新 $q(s,a,w)$。

Q: A2C / Advantage Actor-Critic 是什么？

A2C 的核心是把 Q value 换成 advantage：

$A_\pi(s,a) = q_\pi(s,a) - v_\pi(s)$

Advantage 表示：在状态 $s$ 下，动作 $a$ 比当前策略的平均水平好多少。

实际算法中，advantage 常常用 TD error 近似：

$\delta_t = r_{t+1} + \gamma v(s_{t+1},w_t) - v(s_t,w_t)$

于是 actor 更新变成：

$\theta_{t+1} = \theta_t + \alpha_\theta \delta_t \nabla_\theta \log \pi(a_t\mid s_t,\theta_t)$

A2C 的好处是使用 baseline $v_\pi(s)$ 降低策略梯度估计的方差。

Q: Off-policy Actor-Critic 是什么？

普通 policy gradient 通常是 on-policy 的，因为梯度期望里的动作需要来自当前策略 $\pi(a\mid s,\theta)$。

Off-policy Actor-Critic 允许 behavior policy $\beta$ 和 target policy $\pi$ 不同。为了修正采样分布不一致，常用 importance sampling weight：

$\frac{\pi(a_t\mid s_t,\theta)} {\beta(a_t\mid s_t)}$

直观上，如果某个动作在目标策略下更可能出现，但在行为策略下较少出现，就提高它的权重；反之则降低权重。

Q: Deterministic Policy Gradient / DPG 是什么？

前面的 policy gradient 通常使用随机策略 $\pi(a\mid s,\theta)$。DPG 则使用确定性策略：

$a = \mu(s,\theta)$

它适合连续动作空间，因为连续动作下对所有动作求概率分布再采样可能比较麻烦。DPG 的 actor 直接输出动作，critic 估计 $q(s,a,w)$，然后 actor 根据 $q$ 对动作的梯度来更新策略。

DDPG 可以看成 DPG 的深度学习版本：actor 和 critic 都用神经网络表示，并且通常配合 replay buffer 和 target network。

一些 General 算法和思想

Q: Monte Carlo estimation 是什么？

Monte Carlo estimation 是用采样平均估计期望：

$\mathbb{E}[X] \approx \frac{1}{N} \sum_{i=1}^{N} x_i$

它本身不是 RL 专属算法，但 RL 中很多对象都是期望，比如 value、return、policy gradient，所以 Monte Carlo 思想会反复出现。

Q: Robbins-Monro / Stochastic Approximation 是什么？

Robbins-Monro 算法属于 stochastic approximation。它解决的是这样一类问题：我们想求一个方程的根，

$g(w)=0$

其中 $w\in\mathbb{R}^d$ 是我们要寻找的未知参数，$g(w)$ 是一个确定性的函数。所谓确定性，是指只要 $w$ 给定，$g(w)$ 的值就是固定的。

困难在于：很多时候我们不能直接计算 $g(w_t)$(Model Free)。在第 $t$ 步，算法已经有了当前参数 $w_t$，但是只能通过一次随机采样得到一个 noisy observation：

$\tilde{g}(w_t,\xi_t)$

这里最容易混淆的是 $\xi_t$ 到底是什么。$\xi_t$ 不是参数 $w_t$，也不是 $g(w_t)$ 本身。它表示第 $t$ 次随机采样得到的信息，比如一个数据点、一个 mini-batch、一次随机实验结果，或者 RL 中一次环境交互得到的 transition。

也就是说：

$w_t$：当前算法手里的参数，通常可以看成已经确定的量。
$g(w_t)$：在 $w_t$ 处真正想知道的确定性函数值，但通常算不到。
$\xi_t$：第 $t$ 次采样带来的随机信息。
$\tilde{g}(w_t,\xi_t)$：用这次随机信息构造出来的 $g(w_t)$ 的 noisy observation。

Robbins-Monro 的关键假设是：这个 noisy observation 在条件期望意义下等于真正的 $g(w_t)$：

$\mathbb{E} \left[ \tilde{g}(w_t,\xi_t) \mid w_t \right] = g(w_t)$

所以，随机的来源不是“$g$ 这个函数随机”，而是我们每次只能通过随机样本 $\xi_t$ 去估计 $g(w_t)$。在 $w_t$ 固定时，$\tilde{g}(w_t,\xi_t)$ 会随着样本 $\xi_t$ 改变而改变；但它平均起来应该等于 $g(w_t)$。

Robbins-Monro 的更新形式是：

$w_{t+1} = w_t - \alpha_t \tilde{g}(w_t,\xi_t)$

其中 $\alpha_t>0$ 是 step size。这个迭代形式其实并没有它表面上看起来的那么trival,我们下文只列出它的收敛性条件,它的证明请参考原始课件的第六课.

一个直觉的理解方式：如果我们能直接计算 $g(w_t)$，做如下迭代,如果 $g(w_t)=0$,就已经找到了根.

$w_{t+1} = w_t - \alpha_t g(w_t)$

但现在 $g(w_t)$ 算不到，于是用 $\tilde{g}(w_t,\xi_t)$ 代替它。也就是说，stochastic approximation 是在用“带噪声的观测”逼近一个确定性的求根过程。

Robbins-Monro 的收敛条件

更严格地说，Robbins-Monro 算法的收敛性通常需要三类条件。为了和课程里的表述一致，先把 noisy observation 写成真实函数值加观测误差：

$\tilde{g}(w_t,\xi_t) = g(w_t) + \eta_t$

其中 $\eta_t$ 是第 $t$ 次采样带来的 observation error。设 $\mathcal{H}_t$ 表示第 $t$ 步之前已经产生的历史信息，例如：

$\mathcal{H}_t = \{w_t,w_{t-1},\ldots\}$

课程里给出的 Robbins-Monro 收敛条件可以概括为：

条件 1：$g$ 的方向要稳定，并且根要是唯一的。

在一维情形下，一个常见条件是存在常数 $c_1,c_2>0$，使得：

$0 < c_1 \le \nabla_w g(w) \le c_2$

它表示 $g(w)$ 单调递增，并且斜率既不会太小也不会太大。单调性保证 $g(w)=0$ 的根不会有多个；正的下界保证算法在根附近仍然有明确的修正方向；上界则避免函数变化过于剧烈。

条件 2：step size 要逐渐变小，但不能变得太快。

$\sum_{t=0}^{\infty}\alpha_t = \infty, \qquad \sum_{t=0}^{\infty}\alpha_t^2 < \infty$

这里 $\sum_t\alpha_t=\infty$ 表示总步长不能太小，否则算法可能还没有走到根附近就停住了；$\sum_t\alpha_t^2<\infty$ 表示步长要足够快地变小，使得随机噪声的累计影响可以被控制住。一个典型选择是 $\alpha_t=1/t$。

条件 3：观测误差不能有系统性偏差，并且方差要有限。

课程中写作：

$\mathbb{E} \left[ \eta_t \mid \mathcal{H}_t \right] = 0, \qquad \mathbb{E} \left[ \eta_t^2 \mid \mathcal{H}_t \right] < \infty$

第一个式子表示 noisy observation 平均起来不能总是偏向某个错误方向；第二个式子表示噪声不能无限大。一个常见的特殊情况是 $\eta_t$ 是 iid 的零均值、有限方差随机序列。它不要求噪声必须服从 Gaussian distribution。

在这些条件下，Robbins-Monro 迭代会以概率 1 收敛到 $g(w)=0$ 的根 $w^*$。这里的“以概率 1 收敛”表示：虽然每一次轨迹都会受到随机样本影响，但除了概率为 0 的异常情况，迭代最终都会收敛到正确的根。

应用: 求期望的值

先看一个具体例子：用 stochastic approximation 求期望。假设我们想求随机变量 $X$ 的均值：

$\mu = \mathbb{E}[X]$

如果令未知参数 $w$ 表示对 $\mu$ 的估计，那么这个问题可以写成求根问题：

$g(w) = w - \mathbb{E}[X] = 0$

如果每次只能拿到一个样本 $X_t$，那么这里的随机变量 $\xi_t$ 就可以具体理解为：

$\xi_t = X_t$

在当前参数 $w_t$ 下，$g(w_t)=w_t-\mathbb{E}[X]$ 算不到，因为 $\mathbb{E}[X]$ 算不到。但可以用样本 $X_t$ 构造 noisy observation：

$\tilde{g}(w_t,\xi_t) = \tilde{g}(w_t,X_t) = w_t - X_t$

它确实是 $g(w_t)$ 的无偏观测，因为：

$\mathbb{E} \left[ \tilde{g}(w_t,X_t) \mid w_t \right] = w_t - \mathbb{E}[X] = g(w_t)$

代入 Robbins-Monro 更新：

$w_{t+1} = w_t - \alpha_t (w_t-X_t)$

也就是：

$w_{t+1} = w_t + \alpha_t (X_t-w_t)$

这个例子说明：求期望 $\mathbb{E}[X]$ 可以转化成求 $g(w)=0$ 的根；每次样本 $X_t$ 就是随机观测 $\xi_t$，它帮助我们构造 $\tilde{g}(w_t,\xi_t)$。

应用2: TD learning 是 stochastic approximation 的一个实例

TD learning 和这个思想非常接近。先固定一个策略 $\pi$，再固定一个状态 $s$。按照 state value 的定义，$v_\pi(s)$ 满足：

$v_\pi(s) = \mathbb{E}_\pi \left[ R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t=s \right]$

这个式子本质上仍然是在求一个期望。把等式右边移到左边，就得到一个求根问题：

$v_\pi(s) - \mathbb{E}_\pi \left[ R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t=s \right] = 0$

为了和 Robbins-Monro 的记号一致，把当前 value estimate 记为 $w$。如果先不引入 function approximation，可以把 $w$ 理解为一张 value table，其中 $w(s)$ 是状态 $s$ 的 value estimate。于是对每个状态 $s$，可以定义：

$g_s(w) = w(s) - \mathbb{E}_\pi \left[ R_{t+1} + \gamma w(S_{t+1}) \mid S_t=s \right]$

我们想求的是：

$g_s(w) = 0, \qquad \forall s\in\mathcal{S}$

如果能精确计算这个期望，就可以直接得到 $g_s(w_t)$。但在 model-free RL 中，这个期望通常算不到。一次环境交互只给出一个 transition：

$\xi_t = (s_t,r_{t+1},s_{t+1})$

所以在 TD learning 里，$\xi_t$ 就是这一次环境交互得到的随机 transition。当访问到状态 $s_t$ 时，右侧期望

$\mathbb{E}_\pi \left[ R_{t+1} + \gamma w_t(S_{t+1}) \mid S_t=s_t \right]$

无法直接计算，但可以用这一次 transition 给出的样本来近似：

$r_{t+1} + \gamma w_t(s_{t+1})$

因此，$g_{s_t}(w_t)$ 的 noisy observation 可以写成：

$\tilde{g}(w_t,\xi_t)(s_t) = w_t(s_t) - \left[ r_{t+1} + \gamma w_t(s_{t+1}) \right]$

这和前面的求均值例子完全同构：真实的期望算不到，于是用一次样本构造 $\tilde{g}$。把它代入 Robbins-Monro 更新，就得到 TD(0) 的形式：

$w_{t+1}(s_t) = w_t(s_t) - \alpha_t \tilde{g}(w_t,\xi_t)(s_t)$

也就是：

$w_{t+1}(s_t) = w_t(s_t) + \alpha_t \left[ r_{t+1} + \gamma w_t(s_{t+1}) - w_t(s_t) \right]$

这里方括号里的量就是 TD error。为了和前面 TD learning 的记号对应，也可以把 $w_t(s)$ 重新记为 $v_t(s)$，于是得到熟悉的写法：

$v_{t+1}(s_t) = v_t(s_t) + \alpha_t \left[ r_{t+1} + \gamma v_t(s_{t+1}) - v_t(s_t) \right]$

所以，从 stochastic approximation 的角度看，TD learning 做的事情就是：把每个状态上的 value equation 写成 $g_s(w)=0$，再用一次次随机 transition $\xi_t=(s_t,r_{t+1},s_{t+1})$ 构造 $\tilde{g}(w_t,\xi_t)$，用 noisy observation 逼近这些方程的根。

Q: SGD、BGD、MBGD 分别是什么？

它们都是优化算法，用来最小化目标函数。

BGD，Batch Gradient Descent：每次用全部数据估计梯度。
SGD，Stochastic Gradient Descent：每次用一个样本估计梯度。
MBGD，Mini-batch Gradient Descent：每次用一小批样本估计梯度。

在深度学习里最常见的是 mini-batch SGD 及其变体。RL 中一旦引入 function approximation，尤其是神经网络，就会自然用到这些优化算法。

Q: Importance sampling 是什么？

Importance sampling 是一种用一个分布下的样本估计另一个分布下期望的方法。

如果样本来自 $p_1(x)$，但我们想估计 $p_0(x)$ 下的期望，可以写成：

$\mathbb{E}_{x\sim p_0}[f(x)] = \mathbb{E}_{x\sim p_1} \left[ \frac{p_0(x)}{p_1(x)} f(x) \right]$

这里的 $\frac{p_0(x)}{p_1(x)}$ 就是 importance weight。

在 RL 中，它常用于 off-policy 学习：数据来自 behavior policy，但我们希望估计 target policy 的目标。

强化学习中的概念总结

Model-based 和 Model-free

Model-based 指算法需要或者显式学习环境模型，例如 $p(s^{\prime},r\mid s,a)$。Value iteration 和 policy iteration 是典型 model-based 方法。

Model-free 指算法不需要显式知道环境模型，而是直接从经验样本中学习 value 或 policy。MC、TD、Sarsa、Q-learning、policy gradient、actor-critic 都属于 model-free 方法。

On-policy 和 Off-policy

这个概念前面已经在 TD learning 中结合 Sarsa 和 Q-learning 解释过，可以参考 On-policy 和 Off-policy 是什么？。这里再做一次统一总结。

On-policy 指 behavior policy 和 target policy 是同一个策略。也就是说，用当前正在学习的策略去采样数据，并更新这个策略自身。MC control、Sarsa、A2C 通常是 on-policy。

Off-policy 指 behavior policy 和 target policy 可以不同。Q-learning 是经典 off-policy 算法，因为它可以用探索策略采样数据，但学习的是 greedy target policy。Off-policy actor-critic 也是 off-policy。

这个分类和是否使用 function approximation 没有直接关系。Sarsa with function approximation 仍然是 on-policy，因为它用当前策略采样到的下一动作构造 target；Q-learning with function approximation 仍然是 off-policy，因为它可以用探索策略采样数据，却用 greedy target 构造更新目标。

Online 和 Offline

Online learning 指智能体可以边和环境交互边更新，比如 TD、Sarsa、Q-learning。

Offline learning 指需要先收集数据，再用固定数据集学习，或者至少需要等一整条 episode 完成之后再更新。Monte Carlo 方法通常更接近 offline，因为它需要完整 return。

这里要注意：现代语境里的 offline RL 往往特指“只用已有数据集训练，不再和环境交互”。这和课程中 MC 必须等 episode 结束的 offline 说法不是完全同一个层次，但核心区别都是“是否边采样边更新”。

Online / Offline 和 On-policy / Off-policy 的关系

Online / offline 和 on-policy / off-policy 是两组不同的分类，它们回答的问题不同。

Online / offline 关心的是数据如何产生：训练过程中是否还能继续和环境交互、继续采样新数据。On-policy / off-policy 关心的是数据由谁产生：产生数据的 behavior policy 和正在学习的 target policy 是否相同。

因此，off-policy 不等于 offline。Q-learning 和 DQN 通常是 off-policy，但它们可以是 online 的：智能体一边用 ε-greedy behavior policy 和环境交互，一边学习 greedy target policy。

反过来，offline RL 通常需要 off-policy 思想。原因是：如果数据集已经提前固定，训练时的当前策略 $\pi$ 已经不能再决定数据分布。数据来自某个历史 behavior policy $\beta$，而我们训练时往往希望得到一个新的、更好的 target policy $\pi$。这时 $\beta$ 和 $\pi$ 通常不同，所以问题天然带有 off-policy 性质。

所以，对“是不是只有 off-policy 的策略才能提前采集一大批数据，然后再训练”这个问题，可以这样理解：如果只是做 policy evaluation，并且固定数据刚好来自你要评估的同一个策略，那么可以把它看成 on-policy evaluation。但如果你希望用提前采好的数据不断改进策略，得到一个不同于数据采集策略的新策略，那么通常就需要 off-policy learning 的思想。

简单说：

数据设置	策略关系	典型例子
Online + On-policy	边采样边更新，数据来自当前策略	Sarsa、A2C、PPO 类方法
Online + Off-policy	边采样边更新，但 behavior policy 和 target policy 不同	Q-learning、DQN
Offline + Off-policy	数据集固定，训练目标策略通常不同于数据来源策略	Offline Q-learning、CQL、IQL
Offline + On-policy	数据固定且来自同一个目标策略，通常更像 policy evaluation	用固定轨迹评估某个策略,用来学习的话很别扭,一般没有这种算法.

Behavior policy 和 Target policy

Behavior policy 是用来产生数据的策略。Target policy 是算法真正想学习或评估的策略。

在 on-policy 方法中，二者相同。在 off-policy 方法中，二者不同。例如 Q-learning 中，behavior policy 可以是 ε-greedy 的探索策略，而 target policy 是 greedy policy。

Exploration 和 Exploitation

Exploration 是探索还不确定的动作，以免错过潜在更优选择。Exploitation 是利用当前已经知道的高价值动作。

ε-greedy 是最简单的探索机制：大部分时候选择当前最优动作，小概率随机尝试其他动作。

Policy gradient 和 actor-critic 中的随机策略也天然带有探索能力，因为 $\pi(a\mid s,\theta)$ 本身是一个动作分布。

从“期望”和“样本”理解 RL 算法

RL 算法很多时候看起来很杂，但很多算法都可以用同一个视角来理解：

先问：这个算法真正想估计的期望是什么？
再问：为了估计这个期望，它实际需要什么样的样本？

第一个问题的时候,尤其想一下这个期望到底是哪几个随机变量的联合期望? 要估计它,样本就要来它的联合分布. 类似的思想还有优化目标,先写优化目标的期望形式,再用样本来近似估计这个期望.

很多 RL 对象本质上都是期望。例如 value 是 return 的期望，Q value 是在给定 state-action 后 return 的期望，policy gradient 是某个随机梯度估计的期望。算法的差别，往往不在于“是不是在求期望”，而在于它选择了什么样的期望形式，以及用什么样的样本去近似这个期望。

一个统一模板是：

$\text{target} = \mathbb{E} \left[ \text{random quantity} \right]$

实际训练时，我们通常拿不到这个期望，只能采样一个或一批样本，构造 sampled target，然后让当前 estimate 靠近这个 sampled target。

这个视角很有用，因为很多概念都可以放回这个框架里理解：

On-policy / off-policy：样本来自哪个策略？
Online / offline：样本是在训练中继续采，还是训练前已经固定？
Monte Carlo / TD / n-step / GAE：用多长的轨迹样本估计目标？
Bootstrapping：样本目标里是否用当前 value 或 Q estimate 补未来？

下面用几个典型算法对齐一下。这里用 HTML table，是为了避免 Markdown 表格中的 LaTeX 公式渲染不稳定。

算法	想估计的期望	实际需要的样本	样本目标或估计量
Monte Carlo value	$v_\pi(s)=\mathbb{E}_\pi[G_t\mid S_t=s]$	从 $s$ 开始的一整条 episode	完整 return $G_t$
TD(0)	$v_\pi(s)=\mathbb{E}_\pi[R_{t+1}+\gamma v_\pi(S_{t+1})\mid S_t=s]$	一步 transition $(s_t,r_{t+1},s_{t+1})$	$r_{t+1}+\gamma v_t(s_{t+1})$
Sarsa	$q_\pi(s,a)=\mathbb{E}_\pi[R_{t+1}+\gamma q_\pi(S_{t+1},A_{t+1})\mid S_t=s,A_t=a]$	$(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$	$r_{t+1}+\gamma q_t(s_{t+1},a_{t+1})$
Q-learning	$q^(s,a)=\mathbb{E}[R_{t+1}+\gamma\max_{a^{\prime}}q^(S_{t+1},a^{\prime})\mid S_t=s,A_t=a]$	$(s_t,a_t,r_{t+1},s_{t+1})$	$r_{t+1}+\gamma\max_{a^{\prime}}q_t(s_{t+1},a^{\prime})$
DQN	Q-learning 的 Bellman optimality target	replay buffer 中的 transition mini-batch	$r+\gamma\max_a\hat{q}(s^{\prime},a,w^{-})$
Policy gradient	$\nabla_\theta J(\theta)=\mathbb{E}[\nabla_\theta\log\pi_\theta(A_t\mid S_t)G_t]$	on-policy trajectory	likelihood-ratio gradient sample
Actor-Critic	policy gradient 中的 return / advantage 期望	transition 或短 rollout	TD error / advantage estimate
GAE	advantage 的加权多步估计	一段 rollout	多个 TD error 的折扣加权和

这个表格也解释了为什么 RL 算法的采样方式会不同。Monte Carlo 需要完整 episode，因为它直接用完整 return 估计期望；TD(0) 只需要一步 transition，因为它把期望写成一步 reward 加下一状态 value；Sarsa 需要额外采样 $a_{t+1}$，因为它的 target 里有下一步动作；Q-learning 不需要采样 target action，因为它直接对下一状态的 action value 取最大值。

所以，理解一个 RL 算法时，一个很好的检查顺序是：

它要估计哪个期望？
这个期望条件在什么变量上？
为了构造这个期望的样本估计，需要采样哪些随机变量？
这个 sampled target 有没有 bootstrapping？

RL 中的样本构造

RL 里很多术语都和“样本长什么样”有关。最核心的对象是 trajectory，其他很多词都可以看成 trajectory 的不同切片、不同用途，或者生成 trajectory 的过程。

Trajectory 指一整条交互序列。常见写法是：

$\tau = (s_0,a_0,r_1,s_1,a_1,r_2,\ldots,s_T)$

这里 $s_t$ 是状态，$a_t$ 是动作，$r_{t+1}$ 是从 $s_t$ 执行 $a_t$ 后得到的奖励，$s_{t+1}$ 是下一个状态。也可以把 terminal state 后的最后一个动作和奖励写进序列，具体记号会随教材略有差异。

Episode 通常指有明确开始和结束的一条完整 trajectory。它强调的是“这次交互从初始状态开始，并且到某个 terminal state 结束”。例如一局游戏、一次机器人导航任务、一次完整对话，都可以看成一个 episode。

Transition 是 trajectory 中的一步，通常写成：

$(s_t,a_t,r_{t+1},s_{t+1})$

它是很多 value-based 方法的基本样本单位。比如 TD(0)、Q-learning、DQN 的更新通常只需要一个 transition。

有些算法还需要把下一步动作也作为样本的一部分，例如 Sarsa 的更新目标包含 $a_{t+1}$，因此它需要：

$(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$

Rollout 更强调“生成样本的过程”。让当前策略 $\pi$ 在环境里运行一段时间，采样出一条 trajectory 或一段 partial trajectory，这个过程就叫 rollout。也就是说：

$\text{rollout} \quad \Longrightarrow \quad \text{trajectory}$

在 LLM 语境中也常说 rollout：给定 prompt，让模型根据当前策略生成一段回答，这也是一次 rollout。生成出来的 token 序列就可以看成 trajectory。

Replay buffer 是保存样本的数据容器。它可以保存 transition，也可以保存整条 trajectory 或短 rollout。DQN 这类 off-policy 方法常用 replay buffer：先把历史 transition 存起来，训练时再随机采样 mini-batch。

所以这些词可以用一个简单关系串起来：

Rollout（采样过程）
    ↓
Trajectory（完整或部分交互序列）
    ↓
Episode（有终止状态的一整条 trajectory）
    ↓
Transition（trajectory 中的一步）

不同算法需要不同粒度的样本。TD 和 Q-learning 通常只需要 transition；Sarsa 需要多一个下一步动作；Monte Carlo 和 policy gradient 往往需要一整条 trajectory 或 episode；GAE 和 actor-critic 常用一段 rollout 来构造 advantage estimate。

Bootstrapping 和 Non-bootstrapping

Bootstrapping 指更新目标里使用了当前 value estimate。例如 TD target：

$R_{t+1} + \gamma v_t(S_{t+1})$

这里的 $v_t(S_{t+1})$ 是当前估计值，所以 TD 是 bootstrapping。

更准确地说，bootstrapping 不是“截断轨迹”本身，而是“截断之后用当前估计值补上未来部分”。例如完整 return 是：

$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots$

TD(0) 没有等到完整 return，而是在一步后截断，并用当前估计 $v_t(S_{t+1})$ 代替后面的未来回报：

$R_{t+1} + \gamma v_t(S_{t+1})$

这就是 bootstrapping。

但不是所有截断轨迹的方法都叫 bootstrapping。如果只取前 $n$ 步奖励，然后直接忽略后面的未来：

$R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1}R_{t+n}$

这只是 truncated return，不是 bootstrapping。因为它没有使用当前 value estimate 或 Q estimate。

如果截断后接上当前估计值：

$R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1}R_{t+n} + \gamma^n v_t(S_{t+n})$

这才是 n-step bootstrapping。

所以可以这样区分：

方法	是否截断轨迹	是否 bootstrapping
Monte Carlo	否，等完整 episode	否
TD(0)	是，一步截断	是
n-step TD	是，$n$ 步截断	是，如果后面接 $v_t(S_{t+n})$
Truncated return without value estimate	是	否
GAE / λ-return	混合多个 n-step return	通常是
Q-learning / DQN	是，一步截断	是

所以，一个更准确的说法是：很多 bootstrapping 方法都会截断轨迹，但不是所有截断轨迹的方法都是 bootstrapping。只有当截断后用当前 value estimate 或 Q estimate 去补未来部分时，才叫 bootstrapping。

Monte Carlo 使用完整 return，不依赖当前 value estimate，因此是 non-bootstrapping。TD、Sarsa、Q-learning、DQN 都是 bootstrapping，因为它们的更新目标里都用了当前的 value 或 Q estimate。

Tabular 和 Function Approximation

Tabular 方法把每个状态或 state-action pair 的 value 单独存在表里。它清晰、稳定，但无法扩展到大规模状态空间。

Function approximation 用参数化函数表示 value 或 policy，例如线性模型或神经网络。它可以泛化到没见过的状态，但也引入优化不稳定性。

Value-based、Policy-based 和 Actor-Critic

Value-based 方法先学习 value，再由 value 导出策略。Value iteration、Q-learning、DQN 都属于 value-based。

Policy-based 方法直接优化参数化策略。Policy gradient、REINFORCE 属于 policy-based。

Actor-Critic 是二者结合：actor 学策略，critic 学 value，用 value 信号帮助 policy update。

Episodic Task 和 Continuing Task

Episodic task 有明确终止状态，一条 episode 会结束。例如很多游戏关卡和一次完整对话任务。

Continuing task 没有自然终止状态，智能体会持续和环境交互。TD 方法适合 continuing task，因为它不需要等完整 episode 结束。

常见算法的粗略分类

算法	是否需要模型	On-policy / Off-policy	Online / Offline	是否 bootstrapping
Value iteration	Model-based	不强调	Offline planning	是
Policy iteration	Model-based	不强调	Offline planning	是
Monte Carlo control	Model-free	通常 on-policy	通常 offline	否
TD state value learning	Model-free	On-policy evaluation	Online	是
Sarsa	Model-free	On-policy	Online	是
Q-learning	Model-free	Off-policy	Online	是
DQN	Model-free	Off-policy	Online / replay buffer	是
REINFORCE	Model-free	On-policy	通常按 episode 更新	否
Actor-Critic / A2C	Model-free	通常 on-policy	Online	是
Off-policy Actor-Critic	Model-free	Off-policy	Online / replay buffer	是

Keyboard shortcuts

MiniMind 学习笔记