Chap3:Reinforcement Learning Problem

Ｍarkov Decision Processes:

在學習RL之前必須從MDP開始了解起，什麼是MDP呢？大家可以上上維基百科查詢，如同百科上所說的，MDP是一個數學架構模型，他有一個很特殊的性質叫作馬可夫性質，即系統的未來狀態s(t+1)只與現在狀態s(t)有關，而與之前狀態s(t-1),s(t-2).....無關，那什麼系統符合MDP呢？舉個簡單的例子，下棋就是一個MDP系統，你下一步該怎麼走s(t+1)只根據你現在的盤面狀態s(t)決定即可，跟你之前走的都沒關係，所以這也是AI常常會以下棋做研究的原因，因為他就是一個標準的MDP系統。了解大概什麼是MDP系統後，我們再細部講解馬可夫對這系統下了什麼定義，馬可夫總共定義了六種東西，分別是：

1.一系列的狀態(s):

狀態是可以千變萬化隨自己定義的，以上面的走迷宮圖片為例，我定義狀態為機器人到達的不同位置，因此這個環境就產生了12個不同的狀態。

2.一系列的動作(a):

同理也是可以自己定義的，在這個例子中我可以定義動作為上下左右

3.狀態移轉方程式 T(s, a, s’)：

紀錄著從狀態s採取動作a到達s’的機率，比如上圖機器人再(3,1)的位置上，機器人採取往上這個動作，正常情況下T(s(3,1), 上, s’(3,2))=1，但在現實生活中呢？你有沒有可能因為輪子打滑而造成採取同樣的動作卻抵達不同的狀態，這個T就是把這個因素考慮進來，所以你如果想要在模擬系統中把這個參數也考慮進去你就可以設T(s(3,1), 上, s’(3,2))=0.8，而分別各有0.1的機率打滑造成抵達狀態的左右兩邊，也就是說

T(s(3,1), 上, s’(4,1))=0.1 不同表示法為：P(s’| s, a)=0.1

T(s(3,1), 上, s’(2,1))=0.1

4.獎勵函數方程式 R(s, a, s’) ：

這個是RL學習成功與否的關鍵，你必須告訴機器人，從哪個狀態到哪個狀態是好的，設一個reward獎勵它，就像在教狗狗握手一樣，牠做對了就給牠東西吃(reward=positive)，牠做錯了就打牠一下(reward=negative)或擺個生氣的臉，這樣狗狗就知道做錯了，其實RL就是從這樣的一個學習模式演化而來，目的就是為了讓機器人學會某一件事(狗狗握手)，差別是我們把他數學化了，數學話的目的為了好進行公式推導演算，簡單的來說呢就是使機器人得到的reward最大化就是RL在解決的問題。拿這個地圖範例來說，我們想要機器人走到終點(4,3)，遠離火堆(4,2)，因此我們可以設定 R(s(3,3), 右, s’(4,3))=1 R(s(3,2), 右, s’(4,2))=-1 ，來使機器人學會避開火堆到達終點的最短路徑。

5.起始狀態(start state)：定義系統的初始狀態(1,1)

6.結束狀態(terminal state)：定義系統的終點位置(4,3)

維基百科參考資料：

MDP：

在機率論和統計學中，馬可夫決策過程（英語：Markov Decision Processes，縮寫為 MDPs）提供了一個數學架構模型，用於面對部份隨機，部份可由決策者控制的狀態下，如何進行決策，以俄羅斯數學家安德雷·馬爾可夫的名字命名。在經由動態規劃與強化學習以解決最佳化問題的研究領域中，馬可夫決策過程是一個有用的工具。

Markov property：

馬可夫性質（英語：Markov property）是機率論中的一個概念，因為俄國數學家安德雷·馬可夫得名。當一個隨機過程在給定現在狀態及所有過去狀態情況下，其未來狀態的條件機率分布僅依賴於當前狀態；換句話說，在給定現在狀態時，它與過去狀態（即該過程的歷史路徑）是條件獨立的，那麼此隨機過程即具有馬可夫性質。具有馬可夫性質的過程通常稱之為馬可夫過程。

再來我從學習率的概念帶大家一步一步進入RL的世界，書上通常從這個例子 armed-bandit problem開始介紹起，中文的翻譯為吃角子老虎機。

學習率（α）的概念: learning rate

假設你去玩吃角子老虎機

你想要知道哪一台最好中獎，所以你每一台都去玩看看，玩第一次看贏了多少錢稱做R1，第二次賺得獎勵稱做R2，所以玩了K次之後取平均得到Q，Reinforcement learning 的主要任務就是最大化這個Q值，Q值越大代表我獲得的獎金最多，沒有人玩吃角子老虎機是想要賠錢的吧?

但是這裡有一個問題，我每玩一次就必須要記錄前幾次得到的R，那如果我只想記錄前面一次節省記憶體該怎麼做呢? 下面就是推法

折扣率（γ）的概念: discounting rate

但是我們等下要推的不是過去的經驗，我們想預測未來，所以Gt代表預測未來的R總和，等差級數一直加到最終回合出現，但這會產生一個問題，如果遇到沒有最終回合的情況一直加下去的話，G將會呈現無限大，這不利於我們之後的計算，因此要乘以一個折扣率衰減，所以式子呈現如下，第三行為無最終回合的表示方法，第四行為有最終回合的表示方法。

Bellman equation：

接下來我們要來推鼎鼎有名的Bellman equation，Vπ(s)代表在狀態為s的情況下，策略（policy）為π時G的期望值，我們所要做的就是推出像剛剛推吃角子老虎機的公式一樣，推出動態方程式，下面即為推出的過程。

r(s,a,s')代表在狀態s下採取a這個動作會造成狀態移轉到下一個狀態s'

如果看不懂的話，小編也有一個自己的理解方法如下：

總之就是要推出這個遞迴的Bellman equation

我只是簡化推倒過程方便大家看得懂，但書上把policy還有transition probabilities都考慮進去了，書上完整推導如下:

假設移轉機率都為0.5，小編試算上面這個s給大家看

講完了V值再來講q值，理念都是一樣的，只是這裡的狀態空間多一維action

上面推的是任意policy下(π)，Bellman equation都應該被滿足，那麼當policy 是 optimal policy 時當然也應該被滿足啊，因此我們將最佳策略表示成(*):

原文對照:

Intuitively, the Bellman optimality equation expresses the fact that the value of a state under an optimal policy must equal the expected return for the best action from that state: