贝尔曼方程

概述

贝尔曼方程（Bellman Equation）是强化学习核心理论，它建立了价值函数在不同时刻之间的递归关系。¹

“贝尔曼方程本质上是说：当前状态的价值取决于能够直接获得的奖励，加上从当前状态转移到未来状态的价值。“

回报的递归形式

从定义出发：

$$\begin{array}{rl}{G}_t& =R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots \\ & =R_{t+1}+\gamma (R_{t+2}+\gamma R_{t+3}+\cdots )\\ & =R_{t+1}+\gamma G_{t+1}\end{array}$$

这就是回报的递归定义，也是贝尔曼方程的基础。

状态价值函数的贝尔曼方程

标准形式

$$V^{\pi }(s)={\mathbb{E}}_{\pi }[R_{t+1}+\gamma V^{\pi }(S_{t+1})|S_t=s]$$

展开为对动作和下一状态的期望：

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

期望形式

利用期望的线性性质：

$$V^{\pi }(s)=\sum _{a,s^{\prime }}\pi (a|s)\mathcal{P}(s^{\prime }|s,a)\mathcal{R}(s,a,s^{\prime })+\gamma \sum _{a,s^{\prime }}\pi (a|s)\mathcal{P}(s^{\prime }|s,a)V^{\pi }(s^{\prime })$$

写成紧凑形式：

$$V^{\pi }={\mathcal{R}}^{\pi }+\gamma {\mathcal{P}}^{\pi }{V}^{\pi }$$

其中：

• ${\mathcal{R}}^{\pi }(s)={\sum }_a\pi (a|s){\sum }_{s^{\prime }}\mathcal{P}(s^{\prime }|s,a)\mathcal{R}(s,a,s^{\prime })$
• ${\mathcal{P}}^{\pi }(s^{\prime }|s)={\sum }_a\pi (a|s)\mathcal{P}(s^{\prime }|s,a)$

动作价值函数的贝尔曼方程

标准形式

$$Q^{\pi }(s,a)={\mathbb{E}}_{\pi }[R_{t+1}+\gamma Q^{\pi }(S_{t+1},A_{t+1})|S_t=s,A_t=a]$$

展开：

$$Q^{\pi }(s,a)=\sum _{s^{\prime }\in \mathcal{S}}\mathcal{P}(s^{\prime }|s,a)\left[\mathcal{R}(s,a,s^{\prime })+\gamma \sum _{a^{\prime }\in \mathcal{A}}\pi (a^{\prime }|s^{\prime })Q^{\pi }(s^{\prime },a^{\prime })\right]$$

Q函数与V函数的关系

$$V^{\pi }(s)=\sum _{a\in \mathcal{A}}\pi (a|s)Q^{\pi }(s,a)={\mathbb{E}}_a[Q^{\pi }(s,a)]$$ $$Q^{\pi }(s,a)=\mathcal{R}(s,a)+\gamma \sum _{s^{\prime }}\mathcal{P}(s^{\prime }|s,a)V^{\pi }(s^{\prime })$$

贝尔曼最优方程

最优价值函数

最优状态价值函数：

$$V^{\ast }(s)=\underset{\pi }{\max }{V}^{\pi }(s)$$

最优动作价值函数：

$$Q^{\ast }(s,a)=\underset{\pi }{\max }{Q}^{\pi }(s,a)$$

贝尔曼最优方程

对于最优策略，有：

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

紧凑形式

$$V^{\ast }=\underset{\pi }{\max }{\mathcal{R}}^{\pi }+\gamma {\mathcal{P}}^{\pi }{V}^{\ast }$$

最优策略

从贝尔曼最优方程可以导出最优策略：

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

对于存在多个最优动作的情况，可以均匀随机分配概率。

方程的矩阵形式

对于有限状态MDP，贝尔曼方程可以写成矩阵形式：

$$V^{\pi }={\mathcal{R}}^{\pi }+\gamma {\mathcal{P}}^{\pi }{V}^{\pi }$$

