Reinforcement Learning - VI-PI

a Model-Based RL Algorithm

 

 

 

1. Value Iteration

这个算法在 Reinforcement Learning - Basics 4.3 中已经简要介绍过

Bellman Optimality Equation 的 Iterative Solution，目的是寻找 State Value $v^{\ast }$$v^*$

即 BOE 的 Unique Fixed Point Solution $v_{\pi }^{\ast }$$v^*_{\pi}$ 满足

该 Unique Fixed Point 可以用如下方式迭代解得

本部分，此算法会被用于寻找 Optimal Policy

 

 

1.1 Algorithm

• Step 0 - Initialization

  需要提供的内容

  1. $p(r_{t+1}|s_t,a_t),p(s_{t+1}|s_t,a_t)⟶$$p(r_{t+1}|s_t,a_t),\; p(s_{t+1}|s_t,a_t) \longrightarrow$ Probabilistic Environment Models

  2. $v_0⟶$$v_0 \longrightarrow$ State Value Initial Guess

• Step 1 - Policy Update (PU)

  solve with given $v_k$$v_k$

  $${\pi }_{k+1}=\arg \underset{\pi }{max}[r_{\pi }+\gamma P_{\pi }{v}_k]$$

  以 Elementwise Form 表达

  $${\pi }_{k+1}(a_t|s_t)=\arg \underset{\pi }{max}\sum _{a_t}\{\pi (a_t|s_t)\cdot \underset{q_k(s_t,a_t)}{\underbrace{(\sum _{r_{t+1}}[p(r_{t+1}|s_t,a_t)r_{t+1}]+\gamma \sum _{s_{t+1}}[p(s_{t+1}|s_t,a_t)v_k(s_{t+1})])}}\}\mathrm{\forall }s\in \mathcal{S}$$

  只需要代入 $v_k$$v_k$，然后最大化 $q_k$$q_k$ 即可找到符合上式的 Optimal Greedy Policy

  $$\begin{array}{c}{\pi }_{k+1}(a_t|s_t)=\{\begin{array}{ll}1& a_t=a_k^{\ast }(s_t)\\ 0& a_t\ne a_k^{\ast }(s_t)\end{array}\text{where}{a}_k^{\ast }=\arg \underset{a_t}{max}{q}_k(s_t,a_t)\end{array}$$

• Step 2 - Value Update (VU)

  find next value $v_{k+1}$$v_{k+1}$ with

  $$v_{k+1}=r_{{\pi }_{k+1}}+\gamma P_{{\pi }_{k+1}}{v}_k$$

  以 Elementwise Form 表达，则是代入 ${\pi }_{k+1}(a_t|s_t)$$\pi_{k+1}(a_t|s_t)$ 得

  $$v_{k+1}(s_t)=\sum _{a_t}\{{\pi }_{k+1}(a_t|s_t)\cdot \underset{q_k(s_t,a_t)}{\underbrace{(\sum _{r_{t+1}}[p(r_{t+1}|s_t,a_t)r_{t+1}]+\gamma \sum _{s_{t+1}}[p(s_{t+1}|s_t,a_t)v_k(s_{t+1})])}}\}\mathrm{\forall }s\in \mathcal{S}$$

  由于是 Greedy Policy，所以 Value Update 实际上只需下式即可

  $$v_{k+1}(s_t)=\underset{a_t}{max}{q}_k(s_t,a_t)\mathrm{\forall }s\in \mathcal{S}$$

  Policy 为唯一一个能最大化 Action Value 的 $a_t^{\ast }$$a^*_t$，也就是

  $$\sum _{a_t}{\pi }_{k+1}(a_t|s_t)=1+0+0+\cdots +0=1$$

  然后代入 Elementwise Form，你会发现整件寻找 Next Value 的事情与 Policy 是什么无关

  因为 Policy 本身有 Greedy 的特性，只有最大的那个 Action Value 会被留下作为 $v_{k+1}$$v_{k+1}$

  你可能会觉得 Environment Model 需要 Update，但实际上并不需要

 

 

1.2 Pseudo Code

 

 

1.3 Example

在下图的场景中

• 黄色的 $s_2$$s_2$ 为禁区，蓝色的 $s_4$$s_4$ 为目的地

• Reward 设置

  • $r_{forbid}=r_{bound}=-1$$r_{forbid} = r_{bound} = -1$

  • $r_{target}=1$$r_{target} = 1$

• Discount Rate 设置 $\gamma =0.9$$\gamma = 0.9$

• Action Space 设置 $a_1,a_2,a_3,a_4,a_5=$$a_1,a_2,a_3,a_4,a_5 =$ 上, 右, 下, 左, 不动

那么该场景的 Q-Table 为

Assume the initial guess at $k=0$$k = 0$ is

现在演算 Value Iteration

• At $k=0$$k = 0$

  

  Q-Table 代入 $v_0$$v_0$ 后得到上表，标红数据为每个 State 最大的 Action Value / Q-Value

  • Policy Update

    $${\pi }_1(a_5|s_1)=1{\pi }_1(a_3|s_2)=1{\pi }_1(a_2|s_3)=1{\pi }_1(a_5|s_4)=1$$

    State $s_1$$s_1$ 有两个 Action 可以选，此处采用 Greedy Policy，所以就随便挑一个，比如 $a_5$$a_5$

  • Value Update

    $$\begin{array}{c}{v}_1=\left[\begin{array}{c}{v}_1(s_1)\\ v_1(s_2)\\ v_1(s_3)\\ v_1(s_4)\end{array}\right]=\left[\begin{array}{c}0\\ 1\\ 1\\ 1\end{array}\right]\end{array}$$

  • Policy Visualized

    

• At $k=1$$k = 1$

  

  Q-Table 代入 $v_1$$v_1$ 后得到上表，标红数据为每个 State 最大的 Action Value / Q-Value

  • Policy Update

    $${\pi }_2(a_3|s_1)=1{\pi }_2(a_3|s_2)=1{\pi }_2(a_2|s_3)=1{\pi }_2(a_5|s_4)=1$$

  • Value Update

    $$\begin{array}{c}{v}_2=\left[\begin{array}{c}{v}_2(s_1)\\ v_2(s_2)\\ v_2(s_3)\\ v_2(s_4)\end{array}\right]=\left[\begin{array}{c}0+1\times 0.9\\ 1+1\times 0.9\\ 1+1\times 0.9\\ 1+1\times 0.9\end{array}\right]=\left[\begin{array}{c}0.9\\ 1.9\\ 1.9\\ 1.9\end{array}\right]\end{array}$$

  • Policy Visualized

    

显然，迭代两次就已足以找出 Optimal Policy 了

 

 

 

2. Policy Iteration

这是一个只在理论中存在 的算法，可以理解为与 Value Iteration 相对的一个极端，这一点会在 3. Truncated Policy Iteration 中解释

2.1 ALgorithm

• Step 0 - Initialization

  需要提供的内容：Random Initial Policy ${\pi }_0$$\pi_0$

• Step 1 - Policy Evaluation (PE)

  Find State Value $v_{{\pi }_k}$$v_{\pi_k}$ given Policy ${\pi }_k$$\pi_k$

  $$v_{{\pi }_k}=r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k}$$

  其实就是解个 Bellman Expectation Equation:

  1. Closed-Form Solution

     $$v_{\pi }=(I-\gamma P_{\pi }{)}^{-1}{r}_{\pi }$$

     看起来很美好，但是由于需要求 Inverse Matrix，计算麻烦，直接否决

  2. Iterative Solution

     $$v_{{\pi }_k}^{(j+1)}=r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k}^{(j)}\text{where }{v}_{{\pi }_k}^{(j)}\to v_{{\pi }_k}\text{ as }j\to \mathrm{\infty }$$

     这个是合适的解法，所以 Policy Iteration 不止本身是一个迭代算法，还嵌套了另一个迭代算法

     以 Elementwise Form 表达

     $$v_{{\pi }_k}^{(j+1)}(s_t)=\sum _{a_t}\{{\pi }_k(a_t|s_t)\cdot \underset{q_{{\pi }_k}(s_t,a_t)}{\underbrace{(\sum _{r_{t+1}}[p(r_{t+1}|s_t,a_t)r_{t+1}]+\gamma \sum _{s_{t+1}}[p(s_{t+1}|s_t,a_t)v_{{\pi }_k}^{(j)}(s_{t+1})])}}\}\mathrm{\forall }s\in \mathcal{S}$$

     这一步就是 Policy Iteration 只存在于理论中的原因

     因为按照严格定义，你得真的算到无穷，而不是只算到收敛

