Henry Zha Field Notes

第五章：应用展望与贝尔曼方程推导

涵盖 AlphaGo 与蒙特卡洛树搜索（MCTS）、NAS/推荐系统/网约车应用、强化学习制约因素及贝尔曼方程严谨数学推导。

应用与展望

AlphaGo 与蒙特卡洛树搜索 (MCTS)

强化学习算法分为两类：

  • 无模型 (Model-free)：如 DQN、策略梯度。不学习环境的状态转移与奖励机制，直接学习动作选择策略。
  • 基于模型 (Model-based)：构建环境内部模型，主要包含两部分：
    • 状态转移模型 (Transition Model)：预测 P(s′∣s,a)P(s' \mid s,a)
    • 奖励模型 (Reward Model)：预测 R(s,a,s′)R(s,a,s')

蒙特卡洛树搜索（Monte Carlo Tree Search，MCTS） 是一种基于模型的强化学习方法，在对弈时向前模拟推演做决策，不需要在线更新网络参数。

MCTS 的四个步骤

假设已有策略网络 π(a∣s;θ)\pi(a\mid s;\theta) 和价值网络 v(s;ω)v(s;\omega)，MCTS 每次决策包含多轮模拟，每轮分为四个步骤：

  1. 选择 (Selection)： 依据胜率与策略网络概率之和选择动作： score(a)≜Q(a)+η1+N(a)⋅π(a∣s;θ)\text{score}(a) \triangleq Q(a) + \frac{\eta}{1 + N(a)} \cdot \pi(a\mid s;\theta) 其中 N(a)N(a) 是动作 aa 的访问次数，Q(a)Q(a) 为此前模拟算出的动作平均价值。

  2. 扩展 (Expansion)： 利用策略网络抽样对手动作 at′∼π(⋅∣st′;θ)a_t' \sim \pi(\cdot\mid s_t';\theta)，生成新的推演状态。

  3. 求值 (Evaluation)： 从新状态开始，使用策略网络快速模拟博弈直至出结果（得到奖励 r∈{+1,−1}r \in \{+1, -1\}），并结合价值网络估值计算状态评估： V(st+1)≜r+v(st+1;ω)2V(s_{t+1}) \triangleq \frac{r + v(s_{t+1};\omega)}{2}

  4. 回溯 (Backup)： 更新推演路径上所有动作的访问计数 N(a)N(a) 与平均价值 Q(a)Q(a)。

模拟结束后，根据访问次数最多的动作做出最终决策：at=arg⁡max⁡aN(a)a_t = \arg \max_a N(a)。

AlphaGo 演进历程

  • AlphaGo (2016)：

    1. 行为克隆：从人类棋谱中监督学习策略网络。
    2. 自我博弈：利用 REINFORCE 强化学习提升策略网络。
    3. 价值网络：基于训练好的策略网络训练价值网络。

  • AlphaGo Zero： 不再依赖人类棋谱或 REINFORCE 算法，直接在自我博弈中向 MCTS 产生的策略分布进行对齐学习。

现实世界中的应用

  1. 神经网络结构搜索 (NAS)：利用 RL 自动搜索最优网络架构。
  2. 自动生成 SQL 语句：根据数据库上下文生成高效查询语句。
  3. 推荐系统：
    • 传统监督学习假设用户兴趣固定，拟合已有喜好。
    • 强化学习假设用户兴趣可被发掘，主动探索用户潜在喜好（如虚拟淘宝系统）。
  4. 网约车调度：优化车辆时空分配，需使用正则项保证价值网络对时间、地点平滑。

强化学习落地的四大制约因素

  • 样本复杂度极高：训练需要海量交互数据。
  • 探索代价高昂：在真实物理世界（如自动驾驶、工业机器人）随机探索风险极大。
  • 超参数高度敏感：激活函数、学习率等微小调整会导致结果天差地别。
  • 稳定性较差：同一套代码更换随机种子可能导致从收敛变为完全发散。

附录：贝尔曼方程的严谨数学推导

根据折扣回报定义 Ut=Rt+γUt+1U_t = R_t + \gamma U_{t+1}，动作价值函数为 Qπ(st,at)=E[Ut∣St=st,At=at]Q_{\pi}(s_t,a_t) = \mathbb{E}[U_t \mid S_t = s_t, A_t = a_t]：

Qπ(st,at)=ESt+1:,At+1:[Rt+γ⋅Ut+1∣St=st,At=at]=ESt+1[Rt∣St=st,At=at]+γ⋅ESt+1,At+1[Qπ(St+1,At+1)∣St=st,At=at](A.1)\begin{aligned} Q_{\pi}(s_t,a_t) & = \mathbb{E}_{\mathcal{S}_{t+1:}, \mathcal{A}_{t+1:}}[R_t + \gamma\cdot U_{t+1} \mid S_t = s_t, A_t = a_t]\\ & = \mathbb{E}_{S_{t+1}}[R_t \mid S_t = s_t, A_t = a_t] + \gamma\cdot \mathbb{E}_{S_{t+1}, A_{t+1}}[Q_\pi(S_{t+1}, A_{t+1}) \mid S_t = s_t, A_t = a_t] \end{aligned} \tag{A.1}

定理 A.1：动作价值的贝尔曼方程 (Qπ→QπQ_\pi \to Q_\pi)
假设奖励 RtR_t 是 (St,At,St+1)(S_t, A_t, S_{t+1}) 的函数，则： Qπ(st,at)=ESt+1,At+1[Rt+γ⋅Qπ(St+1,At+1)  |  St=st,At=at]Q_{\pi}(s_t,a_t) = \mathbb{E}_{{S}_{t+1}, {A}_{t+1}}\left[R_t + \gamma \cdot Q_{\pi}(S_{t+1},A_{t+1}) \;\middle|\; S_t=s_t, A_t=a_t \right]

定理 A.2：动作价值与状态价值的关系 (Qπ→VπQ_\pi \to V_\pi)
由于 Vπ(St+1)=EAt+1[Q(St+1,At+1)]V_{\pi}(S_{t+1}) = \mathbb{E}_{A_{t+1}}[Q(S_{t+1},A_{t+1})]，可得： Qπ(st,at)=ESt+1[Rt+γ⋅Vπ(St+1)  |  St=st,At=at]Q_{\pi}(s_t,a_t) = \mathbb{E}_{S_{t+1}}\left[R_t + \gamma\cdot V_{\pi}(S_{t+1}) \;\middle|\; S_t=s_t, A_t=a_t \right]

定理 A.3：状态价值的贝尔曼方程 (Vπ→VπV_\pi \to V_\pi)
由于 Vπ(St)=EAt[Q(St,At)]V_{\pi}(S_t) = \mathbb{E}_{A_t}[Q(S_t,A_t)]，可得： Vπ(st)=EAt,St+1[Rt+γ⋅Vπ(St+1)  |  St=st]V_{\pi}(s_t) = \mathbb{E}_{A_t, S_{t+1}}\left[R_t + \gamma\cdot V_{\pi}(S_{t+1}) \;\middle|\; S_t=s_t \right]

定理 A.4：最优贝尔曼方程 (Optimal Bellman Equations)
设最优动作 At+1=arg⁡max⁡AQ∗(St+1,A)A_{t+1} = \arg \max_{A} Q_*(S_{t+1},A)，可得： Q∗(st,at)=ESt+1∼p(⋅∣st,at)[Rt+γ⋅max⁡A∈AQ∗(St+1,A)  |  St=st,At=at]Q_{*}(s_t,a_t) = \mathbb{E}_{{S}_{t+1} \sim p(\cdot\mid s_t,a_t)}\left[R_t + \gamma \cdot \max_{A\in\mathcal{A}}Q_{*}(S_{t+1},A) \;\middle|\; S_t=s_t, A_t=a_t \right]