贝尔曼方程（Bellman Equation）

---

1. 引言

2. 状态价值函数（State-Value Function）

2.1 定义

状态价值 $v_{\pi }(s)$：在状态 $s$ 按策略 $\pi$ 行动能获得的期望回报。

$$v_{\pi }(s)\doteq {\mathbb{E}}_{\pi }[G_t|S_t=s]$$

展开形式：
$$v_{\pi }(s)={\mathbb{E}}_{\pi }[R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots |S_t=s]$$

2.3 状态价值的组成

$$v_{\pi }(s)=\underset{\text{即时奖励}}{\underbrace{\mathbb{E}[R_{t+1}|S_t=s]}}+\underset{\text{未来奖励}}{\underbrace{\gamma \mathbb{E}[G_{t+1}|S_t=s]}}$$

组成部分	含义	特点
即时奖励	当前动作的直接反馈	确定性较高
未来奖励	后续状态的折扣累积	不确定性高

2.4 状态价值的依赖关系

在平稳MDP + 平稳策略中，$v_{\pi }(s)$ 只依赖于状态s和策略$\pi$，而不依赖于时间 t。因为，

1. 环境是平稳的（stationary），则状态转移概率 $p(s^{\prime },r\mid s,a)$ 不随时间变化
2. 策略是平稳的（stationary），则 $\pi (a\mid s)$ 与时间无关
3. 奖励函数不随时间变化

3. 动作价值函数（Action-Value Function）

3.1 定义

动作价值 $q_{\pi }(s,a)$：在状态 $s$ 采取动作 $a$，然后按策略 $\pi$ 行动的期望回报。

$$q_{\pi }(s,a)\doteq {\mathbb{E}}_{\pi }[G_t|S_t=s,A_t=a]$$

与状态价值的区别：

• 状态价值：从状态出发，按 $\pi$ 选择动作
• 动作价值：指定第一个动作 $a$，之后按 $\pi$ 选择

3.2 状态价值与动作价值的关系

$$v_{\pi }(s)=\sum _{a\in \mathcal{A}}\pi (a|s)\cdot q_{\pi }(s,a)$$

直观理解：

状态价值 = 所有可能动作的价值的加权平均
          （权重为选择该动作的概率）

图示：

       状态 s
          ↓
    π选择动作a
    /    |    \
   /     |     \
  a1    a2     a3
  ↓     ↓      ↓
q(s,a1) q(s,a2) q(s,a3)
  ↓     ↓      ↓
v(s) = π(a1|s)·q(s,a1) + π(a2|s)·q(s,a2) + π(a3|s)·q(s,a3)

4. 贝尔曼方程（Bellman Equation）

4.1 核心思想

贝尔曼方程建立了状态价值之间的递归关系：

$$\boxed{v_{\pi }(s)=\sum _a\pi (a|s)\left[\sum _{r}p(r|s,a)\cdot r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)\cdot v_{\pi }(s^{\prime })\right]}$$

简化形式：
$$v_{\pi }(s)=\sum _a\pi (a|s)\left[r(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)\cdot v_{\pi }(s^{\prime })\right]$$

4.2 推导过程

步骤1：回报的递归分解
$$G_t=R_{t+1}+\gamma G_{t+1}$$

步骤2：状态价值定义
$$v_{\pi }(s)={\mathbb{E}}_{\pi }[G_t|S_t=s]$$

步骤3：代入递归形式
$$\begin{array}{rl}{v}_{\pi }(s)& ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma G_{t+1}|S_t=s]\\ & ={\mathbb{E}}_{\pi }[R_{t+1}|S_t=s]+\gamma {\mathbb{E}}_{\pi }[G_{t+1}|S_t=s]\end{array}$$

步骤4：展开期望
$${\mathbb{E}}_{\pi }[R_{t+1}|S_t=s]=\sum _a\pi (a|s)\sum _{r}p(r|s,a)\cdot r$$

$${\mathbb{E}}_{\pi }[G_{t+1}|S_t=s]=\sum _a\pi (a|s)\sum _{s^{\prime }}p(s^{\prime }|s,a)\cdot v_{\pi }(s^{\prime })$$

