強化學習入門基于模型的強化學習課件

強化學習入門第二講郭憲2017.3.4強化學習入門第二講郭憲1強化學習的形式化強化學習目標：

環(huán)境機器人觀測回報r動作

新的狀態(tài)S狀態(tài)轉移概率

馬爾科夫決策問題(MDP):四元組

策略：常采用隨機策略：

累積回報:

折扣回報:

值函數(shù)最優(yōu)策略：

序貫決策問題強化學習的形式化強化學習目標：

環(huán)境機器人觀測動作

新的狀態(tài)2強化學習方法分類序貫決策問題馬爾科夫決策過程MDP

基于模型的動態(tài)規(guī)劃方法無模型的強化學習方法

策略迭代值迭代策略搜索本節(jié)講基于模型的策略迭代算法和值迭代算法策略搜索offlineonline策略迭代offlineonline值迭代offlineonline強化學習方法分類序貫決策問題馬爾科夫決策過程MDP

基于模3動態(tài)規(guī)劃動態(tài)規(guī)劃是一類算法：包括離散和連續(xù)。動態(tài)：蘊含著序列決策規(guī)劃：蘊含著優(yōu)化，如線性優(yōu)化，二次優(yōu)化或者非線性優(yōu)化。動態(tài)規(guī)劃可以解決的問題：1.整個優(yōu)化問題可以分解成多個子優(yōu)化問題2.子優(yōu)化問題的解可以被存儲和重復利用馬爾科夫決策過程（MDP），貝爾曼最優(yōu)性原理，得到貝爾曼最優(yōu)化方程：

動態(tài)規(guī)劃可以解決MDP的問題核心：動態(tài)規(guī)劃通過值函數(shù)來迭代構造最優(yōu)解動態(tài)規(guī)劃動態(tài)規(guī)劃是一類算法：包括離散和連續(xù)。動態(tài)：蘊含著序列4策略評估(policyevaluation)給定策略構造值函數(shù)：

模型已知，方程組中只有值函數(shù)是未知數(shù)，方程組是線性方程組。未知數(shù)的數(shù)目等于狀態(tài)的數(shù)目。采用數(shù)值迭代算法策略評估(policyevaluation)給定策略構5策略評估(policyevaluation)

高斯-賽德爾迭代策略評估算法輸入：需要評估的策略狀態(tài)轉移概率回報函數(shù)，折扣因子

初始化值函數(shù)：

Repeatk=0,1,…

foreverysdo

Until

輸出：

一次狀態(tài)掃描[1][2][3][5][4][6][7][8]策略評估(policyevaluation)

高斯-賽德6策略評估(policyevaluation)策略評估算法輸入：需要評估的策略狀態(tài)轉移概率回報函數(shù)，折扣因子

初始化值函數(shù)：

Repeatk=0,1,…

foreverysdo

Until

輸出：

一次狀態(tài)掃描狀態(tài)空間：S={1,2..14}動作空間:{東，南，西，北}回報函數(shù)：-1，直到終止狀態(tài)均勻隨機策略：

1234567810911121314動作MDP策略評估(policyevaluation)策略評估算法輸7策略評估算法輸入：需要評估的策略狀態(tài)轉移概率回報函數(shù)，折扣因子

初始化值函數(shù)：

Repeatk=0,1,…

foreverysdo

Until

輸出：

一次狀態(tài)掃描策略評估(policyevaluation)-1.0-1.0-1.0-1.0-1.0-1.0-1.0-1.0-1.0-1.0-1.0-1.0-1.0-1.0K=10.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.0K=00.0-1.7-2.0-2.0-2.0-2.0-2.0-2.0-1.7-2.0-2.0-1.7-2.0-2.0-1.7K=20.00.0-2.4-2.9-3.0-2.9-2.9-3.0-2.9-2.4-2.9-3.0-2.4-3.0-2.9-2.4K=30.00.0策略評估算法輸入：需要評估的策略狀態(tài)轉移概率回報函8策略改進(policyimprovement)計算策略值的目的是為了幫助找到更好的策略，在每個狀態(tài)采用貪婪策略。

-14-20-22-20-18-20-18-14-20-20-14-22-20-140.00.0

0.00.0-6.1-8.4-9.0-8.4-7.7-8.4-7.7-6.1-8.4-8.4-6.1-9.0-8.4-6.1K=100.00.00.00.0

max

策略改進(policyimprovement)計算策略值的9策略迭代(policyiteration)策略評估策略改進

Policyimprovement策略迭代算法輸入：狀態(tài)轉移概率回報函數(shù)，折扣因子

初始化值函數(shù)：初始化策略

輸出：Repeatl=0,1,…

find

Policyevaluation

Until

[1][2][3][5][4][6]策略迭代(policyiteration)策略評估策略改進10值函數(shù)迭代策略改進一定要等到值函數(shù)收斂嗎？當K=1時便進行策略改進，得到值函數(shù)迭代算法

-6.1-8.4-9.0-8.4-7.7-8.4-7.7-6.1-8.4-8.4-6.1-9.0-8.4-6.1K=100.00.00.00.0