重排得：

$$(I-\gamma {\mathcal{P}}^{\pi })V^{\pi }={\mathcal{R}}^{\pi }$$

因此：

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

直接求解需要矩阵求逆，时间复杂度 $O(S^3)$，实际中通常使用迭代方法。

贝尔曼算子

贝尔曼算子定义

定义贝尔曼期望算子 ${\mathcal{T}}^{\pi }$：

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

定义贝尔曼最优算子 ${\mathcal{T}}^{\ast }$：

$$({\mathcal{T}}^{\ast }V)(s)=\underset{a}{\max }\sum _{s^{\prime }}\mathcal{P}(s^{\prime }|s,a)[\mathcal{R}(s,a,s^{\prime })+\gamma V(s^{\prime })]$$

算子的性质

性质	${\mathcal{T}}^{\pi }$	${\mathcal{T}}^{\ast }$
单调性	${\mathcal{T}}^{\pi }(V_1)\le {\mathcal{T}}^{\pi }(V_2)$ 当 $V_1\le V_2$	同样成立
压缩性	$\	\mathcal{T}^\pi(V_1) - \mathcal{T}^\pi(V_2)\
唯一不动点	$V^{\pi }={\mathcal{T}}^{\pi }{V}^{\pi }$	$V^{\ast }={\mathcal{T}}^{\ast }{V}^{\ast }$

压缩性意味着重复应用贝尔曼算子会以几何级数速度收敛：

$$\begin{gathered} |({\mathcal{T}}^{\pi }{)}^{n}V-V^{\pi } \\ {|}_{\infty }\le {\gamma }^n \\ |V-V^{\pi } \\ {|}_{\infty } \end{gathered}$$

求解方法

同步 vs 异步迭代

方法	描述	复杂度
同步	所有状态同时更新	高（需要存储两个价值表）
异步	每次只更新一个或部分状态	低

原地更新（In-place）

原地更新可以加速收敛：

for s in states:
    V[s] = max_a sum_{s'} P[s,a,s'] * (R[s,a,s'] + gamma * V[s'])

原地更新的收敛性依赖于拓扑顺序或随机顺序的多次遍历。

示例：Grid World

问题设置

2x2 网格世界：
+---+---+
| 0 | 1 |
+---+---+
| 2 | 3 |  (目标状态)
+---+---+

转移：确定性（智能体尝试移动，实际移到相邻格子）
奖励：到达目标+1，其他-0.1
折扣：γ = 0.9

贝尔曼方程验证

对于状态0（最左上角）：

$$V(s=0)=\underset{a}{\max }\sum _{s^{\prime }}P(s^{\prime }|0,a)[R(0,a,s^{\prime })+0.9V(s^{\prime })]$$

假设右移动作（a=right）：

$$\begin{array}{rl}V(0)& =0.9\cdot V(1)+(-0.1)\text{（如果没到达目标）}\\ & =0.9\cdot 0.8+(-0.1)=0.62\text{（假设）}\end{array}$$

Python实现

import numpy as np
 
