2.4 贝尔曼方程（Bellman Equation）与蒙特卡洛方法（Monte-Carlo Methods）

在马尔可夫决策过程（MDP）中，一个智能体在时间步 $t$ 处于状态 $S_t=s$，选择动作 $A_t=a$，获得即时奖励 $R_t$（或写作 $r(s,a)$），并以转移概率 $p(s^{\prime }|s,a)$ 到达下一状态 $S_{t+1}=s^{\prime }$。策略 $\pi (a|s)$ 表示在状态 $s$ 选择动作 $a$ 的概率。

为了描述“从某个状态出发，长期能获得多少回报”，引入折扣回报（return）：
$$G_t=\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k}$$
其中折扣因子 $\gamma \in [0,1)$ 控制“未来奖励”的重要程度：$\gamma$ 越大，越重视长期收益。

---

1. 状态价值函数与动作价值函数

**状态价值函数（State-Value Function）**定义为：在策略 $\pi$ 下，从状态 $s$ 出发的期望回报：
$$V^{\pi }(s)={\mathbb{E}}_{\pi }[G_t|S_t=s]$$

**动作价值函数（Action-Value Function）**定义为：在策略 $\pi$ 下，从状态 $s$ 先执行动作 $a$，之后继续按策略 $\pi$ 行动的期望回报：
$$Q^{\pi }(s,a)={\mathbb{E}}_{\pi }[G_t|S_t=s,A_t=a]$$

二者之间有一个关键关系：$V^{\pi }(s)$ 是在状态 $s$ 下对动作价值按策略概率的期望：
$$V^{\pi }(s)=\sum _{a\in \mathcal{A}}\pi (a|s)Q^{\pi }(s,a)$$

直观理解：如果你在 $s$ 会随机选动作，那么“状态价值”就是这些动作价值的平均（加权平均）。

---

2. 贝尔曼期望方程（Bellman Expectation Equation）

贝尔曼方程的核心是把“长期回报”拆成“当前一步 + 下一步之后的长期回报”。
从回报定义出发：
$$G_t=R_t+\gamma G_{t+1}$$
对策略 $\pi$ 下的期望取值，并条件在 $S_t=s$：
$$V^{\pi }(s)={\mathbb{E}}_{\pi }[R_t+\gamma V^{\pi }(S_{t+1})|S_t=s]$$

把期望展开成对动作与下一状态的求和，就得到常见的显式形式：
$$V^{\pi }(s)=\sum _{a\in \mathcal{A}}\pi (a|s)\left(r(s,a)+\gamma \sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }|s,a)V^{\pi }(s^{\prime })\right)$$

这条公式表达了：

• 先按 $\pi (a|s)$ 选择动作 $a$；
• 获得即时奖励 $r(s,a)$；
• 再按环境转移 $p(s^{\prime }|s,a)$ 到 $s^{\prime }$；
• 从 $s^{\prime }$ 继续按同一策略获得 $V^{\pi }(s^{\prime })$，并折扣 $\gamma$。

同理，动作价值函数也满足贝尔曼期望方程：
$$Q^{\pi }(s,a)={\mathbb{E}}_{\pi }[R_t+\gamma Q^{\pi }(S_{t+1},A_{t+1})|S_t=s,A_t=a]$$
展开为可计算的求和形式：
$$Q^{\pi }(s,a)=r(s,a)+\gamma \sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }|s,a)\sum _{a^{\prime }\in \mathcal{A}}\pi (a^{\prime }|s^{\prime })Q^{\pi }(s^{\prime },a^{\prime })$$

这里出现的两层求和分别对应：

• 由 $(s,a)$ 转移到下一状态 $s^{\prime }$；
• 在下一状态 $s^{\prime }$ 按策略选择下一动作 $a^{\prime }$。

---

3. 用一个小例子理解贝尔曼期望方程

考虑一个非常小的 MDP：

