課程這週要我們閱讀 textbook 的 Chapter 4 (Dynamic programming) 稍微瞄了一下內容是有關 policy iteration

但我決定採用 赵世钰老師的課程 Chapter 4 來筆記, 因為能更清楚理解底層數學原理和關係.

主要介紹 3 種方法:

• Value iteration algorithm
• Policy iteration algorithm
• Truncated policy iteration algorithm

第4课 Part1-值迭代算法

其實 Value iteration 算法在 week3 的時候最後有筆記了, 簡單回顧一下

BOE 式子為:

$$ \begin{align} v=\max_\pi(r_\pi+\gamma P_\pi v) \end{align} $$

我們令為 $f(v)$ 為 BOE 的右式

$$ f(v)\triangleq \max_\pi(r_\pi+\gamma P_\pi v) $$

則 BOE 等於是在求解一個 fixed point problem!

$$ v=f(v) $$

可以證明 $f(v)$ 是一個 contraction mapping, 所以 contraction mapping theorem 告訴我們 $\exists!$ fixed point, 並且告訴我們求解的演算法:

$$ \begin{align} v_{k+1}=f(v_k)=\max_\pi(r_\pi+\gamma P_\pi v_k),\quad k=0,1,2,... \end{align} $$

這個演算法其實就是 value iteration algorithm!