• Step 2 - Policy Improvement (PI)

  Plug in derived $v_{{\pi }_k}$$v_{\pi_k}$, solve for improved policy ${\pi }_{k+1}$$\pi_{k+1}$

  $${\pi }_{k+1}=\arg \underset{\pi }{max}[r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k}]$$

  以 Elementwise Form 表达

  $${\pi }_{k+1}(a_t|s_t)=\arg \underset{\pi }{max}\sum _{a_t}\{{\pi }_k(a_t|s_t)\cdot \underset{q_{{\pi }_k}(s_t,a_t)}{\underbrace{(\sum _{r_{t+1}}[p(r_{t+1}|s_t,a_t)r_{t+1}]+\gamma \sum _{s_{t+1}}[p(s_{t+1}|s_t,a_t)v_{{\pi }_k}(s_{t+1})])}}\}\mathrm{\forall }s\in \mathcal{S}$$

  将求得的 $v_{{\pi }_k}$$v_{\pi_k}$ 代入上式即可解得 Improved Greedy Policy

  $$\begin{array}{c}{\pi }_{k+1}(a_t|s_t)=\{\begin{array}{ll}1& a_t=a_k^{\ast }(s_t)\\ 0& a_t\ne a_k^{\ast }(s_t)\end{array}\text{where}{a}_k^{\ast }=\arg \underset{a_t}{max}{q}_{{\pi }_k}(s_t,a_t)\end{array}$$

  为什么能断言 ${\pi }_{k+1}$$\pi_{k+1}$ 会比 ${\pi }_{\pi }$$\pi_{\pi}$ 更好？或者说，为什么能保证 $v_{{\pi }_{k+1}}\ge v_{{\pi }_k}$$v_{\pi_{k+1}} \geq v_{\pi_{k}}$？

  从定义来看有

  $$\begin{array}{rl}{\pi }_{k+1}& =\arg \underset{\pi }{max}[r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k}]\\ v_{{\pi }_k}& =r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k}\\ v_{{\pi }_{k+1}}& =r_{{\pi }_{k+1}}+\gamma P_{{\pi }_{k+1}}{v}_{{\pi }_{k+1}}\end{array}$$

  所以可以确定

  $$\begin{array}{rl}{r}_{{\pi }_{k+1}}+\gamma P_{{\pi }_{k+1}}{v}_{{\pi }_{k+1}}& \ge r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k}\\ v_{{\pi }_{k+1}}& \ge v_{{\pi }_k}\end{array}$$

 

 

