一窥强化学习（长文）

中文精读

原文约 7,574 词 · 24 节

1. 引言：为什么要了解强化学习

   • 近年 AlphaGo 击败顶尖人类棋手，扩展算法 AlphaGo Zero 在不使用人类知识做监督学习的情况下以 100-0 战胜 AlphaGo。
   • OpenAI 开发的机器人在 DOTA2 1v1 比赛中击败顶尖职业选手。
   • 这些算法背后的核心是强化学习（reinforcement learning），本文先介绍基本概念，再进入经典解法。

2. 什么是强化学习

   • 设定一个处于未知环境中的智能体（agent），它通过与环境交互获得奖励，应选择动作以最大化累计奖励。
   • 现实场景可以是打游戏拿高分的机器人，也可以是完成物理任务的机器人，且不限于此。
   • 强化学习的目标是从试验和相对简单的反馈中学习好的策略，使智能体能主动适应环境、最大化未来奖励。

3. 关键概念

   • 智能体在环境中行动，环境对动作的反应由模型（model）定义，模型可能已知也可能未知；智能体处于状态 s∈S，选择动作 a∈A 转移到新状态，去向由转移概率 P 决定，动作后环境给出奖励 r∈R。
   • 模型定义奖励函数与转移概率。知道模型即完全信息下的规划，可用动态规划（DP）求解；不知道模型则为不完全信息下的学习，做无模型（model-free）强化学习，或把模型作为算法一部分显式学习——后文多数内容针对模型未知的情形。
   • 策略 π(s) 给出某状态下应采取的最优动作，目标是最大化总奖励；价值函数 V(s) 预测在该状态下按相应策略行动可获得的期望未来奖励，即量化状态好坏。策略与价值函数都是强化学习要学的东西。
   • 交互按时间 t=1,2,…,T 展开为状态、动作、奖励序列，终止于终止状态 S_T，这样一条完整序列称为一个回合（episode，也叫 trial 或 trajectory）。
   • 常见术语：基于模型（model-based）依赖环境模型、模型已知或显式学习；无模型（model-free）学习时不依赖模型；同策略（on-policy）用目标策略的确定性结果或采样来训练；异策略（off-policy）用另一行为策略产生的转移或回合分布来训练。

