馬可爾夫決策過程 Markov Decision Process

這篇文章是《人工智能：一種現代的方法》及 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。

圖 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\mathrm{\%}$
至於環境的回報（得分）是：

$SCORE(s)=\{\begin{array}{lll}+1& & \text{if }s=(4,3)\\ -1& & \text{if }s=(4,2)\\ -0.04& & \text{otherwise}\end{array}$

書中的轉移模型是不確定的。舉例來說，你決定往上移動，只有 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 點或曾經放棄抽牌，否則可以繼續抽牌，所以有：

$ACTION(s)=ACTION(c,t)=\{\begin{array}{lll}\text{draw},\text{pass}& & \text{if }t=1\text{ and }\sum _{x\in c}x\le 10\\ \text{pass}& & \text{if }t=0\text{ or }\sum _{x\in c}x>10\end{array}$

然後轉移模型此時便不是「確定」的，轉移到不同的狀態是透過機率，
比方說目前我有手牌且可抽牌 $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)=\{\begin{array}{lll}\sum _{x\in c}x& & \text{if }\sum _{x\in c}x\le 10\\ 0& & \text{if }\sum _{x\in c}x>10\end{array}$