介面膜
[拼音]：Ma’erkefu juece guocheng
[英文]：Markovian decision process
研究一類可週期地或連續地進行觀察的隨機動態系統的最優化問題。在各個時刻根據觀察到的狀態，從它的允許決策（控制、行動、措施等）集合中選用一個決策而決定了系統下次的轉移規律與相應的執行效果。並假設這兩者都不依賴於系統過去的歷史。在各個時刻選取決策的目的，是使系統執行的全過程達到某種最優執行效果，即選取控制（影響）系統發展的最優策略。
基本概念
以簡化的機器維修問題為例來說明。設機器的執行有兩種狀態：正常（記作1）和故障(記作2)。在任一時段，如正常執行，可得收益10元，到下一時段，機器仍保持正常執行的概率為 0.7，出現故障的概率為0.3。正常執行時，惟一可供選擇的決策是繼續生產（記作α1），如出了故障，則有兩種決策可供選擇，一是快修（記作α2），需費用5元，且在該時段內能修復的概率為0.6；一是慢修（記作α3），需費用2.5元，在該時段能修復的概率則為0.4。狀態轉移如圖1
和圖2
所示。圖中的方框表示狀態，箭頭表示狀態轉移，其上的數字表示相應的轉移概率。根據各時段初觀察到的狀態來確定採取的決策，使得整個執行期的某種期望收益達到最大的問題，就是此例的最優化問題。
可以看出，每個時段的狀態轉移概率與收益依賴於選取的決策。以q(j│i，α)表示由狀態i採取決策α的時段到下一時段初轉移到狀態j的概率；以r(i，α)表示在狀態i下采取決策α時其相應時段的收益。於是，此例各值如表1所示。
從狀態的允許決策集裡選取決策的規則稱為決策規則。這裡可供選取的決策規則有二：一是在觀察到狀態1取α1，觀察到狀態2取α2，並將此決策規則記為ƒ1；一是觀察到狀態1取α1，觀察到狀態2取α3，並將此決策規則記為ƒ2。它們對應的轉移概率分別由表2和表3給出。機器在t＝0時所用的決策規則是從ƒ1與ƒ2中任選一個，記為ƒ0，則t=0到t=1的狀態轉移概率為q(j|i，ƒ0(i))，i，j=1，2；在t=0到t=1的時段獲得收益r(i，ƒ0(i))，i=1，2。設t=1時，選用的決策規則記為ƒ1，它也是ƒ1與ƒ2中之一，則由t=1到t=2的狀態轉移概率為q(j｜i，ƒ1(i))，i=1，2。如此類推，可得決策序列(ƒ0，ƒ1，…)，稱之為策略，並記作π(它是一般策略的一種特殊形式)。當 t=0時從某一初始狀態出發並使用這種策略π，則狀態的演變形成一馬爾可夫過程。這裡在t=0到t=1時段獲得的效益是確定的，其值為r(i，ƒ0(i))，而t=1到t=2時段的收益則是隨機的，它的期望值為
。由於收益是從t=0開始計算的，基於經濟上利率的考慮，未來時段的收益應打折扣，時段t=n的收益應乘以βn(0<β<1)，β稱為折扣因子，n≥1。於是長期的期望折扣總收益為
這種收益值是衡量諸維修策略優劣的一種指標，它顯然是初始狀態i和策略π的函式。
一般說來，一個離散時間馬爾可夫決策過程（簡記為MDP）必須包含下列五個組成部分。
（1）狀態空間S，它是系統的全體狀態所成之集合。如上例的S={1， 2}。
（2）
A
(i)是狀態i允許的決策集，i∈S。若令
，則
A
稱為決策空間。如上例中，A
(1)={α1}，A
(2)={α2，α3}，其中A
(2)就是在狀態2允許採取的決策（快修與慢修）集。（3）轉移概率q(j│i，α)，式中i∈S，α∈
A
A
(i)， 到時刻t+1系統轉移到狀態j的概率（它與時刻t 以前的歷史無關）。（4）收益（或費用）函式r(i，α)，式中 i∈S，α∈
A
(i)，它表示在觀察到狀態i而選取決策α∈A
(i)的時段所獲得的收益（它也與系統的歷史無關）。（5）指標函式V(π，i)，它依賴於初始狀態i∈S與所選用的策略π∈П（П是全體允許策略之集），是衡量選用策略效果好壞的指標。因此，一個離散時間馬爾可夫決策過程，可按上述意義定義為五元組{S，(
A
(i)│i∈S)，q，r，V }。每個組成部分均可採取各種不同形式。例如，S 和A
(i)(i∈S)各自可以是有限集、可數無窮集、完備可分距離空間的波雷耳集或解析集等。轉移概率可以是時間齊次的、非時間齊次的、半馬氏的或漂移的等。收益函式和指標函式也可以有多種形式。這五個成分各取一種形式就是一種MDP模型，因此，有許多不同形式的MDP模型。策略與指標的類別
從狀態的允許決策集裡選取決策的所謂決策規則，就是指，從狀態空間S 到決策空間
A
的一個對映ƒ，對所有i∈S都有ƒ(i)∈A
(i)成立。全體決策規則組成的集合，記作F。設在離散時刻t=0，1，2，…來考察系統，對每一時刻t選定一個決策規則ƒt∈F，於是這樣選定的序列(ƒ0，ƒ1，ƒ2，…)就是一個特殊策略，其特殊之處在於，每個時刻t選取決策的規則既與系統在時刻t以前的歷史無關，又是由狀態i所對應的一個確定的決策ƒt(i)∈A
(i)，i∈S，因此這種策略稱為決定性馬氏策略，簡稱馬氏策略。如果各個時刻選取的決策，雖然不依賴於系統的歷史，卻不是確定地選取，而是按某一條件概率分佈在允許決策集上選取的，條件是當時觀察到的狀態，那麼相應的策略稱為隨機馬氏策略。一般策略是各個時刻決策的選取，既依賴於系統的歷史，又要根據觀察到的狀態隨機選取的情形。若各個時刻的決策規則都是相同(決定性)的馬氏策略，則稱為平穩策略。即(ƒ，ƒ，ƒ，…)，記作ƒ∞。類似地可定義隨機平穩策略。由於平穩策略的簡單性，因此它是實際應用中特別重要的一類策略。全體一般策略構成的集合，稱為策略空間；其他各種特殊形式的策略的全體，就稱為相應的策略類，如馬氏策略的全體稱為馬氏策略類等。它們的習用符號如下:策略空間П，隨機馬氏策略類Пm，馬氏策略類П
，隨機平穩策鑼Пs，平穩策略類П
。各類之間顯然有下列包含關係：
給定了系統在t=0的初始狀態Y0和使用的策略π，令Yt和墹t分別表示系統在時刻t的狀態和所選取的決策，則定義一隨機序列(Y0，墹0，Y1，墹1，…)，通常稱為由π產生的馬爾可夫決策過程。常用的指標有三種，分別定義如下：
（1）有限階段指標VN為
(1)式中N是給定的正整數；r是收益函式；Eπ是使用策略π時取期望值的符號；VN(π;i)表示t=0時從i出發，使用策略π時在N + 1階段內的總期望收益。
（2）折扣指標Vβ為
(2)式中β(0≤β <1)是給定的，稱為折扣因子。Vβ(π；i)表示 t=0從 i出發，使用策略π 時的長期折扣總期望收益。折扣指標也可用於有限階段情形，這時求和的上限為N 。
（3）平均指標堸為
(i∈S)， (3)式中VN(π;i)由(1)給出。堸(π;i)表示t=0從i出發，使用策略π時的長期的時間平均期望收益。
對於不同類別的指標，可以建立不同的策略最優性概念。例如，若存在π*∈П，使得對於所有i∈S，π∈П都有
(當r為費用時，則為
，則稱π*關於折扣指標是最優的，簡稱β最優的。類似地可以定義關於有限階段指標和平均指標的最優性。對同一指標也可以定義不同的最優性概念。研究各種模型中最優策略的存在性、最優條件以及最優策略的求解方法等，是MDP的主要內容。
扣折模型
假定S及所有
A
(i) (i∈S)均為有限集。其指標由(2)式給出。可以證明，對此模型存在平穩策略是最優策略。因此，在П上尋求最優策略，只需在小得多的平穩策略類П
上去尋求。以前面的機器維修問題為例來說明尋求最優平穩策略的一種演算法，亦即策略迭代法。
首先，策略求值。對給定的或前一輪迭代求出的平穩策略ƒ∞，由下列方程組求解值函式V(i)。
所得的解V(i)滿足
。在前述機器維修問題中，給定β =0.9與平穩策略(ƒ 2)∞，於是方程組(4)即為
10+0.9[0.7V(1)+0.3V(2)]=V(1)，
-2.5+0.9[0.4V(1)+0.6V(2)]=V(2)，解方程組，得
V(1)=53.77，V(2)=36.64。
其次，策略改進。對於前一步求得的值函式
求一個g∈F，使得
若達到左端最大的α不只一個，則任取其一，但是，如ƒ(i)含於其中，則取g(i)=ƒ(i)。又如在機器維修問題中，上一步已求得V(1)和V(2)，再解(5)式：當i=1時，
A
(1)僅含α1，故(5)的解就是α1；當i=2時，(5)即為
即g(1)=α1，g(2)=α2，故g=ƒ1。
最後，終止規則。若g呏ƒ，則ƒ∞是所求的最優策略，而終止計算。若g扝ƒ，則以g代ƒ，再轉入第二步驟，由於F僅包含有限個決策規則，因此經有限次迭代必終止於一最優平穩策略。例如機器維修問題中，F 僅包含兩個元素，故(ƒ1)∞必為最優策略，再經第一步驟可解得
簡史
MDP 是確定性動態規劃與馬爾可夫過程結合的產物。1953年L.S.沙普利在“隨機對策”一文中曾討論過對策的一方是無意志的情形，其實是一種 MDP模型。1957年，R.貝爾曼正式提出MDP的名稱和藉助於最優性原理求解最優策略的方法。1960年，R.A.霍華德在動態規劃基礎上對一類MDP模型提出了策略迭代法。同年，有人發現尋求最優策略問題可以化為求解相應的線性規劃問題。在這項工作中，S 和
A
都假定為有限集，而且只在П
或Пs上探討最優策略。1962年，D.布萊克韋爾在較大的策略類П
上探討最優策略。他和Ε.Б.登金於1965年分別研究了S、
A
都是完備可分距離空間中的波萊爾集與S 、A
都是可數無窮集且轉移律是非時間齊次的MDP，推動了MDP的理論的發展。MDP已在裝置的更換和維修以及庫存論、排隊論、控制工程、可靠性理論、搜尋論、水庫排程、林漁業管理、電話網路等的最優化問題中都有應用，並正在向工程、生物、經濟等領域滲透。
目前，MDP的工作日益增多，有獨立發展的趨勢。有關的文章，除較多地使用動態規劃、馬爾可夫決策過程的名稱外，還有使用馬爾可夫決策規劃、序貫決策過程、受控馬氏鏈等名稱的。研究者注意的新問題主要有：模型更加一般化；連續時間、狀態部分可觀察、半馬氏、適應性等模型的理論探討；特殊模型更有效的解法；如何用易於處理的模型去逼近複雜的模型等。