Lecture 3: Planning by Dynamic Programming

一、Introduction

（一）什么是動態(tài)規(guī)劃（Dynamic Programming）

Dynamic：問題的動態(tài)順序或時間成分
Programming：優(yōu)化“程序”抬驴，即policy
我們認為問題是擁有某種時間或順序方面的特性看尼，也就是問題一步接一步地進行改變丧叽，我們嘗試某些特殊的步驟來解決這些問題骚灸。
數(shù)學(xué)規(guī)劃：線性規(guī)劃或二次規(guī)劃，它的含義就是像數(shù)學(xué)家一樣驴一，使用程序優(yōu)化程序，它實質(zhì)上指的就是一種policy灶壶。案例：從狀態(tài)到動作的映射開始肝断，然后你不斷優(yōu)化程序，以采取最優(yōu)行為驰凛。

解決復(fù)雜問題的方法
通過將它們分解為子問題
- 解決子問題
- 結(jié)合解決子問題

（二）動態(tài)規(guī)劃的要求

對于具有兩個屬性的問題胸懈，動態(tài)規(guī)劃是一種非常通用的解決方案：

最優(yōu)化結(jié)構(gòu)

應(yīng)用最優(yōu)原理
最優(yōu)解可以分解為子問題

最優(yōu)化結(jié)構(gòu)的含義是我們刻意將某些整體性問題分解為兩個或多個子問題，在得到子問題的最優(yōu)解后我們也就知道了整體問題的最優(yōu)解恰响。

重疊子問題

子問題重復(fù)出現(xiàn)多次
解決方案可以緩存和重用

我們不會對不滿足以上兩個條件的問題使用動態(tài)規(guī)劃

馬爾可夫決策過程同時滿足這兩個屬性

貝爾曼方程提供遞歸分解
值函數(shù)存儲和重用解決方案
緩存我們目前找到的MDP的最優(yōu)值信息趣钱，通過value function可以找到任一狀態(tài)出發(fā)的解決方法，可以找到最優(yōu)的行動方式

（三）Planning by Dynamic Programming

動態(tài)規(guī)劃假定您完全了解MDP
知道MDP的結(jié)構(gòu)胚宦，MDP中的動態(tài)變化和獎勵首有，完全了解環(huán)境的工作原理燕垃。
用于MDP中的計劃
對于預(yù)測來說:
- Input:MDP $\left\langle S,A,P,R,\gamma\right\rangle$ and policy $\pi$
- or:MRP $\left\langle S,P^\pi,R^\pi,\gamma\right\rangle$
- Output:value function $v_\pi$
  在知道policy的情況下球的更多的獎勵
或者對于control
- Input:MDP $\left\langle S,A,P,R,\gamma\right\rangle$
- Output:value function $v_\pi$
- and:最優(yōu)policy $\pi_*$
  我們并不知道policy，我們想知道在所有的policy中選擇哪一個才會在MDP中得到最多的獎勵井联。

（四）動態(tài)規(guī)劃的其他應(yīng)用

動態(tài)規(guī)劃用于解決許多其他問題卜壕，例如：

調(diào)度算法
字符串算法（如：序列比對）
圖算法（如：最短路徑算法）
圖模型問題（如：Viterbi algorithm）‘
生物信息學(xué)（如：晶格模型）

二、Policy Evaluation

（一）Iterative Policy Evaluation

