RL——强化学习相关概念汇总

Episodic Task 和 Continuing Task

Episodic Task ：（分幕任务）环境有明确的终止状态（如游戏通关、任务完成），每个独立的交互片段称为一个 episode
- 例如：象棋游戏等
Continuing Task ：（持续任务）环境无终止状态，智能体需无限持续交互。无步长限制（即没有明确终止状态或时间限制）的环境称为 Continuing Task（持续任务）
- 例如：长期运行的自动化控制系统等
- 在持续任务中，通常需要引入 折扣因子（γ） 来确保回报的无穷和有界
- 术语 “Non-episodic“ 或 “Infinite-horizon“ 也偶尔用于描述这类场景，但 Continuing Task 是强化学习领域的标准术语（参考 Sutton & Barto 的《Reinforcement Learning: An Introduction》）

Episode、Rollout 和 Trajectory

Episode（回合） ：一个完整的交互过程，从初始状态开始，到终止状态结束（适用于Episodic Task）
- 明确的时间边界（如游戏的一局、机器人完成一次任务），Episodic Task任务才有明确的终止状态
- 通常用于有终止条件的任务（例如：Atari游戏通关、机器人到达目标）
Rollout（展开、推演） ：包含从当前状态（或某个特定状态）到终止状态的完整过程，和Episode的区别是可以不从初始状态开始
Trajectory（轨迹） ：智能体在环境中产生的一系列状态、动作、奖励的序列，形式化为：
$$
\tau = (s_0, a_0, r_1, s_1, a_1, r_2, \dots)
$$
- 更通用的术语，可指完整或部分序列 ，更侧重强调行为路径和决策序列
- 既可用于Episodic Task（一个 trajectory 对应一个 episode），也可用于持续任务（Continuing Task ，无终止状态）
- 在强化学习理论和推导中常用（如策略梯度方法中的轨迹优化）

State 和 Observation

State（状态） ：对环境的完整描述称为状态
Observation（观测） ：对环境（或状态）的部分描述称为观测
对比：状态包含了环境的全部信息，能够完全确定环境的当前情况以及未来的演化趋势（在给定策略和环境动态的情况下）；观测则往往是不完整的、有噪声的，可能丢失了一些对决策重要的信息
说明：大部分论文中不会严格说明是否获取到了环境的完整描述，会使用 State 来表述观测 Observation

Fully Observable 和 Partially Observable

Fully Observable ：如果智能体能看到完整的环境描述，则称环境为完全可观测的
- 在完全可观测的环境中，智能体能够直接获取到环境的完整状态信息，即智能体观测到的内容与环境的真实状态完全一致，不存在任何隐藏信息或不确定性
Partially Observable ：如果智能体能看到部分的环境描述，则称环境为不完全可观测的
- 在部分可观测的环境中，智能体只能获得环境状态的部分信息，无法直接观测到环境的真实状态。这种情况下，智能体需要根据有限的观测信息来推断环境的状态，进而做出决策

Reward 和 Return

Reward（奖励） ：关注的是当前时刻的单一行动所获得的反馈，是一个即时的、局部的概念
Return（回报） ：从当前状态开始的整个未来序列的累计奖励情况，是一个长期的、全局的概念

State Transition 和 Dynamics

State Transition（状态转移） ：主要关注智能体的状态如何从一个时刻转变到下一个时刻，是 Dynamics（动力学）的一个部分，一般用状态转移概率矩阵或状态转移函数来表示
- 离散空间状态转移通常可表示为 $p$
Dynamics（动力学） ：通常指环境的动态变化规律，它描述了环境如何随着时间步的推进以及智能体的行动而演变。动力学不仅包括状态转移（State Transition）关系，还涵盖了环境中各种因素的变化规律，如奖励的生成机制、环境中其他实体的行为模式等
- Dynamics（动力学）通常用一组复杂的方程或规则来描述，可能涉及多个变量和参数，并且可能需要考虑环境中的各种随机因素和外部干扰

MP、MRP、MDP、POMDP、Contextual MDP

