http://hi.baidu.com/magiccaslte/blog/item/b2d9f09500472c43d1135e93.html


一個(gè)偶爾的機(jī)會(huì)接觸到了MDP，馬爾可夫決策過程，突然發(fā)現(xiàn)多年的困惑有點(diǎn)頭緒了，分享一段東西。

以下東西摘自某博士論文部分（若有版權(quán)問題請(qǐng)及時(shí)告知）：

以哲學(xué)觀點(diǎn)來看，人類來到世間至少有三件事要做：認(rèn)識(shí)世界；改造世界；享受世界。

在這其中，學(xué)習(xí)類問題對(duì)應(yīng)認(rèn)識(shí)世界，而決策類問題便是和改造世界緊密相關(guān)的。決策問題伴隨著人們的日常生活，大至公司乃至國(guó)家的戰(zhàn)略性決定，小至個(gè)人利益相關(guān)的一些選擇。‘決策’又區(qū)別于簡(jiǎn)單的‘決定’以及‘選擇’。它通常涉及的是一個(gè)過程，其最終對(duì)應(yīng)的行動(dòng)的執(zhí)行一般是多步的。在每一步，都要去做一個(gè)選擇。不同的選擇，不同的行動(dòng)，導(dǎo)致不同的結(jié)果，進(jìn)而也意味著不同的收益。決策不能孤立的進(jìn)行，若不考慮現(xiàn)在與將來的聯(lián)系，很難在整個(gè)過程中獲得最好的收益，就如同在一次長(zhǎng)跑比賽中，我們不能在起點(diǎn)就用盡全力沖刺一樣。事實(shí)上，決策問題與人們的社會(huì)生活的聯(lián)系是如此密切，可以說，一切社會(huì)實(shí)踐活動(dòng)都離不開決策，甚至，從辨證的觀點(diǎn)看，若是把主觀世界也當(dāng)作客觀世界的一部份，那么學(xué)習(xí)本身也是一個(gè)改造世界的過程，其過程也一樣講究策略，我們改造就是自己罷了。

對(duì)于智能體而言，當(dāng)其面對(duì)客觀世界中存在的一個(gè)待解決的問題時(shí)，首先，他的學(xué)習(xí)能力使其在主觀世界中獲得了對(duì)該問題的一個(gè)抽象的描述，對(duì)應(yīng)為問題的模型，這其中通常包括：

¨        問題所有可能的狀態(tài)，

¨        問題發(fā)展過程的演變規(guī)律，

¨        智能體在過程中可以做出的選擇，

¨        智能體所期望的結(jié)果等。

事實(shí)上，這就是MDP模型的基本構(gòu)成部分，

而所謂的智能體進(jìn)行決策，也就是指智能體在此模型的基礎(chǔ)上，基于問題過程的規(guī)律進(jìn)行規(guī)劃，利用智能體可行的選擇參與改變過程，使其朝自身期望的結(jié)果發(fā)展，最終解決問題。總的來說，決策基于問題的模型再結(jié)合規(guī)劃的方法兩部分完成。在人工智能領(lǐng)域，馬爾可夫決策過程是用來建模規(guī)劃問題的一個(gè)基本理論模型。以其為基礎(chǔ)，進(jìn)一步發(fā)展出一系列更具一般性的決策模型，如部分可觀察馬爾可夫決策過程，分布式馬爾可夫決策過程，部分可觀察的隨機(jī)博弈及半馬爾可夫決策過程等等。

決策總是與一個(gè)過程相聯(lián)系的（當(dāng)然，從廣義上來看，過程可以只有一步）。智能體要在過程中做出合適的選擇，將過程的發(fā)展引入對(duì)自身有利的方向，必然需要了解描述過程發(fā)展變化的知識(shí)。相對(duì)于窮舉所有變化，如果某些知識(shí)，不止一次可被用來推斷過程發(fā)展，即為規(guī)律。主體更需要就是這種精簡(jiǎn)的知識(shí)。

馬爾可夫過程正是具有一類普遍共性的過程。這類共性既是馬爾可夫性，也稱無后效性。由俄羅斯數(shù)學(xué)家馬爾可夫于1907提出。所謂無后效性，指的是這樣一種性質(zhì)：某階段的狀態(tài)一旦確定，則此后過程的演變不再受此前各狀態(tài)的影響。也就是說，“未來與過去無關(guān)”，當(dāng)前的狀態(tài)是此前歷史的一個(gè)完整總結(jié)，此前的歷史只能通過當(dāng)前的狀態(tài)去影響過程未來的演變。具體地說，如果一個(gè)問題被劃分各個(gè)階段之后，階段 I 中的狀態(tài)只能通過狀態(tài)轉(zhuǎn)移方程去影響階段 I+1 中的狀態(tài)的得來，與其他狀態(tài)沒有關(guān)系，特別是與未發(fā)生的狀態(tài)沒有關(guān)系，這就是無后效性。從更本質(zhì)的的角度來理論，可以認(rèn)為馬爾可夫性來源于對(duì)因果性和時(shí)間的連續(xù)性以及單向性的認(rèn)可。

