Planning by Dynamic Programming

image.png

Dynamic Programming

1. 具有某種時(shí)序關(guān)系的問(wèn)題。

2. 將復(fù)雜的問(wèn)題分解為子問(wèn)題，結(jié)合子問(wèn)題的解決方案，即動(dòng)態(tài)規(guī)劃。

   
   
   image.png

動(dòng)態(tài)規(guī)劃需要滿(mǎn)足的兩個(gè)要求

1. 最優(yōu)化結(jié)構(gòu)，即將整合結(jié)構(gòu)問(wèn)題分解為兩個(gè)或多個(gè)子問(wèn)題。
2. 重疊子問(wèn)題，對(duì)于多次出現(xiàn)的子問(wèn)題，子問(wèn)題的最優(yōu)解可以多次利用。
3. MDP符合這兩種特性和貝爾曼方程。

4. 貝爾曼方程可以理解為，當(dāng)前步采取最優(yōu)的行動(dòng)，余下的其他步驟也將采取最優(yōu)的行動(dòng)，從而獲得整體最優(yōu)值（value function）。

   
   
   image.png

Planning 問(wèn)題

1. 預(yù)測(cè)問(wèn)題：已知Policy，求得最多的獎(jiǎng)勵(lì)。

2. 控制問(wèn)題：尋找最好的Policy，使這個(gè)MDP獲得最大獎(jiǎng)勵(lì)。

   
   
   image.png

Dynamic Programming 適用

1. 生物信息學(xué)中序列比對(duì)。

2. 圖論算法。

   
   
   image.png

Policy Evaluation

1. 貝爾曼方程評(píng)估Policy。
2. 通過(guò)迭代更新 value function。

3. 同步備份，每一次迭代，都將用到全部的MDP中的狀態(tài)用于更新value function。

   
   
   image.png

貝爾曼方程

1. 葉子結(jié)點(diǎn)儲(chǔ)存我們上一次迭代的 value function ， 通過(guò)動(dòng)態(tài)規(guī)劃方式，得到一個(gè)新的value function。

   
   
   image.png

例子 評(píng)估一個(gè)已知的（random）Policy

1. 采用最簡(jiǎn)單的Policy，即向四個(gè)方向移動(dòng)的概率都是1/4.

   
   
   image.png

2. 使用動(dòng)態(tài)規(guī)劃的方法求解value function。

3. 某位置當(dāng)前時(shí)刻四個(gè)方向移動(dòng)獲得的reward + 上一步四個(gè)方向移動(dòng)獲得的reward 除以4得到當(dāng)前value function 位置的值。

4. 根據(jù)動(dòng)態(tài)規(guī)劃，更新value function，同時(shí)得到最優(yōu)的Policy（右邊）。

   
   
   image.png

5. value function 的值最終會(huì)穩(wěn)定。

   
   
   image.png

Policy Iteration

1. 2- step
   1.1 評(píng)估一個(gè)policy，就像上一步所做的，填數(shù)字，計(jì)算出policy能夠得到的分?jǐn)?shù)。
   1.2 貪心算法，右邊最后就是最有policy。
   1.3 MDP中總是存在一個(gè)最優(yōu)的Policy。

   
   
   image.png

2. 向上的箭頭表示評(píng)估（貝爾曼方程）， 向下的過(guò)程表示對(duì)value function 使用貪心算法更新Policy。最終收斂到最優(yōu)Policy和真實(shí)的value function。

   
   
   image.png

image.png

image.png

更精準(zhǔn)的描述下 Policy Inprovement

1. 每一步都取argmax，則更新后的policy至少和開(kāi)始采取的policy得到的一樣多。

2. 所以更新后的policy只會(huì)獲得更好的得分。

   
   
   image.png

3. 最優(yōu)解穩(wěn)定

   
   
   image.png

Modified Policy Iteration

1. 基本思想：提前停止
   1.1 觀察貝爾曼方程 value function的更新幅度。
   1.2 控制迭代次數(shù)。

   
   
   image.png

image.png

Principle of Optimlity

image.png

1. 將value function看作是對(duì)所有子問(wèn)題的兌現(xiàn)方案，是后向傳播算法，及知道最優(yōu)解，更新非葉子結(jié)點(diǎn)value function。

2. 通過(guò)循環(huán)整個(gè)狀態(tài)空間，迭代找到最優(yōu)貝爾曼方程，而不是通過(guò)反向傳播。

   
   
   image.png
3. 同上面的小方格計(jì)算不同，這是一種反向傳播從而獲得最短路徑的方法。
4. 基于已有的完備知識(shí)（我們知道這個(gè)結(jié)構(gòu)是如何工作的），我們就不需要更新每一個(gè)狀態(tài)，只需要從初始狀態(tài)feedback就可以獲得我們關(guān)心的狀態(tài)。

5. 沒(méi)有終點(diǎn)狀態(tài)，我們的算法依舊能夠運(yùn)行。

   
   
   image.png

value iteration

1. Policy iteraction 中迭代（value function + policy（greedy））。

2. 每一步?jīng)]有確定的policy，只有value function的迭代更新。沒(méi)有創(chuàng)建新的policy，只是中間步驟。

   
   
   image.png

3. 每次迭代將會(huì)返回根節(jié)點(diǎn)，利用貝爾曼方程最大化期望，從而更新value function，獲得最優(yōu)的value function。

   
   
   image.png

動(dòng)態(tài)規(guī)劃算法

1. 預(yù)測(cè)問(wèn)題：已知policy，可以得到多少獎(jiǎng)勵(lì)。貝爾曼方程定義了約束方程，得到.
2. 控制問(wèn)題： 如何從已知MDP中獲得最大獎(jiǎng)勵(lì)，獲得， 最優(yōu)policy。
   2.1 policy iteration
   2.2 value iteration： 使用貝爾曼最優(yōu)方程，求解最大值，通過(guò)value function自我迭代求得最大值。
   
   image.png

拓展

image.png

image.png

1. 三種異步更新方法。

   
   
   image.png

image.png

1. 使用某個(gè)軌跡的真實(shí)樣本。

   
   
   image.png

總結(jié)

1. DP使用全尺寸 ，考慮所有的action和所有的后繼狀態(tài)。

   
   
   image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png