• 状态集合：S={s0,s1}\mathcal{S}=\{s_0, s_1\}S={s0​,s1​}
• 动作集合：A={a0,a1}\mathcal{A}=\{a_0,a_1\}A={a0​,a1​}
• 折扣因子：$\gamma =0.9$

环境动力学（只描述关键部分）：

• 在 $s_0$：
  • 选 $a_0$：得到奖励 $r(s_0,a_0)=1$，并确定转移到 $s_1$（即 $p(s_1|s_0,a_0)=1$）
  • 选 $a_1$：得到奖励 $r(s_0,a_1)=0$，并确定留在 $s_0$（即 $p(s_0|s_0,a_1)=1$）
• 在 $s_1$：无论选什么动作，都得到奖励 $0$ 并留在 $s_1$（吸收状态）

给定策略 $\pi$：

• 在 $s_0$：$\pi (a_0|s_0)=0.5,\pi (a_1|s_0)=0.5$
• 在 $s_1$：动作无关紧要

用贝尔曼期望方程写 $V^{\pi }(s_1)$：
$$V^{\pi }(s_1)=\sum _a\pi (a|s_1)\left(0+\gamma \cdot V^{\pi }(s_1)\right)=\gamma V^{\pi }(s_1)$$
由于 $\gamma <1$，唯一解是：
$$V^{\pi }(s_1)=0$$

再写 $V^{\pi }(s_0)$：
Vπ(s0)=∑a∈{a0,a1}π(a∣s0)(r(s0,a)+γ∑s′p(s′∣s0,a)Vπ(s′)) V^{\pi}(s_0)=\sum_{a\in\{a_0,a_1\}}\pi(a|s_0)\left(r(s_0,a)+\gamma\sum_{s'}p(s'|s_0,a)V^{\pi}(s')\right) Vπ(s0​)=a∈{a0​,a1​}∑​π(a∣s0​)(r(s0​,a)+γs′∑​p(s′∣s0​,a)Vπ(s′))
代入：

• 对 $a_0$：$r=1$，转移到 $s_1$，所以后续价值是 $V^{\pi }(s_1)=0$
• 对 $a_1$：$r=0$，转移到 $s_0$，后续价值是 $V^{\pi }(s_0)$

得到：
$$V^{\pi }(s_0)=0.5(1+\gamma \cdot 0)+0.5(0+\gamma V^{\pi }(s_0))$$
化简：
$$V^{\pi }(s_0)=0.5+0.5\gamma V^{\pi }(s_0)$$
移项：
$$(1-0.5\gamma )V^{\pi }(s_0)=0.5$$
因此：
$$V^{\pi }(s_0)=\frac{0.5}{1-0.5\gamma }=\frac{0.5}{1-0.45}=\frac{0.5}{0.55}\approx 0.9091$$

这个结果的含义非常直观：在 $s_0$ 你有一半概率直接拿到 1 并进入零价值的吸收状态；另一半概率原地“拖延”，未来仍有机会拿到 1，但被折扣衰减。

---

4. 贝尔曼最优方程（Bellman Optimality Equation）

当目标从“评估给定策略 $\pi$”变为“寻找最优策略”时，需要定义最优价值函数：

最优状态价值函数
$$V^{\ast }(s)=\underset{\pi }{\max }{V}^{\pi }(s),s\in \mathcal{S}$$

最优动作价值函数
$$Q^{\ast }(s,a)=\underset{\pi }{\max }{Q}^{\pi }(s,a),s\in \mathcal{S},a\in \mathcal{A}$$

最优性的关键在于：
如果从当前状态开始总是做“当下最优”的决策，并且以后每一步也都继续做最优决策，那么得到的价值就是最优价值。

因此最优状态价值满足：
$$V^{\ast }(s)=\underset{a\in \mathcal{A}}{\max }\left\{r(s,a)+\gamma \sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }|s,a)V^{\ast }(s^{\prime })\right\}$$

