《强化学习的数学原理》学习笔记(4-6)

发表于 分类于 ， 本文字数： 3k 阅读时长 ≈ 4 分钟

内容包括值迭代与策略迭代、蒙特卡罗方法、随机近似算法，对应《强化学习的数学原理》4-6章。

四、值迭代与策略迭代

1. 值迭代 (Value Iteration)

值迭代通过贝尔曼最优算子不断更新状态值，其核心在于直接寻找最优值函数：

$V_{k+1} = \max_{a \in \mathcal{A}} (r_a + \gamma P_a V_k), \quad k=0, 1, 2, \dots$

注：在收敛前，$V_k$ 是对最优状态值的估计，而非某一固定策略的状态值。

  • （1）策略更新：$\pi_{k+1} = \arg\max_a (r_a + \gamma P_a V_k)$，即基于当前估计的值函数提取贪婪策略。

  • （2）值更新：$V_{k+1} = r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} V_k$，将提取的策略代入更新值函数。

  • （3）展开形式：

    • 策略更新：$\pi_{k+1}(s) = \arg\max_\pi \sum_a \pi(a|s) q_k(s, a)$

      最优解为确定性策略：

      $\pi_{k+1}(a|s) = \begin{cases} 1, & a = a_k^{max}(s) \\0, & a \neq a_k^{max}(s) \end{cases}$

      其中 $a_k^{max}(s) = \arg\max_a q_k(s, a)$。

    • 值更新：$V_{k+1}(s) = \max_a q_k(s, a)$。

2. 策略迭代 (Policy Iteration)

  • （1）策略评价 (Policy Evaluation)：

    计算当前策略 $\pi_k$ 的精确状态值：$V_{\pi_k} = r_{\pi_k} + \gamma P_{\pi_k} V_{\pi_k}$。

  • （2）策略改进 (Policy Improvement)：

    $\pi_{k+1} = \arg\max_a (r_a + \gamma P_a V_{\pi_k})$。

关键点解析：

  • 如何计算 $V_{\pi_k}$？ 通常利用数值迭代：$V_k^{(j+1)} = r_{\pi_k} + \gamma P_{\pi_k} V_k^{(j)}$。
  • 单调性保障：若 $\pi_{k+1}$ 是基于 $V_{\pi_k}$ 的贪婪改进，则 $V_{\pi_{k+1}} \geq V_{\pi_k}$（策略改进定理）。

3. 对比与截断策略迭代 (Truncated Policy Iteration)

  • 值迭代：本质上是每一步只进行一次值更新，中间产生的 $V_k$ 并不对应某个真实的策略值。
  • 策略迭代：每次改进前都要将策略评价做到收敛，计算量较大。
  • 截断策略迭代：在策略评价阶段不迭代至收敛，而是仅进行 $j$ 步更新，是两者的折中。

算法流程演变：

  • 值迭代：$V_k \xrightarrow{\text{一步更新}} V_{k+1}$
  • 截断策略迭代：$V_k \xrightarrow{j\text{ 步更新}} \bar{V}_{k+1}$
  • 策略迭代：$V_k \xrightarrow{\infty\text{ 步更新}} V_{\pi_k}$

五、蒙特卡罗方法 (Monte Carlo Methods)

1. MC Basic

将基于模型的策略评价转换为**无模型（Model-free）**方法。利用采样数据的经验平均来估计状态-动作值：

$q_{\pi_k}(s, a) = E[G_t | S_t=s, A_t=a] \approx \frac{1}{n} \sum_{i=1}^n g_{\pi_k}^{(i)}(s, a)$

2. MC Exploring Starts (探索性初始化)

  • 高效利用样本：一个完整回合（Episode）的后缀序列可用于估计路径上所有经历过的状态-动作值。
  • 即时策略更新：无需等待所有样本收集完毕，可针对单个回合的回报立即更新策略。

3. MC $\epsilon$-Greedy

为了解决“探索性初始化”在实际中难以实现的问题，引入 $\epsilon$-贪婪策略：

$\pi(a|s) = \begin{cases} 1 - \epsilon + \frac{\epsilon}{|\mathcal{A}(s)|}, & \text{针对最大价值动作} \\ \frac{\epsilon}{|\mathcal{A}(s)|}, & \text{针对其他 } |\mathcal{A}(s)|-1 \text{ 个动作} \end{cases}$

  • 作用：通过强制概率探索，确保所有状态-动作对都有机会被访问，平衡了探索与利用。

六、随机近似算法 (Stochastic Approximation)

1. 增量式计算期望

均值的增量更新公式：$w_{k+1} = w_k - \frac{1}{k}(w_k - x_k)$。

推广到一般形式：$w_{k+1} = w_k - \alpha_k(w_k - x_k)$，其中 $\alpha_k$ 为学习率。

2. RM 算法 (Robbins-Monro Algorithm)

  • 假设求解： $g(w) = 0$
  • 包含观测噪声： $\tilde{g}(w, \eta) = g(w) + \eta$
  • 迭代算法： $w_{k+1} = w_k - \alpha_k \tilde{g}(w_k, \eta_k), \quad k=1, 2, 3, \dots$
  • 收敛条件：
    • (a) 存在正数 $c_1, c_2 > 0$，使得 $0 < c_1 \leq \nabla_w g(w) \leq c_2$ 对所有 $w$ 成立，$g(w)$ 增长受限且梯度为正（或导数大于 0）。
    • (b) $\sum_{k=1}^\infty \alpha_k = \infty$ 且 $\sum_{k=1}^\infty \alpha_k^2 < \infty$，步长足够大以到达解且步长收敛以抵消噪声。
    • (c) $E[\eta_k | H_k] = 0$ 且 $E[\eta_k^2 | H_k] < \infty$，其中 $H_k = {w_k, w_{k-1}, \dots}$，噪声 $\eta_k$ 是零均值且方差有限。

3. RM 解决期望估值

定义 $g(w) = w - E[X]$。得 $X$ 的随机样本，则：

$\tilde{g}(w, \eta) = w - X = (w - E[X]) + (E[X] - X) = g(w) + \eta$，其中 $\eta = E[X] - X$

用 RM 求解：

$w_{k+1} = w_k - \alpha_k \tilde{g}(w_k, \eta_k) = w_k - \alpha_k(w_k - x_k)$

4. 随机梯度下降 (Stochastic Gradient Descent)

  • 对于优化问题： $\min_w J(w) = E[f(w, X)]$

  • 梯度下降 (GD)：

    $w_{k+1} = w_k - \alpha_k \nabla J(w_k) = w_k - \alpha_k E[\nabla_w f(w_k, X)]$

  • 期望基于数据估计，批梯度下降 (Batch GD)：

    $w_{k+1} = w_k - \frac{\alpha_k}{n} \sum_{i=1}^n \nabla_w f(w_k, x_i)$

  • 样本是逐个得到的，随机梯度下降 (SGD)：

    $w_{k+1} = w_k - \alpha_k \nabla_w f(w_k, x_k)$