4. 模型：转移与奖励

   • 模型是环境的描述，借助它可以学习或推断环境如何与智能体交互并给予反馈；模型由两大部分组成：转移概率函数 P 和奖励函数 R。
   • 在状态 s 决定采取动作 a、到达下一状态 s' 并获得奖励 r，这样一个过程称为一个转移步（transition），用元组 (s, a, s', r) 表示。
   • 转移函数记录从 s 执行 a 后转到 s' 同时得到 r 的概率：P(s', r | s, a) = P[S_{t+1}=s', R_{t+1}=r | S_t=s, A_t=a]。
   • 对奖励 r 求和即得状态转移函数 P^a_{ss'} = P(s' | s, a) = P[S_{t+1}=s' | S_t=s, A_t=a] = Σ_{r∈R} P(s', r | s, a)。
   • 奖励函数预测一次动作带来的下一奖励期望：R(s, a) = E[R_{t+1} | S_t=s, A_t=a] = Σ_{r∈R} r Σ_{s'∈S} P(s', r | s, a)。
   text

   $P(s', r \vert s, a) = \mathbb{P} [S_{t+1} = s', R_{t+1} = r \vert S_t = s, A_t = a]$
   
   $P_{ss'}^a = P(s' \vert s, a) = \mathbb{P} [S_{t+1} = s' \vert S_t = s, A_t = a] = \sum_{r \in \mathcal{R}} P(s', r \vert s, a)$
   
   $R(s, a) = \mathbb{E} [R_{t+1} \vert S_t = s, A_t = a] = \sum_{r\in\mathcal{R}} r \sum_{s' \in \mathcal{S}} P(s', r \vert s, a)$

5. 策略

   • 策略是智能体的行为函数 π，指出在状态 s 下该采取哪个动作，是状态 s 到动作 a 的映射。
   • 策略可以是确定性的：π(s) = a，即给定状态就固定输出一个动作。
   • 策略也可以是随机性的：π(a | s) = P_π[A=a | S=s]，即以概率分布形式给出在该状态下选各动作的概率。
   text

   * Deterministic: $\pi(s) = a$.
   * Stochastic: $\pi(a \vert s) = \mathbb{P}_\pi [A=a \vert S=s]$.

6. 模型：转移与奖励；策略；价值函数（续）

   • 状态价值 V_π(s) 是在状态 s 起按策略 π 行动的期望回报；动作价值（Q 值）Q_π(s,a) 是在 s 采取 a 后的期望回报。借助动作概率分布可由 Q 恢复 V：V_π(s)=Σ_a Q_π(s,a)π(a|s)。
   • 动作价值与状态价值之差称为优势函数（advantage）：A_π(s,a)=Q_π(s,a)−V_π(s)。

7. 最优价值与最优策略；马尔可夫决策过程

   • 最优价值函数给出最大回报：V_*(s)=max_π V_π(s)，Q_*(s,a)=max_π Q_π(s,a)；最优策略则是在这些价值函数上取最大，且满足 V_{π_*}=V_*、Q_{π_*}=Q_*。
   • 几乎所有强化学习问题都可形式化为马尔可夫决策过程（MDP），其所有状态具备马尔可夫性：未来只依赖当前状态而非历史，即给定现在时未来与过去条件独立，当前状态已概括决定未来所需的全部统计信息。
   • MDP 由五个要素构成 M=⟨S, A, P, R, γ⟩：状态集、动作集、转移概率函数、奖励函数、未来奖励折扣因子，与前述关键概念一致；在未知环境中，P 与 R 不具备完全知识。

8. 贝尔曼方程

   • 贝尔曼方程把价值函数分解为即时奖励加折扣后的未来价值：V(s)=E[R_{t+1}+γG_{t+1}|S_t=s]=E[R_{t+1}+γV(S_{t+1})|S_t=s]。
   • 对 Q 值同理：Q(s,a)=E[R_{t+1}+γV(S_{t+1})|S_t=s,A_t=a]=E[R_{t+1}+γE_{a∼π}Q(S_{t+1},a)|…]。

9. 贝尔曼期望方程与贝尔曼最优方程

   • 期望方程把递归更新进一步拆成同时建立于状态价值与动作价值上的方程，随着向未来动作步推进，按策略 π 交替展开 V 与 Q：V_π(s)=Σ_a π(a|s)Q_π(s,a)，Q_π(s,a)=R(s,a)+γΣ_{s’}P^a_{ss’}V_π(s’)，两者还可互相代入得到只含 V 或只含 Q 的形式。
   • 若只关心最优值而非按策略求期望，可在交替更新时直接取最大值而不使用策略：V_*(s)=max_a Q_*(s,a)，Q_*(s,a)=R(s,a)+γΣ_{s’}P^a_{ss’}V_*(s’)。
   • 代入后分别得到 V_*(s)=max_a(R(s,a)+γΣ_{s’}P^a_{ss’}V_*(s’)) 和 Q_*(s,a)=R(s,a)+γΣ_{s’}P^a_{ss’}max_{a’}Q_*(s’,a’)，形式与期望方程相似。
   • 若完全掌握环境信息，这就变成规划问题，可用 DP 求解；但多数场景下不知道 P^a_{ss’} 和 R(s,a)，无法直接套用贝尔曼方程解 MDP，不过它为许多强化学习算法奠定了理论基础。

10. 常见方法概览；动态规划

    • 接下来逐一梳理求解强化学习问题的主要方法与经典算法。
    • 当模型完全已知时，依贝尔曼方程可用动态规划（DP）迭代地评估价值函数并改进策略。

11. 策略评估、策略改进与策略迭代

    • 策略评估（policy evaluation）是计算给定策略 π 的状态价值 V_π：V_{t+1}(s)=E_π[r+γV_t(s’)|S_t=s]=Σ_a π(a|s)Σ_{s’,r}P(s’,r|s,a)(r+γV_t(s’))。
    • 策略改进（policy improvement）基于价值函数，用贪心方式生成更好的策略 π’≥π，其依据是 Q_π(s,a)=E[R_{t+1}+γV_π(S_{t+1})|S_t=s,A_t=a]=Σ_{s’,r}P(s’,r|s,a)(r+γV_π(s’))。
    • 广义策略迭代（GPI）把评估与改进结合起来交替进行：π_0 →评估→ V_{π_0} →改进→ π_1 → … → π_* →评估→ V_*。价值函数被反复逼近当前策略的真实值，同时策略不断逼近最优，该过程总能收敛到最优。
    • 收敛原因：若由策略 π 贪心得到 π’(s)=argmax_a Q_π(s,a)，则 Q_π(s,π’(s))=max_a Q_π(s,a)≥Q_π(s,π(s))=V_π(s)，故改进后的 π’ 价值必然不差于原策略。

12. 蒙特卡洛方法

    • 回顾 V(s)=E[G_t|S_t=s]。蒙特卡洛（MC）方法思想简单：不建模环境动态，直接从原始经验的回合中学习，用观测到的平均回报近似期望回报。
    • 计算经验回报 G_t=Σ_{k=0}^{T-t-1}γ^k R_{t+k+1} 需要完整回合 S_1,A_1,R_2,…,S_T，且所有回合必须最终终止。
    • 状态 s 的经验平均回报为 V(s)=Σ_t 1[S_t=s]G_t / Σ_t 1[S_t=s]；1[·] 为指示函数。每访问一次状态就计数为 every-visit，只计回合中首次遇到该状态为 first-visit；把计数对象换成 (s,a) 对即可推广到动作价值。
    • 用 MC 学最优策略时按类似 GPI 的思路迭代：按当前价值贪心改进策略 π(s)=argmax_a Q(s,a)；用新策略生成新回合（ε-greedy 等有助于平衡利用与探索）；再用该回合估计 Q，即对每次 (s,a) 出现的折扣回报之和除以出现次数。

13. 时序差分学习：自举与价值估计

    • 时序差分（TD）学习与 MC 一样是无模型、从经验回合中学习，但 TD 可以从**不完整**的回合学习，无需把回合追踪到终止；Sutton & Barto (2017) 称其为“对强化学习而言核心而新颖的一个想法”。
    • TD 用已有估计来更新目标，而不像 MC 那样完全依赖真实奖励与完整回报，这种做法称为自举（bootstrapping）。
    • TD 的核心是把 V(S_t) 朝估计回报 R_{t+1}+γV(S_{t+1})（即 TD 目标）更新，更新幅度由学习率 α 控制：V(S_t)←(1−α)V(S_t)+αG_t，等价于 V(S_t)←V(S_t)+α(G_t−V(S_t))，用 TD 目标替换 G_t 得 V(S_t)←V(S_t)+α(R_{t+1}+γV(S_{t+1})−V(S_t))。
    • 动作价值同理：Q(S_t,A_t)←Q(S_t,A_t)+α(R_{t+1}+γQ(S_{t+1},A_{t+1})−Q(S_t,A_t))。接下来介绍 TD 控制（学习最优策略）的经典算法。

14. SARSA：同策略 TD 控制；Q-Learning：异策略 TD 控制

    • SARSA 通过 …, S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1}, … 的序列更新 Q 值，思路与 GPI 相同。单个回合内：初始化 t=0；从 S_0 出发按 argmax 选 A_0（常用 ε-greedy）；执行 A_t 后观测 R_{t+1} 并进入 S_{t+1}；以同样方式选下一动作 A_{t+1}=argmax_a Q(S_{t+1},a)；
    • 再按上式的 TD 更新 Q；t←t+1 重复。即每一步都要按当前策略选择下一个动作。
    • Q-Learning（Watkins & Dayan, 1992）是早期强化学习的重大突破，属于异策略 TD 控制。单个回合内：初始化 t=0，从 S_0 出发；在 t 时刻按 Q 值选动作 A_t=argmax_a Q(S_t,a)（常用 ε-greedy）；执行后观测 R_{t+1} 进入 S_{t+1}；
    • 更新 Q(S_t,A_t)←Q(S_t,A_t)+α(R_{t+1}+γmax_{a∈A}Q(S_{t+1},a)−Q(S_t,A_t))；t←t+1 重复。
    • 与 SARSA 的关键区别：Q-Learning 不按当前策略去选第二个动作 A_{t+1}，而是从最优 Q 值中估计 Q*；究竟哪个动作 a* 带来这个最大值并不重要，下一步 Q-Learning 也未必执行 a*。（原文此处给出 Q-Learning 与 SARSA 的备份图对比。）
    text

    SARSA:
    
    1. Initialize t=0.
    2. Start with S_0 and choose action A_0 = argmax_{a in A} Q(S_0, a), where epsilon-greedy is commonly applied.
    3. At time t, after applying action A_t, we observe reward R_{t+1} and get into the next state S_{t+1}.
    4. Then pick the next action in the same way as in step 2: A_{t+1} = argmax_{a in A} Q(S_{t+1}, a).
    5. Update the Q-value function: Q(S_t, A_t) <- Q(S_t, A_t) + alpha (R_{t+1} + gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)).
    6. Set t = t+1 and repeat from step 3.
    
    Q-Learning:
    
    1. Initialize t=0.
    2. Starts with S_0.
    3. At time step t, we pick the action according to Q values, A_t = argmax_{a in A} Q(S_t, a) and epsilon-greedy is commonly applied.
    4. After applying action A_t, we observe reward R_{t+1} and get into the next state S_{t+1}.
    5. Update the Q-value function: Q(S_t, A_t) <- Q(S_t, A_t) + alpha (R_{t+1} + gamma max_{a in A} Q(S_{t+1}, a) - Q(S_t, A_t)).
    6. t = t+1 and repeat from step 3.

