> For the complete documentation index, see [llms.txt](https://ruyuanzhang.gitbook.io/compmodcogpsy/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ruyuanzhang.gitbook.io/compmodcogpsy/di-ba-zhang-qiang-hua-xue-xi/8.1-ji-qi-xue-xi-qiang-hua-xue-xi-ji-chu/8.1.2-dong-tai-gui-hua.md).
# 8.1.2 动态规划
Edited by 王滢洁
前面的基础部分，我们了解了一些强化学习的基本概念(强化学习这一章节的基本概念每个都不复杂，但是就是概念很多...)。强化学习这一章中的单个概念并不复杂，但概念之间关系紧密，需要在后续算法中逐渐理解它们之间的关系。在Richard Sutton 和 Andrew Barto 合著的《Reinforcement Learning : An Introduction》，都会上来介绍动态规划。我们在这一章节继续使用Frozen Lake环境，来介绍一个agent如何通过动态规划来解决冰湖问题。
强化学习中的动态规划（Dynamic Programming, DP）是一类用于解决决策问题的算法，适用于已知环境模型的情况。它依赖于**贝尔曼方程**（Bellman Equation）对状态价值进行更新，并在此基础上逐步改进策略，从而找到最优解。动态规划通常用于处理马尔可夫决策过程（MDP），在这一类问题中，状态转移概率和奖励函数都是已知的，因此 agent 可以利用这些信息计算不同状态和动作的长期价值。
如前一章节所述，强化学习的目标是找到一个最优策略，使得agent的长期累积奖励最大化。在讲述如何找这个最优策略之前，我们先来介绍如何评估一个给定策略好不好。
## **策略评估**
**策略评估(policy evaluation)**的目标是估计一个给定策略 $$\pi$$ 的好坏。具体来说，我们希望知道，如果agent从某个状态 $$s$$出发，并在之后始终按照策略$$\pi$$ 行动，预期能够获得多少累计奖励。这个期望累计奖励由策略 $$\pi$$ 下的状态价值函数 $$V^\pi(s)$$ 表示：
$$
V^\pi(s) = \mathbb{E}\pi \left\[ G\_t | S\_t = s \right]
$$
其中 $$G\_t$$ 是时间 $$t$$ 开始获得的累计回报，通常表示为折扣累计奖励，其中 $$\gamma$$ 是折扣因子（discount factor）：
$$
G\_t = R\_{t+1} + \gamma R\_{t+2} + \gamma^2 R\_{t+3} + \dots = \sum\_{k=0}^{\infty} \gamma^k R\_{t+k+1}
$$
策略评估主要通过Bellman Equation来迭代更新状态价值：
$$
V^\pi(s) = \mathbb{E}*\pi \left\[ R*{t+1} + \gamma V^\pi(S\_{t+1}) | S\_t = s \right]
$$
该方程表示，当前状态 $$s$$ 的价值由前一步可能获得的奖励 $$R\_{t+1}$$ ，以及未来状态 $$S\_{t+1}$$ 的折扣价值共同决定。
根据Richard Sutton 和 Andrew Barto 的[教科书](#user-content-fn-1)[^1]，策略评估通过反复更新状态价值函数，估计给定策略 $$\pi$$ 每个状态的价值。值得关注的是，当前状态的价值 $$V(s)$$ 依赖于下一状态的价值 $$V(s')$$ ，而在开始计算时，我们不知道 $$V(s')$$ 的真实值。状态价值通常无法通过一次更新直接得到，因为一个状态的价值依赖于下一状态的价值，而下一状态的价值同样需要估计。因此，我们需要先为所有状态设置初始价值，再利用 Bellman Equation 反复更新。以 Frozen Lake 为例，靠近目标的状态会较早获得较高的价值。下一轮更新时，与这些状态相邻的位置会将它们作为未来可能到达的状态，因此自己的价值也会发生变化。经过多轮更新后，更远位置的状态也会逐渐得到较稳定的价值估计。当相邻两轮更新得到的价值几乎不再变化时，就可以认为价值函数已经基本收敛。
因此，策略评估的流程为：
1. 初始化每个状态的价值 $$V(s)$$ ，其中终止状态的价值设为 0。
2. 遍历所有非终止状态，根据当前策略 $$\pi$$ 和 Bellman Equation 更新每个状态的价值。
3. 记录本轮更新中状态价值变化的最大值 $$\Delta$$ 。
4. 重复上述更新过程，直到 $$\Delta<\theta$$ ，即状态价值函数基本不再变化。
其中， $$\Delta$$ 表示一轮更新中所有状态价值变化的最大值，可以写为：
$$
\Delta=\max\_s
\left|
V\_{\text{new}}(s)-V\_{\text{old}}(s)
\right|
$$
$$\theta$$ 是预先设定的一个很小的收敛值(convergence threshold）。如果某一轮更新后满足 $$\Delta<\theta$$ ，说明即使是变化最大的状态，其价值也只发生了非常小的改变。此时继续迭代对价值函数的影响已经很小，因此可以认为当前策略对应的状态价值函数已经近似收敛。
在策略评估过程中，策略 $$\pi$$ 始终保持不变。发生变化并逐渐收敛的是状态价值函数：
$$
V\_0
\rightarrow
V\_1
\rightarrow
V\_2
\rightarrow
\cdots
\rightarrow
V^\pi
$$
以下是策略评估的伪代码：
代码实现如下：
我们先设定一个在所有状态下选择任一action的概率为0.25的初始策略：
```python
pi_init = np.full((env.nS, env.nA), 1 / env.nA)
```
接下来，对这个随机的初始化策略进行评估：
```python
def policy_eval(pi, V, env, theta=1e-4, gamma=.99):
# except v(terminal) = 0, 重点价值设置为0
for s in env.s_termination:
V[s] = 0
# loop until convergence
while True:
delta = 0
for s in env.S:
if s not in env.s_termination:
v_old = V[s].copy()
v_new = 0
for a in env.A:
p = env.p_s_next(s, a)
for s_next in env.S:
r, done = env.r(s_next)
v_new += pi[s, a]*p[s_next]*(r + (1-done)*gamma*V[s_next])
V[s] = v_new
# check convergence
delta = np.max([delta, np.abs(v_new - v_old)])
# check convergence
if delta < theta: break
return V
```
```python
V_init = np.zeros(env.nS)
V_pe = policy_eval(pi_init.copy(), V_init.copy(), env)
fig, ax = plt.subplots(1, 1, figsize=(4, 4))
env.show_v(ax, V_pe)
plt.show()
```
通过上面的策略评估，我们可以在给定一个策略之后，得到该策略下每个状态的价值，并将其表示为价值图(value map)。图中的数值表示，如果agent从当前状态出发，并继续按照当前策略行动，预期能够获得多少累积奖励。
{% hint style="info" icon="question" %}
仔细观察上面的这个价值图，我们有以下几个发现
* 我们并不需要计算冰窟窿和出口的价值；
* 所有状态的价值都是负值；
* 越靠近冰窟窿的状态的价值相对越低，越靠近出口的状态的价值相对越高
请思考为什么有以上现象？
{% endhint %}
那么，在得到当前策略下各个状态的价值之后，如何进一步获得一个更好的策略呢？
## **策略改进**
**策略改进(policy improvement)**是在已知一个当前策略 $$\pi$$ 的情况下，尝试找到一个新的、改进后的策略 $$\pi'$$，使得新策略在所有状态下都至少与原策略相同或更优。
为了比较在某个状态 $$s$$ 下不同动作的好坏，进一步引入状态-动作价值函数$$Q^\pi(s, a)$$。它表示，agent在状态 $$s$$ 下先执行动作 $$a$$，之后继续按照策略 $$\pi$$ 行动时，能够获得的期望累计奖励。
在已知状态价值函数 $$V^\pi(s)$$的情况下，$$Q^\pi(s, a)$$可以写为：
$$
Q^\pi(s, a)=
\sum\_{s'}
P(s'\mid s,a)
\left\[
R(s,a,s')
\+
\gamma V^\pi(s')
\right]
$$
有了$$Q^\pi(s, a)$$，我们就可以在同一状态下比较不同动作，并选择其中价值最大的动作。
**策略改进定理**指出，如果对于所有状态 $$s$$，存在：
$$
\pi'(s) = \arg\max\_a Q^\pi(s, a)
$$
即，如果新策略 $$\pi'(s)$$ 选择原策略下动作价值 $$Q^\pi(s, a)$$ 最大的动作，那么新策略 $$\pi'$$ 至少与原策略 $$\pi$$ 一样好，甚至更优。这个过程就是策略改进。这个定律的证明过程这里略过，可以参考Sutton原来的教科书。
策略改进的关键是找到一种策略 $$\pi'$$ ，在每个状态下都选择最优的动作，即**贪婪地**最大化期望回报。在策略改进过程中，利用状态价值函数或者动作价值函数作为参考，对当前策略做出调整。
策略改进的流程为：
1. 遍历每一个状态 $$s$$。
2. 对当前状态下的每一个可能动作 $$a$$，根据状态转移概率、即时奖励以及下一状态的价值，计算该动作的期望回报。
3. 比较不同动作的价值，并选择价值最大的动作作为新策略 $$\pi'$$ 在当前状态下的动作。
4. 对所有状态重复上述过程，得到改进后的策略。
5. 比较新策略与原策略。如果策略没有发生变化，则说明策略已经稳定。
代码实现如下：
```python
def policy_improve(pi, V, env, theta=1e-4, gamma=.99):
pi_old = pi.copy()
for s in env.S: # loop所有的state
q = np.zeros([env.nA]) # 初始化一个qtable
for a in env.A: # loop 所有的action
p = env.p_s_next(s, a) # 注意这里p是一个向量，转移到各个s的概率
for s_next in env.S: # loop所有可能的下一个state
r, done = env.r(s_next)
q[a] += p[s_next]*(r + (1-done)*gamma*V[s_next])
pi[s] = np.eye(env.nA)[np.argmax(q)]
# check stable
if (np.abs(pi_old - pi) < theta).all():
stable = True
else:
stable = False
return pi, stable
```
```python
pi_new, stable = policy_improve(pi_init.copy(), V_pe, env)
fig, ax = plt.subplots(1, 1, figsize=(4, 4))
env.show_pi(ax, pi_new)
plt.show()
```
其中，`pi_new` 是改进后的策略，`stable` 表示新策略与原策略是否已经一致。policy map 中的箭头表示对应状态下的最优动作。
```python
# evaluate the value of new policy
V_new = policy_eval(pi_new.copy(), np.zeros(env.nS), env)
fig, ax = plt.subplots(1, 1, figsize=(4, 4))
env.show_v(ax, V_new)
plt.show()
```
对改进后的策略再次进行策略评估，可以观察新的value map。
讲到这里，也许会有读者问，强化学习的目标是获取一个更好的策略$$\pi$$。但是上面的策略改进说明我们需要先获得所有状态的价值(即价值图)，而获得所有状态的价值的过程策略评估又需要先给定一个策略。那么策略和状态价值就成了一个鸡生蛋、蛋生鸡的关系。
实际上，我们可以从一个很差的随机策略出发，通过不断重复策略评估和策略改进这两步过程，就可以最终获取一个较好的策略。这就是策略迭代的过程。
## **策略迭代**
**策略迭代(policy iteration)**是一种结合策略评估和策略改进的循环过程，用于找到最优策略。
其流程为：
1. **初始化**一个初始策略 $$\pi\_0$$。
2. **策略评估**：通过多次迭代计算得到该策略 $$\pi\_k$$ 下的状态价值函数 $$V^{\pi\_k}$$。
3. **策略改进**：根据评估出的状态价值函数，得到新的策略 $$\pi\_{k+1}$$，使得在每个状态下的期望收益最大。
4. **重复**以上过程，直到策略不再变化，达到收敛。
策略迭代的核心步骤是在当前策略下进行策略评估，然后改进策略，直到找到一个最优策略 $$\pi^*$$ 和最优价值函数 $$V^*(s)$$。其核心是不断交替进行策略评估和策略改进：先计算当前策略下各个状态的价值，再利用这些价值更新策略。如果更新后的策略与原策略不同，就继续进行下一轮策略评估；如果策略不再变化，则说明策略已经稳定。
以下是策略迭代的伪代码：
代码实现如下：
```python
def policy_iter(env, theta=1e-4, gamma=.99):
V = np.zeros(env.nS)
# uniform initial policy: [0.25, 0.25, 0.25, 0.25]
pi = np.full((env.nS, env.nA), 1 / env.nA)
while True:
V = policy_eval(pi, V, env)
pi, stable = policy_improve(pi, V, env)
# check convergence
if stable: break
return V, pi
```
```python
V_pi, pi_pi = policy_iter(env)
fig, axs = plt.subplots(1, 2, figsize=(8, 4))
env.show_v(axs[0], V_pi)
env.show_pi(axs[1], pi_pi)
plt.tight_layout()
plt.show()
```
在设定的游戏环境中模拟得到如下结果，value map 表示每个状态的最优价值，policy map 中的箭头表示对应状态下的最优动作：
不过，策略迭代还有一个特点：每次改进策略之前，都需要先对当前策略进行较完整的策略评估，也就是反复更新状态价值函数，直到其近似收敛。当状态空间较大时，这一过程可能需要进行很多轮迭代，而策略在随后的一次改进中又可能发生变化。这样一来，为一个很快就会被更新的不精准策略计算一个高度精确的价值函数，可能会带来较大的计算开销。
因此，一个自然的问题是，是否真的需要在每次策略改进之前，都等待当前策略的价值函数完全收敛？ 如果不需要，我们是否可以在价值尚未完全收敛时，就利用当前的价值估计直接进行改进？这就是价值迭代的思想。
## 价值迭代
价值迭代（Value Iteration）进一步简化了这个过程。它不再等待当前策略的价值完全收敛，而是在每一次价值更新时直接选择价值最高的动作：
$$
\max\_a
\sum\_{s'}P(s'\mid s,a)
\left\[R(s,a,s')+\gamma V\_k(s')\right]
$$
与策略评估的Bellman Equation相比，最明显的变化是：
$$
\sum\_a\pi(a\mid s)(\cdots)
\quad\longrightarrow\quad
\max\_a(\cdots)
$$
因此，策略评估问的是“按照当前策略行动，这个状态值多少？”，而价值迭代问的是“如果每次都选择当前看来最好的动作，这个状态最多值多少？”。当价值函数收敛时，就可以根据每个状态下价值最高的动作构造最终策略。
价值迭代与策略迭代类似，也通过不断更新状态价值来寻找最优策略，但它不需要在每次改进策略之前完成一次完整的策略评估。其流程为：
1. 初始化每个状态的价值 $$V(s)$$ 。
2. 遍历所有非终止状态。
3. 对当前状态下的所有动作分别计算其期望回报，并直接选择其中的最大值更新 $$V(s)$$ 。
4. 记录本轮更新中状态价值变化的最大值 $$\Delta$$ 。
5. 重复上述过程，直到 $$\Delta<\theta$$ ，价值函数达到收敛。
6. 根据收敛后的价值函数，在每个状态下选择价值最大的动作，得到最终策略。
因此，与策略评估按照当前策略对不同动作进行加权不同，价值迭代在每次更新时都直接选择当前价值最大的动作。
以下是价值迭代的伪代码：
代码实现如下：
```python
def value_iter(env, seed=1234, theta=1e-4, gamma=.99, show_value_pi=False):
rng = np.random.RandomState(seed)
# initialize V(s), arbitrarily except V(terminal)=0
V = np.zeros([env.nS,])
pi = rng.rand(env.nS, env.nA)
# loop until converge
while True:
delta = 0
for s in env.S:
if s not in env.s_termination:
v_old = V[s].copy()
q = np.zeros([env.nA])
for a in env.A:
p = env.p_s_next(s, a)
for s_next in env.S:
r, done = env.r(s_next)
q[a] += p[s_next]*(r + (1-done)*gamma*V[s_next])
# calculate V
V[s] = np.max(q)
pi[s] = np.eye(env.nA)[np.argmax(q)]
delta = np.max([delta, np.abs(V[s] - v_old)])
if delta < theta: break
for s in env.s_termination:
V[s] = 0
return V, pi
```
```python
V_vi, pi_vi = value_iter(env)
fig, axs = plt.subplots(1, 2, figsize=(8, 4))
env.show_v(axs[0], V_vi)
env.show_pi(axs[1], pi_vi)
plt.tight_layout()
plt.show()
```
最终得到的结果中，value map 表示每个状态的最优价值，policy map 中的箭头表示对应状态下的最优动作：
为了更直观地理解策略迭代和价值迭代之间的区别，可以参考下图。
图中左侧表示策略迭代的过程。在策略迭代中，策略评估和策略改进是两个相对独立的步骤：算法首先在当前策略保持不变的情况下反复更新状态价值，直到价值函数基本收敛；随后再根据得到的价值函数进行一次策略改进。对新的策略再次进行评估和改进，如此反复，最终逐步逼近最优策略 $$\pi^*$$ 和最优价值函数 $$V^*(s)$$。因此，图中左侧的更新轨迹表现为策略评估和策略改进交替进行，每一次策略改进之前，都需要先对当前策略进行较充分的评估。
图中右侧表示价值迭代的过程。与策略迭代不同，价值迭代不会在每次更新前等待某一个策略的价值函数完全收敛，而是在每一次价值更新时直接选择当前价值最高的动作。也就是说，它将价值更新和策略改进结合在同一个步骤中，并通过不断重复这一更新过程逐步逼近 $$\pi^*$$ 和 $$V^*(s)$$。因此，策略迭代和价值迭代最终都能够求得最优价值函数和最优策略，但价值迭代省去了每轮都完整评估当前策略的过程，将策略评估和策略改进合并到一次价值更新中。在很多实际问题中，这种简化能够减少计算开销，使算法更快地逼近最优解。
[^1]: citation