Bellman方程与算子理论

Bellman方程是强化学习理论的基石，将递归结构引入值函数的计算，为动态规划算法提供了数学基础。

1. Bellman方程推导

1.1 策略值函数的Bellman方程

从值函数定义出发，利用马尔可夫性质：

$$\begin{array}{rl}{V}^{\pi }(s)& ={\mathbb{E}}_{\pi }\left[G_t|S_t=s\right]\\ & ={\mathbb{E}}_{\pi }\left[R_{t+1}+\gamma G_{t+1}|S_t=s\right]\\ & ={\mathbb{E}}_{\pi }\left[R_{t+1}|S_t=s\right]+\gamma {\mathbb{E}}_{\pi }\left[G_{t+1}|S_t=s\right]\end{array}$$

展开第一项：

$${\mathbb{E}}_{\pi }\left[R_{t+1}|S_t=s\right]=\sum _{a\in A}\pi (a|s)\cdot r(s,a)$$

展开第二项，需要用到全概率公式：

$${\mathbb{E}}_{\pi }\left[G_{t+1}|S_t=s\right]=\sum _{s^{\prime }\in S}\sum _{a\in A}\pi (a|s)\cdot T(s^{\prime }|s,a)\cdot {\mathbb{E}}_{\pi }\left[G_{t+1}|S_{t+1}=s^{\prime }\right]$$

最终得到Bellman策略方程：

$$\boxed{V^{\pi }(s)=\sum _{a\in A}\pi (a|s)\left[r(s,a)+\gamma \sum _{s^{\prime }\in S}T(s^{\prime }|s,a)V^{\pi }(s^{\prime })\right]}$$

1.2 最优值函数的Bellman方程

最优值函数满足：

$$\boxed{V^{\ast }(s)=\underset{a\in A}{\max }\left[r(s,a)+\gamma \sum _{s^{\prime }\in S}T(s^{\prime }|s,a)V^{\ast }(s^{\prime })\right]}$$

动作值函数形式：

$$Q^{\ast }(s,a)=r(s,a)+\gamma \sum _{s^{\prime }\in S}T(s^{\prime }|s,a)\underset{a^{\prime }\in A}{\max }{Q}^{\ast }(s^{\prime },a^{\prime })$$

2. Bellman算子

2.1 策略Bellman算子

定义为从值函数到值函数的映射：

$$(T^{\pi }V)(s)=\sum _{a\in A}\pi (a|s)\left[r(s,a)+\gamma \sum _{s^{\prime }\in S}T(s^{\prime }|s,a)V(s^{\prime })\right]$$

向量形式：

$$T^{\pi }V=r^{\pi }+\gamma P^{\pi }V$$

其中：

• $r^{\pi }\in {\mathbb{R}}^{|S|}$：策略 $\pi$ 下的期望即时奖励，$[r^{\pi }{]}_s={\sum }_a\pi (a|s)r(s,a)$
• $P^{\pi }\in {\mathbb{R}}^{|S|\times |S|}$：策略 $\pi$ 下的转移概率矩阵，$[P^{\pi }{]}_{s,s^{\prime }}={\sum }_a\pi (a|s)T(s^{\prime }|s,a)$

2.2 最优Bellman算子

$$(T^{\ast }V)(s)=\underset{a\in A}{\max }\left[r(s,a)+\gamma \sum _{s^{\prime }\in S}T(s^{\prime }|s,a)V(s^{\prime })\right]$$

向量形式：

$$T^{\ast }V=\underset{\pi }{\max }{T}^{\pi }V=\underset{a\in A}{\max }(r^a+\gamma P^{a}V)$$

3. 压缩映射定理

3.1 范数定义

使用无穷范数（最大范数）：

$$\Vert V{\Vert }_{\infty }=\underset{s\in S}{\max }|V(s)|$$

3.2 Bellman算子的压缩性

定理（Bellman算子是 $\gamma$-收缩）：对于任意两个值函数 $V,\bar{V}$，有：

$$\Vert T^{\pi }V-T^{\pi }\bar{V}{\Vert }_{\infty }\le \gamma \Vert V-\bar{V}{\Vert }_{\infty }$$

证明：

$$\begin{array}{rl}\Vert T^{\pi }V-T^{\pi }\bar{V}{\Vert }_{\infty }& =\underset{s}{\max }\left|\gamma \sum _{s^{\prime }}{P}^{\pi }(s,s^{\prime })[V(s^{\prime })-\bar{V}(s^{\prime })]\right|\\ & \le \gamma \underset{s}{\max }\sum _{s^{\prime }}{P}^{\pi }(s,s^{\prime })|V(s^{\prime })-\bar{V}(s^{\prime })|\\ & \le \gamma \underset{s}{\max }\sum _{s^{\prime }}{P}^{\pi }(s,s^{\prime })\Vert V-\bar{V}{\Vert }_{\infty }\\ & =\gamma \Vert V-\bar{V}{\Vert }_{\infty }\end{array}$$

3.3 推论

• 重复应用 $T^{\pi }$ 必收敛到唯一不动点 $V^{\pi }$
• 收敛速率：$O({\gamma }^k)$
• 类似地，$T^{\ast }$ 也是 $\gamma$-收缩

4. 收敛性分析

4.1 Banach不动点定理

定理：完备赋范空间上的压缩映射有唯一不动点。

应用：

1. $T^{\pi }$ 在 ${\mathbb{R}}^{|S|}$ 上是 $\gamma$-收缩
2. 因此 $T^{\pi }$ 有唯一不动点 $V^{\ast }$ 满足 $T^{\pi }{V}^{\ast }=V^{\ast }$
3. 从任意初始值函数 $V_0$ 出发，迭代 $V_{k+1}=T^{\pi }{V}_k$ 收敛到 $V^{\ast }$