15. 深度 Q 网络（DQN）

    • 理论上 Q-learning 可以为每个状态-动作对记住 Q*(·)，但状态和动作空间一大就计算不可行，因此用带参数 θ 的机器学习模型近似 Q 值，即函数近似（function approximation），记作 Q(s,a;θ)。
    • Q-learning 一旦与非线性 Q 值函数近似和自举（bootstrapping）结合，训练可能不稳定并发散。
    • DQN（Mnih 等，2015）用两个机制稳定 Q-learning 训练：经验回放（experience replay）把所有步骤 (S_t,A_t,R_t,S_{t+1}) 存入回放记忆 D_t，更新时随机抽样，从而提升数据效率、去除观测序列相关性、平滑数据分布变化。
    • 第二个机制是周期性更新的目标网络：每 C 步（C 为超参数）克隆并冻结 Q 网络作为优化目标，克服短期震荡，使训练更稳定。
    • 损失函数为在回放记忆均匀分布 U(D) 下对 (r + γ max_a' Q(s',a';θ⁻) − Q(s,a;θ))² 求期望，θ⁻ 为冻结目标网络参数；此外把误差项裁剪到 [-1,1] 在实践中也有帮助。
    text

    \mathcal{L}(\theta) = \mathbb{E}_{(s, a, r, s') \sim U(D)} \Big[ \big( r + \gamma \max_{a'} Q(s', a'; \theta^{-}) - Q(s, a; \theta) \big)^2 \Big]