步骤5：合并得到原式

4.3 贝尔曼方程的结构

v_π(s) = 即时奖励的期望 + γ × 未来价值的期望
         ───────────────   ──────────────────
              利用                探索

拆解分析：

符号	含义	作用
${\sum }_a\pi (a|s)$	策略选择动作的概率	加权所有可能动作
${\sum }_{r}p(r|s,a)\cdot r$	即时奖励期望	当前步的直接收益
$\gamma$	折扣因子	未来价值的权重
${\sum }_{s^{\prime }}p(s^{\prime }|s,a)\cdot v_{\pi }(s^{\prime })$	未来价值期望	后续状态的累积价值

4.4 贝尔曼方程的矩阵形式

向量形式：
$${\mathbf{v}}_{\pi }={\mathbf{r}}_{\pi }+\gamma {\mathbf{P}}_{\pi }{\mathbf{v}}_{\pi }$$

其中：

• ${\mathbf{v}}_{\pi }\in {\mathbb{R}}^n$：状态价值向量
• ${\mathbf{r}}_{\pi }\in {\mathbb{R}}^n$：即时奖励向量
• ${\mathbf{P}}_{\pi }\in {\mathbb{R}}^{n\times n}$：状态转移矩阵（由策略 $\pi$ 诱导）

解析解：
$${\mathbf{v}}_{\pi }=(I-\gamma {\mathbf{P}}_{\pi }{)}^{-1}{\mathbf{r}}_{\pi }$$

4.5 动作价值的贝尔曼方程

$$q_{\pi }(s,a)=\sum _{r}p(r|s,a)\cdot r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)\cdot v_{\pi }(s^{\prime })$$

或者：
$$q_{\pi }(s,a)=r(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)\sum _{a^{\prime }}\pi (a^{\prime }|s^{\prime })\cdot q_{\pi }(s^{\prime },a^{\prime })$$

---

5. 求解贝尔曼方程

5.1 方法一：解析解（Analytical Solution）

适用场景：状态空间小（$n<100$）

$${\mathbf{v}}_{\pi }=(I-\gamma {\mathbf{P}}_{\pi }{)}^{-1}{\mathbf{r}}_{\pi }$$

5.2 方法二：迭代法（Iterative Method）

迭代公式：
$$v_{k+1}={\mathbf{r}}_{\pi }+\gamma {\mathbf{P}}_{\pi }{v}_k$$

算法流程：

