0%

馬可爾夫決策過程 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\%$
至於環境的回報(得分)是:

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

書中的轉移模型是不確定的。舉例來說,你決定往上移動,只有 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) = \left\{\begin{array}{l} \text{draw}, \text{pass} && \text{if } t = 1 \text{ and } \sum\limits_{x \in c}x \leq 10 \\ \text{pass} && \text{if } t = 0 \text{ or } \sum\limits_{x \in c}x > 10 \\ \end{array}\right .$

然後轉移模型此時便不是「確定」的,轉移到不同的狀態是透過機率,
比方說目前我有手牌且可抽牌 $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 .$