馬爾可夫性用來描述過程的規(guī)律類似數(shù)學(xué)中使用遞推公式描述數(shù)列一樣，并且特點(diǎn)是遞推式只用到了前面一項(xiàng)。做為區(qū)別，比如著名的斐波拉契(Fibonacci)數(shù)列，1，1，2，3，5……的遞推公式F(n)=F(n-1)+F(n-2)就用到了前面的兩項(xiàng)。假設(shè)我們構(gòu)造一個(gè)過程，逐次去讀取數(shù)列中的每一項(xiàng)，任何一個(gè)時(shí)刻的狀態(tài)便是讀取到的數(shù)字。那么，斐波拉契數(shù)列對(duì)應(yīng)的便不是一個(gè)馬爾可夫過程。描述規(guī)律的方式很多，把握“當(dāng)前的狀態(tài)是此前歷史的一個(gè)完整總結(jié)”這一要點(diǎn)后，很多過程可以被轉(zhuǎn)化描述為馬爾可夫過程。當(dāng)然，前提是，可以做到當(dāng)前狀態(tài)完整總結(jié)歷史這點(diǎn)。但事實(shí)上完美總是相對(duì)而言的，從后面不確定性的討論也可以看到。從這個(gè)角度來說，馬爾可夫過程是一個(gè)很實(shí)用的理論。在馬爾可夫過程上做決策的好處顯而易見，我們可以忽略歷史的影響，也無需再去不斷的保存歷史信息，一切規(guī)劃都只要從當(dāng)前狀態(tài)出發(fā)即可。它所蘊(yùn)含的思想是將智能體有限的規(guī)劃能力引導(dǎo)至更有價(jià)值的方向。

馬爾可夫決策過程與馬爾可夫過程的本質(zhì)區(qū)別就是多了主體即決策者的介入。下面將依次簡(jiǎn)單介紹馬爾可夫決策過程(Markov Decision Processes, MDP)，部分可觀察馬爾可夫決策過程(Partially Observable Markov Decision Processes, POMDP)，分布式部分馬爾可夫決策過程（Decentralized-POMDP, DEC-POMDP），部分可觀察的隨機(jī)博弈(Partially Observable Stochastic Games, POSG)及半馬爾可夫決策過程(Semi-MDP)之間的區(qū)別與聯(lián)系。

50年代R.貝爾曼研究動(dòng)態(tài)規(guī)劃時(shí)和L.S.沙普利研究隨機(jī)對(duì)策時(shí)已出現(xiàn)馬爾可夫決策過程的基本思想。R.A.霍華德(1960)和D.布萊克韋爾(1962)等人的研究工作奠定了馬爾可夫決策過程的理論基礎(chǔ)。1965年，布萊克韋爾關(guān)于一般狀態(tài)空間的研究和E.B.丁金關(guān)于非時(shí)齊（非時(shí)間平穩(wěn)性）的研究，推動(dòng)了這一理論的發(fā)展。1960年以來，馬爾可夫決策過程理論得到迅速發(fā)展，應(yīng)用領(lǐng)域不斷擴(kuò)大。凡是以馬爾可夫過程作為數(shù)學(xué)模型的問題，只要能引入決策和效用結(jié)構(gòu)，均可應(yīng)用這種理論。

在人工智能領(lǐng)域中，對(duì)決策類問題的求解過程也可以稱為規(guī)劃。經(jīng)典規(guī)劃一般基于確定式的環(huán)境模式，如搜索算法A*等。這類方法在現(xiàn)實(shí)應(yīng)用中有很大的局限性。面對(duì)現(xiàn)實(shí)中的規(guī)劃問題，主體對(duì)環(huán)境特性的把握常常是不完整的，正是由于這種知識(shí)的缺失，造成了不確定性。馬爾可夫決策模型則可以處理這類問題。利用下圖信息集合劃分的方式，可以更清晰的理解不確定性，以及馬爾可夫決策過程(MDP)與下面將提到部分可觀察馬爾可夫決策過程(POMDP)的區(qū)別。

針對(duì)某個(gè)決策問題，從信息或者知識(shí)的角度我們區(qū)分出如下所示3個(gè)依次為包含關(guān)系的集合：

圖1.1 決策問題中的信息劃分

A集合：為客觀存在的影響過程的全部信息，是整個(gè)客觀世界的世界狀態(tài)中與問題所對(duì)應(yīng)過程相關(guān)的因素。