马尔可夫性（Markov property） ：马尔可夫性是指在一个随机过程中，系统在未来时刻的状态只取决于当前时刻的状态，而与过去的历史状态无关
MP（Markov Process） ：即马尔可夫过程 ，也称为马尔可夫链。形式上，一个马尔可夫过程可以用一个二元组 $(S, P)$ 表示
- 其中 $S$ 是状态空间， $P$ 是状态转移概率矩阵， $P_{ss’}=P(s_{t + 1}=s’|s_t = s)$ 表示在时刻 $t$ 处于状态 $s$ ，在下一时刻 $t + 1$ 转移到状态 $s’$ 的概率，它是一个无记忆的随机过程，具有马尔可夫性质，即未来的状态只取决于当前状态，与过去的历史无关
MRP（Markov Reward Process） ：马尔可夫奖励过程 ，是在马尔可夫过程的基础上增加了奖励信号。它是一个四元组 $(S, P, R, \gamma)$
- 其中 $S$ 是状态空间， $P$ 是状态转移概率矩阵， $R$ 是奖励函数， $R(s)=E[r_{t + 1}|s_t = s]$ 表示在状态 $s$ 下获得的即时奖励， $\gamma$ 是折扣因子，用于衡量未来奖励的重要性，取值范围通常在 $[0, 1]$ 之间
MDP（Markov Decision Process） ：马尔可夫决策过程 ，它在马尔可夫奖励过程的基础上增加了决策动作 ，是一个五元组 $(S, A, P, R, \gamma)$
- 其中 $S$ 是状态空间， $A$ 是动作空间， $P$ 是状态转移概率矩阵， $P_{ss’}^a = P(s_{t + 1}=s’|s_t = s, a_t = a)$ 表示在状态 $s$ 下执行动作 $a$ 后转移到状态 $s’$ 的概率， $R$ 是奖励函数， $R(s, a)=E[r_{t + 1}|s_t = s, a_t = a]$ 表示在状态 $s$ 下执行动作 $a$ 获得的即时奖励， $\gamma$ 是折扣因子。智能体通过选择不同的动作来最大化长期累积奖励
POMDP（Partially Observable Markov Decision Process） ：部分可观测马尔可夫决策过程 ，在POMDP中，智能体不能直接观测到环境的真实状态，只能通过观测函数获得部分观测信息。它是一个七元组 $(S, A, O, P, R, \gamma, Z)$
- 其中 $S$ 、 $A$ 、 $P$ 、 $R$ 、 $\gamma$ 与MDP中的含义相同， $O$ 是观测空间， $Z$ 是观测函数， $Z(o|s, a)=P(o_{t + 1}=o|s_{t + 1}=s, a_t = a)$ 表示在状态 $s$ 下执行动作 $a$ 后，观测到 $o$ 的概率。POMDP比MDP更具挑战性，因为智能体需要根据不完整的观测信息来做出决策
Contextual MDP（Contextual Markov Decision Process） ：上下文马尔可夫决策过程 ，Contextual MDP可以表示为六元组 $(S, A, C, P, R, \gamma)$
- 其中 $C$ 是上下文空间，状态转移概率 $P$ 和奖励函数 $R$ 都与上下文 $c$ 有关，即 $P_{ss’}^a(c)=P(s_{t + 1}=s’|s_t = s, a_t = a, c_t = c)$ ， $R(s, a, c)=E[r_{t + 1}|s_t = s, a_t = a, c_t = c]$。它在MDP的基础上增加了上下文信息，即状态不仅取决于当前的环境状态，还与一些外部的上下文因素有关。例如，在推荐系统中，用户的偏好和行为可能受到当前的时间、地点、用户历史记录等上下文因素的影响。智能体需要根据当前的上下文信息来选择合适的动作，以最大化长期累积奖励

MC、TD、DP

蒙特卡罗方法（Monte-Carlo，MC）：通过完整轨迹的采样回报估计值函数，依赖实际经验，无需环境模型
动态规划（Dynamic Programming，DP）：基于模型的全宽度（Full-width）回溯更新，利用贝尔曼方程迭代求解值函数，需已知环境动力学
时序差分（Temporal-Difference，TD）：结合当前奖励和后续状态的价值估计来更新当前状态
三者比较如下：

Bellman Operator

