biscuitの博客

1. 状态价值函数#

固定策略 $\pi$ 后，状态 $s$ 的状态价值函数（state-value function） 定义为回报的期望：

它回答：从状态 $s$ 出发，之后一直按策略 $\pi$ 行动，能得到的期望折扣回报是多少？ 价值必须带策略上标，因为同一状态用不同策略，未来回报通常不同。

2. 动作价值函数#

固定策略 $\pi$ 后，状态—动作对 $(s,a)$ 的动作价值函数（action-value function） 为：

它回答：在 $s$ 先执行动作 $a$，之后按策略 $\pi$ 行动，能得到的期望折扣回报是多少？ 如果不考虑具体动作，那么 $V^\pi(s)$ 就相当于对 $Q^\pi(s,a)$ 按策略取期望。状态价值和动作价值的关系为：

Q 比 V 更重要

$V$ 只能告诉”这个状态大概值多少分”，不能直接指导选哪个动作；$Q$ 可以在同一状态下直接比较 $Q(s,a_1),Q(s,a_2),\dots$，选最大的那个。所以决策阶段几乎都用 $Q$。

1. 状态价值的贝尔曼方程#

从状态价值函数的定义出发，先用回报递推和期望的线性性把”当前一步”和”未来”拆开：

两项分别落地，需要把 $\mathbb{E}_\pi$ 换成具体的表达式。

• 当前一步按策略 $\pi$ 选动作 $a$（乘 $\pi(a\mid s)$ ）、再取平均奖励：

• 未来项要先按 $\pi$ 选动作 $a$、再按 $p$ 转移到 $s'$，然后把条件从 $S_t=s$ 换成 $S_{t+1}=s'$：

这一步正是马尔可夫性在起作用：给定 $s'$ 之后，$G_{t+1}$ 的期望与”你从哪个 $s$ 来”无关，于是塌缩成 $V^\pi(s')$。没有马尔可夫性，这个条件替换不成立，贝尔曼方程也就写不出来。

放一块发现可以提出 $\sum_a\pi(a\mid s)$，得到状态价值的贝尔曼期望方程：

