# An Outsider’s Tour of Reinforcement Learning (Part12)

[TOC]

## [Reinforcement learning as optimal control with unknown costs and state transitions](http://www.argmin.net/2018/05/02/adp/)

 

:::info
當 costs 跟 state transitions 已知 :
- Dynamic programimg 可以為我們得到最佳的解答, e.g. **MDP**

當 costs 跟 state transitions 未知 或是難以用DP來處理時 :
- 無法建立MDP模型，必須依靠 "**近似**" 的技術 (approximation techniques) 來解決RL問題
:::

DP 難處理的可能狀況 :
1. 動作空間過大
2. 狀態空間過大
3. 狀態轉移機率未知

當然， "近似" Dynamic programimg 是不容易的

 

### Approximate Dynamic Programming

Dynamic Programming 的基本理念 :
典型的最佳控制問題 :


u : 控制輸入 (control action)
X : 狀態 ( state )

 
 
有一種基於動態規劃(dynamic programming)和最佳化原理(principle of optimality)的簡單策略 :
 
:::info
dynamic programming : 路徑最佳(小)原則
 
下圖為 Ａ 到 Ｂ 的最佳路徑
 

principle of optimality :
於兩點 Ａ 與 Ｂ 之最佳路徑上任取一點Ｃ，則此最佳路徑上 Ｃ → Ｂ 的部分必為 Ｃ 與 Ｂ 之間的最佳路徑

e.g.
從台北到高雄的最短路徑 : 台北 → 新竹 → 台中 → 台南 → 高雄
在最短路徑上取一點 (台中)
從台中到高雄的最短路徑 : 台中 → 台南 → 高雄
:::
 
:::success
- 如果找到了一個時間長度為 N (time horizon of length N) 的最佳控制策略 $π_1$,..., $π_N$
- 想知道從時間 t 開始的最佳策略，那只需要從時間 t 開始採取最佳策略，$π_t$,..., $π_N$ ,
t ∈ [1,N]
:::
 

如果 x 為初始狀態，V(x) 為解決最佳控制問題得到的值 :
 

 
從最佳問題的結構，我們把上述的方程式稱為 **貝爾曼方程（Bellman Equation）**，也稱為 **動態規劃方程（Dynamic Programming Equation）**
- 貝爾曼方程是動態規劃（DP）這種數學最佳化方法能達到最佳化的必要條件
- 此方程**將「決策問題在特定時間點的值」以「來自初始選擇的報酬 及 由初始選擇衍生的決策問題的值」的形式表示**。藉這個方式將動態最佳化問題變成較簡單的子問題，而這些子問題遵守由貝爾曼所提出的「最佳化原理」。
- 通過 Bellman Equation ，我們可以得到最佳的價值函數，亦同得到最佳的控制策略
 
我們可以用DP算法為 V 定義一個遞迴公式，如果我們有一種方法來優化方程式的右側，那麼我們可以通過得出最小化右側的 u 來找到最佳操作。
 
 

### Receding Horizon Control

95% 的控制器是 PID，在剩餘的5%中，可能又有95%基於滾動域控制（RHC）

RHC，也稱為模型預測控制（MPC），是一種非常強大的控制方法，可以使 模擬(simulation) 和 回授(feedback) 相結合。
 

:::info
- RHC 的特點是每一次針對目前的時間區塊內作最佳化，然後下一個時間再針對時間區塊內作最佳化。它能夠預測未來事件並且進行對應的處理，PID控制器沒有這樣的預測功能。
:::
 

 
 
 

**Theory behind RHC :**

RHC是以針對**受控體模型的疊代式、有限時域滾動（finite-horizon）最佳化**為基礎。
在時間 t 時針對受控體的狀態取樣，並且針對未來一段很短的時域 [t,t+T]，計算使 cost 最小化的控制策略（數值最小化演算化)

- RHC 的優化是隨著取樣時間的前進反覆的**在線**進行，預測的時間域會漸漸前進，因此稱為滾動域控制
1. RHC 在每一時刻 (時間t) 的優化性能指標只涉及到從該時刻起的未來有限時間 (時間 t+T) ，而到下一時刻，這一優化時間同時向前推移，不斷地進行在線優化。
2. 在每一時刻得到一組未來的控制動作，而只實現當下時刻的控制動作，到下一時刻重新預測優化出一組新的控制，也是只實現一個新的控制動作。
3. 每一步都是 feedback 校正，feedback loop 使系統選擇的動作的實際影響與模擬的內容聯繫起來，因此可以校正模型不匹配，雜訊問題和其他意外的錯誤
 
 

 

整體時間越長 (N 越大)，疊代與反饋次數越多，我們就越不必擔心價值函數 V 是否準確
 
 

[test the power of a nonlinear RHC algorithm](https://homes.cs.washington.edu/~todorov/media/TassaIROS12.mp4)

請注意，即使模型指定不當，控制器仍可使機器人保持直立狀態。 因此可知，RHC 循環內的反饋為建模錯誤提供了相當大的穩健性。

 

:::info
- 如果你有一個完美的價值函數模型，通過解決 Bellman Equation ，可以得到最佳的控制政策。
- 但如果沒有的話，通過 RHC 方法近似價值函數，在 real-time 的情況下依然能夠有好的結果。
:::

 
 
 
 

參考資料 :

https://en.wikipedia.org/wiki/Model_predictive_control
https://en.wikipedia.org/wiki/Bellman_equation
http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/DP.pdf
http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/FA.pdf
https://ch-hsieh.blogspot.com/2009/04/0-principle-of-optimality-bellman.html
https://blog.csdn.net/matlabmonkey/article/details/44338901
https://blog.csdn.net/hhy_csdn/article/details/89105908
https://zhuanlan.zhihu.com/p/58837258