某某大學(xué)某某學(xué)院某某某2第8章決策理論規(guī)劃上一章的時(shí)空關(guān)聯(lián)規(guī)劃基于如下假設(shè)條件：確定性、完全可觀測(cè)、可達(dá)性目標(biāo)。本章將討論在上述假設(shè)之外如何進(jìn)行規(guī)劃的問(wèn)題，即決策理論規(guī)劃（Decision-TheoreticPlanning）。決策理論規(guī)劃的應(yīng)用非常廣泛，例如：高端機(jī)器人控制、醫(yī)藥治療、災(zāi)害救援、等等。因?yàn)椴煌男袆?dòng)會(huì)有不同的結(jié)果，某些動(dòng)作可能更有利，因此需要對(duì)實(shí)現(xiàn)目標(biāo)的潛力、風(fēng)險(xiǎn)、以及成本做出決策。第8章決策理論規(guī)劃引言3第8章決策理論規(guī)劃目錄4決策理論規(guī)劃概述馬爾科夫模型馬爾科夫決策過(guò)程的優(yōu)化控制動(dòng)態(tài)規(guī)劃決策理論是一種決策的理論框架，用于衡量行動(dòng)方案的優(yōu)劣。決策理論的基礎(chǔ)概率論（Gametheory）用于在給定的狀態(tài)下求得某個(gè)行動(dòng)可能結(jié)果的概率分布、以及合理性偏好函數(shù)。效用論（Utilitytheory）采用效用函數(shù)，使得智能主體偏好的規(guī)劃具有更高的預(yù)期效用最大期望效用（maximumexpectedutility,MEU）決策理論規(guī)劃概述決策理論（Decisiontheory）5但是，決策理論并未涉獵如何構(gòu)建具有高期望效用的規(guī)劃。決策理論規(guī)劃

=決策理論+人工智能規(guī)劃形式框架：馬爾科夫決策過(guò)程（Markovdecisionprocess）優(yōu)化控制：動(dòng)態(tài)規(guī)劃（Dynamicprogramming）、線性規(guī)劃（Linearprogramming）決策理論規(guī)劃≒不確定性環(huán)境規(guī)劃（planningunderuncertainty）從環(huán)境接收的信息是不完全或不完備的動(dòng)作并非總是得到同樣的結(jié)果需要在規(guī)劃的不同結(jié)果之間做出權(quán)衡馬爾科夫決策過(guò)程∈馬爾科夫模型（Markovmodels）決策理論規(guī)劃概述決策理論規(guī)劃（Decision-TheoreticPlanning）6杰羅姆·費(fèi)爾德曼（JeromeFeldman）和羅伯特·斯普勞爾（RobertSproull）

是最早從事決策理論規(guī)劃研究的學(xué)者第8章決策理論規(guī)劃目錄7決策理論規(guī)劃概述馬爾科夫模型馬爾科夫決策過(guò)程的優(yōu)化控制動(dòng)態(tài)規(guī)劃概述一種統(tǒng)計(jì)模型，用于對(duì)隨機(jī)變化的系統(tǒng)進(jìn)行建模。性質(zhì)馬爾科夫模型的下一個(gè)狀態(tài)只依賴于當(dāng)前的狀態(tài)，而與之前發(fā)生的事件無(wú)關(guān)。馬爾科夫模型馬爾科夫模型（Markovmodels）8

完全可觀測(cè)（fullyobservable）部分可觀測(cè)（partiallyobservable）自主

（autonomous）馬爾科夫過(guò)程

（Markovprocess）隱馬爾科夫模型

（HiddenMarkovmodel）控制（controlled）馬爾科夫決策過(guò)程

（Markovdecisionprocess）部分可觀測(cè)馬爾科夫決策過(guò)程

（PartiallyobservableMarkovdecisionprocess）四種馬爾科夫模型以俄羅斯數(shù)學(xué)家安德烈·馬爾科夫（AndreyMarkov）的名字命名。定義馬爾科夫模型隨機(jī)過(guò)程（Stochasticprocess,SP）9