贝尔曼算子（Bellman Operator），又称为贝尔曼Backup算子（Bellman Backup Operator）
一句话理解：贝尔曼算子是一种函数到函数的映射，Bellman的核心原理是利用当前状态的奖励和后续状态的价值来更新当前状态的价值估计
其本质可以表达为“当前状态的价值 = 即时奖励 + 未来价值的折扣期望”
贝尔曼算子作用到Q函数上：
$$ \mathcal{T^\color{red}{\pi}}Q^{k+1}(s,a) = \mathbb{E}_{s’\sim P(\cdot|s,a)}[r(s,a) + \gamma\mathbb{E}_{a’\sim \color{red}{\pi}(\cdot|s’)}[Q^k(s’,a’)]] $$
- 以上迭代公式走下去，Q值会收敛到：$Q^\pi(s,a)$
贝尔曼算子作用到V函数上：
$$ \mathcal{T^\color{red}{\pi}}V^{k+1}(s) = \mathbb{E}_{a \sim \color{red}{\pi}(\cdot|s)}[r(s,a) + \gamma\mathbb{E}_{s’\sim P(\cdot|s,a)}[V^k(s’)]] $$
- 以上迭代公式走下去，Q值会收敛到：$V^\pi(s)$

SMDP

半马尔可夫决策过程（Semi-Markov Decision Process, SMDP）是马尔可夫决策过程（MDP）的扩展，专门用于建模动作持续时间可变的决策问题
在标准 MDP 中，每个动作在一个时间步内完成，而 SMDP 允许动作持续多个时间步，这在现实世界应用中更为常见，引入 SMDP 的核心原因是：
- 时间抽象：许多真实世界的决策涉及持续时间不同的动作
- 层次决策：高层决策可能对应一系列底层动作的执行
- 计算效率：在更高时间尺度上进行规划可减少决策频率
一个 SMDP 可以表示为五元组：$ (S, A, P, R, F) $
- $ S $：状态空间（有限或可数）
- $ A $：动作空间（有限或可数）
- $ P $：状态转移函数，包含时间维度
- $ R $：奖励函数，考虑累积折扣奖励
- $ F $：动作持续时间分布
在 SMDP 中，转移概率包含时间维度 ：
$$
P(s’, \tau | s, a) = \mathbb{P}(S_{t+\tau} = s’, \tau | S_t = s, A_t = a)
$$
- 其中 $ \tau \in \mathbb{Z}^+ $ 是动作执行的时间步数
- 作为对比：在传统的 MDP 中，转移概率为：
  $$
  P(s’ | s, a) = \mathbb{P}(S_{t+1} = s’ | S_t = s, A_t = a)
  $$
SMDP 的状态-动作转移概率：
- 当在状态 $ s $ 执行动作 $ a $ 时，系统以概率 $ P(s’, \tau | s, a) $ 在 $ \tau $ 步后转移到状态 $ s’ $
SMDP 的累积折扣奖励：不是每个时间步单独获得，而是在动作执行期间累积：
$$
r(s, a) = \mathbb{E} \left[ \sum_{k=0}^{\tau-1} \gamma^k R_{t+k} \mid S_t = s, A_t = a \right]
$$
- $ \tau $ 是动作 $ a $ 的持续时间
- $ R_{t+k} $ 是在时间步 $ t+k $ 获得的即时奖励
- $ \gamma \in [0, 1] $ 是折扣因子
SMDP 下的贝尔曼最优方程
- 状态值函数：
  $$
  V^*(s) = \max_{a \in A} \left[ r(s, a) + \sum_{s’, \tau} \gamma^\tau P(s’, \tau | s, a) V^*(s’) \right]
  $$
- 动作值函数：
  $$
  Q^*(s, a) = r(s, a) + \sum_{s’, \tau} \gamma^\tau P(s’, \tau | s, a) \max_{a’ \in A} Q^*(s’, a’)
  $$
- 注意：折扣因子 $ \gamma $ 的指数是 $ \tau $（动作持续时间），这与 MDP 中每个时间步都打折不同
SMDP的求解方法（Q-learning 的 SMDP 扩展），即SMDP Q-learning 更新规则：
- 当在状态 $ s $ 执行动作 $ a $，经过 $ \tau $ 步后到达状态 $ s’ $ 并获得累积奖励 $ r $ 时：
  $$
  Q(s, a) \leftarrow Q(s, a) + \alpha \left[ r + \gamma^\tau \max_{a’} Q(s’, a’) - Q(s, a) \right]
  $$

