人工智慧與增強學習-2：多臂吃角子老虎機理論

前情提要：人工智慧與增強學習 1：什麼是增強學習？

Google DeepMind 所設計出的 AlphaGo，在2016年擊敗韓國棋王李世乭，震驚全世界，也因此有人認為2016年可說是 AI 元年。在 AlphaGo 的演算法中，有一部分是透過「增強學習」讓 AlphaGo 不斷從過去的對戰紀錄中自我學習，這是AI領域的一大突破。

「增強學習」的始祖要回到所謂的「馬可夫決策過程」(Markov Decision Process)，這是一個相當特別的隨機過程(stochastic process)設定，定義如下：

馬可夫決策過程 (MDP) 是一個由 $(\mathcal{S}, \mathcal{A}(\cdot), P_{\cdot} (\cdot,\cdot),R_{\cdot}(\cdot,\cdot),\gamma)$ 形成的元組(tuple)，其中：

$\mathcal{S}$ 是一個有限的狀態 (state) 集合。

$\mathcal{A}(s)$ 是在目前狀態 $S_t$ 為 $s$ 的情況下，一個有限的動作 (action) 集合。

轉移機率(transition probability)：
$P_{a} (s,s')=\mathbb{P}(S_{t+1} = s' | S_t = s, A_t = a)$ ，在目前狀態 $S_t$ 為 $s$ ，目前執行動作 $A_t$ 為 $a$ 的情況下，下一期狀態 $S_{t+1}$ 為 $s'$ 的機率。

報酬函數 (expected reward)：
$R_a(s) = R_{t+1} |S_t = s, a_t = a$ ，在目前狀態 $S_t$ 為 $s$ ，目前執行動作 $a_t$ 為 $a$ ，下一期狀態 $S_{t+1}$ 為 $s'$ 的情況下，該動作可以得到的期望報酬。值得注意的是， $(S_{t+1},R_a(s))$ 存在聯合分配(joint distribution)。

$\gamma$ 是一個折現因子 (discounted factor)。

在馬可夫決策過程中，有兩件事情是我們希望學會的：一是報酬函數 $~R_a(s) = R_{t+1} |S_t = s, A_t = a~$ 的確切分配或是期望值，二是一個好的「策略」(policy) ，讓我們在在整個決策過程結束後，折現期望報酬和最大。統計學家 Blackwell (1965) 的論文中，我們可以得知如果對於所有可能的狀態 $s\in \mathcal{S}$ 而言，若 $\mathcal{A}(s)$ 皆相同，則存在一個最佳的「策略」，也就是該策略所獲得的折現期望報酬和將會大於其他所有不同的策略。這個定理告訴我們：增強學習在一些寬鬆的條件下，是可以被達成的。

多臂式吃角子老虎機：賭徒的智慧

從上面的定義可以發現，MDP 是一個相當理論的「決策架構」，因此在研究 MDP 的初期，很適合先了解「多臂式吃角子老虎機」(multi-armed bandit) 問題。簡單來說，「多臂式拉吃角子老虎機」是一個 MDP，而我們將動作集合簡化成 $\mathcal{A}(s) = \{1,2,\cdots,K\},~\forall s\in\mathcal{S}$ ，且假設執行動作得到的報酬僅跟執行的動作有關，也就是我們可以將狀態空間寫為 $\mathcal{S}=\{S_1,\cdots,S_K\}$ 。因此，多臂式吃角子老虎機的問題其實是在考量，目前有個吃角子老虎機，上面有 $K$ 個手臂，一次只能拉一個臂，拉完之後會觀察到一個新的報酬，要採用什麼樣子的策略，能夠獲得最大的期望報酬？為了回答這個問題，「如何決定要去拉哪一個手臂」，以及「 $R_a(s)$ 該被如何刻劃」，將是多臂式吃角子老虎機的重要元素。

以數學式表示，一個多臂式吃角子老虎機的問題可以寫成一個最佳化的問題： $V(S_0)=\max_{a}\mathbb{E}\left(\sum_{t=0}^{\infty}\gamma_t R_{a_t}(s)\right)$ ，這樣的最佳化問題是相當難解的，因此 Gittins 和 Jones (1974) 提出了 celebrated index theorem，將無窮期的最佳化問題轉化成一個有限期的最佳化問題，首先我們先定義吉丁係數 (Gittins index) 為 $m^{a_t}(S_t) = \max_{\tau}\frac{\mathbb{E}\left(\sum_{u=t}^{\tau} \gamma^{u-t} R_{a_u} (S_u)\right)}{\sum_{u=t}^{\tau} \gamma^{u-t}}$ ，其中 $\tau$ 為狀態過程 $\{S_0,S_1,\cdots\}$ 的一個停止時間(stopping time)。

什麼是停止時間呢？對於一個隨機過程 $\{S_t\}_{t\in\mathbb{N}\cup\{0\}}$ ，停止時間 $\tau$ 是某一特定「停止規則」(stopping rule) 發生的時間，且隨機變數 $\tau$ 滿足 $\tau=T$ 只跟狀態 $\{S_0,\cdots,S_T\}$ 。也就是說，停止時間 $\tau$ 只會跟過去到該「停止規則」發生當下的狀態有關，跟未來的狀態無關。舉例來說，考慮一個狀態隨機過程 $\tau=T$ ，首達時間(hitting time) $\tau=\min_{t}\{t\geq 0:S_t = s\}$ ，也就是狀態 $s$ 第一次發生的時間，是一個停止時間，且 $S_t = s$ 是一個停止規則 (stopping rule)。

