這篇文章是《人工智能：一種現代的方法》及 Udacity 上的強化學習課程筆記及其他內容的整理，
從馬可爾夫決策過程、價值迭代、策略迭代、Q 學習，最後到深度 Q 網路的思路。
前言
前半年太忙一直沒時間更新 Blog，現在終於有時間寫新文章了 XD
強化學習（reinforcement learning）一直是非常有趣的主題，跟遊戲設計搭配更是如此。
我曾經在 RPG Maker MV 中使用手刻的 3 層全連接神經網路來做 ARPG（動作 RPG）怪物的 AI 設計，
雖然效果不是很理想，不過確實可以觀察到怪物可以學習到一些玩家的攻擊模式並且迴避。
全連接神經網路在分類上是屬於監督學習，而本篇著重於強化學習，
強化學習是不透過標籤（label），系統直接由環境中取得資訊來學習的 AI 系統。
當時初學時，關於 Q 學習的部分其實看不太懂，我後來發現有一系列的途徑去理解，
一開始是自己閱讀《人工智能：一種現代的方法》，好不容易看懂（筆者數學不好……），
後來在 Udacity 的強化學習課程，又做了一次整理才明白。
關於課程請至 Udacity 的課程資訊
我認為的最佳學習途徑：
- 馬可爾夫決策過程（Markov Decision Process, MDP）
- 價值迭代（value iteration）與策略迭代（policy iteration）
- Q 學習（Q-learning）
- 深度 Q 網路（Deep Q-Network, DQN）
其中，前兩部分是序列式決策問題（sequential decision problem）的入門，
第三部分 Q 學習是關於序列決策的變體，最後深度 Q 網路則是將 Q 學習結合神經網路所誕生的算法。
本篇是第一部分，重點擺在討論馬可爾夫決策過程與問題建模，
至於策略、效用與貝爾曼方程將在下一篇文章解決。
這是 DQN 的系列文章，下一篇是 價值迭代 Value Iteration
於 2019.05.13 更新了部分數學符號的表示
馬可爾夫決策
馬可爾夫決策由下列部分組成：
- 狀態集合 $S$
- 動作函數 $ACTION: S \mapsto A$ 其中 $A$ 為可執行的動作
- 轉移模型 $P(s_{t+1}|s_{t}, a)$ 其中 $s_{t} \in S$ 為當前狀態、$s_{t+1} \in S$ 為下一個狀態，$a \in A$ 為時間 $t$ 時執行的動作
- 回報函數 $R(s)$
其中轉移模型必須滿足馬可爾夫假設（Markov assumption）即「$s_{t+1}$ 的狀態僅受 $s_{t}$ 狀態影響」。
動作函數，通常被說是「動作集合」，但在書中公式表達像是「回傳集合的函數」，故在此以函數說明。
玩具問題
筆者的經驗是，初學見到這些符號會水土不服，
所以可以先過渡到幾個其他的玩具問題（toy problem）來理解馬可爾夫決策的過程。
順便練習把問題定義清楚。
地圖尋路
這是《人工智能：一種現代的方法》第 17.1 節序列式決策出現的玩具問題。
地圖大小寬度為 3、長度為 4，位置 $(2, 2)$ 是一堵牆，
寶藏在 $(4, 3)$，陷阱在 $(4, 2)$。電腦從 $(1, 1)$ 開始，每次移動 1 格，移動會消耗 0.04 分，
目標是透過探索地圖，找到一個最佳策略來獲得高分。
很難想像的話，看下面的圖 1。
對於這個問題來說，建模的四個部分分別為：
- 狀態集合，即座標集合 $S = \{(x, y)| x \in \{1, 2, 3\}, y \in \{1, 2, 3, 4\} \}$
- 動作函數，即在某一座標可以執行的動作 $MOVE: S \mapsto A$ 其中 $A = \{\text{up}, \text{left}, \text{right}, \text{down}\}$
- 轉移模型，即在某座標、執行某動作後，轉移到下個狀態的機率 $P(s_{t+1}|s_{t}, a_{t})$ 其中 $s_{t}, s_{t+1} \in S$ 且 $a_{t} \in A$
- 回報函數，每個位置的得分 $SCORE(s) = SCORE(x, y)$
下面給出一段淺白的描述作為例子。
目前在某一個座標 $x = 1$ 且 $y = 3$，所以我的「狀態」是 $s = (1, 3) \in S$
在這個狀態下，我可以執行的動作為 $MOVE(1, 3) = \text{up}, \text{left}, \text{right}, \text{down}$
也就是上下左右；如果此時我選擇 $a = \text{right} \in A$ 即向右移動。
注意這裡的動作函數 $MOVE$ 是「一對多映射」，正因如此，玩家才在某些狀態，可以選擇多種動作。
若動作「一定會成功」則轉移模型為：$P((2, 3)|(1, 3), \text{right}) = 100\%$
至於環境的回報（得分）是：
書中的轉移模型是不確定的。舉例來說，你決定往上移動，只有 80% 的機會成功之類的。
簡化的二十一點
為了更理解「轉移模型」的部分，筆者再針對簡化過後的二十一點（Black Jack）建模，
這個簡化過後的規則如下：
- 牌面 1、2、3、4、5 每種牌都有無限多張且抽到每一種的機率相等
- 牌面 1、2、3、4、5 對應點數為牌面的數字
- 每一回合莊家、玩家決定要不要繼續抽牌
- 若某回合不抽牌，接下來的回合不能繼續抽牌
- 若超過 10 點，則判輸
- 若雙方皆超過 10 點，則平手
- 若雙方皆小於等於 10 點，則點數大者勝
- 所有牌都是明牌（玩家可觀察）
- 莊家先抽牌
如果你覺得規則理解有點困難，請嘗試玩玩看：
因為還沒介紹完策略，暫時不將完整的 AI 放出來，這裡的電腦僅是單純的邏輯模擬。
對於這個問題來說，建模的四個部分分別為：
- 狀態集合，即各種手牌 $s$ 及允許抽牌標誌 $t$ 的集合 $S = \{s = (c, t) | c \subseteq \{1, 2, 3, 4, 5\}, t \in \{1, 0\}\}$
- 動作函數，即每回合可以執行的動作 $ACTION: S \mapsto A$ 其中 $A = \{\text{draw}, \text{pass}\}$
- 轉移模型，即抽牌後，轉移到下個狀態的機率 $P(s_{t+1}|s_{t}, a_{t})$ 其中 $s_{t}, s_{t+1} \in S, a_{t} \in A$
- 回報函數，即一局遊戲的牌面數字 $POINT(s), s \in S$
我們先看動作函數，對於每一種手牌的狀態，
除非已經超過 10 點或曾經放棄抽牌，否則可以繼續抽牌，所以有：
然後轉移模型此時便不是「確定」的，轉移到不同的狀態是透過機率，
比方說目前我有手牌且可抽牌 $s = (\{1, 2, 3\}, 1)$ 考慮動作函數有 $ACTION(c, t) = \text{draw}, \text{pass}$
所以轉移模型，有兩種動作可以選擇：
若選擇不抽牌，那下回合一定保持原來的手牌，但抽牌標誌變成 0。
$P((\{1, 2, 3\}, 0)|(\{1, 2, 3\}, 1), \text{pass}) = 100%$
若選擇抽牌，那下回合增加手牌（每種機率相等），抽牌標誌不變。
$P((\{1, 2, 3, 1\}, 1)|(\{1, 2, 3\}, 1), \text{draw}) = 20%$（抽到點數 1）
$P((\{1, 2, 3, 2\}, 1)|(\{1, 2, 3\}, 1), \text{draw}) = 20%$（抽到點數 2）
$P((\{1, 2, 3, 3\}, 1)|(\{1, 2, 3\}, 1), \text{draw}) = 20%$（抽到點數 3）
$P((\{1, 2, 3, 4\}, 1)|(\{1, 2, 3\}, 1), \text{draw}) = 20%$（抽到點數 4）
$P((\{1, 2, 3, 5\}, 1)|(\{1, 2, 3\}, 1), \text{draw}) = 20%$（抽到點數 5）
不難發現，對於某一種動作，機率和必為 $1$。
回報函數為牌面點數和，點數和越高越好，而超過 10 點則給予 0 值：
$POINT(s) = POINT(c, t) = \left\{\begin{array}{l} \sum\limits_{x \in c}x && \text{if } \sum\limits_{x \in c}x \leq 10 \\ 0 && \text{if } \sum\limits_{x \in c}x > 10 \\ \end{array}\right .$