本文章没有找到对应的语言版本

零、写在前面

之前已经把无限未来压缩成贝尔曼方程。例如，固定策略的价值满足

$$ v_\pi(s) =\sum_{a,s'}\pi(a\mid s)p(s'\mid s,a) \left[r(s,a,s')+\gamma v_\pi(s')\right]. $$

在两格世界中，我们可以把它写成两条联立方程并直接解出答案。但状态和行动一多，显式列方程、再交给通用线性或非线性求解器，就很快不再实际。

这次我们换一个角度：不一次性解出整个方程组，而是从任意价值估计出发，反复做局部贝尔曼更新，直到价值函数不再显著变化。

$$ \text{贝尔曼方程（价值必须满足的关系）} \quad\Longrightarrow\quad \text{动态规划（逐步逼近该关系的算法）}. $$

一、动态规划法和策略评估

强化学习中有两类任务：

任务 问题 代表算法
策略评估（policy evaluation） 给定策略 $\pi$，它的 $v_\pi$、$q_\pi$ 是多少？ 迭代策略评估
策略控制（policy control） 如何调整策略，直到得到最优策略？ 策略迭代、价值迭代

最终目的当然是策略控制，但策略评估是重要的中间能力：如果连“当前策略有多好”都不能算，就没有可靠依据判断怎样改进。

1.1 从贝尔曼方程到更新式

回顾状态价值的贝尔曼期望方程：

$$ v_\pi(s) =\sum_{a,s'}\pi(a\mid s)p(s'\mid s,a) \left[r(s,a,s')+\gamma v_\pi(s')\right]. \tag{4.1} $$

它的左右两边都是真实的 $v_\pi$。动态规划不假装已经知道这个真值，而是从一个估计 $V_0$ 开始。把右侧的真实未来价值替换为第 $k$ 轮估计，得到：

$$ \boxed{ V_{k+1}(s) =\sum_{a,s'}\pi(a\mid s)p(s'\mid s,a) \left[r(s,a,s')+\gamma V_k(s')\right] }. \tag{4.2} $$

这就是迭代策略评估（iterative policy evaluation）的核心更新式。

