VI&PI truncated policy iteration

Truncated Policy Iteration

Compare value iteration and policy iteration

Policy iteration: start from ${\pi }_0$

• Policy evaluation (PE) $$v_{{\pi }_k}=r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k}$$
• Policy improvement (PI) $${\pi }_{k+1}=\arg \underset{\pi }{\max }(r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k})$$

Value iteration: start from $v_0$

• Policy update (PU) $${\pi }_{k+1}=\arg \underset{\pi }{\max }(r_{\pi }+\gamma P_{\pi }{v}_k)$$
• Value update (VU) $$v_{k+1}=r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_k$$

PE=policy evaluation, PI=policy improvement, PU=policy update, VU=value update

$$\begin{array}{rl}& \text{Policy iteration:}{\pi }_0\stackrel{PE}{\to }{v}_{{\pi }_0}\stackrel{PI}{\to }{\pi }_1\stackrel{PE}{\to }{v}_{{\pi }_1}\stackrel{PI}{\to }{\pi }_2\stackrel{PE}{\to }{v}_{{\pi }_2}\stackrel{PI}{\to }\dots \\ & \text{Value iteration:}{u}_0\stackrel{PU}{\to }{\pi }_1^{\prime }\stackrel{VU}{\to }{u}_1\stackrel{PU}{\to }{\pi }_2^{\prime }\stackrel{VU}{\to }{u}_2\stackrel{PU}{\to }\dots \end{array}$$

Algorithm

$$\boxed{\begin{array}{rl}& \text{Algorithm}\text{Truncated Policy Iteration}\\ & \text{Input: }\text{Probability models }p(r|s,a)\text{ and }p(s^{\prime }|s,a),\text{ max iterations }{j}_{\text{truncate}}.\\ & \text{Initialization: }\text{Initial guess }{\pi }_0.\\ & \text{While }{v}_k\text{ not converged:}\\ & \text{Policy Evaluation:}\\ & \text{Initialize: }{v}_k^{(0)}\text{ arbitrarily}.\\ & \text{For }j=0\text{ to }{j}_{\text{truncate}}-1:\\ & \text{For each }s\in \mathcal{S}:\\ & v_k^{(j+1)}(s)\leftarrow \sum _a{\pi }_k(a|s)\left[\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_k^{(j)}(s^{\prime })\right]\\ & v_k\leftarrow v_k^{(j_{\text{truncate}})}\text{(Update value function)}\\ & \text{Policy Improvement:}\\ & \text{For each }s\in \mathcal{S}:\\ & \text{For each }a\in \mathcal{A}(s):\\ & q_k(s,a)\leftarrow \sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_k(s^{\prime })\text{(Q-computation)}\\ & a_k^{\ast }(s)\leftarrow \arg \underset{a}{\max }{q}_k(s,a)\text{(Greedy selection)}\\ & {\pi }_{k+1}(a|s)\leftarrow \{\begin{array}{ll}1& \text{if }a=a_k^{\ast }(s)\\ 0& \text{otherwise}\end{array}\text{(Policy update)}\end{array}}$$

Policy Iteration(PI) vs. Value Iteration(VI) vs. Trucated Policy Iteration(TPI)

$$\begin{array}{rl}{v}_{{\pi }_1}^{(0)}& =v_0\\ \text{value iteration}\leftarrow v_{{\pi }_1}^{(1)}& =r_{{\pi }_1}+\gamma P_{{\pi }_1}{v}_{{\pi }_1}^{(0)}\\ v_{{\pi }_1}^{(2)}& =r_{{\pi }_1}+\gamma P_{{\pi }_1}{v}_{{\pi }_1}^{(1)}\\ ⋮& \\ \text{truncated policy iteration}\leftarrow v_{{\pi }_1}^{(j)}& =r_{{\pi }_1}+\gamma P_{{\pi }_1}{v}_{{\pi }_1}^{(j-1)}\\ ⋮& \\ \text{policy iteration}\leftarrow v_{{\pi }_1}^{(\infty )}& =r_{{\pi }_1}+\gamma P_{{\pi }_1}{v}_{{\pi }_1}^{(\infty )}\end{array}$$

实际上三个算法的效果为PI>TPI>VI，而且通过TPI，可以很清晰的将价值迭代和策略迭代之间的关系紧密联系起来：

1. PI的Policy evaluation部分和VI的Value update部分的公式是一样的，都是通过Bellman equation来更新状态价值函数，但是有所区别的是PI中的Policy evaluation部分需要迭代至收敛，而VI中的Policy update部分只需要一次迭代。
2. 观察TPI中的$j_{\text{truncate}}$，当这个参数为1时（再交换一下Policy evaluation和Policy improvement的顺序，同时保持pe中的$v_0$继承最新那个v），TPI就退化为VI，当这个参数为$\infty$时，TPI就变成了PI，所以TPI是PI和VI的一个折中方案。