Option 相关概念

Option 的基本定义

Option（选项）框架是实现层级强化学习（Hierarchical Reinforcement Learning, HRL） 的核心机制
- Option 由 Sutton, Precup 和 Singh 在 1999 年正式提出，旨在解决传统 RL 在处理长路径、复杂任务时的“维度灾难”
Option 是一种形式化的时间抽象机制，允许智能体在更高的时间尺度上进行规划和决策
- 一个 Option 可以看作是一个可重用的技能或子策略，它能够在一段时间内自主执行，直到满足特定的终止条件
简单来说，Option 的本质就是一种 “宏动作”（Macro-action）
- 比如“回家”这个任务，传统的动作是“左转”、“右转”、“迈步”，而 Option 则是“出办公室”、“下楼”、“开车”等一系列子策略
- 下面的概念理解中，可以将 Option 当做一种 “抽象高阶动作” 来看
Option 允许在更长的时间尺度上进行规划；学习到的技能可以在不同任务中重复使用；可通过高层策略加速探索过程；
Option 通常对应有意义的子任务或技能
Option 常用于层次强化学习中：构建多层次的决策体系

Option 的数学定义

一个 Option $ \omega \in \Omega $ 是一个三元组，由三个部分组成：
$$
\omega = \langle I_\omega, \pi_\omega, \beta_\omega \rangle
$$
- 起始状态集 $ I_\omega \subseteq S $： Option 可以被调用的状态集合
  - 表示在哪些状态下可以启动这个 Option，启动这个 Option 相当于是做了一个 Action
- 内部策略 $ \pi_\omega : S \times A \rightarrow [0,1] $：Option 执行期间遵循的策略
  - 即该 Option 运行时，Agent 采取动作的概率分布
  - 注意：每个 Option $\omega$ 对应的策略 $\pi_\omega$ 不同，也就是说，对于相同的状态 $s_t$，若其 Option $\omega$ 不同，则选择的动作 $a_\omega \sim \pi_\omega(\cdot|s_t)$ 也不同
- 终止函数 $ \beta_\omega : S \rightarrow [0,1] $：表示在给定状态下 Option 终止的概率
  - 即在某个状态下，该 Option 终止的概率
  - 理解：在有些状态下，可以认为是这个 Option 的目标（如下楼）已经达到了，所以可以退出这个 Option 了，有些状态下则还没达到，不能退出

Option 的执行过程

Option 的调用和执行

当智能体在状态 $ s_t $ 且 $ s_t \in I_\omega $ 时，可以选择执行一个 Option $ \omega $
在选择确定的 Option $ \omega $ 后，后续的动作选择如下：
- 1）智能体按照 Option $ \omega $ 对应的策略 $ \pi_\omega $ 选择动作 Action 并与环境多次交互，直到 Option 终止
- 2）在每个时间步 $ t’ $ 时，Option 都以概率 $ \beta_\omega(s_{t’}) $ 终止
  - 注：不同状态的终止概率不同，极端情况下，有的状态表示已经达成 Option 的目标，则结束概率是 1，有的状态表示完全未完成目标，结束概率是 0；
  - 理解：这有点类似于状态转移，但不完全相似

Option 的马尔可夫性

尽管单个 Option 的内部执行（按策略 $ \pi_\omega $ 选择动作 Action 并与环境多次交互）可能依赖于历史，但在半马尔可夫决策过程（Semi-Markov Decision Process, SMDP） 的框架下，Option 的选择可以被视为一个马尔可夫决策过程
注：SMDP 是 MDP 的扩展，专门用于建模动作持续时间可变的决策问题
- 在标准 MDP 中，每个动作在一个时间步内完成
- SMDP 允许动作持续多个时间步，这在现实世界应用中更为常见

Option 框架下的值函数

Option 的价值函数

对于一个 Option $ \omega $，其状态 $ s $ 的价值函数定义为从状态 $ s $ 开始执行该 Option 的期望回报：
$$
V^\omega(s) = \mathbb{E} \left[ r_{t+1} + \gamma r_{t+2} + \cdots + \gamma^{k-1} r_{t+k} + \gamma^k V(s_{t+k}) \mid \mathcal{E}(\omega, s, t) \right]
$$
- 其中 $ \mathcal{E}(\omega, s, t) $ 表示在时间 $ t $ 从状态 $ s $ 开始执行 Option $ \omega $，$ k $ 是 Option 执行的步数

