强化学习的数学原理（二）：贝尔曼公式（笔记整理版）
贝尔曼方程笔记整理
一、基本过程与定义
1. 单步过程 (A single step process) $$S_t \xrightarrow{A_t} R_{t+1}, S_{t+1}$$
- $t, t+1$: 离散时间步 (discrete time instances)。
- $S_t$: 状态
- $A_t$: 动作
- $R_{t+1}$: 奖励
- $S_{t+1}$: 下一状态
此过程由以下概率分布所决定：
- $S_t \to A_t$ 由策略决定: $\pi(A_t=a | S_t=s)$
- $S_t, A_t \to R_{t+1}$ 由环境动态决定: $p(R_{t+1}=r | S_t=s, A_t=a)$
- $S_t, A_t \to S_{t+1}$ 由环境动态决定: $p(S_{t+1}=s’ | S_t=s, A_t=a)$
2. 多步轨迹 (Multi-step trajectory) $$S_t \xrightarrow{A_t} R_{t+1}, S_{t+1} \xrightarrow{A_{t+1}} R_{t+2}, S_{t+2} \xrightarrow{A_{t+2}} \dots$$
3. 折扣回报 (The discounted return) $$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots$$ 注：$G_t, R_{t+1}, \dots$ 均为随机变量。
二、价值函数
1. 状态价值 (State Value)
- 定义: 状态价值是回报 $G_t$ 的期望。 $$V_{\pi}(s) = E[G_t | S_t = s]$$
- 它是状态 $s$ 的函数。
- 它基于策略 $\pi$。对于不同的策略，状态价值可能不同。
- 状态价值越大，策略越好。
- 回报与状态价值的关系: 回报是一条轨迹的累积奖励，状态价值是多个轨迹对应回报的期望。
2. 动作价值 (Action Value)
- 我们为什么关心动作价值？ 因为我们想知道哪个动作更好。
- 定义: $$q_{\pi}(s, a) = E[G_t | S_t=s, A_t=a]$$
- $q_{\pi}(s, a)$ 是状态-动作对 $(s,a)$ 的函数，并依赖于策略 $\pi$。
三、贝尔曼方程推导
从状态价值的定义出发： $$V_{\pi}(s) = E[G_t | S_t=s]$$根据回报的递归性 $G_t = R_{t+1} + \gamma G_{t+1}$，可得：$$V_{\pi}(s) = E[R_{t+1} + \gamma G_{t+1} | S_t=s] = E[R_{t+1} | S_t=s] + \gamma E[G_{t+1} | S_t=s]$$
1. 第一部分：即时奖励的均值 (The mean of immediate rewards) $$E[R_{t+1} | S_t=s] = \sum_{a}\pi(a|s) E[R_{t+1}|S_t=s, A_t=a] = \sum_a \pi(a|s) \sum_r p(r|s,a) r$$
2. 第二部分：未来奖励的均值 (The mean of future rewards) $$\begin{aligned} E\left[G_{t+1} \mid S_{t}=s\right] & =\sum_{s^{\prime}} E\left[G_{t+1} \mid S_{t}=s, S_{t+1}=s^{\prime}\right] P\left(s^{\prime} \mid s\right) \\ & =\sum_{s^{\prime}} E\left[G_{t+1} \mid S_{t+1}=s^{\prime}\right] P\left(s^{\prime} \mid s\right) \\ & =\sum_{s^{\prime}} V_{\pi}\left(s^{\prime}\right) P\left(s^{\prime} \mid s\right) \\ & =\sum_{s^{\prime}} V_{\pi}\left(s^{\prime}\right) \sum_{a} \pi(a \mid s) p\left(s^{\prime} \mid s, a\right) \end{aligned}$$
3. 贝尔曼方程
将上述两部分合并，得到贝尔曼方程： $$V_{\pi}(s) = \sum_a \pi(a|s) \left[ \sum_r p(r|s,a)r + \gamma \sum_{s’} V_{\pi}(s’) p(s’|s,a) \right]$$
- $\pi(a|s)$为给定的策略，求解该方程的过程称为策略评估 (policy evaluation)。
- $p(r|s,a)$ 和 $p(s’|s,a)$ 代表了动态模型。
- 基于模型 (model-based): 已知概率分布。
- 无模型 (model-free): 未知概率分布。
四、贝尔曼方程求解
1. 方程的紧凑形式 $$V_{\pi}(s) = r_{\pi}(s) + \gamma \sum_{s’} P_{\pi}(s’|s) V_{\pi}(s’)$$ 其中:
- $r_{\pi}(s) \triangleq \sum_a \pi(a|s) \sum_r p(r|s,a)r = E[R_{t+1}|S_t=s]$
- $P_{\pi}(s’|s) \triangleq \sum_a \pi(a|s) \sum_{s’} p(s’|s,a)$
2. 矩阵向量形式 (matrix-vector form) $$\vec{V_{\pi}} = \vec{r_{\pi}} + \gamma P_{\pi} \vec{V_{\pi}}$$ 其中:
- $\vec{V_{\pi}} = [V_{\pi}(s_1), \dots, V_{\pi}(s_n)]^T \in \mathbb{R}^n$
- $\vec{r_{\pi}} = [r_{\pi}(s_1), \dots, r_{\pi}(s_n)]^T \in \mathbb{R}^n$
- $P_{\pi} \in \mathbb{R}^{n \times n}$ 是状态转移矩阵，其中 $[P_{\pi}]_{ij} = P_{\pi}(s_j | s_i)$。
在基于模型的情况下，$\vec{r_{\pi}}, \gamma, P_{\pi}$ 都是已知的。
3. 求解方法
解析解 (closed-form solution) $$\vec{V_{\pi}} = (I - \gamma P_{\pi})^{-1} \vec{r}_{\pi}$$
迭代解 (iterative solution) $$\vec{V_{k+1}} = \vec{r_{\pi}} + \gamma P_{\pi} \vec{V_k}$$