強化式學習的困難之處，有時在於處理馬可夫決策過程(Markov Decision Process)，而各種知名的演算法，如Q-Learning、A2C，都是用來解決馬可夫決策過程最佳化問題，詳細的內容可以參考旗標出版的「深度強化式學習」。到底馬可夫決策過程有多複雜呢？今天我們就來好好看一下。
一、馬可夫決策過程
馬可夫決策過程是用來模型化代理人(Agent)與環境(Environment)互動的過程(圖一)。代理人會根據目前環境的狀態，來決定可以獲得最大回饋值(Reward)的動作(Action)；當代理人執行該動作時，環境會因此而改變狀態，並且反饋給代理人一個回饋值；代理人收到新的回饋值後，會更新自己選擇動作的策略(Policy)，並且根據環境新的狀態，決定下一個動作；如此雙方不斷互動。而我們想要的是：找到一個演算法，可以解出最佳的馬可夫決策過程，讓代理人跟環境互動後，得到最多的回饋值。
二、P-Complete與NC
在分析問題複雜度的時候，我們通常會將複雜度類似的問題歸類在一起。P類的問題都是屬於可以在Polynomial Time解決，意思是當問題的資料量為N，我們具有演算法可以在N的常數次方內，用一部電腦(嚴謹來說是Deterministic Turing Machine)解決這個問題。而如果有一個問題是屬於P-Complete，代表：
1、這個問題本身屬於P類問題
2、所有P類的問題都是Reducible到這個問題
上述的2是什麼意思呢？直觀一點想就是「能夠解決P-Complete問題的演算法，也可以解決所有屬於P的問題」，那顯然「能夠解決P-Complete問題的演算法的廣泛性較大，就不太可能針對特定問題做最佳化」，所以「能夠解決P-Complete問題的演算法，通常效能是比較差」。
讀者可能會問：針對特定問題做最佳化是要怎麼做？其實有一個常用的最佳化方法即是平行處理，假設同時使用兩部電腦做運算，預期應該可以用一半的時間解決同樣的問題。因此，如果有問題可以透過平行運算來降低解決問題所需時間，這類問題我們就稱為NC。
至於P-Complete類的問題，跟NC類的問題，到底是不是有共通處呢？很不幸到目前為止，似乎還沒有人知道是否存在一個演算法，可以用平行處理解決P-Complete的問題；而且似乎也還沒有人知道是否P-Complete一定無法平行處理。目前大家還在尋找可以平行處理P-Complete問題的演算法。
這世界上存在著更困難的問題：目前為止似乎無法在Polynomial Time解決的問題，簡單說這類問題隨著資料量越大，似乎解決問題所需的時間會呈指數成長…有一個非常有名的問題類別叫NP-Complete，即是屬於似乎無法在Polynomial Time解決的問題，詳細可以看旗標出版的「白話演算法！培養程式設計的邏輯思考」。
三、Circuit Value Problem
上一節都是學理的描述，我們現在來看一個非常有名的P-Complete問題：Circuit Value Problem (Ladner, 1975)。這個問題是想知道一組輸入，經過一大堆AND跟OR的邏輯運算後，輸出到底是什麼？從圖二範例可以知道，我們必須先算出AND的結果，然後將AND的結果輸入到OR，最後算出OR的結果。把問題推廣成更複雜的邏輯運算，會發現我們必須從輸入開始，依序往輸出端計算，才能算出正確的結果。而這種問題到目前為止，還沒有找到可以平行處理的演算法。
四、馬可夫決策過程有多複雜
我們要怎麼知道馬可夫決策過程的複雜度呢？現在我們要用的策略是檢查是否Circuit Value Problem可以Reducible到馬可夫決策過程(Papadimitriou and Tsitsiklis, 1987)。
現在，我們來改寫Circuit Value Problem。我們先把輸入、AND、以及OR如圖三的方式做狀態編碼，轉換成馬可夫決策過程裡環境的狀態，然後我們額外加一個狀態q。
接著，我們來建立狀態轉變的關係、轉變的機率、以及對應的回饋值。方法如下：
1、如果是輸入True，則代理人能選的動作只有0，狀態轉移到q狀態的機率是1，回饋值是0。
2、如果是輸入False，則代理人能選的動作只有0，狀態轉移到q狀態的機率是1，回饋值是-1。
3、如果是AND，若代理人選擇動作0則會有0.5的機率狀態會轉移到AND的第一個輸入的狀態。反之，動作1則會有0.5的機率狀態會轉移到AND的第二個輸入的狀態。回饋值都是0。
4、如果是OR，若代理人選擇動作0則狀態會轉移到OR的第一個輸入的狀態。反之，動作1則狀態會轉移到OR的第二個輸入的狀態。回饋值都是0。
這規則看起來很複雜…因此小編幫大家把規則套用在圖三的Circuit Value Problem，得到如表一跟圖四的結果。
經過轉換之後，我們就可以用解決馬可夫決策過程最佳化問題的演算法，來解Circuit Value Problem了！只要代理人有辦法找到一個策略，讓代理人從Start走到q，其累積回饋值的期望值是0，就代表這個Circuit Value Problem的結果是True；反之，如果代理人找到的最佳策略，其累積回饋值的期望值小於0，代表這個Circuit Value Problem的結果是False。
可是我們剛剛已經有說，如果問題A可以Reducible到問題B，代表解決問題B的方法比較廣泛，效能也可能比較差。而現在我們發現一個P-Complete問題(Circuit Value Problem)可以Reducible到馬可夫決策過程，然後稍早也提到目前為止還沒有人知道有什麼平行處理的方法可以解決P-Complete的問題。因此我們可以得到一個不幸的結論：目前為止不存在一個演算法可以用平行處理解決馬可夫決策過程。
重點整理
1、目前還沒有找到一個平行處理的演算法可以解決P-Complete的問題。
2、可以使用平行處理的演算法解決的問題屬於NC類的問題。
3、透過確認一個已知類別的問題可以Reducible到新問題，可以知道新問題的類別。
4、馬可夫決策過程最佳化屬於P-Complete的問題，因此目前似乎不存在一個平行處理的演算法。
參考資料
1、Ladner R. E. (1975). The Circuit Value Problem is Log Space Complete for P. SIGACT News, 7(1), pp. 18–20.
2、Papadimitriou C. H. and Tsitsiklis J. N. (1987). The Complexity of Markov Decision Process. Mathematics of Operations Research, 12(3), pp. 441–450.
關於作者
Chia-Hao Li received the M.S. degree in computer science from Durham University, United Kingdom. He engages in computer algorithm, machine learning, and hardware/software codesign. He was former senior engineer in Mediatek, Taiwan. His currently research topic is the application of machine learning techniques for fault detection in the high-performance computing systems.
