第三章：有模型数值迭代

对于实际问题，由于直接求解 Bellman 期望方程和 Bellman 最优方程往往有困难（例如需要极多的计算资源），本章在动力系统完全已知的情况下，用迭代的数值方法来求解。由于有模型迭代并没有从数据中学习，所以一般不认为是一种机器学习或强化学习方法。

一、度量空间与压缩映射

有模型策略迭代的理论基础：度量空间上的 Banach 不动点定理。下面简单介绍必要的概念，并证明 Bellman 算子是压缩映射，可以用 Banach 不动点定理迭代求解 Bellman 方程。

度量（mertic，又称距离），是定义在集合上的二元函数。对于集合 $\mathcal X$ ，其上的度量 $d: \mathcal X \times \mathcal X \rightarrow \Bbb R$ ，需满足：

• 非负性：对任意的 $x', x'' \in \mathcal X$ ，有 $d\left(x', x''\right) \ge 0$ ；

• 同一性：对任意的 $x', x'' \in \mathcal X$ ，如果 $d\left(x', x''\right) = 0$ ，则 $x'=x''$ ；

• 对称性：对任意的 $x', x'' \in \mathcal X$ ，有 $d\left(x', x''\right) = d\left(x'',x'\right)$ ；

• 三角不等式：对任意的 $x', x'', x''' \in \mathcal X$ ，有 $d\left(x', x'''\right) \le d\left(x', x''\right) + d\left(x'', x'''\right)$ ；

  度量看起来与范数很像，但其本质是不一样的，参考资料：https://www.zhihu.com/question/42312263

有序对 $(\mathcal X, d)$ 又称为度量空间（metric space）。考虑有限 Markov 决策过程状态函数 $v(s) \; (s \in \mathcal S)$ ，其中所有可能的取值组成集合 $\mathcal V = \Bbb R^{|\mathcal S|}$ ，定义 $d_\infty$ 如下 ：

可以证明 $d_\infty$ 是 $\mathcal V$ 上的一个度量。证明：显然满足非负性、同一性、对称性，而对于 $\forall s \in \mathcal S$ 有：

可得三角不等式，所以 $(\mathcal V, d_\infty)$ 是一个度量空间。

对于一个度量空间，如果 Cauchy 序列都收敛在该空间内，则称这个度量空间是完备的（complete）。例如，实数集 $\Bbb R$ 就是一个著名的完备空间（事实上实数集就是由完备性定义出来的。有理数集不完备，加上无理数集就完备了），对于 $(\mathcal V, d_\infty)$ 度量空间也是完备的（证明：略）。

对于一个度量空间 $(\mathcal X, d)$ 和其上的一个映射 $t:\mathcal X \rightarrow \mathcal X$ ，如果存在某个实数 $\gamma \in (0,1)$ ，使得对于任意的 $x', x'' \in \mathcal X$ ，都有 $d\left(\, t(x'), t(x'')\,\right) < \gamma\, d\left(x',x''\right)$ ，则称映射 $t$ 是压缩映射（contraction mapping，或 Lipschitzian mapping）。其中的实数 $\gamma$ 被称为 Lipschitzian 常数。而 Bellman 期望算子和 Bellman 最优算子 $t_*$ 是度量空间 $(\mathcal V, d_\infty)$ 上的压缩映射（证明：使用 $\eqref{eq:2} \eqref{eq:3}$ 代入到定义中使用不等式去证明，过程略）。

• 给定策略 $\pi\left(a \mid s\right) (s \in \mathcal S,a \in \mathcal A(s))$ 的 Bellman 期望算子 $t_\pi:\mathcal V \rightarrow \mathcal V$ ：

• Bellman 最优算子 $t_*:\mathcal V \rightarrow \mathcal V$ ：

对于度量空间 $(\mathcal X, d)$ 上的映射 $t:\mathcal X \rightarrow \mathcal X$ ，如果 $x \in \mathcal X$ 使得 $t(x)=x$ ，则称 $x$ 是映射 $t$ 的不动点（fix point）。在完备度量空间上的压缩映射有非常重要的结论：Banach 不动点定理（Banach fixed-point theorem，又称压缩映射定理，compressed mapping theorem）。其内容为： $(\mathcal X, d)$ 是非空的完备度量空间， $t:\mathcal X \rightarrow \mathcal X$ 是一个压缩映射，则映射 $t$ 在 $\mathcal X$ 内有且仅有一个不动点 $x_{+\infty}$ 。

不动点的求取方法：从 $\mathcal X$ 内的任意一个元素 $x_0$ 开始，定义迭代序列 $x_k = t(x_{k-1}) \; (k=1,2,3,...)$ ，这个序列收敛，且极限为 $x_{+\infty}$ 。收敛证明：对于任意的 $k', k''$ 且 $k' < k''$ ，由三角不等式和非负性及压缩映射可知：

由于 $\gamma \in (0,1)$ ，所以上式不等式右端可以任意小，证毕。另外，在证明过程中可以看出迭代正比于 $\gamma^k$ 的速度收敛。

有了不动点的求取方法，那么就可以用该方法求 Bellman 期望算子和最优算子的不动点。其中 Bellman 期望算子的不动点是策略价值，对应于策略迭代算法；Bellman 最优算子的不动点是最有价值，对应于价值迭代算法。

二、有模型策略迭代

各种策略迭代算法中包含以下的三个概念：

• 策略评估（policy evaluation）：对于给定的策略 $\pi$ ，估计策略的价值，包括动作价值和状态价值。
• 策略改进（policy improvement）：对于给定的策略 $\pi$ ，在已知其价值函数的情况下，找到一个更优的策略。
• 策略迭代（policy iteration）：综合利用策略评估和策略改进，找到最优策略。

对于策略评估，由于状态价值函数有 $|\mathcal S|$ 各自变量，而动作价值函数有 $|\mathcal S| \times |\mathcal A|$ 个自变量，因此选择使用状态价值函数作为迭代存储变量，以节约空间。策略评估在迭代中使用 Bellman 期望方程的表达式更新一轮所有状态的状态价值函数，这样对所有状态价值函数的一次更新又称为一次扫描。策略评估迭代算法有以下两种：

事实上算法 3-1 没必要为每次扫描都重新分配一套空间 $v_k\;(k=0,1,2,...)$ 来存储，一种优化方法是，设置奇数次迭代的存储空间和偶数次迭代的存储空间，迭代更新时交换使用 $v_{odd} = f\left(v_{even}\right)$ 和 $v_{even} = f\left(v_{odd}\right)$ ，这样只需要两套存储空间就可以完成算法。

算法 3-2 则只使用了一套存储空间，每次扫描时，他都及时更新状态价值函数。这样在更新后续的状态时，用来更新的状态价值函数有些在本次迭代中已经更新，有些在本次迭代中还没更新，所以，算法 3-2 的计算结果和算法 3-1 的计算结果不完全相同。不过，算法 3-2 在迭代次数不限的情况下也能收敛到状态价值函数。

对于策略改进，有策略改进定理：对于两个确定性的策略 $\pi$ 和 $\pi'$ ，如果

则 $\pi \le \pi'$ ，即

在此基础上，若存在状态使得 $\eqref{eq:4}$ 的不等号是严格小于号，那么就存在状态使得 $\eqref{eq:5}$ 中的不等号也是严格小于号。（证明：略）

根据策略改进定理，对于确定性策略，若 $q_\pi\left(s,a\right) \gt v_\pi\left(s\right)$ ，那么就可以构造一个新策略 $\pi'$ ，该策略在状态 $s$ 做动作 $a$ ，而其他状态则与策略 $\pi$ 一致。这样的策略改进算法也有两个版本：

算法 3-3 中，如果在后续不需要使用旧策略的情况下，可以不为新策略分配空间，由此就得到了算法 3-4 的版本。

在了解策略评估和策略改进后，通过策略迭代综合利用两者来获得最优策略。策略迭代从一个任意的确定性策略 $\pi_0$ 开始，交替进行策略评估和策略改进，其基本步骤顺序如下图所示：

对于有限 Markov 决策过程，其确定性策略数是有限的，因此迭代过程中得到的策略序列一定能收敛。策略迭代算法的两个版本如下所示：

同样为了节省空间，在各次迭代中用相同的空间 $v\left(s\right)（s \in \mathcal S）$ 来存储状态价值函数，用空间 $\pi\left(s\right)（s \in \mathcal S）$ 来存储确定性策略，即可得到策略迭代算法 3-6 的版本

三、有模型价值迭代

策略评估迭代算法利用 Bellman 期望方程迭代求解给定策略的价值函数，而价值迭代算法则是利用 Bellman 最优方程迭代求解最优策略的价值函数，并进而求得最优策略，其算法如下：

同样，价值迭代也可以在存储状态价值函数时重复使用空间，因此有以下版本的价值迭代算法：

四、案例：冰面滑行（FrozenLake-v0）

使用 gym 库中的冰面滑行问题（FrozenLake-v0）作为案例分析，该环境也是一个有限 Markov 决策过程，具体环境和规则可查看源代码。书上的源代码是使用算法 3-2 实现策略评估算法，使用算法 3-4 实现策略改进算法，使用算法 3-6 实现策略迭代算法来获取最优策略及其状态价值函数。

根据书上的源代码，将其改写成了一个类 PolicyIteration ，为了方便研究整个评估和改进过程，将动作价值函数 $q(s,a)$ 也存储了下来，所以策略改进部分没有严格按算法实现，并且并综合修改了其他模块的部分语句，改写的代码如下：

​x
1
class PolicyIteration():
2
    def __init__(self, env, gamma=0.99, tolerant=1e-6):
3
        self.env = env
4
        self.gamma = gamma
5
        self.tolerant = tolerant
6
        self.policy = np.ones((env.observation_space.n, env.action_space.n)) / env.action_space.n
7
        self.v_table = np.zeros(env.observation_space.n)
8
        self.q_table = np.zeros((env.observation_space.n, env.action_space.n))
9
        self.policy_is_optimal = False
10
​
11
    def v2q(self, single_state=None):
12
        if single_state is not None:
13
            q_line = np.zeros(self.env.action_space.n)
14
            for action in range(self.env.action_space.n):
15
                for proba, next_state, reward, done in self.env.P[single_state][action]:
16
                    q_line[action] += proba * (reward + self.gamma * self.v_table[next_state] * (1.0 - done))
17
            return q_line
18
        else:
19
            for state in range(self.env.observation_space.n):
20
                self.q_table[state] = self.v2q(state)
21
​
22
    def evaluate_policy(self):
23
        self.v_table[:] = 0
24
        while True:
25
            delta = 0
26
            for state in range(self.env.observation_space.n):
27
                v_new = sum(self.policy[state] * self.v2q(state))
28
                delta = max(delta, abs(self.v_table[state]-v_new))
29
                self.v_table[state] = v_new
30
            if delta < self.tolerant:
31
                break
32
​
33
    def improve_policy(self):
34
        self.v2q()
35
        actions = np.argmax(self.q_table, axis=1)
36
        policy = np.eye(self.env.observation_space.n, \
37
                self.env.action_space.n)[actions]
38
        if (self.policy == policy).all():
39
            self.policy_is_optimal = True
40
        else:
41
            self.policy = policy
42
​
43
    def iterate_policy(self):
44
        while True:
45
            self.evaluate_policy()
46
            self.improve_policy()
47
            if self.policy_is_optimal:
48
                break

对于该案例也可以使用价值迭代算法去求解最优策略，书上的源代码是使用算法 3-8 实现的价值迭代算法，同样的，也将其改写成了一个类 ValueIteration ，并且记录了动作价值函数 $q(s,a)$ ，改写的代码如下：

xxxxxxxxxx
32
1
class ValueIteration():
2
    def __init__(self, env, gamma=0.99, tolerant=1e-6):
3
        self.env = env
4
        self.gamma = gamma
5
        self.tolerant = tolerant
6
        self.v_table = np.zeros(env.observation_space.n)
7
        self.q_table = np.zeros((env.observation_space.n, env.action_space.n))
8
​
9
    def v2q(self, single_state=None):
10
        if single_state is not None:
11
            q_line = np.zeros(self.env.action_space.n)
12
            for action in range(self.env.action_space.n):
13
                for proba, next_state, reward, done in self.env.P[single_state][action]:
14
                    q_line[action] += proba * (reward + self.gamma * self.v_table[next_state] * (1.0 - done))
15
            return q_line
16
        else:
17
            for state in range(self.env.observation_space.n):
18
                self.q_table[state] = self.v2q(state)
19
​
20
    def iterate_value(self):
21
        while True:
22
            delta = 0
23
            for state in range(self.env.observation_space.n):
24
                v_max = max(self.v2q(state))
25
                delta = max(delta, abs(self.v_table[state]-v_max))
26
                self.v_table[state] = v_max
27
            if delta < self.tolerant:
28
                break
29
        self.v2q()
30
        actions = np.argmax(self.q_table, axis=1)
31
        self.policy = np.eye(self.env.observation_space.n, \
32
                self.env.action_space.n)[actions]