SMDP 贝尔曼方程

在 Option 框架下，SMDP 的贝尔曼方程为（理解：本质就是把 Option 的选择看做是一种动作的选择，从而构成贝尔曼方程）：
$$
V(s) = \max_{\omega \in \Omega_s} \left[ R(s,\omega) + \sum_{s’} \gamma^\tau P(s’ \mid s,\omega) V(s’) \right]
$$
- $ \Omega_s $ 是在状态 $ s $ 下可用的 Option 集合
- $ R(s,\omega) $ 是从状态 $ s $ 执行 Option $ \omega $ 的期望累积折扣回报
- $ P(s’ \mid s,\omega) $ 是从状态 $ s $ 执行 Option $ \omega $ 后到达状态 $ s’ $ 的概率
- $ \tau $ 是 Option 执行的期望步数

分层学习：Intra-Option 学习（Option 内部学习）

Intra-Option 学习关注于改进单个 Option 的内部策略 $ \pi_\omega $，而不改变 Option 的选择策略
这可以通过各种策略梯度方法实现：
$$
\nabla_\theta J(\pi_\omega) = \mathbb{E}_{s \sim \rho^\omega, a \sim \pi_\omega} \left[ \nabla_\theta \log \pi_\omega(a|s) Q_U(s,\omega) \right]
$$
- 其中 $ Q_U(s,\omega) $ 是执行 Option $ \omega $ 的动作值函数
- 整个优化过程会优化策略 $\pi_\omega$ 本身，但不会优化选择 $\omega$ 的概率分布（或高阶策略）

分层学习：Inter-Option 学习（Option 间学习）

Inter-Option 学习关注于学习如何在不同 Option 之间进行选择，即学习一个上层策略 $ \mu : S \times \Omega \rightarrow [0,1] $：
$$
Q_\Omega(s,\omega) = R(s,\omega) + \sum_{s’} P(s’ \mid s,\omega) \max_{\omega’ \in \Omega_{s’} } Q_\Omega(s’,\omega’)
$$

Option 发现方法

基于子目标的方法

通过识别状态空间中的关键状态（子目标）来构建 Option：
$$
g^* = \arg \max_g \Phi(g)
$$
- 其中 $ \Phi(g) $ 是子目标 $ g $ 的某种效用函数，如访问频率或状态覆盖度

基于技能的方法

通过最大化多样性来发现有用的技能：
$$
\max_{\pi} \mathbb{E}_{s \sim p(s)} \left[ H(\pi(\cdot|s)) \right] \\
\text{s.t. } \mathbb{E}_{z \sim p(z), s \sim \pi_z} \left[ | z - f(s) |^2 \right] \leq \epsilon
$$
- 其中 $ z $ 是技能隐变量，$ f(\cdot) $ 是状态编码器

SMDP 与 Option 框架的关系

Option 作为 SMDP 动作：在 Option 框架中，每个 Option $ \omega $ 可以看作 SMDP 中的一个”动作”：
- 持续时间：Option 执行的时间步数 $ \tau $
- 累积奖励：Option 执行期间获得的折扣奖励之和
- 转移概率：从起始状态到终止状态的概率
Option 的 SMDP 参数概念对齐：对于 Option $ \omega = \langle I_\omega, \pi_\omega, \beta_\omega \rangle $，对应的 SMDP 参数为：
- 累积奖励函数：
  $$
  r(s, \omega) = \mathbb{E} \left[ \sum_{k=0}^{\tau-1} \gamma^k R_{t+k} \mid S_t = s, \text{执行} \omega \right]
  $$
- 状态转移概率：
  $$
  P(s’, \tau | s, \omega) = \mathbb{P}(S_{t+\tau} = s’, \tau \mid S_t = s, \text{执行} \omega)
  $$
SMDP 中的 Option 策略：在 SMDP 层面，策略 $ \mu : S \rightarrow \Delta(\Omega) $ 选择 Option，满足 SMDP 贝尔曼方程：
$$
V_\mu(s) = \sum_{\omega \in \Omega} \mu(\omega | s) \left[ r(s, \omega) + \sum_{s’, \tau} \gamma^\tau P(s’, \tau | s, \omega) V_\mu(s’) \right]
$$