最优动作价值满足：
$$Q^{\ast }(s,a)=r(s,a)+\gamma \sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }|s,a)\underset{a^{\prime }\in \mathcal{A}}{\max }{Q}^{\ast }(s^{\prime },a^{\prime })$$

这里的 $\max$ 把“对策略的期望”替换成“对动作的最优选择”。

---

5. 最优策略（Optimal Policy）

通常最优策略可能不唯一（多个动作都能达到同样的最优值时），但最优价值函数是唯一的。

如果已知 $Q^{\ast }(s,a)$，可以构造一个确定性最优策略：
$${\pi }^{\ast }(s)=\arg \underset{a\in \mathcal{A}}{\max }{Q}^{\ast }(s,a)$$

最优价值函数之间还有两个常用关系：
$$Q^{\ast }(s,a)=r(s,a)+\gamma \sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }|s,a)V^{\ast }(s^{\prime })$$
以及
$$V^{\ast }(s)=\underset{a\in \mathcal{A}}{\max }{Q}^{\ast }(s,a)$$

直观解释：

• $Q^{\ast }(s,a)$：先做 $a$ 的即时奖励 + 转移后在下一状态“按最优方式继续”的折扣期望
• $V^{\ast }(s)$：在当前状态从所有动作里挑一个能把长期回报做到最大的动作

---

蒙特卡洛方法（Monte-Carlo Methods）

蒙特卡洛方法是一类“用随机采样估计期望”的方法。只要目标可以表示为某种期望（Expectation），就可以通过大量采样求平均来近似它。

---

1. 一个直观例子：用随机点估计圆面积

在边长为 1 的正方形内随机采样点，圆为内切圆（半径 $0.5$）。
若采样点均匀分布，则：

• 落在圆内的概率 $\approx$ 圆面积 / 正方形面积
• 用点数比例近似面积比

因此：
$$\frac{\text{圆的面积}}{\text{正方形的面积}}\approx \frac{\text{落在圆内的点数}}{\text{总点数}}$$

这个例子体现了蒙特卡洛的核心：用“频率”逼近“概率”，再用“概率”逼近“几何量/期望”。

---

2. 用蒙特卡洛估计状态价值

在强化学习中，状态价值是一个期望回报：
$$V^{\pi }(s)={\mathbb{E}}_{\pi }[G_t|S_t=s]$$

蒙特卡洛方法的思路是：
从状态 $s$ 出发，在策略 $\pi$ 下运行很多次（采样很多条轨迹），得到多次回报 $G_t^{(i)}$，用样本均值估计期望：
$$V^{\pi }(s)\approx \frac{1}{N}\sum _{i=1}^N{G}_t^{(i)}$$

当 $N$ 趋向无穷大时，根据大数定律，样本均值会收敛到真实期望：
$$\text{当 }N(s)\to \infty ,V(s)\to V^{\pi }(s)$$

---

3. MC 状态价值估计的标准流程（逐步解释）

下面描述一个典型的“基于策略 $\pi$ 的 MC 状态价值估计”流程。核心是统计每个状态出现时对应的回报，然后求平均。

步骤 1：采样轨迹（Episode / 序列）

用策略 $\pi$ 与环境交互，得到多条完整序列（终止或截断），第 $i$ 条序列写作：
$$s_0^{(i)}\stackrel{a_0^{(i)}}{\to }{r}_0^{(i)},s_1^{(i)}\stackrel{a_1^{(i)}}{\to }{r}_1^{(i)},\dots ,s_{T-1}^{(i)}\stackrel{a_{T-1}^{(i)}}{\to }{r}_{T-1}^{(i)},s_T^{(i)}$$

这里 $T$ 是终止时间步（或截断长度）。轨迹中的每一步都包含状态、动作、奖励与下一状态。

步骤 2：计算每个时间步的回报 $G_t$