0.00.0-14-20-22-20-18-20-18-14-20-20-14-22-20-140.00.0

輸入：狀態(tài)轉移概率回報函數(shù)，折扣因子

初始化值函數(shù)：初始化策略

輸出：

UntilRepeatl=0,1,…

foreverysdo

[1][2][3][5][4][6]值函數(shù)迭代策略改進一定要等到值函數(shù)收斂嗎？當K=1時便進行策11值函數(shù)迭代與最優(yōu)控制輸入：狀態(tài)轉移概率回報函數(shù)，折扣因子

初始化值函數(shù)：初始化策略

輸出：

UntilRepeatl=0,1,…

foreverysdo

值函數(shù)迭代算法狀態(tài)方程：性能指標函數(shù)：最優(yōu)控制問題：Bellman最優(yōu)性原理：2.利用變分法，將微分方程轉化成變分代數(shù)方程，在標稱軌跡展開，得到微分動態(tài)規(guī)劃DDP1.將值函數(shù)進行離散，進行數(shù)值求解。值函數(shù)迭代與最優(yōu)控制輸入：狀態(tài)轉移概率回報函數(shù)，12值函數(shù)迭代與最優(yōu)控制輸入：狀態(tài)轉移概率回報函數(shù)，折扣因子

初始化值函數(shù)：初始化策略

輸出：

UntilRepeatl=0,1,…

foreverysdo

值函數(shù)迭代算法此式是關于值函數(shù)的偏微分方程，利用數(shù)值算法可進行迭代計算值函數(shù)。From胡亞楠博士論文值函數(shù)迭代與最優(yōu)控制輸入：狀態(tài)轉移概率回報函數(shù)，13值函數(shù)迭代與最優(yōu)控制輸入：狀態(tài)轉移概率回報函數(shù)，折扣因子

初始化值函數(shù)：初始化策略

輸出：

UntilRepeatl=0,1,…

foreverysdo

值函數(shù)迭代算法

貪婪策略：

利用變分法，將微分方程轉化成變分代數(shù)方程值函數(shù)迭代與最優(yōu)控制輸入：狀態(tài)轉移概率回報函數(shù)，14微分動態(tài)規(guī)劃方法微分動態(tài)規(guī)劃：1.前向迭代：給定初始控制序列正向迭代計算標稱軌跡2.反向迭代：由代價函數(shù)邊界條件反向迭代計算（1）,（2）,(3)得到

序列

（1）（3）（2）3.正向迭代新的控制序列：微分動態(tài)規(guī)劃方法微分動態(tài)規(guī)劃：1.前向迭代：給定初始控制序15值函數(shù)迭代與最優(yōu)控制輸入：狀態(tài)轉移概率回報函數(shù)，折扣因子

初始化值函數(shù)：初始化策略

輸出：

UntilRepeatl=0,1,…

foreverysdo

值函數(shù)迭代算法微分動態(tài)規(guī)劃：1.前向迭代：給定初始控制序列正向迭代計算標稱軌跡2.反向迭代：由代價函數(shù)邊界條件反向迭代計算（1）,（2）,(3)得到

序列

3.正向迭代新的控制序列：值函數(shù)迭代與最優(yōu)控制輸入：狀態(tài)轉移概率回報函數(shù)，16基于模型的其他方法逼近動態(tài)規(guī)劃（逼近值函數(shù)）基于模型的策略搜索（dynamic）異步動態(tài)規(guī)劃實時動態(tài)規(guī)劃Guidedpolicysearch基于模型的其他方法逼近動態(tài)規(guī)劃（逼近值函數(shù)）17強化學習入門第二講郭憲2017.3.4強化學習入門第二講郭憲18強化學習的形式化強化學習目標：

環(huán)境機器人觀測回報r動作

新的狀態(tài)S狀態(tài)轉移概率

馬爾科夫決策問題(MDP):四元組

策略：常采用隨機策略：

累積回報:

折扣回報:

值函數(shù)最優(yōu)策略：

序貫決策問題強化學習的形式化強化學習目標：

環(huán)境機器人觀測動作

新的狀態(tài)19強化學習方法分類序貫決策問題馬爾科夫決策過程MDP

基于模型的動態(tài)規(guī)劃方法無模型的強化學習方法

策略迭代值迭代策略搜索本節(jié)講基于模型的策略迭代算法和值迭代算法策略搜索offlineonline策略迭代offlineonline值迭代offlineonline強化學習方法分類序貫決策問題馬爾科夫決策過程MDP

基于模20動態(tài)規(guī)劃動態(tài)規(guī)劃是一類算法：包括離散和連續(xù)。動態(tài)：蘊含著序列決策規(guī)劃：蘊含著優(yōu)化，如線性優(yōu)化，二次優(yōu)化或者非線性優(yōu)化。動態(tài)規(guī)劃可以解決的問題：1.整個優(yōu)化問題可以分解成多個子優(yōu)化問題2.子優(yōu)化問題的解可以被存儲和重復利用馬爾科夫決策過程（MDP），貝爾曼最優(yōu)性原理，得到貝爾曼最優(yōu)化方程：

