04 Value Iteration & Policy Iteration

• First algorithms for optimal policies
• Three algorithms:
  • value iteration vi
  • policy iteration pi
  • truncated policy iteration
• Two updates
  • policy update
  • value update
• Need the enviroment model

Outline

1. Value iteration algorithm
2. Policy iteration algorithm
3. Truncated policy iteration algorithm

Summary

• Value iteration: iterative algorithm solving BOE given an initial value ($v_0$)

$$v_{k+1}=\underset{\pi }{\max }(r_{\pi }+\gamma P_{\pi }{v}_k)\iff \{\begin{array}{ll}\text{Policy update:}& {\pi }_{k+1}=\arg {\max }_{\pi }(r_{\pi }+\gamma P_{\pi }{v}_k)\\ \text{Value update:}& v_{k+1}=r_{{\pi }_{k+1}}+\gamma P_{{\pi }_{k+1}}{v}_k\end{array}$$

• Policy iteration: given an initial policy (${\pi }_0$)

$$\{\begin{array}{ll}\text{Policy evaluation:}& v_{{\pi }_k}=r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k}\\ \text{Policy improvement:}& {\pi }_{k+1}=\arg {\max }_{\pi }(r_{\pi }+\gamma P_{\pi }{v}_{{\pi }_k})\end{array}$$

• Truncated policy iteration: a mix of value and policy iteration

一些想法

1. 随着策略迭代的过程，其实是先靠近目标状态的策略开始变好，离目标状态远一点的策略后变好；
2. 直观的用走迷宫的例子去说明价值迭代和策略迭代：
   • 价值迭代就是人想一步(policy update)走一步(value update)，然后看着迷宫上的value再想再下
   • 策略迭代就是先从随便一个迷宫value来评估自己的策略会最终导致什么样的局面（policy evaluation），根据最终局面的看哪个方法好用哪个（policy improvement）

Later

model-based & model-free

Policy iteration和Value iteration通常被认为是dynamic programming的方法，但是其实也是属于model-based的方法，model-based通常指的是可以知道环境的$p(s^{\prime }|s,a),p(r|s,a)$，也可以是基于数据的方式来得到环境模型的估计；之后我们将介绍model-free的MC方法。

with model to without model⇒ 05 Monte Carlo Methods