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ī)劃需要滿足的兩個(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