問題：評估給定的策略 $\pi$
解決方案：Bellman期望備份的迭代應(yīng)用
$v_1\rightarrow v_2\rightarrow ...\rightarrow v_\pi$
使用同步備份
- 在每次迭代k + 1
- 對于所有狀態(tài) $s\in S$
- 從 $v_k(s')$ 更新 $v_{k+1}(s)$
- 其中 $s’$ 是 $s$ 的后繼狀態(tài)
稍后我們將討論異步備份
講座結(jié)束時將證明 $v_\pi$ 的收斂

使用貝爾曼方程來評估policy烙常，解決control問題轴捎，你知道了MDP和policy，采取這個policy獎勵會是多少蚕脏。

$v_1$ 是一個向量侦副，也就是MDP的value，從某個初始的value開始驼鞭，一般初始取0（0表示我們沒有在任何地方得到任何指令）秦驯，接下來每一步都要用貝爾曼方程，向前看一步终议，就能找到一個新的value函數(shù) $v_2$ 汇竭，迭代多次，得到真正的value函數(shù)穴张。

（二）Iterative Policy Evaluation（2）

image.png

為了實現(xiàn)動態(tài)規(guī)劃我們將會將這個方程轉(zhuǎn)化為迭代更新操作细燎。
我們在葉節(jié)點存儲我們先前迭代的value，然后就可以求得下一次迭代的value皂甘。
將k迭代產(chǎn)生的值插入到葉節(jié)點玻驻，通過存儲的這些值，我們就能計算出路徑下一次迭代產(chǎn)生的一個新value

（三）Evaluating a Random Policy in the Small Gridworld

在小型網(wǎng)格世界中評估隨機策略

沒有折扣情況的MDP（ $\gamma=1$ ）
非終端狀態(tài) 1,...,14
一個終端狀態(tài)（以陰影正方形顯示兩次）
退出網(wǎng)格的動作保持狀態(tài)不變
直到達到最終狀態(tài)偿枕，獎勵為-1
agent遵循統(tǒng)一的隨機策略

image.png

（四）Iterative Policy Evaluation in Small Gridworld

image.png

-1.7如何得到璧瞬？
應(yīng)用公式

image.png

在本問題中，公式中,,,（因為執(zhí)行一個action只能到達一個狀態(tài)）
向北走：得到即時獎勵-1渐夸，回到原地嗤锉，加上上一步原地的value為-1，
向南走：得到即時獎勵-1墓塌，到下個狀態(tài)瘟忱，加上上一步該狀態(tài)的value為-1，
向西走：得到即時獎勵-1苫幢，到下個狀態(tài)访诱，加上上一步該狀態(tài)的value為0，
向東走：得到即時獎勵-1韩肝，到下個狀態(tài)触菜，加上上一步該狀態(tài)的value為-1，
將上述四項加到一塊哀峻，

image.png

右邊的policy是根據(jù)左邊的value值涡相，應(yīng)用貪婪算法得到的哲泊，可以發(fā)現(xiàn)到最后policy是可以收斂的，因為k=3的時候policy就不再改變漾峡。

三攻旦、Policy Iteration

（一）如何改進policy

提供一個policy
- 評估policy $\pi$
- 應(yīng)用貪婪的方法來改進policy $\pi$
在Small Gridworld中，改進策略是最佳的生逸， $\pi'=\pi^*$
一般而言牢屋，需要進行更多迭代的改進/評估
但是，此策略迭代過程始終收斂于 $\pi^*$

無論你從哪里開始槽袄，無論你的value函數(shù)是什么烙无、policy是什么，最終你總會得到最優(yōu)的value函數(shù)和最優(yōu)的policy遍尺。

示例：杰克的租車

States：兩個地點截酷，每個地點最多20輛車
Actions：一夜之間在各地點之間最多可移動5輛汽車
Reward：每輛租車$ 10（必須可以得到）
Transitions：汽車歸還和請求是隨機的
- 泊松分布，n個歸還/請求乾戏，概率為 $\frac{\lambda^n}{n!}e^{-\lambda}$
- 第一個位置：平均請求數(shù)= 3迂苛，平均歸還= 3
- 第二個位置：平均請求數(shù)= 4，平均歸還= 2
  
  policy輪廓圖鼓择，數(shù)字表示從一個位置往另一個位置移動幾輛車
  
  首先是一個隨機policy三幻，然后用value function，然后用value function得到new policy呐能，然后再用value function評估念搬，然后得到更新的policy，然后再評估摆出，最終得到最優(yōu)policy朗徊。

（二）Policy Improvement

考慮一個確定性策略， $a =\pi(s)$
我們可以通過貪婪的方法改進這個策略
這就可以一步提高任何狀態(tài)s的值

找到使得q的值最大的action偎漫，這個action比之前一個特定的action要好爷恳。
因此，它改善了價值函數(shù)象踊， $v_\pi'(s)\geq v_\pi(s)$
如果改進停止
然后滿足Bellman最優(yōu)方程
因此對所有的 $s\in S$ , $v_\pi(s)=v_*(s)$
所以 $\pi$ 是最優(yōu)policy

（三）Extensions to Policy Iteration

1舌仍、Modified Policy Iteration

修改的策略迭代
基本思想：提前停止迭代

policy評估需要收斂到 $v_\pi$ 嗎？
還是應(yīng)該引入停止條件
- 例如value function 的 $\varepsilon-convergence$
還是在k次迭代策略評估后停止通危？
例如，在小型網(wǎng)格世界中灌曙，k = 3足以實現(xiàn)最佳策略
為什么不每次迭代都更新策略菊碟？即在k = 1之后停止
- 這等效于值迭代（下一部分）

2、Generalised Policy Iteration

廣義策略迭代

policy evaluation algorithm在刺、policy improvement algorithm不再是固定的逆害，可以用任意的算法

四头镊、Value Iteration

（一）Value Iteration in MDPs

1、Principle of Optimality(最優(yōu)原則)

任何最佳策略都可以細分為兩個部分

最佳的第一個動作 $A_*$
緊隨后繼狀態(tài)S'的最優(yōu)策略

定理（Principle of Optimality）
一個策略 $\pi(a|s)$ 從狀態(tài)s獲得最佳值, $v_\pi(s)=v_*(s)$ ,當且僅當
從 $s$ 可到達的任意狀態(tài) $s'$
$\pi$ 從狀態(tài) $s'$ 獲得最佳值魄幕， $v_\pi(s’)=v_*(s')$

