大三下的一個契機，選了一堂人工智慧，從簡單的 Search 、HillClimbing 、Simulated annealing 到 DeepBlue 用的 minimax 和 alpha-beta purning 然後是DeepMind用的 neural network、forward/back propagation。我在學習過程感受到人工智慧魅力以及可貴之處。
當然。我也理解人工智慧還在發展中且也有許多問題需要克服及討論，我們可以參考這篇 AlphaGo 使用的強化學習是人工智慧新星？讓專家告訴你為什麼這不是通用解方 。我在做強化學習(Reinforcement Learning)時也有這種想法，但這也是吸引我的地方：我們就像在解一個世紀大問題，它不屬於封閉解(Closed-form solution)，而是需要我們找到一個好方法再慢慢去逼近。上面那篇文章提到，甚至是區域最佳解(Local Optima)就可以解決目前問題了！
我的研究目標是做強化學習(Reinforcement Learning)從 Q-Learning開始理解，但前面還有一個非常重要問題我們需要理解，那就是 Markov Decision Process。
(這篇文章我們只會簡單去描述MDP，並不會講解太深推論。如果已經看過這方面論文的可以選擇跳過)
在討論 MDP（我們以後這樣稱呼)之前，要先討論 Markov Process是什麼
Markov Process
Markov Process是一種我們將問題歸類的方法，如果他符合下述兩點，我們就可以用Markov的solution去處理這個問題。
- Markov 是一種問題現象，只要符合Markov 性質的 “隨機過程”
- 如果Markov屬於離散，則被稱為Markov 鏈，而與它的過去歷史或未來狀態，都是獨立、不相關的
我們來舉個兩個例子：
這是 OpenAI gym提供的一個學習環境，我們有三個動作可以操作這台車子：左、不動、右。當達到終點時就會結束這回合(episode)。
這台車在 x1會做一個選擇，這個選擇決定了下一個狀態(next state)，我們在考慮x1動作時不需要考慮x2及x3因為他們之間是完全沒關係的，我們只要考慮當前狀態(state)到 最好的 下一個狀態(next state)就行了。
這是一個超級古老的遊戲：毀滅戰士。我們可以選擇 移動視角、左、右、前進、後退、開槍，如果我們只考慮擊殺眼前的怪物的話，那我們就只要考慮當前狀態(state)以及動作後的下一個狀態(next state)。
Student Problem
這是一個非常經典例子，我們來解釋一下這些狀態
- 開始為 第一堂課：結束為 睡覺
- 第一堂課狀態
50%會滑 FB; 50%上第二堂課 - 第二堂課狀態
20%睡著zz;80%上第二堂課 - 第三堂課狀態
60%參加考試; 40%跑去pub玩 - Pub玩狀態
20%上第一堂課; 40%上第二堂課; 40上第三堂課 - 滑Fb狀態
90%會繼續滑; 10%回去上第一堂課 - 參加考試狀態
100%通過後回去睡覺
這就是一個簡單Markov Process，接下來我們要把機率填進 狀態對狀態(state-state)之間矩陣。你可以看橫排加起來機率一定會等於1
接下來我們需要再加上 獎勵(Reward)以及衰減係數(Discount factor)
這個獎勵是從St移轉到 St+1時會得到的
衰減係數則是為了做一個評估獎勵是否合理另一個方法，有了衰減係數我們可以更好控制獎勵。
如果係數接近 0 ; 代表我們看待這問題比較需要近視利益
如果係數接近1 ; 代表我們需要比較宏觀看待利益
左邊的方程式就是我們加入衰減係數以及獎勵的公式
Markov Reward Process
有了獎勵跟衰減係數(以後稱為 gamma)，我們就可以來計算 Markov獎勵過程了
我們來試著算算看吧
C1 : -2 + 0*[(0.5*-1)+(0.5*-2)] = -2
C2 : -2 + 0*[(0.2*0)+(0.8*-2)] = -2
…….重複以上算法，數字會不斷收斂。但，因為 gamma為0看不出來收斂結果
C1 : -2 + 1*[(0.5*-23)+(0.5*1.5)] = -13
C2 : -2 + 1*[(0.2*0)+(0.8*-4.3)] = 1.5
…….重複以上算法，數字會不斷收斂。
但，你一定會有一個問題：為什麼我們在計算 S 時 可以用 S+1 的數值呢？一開始S的值可以是亂數，透過不斷迭代我們的數值會漸漸地收斂(意思就是達到一個穩定不在變動的值)
我們可以將上面算法整理成:
這樣就是簡單的 MRP計算了，我的github有放整個計算過程，有興趣或是還是不太懂可以上去看看，順便給我一個星星XD支持一下
你可能會覺得這麼簡單的計算或過程跟 AI或 RL有什麼關西？其實強化學習的推導就是從MDP開始，像是我們今天提到的方法是一種value-base，Q-learning也是屬於一種value-base改進方法，下一篇我們會將 policy(決策)加入到MRP 裡(強化學習裡也有一種方法叫Policy gradient)，就是MDP了。