當我們對於 Gittins index有一定了解後，我們就可以來理解 celebrated index theorem，該定理的定義如下：

對於一個多臂式吃角子老虎機問題 (multi-armed bandit problem) ，最佳策略 (optimal policy) 在時間 $t$ 將選擇 $a_t = \arg\max_{ j\in\{1,\cdots,K\}} m^{j}(S_t)$ 。

因此，若我們能決定每一期每個動作得到的期望報酬 $R_{a_t} (s_t)$ ，並針對每個動作決定最佳停止時間(optimal stopping time)，我們就可以計算出吉丁係數 $m^{a_t}(S_t) = \max_{\tau}\frac{\mathbb{E}\left(\sum_{u=t}^{\tau}\gamma^{u-t} R_{a_u} (S_u)\right)}{\sum_{u=t}^{\tau} \gamma^{u-t}}$ ，也就解決了多臂式吃角子老虎機的問題了！

然而，最佳停止時間並不是一個很容易決定的事情，若每一個時間點我們所得到的報酬與過去的狀態無關，我們或許可以利用Wald Equation來簡化最佳停止時間的問題，但實際上，每一次的報酬 $R_{a_t} (S_t) = R_{t+1}|S_t$ ，其實是會受到過去的狀態 $S_{t}$ 所影響的，因此我們很難ˊ直接利用「最佳停止時間」完成多臂吃角子老虎機的學習過程。

實務上的「多臂式吃角子老虎機」

由於前面的設定狀態間及報酬間的關聯結構太過複雜，難以進行建模，因此實際在設計「吃角子老虎機」演算法時，我們會將問題設定的更簡單一點：我們把「狀態」的描繪拿掉，讓報酬函數 $R_{a_t}(S_t)=R_{a_t}$ 只與時間 $t$ 時所執行的動作 $a_t$ 有關，因此整個問題將被簡化成：

一個多臂式吃角子老虎機 (multi-armed bandit) 由兩個元素所組成：

$\mathcal{A} = \{1,2,\cdots,K\}$ ，每次執行動作時共有 $K$ 個手臂可以選擇。

$K$ 個報酬函數 $(R_{1}, \cdots, R_{K})$ 的機率分配 (probability distribution)。

此外，我們也不使用 $\max_{a}\mathbb{E}\left(\sum_{t=1}^{\infty}\gamma^t R_{a_t,t}(s)\right)$ 解決多臂式吃角子老虎機的問題，而是用一個等價的最佳化問題 $\min \rho_T = T\max_{k\in\{1,\cdots,K\}}\{\mathbb{E}(R_{k})\} - \sum_{t=1}^{T} \mathbb{E}(R_{a_t})$ 來進行增強學習(不考慮折現)。在此處，我們稱 $\rho_T$ 為時間 $T$ 的後悔函數 (regret function)。

對於這個後悔函數，我們其實可以進行更深一步的探討。如果考量一個無窮期的多臂式吃角子老虎機問題，後悔函數將無法估計，而且在每一個時間點 $t$ ，我們很難去描繪未來的行為。因此，在執行每一次動作時，我們將會試著極小化當期的損失函數，也就是說， $a_t = \arg\max_{k\in\{1,\cdots,K\}} \mathbb{E}(R_{a_t})$ ，這樣的結果其實是一個子完美策略 (sub-optimal policy)，並不一定真正能極小化後悔函數。

然而，我們其實可以將後悔函數改寫為 $\rho_T = T\times\left(\max_{k\in\{1,\cdots,K\}}\{\mathbb{E}(R_{k})\}\right) - (\mathbb{E}(R_{a_t}))\times\sum_{k=1}^{K} \mathbb{E}(T_k(T))$ ，其中 $T_{k}(T)$ 代表總時間為 $T$ 時，第 $k$ 個手臂被使用的總次數。在 Lai 和 Robbins (1985) 的論文中證明了 $\mathbb{E}(T_k(T))\geq\frac{\ln T}{D(p_k\|p_{\star})}$ ，其中 $p_k$ 為子完美策略所選擇手臂的機率分配，而 $p_{\star}$ 為全域完美策略所選擇手臂的機率分配，而 $D(p_k\|p_{\star})=\int p_k \ln\frac{p_k}{p_{\star}}d\mu$ 為 $p_{k}$ 與 $p_{j}$ 的Kullback-Leibler divergence。這個定理告訴我們，在我們使用子完美策略作為運算模型 (computational model) 的情況下，多臂式吃角子老虎機的後悔函數的遞減速度為 $\rho_T = \Omega(\log (T))$ ，因此如果我們能夠設計一個演算法 $\mathbf{A}$ ，使得該演算法的後悔函數 $\rho_T (\mathbf{A}) = O(\log(T))$ ，則我們就稱該演算法解決了多臂式吃角子老虎機的問題。