# 策略评估（Policy Evaluation）
初始化: v_0(s) = 0, ∀s
重复:
    for s in S:
        v_{k+1}(s) = Σ_a π(a|s) [r(s,a) + γ Σ_s' P(s'|s,a) v_k(s')]
    k += 1
直到: ||v_{k+1} - v_k|| < θ

收敛性证明：

定义误差：${\delta }_k=v_k-v_{\pi }$

$$\begin{array}{rl}\Vert {\delta }_{k+1}\Vert & =\Vert v_{k+1}-v_{\pi }\Vert \\ & =\Vert \gamma {\mathbf{P}}_{\pi }{v}_k+{\mathbf{r}}_{\pi }-\gamma {\mathbf{P}}_{\pi }{v}_{\pi }-{\mathbf{r}}_{\pi }\Vert \\ & =\gamma \Vert {\mathbf{P}}_{\pi }(v_k-v_{\pi })\Vert \\ & =\gamma \Vert {\mathbf{P}}_{\pi }{\delta }_k\Vert \\ & \le \gamma \Vert {\delta }_k\Vert \end{array}$$

因为 $\gamma <1$，所以 ${\delta }_k\to 0$。

5.3 示例：简单MDP

状态空间： S = { s 1 , s 2 } \mathcal{S} = \{s_1, s_2\} S={s1​,s2​}

策略 $\pi$：

• $s_1$: 总是选择动作 $a_1$
• $s_2$: 总是选择动作 $a_2$

状态转移：
$$P(s_1|s_1,a_1)=0.5,P(s_2|s_1,a_1)=0.5$$
$$P(s_1|s_2,a_2)=0,P(s_2|s_2,a_2)=1$$

奖励：
$$r(s_1,a_1)=5,r(s_2,a_2)=10$$

折扣因子：$\gamma =0.9$

贝尔曼方程：
$$v(s_1)=5+0.9\times [0.5\times v(s_1)+0.5\times v(s_2)]$$
$$v(s_2)=10+0.9\times v(s_2)$$

求解：
$$v(s_2)=\frac{10}{1-0.9}=100$$
$$v(s_1)=5+0.45\times v(s_1)+0.45\times 100$$
$$0.55\times v(s_1)=50$$
$$v(s_1)\approx 90.9$$

---

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

6.1 最优策略

策略的偏序关系：

策略 ${\pi }_1$ 优于策略 ${\pi }_2$，记作 ${\pi }_1\ge {\pi }_2$，当且仅当：
$$v_{{\pi }_1}(s)\ge v_{{\pi }_2}(s),\forall s\in \mathcal{S}$$

最优策略 ${\pi }^{\ast }$：
$$v_{{\pi }^{\ast }}(s)\ge v_{\pi }(s),\forall s\in \mathcal{S},\forall \pi$$

最优状态价值：
$$v^{\ast }(s)\doteq \underset{\pi }{\max }{v}_{\pi }(s)$$

最优动作价值：
$$q^{\ast }(s,a)\doteq \underset{\pi }{\max }{q}_{\pi }(s,a)$$

6.2 最优策略的性质

定理1：最优策略一定存在。

定理2：最优策略可能不唯一，但最优价值函数唯一。

定理3：最优策略可以是确定性的。

定理4：最优策略满足：
$${\pi }^{\ast }(a|s)=\{\begin{array}{ll}1& \text{if }a=\arg {\max }_{a^{\prime }}{q}^{\ast }(s,a^{\prime })\\ 0& \text{otherwise}\end{array}$$

6.3 贝尔曼最优方程（BOE）

状态价值的BOE：
$$v^{\ast }(s)=\underset{a}{\max }\left[r(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)\cdot v^{\ast }(s^{\prime })\right]$$

动作价值的BOE：
$$q^{\ast }(s,a)=r(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)\cdot \underset{a^{\prime }}{\max }{q}^{\ast }(s^{\prime },a^{\prime })$$

关系：
$$v^{\ast }(s)=\underset{a}{\max }{q}^{\ast }(s,a)$$
$$q^{\ast }(s,a)=r(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)\cdot v^{\ast }(s^{\prime })$$

6.4 BOE与贝尔曼方程的区别

特性	贝尔曼方程 (BE)	贝尔曼最优方程 (BOE)
策略	给定策略 $\pi$	最优策略 ${\pi }^{\ast }$
选择动作	按 $\pi (a|s)$ 加权	${\max }_a$ 选择最优
方程类型	线性方程组	非线性方程组
求解难度	简单（迭代收敛）	困难（需要优化）

对比：

贝尔曼方程:
v_π(s) = Σ_a π(a|s) [r(s,a) + γ Σ_s' P(s'|s,a) v_π(s')]
         ────────────────────────────────────────
                 按策略π加权平均

贝尔曼最优方程:
v*(s) = max_a [r(s,a) + γ Σ_s' P(s'|s,a) v*(s')]
        ────────────────────────────────────
              选择最优动作

6.5 求解BOE的方法

6.5.1 价值迭代（Value Iteration）

初始化: v_0(s) = 0, ∀s
重复:
    for s in S:
        v_{k+1}(s) = max_a [r(s,a) + γ Σ_s' P(s'|s,a) v_k(s')]
直到: ||v_{k+1} - v_k|| < θ

# 提取最优策略
for s in S:
    π*(s) = argmax_a [r(s,a) + γ Σ_s' P(s'|s,a) v*(s')]

6.5.2 策略迭代（Policy Iteration）

初始化: π_0 为任意策略
重复:
    # 策略评估
    求解 v_π_k

    # 策略改进
    π_{k+1}(s) = argmax_a [r(s,a) + γ Σ_s' P(s'|s,a) v_π_k(s')]

直到: π_{k+1} = π_k

---

7. 最优策略与价值函数的关系

7.1 从最优价值推导最优策略

已知 $v^{\ast }(s)$，求 ${\pi }^{\ast }(a|s)$：

$${\pi }^{\ast }(a|s)=\{\begin{array}{ll}1& \text{if }a\in \arg {\max }_{a^{\prime }}{q}^{\ast }(s,a^{\prime })\\ 0& \text{otherwise}\end{array}$$

其中：
$$q^{\ast }(s,a)=r(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)\cdot v^{\ast }(s^{\prime })$$

已知 $q^{\ast }(s,a)$，求 ${\pi }^{\ast }(a|s)$：

$${\pi }^{\ast }(a|s)=\{\begin{array}{ll}1& \text{if }a=\arg {\max }_{a^{\prime }}{q}^{\ast }(s,a^{\prime })\\ 0& \text{otherwise}\end{array}$$

8. 强化学习训练的目标

1. 学习最优策略 π*，使得在与环境
2. 持续交互中，获得最大的长期累积奖励

数学表达：
$${\pi }^{\ast }=\arg \underset{\pi }{\max }{\mathbb{E}}_{\pi }\left[\sum _{t=0}^{\infty }{\gamma }^t{R}_{t+1}\right]$$

8.2 具体目标

1. 学习最优策略 ${\pi }^{\ast }$

   • 定义智能体在每个状态下应采取的最优动作
   • 可以是确定性或随机性策略

2. 最大化累积奖励

   • 不是追求单步即时奖励最大
   • 而是长期累积奖励（带折扣）最大

3. 理解环境

   • 基于模型（Model-Based）：学习 $P(s^{\prime }|s,a)$ 和 $r(s,a)$
   • 无模型（Model-Free）：直接学习 $v_{\pi }(s)$ 或 $q_{\pi }(s,a)$

4. 平衡探索与利用

   • 探索（Exploration）：尝试未知动作，发现更优策略
   • 利用（Exploitation）：选择已知最优动作，获取高奖励

5. 泛化到未见状态

   • 在训练中未遇到的状态也能做出合理决策
   • 通过函数逼近（神经网络）实现

8.3 训练流程

开始
  ↓
初始化策略 π
  ↓
┌──────────────────┐
│ 与环境交互        │
│  - 观测状态 s     │
│  - 选择动作 a~π  │
│  - 获得奖励 r     │
│  - 转移到 s'      │
└──────────────────┘
  ↓
更新策略/价值函数
  ↓
评估性能
  ↓
是否收敛? ─No─→ 返回交互
  ↓Yes
输出最优策略 π*

9. 贝尔曼方程的应用

9.1 策略评估（Policy Evaluation）

问题：给定策略 $\pi$，计算 $v_{\pi }(s)$

方法：迭代求解贝尔曼方程
$$v_{k+1}(s)=\sum _a\pi (a|s)\left[r(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)v_k(s^{\prime })\right]$$

9.2 策略改进（Policy Improvement）

问题：已知 $v_{\pi }(s)$，改进策略

方法：贪心选择
$${\pi }^{\prime }(s)=\arg \underset{a}{\max }\left[r(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)v_{\pi }(s^{\prime })\right]$$

定理（策略改进定理）：
$$v_{{\pi }^{\prime }}(s)\ge v_{\pi }(s),\forall s$$

9.3 动态规划（Dynamic Programming）

策略迭代：

π_0 → 评估 → v_π_0 → 改进 → π_1 → 评估 → v_π_1 → ... → π*

价值迭代：

v_0 → 最大化 → v_1 → 最大化 → v_2 → ... → v* → 提取 → π*

9.4 时序差分学习（TD Learning）

无需模型的贝尔曼方程更新：
$$v(s)\leftarrow v(s)+\alpha [r+\gamma v(s^{\prime })-v(s)]$$

其中 $r+\gamma v(s^{\prime })$ 是贝尔曼目标（Bellman Target）。

---

参考资料

• Sutton & Barto - Reinforcement Learning: An Introduction (Chapter 3-4)
• David Silver - UCL强化学习课程 Lecture 2-3
• 动手学强化学习 - 第4章
• Bellman, R. (1957) - Dynamic Programming
• 贝尔曼方程解析