隨機(jī)過(guò)程的實(shí)例細(xì)菌種群的增長(zhǎng)、由于熱噪聲或氣體分子的移動(dòng)而導(dǎo)致電流波動(dòng)等。隨機(jī)過(guò)程的應(yīng)用生物學(xué)、化學(xué)、生態(tài)學(xué)、神經(jīng)科學(xué)、物理學(xué)、以及工程和技術(shù)領(lǐng)域，如：圖像處理、信號(hào)處理、信息論、計(jì)算機(jī)科學(xué)、密碼學(xué)、電信等；此外，還被廣泛用于金融領(lǐng)域。隨機(jī)過(guò)程是針對(duì)隨機(jī)變化的現(xiàn)象而建立的系統(tǒng)的數(shù)學(xué)模型定義馬爾科夫模型馬爾科夫性質(zhì)（Markovproperty）10

所有的馬爾科夫模型都具有馬爾科夫性質(zhì)。無(wú)記憶性質(zhì)（memory-lessproperty）采用馬爾科夫模型的領(lǐng)域：預(yù)測(cè)建模（predicatemodeling）、概率預(yù)報(bào)（probabilisticforecasting）等。回置抽樣vs無(wú)回置抽樣馬爾科夫模型馬爾科夫性質(zhì)（Markovproperty）11對(duì)于一個(gè)隨機(jī)過(guò)程，回置抽樣（samplingwithoutreplacement）具備馬爾科夫性質(zhì)，而無(wú)回置抽樣（samplingwithreplacement）則不具備馬爾科夫性質(zhì)。例：一個(gè)壇子里有三個(gè)雞蛋，兩個(gè)紅皮的，一個(gè)白皮的。昨天拿出一個(gè)，今天再拿出一個(gè)，問(wèn)：明天拿出的雞蛋的顏色？若只知道今天拿出的雞蛋是紅皮的，而不知道昨天拿出雞蛋的顏色時(shí)，則明天拿出的最后一個(gè)雞蛋顏色的概率是紅白各占二分之一；只有既知道昨天、又知道今天拿出的雞蛋的顏色時(shí)，才能判斷明天拿出的最后一個(gè)雞蛋的顏色。顯然，這種觀察雞蛋顏色的隨機(jī)過(guò)程問(wèn)題不具有馬爾科夫性質(zhì)。

這是一個(gè)無(wú)回置抽樣的實(shí)例?；刂贸闃觱s無(wú)回置抽樣馬爾科夫模型馬爾科夫性質(zhì)（Markovproperty）12對(duì)于一個(gè)隨機(jī)過(guò)程，回置抽樣（samplingwithoutreplacement）具備馬爾科夫性質(zhì)，而無(wú)回置抽樣（samplingwithreplacement）則不具備馬爾科夫性質(zhì)。例：用一個(gè)操縱桿控制一個(gè)玩具車(chē)，可操控玩具車(chē)朝前、后、左、右方向行進(jìn)，記錄儀可顯示玩具車(chē)當(dāng)前的方向。當(dāng)記錄儀顯示玩具車(chē)處于前進(jìn)方向時(shí)，操縱桿向左，問(wèn)：玩具車(chē)的行進(jìn)方向？這個(gè)問(wèn)題的答案不言自明。

這是一個(gè)回置抽樣的實(shí)例。定義馬爾科夫模型馬爾科夫過(guò)程（Markovprocess,MP）13

馬爾科夫過(guò)程是具有馬爾科夫性質(zhì)的隨機(jī)過(guò)程安德烈·馬爾科夫早在1900年就研究了馬爾科夫過(guò)程，并于1906年就此發(fā)表了論文。離散時(shí)間的馬爾科夫過(guò)程馬爾科夫模型馬爾科夫過(guò)程（Markovprocess,MP）14

馬爾科夫過(guò)程是一類(lèi)重要的隨機(jī)過(guò)程，是隨機(jī)模擬方法的基礎(chǔ)，例如：機(jī)動(dòng)車(chē)輛的巡航控制系統(tǒng)、機(jī)場(chǎng)旅客的隊(duì)列、貨幣兌換率、存儲(chǔ)系統(tǒng)、某些物種的增長(zhǎng)、搜索引擎、等等。離散時(shí)間的馬爾科夫過(guò)程馬爾科夫模型馬爾科夫過(guò)程（Markovprocess,MP）15布朗運(yùn)動(dòng)過(guò)程（Brownianmotionprocess）一維泊松過(guò)程（Poissonprocess）例：賭徒破產(chǎn)（gambler'sruin）一個(gè)賭博成癮的賭徒，每次賭博獲勝時(shí)就將下一次賭注提高到固定比例的金額，但在輸?shù)魰r(shí)不會(huì)減少。即使是每次下注都有贏錢(qián)的預(yù)期，但最終該賭徒不可避免地會(huì)輸?shù)镁?。連續(xù)時(shí)間的馬爾科夫過(guò)程定義馬爾科夫模型馬爾科夫鏈（Markovchain）16