4.2 收敛速率

引理：

$$\Vert V_k-V^{\pi }{\Vert }_{\infty }\le {\gamma }^k\Vert V_0-V^{\pi }{\Vert }_{\infty }$$

4.3 迭代值函数

算法：Value Iteration (VI)

V_0 = zeros(|S|)
for k in range(K):
    for s in S:
        V_{k+1}(s) = max_a [r(s,a) + γ Σ_{s'} T(s'|s,a) V_k(s')]

收敛条件：$\Vert V_{k+1}-V_k{\Vert }_{\infty }<ϵ$

5. 策略迭代算法

5.1 两阶段交替

策略评估：计算 $V^{{\pi }_k}$

$$V^{{\pi }_k}=(I-\gamma P^{{\pi }_k}{)}^{-1}{r}^{{\pi }_k}$$

或迭代求解：

$$V^{k+1}=T^{{\pi }_k}{V}^k$$

策略改进：贪心选择

$${\pi }_{k+1}(s)=\arg \underset{a}{\max }\left[r(s,a)+\gamma \sum _{s^{\prime }}T(s^{\prime }|s,a)V^{{\pi }_k}(s^{\prime })\right]$$

5.2 策略改进定理

定理：设 ${\pi }^{\prime }$ 是基于 $V^{\pi }$ 贪心改进的策略，则：

$$V^{{\pi }^{\prime }}(s)\ge V^{\pi }(s),\forall s\in S$$

且至少有一个状态使不等式严格成立。

证明：

$$V^{{\pi }^{\prime }}(s)=\underset{a}{\max }{Q}^{\pi }(s,a)\ge Q^{\pi }(s,\pi (s))=V^{\pi }(s)$$

5.3 收敛性保证

定理：有限状态空间MDP的策略迭代在有限步内收敛到最优策略。

单调性：

$$V^{{\pi }_0}\le V^{{\pi }_1}\le \cdots \le V^{\ast },\underset{k\to \infty }{\lim }{V}^{{\pi }_k}=V^{\ast }$$

6. 广义策略迭代

6.1 GPI框架

策略迭代和值迭代是**广义策略迭代（GPI）**的特殊情况：

                    ┌─────────────────────────────────┐
                    │      最优性（贪婪）               │
                    │   V = T*V 或 π = greedy(V)      │
                    └─────────────────────────────────┘
                                ▲
                                │
                                │
┌─────────────────────────────────┐
│       评估（预测）               │
│   V = T^πV 或 π = E(V)         │
└─────────────────────────────────┘

6.2 同步与异步更新

类型	更新方式	收敛性
同步	所有状态同时更新	保证收敛
异步	单个状态更新	需满足异步收敛条件

7. 矩阵形式求解

7.1 解析解

对于线性方程组 $V^{\pi }=r^{\pi }+\gamma P^{\pi }{V}^{\pi }$：

$$V^{\pi }=(I-\gamma P^{\pi }{)}^{-1}{r}^{\pi }$$

7.2 矩阵求逆的复杂性

• 直接求逆：$O(|S{|}^3)$
• 迭代求解：$O(|S{|}^2\cdot \text{迭代次数})$

7.3 Sherman-Morrison公式

对于稀疏转移矩阵，可使用Woodbury矩阵恒等式加速：

$$(I-\gamma P^{\pi }{)}^{-1}=I+\gamma (I-\gamma P^{\pi }{)}^{-1}{P}^{\pi }$$

8. 备份图视角

8.1 Bellman备份

当前状态 s                    下一状态 s'
     │                              ▲
     ▼                              │
┌─────────────┐              ┌─────────────┐
│  选择动作 a │              │  值函数 V   │
│  π(a|s)    │              │             │
└─────────────┘              └─────────────┘
     │                              │
     ▼                              │
┌─────────────┐                      │
│  即时奖励   │                      │
│  r(s,a)    │                      │
└─────────────┘                      │
     │                              │
     └──────────────────────────────┘

8.2 备份运算

$$T^{\pi }V(s)=\sum _a\pi (a|s)\sum _{s^{\prime }}T(s^{\prime }|s,a)[r(s,a)+\gamma V(s^{\prime })]$$

9. 与深度学习的联系

9.1 神经网络近似

深度强化学习用神经网络近似Bellman方程中的值函数：

• DQN：$Q(s,a)\approx \theta$ 参数化
• 经验回放：存储 $(s,a,r,s^{\prime })$ 样本
• 目标网络：稳定Bellman更新

9.2 时序差分学习

$$V(S_t)\leftarrow V(S_t)+\alpha [R_{t+1}+\gamma V(S_{t+1})-V(S_t)]$$

其中 $R_{t+1}+\gamma V(S_{t+1})$ 是 $V(S_t)$ 的TD目标。

10. 扩展形式

10.1 平均奖励Bellman方程

对于$\gamma =1$的设置：

$$h^{\pi }(s)=\sum _a\pi (a|s)\left[r(s,a)-{\bar{r}}^{\pi }+\sum _{s^{\prime }}T(s^{\prime }|s,a)h^{\pi }(s^{\prime })\right]$$

其中 ${\bar{r}}^{\pi }$ 是平均奖励，$h^{\pi }$ 是相对值函数。

10.2 softmax-Bellman方程

对于柔性策略：

$$V^{\pi }(s)=\log \sum _a\exp \left(\frac{1}{\tau }[r(s,a)+\gamma \sum _{s^{\prime }}T(s^{\prime }|s,a)V^{\pi }(s^{\prime })]\right)$$

其中 $\tau$ 是温度参数。

11. 参考文献

---

相关主题：MDP数学基础 | 值函数近似理论 | PPO全局收敛性理论