对某条轨迹的某个时间步 $t$，从该步开始的折扣回报为：
$$G_t=r_t+\gamma r_{t+1}+{\gamma }^2{r}_{t+2}+\cdots +{\gamma }^{T-1-t}{r}_{T-1}$$

注意：MC 的关键是它不使用贝尔曼方程做“引导式更新”，而是等整条轨迹跑完后，用真实采样到的回报来估计价值。

步骤 3：为每个状态累计回报并计数

维护两个量：

• 状态出现次数：$N(s)$
• 状态回报总和：$M(s)$

当在某条轨迹的时间步 $t$ 访问到状态 $s$ 时：
$$N(s)\leftarrow N(s)+1$$
$$M(s)\leftarrow M(s)+G_t$$

最后用平均回报作为价值估计：
$$V(s)=\frac{M(s)}{N(s)}$$

---

4. 增量更新形式（更便于在线统计）

如果不想保存所有历史回报，而是每次来一个样本就更新一次平均值，可以用增量均值公式。

设当前第 $N(s)$ 次观察到状态 $s$ 时对应回报为 $G$，则：
$$V(s)\leftarrow V(s)+\frac{1}{N(s)}(G-V(s))$$

这个公式等价于“维护样本均值”，其直观含义是：

• $(G-V(s))$ 是新样本相对当前估计的偏差
• $\frac{1}{N(s)}$ 是步长，随着次数变多逐渐变小，使估计趋于稳定

---

5. 一个具体轨迹例子：手算 MC 回报与 $V(s)$

设某次采样得到一条长度为 4 的轨迹（$t=0,1,2,3$），奖励序列为：

• $r_0=2$
• $r_1=0$
• $r_2=1$
• $r_3=3$

折扣因子 $\gamma =0.9$。则从各时间步开始的回报：

从 $t=0$：
$$G_0=2+0.9\cdot 0+0.9^2\cdot 1+0.9^3\cdot 3$$

从 $t=1$：
$$G_1=0+0.9\cdot 1+0.9^2\cdot 3$$

从 $t=2$：
$$G_2=1+0.9\cdot 3$$

从 $t=3$：
$$G_3=3$$

如果在这条轨迹里状态 $s$ 恰好出现在 $t=1$ 和 $t=3$ 两个时刻，那么它会收到两个样本回报 $G_1$ 与 $G_3$。
若这是目前为止仅有的两次访问，则：
$$N(s)=2,M(s)=G_1+G_3,V(s)=\frac{G_1+G_3}{2}$$

用增量更新也能得到相同结果：

• 第一次看到 $s$：$V(s)=G_1$
• 第二次看到 $s$：
  $$V(s)\leftarrow V(s)+\frac{1}{2}(G_3-V(s))=\frac{G_1+G_3}{2}$$

这体现了 MC 的基本机制：价值估计来自“真实采样回报”的平均，而不是来自下一状态价值的递推。

---

贝尔曼方程与蒙特卡洛方法的关系（理解差异的关键）

两者都在估计价值函数，但信息来源不同：

• 贝尔曼方程强调“递推结构”，把价值写成一步奖励加上下一状态价值的期望：
  $$V^{\pi }(s)={\mathbb{E}}_{\pi }[R_t+\gamma V^{\pi }(S_{t+1})|S_t=s]$$

• 蒙特卡洛方法强调“采样估计”，直接用整段轨迹的实际回报近似期望：
  $$V^{\pi }(s)\approx \frac{1}{N}\sum _{i=1}^N{G}_t^{(i)}$$

因此：

• 贝尔曼方程更像“结构性定义”，可以导出动态规划/TD 等方法；
• 蒙特卡洛更像“统计估计”，在能采样完整轨迹时非常自然。

这两条路线后续会在时序差分（TD）方法中汇合：TD 同时利用贝尔曼递推结构与采样数据，以较低方差、可在线更新的方式估计价值。