一、Introduction

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

Dynamic：問題的動態(tài)順序或時間成分
Programming：優(yōu)化“程序”，即policy
我們認(rèn)為問題是擁有某種時間或順序方面的特性，也就是問題一步接一步地進行改變，我們嘗試某些特殊的步驟來解決這些問題。
數(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)原則)

任何最佳策略都可以細(xì)分為兩個部分

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

定理（Principle of Optimality）
一個策略 $\pi(a|s)$ 從狀態(tài)s獲得最佳值, $v_\pi(s)=v_*(s)$ ,當(dāng)且僅當(dāng)
從 $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

我們認(rèn)為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)是目標(biāo)朝向了我們源方向，這說明迭代通過一次掃描所有的狀態(tài)，我們就能找到最佳的解決方案。你不需要進行不同的掃描，因為你是從目標(biāo)出開始的，你找到了目標(biāo)的最優(yōu)值，你回退一步，現(xiàn)在你插入的最新的value，然后再該狀態(tài)再回退一步，插入最新value，再回退......。一直使用最新的估計來進行更新，這樣會更加高效。加入你掃描到其他東西，那么你什么都不會得到。因此，排序真的很重要。

2、Prioritised Sweeping

思想：找到評估MDP狀態(tài)重要性的標(biāo)準(zhǔn)。現(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)方程估算目標(biāo)值
  
  使用目標(biāo) $\{\left\langle s,{\widetilde v}_k(s)\right\rangle\}$ 訓(xùn)練下一個value function $\widehat v(\cdot,w_{k+1})$

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

Lecture 3: Planning by Dynamic Programming

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