当前位置：首页 > news >正文

强化学习笔记

news 来源：原创 2025/9/19 12:41:47

强化学习的总体目标：寻找最优策略。

关键名词

智能体（Agent）
状态（State）：智能体相对于环境的状态 $s \in S$
状态空间（State space）：把所有状态放在一起，所有状态的集合（set） $S=\{s_1,s_2,…,s_n\}$
动作（Action）：对于每个状态，所可能采取的行动 $a \in A (s)$
动作空间（Action space）：某状态下所可能采取的所有动作的集合（动作依赖于状态） $A(s)=\{a_1,a_2,…,a_m\}$
状态转移（State transition）：通过采取一个动作，智能体从一个状态进入另一个
状态转移概率（State transition probability）：用条件概率描述状态转移 $P (s' ∣ s, a)$
策略（Policy）：策略告诉智能体在某一状态下应采取什么行动

在数学上，策略被定义为在给定状态 $s$ 时选择行动 $a$ 的概率，即 $π (a ∣ s)$ 。

策略 $π$ 需要满足以下条件：对于所有状态 $s \in S$ ，所有可能行动 $a \in A (s)$ 的概率之和等于 1：

$\sum_{a∈A(s)}π(a∣s)=1$

回报（Reward）：回报 $R (s, a)$ 是智能体在状态 $s$ 下执行动作 $a$ 后获得的标量值。它可以是正数（奖励）或负数（惩罚）。
轨迹（Trajectory）和收益（Return）：轨迹是一系列状态、动作和回报的序列，形式为 $s_0,a_0,r_0,s_1,a_1,r_1,…,s_T)$ 。轨迹的收益 $G$ 是沿轨迹收集的所有回报的总和：
$G=\sum_{t=0}^{T−1}r_t$
折扣收益（Discounted Return）：在无限或长期的环境中，折扣收益用于优先考虑即时回报，而不是未来的回报。它通过折扣因子 $γ$ （其中 $0 \leq γ \leq 1$ ）来计算：
$G=\sum_{∑t=0}^{∞}γ_tr_t$
当 $\gamma=1$ 时，它就是标准的收益。折扣因子可使得无限序列的总和是有限的，并且模型能够捕捉到即时回报比未来回报更有价值这一概念。 $\gamma$ 越接近1越远视（注重长期回报）， $\gamma$ 越接近0越近视（注重及时回报）。
Episode：一个有限的轨迹，通常在特定的终止状态处结束。
马尔科夫决策过程（Markov decision process, MDP)：MDP 的目标是找到一个策略 $π$ ，使得从起始状态开始的预期折扣收益最大化。具有无记忆性（和之前的状态无关）。

$π^∗=\mathrm{argmax_{\pi}}E_π[G∣s0]$

其中 $E_π[G∣s0]$ 表示在策略 $π$ 下，从初始状态 $s_0$ 开始的预期折扣收益。

MDP 由以下组件定义：

