有模型数值迭代 - 布武不舞

一．有模型数值迭代

1.1 度量空间与压缩映射

1.1.1 度量空间及其完备性

度量 ( metric，又称距离 )，是定义在集合上的二元函数．对于集合 $X$ ，其上的度量 $d : X \times X \to R$ ，需要满足 $:$

非负性：对任意的 $x^{'}, x^{''} \in X$ , 有 $d (x^{'}, x^{''}) ⩾ 0;$
同一性：对任意的 $x^{'}, x^{''} \in X$ , 如果 $d (x^{'}, x^{''}) = 0$ , 则 $x^{'} = x^{''};$
对称性：对任意的 $x^{'}, x^{''} \in X$ , 有 $d (x^{'}, x^{''}) = d (x^{''}, x^{'});$
三角不等式: 对任意的 $x^{'}, x^{''}, x^{'''} \in X$ , 有 $d (x^{'}, x^{'''}) ⩽ d (x^{'}, x^{''}) + d (x^{''}, x^{'''})$ ．

有序对 $(X, d)$ 又称为度量空间 (metric space)．我们来看一个度量空间的例子．考虑有限 Markov 决策过程状态函数 $v (s) (s \in S)$ ，其所有可能的取值组成集合 $V = R^{∣ S ∣}$ ，定义 $d_{\infty}$ 如下: $d_{\infty} (v^{'}, v^{''}) = s \in S max ∣ v^{'} (s) - v^{''} (s) ∣, v^{'}, v^{''} \in V$ 可以证明, $d_{\infty}$ 是 $V$ 上的一个度量．（证明: 非负性、同一性、对称性是显然的．由于 $\forall s \in S$ 有 $∣ v^{'} (s) - v^{'''} (s) ∣ = ∣ [v^{'} (s) - v^{''} (s)] + [v^{''} (s) - v^{''} (s)] ∣ ⩽ ∣ v^{'} (s) - v^{''} (s) ∣ + ∣ v^{''} (s) - v^{'''} (s) ∣ ⩽ max_{s \in S} ∣ v^{'} (s) - v^{''} (s) ∣ + max_{s \in S} ∣ v^{''} (s) - v^{''} (s) ∣$ 可得三角不等式．）所以， $(V, d_{\infty})$ 是一个度量空间．对于一个度量空间，如果 Cauchy 序列都收敛在该空间内，则称这个度量空间是完备的(complete)．对于度量空间 $(V, d_{\infty})$ 也是完备的．(证明: 考虑其中任意 Cauchy 列 ${v_{k} : k = 0, 1, 2, \dots}$ ，即对任意的正实数 $ε > 0$ ，存在正整数 $κ$ 使得任意的 $k^{'}, k^{''} > κ$ ，均有 $d_{\infty} (v_{k^{'}}, v_{k^{'}}) < ε_{0}$ 对于 $\forall s \in S, ∣ v_{k^{'}} (s) - v_{k^{'}} (s) ∣ ⩽ d_{\infty} (v_{k^{'}}, v_{k^{'}}) < ε$ ，所以 ${v_{k} (s) : k = 0, 1, 2, \dots}$ 是 Cauchy 列．由实数集的完备性，可以知道 ${v_{k} (s) : k = 0, 1, 2, \dots}$ 收敛于某个实数，记这个实数为 $v_{\infty} (s)$ ．所以，对于 $\forall ε > 0$ ，存在正整数 $κ (s)$ ，对于任意 $k > κ (s)$ ，有 $∣ v_{k} (s) - v_{\infty} (s) ∣ < ε_{0}$ 取 $κ (S) = max_{s \in S} κ (s)$ ，有 $d_{\infty} (v_{k}, v_{\infty}) < ε$ ，所以 ${v_{k} : k = 0, 1, 2, \dots}$ 收敛于 $v_{\infty}$ ，而 $v_{\infty} \in V$ ，完备性得证)．

1.1.2 压缩映射与Bellman算子

本节介绍压缩映射的定义，并证明 Bellman 期望算子和 Bellman 最优算子是度量空间 $(V, d_{\infty})$ 上的压缩映射．

对于一个度量空间 $(X, d)$ 和其上的一个映射 $t : X \to X$ ，如果存在某个实数 $γ \in (0, 1)$ ，使得对于任意的 $x^{'}, x^{''} \in X$ ，都有 $d (t (x^{'}), t (x^{''})) < γ d (x^{'}, x^{''})$ 则称映射 $t$ 是压缩映射 ( contraction mapping, 或 Lipschitzian mapping)．其中的实数 $γ$ 被称为 Lipschitz 常数．

※ Bellman期望方程

用状态价值函数表示状态价值函数： $v_{π} (s) = a \sum π (a ∣ s) [r (s, a) + γ s^{'} \sum p (s^{'} ∣ s, a) v_{π} (s^{'})], s \in S$ 用动作价值函数表示动作价值函数： $q_{π} (s, a) = s^{'}, r \sum p (s^{'}, r ∣ s, a) [r + γ a^{'} \sum π (a^{'} ∣ s^{'}) q_{π} (s^{'}, a^{'})], s \in S, a \in A$

※ Bellman最优方程

用最优状态价值函数表示最优状态价值函数： $v_{*} (s) = a \in A max [r (s, a) + γ s^{'} \sum p (s^{'} ∣ s, a) v_{*} (s^{'})], s \in S$ 用最优动作价值函数表示最优动作价值函数： $q_{*} (s, a) = r (s, a) + γ s^{'} \sum p (s^{'} ∣ s, a) a^{'} max q_{*} (s^{'}, a^{'}), s \in S, a \in A$

这两个方程都有用状态价值表示状态价值的形式．根据这个形式，我们可以为度量空间 $(V, d_{\infty})$ 定义 Bellman 期望算子和 Bellman 最优算子．

给定策略 $π (a ∣ s) (s \in S, a \in A (s))$ 的 Bellman 期望算子 $t_{π} : V \to V :$ $t_{n} (v) (s) = a \sum π (a ∣ s) [r (s, a) + γ s^{'} \sum p (s^{'} ∣ s, a) v (s^{'})], s \in S$ Bellman 最优算子 $t_{.} : V \to V$ : $t_{*} (v) (s) = ces A max [r (s, a) + γ ses \sum p (s^{'} ∣ s, a) v_{\cdot} (s^{'})], s \in S$ 下面我们就来证明，这两个算子都是压缩映射．

首先来看 $Bellman$ 期望算子 $t_{π}$ ．由 $t_{π}$ 的定义可知，对任意的 $v^{'}, v^{''} \in V$ ，有 $t_{π} (v^{'}) (s) - t_{π} (v^{''}) (s) = γ a \sum π (a ∣ s) s^{'} \sum p (s^{'} ∣ s, a) [v^{'} (s^{'}) - v^{''} (s^{'})]$ 所以 $∣ t_{π} (v^{'}) (s) - t_{π} (v^{''}) (s) ∣ ⩽ γ a \sum π (a ∣ s) s^{'} \sum p (s^{'} ∣ s, a) s^{'} max ∣ v^{'} (s^{'}) - v^{''} (s^{'}) ∣ = γ d_{\infty} (v^{'}, v^{''})$ 考虑到 $s$ 是任取的，所以有 $d_{\infty} (t_{π} (v^{'}), t_{π} (v^{''})) ⩽ γ d_{\infty} (v^{'}, v^{''})$ 当 $γ < 1$ 时， $t_{n}$ 就是压缩映射．接下来看 Bellman 最优算子 $t_{*}$ ．要证明 $t_{*}$ 是压缩映射，需要用到下列不等式: $a max f^{'} (a) - a max f^{''} (a) ⩽ a max ∣ f^{'} (a) - f^{''} (a) ∣$ 其中 $f^{'}$ 和 $f^{''}$ 是任意的以 $a$ 为自变量的函数。(证明: 设 $a^{'} = ar g max_{a} f^{'} (a)$ , 则 $a max f^{'} (a) - a max f^{''} (a) = f^{'} (a^{'}) - a max f^{''} (a) ⩽ f^{'} (a^{'}) - f^{''} (a^{'}) ⩽ a max ∣ f^{'} (a) - f^{''} (a) ∣$ 同理可证 $max_{a} f^{''} (a) - max_{a} f^{'} (a) ⩽ max_{a} ∣ f^{'} (a) - f^{''} (a) ∣$ ，于是不等式得证． $)$ 利用这个不等式，对任意的 $v^{'}, v^{''} \in V$ ，有 $t_{*} (v^{'}) (s) - t_{*} (v^{''}) (s) = a \in A max [r (s, a) + γ s^{'} \in S \sum p (s^{'} ∣ s, a) v^{'} (s^{'})] - a \in A max [r (s, a) + γ s^{'} \in S \sum p (s^{'} ∣ s, a) v^{''} (s^{'})] ⩽ a^{'} \in A max γ s^{'} \in S \sum p (s^{'} ∣ s, a^{'}) (v^{'} (s^{'}) - v^{''} (s^{'})) ⩽ γ a^{'} \in A max s^{'} \in S \sum p (s^{'} ∣ s, a^{'}) s^{'} \in S max ∣ v^{'} (s^{'}) - v^{''} (s^{'}) ∣ ⩽ γ d_{\infty} (v^{'}, v^{''})$ 进而易知 $∣ t_{*} (v^{'}) (s) - t_{*} (v^{''}) (s) ∣ ⩽ γ d_{\infty} (v^{'}, v^{''})$ ，所以 $t_{*}$ 是压缩映射．

1.1.3 Banach不动点定理

对于度量空间 $(X, d)$ 上的映射 $t : X \to X$ ，如果 $x \in X$ 使得 $t (x) = x$ ，则称 $x$ 是映射 $t$ 的不动点 (fix point)．

例如，策略 $π$ 的状态价值函数 $v_{π} (s) (s \in S)$ 满足 Bellman 期望方程，是 Bellman 期望算子 $t_{π}$ 的不动点．最优状态价值 $v_{*} (s) (s \in S)$ 满足 Bellman 最优方程，是 Bellman 最优算子 $t_{*}$ 的不动点．

完备度量空间上的压缩映射有非常重要的结论: Banach 不动点定理． Banach 不动点定理（Banach fixed-point theorem, 又称压缩映射定理， compressed mapping theorem) 的内容是: $(X, d)$ 是非空的完备度量空间, $t : X \to X$ 是一个压缩映射，则映射 $t$ 在 $X$ 内有且仅有一个不动点 $x_{+ \infty}$ ．更进一步，这个不动点可以通过下列方法求出：从 $X$ 内的任意一个元素 $x_{0}$ 开始，定义迭代序列 $x_{k} = t (x_{k - 1}) (k = 1, 2, 3, \dots)$ ，这个序列收敛，且极限为 $x_{+ \infty}$ ．

证明：考虑任取的 $x_{0}$ 及其确定的列 ${x_{k} : k = 0, 1, \dots}$ ，我们可以证明它是 Cauchy 序列．对于任意的 $k^{'}, k^{''}$ 且 $k^{'} < k^{n}$ ，用距离的三角不等式和非负性可知， $d (x_{k}, x_{k^{'}}) ⩽ d (x_{k^{'}}, x_{k^{'} + 1}) + d (x_{k^{'} + 1}, x_{k^{'} + 2}) + \dots + d (x_{k^{''} - 1}, x_{k^{''}}) ⩽ k = k^{'} \sum + \infty d (x_{k + 1}, x_{k})$ 再反复利用压缩映射可知，对于任意的正整数 $k$ 有 $d (x_{k + 1}, x_{k}) ⩽ γ^{k} d (x_{1}, x_{0})$ ，代人得： $d (x_{k^{'}}, x_{k^{''}}) ⩽ k = k^{'} \sum + \infty d (x_{k + 1}, x_{k}) ⩽ k = k^{'} \sum + \infty γ^{k} d (x_{1}, x_{0}) = \frac{γ ^{k^{'}}}{1 - γ} d (x_{1}, x_{0})$ 由于 $γ \in (0, 1)$ ，所以上述不等式右端可以任意小，得证．

Banach 不动点定理给出了求完备度量空间中压缩映射不动点的方法：从任意的起点开始，不断迭代使用压缩映射，最终就能收敛到不动点．并且在证明的过程中，还给出了收敛速度，即迭代正比于 $γ^{k}$ 的速度收敛 $($ 其中 $k$ 是迭代次数)．在 $1.1.1$ 节我们已经证明 $(V, d_{\infty})$ 是完备的度量空间，而 $1.1.2$ 节又证明了 Bellman 期望算子和 $Bellman$ 最优算子是压缩映射，那么就可以用迭代的方法求 Bellman 期望算子和 Bellman 最优算子的不动点．于 $Bellman$ 期望算子的不动点就是策略价值，Bellman 最优算子的不动点就是最优价值，所以这就意味着我们可以用迭代的方法求得策略的价值或最优价值．在后面的小节中，就来具体看看求解的算法．

1.2 有模型策略迭代

本节介绍在给定动力系统 $p$ 的情况下的策略评估、策略改进和策略迭代．策略评估、策略改进和策略迭代分别指以下操作．

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

1.2.1 策略评估

本节介绍如何用迭代方法评估给定策略的价值函数．如果能求得状态价值函数，那么就能很容易地求出动作价值函数．由于状态价值函数只有 $∣ S ∣$ 个自变量，而动作价值函数有 $∣ S ∣ \times ∣ A ∣$ 个自变量，所以存储状态价值函数比较节约空间．

用迭代的方法评估给定策略的价值函数的算法如算法 1-1 所示．算法 1-1 一开始初始化状态价值函数 $v_{0}$ ，并在后续的迭代中用 $Bellman$ 期望方程的表达式更新一轮所有状态的状态价值函数．这样对所有状态价值函数的一次更新又称为一次扫描（sweep)．在第 $k$ 次扫描时，用 $v_{k - 1}$ 的值来更新 $v_{k}$ 的值，最终得到一系列的 $v_{0}, v_{1}, ν_{2}, \dots$ ．

算法 1-1：有模型策略评估迭代算法

输入: 动力系统 $p$ , 策略 $π$ 输出：状态价值函数 $v_{π}$ 的估计值参数: 控制迭代次数的参数（如误差容忍度 $ϑ_{m a x}$ 或最大迭代次数 $k_{m a x})$

(初始化) 对于 $s \in S$ ，将 $v_{0} (s)$ 初始化为任意值 (比如 0 )．如果有终止状态，将终止状态初始化为 0，即 $v_{0} (S_{终止}) \leftarrow 0$
(迭代) 对于 $k \leftarrow 0, 1, 2, 3, \dots$ ，迭代执行以下步骤 2.1 对于 $s \in S$ , 逐一更新 $v_{k + 1} (s) \leftarrow \sum_{a} π (a ∣ s) q_{k} (s, a)$ ，其中 $q_{k} (s, a) \leftarrow r (s, a) + γ \sum_{s^{'}} p (s^{'} ∣ s, a) v_{k} (s^{'})$ ． 2.2 如果满足迭代终止条件 (如对 $s \in S$ 均有 $∣ v_{k + 1} (s) - v_{k} (s) ∣ < ϑ_{m a x}$ ，或达到最大迭代次数 $k = k_{m a x})$ ，则跳出循环

值得一提的是，算法 1-1 没必要为每次捉描都重新分配一套空间来存储．一种优化的方法是，设置奇数次迭代的存储空间和偶数次迭代的存储空间，一开始初始化偶数次存储空间，当 $k$ 是奇数时，用偶数次存储空间来更新奇数次存储空间; 当 $k$ 是偶数时, 用奇数次存储空间来更新偶数次存储空间．这样，一共只需要两套存储空间就可以完成算法．

1.2.2 策略改进

对于给定的策略 $π$ ，如果得到该策略的价值函数，则可以用策略改进定理得到一个改进的策略．

策略改进定理的内容如下：对于策略 $π$ 和 $π^{'}$ ，如果 $v_{π} (s) ⩽ a \sum π^{'} (a ∣ s) q_{π} (s, a), s \in S$ 则 $π ⩽ π^{'}$ ，即 $v_{π} (s) ⩽ v_{π^{'}} (s), s \in S$ 在此基础上，如果存在状态使得第一式的不等号是严格小于号，那么就存在状态使得第二式中的不等号也是严格小于号．

证明: 考虑到第一个不等式等价于 $v_{π} (s) = E_{π^{'}} [v_{π} (S_{t}) ∣ S_{t} = s] ⩽ E_{π^{'}} [q_{π} (S_{t}, A_{t}) ∣ S_{t} = s], s \in S$ 其中的期望是针对用策略 $π^{'}$ 生成的轨迹中，选取 $S_{t} = s$ 的那些轨迹而言的．进而有 $E_{π^{'}} [ν_{π} (S_{t + τ}) ∣ S_{t} = s] = E_{π^{'}} [E_{π^{'}} [v_{π} (S_{t + τ}) ∣ S_{t + τ}] ∣ S_{t} = s] ⩽ E_{π^{'}} [E_{π^{'}} [q_{π} (S_{t + τ}, A_{t + τ}) ∣ S_{t + τ}] ∣ S_{t} = s] = E_{π^{'}} [q_{π} (S_{t + τ}, A_{t + τ}) ∣ S_{t} = s], s \in S, τ = 0, 1, 2, \dots$ 考虑到 $E_{π^{'}} [q_{π} (S_{t + τ}, A_{t + τ}) ∣ S_{t} = s] = E_{π^{'}} [R_{t + τ + 1} + γ v_{π} (S_{t + τ + 1}) ∣ S_{t} = s], s \in S, τ = 0, 1, 2, \dots$ 所以 $E_{π^{'}} [v_{π} (S_{t + τ}) ∣ S_{t} = s] ⩽ E_{π^{'}} [R_{t + τ + 1} + γ v_{π} (S_{t + τ + 1}) ∣ S_{t} = s], s \in S, τ = 0, 1, 2, \dots$ 进而有 $v_{π} (s) = E_{π^{'}} [v_{π} (S_{t}) ∣ S_{t} = s] ⩽ E_{π^{'}} [R_{t + 1} + γ v_{π} (S_{t + 1}) ∣ S_{t} = s] ⩽ E_{π^{'}} [R_{t + 1} + γ E_{π^{'}} [R_{t + 2} + γ v_{π} (S_{t + 2}) ∣ S_{t} = s] ∣ S_{t} = s] ⩽ E_{π^{'}} [R_{t + 1} + γ R_{t + 2} + γ^{2} v_{π} (S_{t + 2}) ∣ S_{t} = s] ⩽ E_{π^{'}} [R_{t + 1} + γ R_{t + 2} + γ^{2} R_{t + 3} + γ^{3} v_{π} (S_{t + 4}) ∣ S_{t} = s] \dots ⩽ E_{π^{'}} [R_{t + 1} + γ R_{t + 2} + γ^{2} R_{t + 3} + γ^{3} R_{t + 4} + \dots ∣ S_{t} = s] = E_{π^{'}} [G_{t} ∣ S_{t} = s] = v_{π^{'}} (s), s \in S$ 严格不等号的证明类似．

对于一个确定性策略 $π$ ，如果存在着 $s \in S, a \in A$ ，使得 $q_{π} (s, a) > v_{π} (s)$ ，那么我们可以构造一个新的确定策略 $π^{'}$ ，它在状态 $s$ 做动作 $a$ ，而在除状态 $s$ 以外的状态的动作都和策略一样．可以验证，策略 $π$ 和 $π^{'}$ 满足策略改进定理的条件．这样，我们就得到了一个比策略 $π$ 更好的策略 $π^{'}$ ．这样的策略更新算法可以用算法 1-2 来表示．

算法 1-2：有模型策略改进算法

输入: 动力系统 $p$ ，策略 $π$ 及其状态价值函数 $v_{π}$ 输出：改进的策略 $π^{'}$ ，或策略 $π$ 已经达到最优的标志

对于每个状态 $s \in S$ ，执行以下步骤: 1.1 为每个动作 $a \in A$ ，求得动作价值函数 $q_{π} (s, a) \leftarrow r (s, a) + γ \sum_{s^{'}} p (s^{'} ∣ s, a) v_{π} (s^{'})$ 1.2 找到使得 $q_{π} (s, a)$ 最大的动作 $a$ ，即 $π^{'} (s) = ar g max_{a} q (s, a)$
如果新策略 $π^{'}$ 和旧策略 $π$ 相同，则说明旧策略巳是最优; 否则，输出改进的新策略 $π^{'}$

值得一提的是，在算法 1-2 中，旧策略 $π$ 和新策略 $π^{'}$ 只在某些状态上有不同的动作值, 新策略 $π^{'}$ 可以很方便地在旧策略 $π$ 的基础上修改得到．所以，如果在后续不需要使用旧策略的情况下，可以不为新策略分配空间．

1.2.3 策略迭代

策略迭代是一种综合利用策略评估和策略改进求解最优策略的迭代方法．

见算法 1-3 ，策略迭代从一个任意的确定性策略 $π_{0}$ 开始，交替进行策略评估和策略改进．这里的策略改进是严格的策略改进，即改进后的策略和改进前的策略是不同的对于状态空间和动作空间均有限的 Markov 决策过程，其可能的确定性策略数是有限的．由于确定性策略总数是有限的，所以在迭代过程中得到的策略序列 $π_{0}, π_{1}, π_{2}, \dots$ 一定能收敛，使得到某个 $k$ ，有 $π_{k} = π_{k + 1}$ (即对任意的 $s \in S$ 均有 $π_{k + 1} (s) = π_{k} (s))$ ．由于在 $π_{k} = π_{k + 1}$ 的情况下， $π_{k} (s) = π_{k + 1} (s) = ar g max_{a} q_{π_{k}} (s, a)$ ，进而 $v_{π_{k}} (s) = max_{a} q_{π_{k}} (s, a)$ ，满足 Bellman 最优方程．因此， $π_{k}$ 就是最优策略．这样就证明了策略迭代能够收敛到最优策略．

算法 1-3：有模型策略迭代

输入: 动力系统 $p$ 输出：最优策略

(初始化）将策略 $π_{0}$ 初始化为一个任意的确定性策略．
(迭代) 对于 $k \leftarrow 0, 1, 2, 3, \dots$ , 执行以下步骤 2.1 （策略评估）使用策略评估算法，计算策略 $π_{k}$ 的状态价值函数 $v_{π_{k}}$ 2.2 （策略更新）利用状态价值函数 $v_{π_{k}}$ 改进确定性策略 $π_{k}$ ，得到改进的确定性策略 $π_{k + 1}$ ．如果 $π_{k + 1} = π_{k}$ ．（即对任意的 $s \in S$ 均有 $π_{k + 1} (s) = π_{k} (s)$ ），则迭代完成，返回策略 $π_{k}$ 为最终的最优策略．

策略迭代也可以通过重复利用空间来节约空间．为了节约空间，在各次迭代中用相同的空间 $v (s) (s \in S)$ 来存储状态价值函数，用空间 $π (s) (s \in S)$ 来存储确定性策略．

1.3 有模型价值迭代

价值迭代是一种利用迭代求解最优价值函数进而求解最优策略的方法．在 $1.2.1$ 节介绍的策略评估中，迭代算法利用 Bellman 期望方程迭代求解给定策略的价值函数．与之相对，本节将利用 Bellman 最优方程迭代求解最优策略的价值函数，并进而求得最优策略．

与策略评估的情形类似，价值迭代算法有参数来控制迭代的终止条件，可以是误差容忍度 $ϑ_{m a x}$ 或是最大迭代次数 $k_{m a x}$ ．

算法 1-4 给出了一个价值迭代算法．这个价值迭代算法中先初始化状态价值函数，然后用 Bellman 最优方程来更新状态价值函数．根据第 1.1 节的证明，只要迭代次数足够多，最终会收敘到最优价值函数．得到最优价值函数后，就能很轻易地给出确定性的最优策略．

算法 1-4：有模型价值迭代算法

输入：动力系统 $p$ 愉出：最优策略估计 $π$ 参数：策略评估需要的参数

(初始化) $v_{0} (s) \leftarrow$ 任意值， $s \in S$ ．如果有终止状态， $v_{0} (s_{终止}) \leftarrow 0$
(迭代) 对于 $k \leftarrow 0, 1, 2, 3, \dots$ ，执行以下步骤 2.1 对于 $s \in S$ ，逐一更新 $v_{k + 1} (s) \leftarrow max_{a} {r (s, a) + γ \sum_{s^{'}} p (s^{'} ∣ s, a) v_{k} (s^{'})}$ 2.2 如果满足误差容忍度 (即对于 $s \in S$ 均有 $∣ v_{k + 1} (s) - v_{k} (s) ∣ < ϑ)$ 或达到最大迭代次数 (即 $k = k_{m a x})$ ，则跳出循环
(策略) 根据价值函数输出确定性策略 $π_{*}$ ，使得 $π_{*} (s) \leftarrow a ar g max {r (s, a) + γ \sum_{s^{'}} p (s^{'} ∣ s, a) v_{k + 1} (s^{'})}, s \in S_{0}$

与策略评估的迭代求解类似，价值迭代也可以在存储状态价值函数时重复使用空间．算法 1-5 给出了重复使用空间以节约空间的版本．

算法 1-5：有模型价值迭代 (节约空间的版本 )

输入: 动力系统 $p$ 输出：最优策略参数：策略评估需要的参数

(初始化) $v_{0} (s) \leftarrow$ 任意值, $s \in S$ ．如果有终止状态， $v_{0} (s_{终止}) \leftarrow 0$
(迭代) 对于 $k \leftarrow 0, 1, 2, 3, \dots$ ，执行以下步骤 2.1 对于使用误差容忍度的情况，初始化本次迭代观测到的最大误差 $ϑ \leftarrow 0$ 2.2 对于 $s \in S$ 执行以下操作:
1. 计算新状态价值 $v_{新} \leftarrow max_{a} {r (s, a) + γ \sum_{s^{'}} p (s^{'} ∣ s, a) v (s^{'})}$
2. 对于使用误差容忍度的情况，更新本次迭代观测到的最大误差 $ϑ \leftarrow max {ϑ, ∣ v_{新} - v (s) ∣}$
3. 更新状态价值函数 $v (s) \leftarrow v_{新}$ 2.3 如果满足误差容忍度（即 $ϑ < ϑ_{m a x})$ 或达到最大迭代次数 $($ 即 $k = k_{m a x})$ ，则跳出循环
(策略) 根据价值函数输出确定性策略: $π (s) = a ar g max {r (s, a) + γ s \sum p (s^{'} ∣ s, a) v (s^{'})} ．$