class SimpleGridWorld:
    """演示贝尔曼方程的简单环境"""
    
    def __init__(self, gamma=0.9):
        self.gamma = gamma
        self.n_states = 4
        self.n_actions = 4
        self.target = 3
        
        # 转移概率和奖励
        self.P = {
            # (s, a) -> [(prob, next_s, reward), ...]
            (0, 0): [(1.0, 0, -0.1)],  # up: stay
            (0, 1): [(1.0, 2, -0.1)],  # down
            (0, 2): [(1.0, 0, -0.1)],  # left: stay
            (0, 3): [(1.0, 1, -0.1)],  # right
            (1, 0): [(1.0, 1, -0.1)],  # up: stay
            (1, 1): [(1.0, 3, 1.0)],   # down: reach target!
            (1, 2): [(1.0, 0, -0.1)], # left
            (1, 3): [(1.0, 1, -0.1)], # right: stay
            (2, 0): [(1.0, 0, -0.1)], # up
            (2, 1): [(1.0, 2, -0.1)], # down: stay
            (2, 2): [(1.0, 2, -0.1)],# left: stay
            (2, 3): [(1.0, 3, 1.0)],  # right: reach target!
            (3, 0): [(1.0, 3, 0.0)],  # up: terminal
            (3, 1): [(1.0, 3, 0.0)],  # down: terminal
            (3, 2): [(1.0, 3, 0.0)],  # left: terminal
            (3, 3): [(1.0, 3, 0.0)],  # right: terminal
        }
    
    def bellman_update(self, V, s):
        """对状态s应用一次贝尔曼最优算子"""
        max_q = float('-inf')
        for a in range(self.n_actions):
            q = 0
            for prob, next_s, reward in self.P[(s, a)]:
                q += prob * (reward + self.gamma * V[next_s])
            max_q = max(max_q, q)
        return max_q
    
    def solve(self, theta=1e-6, max_iter=1000):
        """迭代求解最优价值函数"""
        V = np.zeros(self.n_states)
        
        for _ in range(max_iter):
            delta = 0
            for s in range(self.n_states):
                if s == self.target:
                    continue  # 终止状态的价值为0
                new_v = self.bellman_update(V, s)
                delta = max(delta, abs(new_v - V[s]))
                V[s] = new_v
            
            if delta < theta:
                break
        
        return V
    
    def extract_policy(self, V):
        """从价值函数提取贪婪策略"""
        pi = np.zeros((self.n_states, self.n_actions))
        for s in range(self.n_states):
            q_values = []
            for a in range(self.n_actions):
                q = 0
                for prob, next_s, reward in self.P[(s, a)]:
                    q += prob * (reward + self.gamma * V[next_s])
                q_values.append(q)
            best_a = np.argmax(q_values)
            pi[s, best_a] = 1.0
        return pi
 
 
env = SimpleGridWorld()
V = env.solve()
pi = env.extract_policy(V)
 
print("最优价值函数:")
print(f"V = {V}")
print("\n最优策略 (0:up, 1:down, 2:left, 3:right):")
for s in range(4):
    action_names = ['up', 'down', 'left', 'right']
    print(f"  State {s}: {action_names[np.argmax(pi[s])]}")

输出

最优价值函数:
V = [0.621 0.899 0.621 0.   ]

最优策略 (0:up, 1:down, 2:left, 3:right):
  State 0: right
  State 1: down
  State 2: right
  State 3: terminal

可以看到：

• 状态3（目标）的价值为0
• 状态1的价值最高（0.899），因为向下一步就能到达目标
• 最优策略指向目标方向

备份图（Backup Diagram）

贝尔曼方程可以用备份图直观表示：

状态价值的备份

          s
          │
    ┌─────┴─────┐
    │ π(a|s)    │
    └─┬───────┬─┘
      │       │
      ▼       ▼
     a=0     a=1
      │       │
  ┌───┴───┐ ┌─┴───────┐
  │P(s'|s,0)│ │P(s'|s,1)│
  └─┬───┬─┘ └─┬─────┬─┘
    ▼   ▼     ▼     ▼
   s'  s'    s'    s'
    \   │     │    │
     R+γV'  R+γV'  R+γV'
       \     │    /
        └──+V(s)+┘

动作价值的备份

    s ──a──▶ s'
     \      │
      \     R+γ Σ π(a'|s')Q(s',a')
       \    │
        └─+Q(s,a)

参考

---

后续主题

• 动态规划：利用贝尔曼方程求解最优策略
• Q-Learning：无模型环境下的贝尔曼方程应用
• MDP基础：回顾马尔可夫决策过程

Footnotes

1. Sutton & Barto, “Reinforcement Learning: An Introduction”, 2nd Edition, 2018, Chapter 3-4 ↩