16. 结合 TD 与 MC 学习（n 步回报与 TD(λ)）

    • 在 TD 学习中计算目标时只向前看一步，可推广到多步：n 步估计回报 G_t^(n) 为前 n 步折扣奖励之和加上 γ^n V(S_{t+n})；n=1 即 TD 学习，n=∞ 即蒙特卡洛估计。
    • 广义 n 步 TD 的更新形式不变：V(S_t) ← V(S_t) + α(G_t^(n) − V(S_t))。
    • n 取多大最好没有唯一答案，常见的做法是对所有 n 步目标做加权求和，权重按 λ^(n−1) 衰减；直觉与折扣未来奖励类似——看得越远越不确定。
    • 为使权重和（n→∞）为 1，每个权重乘以 (1−λ)，因为 1+λ+λ²+… = 1/(1−λ)；这样的加权和称为 λ-回报 G_t^λ = (1−λ)Σ λ^(n−1) G_t^(n)。
    • 采用 λ-回报更新价值的方法称为 TD(λ)，前面介绍的一步版本等价于 TD(0)。
    text

    G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{n-1} R_{t+n} + \gamma^n V(S_{t+n})

17. 策略梯度（Policy Gradient）

    • 前面所有方法都是先学习状态/动作价值函数再据此选动作；策略梯度方法直接用参数化函数 π(a|s;θ) 学习策略。
    • 目标是最大化期望回报（即奖励函数，与损失函数相反）：离散空间下 J(θ)=V_{π_θ}(S_1)，S_1 为初始状态；连续空间下按状态的平稳分布 d_{π_θ}(s) 加权求和 π(a|s,θ)Q_π(s,a)。
    • 用梯度上升寻找产生最高回报的 θ。策略类方法在连续空间更实用，因为连续空间中动作和/或状态无穷多，基于价值的方法计算代价大得多。
    • 作者指出其后续文章给出了策略梯度定理的证明并介绍了多种策略梯度算法。
    text

    \mathcal{J}(\theta) = \sum_{s \in \mathcal{S}} d_{\pi_\theta}(s) V_{\pi_\theta}(s) = \sum_{s \in \mathcal{S}} \Big( d_{\pi_\theta}(s) \sum_{a \in \mathcal{A}} \pi(a \vert s, \theta) Q_\pi(s, a) \Big)