吉布斯采樣（Gibbssampling）和馬爾科夫鏈蒙特卡羅（MarkovChainMonteCarlo,MCMC），被用于模擬具有特定概率分布的隨機(jī)對(duì)象，并且已經(jīng)在貝葉斯統(tǒng)計(jì)中得到廣泛應(yīng)用。用馬爾科夫鏈表示某股票市場(chǎng)一周內(nèi)的牛市、熊市或停滯的市場(chǎng)趨勢(shì)。定義馬爾科夫模型馬爾科夫決策過(guò)程（Markovdecisionprocess,MDP）17

馬爾科夫決策過(guò)程是有限離散事件的馬爾科夫過(guò)程的擴(kuò)展，

在自主式馬爾科夫過(guò)程的基礎(chǔ)上增加了改變狀態(tài)的動(dòng)作、以及環(huán)境的獎(jiǎng)懲（reward）等。作用馬爾科夫模型馬爾科夫決策過(guò)程（Markovdecisionprocess,MDP）18是決策理論規(guī)劃的形式化方法是一種離散時(shí)間隨機(jī)控制過(guò)程（discretetimestochasticcontrolprocess）是構(gòu)建序貫決策（sequentialdecision-making）方法的理論框架馬爾科夫決策過(guò)程中主體與環(huán)境之間的狀態(tài)、獎(jiǎng)懲、以及動(dòng)作的交互過(guò)程。定義馬爾科夫模型隱馬爾科夫模型（HiddenMarkovmodel）19隱馬爾科夫模型可以表示為簡(jiǎn)單的動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)（dynamicBayesiannetwork），

在機(jī)器學(xué)習(xí)中發(fā)揮了重要作用，而與規(guī)劃問(wèn)題沒(méi)有直接關(guān)系。是一種基于統(tǒng)計(jì)學(xué)的馬爾科夫模型，用于描述一個(gè)含有隱含未知參數(shù)的馬爾科夫過(guò)程。其狀態(tài)可通過(guò)觀測(cè)向量序列觀察到，每個(gè)觀測(cè)向量都是通過(guò)某些概率密度分布表現(xiàn)出的狀態(tài)，形成一個(gè)具有相應(yīng)概率密度分布的狀態(tài)序列。隱馬爾科夫模型是一個(gè)雙重隨機(jī)過(guò)程，即具有一定狀態(tài)數(shù)的隱馬爾科夫鏈并顯示隨機(jī)函數(shù)集。定義馬爾科夫模型部分可觀測(cè)馬爾科夫決策過(guò)程

（PartiallyobservableMarkovdecisionprocess,POMDP20

部分可觀測(cè)馬爾科夫決策過(guò)程是馬爾科夫決策過(guò)程在部分可觀測(cè)環(huán)境下的擴(kuò)展。第8章決策理論規(guī)劃目錄21決策理論規(guī)劃概述馬爾科夫模型馬爾科夫決策過(guò)程的優(yōu)化控制動(dòng)態(tài)規(guī)劃定義馬爾科夫決策過(guò)程的優(yōu)化控制策略（Policy）22確定性策略（deterministicpolicy）隨機(jī)策略（stochasticpolicy）

馬爾科夫決策過(guò)程優(yōu)化控制的核心問(wèn)題是找到一個(gè)策略。馬爾科夫決策過(guò)程的優(yōu)化控制策略（Policy）23

該策略由智能主體加以實(shí)施，其目的是控制被建模為馬爾科夫決策過(guò)程的環(huán)境。

定義馬爾科夫決策過(guò)程的優(yōu)化控制獎(jiǎng)懲（Reward）24

片段是主體與環(huán)境進(jìn)行反復(fù)交互的過(guò)程中形成一些子序列。具有這種片段的任務(wù)被稱(chēng)為片段化任務(wù)（episodictasks）。片段在終止?fàn)顟B(tài)（terminalstate）下結(jié)束。片段（episodes）定義馬爾科夫決策過(guò)程的優(yōu)化控制折扣（Discounting）25考慮折扣：

馬爾科夫決策過(guò)程的優(yōu)化控制價(jià)值函數(shù)（valuefunction）26

