馬可夫鍊

什麼是強化學習

美國的心理學家 Skinner (史金納)，做一個叫 Skinner Box 的實驗裝置 。把一隻飢餓的老鼠放到箱子裏，箱子中有一根桿子，按下桿子就會有食物掉出。實驗結果老鼠竟然學會了按下桿子，得到食物。

老鼠處於一種狀態(飢餓)。然後有二種選擇，也就是動作(壓桿子，或什麼事都不作)。最後產生結果，也就是回饋(有得吃或餓死)。飢餓狀態下會使按下桿子出現食物的機會大增，屬於正向回饋。發呆餓死為負向回饋，所以發呆的動作就會減少。這種藉由某個狀態強迫老鼠學習的方式，俗稱強迫學習，在此則稱為強化學習。

有養寵物的人也常使用這種強迫學習的方式，狗狗在家裏亂大小便，就把他關進籠子一小時，久了就會學乖了。狗狗也常會挑食，就讓他餓個二天，第三天就會乖乖的把飼料吃完。

現實世界中，狀態可能有很多種，動作也有很多種。為了知道在某種狀態下需採取什麼樣的動作，就需使用很有名的馬可夫決策。

馬可夫決策(Markov Decision Process, MDP)

Andrey Markov 是俄羅斯的數學家，主要研究在一連串相關事件所組成的系統中，會如何隨著時間變化。MDP定義如下的數學模型 :

狀態集合S : 有m種狀態，標示為 $(S=\{s_{0},s_{1},s_{2},….s_{m}\})$
動作函數A : A為可執行的動作集合
轉移模型$(P(s_{t+1}|s_{t}, a))$ : $(s_{t})$為當前狀態, $(s_{t+1})$為下一個狀態, a為時間為 t 時執行的動作
獎勵函數 R(s)
價值函數U(s)

格子找路

上面四個集合或模型，實在是霧沙沙，所以用格子找路的例子說明。底下有 4*3 個格子，
1. 最初在 (1,1) 的格子
2. (2,2) 為一道牆，不能進入
3. 寶藏在(4, 3) 格，到達此格可加 1 分 (獎勵函數)
4. 陷井在 (4,2) 格，到達此格會減 1 分 (獎勵函數)
5. 每次移動 1 格，會消耗 0.04 分 (獎勵函數)

模型建立如下

狀態集合 : $(S=\{(x,y)|x\in \{1,2,3\},y\in \{1,2,3,4\} \})$
動作函數 : A={up, left, right, down}
轉移模型 : $(P(s_{t+1}|s_{t}, a))$ ，執行某動作後，轉移到下個狀態的機率
獎勵函數 : SCORE(s) = SCORE(x, y)，每個位置的得分(1, -1,  0, -0.04 )。

假設目前在 (1,3)，則 s=(1, 3)。往右走，則 a=right，此動作一定會成功，則 P((2,3)|(1, 3), right) = 100%。

獎勵分數為 $(SCORE(s)=\left\{\begin{matrix}
+1\;\;\;\;\;\;\;\;if\;\;\;s=(4, 3)\\
-1\;\;\;\;\;\;\;\;if\;\;\;s=(4, 2)\\
0\;\;\;\;\;\;\;\;\;if\;\;\;s=(2, 2)\\
-0.04\;\;\;\;\;\;\;\;other\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;
\end{matrix}\right.)$

策略

策略 (policy) 定義為 $(\pi (s_{t}))$，指在狀態 $(s_{t})$ 時所推薦的動作。動作是 $(A(s_{t}))$ 集合，所以 $(\pi (s_{t}))$ 必然為 $(A(s_{t}))$ 其中之一。

最佳策略(best policy) 以 $(\pi^*(s_{t}))$ 表示，為狀態 $(s_{t})$ 時的最佳行動。

貝爾曼方程式

貝爾曼方程式是計算 s 狀態在 t 時間，往上下左右走到下一格時，取得那個一動作的最大值當作效用值。公式如下