Value iteration algorithm
之前已经介绍了 Bellman Optimality Equation：
并且，我们也可以通过 contraction mapping theorem ，通过迭代的方法求解：
其中 可以是随机的.
这种方法就称为 value iteration.
Algorithm description
整个算法可以分为两步:
- Step 1: policy update 这一步就是通过求解右侧的优化问题，得到一个新的 policy
其中 给定
- Step 2: value update 这一步就是在上一步的基础上，通过迭代得到
注意：在这里 并不是 state value! 只是过程中间满足 Bellman Equation 的一个向量而已，它可以是任何向量！
Elementwise form
- Step 1: Policy update
该公式的 elementwise form为：
求解上述优化问题的 optimal policy 为：
其中 。 被称为 greedy policy，因为它仅仅选择最大的 q-value。
- Step 2: Value update
该公式的 elementwise form为：
因为 是 greedy 的，上述等式可以简化为：
Pseudocode
Policy iteration algorithm
Algorithm description
给定一个随机的 initial policy ，
- Step 1: Policy evaluation (PE) 这一步是为了计算 的 state value
注意 是一个 state value function。
- Step 2: Policy improvement (PI)
这个最大化是 componentwise (逐分量) 进行的！
Elementwise form
Step 1: Policy evaluation Details
- Matrix-vector form:
- Elementwise form:
当 或足够大，或者足够小时停止。
Step 2: Policy improvement Details
- Matrix-vector form:
- Elementwise form:
这里，是 policy 下的 action value。
令
那么，greedy policy 为
Pseudocode
Truncated policy iteration algorithm
Compare value iteration and policy iteration
Policy iteration: start from (从 开始)
- Policy evaluation (PE):
- Policy improvement (PI):
Value iteration: start from (从 开始，收敛至 )
- Policy update (PU):
- Value update (VU):
这两个算法非常相似：
Policy iteration:
Value iteration:
- PE = policy evaluation
- PI = policy improvement
- PU = policy update
- VU = value update
考虑求解 的步骤：
- Value iteration algorithm 只计算 一次。
- Policy iteration algorithm 计算无数次迭代。
- Truncated policy iteration algorithm 计算有限次迭代，比如次。剩下的从到 的迭代被 truncated了。
Pseudocode