動態(tài)規(guī)劃可以解決MDP的問題核心：動態(tài)規(guī)劃通過值函數(shù)來迭代構造最優(yōu)解動態(tài)規(guī)劃動態(tài)規(guī)劃是一類算法：包括離散和連續(xù)。動態(tài)：蘊含著序列21策略評估(policyevaluation)給定策略構造值函數(shù)：

模型已知，方程組中只有值函數(shù)是未知數(shù)，方程組是線性方程組。未知數(shù)的數(shù)目等于狀態(tài)的數(shù)目。采用數(shù)值迭代算法策略評估(policyevaluation)給定策略構22策略評估(policyevaluation)

高斯-賽德爾迭代策略評估算法輸入：需要評估的策略狀態(tài)轉移概率回報函數(shù)，折扣因子

初始化值函數(shù)：

Repeatk=0,1,…

foreverysdo

Until

輸出：

一次狀態(tài)掃描[1][2][3][5][4][6][7][8]策略評估(policyevaluation)

高斯-賽德23策略評估(policyevaluation)策略評估算法輸入：需要評估的策略狀態(tài)轉移概率回報函數(shù)，折扣因子

初始化值函數(shù)：

Repeatk=0,1,…

foreverysdo

Until

輸出：

一次狀態(tài)掃描狀態(tài)空間：S={1,2..14}動作空間:{東，南，西，北}回報函數(shù)：-1，直到終止狀態(tài)均勻隨機策略：

1234567810911121314動作MDP策略評估(policyevaluation)策略評估算法輸24策略評估算法輸入：需要評估的策略狀態(tài)轉移概率回報函數(shù)，折扣因子

初始化值函數(shù)：

Repeatk=0,1,…

foreverysdo

Until

輸出：

一次狀態(tài)掃描策略評估(policyevaluation)-1.0-1.0-1.0-1.0-1.0-1.0-1.0-1.0-1.0-1.0-1.0-1.0-1.0-1.0K=10.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.0K=00.0-1.7-2.0-2.0-2.0-2.0-2.0-2.0-1.7-2.0-2.0-1.7-2.0-2.0-1.7K=20.00.0-2.4-2.9-3.0-2.9-2.9-3.0-2.9-2.4-2.9-3.0-2.4-3.0-2.9-2.4K=30.00.0策略評估算法輸入：需要評估的策略狀態(tài)轉移概率回報函25策略改進(policyimprovement)計算策略值的目的是為了幫助找到更好的策略，在每個狀態(tài)采用貪婪策略。

-14-20-22-20-18-20-18-14-20-20-14-22-20-140.00.0

0.00.0-6.1-8.4-9.0-8.4-7.7-8.4-7.7-6.1-8.4-8.4-6.1-9.0-8.4-6.1K=100.00.00.00.0

max

策略改進(policyimprovement)計算策略值的26策略迭代(policyiteration)策略評估策略改進

Policyimprovement策略迭代算法輸入：狀態(tài)轉移概率回報函數(shù)，折扣因子

初始化值函數(shù)：初始化策略

輸出：Repeatl=0,1,…

find

Policyevaluation

Until

[1][2][3][5][4][6]策略迭代(policyiteration)策略評估策略改進27值函數(shù)迭代策略改進一定要等到值函數(shù)收斂嗎？當K=1時便進行策略改進，得到值函數(shù)迭代算法

-6.1-8.4-9.0-8.4-7.7-8.4-7.7-6.1-8.4-8.4-6.1-9.0-8.4-6.1K=100.00.00.00.0

0.00.0-14-20-22-20-18-20-18-14-20-20-14-22-20-140.00.0

輸入：狀態(tài)轉移概率回報函數(shù)，折扣因子

初始化值函數(shù)：初始化策略

輸出：

UntilRepeatl=0,1,…

foreverysdo

[1][2][3][5][4][6]值函數(shù)迭代策略改進一定要等到值函數(shù)收斂嗎？當K=1時便進行策28值函數(shù)迭代與最優(yōu)控制輸入：狀態(tài)轉移概率回報函數(shù)，折扣因子

初始化值函數(shù)：初始化策略

輸出：

UntilRepeatl=0,1,…

foreverysdo

值函數(shù)迭代算法狀態(tài)方程：性能指標函數(shù)：最優(yōu)控制問題：Bellman最優(yōu)性原理：2.利用變分法，將微分方程轉化成變分代數(shù)方程，在標稱軌跡展開，得到微分動態(tài)規(guī)劃DDP1.將值函數(shù)進行離散，進行數(shù)值求解。值函數(shù)迭代與最優(yōu)控制輸入：狀態(tài)轉移概率回報函數(shù)，29值函數(shù)迭代與最優(yōu)控制輸入：狀態(tài)轉移概率回報函數(shù)，折扣因子

初始化值函數(shù)：初始化策略

輸出：

UntilRepeatl=0,1,…

foreverysdo

值函數(shù)迭代算法此式是關于值函數(shù)的偏微分方程，利用數(shù)值算法可進行迭代計算值函數(shù)。From胡亞楠博士論文值函數(shù)迭