理解层次：先按 $p(s'\mid s,a)$ 加权，表示状态转移可能到不同的状态，再按 $\pi(a\mid s)$ 对动作加权，表示按策略选动作。若 $s'$ 是终止状态，约定 $V^\pi(s')=0$。

奖励的三种等价格式

$$\begin{aligned} V^\pi(s) &=\sum_a\pi(a\mid s)\Big[\bar r(s,a)+\gamma\sum_{s'}p(s'\mid s,a)V^\pi(s')\Big] & &\text{① 平均奖励（正文采用）}\\ &=\sum_a\pi(a\mid s)\sum_{s'}p(s'\mid s,a)\big[R(s,a,s')+\gamma V^\pi(s')\big] & &\text{② 转移绑定（教材常见）}\\ &=\sum_a\pi(a\mid s)\sum_{r,s'}p(r,s'\mid s,a)\big[r+\gamma V^\pi(s')\big] & &\text{③ 联合分布（最一般）} \end{aligned}$$

三者靠一条全期望公式互相换算：

$$\bar r(s,a)=\sum_{s'}p(s'\mid s,a)R(s,a,s')=\sum_r r\,p(r\mid s,a)$$

其中 $R(s,a,s')=\mathbb{E}[R_t\mid S_t=s,A_t=a,S_{t+1}=s']$。③ 最一般，不要求奖励与下一状态独立；$Q$、$v_*$、$q_*$ 的方程同理，之后正文一律用 ①。

（有的教材把“执行 $A_t$ 后得到的奖励”记作 $R_{t+1}$，回报随之写成 $G_t=R_{t+1}+\gamma R_{t+2}+\cdots$；本文沿用第一篇的 $R_t$ 记法，两者只差一位下标平移，方程形状不变。）

2. 动作价值的贝尔曼方程#

把动作也固定住，推理与上一小节完全平行：条件从 $S_t=s$ 细化为 $S_t=s,A_t=a$，未来项除了按 $p$ 转移到 $s'$，还要再按 $\pi$ 选出 $a'$：

把内层的 $\sum_{a'}\pi(a'\mid s')Q^\pi(s',a')$ 认出来——它就是 $V^\pi(s')$——方程立刻折成与 $V$ 直接相连的紧凑形式：

对第一式两边按 $\pi(a\mid s)$ 加权求和，左边恰好是 $V^\pi(s)$，右边还原出的就是上一小节的 $V$ 方程——两节推导的其实是同一个递推，$Q$ 版只是条件里多固定了一个动作。

$P$ 的形状：行是”从哪”，列是”到哪”#

第 $i$ 行就是”从 $s_i$ 出发、一步后落到各状态”的概率分布，每行之和为 $1$：

它一般不对称（$P_{ij}\ne P_{ji}$）——从 A 能到 B，不代表从 B 能到 A。

$P$ 是策略诱导的：每个元素里已经把”策略选动作”和”环境转状态”两层随机性乘好、并对动作求和，

也就是说策略选动作与环境转状态这两层随机性都被收进了 $P$ 这一个符号。

奖励向量的形状#

奖励向量同理按策略加权

（带动作的 $\bar r(s_i,a)$ 对策略求期望后记为 $\bar r(s_i)$）。（终止状态一般不放进方程组，等价于取其 $v_i=0$。）

对于奖励和动作无关的简化情形，$\bar r(s_i,a)=\bar r(s_i)$，就不必对动作求和了。

一步贝尔曼 = 一次矩阵乘法#

形状上 $(n\times n)\cdot(n\times1)=n\times1$，还是列向量。展开第 $i$ 个分量：

正好是贝尔曼方程右边那个”下一状态的折扣期望价值”。于是

形状 $(n\times1)=(n\times1)+\gamma(n\times n)(n\times1)$ 自洽。它只是把标量方程 $V^\pi(s)=\bar r(s)+\gamma\sum_{s'}p_\pi(s'\mid s)V^\pi(s')$ 竖着堆了 $n$ 遍。

求解：求逆 = 把所有时间步加起来#

移项（$I$ 与 $\gamma P$ 同形状才能相减）：

$\gamma<1$ 且 $P$ 每行和为 $1$（谱半径 $\le1$）保证 $I-\gamma P$ 可逆，理论上的精确解为

把逆矩阵展开成几何级数（Neumann 级数）$(I-\gamma P)^{-1}=I+\gamma P+\gamma^2P^2+\cdots$，代回去得：

第 $k$ 项 $\gamma^kP^kr$ 是”从各状态出发、$k$ 步后领到奖励”的期望，正好与回报 $G_t=R_t+\gamma R_{t+1}+\gamma^2R_{t+2}+\cdots$ 逐项对应。矩阵求逆就是把未来所有时间步的奖励折扣求和。 也正因为 $\gamma^k\to0$ 级数才收敛，$(I-\gamma P)^{-1}$ 才存在。

不过状态数很大时显式求逆的计算和存储代价都很高，所以矩阵求逆主要用于理论分析，实践中用下面的迭代法。

贝尔曼更新与自举#

给定价值估计 $v_k$，用它计算下一次估计：

用后继状态当前的估计来更新当前状态的估计，这种”用估计更新估计”的思想称为自举（bootstrapping）——它是后续 TD 方法的核心。

迭代策略评估#

1
输入：已知的 MDP 模型、策略 π、折扣因子 γ
2
初始化 v(s)，例如全部设为 0
3
重复：
4
    对每个非终止状态 s：
5
        v_new(s) = Σ_a π(a|s)
6
                   [r̄(s,a) + γ Σ_{s'} p(s'|s,a) v(s')]
7
    v ← v_new
8
直到 max_s |v_new(s) - v(s)| < ε
9
输出：v

在有限状态、有限动作且 $0\le\gamma<1$ 时，贝尔曼期望算子是压缩映射，迭代收敛到唯一的 $v_\pi$。该方法需要知道奖励和转移模型，属于基于模型（model-based） 的动态规划方法。

1. 最优价值函数#

在所有策略中，状态 $s$ 能达到的最大价值定义为：

$q_*(s,a)$ 表示先在 $(s,a)$ 执行动作，然后从后续状态开始采取最优行为。

2. 贝尔曼最优方程#

与期望方程的区别在于：把”按策略对动作取期望”换成”对动作取最大”。

并且 $v_*(s)=\max_{a}q_*(s,a)$。

3. 最优策略#

一旦有了 $q_*$，最优策略直接读出来——任意满足下式的策略都是最优的：

最简单的确定性贪心策略为：

在有限状态—动作空间、$\gamma<1$ 或满足适当终止条件时，最优值函数存在且唯一；但最优策略不一定唯一：若多个动作的 $q_*(s,a)$ 相同，它们都可组成最优策略。