2相艇、Deterministic Value Iteration（確定性值迭代）

如果我們知道子問題 $v_*(s')$ 的解決方案
然后可以通過一步查找來找到解決方案 $v_*(s)$
價值迭代的思想是迭代地應(yīng)用這些更新
直覺：從最終的獎勵開始，然后倒退
仍適用于循環(huán)的纯陨，隨機的MDP

3坛芽、Example: Shortest Path

應(yīng)用此公式進行計算

每移動一步得到的獎勵為-1，翼抠，
因為每個action只能到唯一一個后繼狀態(tài)咙轩，

-1=max{
向北：即時獎勵-1，加上回到原地的上個狀態(tài)value=0阴颖，相加為-1活喊；
向南：即時獎勵-1，加上到達的下個格子的上個狀態(tài)value=0量愧，相加為-1钾菊；
向西：即時獎勵-1，加上到達的下個格子的上個狀態(tài)value=0偎肃，相加為-1煞烫；
向東：即時獎勵-1，加上到達的下個格子的上個狀態(tài)value=0软棺，相加為-1红竭；}
-2=max{
向北：即時獎勵-1，加上回到原地的上個狀態(tài)value=-1喘落，相加為-2茵宪；
向南：即時獎勵-1，加上到達的下個格子的上個狀態(tài)value=-1瘦棋，相加為-2稀火；
向西：即時獎勵-1，加上到達的下個格子的上個狀態(tài)value=-1赌朋，相加為-2凰狞；
向東：即時獎勵-1，加上到達的下個格子的上個狀態(tài)value=-1沛慢，相加為-2赡若；}
-3=max{
向北：即時獎勵-1，加上回到原地的上個狀態(tài)value=-2团甲，相加為-3逾冬；
向南：即時獎勵-1，加上到達的下個格子的上個狀態(tài)value=-2，相加為-3身腻；
向西：即時獎勵-1产还，加上到達的下個格子的上個狀態(tài)value=-2，相加為-3嘀趟；
向東：即時獎勵-1脐区，加上到達的下個格子的上個狀態(tài)value=-2，相加為-3她按；}
-3=max{
向北：即時獎勵-1牛隅，加上到達的下個格子的上個狀態(tài)value=-5，相加為-6尤溜；
向南：即時獎勵-1倔叼，加上回到原地的上個狀態(tài)value=-5，相加為-6宫莱；
向西：即時獎勵-1丈攒，加上到達的下個格子的上個狀態(tài)value=-5，相加為-6授霸；
向東：即時獎勵-1巡验，加上到達的下個格子的上個狀態(tài)value=-5，相加為-6碘耳；}
-6=max{
向北：即時獎勵-1显设，加上回到原地的上個狀態(tài)value=-5，相加為-6辛辨；
向南：即時獎勵-1捕捂，加上到達的下個格子的上個狀態(tài)value=-2，相加為-6斗搞；
向西：即時獎勵-1指攒，加上回到原地的上個狀態(tài)value=-5，相加為-6僻焚；
向東：即時獎勵-1允悦，加上到達的下個格子的上個狀態(tài)value=-2，相加為-6虑啤；}

4隙弛、Value Iteration

問題：找到一個最優(yōu)的policy $\pi$
方法：迭代應(yīng)用貝爾曼最優(yōu)備份（Bellman optimality backup）
$v_1\rightarrow v_2\rightarrow ... \rightarrow v_*$
用同步備份（synchronous backups）
- 在每個迭代 $k+1$
- 對于每個states $s\in S$
- 從 $v_k(s')$ 更新 $v_{k+1}(s)$
收斂到 $v_*$ 稍后將證明.
與policy Iteration 不同，這里沒有明確的policy
中間值函數(shù)（value function）可能不符合任何policy

我們認為value function是對所有子問題的兌現(xiàn)方案狞山，最優(yōu)的value是來自 $s'$ ,有人告訴我們全闷，我會從那個狀態(tài)獲得多少獎勵，現(xiàn)在問題是我們該如何利用這些信息來構(gòu)造一個先前那一步驟的最優(yōu)value函數(shù)萍启，我們需要做的是向前看一步总珠，為了構(gòu)造這棵樹我們使用了貝爾曼最優(yōu)方程。

我們來看看這棵樹的樹葉，樹葉將他們存儲起來姚淆，我們歸納的前提是：我們的最優(yōu)解來自于我們的樹葉，我們將這個存儲起來我們最大化的所有的東西屡律，那么在根處腌逢，我們就得到了最優(yōu)值，value迭代的思想是不斷地重復(fù)更新超埋，從任意值開始搏讶，我們會很直觀的找到答案，把這個存儲起來霍殴，我們就得到了一個新的value函數(shù)媒惕，存儲新的value函數(shù)得到更好的value函數(shù)。

5来庭、Example of Value Iteration in Practice

http://www.cs.ubc.ca/~poole/demos/mdp/vi.html

6妒蔚、Synchronous Dynamic Programming Algorithms（同步動態(tài)規(guī)劃算法）

算法基于狀態(tài)值函數(shù) $v_\pi(s)$ 或 $v_*(s)$
對于m個動作和n個狀態(tài)，每次迭代的復(fù)雜度 $O(mn^2)$
n種狀態(tài)月弛，每個狀態(tài)可以執(zhí)行m個action肴盏，每個action又可能有n個后繼狀態(tài)输虱。
還可應(yīng)用與action-value函數(shù) $q_\pi(s,a)$ 或q_*(s,a)
每次迭代的復(fù)雜度 $O(m^2n^2)$
總共有mn個每個action-value對婿滓，后繼有mn個action-value對，所以為 $m^2n^2$

五镇草、Extension to Dynamic Programming

（一）Asynchronous Dynamic Programming

異步動態(tài)編程

到目前為止介紹的DP方法使用了同步備份
即所有狀態(tài)都并行備份
異步DP以任何順序分別備份狀態(tài)
一般來說厉萝，你可以挑選任何state恍飘，并將該state進行備份。你可以立即行動谴垫，可以立即插入你的新的value函數(shù)章母，它會在底部進行備份，你并不需要等待全部狀態(tài)更新完弹渔。你需要更新的是單一的狀態(tài)胳施，而不是整個狀態(tài)空間。
對于每個選定狀態(tài)肢专，應(yīng)用合適的備份
可以大大減少計算
如果繼續(xù)選擇所有狀態(tài)舞肆，則保證收斂
不管你選擇的順序是怎么樣的，只要你持續(xù)選擇博杖，那么你的算法都會收斂到最優(yōu)value函數(shù)椿胯。

異步動態(tài)規(guī)劃的三個簡單思路：

In-place dynamic programming
Prioritised sweeping
Real-time dynamic programming
實時動態(tài)規(guī)劃

1、In-Place Dynamic Programming

Synchronous value iteration存儲值函數(shù)的兩個副本
對于S中的所有s
In-place value iteration僅存儲值函數(shù)的一個副本
對于S中的所有s

放棄了區(qū)分新的和舊的剃根，將它進行掃描哩盲，然后無論我們的次序是什么，我們總是使用最新的版本，我們會即時更新我們的value函數(shù)廉油，無論我們到了哪一種狀態(tài)惠险，我們將會使用的是最新的value，因為最新的value包含更多的信息抒线，會更高效班巩。
唯一的問題是你該如何安排state的次序，才能以最有效的方式進行計算嘶炭。這表明知道問題的某些狀態(tài)抱慌，你可以更加高效的進行計算。它就像一條長廊眨猎，我們掃描到了那個狀態(tài)抑进，即該狀態(tài)是目標朝向了我們源方向，這說明迭代通過一次掃描所有的狀態(tài)睡陪，我們就能找到最佳的解決方案寺渗。你不需要進行不同的掃描，因為你是從目標出開始的宝穗，你找到了目標的最優(yōu)值户秤，你回退一步，現(xiàn)在你插入的最新的value逮矛，然后再該狀態(tài)再回退一步鸡号，插入最新value，再回退......须鼎。一直使用最新的估計來進行更新鲸伴，這樣會更加高效。加入你掃描到其他東西晋控，那么你什么都不會得到汞窗。因此，排序真的很重要赡译。

2仲吏、Prioritised Sweeping

思想：找到評估MDP狀態(tài)重要性的標準。現(xiàn)在我們知道了你可以以任何順序更新你的狀態(tài)蝌焚。我們應(yīng)該首先更新哪些狀態(tài)呢裹唆？
我們來組織一個優(yōu)先級序列，來看看哪個狀態(tài)相較于其他狀態(tài)更好只洒。我們會以某種順序進行更新许帐，依據(jù)就是state的重要性。

使用Bellman誤差的幅度指導(dǎo)狀態(tài)選擇

我們的直覺告訴我們毕谴，改變最多的state成畦，比如：更新之前該狀態(tài)value是0距芬，更新之后value狀態(tài)為1000，這將會對之后的計算產(chǎn)生巨大的影響循帐。
備份保存的Bellman誤差最大的狀態(tài)
每次備份后更新受影響狀態(tài)的Bellman誤差
需要了解逆向動態(tài)（先前狀態(tài)）
通過組織優(yōu)先級隊列可以有效地實現(xiàn)

3框仔、Real-Time Dynamic Programming

思想：選擇那些agent真正訪問過的state。我們并不是簡單的掃描所有的東西拄养，實際上是存和，在真實環(huán)境中運行一個agent，搜集真正的樣本衷旅，使用來自某個軌跡的真正的樣本。

想法：僅與agent相關(guān)的狀態(tài)
運用agent的經(jīng)驗來指導(dǎo)狀態(tài)的選擇
在每個時間步 $S_t纵朋，A_t柿顶，R_{t + 1}$ 之后
備份狀態(tài) $S_t$

（二）Full-width and sample backups

1、Full-Width Backups

DP使用full-width備份
對于每個備份（同步或異步）
- 每個后繼的狀態(tài)和動作都被考慮
- 使用有關(guān)MDP轉(zhuǎn)換和reward function的知識
DP對中等規(guī)模的問題（數(shù)百萬個狀態(tài)）有效
對于大問題操软，DP受到貝爾曼的維數(shù)詛咒
- 狀態(tài)數(shù) $n = |S|$ 隨狀態(tài)變量數(shù)呈指數(shù)增長
即使一次備份也可能太昂貴

2嘁锯、Sample Backups

在隨后的課程中，我們將考慮樣本備份
使用sample rewards and sample transitions $\left\langle S,A,R,S'\right\rangle$
代替reward function $R$ 和transition dynamics $P$
Advantages:
- Model-free：無需MDP的先驗知識
- 通過采樣打破維數(shù)的詛咒
- 備份成本是恒定的聂薪，與 $n = |S|$ 無關(guān)

3家乘、Approximate Dynamic Programming

近似value function
使用函數(shù)逼近器 $\widehat v(s,W)$
將動態(tài)規(guī)劃應(yīng)用于 $\widehat v(\cdot,W)$
例如:擬合值迭代在每個迭代k重復(fù)一次，
- Sample states $\widetilde S\subseteq S$
- 對于每個狀態(tài) $s\in\widetilde S$ 藏澳，使用Bellman最優(yōu)方程估算目標值
  
  使用目標 $\{\left\langle s,{\widetilde v}_k(s)\right\rangle\}$ 訓(xùn)練下一個value function $\widehat v(\cdot,w_{k+1})$

六仁锯、Contraction Mapping

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市翔悠，隨后出現(xiàn)的幾起案子业崖，更是在濱河造成了極大的恐慌，老刑警劉巖蓄愁，帶你破解...
沈念sama閱讀 217,185評論 6贊 503
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件双炕，死亡現(xiàn)場離奇詭異，居然都是意外死亡撮抓，警方通過查閱死者的電腦和手機妇斤，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,652評論 3贊 393
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來丹拯，“玉大人站超，你說我怎么就攤上這事⊙柿” “怎么了顷编？”我有些...
開封第一講書人閱讀 163,524評論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長剑刑。經(jīng)常有香客問我媳纬，道長双肤，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 58,339評論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任钮惠，我火速辦了婚禮茅糜，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘素挽。我一直安慰自己蔑赘，他們只是感情好，可當我...
茶點故事閱讀 67,387評論 6贊 391
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布预明。她就那樣靜靜地躺著缩赛，像睡著了一般。火紅的嫁衣襯著肌膚如雪撰糠。梳的紋絲不亂的頭發(fā)上酥馍，一...
開封第一講書人閱讀 51,287評論 1贊 301
城市分裂傳說
那天，我揣著相機與錄音阅酪，去河邊找鬼旨袒。笑死，一個胖子當著我的面吹牛术辐，可吹牛的內(nèi)容都是我干的砚尽。我是一名探鬼主播，決...
沈念sama閱讀 40,130評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼辉词，長吁一口氣：“原來是場噩夢啊……” “哼必孤！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起瑞躺，我...
開封第一講書人閱讀 38,985評論 0贊 275
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤隧魄，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后隘蝎，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體购啄，經(jīng)...
沈念sama閱讀 45,420評論 1贊 313
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,617評論 3贊 334
?白月光啟示錄
正文我和宋清朗相戀三年嘱么，在試婚紗的時候發(fā)現(xiàn)自己被綠了狮含。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點故事閱讀 39,779評論 1贊 348
活死人
序言：一個原本活蹦亂跳的男人離奇死亡曼振，死狀恐怖几迄，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情冰评，我是刑警寧澤映胁，帶...
沈念sama閱讀 35,477評論 5贊 345
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站甲雅，受9級特大地震影響解孙，放射性物質(zhì)發(fā)生泄漏坑填。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點故事閱讀 41,088評論 3贊 328
男人毒藥：我在死后第九天來索命
文/蒙蒙一弛姜、第九天我趴在偏房一處隱蔽的房頂上張望脐瑰。院中可真熱鬧，春花似錦苍在、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,716評論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽莱没。三九已至掠剑，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間郊愧，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 32,857評論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工井佑，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留属铁，地道東北人。一個月前我還...
沈念sama閱讀 47,876評論 2贊 370
代替公主和親
正文我出身青樓躬翁，卻偏偏與公主長得像焦蘑，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子盒发，可洞房花燭夜當晚...
茶點故事閱讀 44,700評論 2贊 354

Lecture 3: Planning by Dynamic Programming

一、Introduction

（一） 什么是動態(tài)規(guī)劃（Dynamic Programming）

（二）動態(tài)規(guī)劃的要求

（三）Planning by Dynamic Programming

（四）動態(tài)規(guī)劃的其他應(yīng)用

二、Policy Evaluation

（一）Iterative Policy Evaluation

（二）Iterative Policy Evaluation（2）

（三）Evaluating a Random Policy in the Small Gridworld

（四）Iterative Policy Evaluation in Small Gridworld

三攻旦、Policy Iteration

（一）如何改進policy

示例：杰克的租車

（二）Policy Improvement

（三）Extensions to Policy Iteration

1舌仍、Modified Policy Iteration

2、Generalised Policy Iteration

四头镊、Value Iteration

（一）Value Iteration in MDPs

1、Principle of Optimality(最優(yōu)原則)

2相艇、Deterministic Value Iteration（確定性值迭代）

3坛芽、Example: Shortest Path

4隙弛、Value Iteration

5来庭、Example of Value Iteration in Practice

6妒蔚、Synchronous Dynamic Programming Algorithms（同步動態(tài)規(guī)劃算法）

五镇草、Extension to Dynamic Programming

（一）Asynchronous Dynamic Programming

1、In-Place Dynamic Programming

2仲吏、Prioritised Sweeping

3框仔、Real-Time Dynamic Programming

（二）Full-width and sample backups

1、Full-Width Backups

2嘁锯、Sample Backups

3家乘、Approximate Dynamic Programming

六仁锯、Contraction Mapping

推薦閱讀更多精彩內(nèi)容

（一）什么是動態(tài)規(guī)劃（Dynamic Programming）