18. 策略梯度定理

    • 数值求梯度：在第 k 维给 θ 加小扰动 ε，用 (J(θ+εu_k)−J(θ))/ε 近似；即使 J(θ) 不可微也适用，但速度很慢。
    • 解析推导中把平稳分布 d_{π_θ}(·) 替换为 d(·) 是成正比的，依据见 Sutton & Barto (2017) 第 13.1 节。
    • 推导关键是乘除 π(a|s;θ) 得到 ∇ln π(a|s;θ)，最终梯度写为期望 E_{π_θ}[∇ln π(a|s;θ) Q_π(s,a)]。
    • 这一结果即“策略梯度定理”，为各种策略梯度算法提供理论基础。
    text

    \nabla \mathcal{J}(\theta) = \mathbb{E}_{\pi_\theta} [\nabla \ln \pi(a \vert s, \theta) Q_\pi(s, a)]

19. REINFORCE

    • REINFORCE 又称蒙特卡洛策略梯度，依赖用回合样本做 MC 估计得到的 Q_π(s,a) 来更新策略参数 θ。
    • 常见变体是从回报 G_t 中减去基线值以降低梯度估计方差而不改变偏差；常用基线是状态价值，此时用 A(s,a)=Q(s,a)−V(s) 做梯度上升。
    • 算法流程：随机初始化 θ；生成一个回合 S_1,A_1,R_2,…,S_T；对每个 t 估计自 t 起的回报 G_t，并按 θ ← θ + αγ^t G_t ∇ln π(A_t|S_t,θ) 更新。
    text

    \theta \leftarrow \theta + \alpha \gamma^t G_t \nabla \ln \pi(A_t \vert S_t, \theta)

20. 演员-评论家（Actor-Critic）

    • 在策略之外再学习价值函数，就得到 Actor-Critic 算法。
    • 评论家（Critic）更新价值函数参数 w，按算法不同可以是动作价值 Q(a|s;w) 或状态价值 V(s;w)；演员（Actor）按评论家指示的方向更新策略参数 θ，即 π(a|s;θ)。
    • 动作价值版流程：随机初始化 s、θ、w 并采样 a∼π(a|s;θ)；每步采样奖励 r_t 和下一状态 s'，再采样下一动作 a'。
    • 策略更新：θ ← θ + α_θ Q(s,a;w)∇_θ ln π(a|s;θ)。
    • 价值修正：G_{t:t+1} = r_t + γQ(s',a';w) − Q(s,a;w)，并用 w ← w + α_w G_{t:t+1} ∇_w Q(s,a;w) 更新；最后令 a←a'、s←s'。α_θ 与 α_w 分别是策略和价值函数的学习率。
    text

    G_{t:t+1} = r_t + \gamma Q(s', a'; w) - Q(s, a; w)
    w \leftarrow w + \alpha_w G_{t:t+1} \nabla_w Q(s, a; w)