2.2 Pseudo Code

 

 

2.3 Example 1

在下图的场景中

• 蓝色的 $s_2$$s_2$ 为目的地

• Reward 设置

  • $r_{bound}=-1$$r_{bound} = -1$

  • $r_{target}=1$$r_{target} = 1$

• Discount Rate 设置 $\gamma =0.9$$\gamma = 0.9$

• Action Space 设置 $a_l,a_0,a_r=$$a_l,a_0,a_r =$ 左, 不动, 右

• Initial Guess 设置 ${\pi }_0$$\pi_0$ 为全部 $a_l$$a_l$，即初始状态为左图

现在演算 Policy Iteration

• At $k=0$$k = 0$, Policy Evaluation

  方便起见，不用 Iterative Solution 直接解

  $$\begin{array}{c}\{\begin{array}{rl}{v}_{{\pi }_0}(s_1)& =-1+0.9\times v_{{\pi }_0}(s_1)\\ v_{{\pi }_0}(s_2)& =0+0.9\times v_{{\pi }_0}(s_2)\end{array}⟶\{\begin{array}{rl}{v}_{{\pi }_0}(s_1)& =-10\\ v_{{\pi }_0}(s_2)& =-9\end{array}\end{array}$$

• At $k=0$$k = 0$, Policy Improvement

  该场景的 Q-Table 为

  

  代入上一步求得的 $v_{{\pi }_k}$$v_{\pi_k}$ 可得

  

  标红数据为每个 State 最大的 Action Value / Q-Value，得到的 Improved Policy 为

  $${\pi }_1(a_r|s_1)=1{\pi }_1(a_0|s_2)=1$$

• At $k=1$$k = 1$, Done

  如右图中 Final Optimal Policy 所示，只用了一次迭代就达到了最优

 

 

2.4 Example 2

在下图的场景中

• 黄色区域为禁区，蓝色区域为目的地

• Reward 设置

  • $r_{forbid}=-10$$r_{forbid} = -10$

  • $r_{bound}=-1$$r_{bound} = -1$

  • $r_{target}=1$$r_{target} = 1$

• Discount Rate 设置 $\gamma =0.9$$\gamma = 0.9$

图中的 (a) ~ (h) 展示了 Policy Iteration 改进 Policy 的效果：

• 未优化 $⟶$$\longrightarrow$ 绿色 Action

• 已优化 $⟶$$\longrightarrow$ 粉色 Action

• 正在被优化 $⟶$$\longrightarrow$ 红色方框套绿色 Action

你会发现优化是有顺序的：离目的地越近的 State 越先被优化

 

 

 

3. Truncated Policy Iteration

这是一种介于 Value Iteration 和 Policy Iteration 之间的算法，如果对比一下两种算法

你会发现，除了 Policy Iteration 初始化了 ${\pi }_0$$\pi_0$，两种算法关于 Policy 的步骤都是相同的，即 Step 3 / 5 实际作用相同，都是通过现有的 Value 获取一个更好的 Policy，而区别在于各自使用的 Value 是什么

两种算法关于 Value 的步骤 Step 4 都与 Bellman Expectation Equation 的 Iterative Solution 相关

可以看出

• Value Iteration 要求是 Iterate 一次

• Policy Iteration 要求是 Iterate 到无穷，在实操中就是迭代到收敛

• Truncated Policy Iteration 要求是 Iterate 到指定次数

所以 Truncated Policy Iteration 的步骤 / Pseudo Code 和 Policy Iteration (see 2.2) 大体是一样的

只需要改动一下套在最外面的 while 停止条件，让 $\lambda$$\lambda$ 从收敛条件变成最大 Iterate 次数即可

[Question] Truncation 会影响收敛性吗？

不会

可证得在 BEE 的 Iterative Solution 中 $v_{{\pi }_k}^{(j+1)}\ge v_{{\pi }_k}^{(j)}$$v_{\pi_k}^{(j+1)}\geq v_{\pi_k}^{(j)}$

因此你迭代 $1$$1$ 次 Value 会变大，迭代 $j$$j$ 次 Value 也会变大，只是收敛速度的问题