本文介紹增強學習和自适應控制。
在監督學習中，算法是要輸出盡量模仿訓練集中的标簽 y，标簽給每個輸入 x 一個清楚的正确答案。與此不同，對于許多序列決策和控制問題，就很難對算法給出這種明确的監督。例如，如果要造一個四足機器人，并程式設計讓它行走，起初我們并不知道讓它行走的正确行動，是以也不知道怎麼模仿學習算法給出明确的監督。
在增強學習架構中，我給算法一個回報函數，告訴學習代理執行得好壞。在四足行走的機器人例子中，當機器人往前走時，回報函數就給予正回報，退後或者摔倒就給予負回報。學習算法的工作就是弄清楚怎麼随着時間選擇動作，以使總回報最大。
增強學習的應用非常廣泛，如無人機、運動機器人、蜂窩電話網絡路由、市場政策選擇、工業控制和高效的頁面排序。我們對增強學習的研究将從 MDP 馬爾科夫決策過程開始，形式化增強學習遇到的問題。
1、馬爾可夫決策過程
一個馬爾可夫決策過程是元組 (S,A,{Psa},γ,R)，其中：
- S 是狀态集合。（例如，在無人機飛行中，S 可以是直升機所有可能的位置和方向）
- A 是動作集合。（例如，直升機操縱杆能夠轉動的所有方向）
- Psa 是狀态轉換機率。對每一個狀态 s∈S 和動作 a∈A，Psa 是在狀态空間上的分布。簡單地說，Psa 給定的是，當在狀态 s 采取行動 a，我們會變成哪種狀态的分布機率。
- γ 是折扣因子。
- R：S×A—>R 是回報函數。（回報有時寫成隻有狀态 S 的函數，R：S—>R）
MDP 執行的動态過程如下：從狀态 s0 開始，在 MDP 中選擇一些動作 a0∈A 來執行，作為選擇的結果，根據 s1~Ps0a0， MDP 的狀态随機切換到後繼狀态 s1，然後再選擇另外一個動作 a1，作為動作的結果，根據 s2~Ps1a1，狀态再次切換，然後選擇 a2，等等。周期性的，這個過程可表示如下：
通路狀态序列 s0,s1,...，并執行動作 a0,a1,...，總回報為：
或者，如果回報僅僅是狀态的函數，那麼總回報可寫作：
對大部分應用來說，我們會使用更簡單的狀态回報 R(s)，雖然狀态動作回報 R(s,a) 的泛化也沒有特别的困難。
增強學習的目标是随着時間選擇動作以最大化總回報的期望值：
時間點 t 的回報通過乘以因子 γt 打了折扣，是以為使期望最大，我們希望正回報來得越早越好，負回報盡量往後面去。在經濟應用中，R(·) 是掙錢的總金額，γ 自然可以解釋為利率（今天的一英鎊比明天的一英鎊值錢）。
一個政策是一些從狀态到動作的映射函數 π：S—>A。無論何時，我們在狀态 s 執行了動作 a=π(s)，就說在執行政策 π。定義 π 的值函數為：
V(s) 是從狀态 s 開始，根據政策 π 采取行動，最終的折扣回報期望和。
給定固定政策 π，它的值函數 Vπ 滿足 Bellman 方程：
也就是說，從 s 開始的折扣回報 Vπ(s) 的期望和由兩部分組成：第一，從狀态 s 開始的立即回報 R(s)，第二，未來折扣回報的期望和。仔細檢查第二項，和式可寫為：
這是從狀态 s' 開始的折扣回報的期望和，s' 符合分布 Psπ(s)，也就是從狀态 s 執行第一個動作 π(s) 後的狀态分布，是以，第二項給的是在 MDP 中第一步後的折扣回報的期望和。
Bellman 方程能用于高效解出 Vπ，特别是在一個有限狀态 MDP（|S|<∞），可以為每個狀态寫下這個方程 Vπ(s)，這給定了一個有 |S| 個變量（每個狀态都有個未知的 Vπ(S)）的 |S| 個線性方程的集合，可以有效解出 Vπ(s)。
定義最優值函數：
也就是能使用政策得到的最好的折扣回報期望和。還有另一個版本的 Bellman 方程。
第一項跟之前一樣是立即回報，第二項是執行動作 a 後的折扣回報未來期望和的最大值。要特别注意，這裡的 max 是要從所有動作中選擇回報最大的動作，而 max 後面的 γ 乘以求和項就是執行某動作後的回報期望。要確定你了解了上式的含義。
定義政策 π*：S—>A 如下：
π*(s) 給出了能使總回報最大的行動 a。
事實上，對每一個狀态和每一個政策有：
第一個等式是說 Vπ*，π* 的值函數，等于對每個狀态 s 來說的最優值函數 V*。第二個不等式是說，π* 的值至少跟其它政策一樣大。換句話說，π* 就是最優政策。
注意到 π* 有一個有趣的屬性，對所有的狀态它都是個最優政策。特别的，并不是說，如果從 s 開始就有針對那個狀态的最優政策，如果從其它的 s' 開始就有針對 s' 的其它最優政策。特别的，同樣的政策 π* 對所有的狀态都能獲得最大值，這意味着我們可以使用同樣的政策 π*，而不管 MDP 的初始狀态是什麼。
2、值疊代和政策疊代
現在介紹兩種解決有限狀态 MDP 的高效算法，這裡隻考慮有限狀态和動作空間的 MDP。
第一個算法，值疊代，如下：
這個算法可以看作是使用 Bellman 方程重複更新估計值函數。這裡 R(s) 是回報函數，V(s) 是值函數，注意這兩者的差別，有助于了解該算法。
有兩種方法執行算法内環的更新，第一種是，先對每一個狀态 s 計算新值 V(s)，并覆寫舊值，這被稱為同步更新；另一種是異步更新，以一定順序循環周遊狀态，一次更新一個值。
不管是同步更新還是異步更新，值函數 V 都會收斂到 V*，找到 V* 後，就能夠使用上面介紹過的如下方程找到最優政策。
除了值疊代，還有一種尋找最優政策的算法，政策疊代：
是以，内循環重複地為目前政策計算值函數，然後使用目前值函數更新政策。注意到步驟 (a) 可以通過解之前描述的 Bellman 方程來完成，在政策固定的情況下，它是一個有 |S| 個變量的 |S| 個線性方程的集合。
在算法的有限次疊代後，V 将收斂到 V*，π 将收斂到 π*。
值疊代和政策疊代都是解 MDP 的标準算法，關于哪個算法更好沒有一緻的看法。對于小的 MDPs，政策疊代經常很快，很少疊代就能收斂；但對于有大量狀态空間的 MDPs 來說，解 MDPs 會涉及大量線性方程，就比較困難，這種情況使用值疊代更好，由于這個原因，實際中值疊代會比政策疊代用得多。
3、為 MDP 學習一個模型
目前為止，我們讨論了 MDPs 和它的算法，假定狀态轉換矩陣和回報是已知的，在許多現實問題中，并不知道狀态轉換矩陣和清晰的回報，但可以從資料中估計出來。（通常 S，A 和 γ 是知道的）
例如，在倒立擺問題中，在 MDP 中有一些嘗試：
這裡 si(j) 表示我們在時間點 i 嘗試 j 時所處的狀态， ai(j) 是在那個狀态采取的相應動作。實際上，上面的每一次嘗試都可以一直運作直到 MDP 終止，或者運作一個很大但是有限的時間步。
有了這些在 MDP 中嘗試的經驗，我們就很容易推導出狀态轉換矩陣的最大似然估計。
如果上面的比率是 0/0，也就是說從沒在狀态 s 采取動作 a，那就簡單估計 Psa(s') 為 1/|S|，也就是估計 Psa 在所有狀态上均勻分布。
使用類似的過程，如果 R 是未知的，我們也可以估計狀态 s 的期望立即回報 R(s) 為在狀态 s 觀察到的平均回報。
從 MDP 中學習到一個模型後，就可以使用值疊代或者政策疊代來解 MDP，該 MDP 使用的是估計轉換機率和回報。例如，結合模型學習和值疊代，這是一個可能的算法，在狀态轉換矩陣未知的 MDP 中學習。
注意到針對這個算法，有一個簡單的優化能使它運作得更快。在使用值疊代的内循環中，如果不初始化 V=0，而是用算法上一輪疊代使用的結果，就會為值疊代提供一個更好的起始點，使它更快收斂。
4、連續狀态 MDPs
目前為止，我們讨論的都是有限狀态的 MDPs。現在讨論無限狀态的 MDPs 算法，例如，一輛汽車的狀态可以表示為 (x,y,θ,x.,y.,θ.)，(x,y) 是位置，方向 θ，x 和 y 方向的速度 x. 和 y.，θ 的角速度為 θ.。是以，S=R6 是一個無限狀态的集合，因為對于一輛車有無限個位置和方向。類似的，PS4 中的倒立擺的狀态為 (x,θ,x',θ')，θ 是杆的角度。直升機在 3D 空間中的狀态為 (x,y,z,Φ,θ,Ψ,x',y',z',Φ',θ',Ψ')，其中翻滾角 Φ，俯仰角 θ 和偏航角 Ψ 指定了飛機的 3D 方向。
下面我們讨論狀态空間 S=Rn 的情況，并描述解 MDPs 的方法。
4.1 離散化
或許解連續狀态 MDP 最簡單的方法就是離散化狀态空間，然後使用之前介紹的值疊代或政策疊代算法。
例如，如果是 2d 的狀态，那麼就可以用表格來離散化狀态空間：
這裡每一個表格單元代表一個分離的離散狀态 \(\overline{s}\) ，我們可以通過離散狀态 \((\overline{S},A,\{P_{\overline{s}a}\},γ,R)\) 來近似連續狀态的 MDP，其中 \( \overline{S}\) 是離散狀态的集合，\( P_{\overline{s}a}\) 是離散狀态的狀态轉換矩陣。我們可以使用值疊代或政策疊代來解出離散狀态 MDP \((\overline{S},A,\{P_{\overline{s}a}\},γ,R)\) 的 \( V^{*}(\overline{s})\) 和 \( \pi ^{*}( \overline{s}) \)，當我們實際的系統在連續值狀态 s∈S，需要選擇一個動作來執行，我們就計算相應的離散狀态 \( \overline{x}\)，然後執行動作 \( \pi ^{*}( \overline{s}) \)。
這種離散化可以解決很多問題，但是有兩個弊端。
首先，它用的是一種比較簡單的方法來表示 V* 和 π*，特别是，它假定值函數在離散區間取的是常量（值函數在每個表格中是分段常量）。
為了更好地了解這種表示的限制，看一個監督學習問題，用一個函數來拟合這些資料：
很清楚，線性回歸在這個問題上會做得很好，但如果在 x 軸上離散化，然後使用分段函數來對應每一個區間，拟合的資料會像這樣。
這種分段常量表示對很多平滑函數都不是一個好的選擇，它會導緻輸入不再平滑，在不同的表格中沒有泛化能力，使用這種表示，我們也需要一種好的離散化（非常小的表格單元）來得到一種好的近似。
這種表示的第二個弊端被稱為次元詛咒。假設 S=Rn，我們要把 n 個狀态的次元都離散化為 k 個值，那麼離散狀态的總數目為 kn。這種狀态次元的指數增長非常快，不适用于大型問題。例如有 10d 個狀态，每個狀态變量離散化為 100 個值，就有 10010=1020 個離散狀态，這對于當代的桌面電腦來說還是太龐大了。
一般來說，離散化對于 1d 和 2d 問題工作得很好（有簡單和快速執行的好處）。或許聰明加上小心選擇離散化方法，在頂多 4d 問題上都能工作很好。如果你極其聰明，加一點運氣，你可以用到 6d 問題上。但是，它很少能運作在比那更高維問題上。
4.2 值函數近似
這裡介紹一種在連續狀态 MDPs 尋找政策的可選方法，直接近似于 V*，而不是用離散化。這種方法被稱為值函數近似，已經被成功用到很多增強學習問題中。
4.2.1 使用模型或模拟器
為實作值函數近似算法，我們假定對于 MDP 有一個模型，或者模拟器。非正式地解釋，模拟器是個黑盒子，把連續值狀态 st 和動作 at 作為輸入，輸出下一個狀态 st+1，根據的是狀态轉換機率 \( P_{s_{t}a_{t}}\)：
有許多方法得到這樣的模型，一種是使用實體模拟，例如，PS4 中的倒立擺的模拟器就是使用實體法則來計算杆在時間點 t+1 的位置和方向，給定了目前時間點 t 的狀态和要采取的動作 a，假定知道系統的所有參數，如杆的長度、品質等等；也可使用現成的模拟軟體包，把輸入當作一個數學系統的完整實體描述，目前狀态 st 和動作 at，計算下一個狀态 st+1。
還有一個可選的方法是從 MDP 收集的資料中學習模型。例如，假設我們在 MDP 中重複執行動作執行了 m 次嘗試（trial），每次嘗試 T 個時間步。做這些嘗試可以随機選擇動作，執行一些特定的政策，或通過其它方法來選擇動作。然後就可以觀察到如下 m 個狀态序列。
現在用學習算法來預測 st+1，把它作為 st 和 at 的函數。
例如，可以選擇線性模型的形式：
$$s_{t+1}=As_{t}+Ba_{t}$$
使用類似于線性回歸的算法。這裡模型的參數是矩陣 A 和 B，使用 m 次嘗試的資料來估計它們：
這跟參數的極大似然估計有關。
學習到 A 和 B 之後，一個選擇是建立确定性的模型，給定輸入 st 和 at，就确定了 st+1。另一個選擇是建立随機性的模型，st+1 是輸入的随機函數。
這裡 εt 是一個噪聲項，通常模組化為 εt~N(0,Σ)，協方差矩陣 Σ 也可以直接從資料中估計。
這裡我們把下一個狀态 st+1 作為目前狀态和動作的線性函數，當然，非線性函數也是可能的，比如可以學到模型 st+1=AΦs(st)+BΦa(at)，Φs 和 Φa 是狀态和動作的非特性映射，可以使用非線性學習算法，如局部權重線性回歸，把 st+1 作為 st 和 at 的函數來估計。這些方法也可以用來建立 MDP 的确定性或随機性模拟器。
4.2.2 拟合值函數
這裡介紹一種趨近連續狀态 MDP 的值函數的拟合值疊代算法。假定問題有連續狀态空間 S=Rn，但動作空間 A 是很小和離散的。
同之前介紹的離散狀态的值疊代類似，我們執行如下更新：
這裡把和換成了積分，表示這是在連續狀态空間下。
拟合值疊代的主要思想是，在有限的狀态采樣中 s(1),...,s(m)，趨近執行這一步。 特别的，我們使用監督學習算法——線性回歸來近似值函數，作為狀态的線性或非線性函數：
$$V(s)=\theta ^{T}\phi (s)$$
這裡，Φ 是一些狀态的近似特征映射。
對于 m 個狀态的有限采樣的每一個狀态，拟合值疊代将首先計算量值 y(i)，将是 \( R(s)+\gamma max_{a}E_{s^{'}~P_{sa}}[V(s^{'})]\) 的近似，也就是上面方程的右邊部分，然後我們将使用學習算法來得到接近 \( R(s)+\gamma max_{a}E_{s^{'}~P_{sa}}[V(s^{'})]\) 的 V(s)（或者換句話說，獲得 V(s) 以接近 y(i)）。
詳細算法如下：
上面所寫的拟合值函數使用線性回歸算法以使 V(s(i)) 趨近 y(i)。算法的那一步完全可以類比标準的監督學習問題，有一個訓練集 (x(1),y(1)),(x(2),y(2)),...,(x(m),y(m))，要學習一個函數從 x 映射到 y，唯一的不同是這裡的 s 扮演着 x 的角色，雖然上面的描述使用了線性回歸，但明顯其它的回歸算法（如局部權重線性回歸）也可以使用。
不像離散狀态的值疊代，拟合值疊代不能證明會一直收斂，不過實際中經常是收斂的，或近似收斂。同時也注意到，如果我們使用 MDP 的确定性模拟器，那麼拟合值疊代就能通過在算法中設定 k=1 來簡化，這是因為方程 \( R(s)+\gamma \mathop{max}\limits_{a}E_{s^{'}~P_{sa}}[V(s^{'})]\) 變成了一個确定性分布的期望。否則，在上面的算法中，我不得不作 k 次采樣并平均，以近似期望（見上面僞代碼中 q(a) 的定義）。
最後，拟合值疊代算法輸出了 V，它是對 V* 的近似。這隐含定義了我們的政策。特别的，當系統在狀态 s，需要選擇一個動作，我們會這樣選擇：
$$arg \mathop{max}\limits_{a}E_{s^{'}~P_{sa}}[V(s^{'})]$$
這個計算近似過程類似于拟合值疊代的内循環，對每一個動作，都取 \( s_{1}^{'}\) ,...,\( s_{k}^{'}\) ~\( P_{sa}\) 以近似期望（如果模拟器是确定性的，可以設 k=1）。
在實際中，經常有其它的方法來近似這一步，例如，一個通用的例子是，如果模拟器的形式為 st+1=f(st,at)+ε，其中 f 是狀态的确定性函數（比如 f(st,at)=Ast+Bat），ε 是零均值高斯噪聲。在這種情況下，可以選擇動作：
$$arg \mathop{max}\limits_{a}V(f(s,a))$$
換句話說，這裡設定 εt=0（例如，忽略模拟器的噪聲），設定 k=1。等同的，這能夠使用如下近似從方程 \(arg \mathop{max}\limits_{a}E_{s^{'}~P_{sa}}[V(s^{'})]\) 推導。
這裡期望是指 s'~Psa，噪聲項 εt 很小，這通常是一個合理的近似。
盡管如此，對于不使用這些近似的問題，不得不使用模型采樣 k|A| 個狀态，以近似上面的期望，這會是很高的計算複雜度。
參考資料：
[1] http://cs229.stanford.edu/notes/cs229-notes12.pdf
轉載于:https://www.cnblogs.com/NaughtyBaby/p/5438013.html