---
# System prepended metadata

title: An Outsider’s Tour of Reinforcement Learning (Part12)

---

# 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/)

&emsp;

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

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

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


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

&emsp;


### Approximate Dynamic Programming

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

![](https://i.imgur.com/T9yP6Gi.png)

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

&emsp;
&emsp;
有一種基於動態規劃(dynamic programming)和最佳化原理(principle of optimality)的簡單策略 : 
&emsp;
:::info
dynamic programming : 路徑最佳(小)原則
&emsp;
下圖為 Ａ 到 Ｂ 的最佳路徑
&emsp;
![](https://i.imgur.com/KIOJX66.png)

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

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

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

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

### Receding Horizon Control


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

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

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

&emsp;
![](https://i.imgur.com/dFXvU2p.png)
&emsp;
&emsp;

**Theory behind RHC :** 

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


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



![](https://i.imgur.com/ejaPgPD.png)
&emsp;

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

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


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

&emsp;



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


&emsp;
&emsp;
&emsp;
&emsp;


參考資料 : 

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