状态空间 $S$
动作空间 $A (s)$
状态转移概率 $P (s' ∣ s, a)$
回报函数 $R (s, a)$
折扣因子 $γ$

贝尔曼公式

状态值函数（State Value Function）

定义：
在策略 $\pi$ 下从状态 $s$ 出发的预期折扣收益，其定义为：
$V^{\pi}(s) = \mathbb{E}_{\pi} \left[ G \mid s_0 = s \right] = \mathbb{E}_{\pi} \left[ \sum_{t=0}^{\infty} \gamma^t r_t \bigg| s_0 = s \right]$
其中：

$\mathbb{E}_{\pi}[\cdot]$ 表示在策略$\pi $下的期望，覆盖动作选择和状态转移的随机性。
$\sum_{t=0}^{\infty} \gamma^t r_t$ 是折扣收益， $\gamma \in [0,1)$ 是折扣因子，确保无穷级数收敛。
$r_t = R(s_t, a_t)$ 是时刻 $t$ 的即时回报， $a_t \sim \pi(\cdot \mid s_t)$ ，状态转移由 $s_{t+1} \sim P(\cdot \mid s_t, a_t)$ 决定。

贝尔曼方程（Bellman Equation）

状态值函数满足递归关系：
$V^{\pi}(s) = \sum_{a \in A} \pi(a \mid s) \left[ R(s,a) + \gamma \sum_{s' \in S} P(s' \mid s,a) V^{\pi}(s') \right], \quad \forall s \in S$
含义：
当前状态的值等于即时回报的期望，加上未来状态的期望折扣值。

矩阵形式：

$\mathbf{V}^{\pi} = \mathbf{R}^{\pi} + \gamma \mathbf{P}^{\pi} \mathbf{V}^{\pi}$
其闭式解为：
$\mathbf{V}^{\pi} = (I - \gamma \mathbf{P}^{\pi})^{-1} \mathbf{R}^{\pi}$
当 $\gamma < 1$ 时，矩阵 $\gamma \mathbf{P}^{\pi})$ 可逆。

动作值函数（Action Value Function）

定义：
动作值函数 $Q^{\pi}(s,a)$ 表示从状态 $s$ 执行动作 $a$ 后，遵循策略$ \pi $的预期折扣收益：
$Q^{\pi}(s,a) = \mathbb{E}_{\pi} \left[ \sum_{t=0}^{\infty} \gamma^t r_t \bigg| s_0 = s, a_0 = a \right]$

与状态值函数的关系：
状态值函数可表示为动作值函数的期望：
$V^{\pi}(s) = \sum_{a \in A} \pi(a \mid s) Q^{\pi}(s,a)$

动作值的贝尔曼方程：
动作值函数同样满足递归关系：
$Q^{\pi}(s,a) = R(s,a) + \gamma \sum_{s' \in S} P(s' \mid s,a) V^{\pi}(s')$

贝尔曼最优公式

最优策略与最优值函数

最优策略定义：
策略 $\pi^*$ 是最优的，当且仅当对任意状态 $s$ ，其满足：
$\pi^*(a \mid s) = \begin{cases} 1, & a = \arg\max_{a'} Q^{\pi^*}(s,a') \\ 0, & \text{其他} \end{cases}$

最优状态值函数：
最优值函数 $V^*(s)$ 是所有策略中最大的状态值：
$V^*(s) = \max_{\pi} V^{\pi}(s)$

贝尔曼最优方程：
最优值函数满足：
$V^*(s) = \max_{a \in A} \left[ R(s,a) + \gamma \sum_{s' \in S} P(s' \mid s,a) V^*(s') \right], \quad \forall s \in S$
对应动作值函数的最优方程为：
$Q^*(s,a) = R(s,a) + \gamma \sum_{s' \in S} P(s' \mid s,a) \max_{a'} Q^*(s',a')$

存在性与唯一性

存在性：在有限马尔可夫决策过程MDP中，若 $\gamma < 1$ ，则存在唯一的最优值函数 $V^*$ 和 $Q^*$ ，以及至少一个确定性最优策略 $\pi^*$ 。
唯一性：存在唯一最优解（最优策略不一定唯一）。放缩映射证明。
收敛性：通过值迭代或策略迭代算法，可逐步逼近 $V^*$ 和 $\pi^*$ （指数级收敛）。

值迭代（Value Iteration）

基本思想

通过直接迭代贝尔曼最优方程求解最优值函数，最终从最优值函数中提取最优策略。通过同步备份（synchronous backup）更新所有状态的值。

算法步骤
$V_{k}(s)\to Q_{k}(s,a) \to \pi_{k+1}(a|s) \to V_{k+1}(s) \to \max_aQ_{k}(s,a)$

初始化：
对所有状态 $\in S$ ，设置初始值 $V_0(s) = 0$ （或其他任意值）
迭代更新：
重复以下更新直至收敛：
$V_{k+1}(s) = \max_{a \in A} \left[ R(s,a) + \gamma \sum_{s' \in S} P(s' \mid s,a) V_k(s') \right], \quad \forall s \in S$
更新方式为同步备份（先计算所有新值，再整体替换旧值）
终止条件：
当 $\max_{s \in S} |V_{k+1}(s) - V_k(s)| < \varepsilon$ （预设阈值）时停止
策略提取：
最终通过最优值函数 $V^*$ 得到确定性策略：
$\pi^*(s) = \arg\max_{a \in A} \left[ R(s,a) + \gamma \sum_{s' \in S} P(s' \mid s,a) V^*(s') \right]$

特性分析

收敛性：
- 当 $\gamma < 1$ 时，值迭代以指数速度收敛到唯一最优解
- 迭代次数与状态数无关，仅依赖 $\gamma$ 和 $\varepsilon$
时间复杂度：
每轮迭代复杂度为 $O(|S|^2|A|)$ ，适用于状态空间较小的问题
与贝尔曼方程关系：
值迭代本质是不断应用贝尔曼最优算子的不动点迭代

策略迭代（Policy Iteration）

基本思想

通过**交替进行策略评估（Policy Evaluation）和策略改进（Policy Improvement）**来优化策略，直到收敛到最优策略。

算法步骤

初始化：
随机选择一个初始策略 $\pi_0$
策略迭代循环：
Repeat:
- (1) 策略评估：
  计算当前策略 $\pi_k$ 的值函数 $V^{\pi_k}$
  通过求解贝尔曼方程：
  $V^{\pi_k}(s) = \sum_{a} \pi_k(a|s) \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V^{\pi_k}(s') \right]$
  可通过迭代法（重复应用上式直至收敛）或直接求解线性方程组获得精确解
- (2) 策略改进：
  对每个状态 $s$ ，选择使动作值最大的动作：
  $\pi_{k+1}(s) = \arg\max_{a} \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V^{\pi_k}(s') \right]$
Until $\pi_{k+1} = \pi_k$ （策略稳定，实际上是无限逼近）

特性分析

收敛速度：
- 通常比值迭代更快（尤其当策略空间较小时）
- 策略改进阶段保证每次迭代策略至少不劣化
计算复杂度：
- 策略评估阶段需要 $O(|S|^3)$ （直接求解）或 $O(m|S|^2)$ （迭代m次）
- 适用于中等规模状态空间问题

截断策略迭代（Truncated Policy Iteration）

基本思想

在标准策略迭代的基础上，放宽策略评估的精度要求。通过限制策略评估阶段的迭代次数（如固定次数 $k$ 次），提前截断对当前策略的值函数计算，以降低每次迭代的计算量，同时仍能保证策略逐步优化。

算法步骤

初始化：
- 随机初始化策略 $\pi_0$
- 设置策略评估阶段的迭代次数上限 $k$ （例如 $k = 3$ ）
策略迭代循环：
Repeat:
- (1) 截断策略评估：
  对当前策略 $\pi_i$ ，执行以下步骤（从初始值函数 $V_0$ 开始）:
  - For $t = 0$ to $k - 1$ do:
    更新值函数：
    $V_{t+1}(s) = \sum_{a} \pi_i(a|s) \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V_t(s') \right]$
  - 最终得到近似值函数 $V_k \approx V^{\pi_i}$
- (2) 策略改进：
  基于近似值函数 $V_k$ ，贪婪更新策略：
  $\pi_{i+1}(s) = \arg\max_{a} \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V_k(s') \right]$
Until $\pi_{i+1} = \pi_i$ （策略稳定）

特性分析

收敛性：
- 即使策略评估未完全收敛，只要策略改进阶段能提升策略，算法仍能收敛到最优策略
- 收敛速度可能慢于标准策略迭代，但快于值迭代
精度-效率权衡：
- 增大 $k$ ：策略评估更精确，策略改进更有效，但单次迭代时间增加
- 减小 $k$ ：单次迭代更快，但可能需要更多轮次策略迭代

关键名词

贝尔曼公式

状态值函数（State Value Function）

贝尔曼方程（Bellman Equation）

动作值函数（Action Value Function）

贝尔曼最优公式

最优策略与最优值函数

值迭代（Value Iteration）

策略迭代（Policy Iteration）

截断策略迭代（Truncated Policy Iteration）

相关文章：