式 (4.2) 的部分 含义
$V_k(s')$ 取已经拥有的“下一状态未来价值”估计
$r+\gamma V_k(s')$ 组成该一步分支的即时奖励加折现未来
$\pi p$ 对策略随机性和环境随机性求期望
$V_{k+1}(s)$ 用这个期望覆盖/写入当前状态的新估计

用估计值改善另一个估计值的做法称为自举（bootstrapping）。这并不等于“凭空猜答案”：模型给出了正确的一步奖励和转移关系，反复传播后，离奖励近的信息会逐渐传到更远的状态。

这里写的是递推自底向上计算，当然我们也可以写成记忆化搜索，自上而下计算。

1.2 两格世界：第一次迭代到底做了什么

我们先回到最简单的两格世界：

image.png

策略是随机的：Left、Right 各以 \(0.5\) 的概率选择；折现率 $\gamma=0.9$。转移是确定的，因此可写 $s'=f(s,a)$，式 (4.2) 不再需要对全部候选 $s'$ 求和：

$$ \boxed{ V_{k+1}(s) =\sum_a\pi(a\mid s) \left[ r(s,a,f(s,a))+\gamma V_k(f(s,a)) \right] }. \tag{4.3} $$

从 $V_0(L1)=V_0(L2)=0$ 开始，第一次更新是：

$$ \begin{aligned} V_1(L1) &=0.5[-1+0.9V_0(L1)]+0.5[1+0.9V_0(L2)]\\ &=0,\\[4pt] V_1(L2) &=0.5[0+0.9V_0(L1)]+0.5[-1+0.9V_0(L2)]\\ &=-0.5. \end{aligned} $$

这一步很值得停下来理解：

  • L1 的两种即时奖励 $-1$ 与 $+1$ 恰好抵消，所以第一次估计为 0；
  • L2 的两种即时奖励 $0$ 与 $-1$ 平均后为 $-0.5$；
  • 这还不是最终价值，因为 $V_0$ 把所有未来都当成 0。

下一轮使用 $V_1$，就会把“从 L1 到 L2 后经常撞墙”的负面未来传播回 L1：

$$ V_2(L1)=-0.225,\qquad V_2(L2)=-0.725. $$

不断重复后，估计会收敛到之前通过联立方程得到的真值：

$$ v_\pi(L1)=-2.25,\qquad v_\pi(L2)=-2.75. $$

我们把上式写成代码：

from copy import deepcopy

V = {'L1': 0.0, "L2": 0.0}
new_V = V.copy()

cnt = 0
while True:
    new_V['L1'] = 0.5 * (-1 + 0.9 * V['L1']) + 0.5 * (1 + 0.9 * V['L2'])
    new_V['L2'] = 0.5 * (0 + 0.9 * V['L1']) + 0.5 * (-1 + 0.9 * V['L2'])

    delta = abs(new_V['L1'] - V['L1'])
    delta = max(delta, abs(new_V['L2'] - V['L2']))
    V = deepcopy(new_V)

    cnt += 1
    if delta < 0.0001:
        print(V)
        print(cnt)
        break

运行得到：

{'L1': -2.249167525908671, 'L2': -2.749167525908671}
76

收敛值和我们之前推导值一样。

1.3 原地修改写法

只保留一个字典 V，更新 L1 后立刻覆盖它；更新 L2 时马上使用新 L1：

t = 0.5 * (-1 + 0.9 * V['L1']) + 0.5 * (1 + 0.9 * V['L2'])
V['L1'] = t

t = 0.5 * (0 + 0.9 * V['L1']) + 0.5 * (-1 + 0.9 * V['L2'])
V['L2'] = t

于是就有如下代码：

V = {'L1': 0.0, 'L2': 0.0}

cnt = 0
while True:
    t = 0.5 * (-1 + 0.9 * V['L1']) + 0.5 * (1 + 0.9 * V['L2'])
    delta = abs(t - V['L1'])
    V['L1'] = t

    t = 0.5 * (0 + 0.9 * V['L1']) + 0.5 * (-1 + 0.9 * V['L2'])
    delta = max(delta, abs(t - V['L2']))
    V['L2'] = t

    cnt += 1
    if delta < 0.0001:
        print(V)
        print(cnt)
        break

运行得到：

{'L1': -2.2493782177156936, 'L2': -2.7494201578106514}
60

我们发现第二种写法收敛的更快，原因是第二种写法相当于 新状态利用了新的信息，所以新信息传播的更快，从而使得收敛速度变快。

二、解决更大的问题

我们从二格世界扩展到 3x4 世界。

image.png

问题设定如下：

  1. 代理可以向上、下、左、右移动；
  2. 灰色格是墙，网格外也视为墙；撞墙后停留在原格，奖励为 0；
  3. 进入右上角苹果格得到 +1，进入炸弹格得到 -1；
  4. 转移是确定的；
  5. 只有拿到苹果后回合结束，因此目标格的后续价值规定为 0；炸弹格只是进入时给出 -1，不会终止回合。

奖励标签不是终止标签。
+1 与 -1 都由 next_state 所在格决定；炸弹格 (1,3) 不是终止状态，代理可以从那里离开，也可以再次进入。

目标格价值为 0，不等于奖励为 0。
从相邻状态进入目标格的一步奖励仍然是 +1。把 $V(\mathrm{goal})$ 设为 0 表达的是“到达后没有更多未来收益”。

4.2.1 GridWorld类实现

写一个 GridWorld 辅助类，保存 3x4 世界的状态，以及一些更新操作：

import numpy as np
import common.gridworld_render as render_helper


class GridWorld:
    def __init__(self):
        self.action_space = [0, 1, 2, 3]
        self.action_meaning = {
            0: "UP",
            1: "DOWN",
            2: "LEFT",
            3: "RIGHT",
        }

        self.reward_map = np.array(
            [[0, 0, 0, 1.0],
             [0, None, 0, -1.0],
             [0, 0, 0, 0]]
        )
        self.goal_state = (0, 3)
        self.wall_state = (1, 1)
        self.start_state = (2, 0)
        self.agent_state = self.start_state

    @property
    def height(self):
        return len(self.reward_map)

    @property
    def width(self):
        return len(self.reward_map[0])

    @property
    def shape(self):
        return self.reward_map.shape

    def actions(self):
        return self.action_space

    def states(self):
        for h in range(self.height):
            for w in range(self.width):
                yield (h, w)

    def next_state(self, state, action):
        action_move_map = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        move = action_move_map[action]
        next_state = (state[0] + move[0], state[1] + move[1])
        ny, nx = next_state

        if nx < 0 or nx >= self.width or ny < 0 or ny >= self.height:
            next_state = state
        elif next_state == self.wall_state:
            next_state = state

        return next_state

    def reward(self, state, action, next_state):
        return self.reward_map[next_state]

    def reset(self):
        self.agent_state = self.start_state
        return self.agent_state

    def step(self, action):
        state = self.agent_state
        next_state = self.next_state(state, action)
        reward = self.reward(state, action, next_state)
        done = (next_state == self.goal_state)

        self.agent_state = next_state
        return next_state, reward, done

    def render_v(self, v=None, policy=None, print_value=True):
        renderer = render_helper.Renderer(self.reward_map, self.goal_state,
                                          self.wall_state)
        renderer.render_v(v, policy, print_value)

    def render_q(self, q=None, print_value=True):
        renderer = render_helper.Renderer(self.reward_map, self.goal_state,
                                          self.wall_state)
        renderer.render_q(q, print_value)

4.2.2 一般网格上的迭代策略评估

我们已经知道它确定性转移下的式 (4.3)：

$$ V_{\text{new}}(s) =\sum_a\pi(a\mid s) \left[ r(s,a,f(s,a))+\gamma V(f(s,a)) \right]. $$

我们把一轮迭代封装成函数：

def eval_onestep(pi, V, env, gamma=0.9):
    for state in env.states():
        if state == env.goal_state:
            V[state] = 0
            continue

        action_probs = pi[state]
        new_V = 0
        for action, action_prob in action_probs.items():
            next_state = env.next_state(state, action)
            r = env.reward(state, action, next_state)
            new_V += action_prob * (r + gamma * V[next_state])
        V[state] = new_V
    return V

然后外层 policy_eval 负责重复扫描和阈值判断：

def policy_eval(pi, V, env, gamma, threshold=0.001):
    while True:
        old_V = deepcopy(V)
        V = eval_onestep(pi, V, env, gamma)

        delta = 0
        for state in V.keys():
            t = abs(V[state] - old_V[state])
            if delta < t:
                delta = t

        if delta < threshold:
            break
    return V

测试一下：

if __name__ == '__main__':
    env = GridWorld()
    gamma = 0.9

    pi = defaultdict(lambda: {0: 0.25, 1: 0.25, 2: 0.25, 3: 0.25})
    V = defaultdict(lambda: 0)

    V = policy_eval(pi, V, env, gamma)
    env.render_v(V, pi)

image.png

这显示了随机性策略的价值函数。例如，左下角的起点的价值函 数是 −0.10。这意味着如果智能代理从左下角的起点随机移动，那么获得的 收益的期望值将是 −0.10。

智能代理也可能因为随机移动而意外地得到炸弹。根据 −0.10 可知，得到炸弹（−1 的奖励）的概率比得到苹果（+1 的奖励）的概率略大一些。另外，总的来说，底部和中间的几行都是负数。这说明炸弹在这些地方的影响更大。

三、策略迭代法

上面我们用dp进行策略评估回答“当前策略有多好”，但我们真正要的是最优策略。我们可以：先正确评估一个策略，再根据这个价值函数进行贪婪化。

3.1 策略改进

设当前确定性策略为 $\mu$，其真实状态价值为 $v_\mu$。让新策略在每个状态选择当前长期价值最大的行动：

$$ \boxed{ \mu'(s) =\operatorname*{argmax}_a q_\mu(s,a) =\operatorname*{argmax}_a \sum_{s'}p(s'\mid s,a) \left[r(s,a,s')+\gamma v_\mu(s')\right] }. \tag{4.6–4.7} $$

确定性转移时，简化为：

$$ \boxed{ \mu'(s) =\operatorname*{argmax}_a \left[r(s,a,f(s,a))+\gamma v_\mu(f(s,a))\right] }. \tag{4.8} $$

因此，第一次贪婪化得到的 $\mu'$ 不是“因为使用了 argmax 就自动最优”。它保证的是不会比 $\mu$ 更差：策略改进定理给出

$$ v_{\mu'}(s)\ge v_\mu(s),\qquad \forall s. $$

如果贪婪化后所有状态的行动都没有变化，即 $\mu'=\mu$，当前策略已经稳定。对有限 MDP 而言，这正意味着它满足最优性条件，可以视为最优策略。

上面“不变即最优”和“不比原策略差”是以精确得到 $v_\mu$ 为前提的理论结论。

3.2 交替评估与改进

**策略迭代法（policy iteration）**就是下面这个循环：

image.png

更紧凑地写为：

$$ \pi_k \xrightarrow{\text{policy evaluation}} v_{\pi_k} \xrightarrow{\text{greedy improvement}} \pi_{k+1}. $$

这种重复评估 和改进的算法叫作策略迭代法（policy iteration）。

四、实施策略迭代法

4.1 argmax 与贪婪策略

先实现一个从字典值中找最大键的辅助函数：

def argmax(d):
    """d (dict)"""
    max_val = -float('inf')
    max_key = -1
    for k, v in d.items():
        if v > max_val:
            max_key = k
            max_val = v
    return max_key

随后 greedy_policy 对每个状态枚举行动：

取出具有最大价值函数的行动，然后生成被选中的概率为 1.0 的概率分布：

def greedy_policy(V, env, gamma):
    pi = {}
    for state in env.states():
        action_values = {}
        for action in env.actions():
            next_state = env.next_state(state, action)
            r = env.reward(state, action, next_state)
            value = r + gamma * V[next_state]
            action_values[action] = value

        max_action = argmax(action_values)
        action_probs = {0: 0, 1: 0, 2: 0, 3: 0}
        action_probs[max_action] = 1.0
        pi[state] = action_probs
    return pi

4.2 policy_iter：完整的评估—改进循环 

def policy_iter(env, gamma, threshold=0.001, is_render=True):
    pi = defaultdict(lambda: {0: 0.25, 1: 0.25, 2: 0.25, 3: 0.25})
    V = defaultdict(lambda: 0)

    while True:
        V = policy_eval(pi, V, env, gamma, threshold)
        new_pi = greedy_policy(V, env, gamma)

        if is_render:
            env.render_v(V, pi)

        if new_pi == pi:
            break
        pi = new_pi

    return pi

每轮先评估当前策略，然后生成新概率，直到没有更新，说明贝尔曼最优方程得到满足。

跑一下看看效果：

第一轮：

image.png

最终：

image.png

我们用策略迭代法得出了最优策略。也就是说，我们已经完 全解决了 3×4 网格世界问题。

五、价值迭代法

策略迭代每次都会先把当前策略评估到阈值以内，再做一次完整贪婪改进。它很清楚，但“评估”和“改进”之间存在可合并的重复计算。

image.png

观策略改进和策略评估的式子：

image.png

我们发现策略评估用了策略改进的策略，那么这两个计算是重合的，那么我们不妨把改进部分的计算放到评估部分，等到评估收敛后，再取出最优策略。

5.1 把一次改进和一次评估合并

$$ \boxed{ V_{k+1}(s) =\max_a\sum_{s'}p(s'\mid s,a) \left[r(s,a,s')+\gamma V_k(s')\right] }. \tag{4.11} $$

这就是价值迭代（value iteration）的更新式。它是贝尔曼最优方程的迭代形式：

贝尔曼最优方程 价值迭代更新
$v^*(s)=\max_a\sum_{s'}p[r+\gamma v^*(s')]$ $V_{k+1}(s)=\max_a\sum_{s'}p[r+\gamma V_k(s')]$
右侧使用未知真值 $v^*$ 右侧使用当前估计 $V_k$
描述最优值的固定点条件 给出逼近固定点的具体步骤

价值迭代的更新式中不显式出现策略 $\pi$ 或 $\mu$。策略被 max 隐式地“选掉”了。收敛到 $V^*$ 后，再提取行动：

$$ \boxed{ \mu^*(s) =\operatorname*{argmax}_a \sum_{s'}p(s'\mid s,a) \left[r(s,a,s')+\gamma V^*(s')\right] }. \tag{4.12} $$

确定性转移时：

$$ \boxed{ V_{k+1}(s) =\max_a \left[ r(s,a,f(s,a))+\gamma V_k(f(s,a)) \right] }. \tag{4.13} $$

5.2 价值迭代法的实现

因为评估部分用的是改进部分的策略，这是确定策略，所以可以改写：

image.png

一次价值扫描的实现：

def value_iter_onestep(V, env, gamma):
    for state in env.states():
        if state == env.goal_state:
            V[state] = 0
            continue

        action_values = []
        for action in env.actions():
            next_state = env.next_state(state, action)
            r = env.reward(state, action, next_state)
            value = r + gamma * V[next_state]
            action_values.append(value)

        V[state] = max(action_values)	 # 这一行就是把改进和评估做了合并
    return V

因为我们希望V收敛，所以要封装一层循环：

def value_iter(V, env, gamma, threshold=0.001, is_render=True):
    while True:
        if is_render:
            env.render_v(V)

        old_V = V.copy()
        V = value_iter_onestep(V, env, gamma)

        delta = 0
        for state in V.keys():
            t = abs(V[state] - old_V[state])
            if delta < t:
                delta = t

        if delta < threshold:
            break
    return V

跑一下：

第一轮：

image.png

最后一轮：

image.png

和我们之前得到的结论是一样的。

六、小结

总结一下，这一章就是不断地跑期望dp来获得最优策略。

通过策略迭代 和 改进交替进行，让价值函数逼近贝尔曼固定点。

其实还有一个问题就是，为什么我们的算法一定会收敛呢？

因为我们的模型是 固定的 MDP 模型 + 有限状态/行动 + 折现或可靠终止条件。

并且折现率是在 (0, 1)之间，那么贝尔曼算子是一个“压缩映射”。那么根据巴拿赫不动点定理：

  1. 任何一个压缩映射，在完备的度量空间中，存在且仅存在唯一的一个不动点（Fixed point）；
  2. 从任意一个初始起点 V0 开始，不断地应用这个算子，序列必然收敛到这个唯一的不动点。

说些什么吧！

giscus