Introduction
本节介绍 Value Iteration, Policy Iteration 和 Truncated Policy Iteration. 这三种办法都是解决 Bellman Optimal Equation 的方法，而且都是在 Model-Based 的情况下的算法。
Value Iteration
下面给出 Value Iteration 的基本流程：
- 给定 State Value 的初始值$v_c(s)$
进入循环：
- Policy Update
基于上一轮更新的 State Value, 选定最优策略（贪心策略），即：
\[
\begin{align}
\pi_{k+1} = \mathrm{arg} \max\limits_{\pi}(r_{\pi} + \gamma P_{\pi} v_k) \\
\begin{cases}
\pi_{k+1}(a|s) = 1, a = a_k^*(s) \\
\pi_{k+1}(a|s) = 0, a \neq a_k^*(s) \\
\end{cases}
\end{align}
\]
式中，$a_k^*(s) = \mathrm{arg} \max\limits_{a}q_k(a,s)$. Value Update
在新的 Policy 基础上，更新 State Value，即：
\[
v_{k+1} = r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{k}
\]由于我们采用了贪心策略，因此，上式其实就是：
\[
v_{k+1} = \max \limits_{a} q(a,s)
\]- Check
检查是否满足 $||v_{k+1} - v_{k}|| < \delta $, 其中 $\delta$ 是一个事先指定的很小的正数。如果满足，则退出循环，求解完毕。如果不满足，则继续循环。
- Policy Update
Policy Iteration
下面给出 Policy Iteration 的基本流程：
- 给定 Policy 的初始值 $\pi_0$
- 进入循环：
- Policy Evaluation
Policy Evaluation 基于上一轮更新的 Policy 解 Bellman Equation.
\[
v_{\pi_k} = r_{\pi_{k}} + \gamma P_{\pi_{k}} v_{\pi_k}
\]
一个有趣的问题：此处如何解 Bellman Equation? 方法就是在第2节中所展示的迭代方法，即：
\[
v_{\pi_k}^{(j+1)} = r_{\pi} + \gamma P_{\pi}v_{\pi_k}^{(j)}
\]
将这个迭代方法进行很多次，直至 $||v_{\pi_k}^{(j+1)} - v_{\pi_k}^{(j)}|| < \epsilon $, $\epsilon$ 是一个事先指定的很小的正数。 - Check
检查是否满足 $||v_{\pi_k} - v_{\pi_{k-1}}|| < \delta $, 其中 $\delta$ 是一个事先指定的很小的正数。- 如果此条件满足，则退出循环。
- 如果此条件不满足，则进行 Policy Improvement.
基于求解的 State Value 更新 Policy.
\[
\begin{align}
\pi_{k+1} = \mathrm{arg} \max\limits_{\pi}(r_{\pi} + \gamma P_{\pi} v_{\pi_k}) \\
\begin{cases}
\pi_{k+1}(a|s) = 1 \ \ \ a = a_{\pi_k}^*(s) \\
\pi_{k+1}(a|s) = 0 \ \ \ a \neq a_{\pi_k}^*(s) \\
\end{cases}
\end{align}
\]
- Policy Evaluation
Truncated Policy Iteration
通过观察可以发现，Policy Iteration 和 Value Iteration 的区别在于，Value Iteration 每次更新 State Value 时，只根据 Bellman Equation 迭代了一次，而 Policy Iteration 从理论上迭代了无穷多次，求出了 Bellman Equation 的一个精确解。因此，我们可以设想有这样一种办法，它每次根据 Bellman Equation 迭代了有穷多次（不妨记为$j$次），这就是 Truncated Policy Iteration, 如同将 Policy Iteration 截断。 Value Iteration 和 Policy Iteration 可以分别视为 Truncated Policy Iteration 的两个特殊情况。
下面给出 Truncated Policy Iteration 的基本流程：
- 给定 Policy 的初始值 $\pi_0$
- 进入循环：
- Policy Evaluation
Policy Evaluation 基于上一轮更新的 Policy 解 Bellman Equation.
\[
v_{\pi_k} = r_{\pi_{k}} + \gamma P_{\pi_{k}} v_{\pi_k}
\]
设定$j = 0$, 进入子循环，检查是否有$j \leq j_{max}$:- 如果$j \leq j_{max}$, 则继续迭代：
\[
v_{\pi_k}^{(j+1)} = r_{\pi} + \gamma P_{\pi}v_{\pi_k}^{(j)}
\]
并且更新$j$值：$j = j+1$ - 如果$j > j_{max}$ 则退出子循环，最终：$v_{\pi_k}= v_{\pi_k}^{j_{max}} $.
- 如果$j \leq j_{max}$, 则继续迭代：
- Check
检查是否满足 $||v_{\pi_k} - v_{\pi_{k-1}}|| < \delta $, 其中 $\delta$ 是一个事先指定的很小的正数。- 如果此条件满足，则退出循环。
- 如果此条件不满足，则进行 Policy Improvement.
基于求解的 State Value 更新 Policy.
\[
\pi_{k+1} = \mathrm{arg} \max\limits_{\pi}(r_{\pi} + \gamma P_{\pi} v_{\pi_k})
\]
根据贪心策略：
\[
\begin{align}
\begin{cases}
\pi_{k+1}(a|s) = 1, a = a_{\pi_k}^*(s) \\
\pi_{k+1}(a|s) = 0, a \neq a_{\pi_k}^*(s) \\
\end{cases}
\end{align}
\]
- Policy Evaluation
观察 Truncated Policy Iteration 的流程，我们可能有这样的疑问：State Value 的最大迭代次数 $j_{max}$ 到底取多少比较合适呢？