21. A3C

    • 异步优势演员-评论家（Asynchronous Advantage Actor-Critic，A3C；Mnih 等，2016）是侧重并行训练的经典策略梯度方法。
    • A3C 中评论家学习状态价值 V(s;w)，多个演员并行训练并时不时与全局参数同步，因此天然适合多核 CPU 单机并行。
    • 状态价值的损失是最小化均方误差 J_v(w)=(G_t−V(s;w))²，用梯度下降求最优 w；该状态价值用作策略梯度更新中的基线。
    • 算法框架：维护全局 θ、w 与线程私有 θ'、w'；每轮清零梯度、把线程参数同步为全局参数，收集最多 t_max 步的轨迹。
    • 从轨迹末端回溯计算回报 R（终止为 0，否则为 V(s_t;w')），逐步 R ← r_i + γR，累加策略梯度 ∇_θ' log π(a_i|s_i;θ')(R−V(s_i;w')) 和价值梯度 ∇_w'(R−V(s_i;w'))²，最后用累加梯度更新全局 θ 和 w。
    • 第 6.2 步的梯度累加可看作小批量随机梯度更新的变体：θ 和 w 各自朝每条训练线程的方向做小幅修正。
    text

    d\theta \leftarrow d\theta + \nabla_{\theta'} \log \pi(a_i \vert s_i; \theta')(R - V(s_i; w'))
    dw \leftarrow dw + \nabla_{w'} (R - V(s_i; w'))^2

22. 进化策略（Evolution Strategies）

    • 进化策略（ES）是与模型无关的优化方法，仿照达尔文自然选择：解可自由与环境交互看能否解决问题，且能计算每个解的适应度（fitness），无需知道环境配置。
    • 从随机解构成的种群开始，只有高适应度的候选能存活，再由幸存者重组设置（基因变异）产生新一代，重复直到新解足够好。
    • ES 不依赖价值近似，直接学策略参数 θ：假设 θ 服从均值 μ、协方差固定为 σ²I 的各向同性高斯分布，用与策略梯度类似的技巧推出梯度的期望形式 E[F(θ)(θ−μ)/σ²]。
    • 改写为以“均值”参数 θ（作为继续变异的基础基因）和噪声 ε∼N(0,I) 表示：∇_θ E[F(θ+σε)] = (1/σ)E[F(θ+σε)ε]，ε 控制加入的高斯噪声幅度。
    • 并行实现中工作进程共享随机种子，从而能以极小通信量重建高斯噪声（Salimans 等，2017）。
    • ES 作为黑盒优化用于 RL 的特点：不需要价值函数近似、不做梯度反向传播、对延迟或长期奖励不变、高度可并行且数据通信很少。
    text

    \nabla_\theta \mathbb{E}_{\epsilon \sim N(0, I)} F(\theta + \sigma \epsilon) = \frac{1}{\sigma} \mathbb{E}_{\epsilon \sim N(0, I)} [F(\theta + \sigma \epsilon) \epsilon]

23. 探索与利用的困境

    • 面对未知环境时，探索与利用（exploration-exploitation）的权衡是找到好解的关键：探索不足无法了解环境，利用不足无法完成奖励优化。
    • 不同算法平衡方式不同：MC 方法、Q-learning 以及许多同策略算法通常用 ε-greedy 实现探索；在 ES 中探索由策略参数扰动体现。开发新 RL 算法时需要考虑这一点。

24. 致命三角问题

    • 我们想要 TD 方法带来效率与灵活性，但若把离策略（off-policy）、非线性函数近似和自举三者结合在同一算法中，训练可能不稳定、难以收敛。
    • 该问题称为致命三角（deadly triad；Sutton & Barto，2017）；DQN 用经验回放和周期性冻结目标网络来稳定训练，是应对该问题的架构之一。