馬爾科夫決策過(guò)程的優(yōu)化控制算法通過(guò)價(jià)值函數(shù)來(lái)計(jì)算最優(yōu)策略。馬爾科夫決策過(guò)程的優(yōu)化控制貝爾曼公式（Bellmanequation）27

上述公式被稱(chēng)為貝爾曼最優(yōu)化方程（Bellmanoptimalityequation）。它表明，最優(yōu)策略下的狀態(tài)值必須等于該狀態(tài)最佳動(dòng)作的預(yù)期回報(bào)。馬爾科夫決策過(guò)程的優(yōu)化控制貝爾曼公式（Bellmanequation）28

最優(yōu)狀態(tài)值是：

最優(yōu)動(dòng)作選擇可以表示為：

馬爾科夫決策過(guò)程的優(yōu)化控制優(yōu)化控制方法29

主要方法：基于模型（Model-based）、模型無(wú)關(guān)（Model-free）?；谀Ｐ偷姆椒ň褪莿?dòng)態(tài)規(guī)劃（Dynamicprogramming）。其基本假設(shè)是已知一個(gè)MDP模型，并且可以使用貝爾曼公式來(lái)計(jì)算價(jià)值函數(shù)和策略，大多數(shù)方法是計(jì)算狀態(tài)價(jià)值函數(shù)（statevaluefunctions）。用動(dòng)態(tài)規(guī)劃對(duì)馬爾科夫決策過(guò)程進(jìn)行優(yōu)化控制，屬于決策理論規(guī)劃的范疇→本章。模型無(wú)關(guān)的方法就是強(qiáng)化學(xué)習(xí)（Reinforcementlearning）。它通過(guò)與環(huán)境的互動(dòng)形成模擬策略，生成狀態(tài)轉(zhuǎn)換和獎(jiǎng)懲樣本，再將這些樣本用于估計(jì)狀態(tài)-動(dòng)作價(jià)值函數(shù)（state-actionvaluefunctions）。用強(qiáng)化學(xué)習(xí)對(duì)馬爾科夫決策過(guò)程進(jìn)行優(yōu)化控制，屬于機(jī)器學(xué)習(xí)的范疇→第11章?；谀Ｐ蛌s模型無(wú)關(guān)動(dòng)態(tài)規(guī)劃

vs強(qiáng)化學(xué)習(xí)第8章決策理論規(guī)劃目錄30決策理論規(guī)劃概述馬爾科夫模型馬爾科夫決策過(guò)程的優(yōu)化控制動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃（DynamicProgramming）31將DynamicProgramming譯成動(dòng)態(tài)規(guī)劃，是因?yàn)镻rogramming的含義使然1950年代初，美國(guó)數(shù)學(xué)家理查德·貝爾曼（RichardBellman）在研究多步?jīng)Q策過(guò)程（multistepdecisionprocess）的優(yōu)化問(wèn)題時(shí)，將多步過(guò)程轉(zhuǎn)化為一系列單步問(wèn)題，利用各階段之間的關(guān)系逐個(gè)加以解決，從而創(chuàng)立了動(dòng)態(tài)規(guī)劃理論（TheoryofDynamicProgramming）。在決策理論規(guī)劃中，動(dòng)態(tài)規(guī)劃被用于對(duì)馬爾科夫決策過(guò)程進(jìn)行優(yōu)化控制，計(jì)算馬爾科夫決策過(guò)程的最優(yōu)策略。動(dòng)態(tài)規(guī)劃的兩個(gè)核心方法：策略迭代（Policyiteration）和價(jià)值迭代（Valueiteration），分別由羅納德·霍華德（RonaldAHoward）和理查德·貝爾曼提出。ItwasfirstcoinedbyRichardBellmaninthe1950s,atimewhencomputerprogrammingwasanesotericactivitypracticedbysofewpeopleastonotevenmeritaname.Backthenprogrammingmeant“planning,”and“dynamicprogramming”wasconceivedtooptimallyplanmultistageprocesses.動(dòng)態(tài)規(guī)劃策略迭代（Policyiteration）32策略迭代算法：1）策略評(píng)估（policyevaluation），計(jì)算當(dāng)前策略的價(jià)值函數(shù)；2）策略改進(jìn)（policyimprovement），通過(guò)價(jià)值函數(shù)的最大化來(lái)計(jì)算改善的策略；3）重復(fù)上述操作，直到收斂于一個(gè)最優(yōu)策略。動(dòng)態(tài)規(guī)劃策略評(píng)估（policyevaluation）33已知貝爾曼公式：