http://hi.baidu.com/magiccaslte/blog/item/b2d9f09500472c43d1135e93.html
一個偶爾的機會接觸到了MDP，馬爾可夫決策過程，突然發現多年的困惑有點頭緒了，分享一段東西。
以下東西摘自某博士論文部分（若有版權問題請及時告知）：
以哲學觀點來看，人類來到世間至少有三件事要做：認識世界；改造世界；享受世界。
在這其中，學習類問題對應認識世界，而決策類問題便是和改造世界緊密相關的。決策問題伴隨著人們的日常生活，大至公司乃至國家的戰略性決定，小至個人利益相關的一些選擇。‘決策’又區別于簡單的‘決定’以及‘選擇’。它通常涉及的是一個過程，其最終對應的行動的執行一般是多步的。在每一步，都要去做一個選擇。不同的選擇，不同的行動，導致不同的結果，進而也意味著不同的收益。決策不能孤立的進行，若不考慮現在與將來的聯系，很難在整個過程中獲得最好的收益，就如同在一次長跑比賽中，我們不能在起點就用盡全力沖刺一樣。事實上，決策問題與人們的社會生活的聯系是如此密切，可以說，一切社會實踐活動都離不開決策，甚至，從辨證的觀點看，若是把主觀世界也當作客觀世界的一部份，那么學習本身也是一個改造世界的過程，其過程也一樣講究策略，我們改造就是自己罷了。
對于智能體而言，當其面對客觀世界中存在的一個待解決的問題時，首先，他的學習能力使其在主觀世界中獲得了對該問題的一個抽象的描述，對應為問題的模型，這其中通常包括：
¨ 問題所有可能的狀態，
¨ 問題發展過程的演變規律，
¨ 智能體在過程中可以做出的選擇，
¨ 智能體所期望的結果等。
事實上，這就是MDP模型的基本構成部分，
而所謂的智能體進行決策，也就是指智能體在此模型的基礎上，基于問題過程的規律進行規劃，利用智能體可行的選擇參與改變過程，使其朝自身期望的結果發展，最終解決問題。總的來說，決策基于問題的模型再結合規劃的方法兩部分完成。在人工智能領域，馬爾可夫決策過程是用來建模規劃問題的一個基本理論模型。以其為基礎，進一步發展出一系列更具一般性的決策模型，如部分可觀察馬爾可夫決策過程，分布式馬爾可夫決策過程，部分可觀察的隨機博弈及半馬爾可夫決策過程等等。
決策總是與一個過程相聯系的（當然，從廣義上來看，過程可以只有一步）。智能體要在過程中做出合適的選擇，將過程的發展引入對自身有利的方向，必然需要了解描述過程發展變化的知識。相對于窮舉所有變化，如果某些知識，不止一次可被用來推斷過程發展，即為規律。主體更需要就是這種精簡的知識。
馬爾可夫過程正是具有一類普遍共性的過程。這類共性既是馬爾可夫性，也稱無后效性。由俄羅斯數學家馬爾可夫于1907提出。所謂無后效性，指的是這樣一種性質：某階段的狀態一旦確定，則此后過程的演變不再受此前各狀態的影響。也就是說，“未來與過去無關”，當前的狀態是此前歷史的一個完整總結，此前的歷史只能通過當前的狀態去影響過程未來的演變。具體地說，如果一個問題被劃分各個階段之后，階段 I 中的狀態只能通過狀態轉移方程去影響階段 I+1 中的狀態的得來，與其他狀態沒有關系，特別是與未發生的狀態沒有關系，這就是無后效性。從更本質的的角度來理論，可以認為馬爾可夫性來源于對因果性和時間的連續性以及單向性的認可。
馬爾可夫性用來描述過程的規律類似數學中使用遞推公式描述數列一樣，并且特點是遞推式只用到了前面一項。做為區別，比如著名的斐波拉契(Fibonacci)數列，1，1，2，3，5……的遞推公式F(n)=F(n-1)+F(n-2)就用到了前面的兩項。假設我們構造一個過程，逐次去讀取數列中的每一項，任何一個時刻的狀態便是讀取到的數字。那么，斐波拉契數列對應的便不是一個馬爾可夫過程。描述規律的方式很多，把握“當前的狀態是此前歷史的一個完整總結”這一要點后，很多過程可以被轉化描述為馬爾可夫過程。當然，前提是，可以做到當前狀態完整總結歷史這點。但事實上完美總是相對而言的，從后面不確定性的討論也可以看到。從這個角度來說，馬爾可夫過程是一個很實用的理論。在馬爾可夫過程上做決策的好處顯而易見，我們可以忽略歷史的影響，也無需再去不斷的保存歷史信息，一切規劃都只要從當前狀態出發即可。它所蘊含的思想是將智能體有限的規劃能力引導至更有價值的方向。
馬爾可夫決策過程與馬爾可夫過程的本質區別就是多了主體即決策者的介入。下面將依次簡單介紹馬爾可夫決策過程(Markov Decision Processes, MDP)，部分可觀察馬爾可夫決策過程(Partially Observable Markov Decision Processes, POMDP)，分布式部分馬爾可夫決策過程（Decentralized-POMDP, DEC-POMDP），部分可觀察的隨機博弈(Partially Observable Stochastic Games, POSG)及半馬爾可夫決策過程(Semi-MDP)之間的區別與聯系。
50年代R.貝爾曼研究動態規劃時和L.S.沙普利研究隨機對策時已出現馬爾可夫決策過程的基本思想。R.A.霍華德(1960)和D.布萊克韋爾(1962)等人的研究工作奠定了馬爾可夫決策過程的理論基礎。1965年，布萊克韋爾關于一般狀態空間的研究和E.B.丁金關于非時齊（非時間平穩性）的研究，推動了這一理論的發展。1960年以來，馬爾可夫決策過程理論得到迅速發展，應用領域不斷擴大。凡是以馬爾可夫過程作為數學模型的問題，只要能引入決策和效用結構，均可應用這種理論。
在人工智能領域中，對決策類問題的求解過程也可以稱為規劃。經典規劃一般基于確定式的環境模式，如搜索算法A*等。這類方法在現實應用中有很大的局限性。面對現實中的規劃問題，主體對環境特性的把握常常是不完整的，正是由于這種知識的缺失，造成了不確定性。馬爾可夫決策模型則可以處理這類問題。利用下圖信息集合劃分的方式，可以更清晰的理解不確定性，以及馬爾可夫決策過程(MDP)與下面將提到部分可觀察馬爾可夫決策過程(POMDP)的區別。
針對某個決策問題，從信息或者知識的角度我們區分出如下所示3個依次為包含關系的集合：
圖1.1 決策問題中的信息劃分
A集合：為客觀存在的影響過程的全部信息，是整個客觀世界的世界狀態中與問題所對應過程相關的因素。
B集合：為影響智能體主觀決策的信息，進一步解釋，是智能體主觀上知道存在，并能夠把握運用的一些信息。因為對于某些因素，即便智能體知道應該與過程相關，但無法把握運用，這些信息也不會影響智能體決策。比如，一般都認為擲硬幣，正反面的概率各50%。事實上，風力，擲硬幣的具體操作方式，拋出軌跡，用力情況，地面情況等都會影響過程結果，而這些因素通常無法把握運用，即使考慮進來，也難以改變決策。因此，這類智能體知道存在卻無法把握利用的信息，及主觀上根本不知道其存在而客觀上卻影響過程的因素，構成了B集合與A集合的差別。同時，也正是這些差別，造成了不確定性的存在。從另一個角度，只要B不是空集，基于應用的需求，就存在進行決策的意義。但對不確定性仍需進行刻畫，于是便引入了統計意義上概率。
C集合：為智能體總是能觀察到的信息。現實中很多決策過程，對于B集合中的信息，智能體有時觀察不到。比如踢足球，自己身后球員的位置是會影響決策的，但卻可能會觀察不到。
根據定義內容，首先有前提A>=B>=C，進而可以對問題做下面的分類：
1> 當 A=B=C時是一個確定性問題。
2> 當 A>=B=C時是一個MDP問題。
3> 當 A>=B>C時是一個POMDP問題。
MDP本身既可以處理確定性問題，也可處理不確定性問題。而POMDP在MDP模型上進行了一定擴展，引入了對觀察不確定性的處理。從一定意義上也可以認為，MDP是POMDP的一種極端的情況，即決策相關信息全部可觀察。
MDP及POMDP模型中都認為決策的智能體只有一個，并把其它一切因素都歸于客觀環境。這些因素一部分是確定性的知識；另一部分則是已歸入統計概率的不確定性，認為在當前條件下，從處理問題的實際情況出發，不適合再進行探究，只作概率推理。當一個過程中，有多個智能體同時決策合作來解決一個問題時，上述模型是否適用的關鍵因素即其他智能體的策略是否已知。策略是決策的結果，指出在過程某個狀態要采用哪個行動。如果認為其他智能體策略已知，無論是確定性的策略亦或含概率表示的不確定性策略，那么其他智能體一樣可以歸入環境，仍可使用MDP或POMDP模型處理。否則，其它智能體會采用何種策略也是需要納入考慮的，在生成智能體自身決策的同時，也要生成其他智能體的決策，這是其客觀過程本身的模型決定的。分布式馬爾可夫決策過程(DEC-MDP)及分布式部分可觀察馬爾可夫決策過程(DEC-POMDP)可以處理這類多智能體合作問題。
在現實應用中，多智能體間除了合作也可能存在對抗，這類問題可以歸為博弈。其中本質的區別即智能體間收益評價的不同。合作類問題，各個智能體有相同的收益評價，或者說有共同的目標；而博弈類問題，各個智能體收益評價存在區別，甚至完全對立。部分可觀察的隨機博弈(POSG)便是進一步擴展的一個決策模型，可以處理這類帶有不確定性的博弈問題。
半馬爾可夫過程又可以稱為非時齊馬爾可夫過程，這是相對于一般的時齊馬爾可夫過程而言的。所謂時齊是指過程的每兩個相鄰狀態點間的時間間隔是一致的，對應決策過程則是每步行動的執行時間是定長的。非時齊則是描述了一類更一般的情況，對應決策過程中行動的執行時間并不固定，甚至是時間上的一個概率分布。
我的收獲：早些年研究的東西，基本思路是有一定的科學理論依據的，只是出發點有了問題，所以難逃計算量的恐怖。就像目前的彩票研究者一樣，最終的常理的結論是預知性不明朗，靠運氣吧。現在想想其實換一個研究層面去研究，然后按原來的方法計算，很多層面的東西還是相當有可能的。感謝數學，感謝馬爾可夫。