B集合：為影響智能體主觀決策的信息，進(jìn)一步解釋，是智能體主觀上知道存在，并能夠把握運(yùn)用的一些信息。因?yàn)閷?duì)于某些因素，即便智能體知道應(yīng)該與過程相關(guān)，但無法把握運(yùn)用，這些信息也不會(huì)影響智能體決策。比如，一般都認(rèn)為擲硬幣，正反面的概率各50%。事實(shí)上，風(fēng)力，擲硬幣的具體操作方式，拋出軌跡，用力情況，地面情況等都會(huì)影響過程結(jié)果，而這些因素通常無法把握運(yùn)用，即使考慮進(jìn)來，也難以改變決策。因此，這類智能體知道存在卻無法把握利用的信息，及主觀上根本不知道其存在而客觀上卻影響過程的因素，構(gòu)成了B集合與A集合的差別。同時(shí)，也正是這些差別，造成了不確定性的存在。從另一個(gè)角度，只要B不是空集，基于應(yīng)用的需求，就存在進(jìn)行決策的意義。但對(duì)不確定性仍需進(jìn)行刻畫，于是便引入了統(tǒng)計(jì)意義上概率。

C集合：為智能體總是能觀察到的信息。現(xiàn)實(shí)中很多決策過程，對(duì)于B集合中的信息，智能體有時(shí)觀察不到。比如踢足球，自己身后球員的位置是會(huì)影響決策的，但卻可能會(huì)觀察不到。

根據(jù)定義內(nèi)容，首先有前提A>=B>=C，進(jìn)而可以對(duì)問題做下面的分類：

1> 當(dāng) A=B=C時(shí)是一個(gè)確定性問題。

2> 當(dāng) A>=B=C時(shí)是一個(gè)MDP問題。

3> 當(dāng) A>=B>C時(shí)是一個(gè)POMDP問題。

MDP本身既可以處理確定性問題，也可處理不確定性問題。而POMDP在MDP模型上進(jìn)行了一定擴(kuò)展，引入了對(duì)觀察不確定性的處理。從一定意義上也可以認(rèn)為，MDP是POMDP的一種極端的情況，即決策相關(guān)信息全部可觀察。

MDP及POMDP模型中都認(rèn)為決策的智能體只有一個(gè)，并把其它一切因素都?xì)w于客觀環(huán)境。這些因素一部分是確定性的知識(shí)；另一部分則是已歸入統(tǒng)計(jì)概率的不確定性，認(rèn)為在當(dāng)前條件下，從處理問題的實(shí)際情況出發(fā)，不適合再進(jìn)行探究，只作概率推理。當(dāng)一個(gè)過程中，有多個(gè)智能體同時(shí)決策合作來解決一個(gè)問題時(shí)，上述模型是否適用的關(guān)鍵因素即其他智能體的策略是否已知。策略是決策的結(jié)果，指出在過程某個(gè)狀態(tài)要采用哪個(gè)行動(dòng)。如果認(rèn)為其他智能體策略已知，無論是確定性的策略亦或含概率表示的不確定性策略，那么其他智能體一樣可以歸入環(huán)境，仍可使用MDP或POMDP模型處理。否則，其它智能體會(huì)采用何種策略也是需要納入考慮的，在生成智能體自身決策的同時(shí)，也要生成其他智能體的決策，這是其客觀過程本身的模型決定的。分布式馬爾可夫決策過程(DEC-MDP)及分布式部分可觀察馬爾可夫決策過程(DEC-POMDP)可以處理這類多智能體合作問題。

在現(xiàn)實(shí)應(yīng)用中，多智能體間除了合作也可能存在對(duì)抗，這類問題可以歸為博弈。其中本質(zhì)的區(qū)別即智能體間收益評(píng)價(jià)的不同。合作類問題，各個(gè)智能體有相同的收益評(píng)價(jià)，或者說有共同的目標(biāo)；而博弈類問題，各個(gè)智能體收益評(píng)價(jià)存在區(qū)別，甚至完全對(duì)立。部分可觀察的隨機(jī)博弈(POSG)便是進(jìn)一步擴(kuò)展的一個(gè)決策模型，可以處理這類帶有不確定性的博弈問題。

半馬爾可夫過程又可以稱為非時(shí)齊馬爾可夫過程，這是相對(duì)于一般的時(shí)齊馬爾可夫過程而言的。所謂時(shí)齊是指過程的每?jī)蓚€(gè)相鄰狀態(tài)點(diǎn)間的時(shí)間間隔是一致的，對(duì)應(yīng)決策過程則是每步行動(dòng)的執(zhí)行時(shí)間是定長(zhǎng)的。非時(shí)齊則是描述了一類更一般的情況，對(duì)應(yīng)決策過程中行動(dòng)的執(zhí)行時(shí)間并不固定，甚至是時(shí)間上的一個(gè)概率分布。

我的收獲：早些年研究的東西，基本思路是有一定的科學(xué)理論依據(jù)的，只是出發(fā)點(diǎn)有了問題，所以難逃計(jì)算量的恐怖。就像目前的彩票研究者一樣，最終的常理的結(jié)論是預(yù)知性不明朗，靠運(yùn)氣吧。現(xiàn)在想想其實(shí)換一個(gè)研究層面去研究，然后按原來的方法計(jì)算，很多層面的東西還是相當(dāng)有可能的。感謝數(shù)學(xué)，感謝馬爾可夫。