CPI：保守策略迭代 (Conservative Policy Iteration)

CPI 是由 Kakade 和 Langford 在 2002 年提出的一种策略迭代改进方法，是 RL 领域具有里程碑意义的算法
CPI 的核心思想是“保守”地更新策略，即不直接将策略完全替换为当前的贪婪策略（Greedy Policy），而是采用一种混合策略（Mixture Strategy）的方式进行更新
TLDR：CPI 告诉我们在理论上“怎么走才安全”（步子要小，要混合）
CPI 的核心思路 & 贡献：
- 混合策略更新：
  - 传统的策略迭代通常直接寻找使当前优势函数最大化的动作作为新策略
  - CPI 提出，新策略 $\pi_{new}$ 应当是旧策略 $\pi_{old}$ 和贪婪策略 $\pi’$ 的加权混合：
    $$ \pi_{new} = (1-\alpha)\pi_{old} + \alpha \pi’ $$
    - 其中 $\alpha$ 是一个很小的正数（步长）
- 单调性证明：CPI 的最大贡献在于它从理论上证明了，只要 $\alpha$ 足够小，这种混合更新策略可以保证值函数（Value Function）的单调不减（Monotonic Improvement）
- 解决的问题：在近似强化学习中，由于函数逼近误差的存在，直接的贪婪更新往往会导致策略性能突然大幅下降（Policy Degradation）
  - CPI 通过限制策略变化的幅度，给出了策略提升的下界（Lower Bound），从而保证了学习过程的稳定性
CPI 的地位：CPI 是现代“信赖域”类算法（如 TRPO）的理论鼻祖，其关于“策略提升下界”的推导直接启发了后续算法中对 KL 散度约束的使用

NPG：自然策略梯度 (Natural Policy Gradient)

NPG 是由 Kakade 提出的一种优化方法，是 RL 领域具有里程碑意义的算法，它试图解决标准梯度下降在强化学习参数空间中效率低下的问题
NPG 是 TRPO 算法的前身，其核心在于引入了黎曼几何的概念来优化策略参数
TLDR：NPG 告诉我们在数学上“朝哪个方向走最快”（考虑分布的几何形状）
NPG 的核心思路 & 贡献
- 黎曼几何与费雪信息矩阵（Fisher Information Matrix）：
  - 标准的策略梯度（Policy Gradient, PG）假设参数空间是欧几里得空间，使用标准的梯度下降方向
    - 然而，策略通常以概率分布的形式存在，参数的一点点变化可能导致概率分布的剧烈变化
  - NPG 认为，更新方向不应基于参数的欧氏距离，而应基于分布之间的距离（通常用 KL 散度衡量）
- 自然梯度更新：
  - NPG 在更新参数时，使用费雪信息矩阵 $F$ 的逆矩阵对标准梯度 $\nabla J(\theta)$ 进行预处理（Preconditioning）：
    $$ \theta_{new} = \theta_{old} + \eta F^{-1} \nabla J(\theta) $$
    - 这种更新方向被称为“自然梯度”，它代表了在分布流形上最陡峭的下降方向
- 协变性（Covariant）： NPG 的更新具有参数化无关性，即无论你如何参数化你的策略网络，只要表示的分布相同，更新的轨迹就是一致的
特别说明：
- NPG 极大地提高了策略梯度的收敛效率，特别是在高维参数空间中
- NPG 指出了标准 PG 算法在“步长”和“方向”上的缺陷，直接催生了后来的 TRPO（TRPO 可以看作是 NPG 加上了强制的 KL 散度约束步长）
CPI 和 NPG 的比较：
- CPI 和 NPG 这两个方法通常被放在一起讨论，因为它们共同构成了现代深度强化学习中策略优化（Policy Optimization） 流派的基石：
- 简单来说，CPI 告诉我们在理论上“怎么走才安全”（步子要小，要混合），而 NPG 告诉我们在数学上“朝哪个方向走最快”（考虑分布的几何形状） 这两者的结合最终导致了 TRPO 等算法的诞生，使得强化学习能够更稳定地应用于复杂的连续控制任务中