POMDPs算法復(fù)雜度對比分析研究*

仵 博，鄭紅燕，馮延蓬

（深圳職業(yè)技術(shù)學(xué)院 教育技術(shù)與信息中心，廣東 深圳 518055）

在人工智能領(lǐng)域，規(guī)劃和決策是許多問題的核心．在連續(xù)的時間片上，對于規(guī)定的問題，智能體通過選擇合適的動作序列來完成既定目標(biāo)，這種決策稱之為序貫決策，這個過程稱之為序貫決策過程．在序貫決策過程中，智能體必須在貪婪獲取短期目標(biāo)與長期規(guī)劃之間做出平衡[1]．部分可觀察馬爾可夫決策過程[2]（Partially Observable Markov Decision Processes，POMDPs）是智能體在動態(tài)不確定環(huán)境下進(jìn)行序貫決策的一種理想數(shù)學(xué)模型．因此，動態(tài)不確定環(huán)境下的智能體序貫決策問題可以看成 POMDPs的求解問題．由于POMDPs能夠更加客觀地、準(zhǔn)確地描述真實世界，使它成為研究隨機(jī)決策過程的重要分支，最近成為計算機(jī)、控制和管理等學(xué)科研究的熱點[3]．

綜述現(xiàn)有算法，按照年代劃分，可大致分為兩個階段．第一階段（20世紀(jì)末），主要是精確求解算法[4]，代表算法為 Witness算法和 Incremental Pruning算法．第二階段（21世紀(jì)初），主要是近似求解算法，可再分為在線求解算法和離線求解算法．在線近似算法主要是樹查找算法[5]，將POMDPs看成智能體與環(huán)境之間的博弈，在每一個信念狀態(tài)結(jié)點，智能體必須選擇一個動作，然后環(huán)境隨機(jī)選擇下一時刻的觀察，在給定的深度內(nèi)，通過查找獲得最佳動作．樹查找算法可分為蒙特卡羅采樣算法、分支界限裁剪算法和啟發(fā)式搜索算法．離線求解算法主要分值函數(shù)近似算法、策略近似算法、基于網(wǎng)格近似算法和分層近似算法等．值函數(shù)近似算法分為完全觀察 MDP近似算法和基于點的近似算法[6]．由于基于點的近似算法符合人類認(rèn)識世界的規(guī)律，因此，最近幾年得到眾多學(xué)者的重視．基于點的算法主要思想是在給定的信念狀態(tài)點上更新整個a - vector ，可分為分批處理更新和異步更新．但是，現(xiàn)有算法都陷入“維數(shù)災(zāi)”和“歷史災(zāi)”問題，造成理想的POMDPs模型無法在實際工程中得到應(yīng)用．本文首先詳細(xì)分析POMDPs精確算法的復(fù)雜度，指出造成兩個“維數(shù)災(zāi)”的原因；然后介紹基于點的離線算法的算法思想和求解過程，分析比較現(xiàn)有算法的時間復(fù)雜度和各自的信念點采集和更新方法；接著介紹基于在線算法的思想和理論基礎(chǔ)，實驗分析現(xiàn)有算法的優(yōu)劣；最后簡介POMDPs的應(yīng)用情況，指出信念狀態(tài)空間有效降維以及基于點的離線算法與在線算法的有機(jī)結(jié)合將是解決POMDPs2個“維數(shù)災(zāi)”難題的有效方法．

1 POMDPs模型

在文中，除特殊說明外，上標(biāo)代表時間，下標(biāo)代表集合中的具體實例，例如 si代表狀態(tài)集合中的第i個狀態(tài)；st代表t時刻的狀態(tài)； P(st=si)代表t時刻狀態(tài)為 si時的概率．有時根據(jù)描述問題的需要，沒有上下標(biāo)的表示當(dāng)前時刻的變量，上標(biāo)是'的表示下一時刻的變量，例如s表示當(dāng)前時刻的狀態(tài)；而 s '表示下一時刻的狀態(tài)．

POMDPs通常用六元組來描述[7]，其序貫決策示意圖如圖1所示．狀態(tài)集合S={s1,s2,s3,...,sn}，動作集合A={ a1,a2,a3,...,am}，觀察集合Z={z1,z2,z3,...,zl}，分別表示Agent所有可能的狀態(tài)、動作和觀察．狀態(tài)轉(zhuǎn)移函數(shù)集合T(si,a,sj)=P(sj|si,a)，是Agent在狀態(tài) si下采用動作a，可能轉(zhuǎn)移到狀態(tài) sj的概率．狀態(tài)轉(zhuǎn)移函數(shù)滿足馬爾可夫特性，即公式（1）成立．

由于狀態(tài)轉(zhuǎn)移函數(shù)是完全條件概率分布，即公式

（2）成立．

觀察函數(shù)集合O(si,aj,zk)=P(zk|si,aj)，當(dāng)Agent在狀態(tài) si下采用動作 aj，觀察為 zk的概率，報酬函數(shù)集合R:S′A′ZaR，R為負(fù)值時是損失，為正值時是報酬．

圖1 POMDPs模型

t時刻的信念狀態(tài)B由公式（3）來描述，由公式（4）來計算．

使用Bellman公式計算POMDPs的值函數(shù)V和策略p，計算如下：

POMDPs決策的策略是將信念狀態(tài)映射到動作，同時滿足使智能體選擇的動作能夠獲得環(huán)境報酬的累計值最大．其中，g為折扣因子，其目標(biāo)是讓期望值收斂．

最優(yōu)策略*p是使折扣報酬值和的期望值最大．

其中，rt為指數(shù)，(bt)表示在t時刻的動作，為- ve ctor集合．

在POMDPs中最優(yōu)策略是從所有的信念狀態(tài)中選取一個動作使得期望值最大，信念狀態(tài)空間為其中，R的大小為因此，求解信念狀態(tài)空間是一個“維數(shù)災(zāi)”問題．

Sondik[8]證明任何t時間段的值函數(shù)可以用來表示，每一個維的超平面．在每個信念狀態(tài)上的值函數(shù)定義如下：

每一個a-vector對應(yīng)著一個最優(yōu)策略，每一個策略對應(yīng)一個動作．t時間段的-vector集合可以定義如下：

由于信念狀態(tài)空間很大，值函數(shù) Vt(b)無法直接計算，但是與之相對應(yīng)的可以由來迭代計算．精確求解算法如下：

2 基于點的離線算法

基于點的值迭代算法主要思想：根據(jù)誤差判定條件，給出固定的有限可達(dá)信念狀態(tài)集合在B上進(jìn)行更新操作，避免對整個信念狀態(tài)空間單純體D進(jìn)行求解，從而在有限的誤差范圍內(nèi)快速求解．其中，對于每一個信念狀態(tài)點，值函數(shù)至多包含一個因此，基于點的值函數(shù)可以用與之相對應(yīng)的集合來表示．其主要步驟如下[9]：

步驟 2：由于在有限信念狀態(tài)點上進(jìn)行更新操作，因此可以使用簡單的加法操作代替交叉和操作．

終止條件可以是時間，可以是固定的迭代次數(shù)，也可以是期望獲得的策略質(zhì)量等，主要根據(jù)實際應(yīng)用而定．在終止條件出現(xiàn)之前，可達(dá)信念狀態(tài)點的采集和信念狀態(tài)點的更新交替進(jìn)行．

目前，基于點的值迭代算法主要的區(qū)別在于可達(dá)信念狀態(tài)點的采集，信念狀態(tài)點的更新操作基本相同．本節(jié)主要對現(xiàn)有的算法進(jìn)行復(fù)雜度分析，見表1．

圖2 可達(dá)信念狀態(tài)樹

表1 幾種經(jīng)典算法分析與比較

PBVI和SARSOP是完全Backup操作，時間復(fù)雜度為其他更新算法時間復(fù)雜度都要小于完全Backup操作．它們之間的主要區(qū)別為信念點采集算法[6]．從采集算法時間復(fù)雜度分析可知，Perseus算法和FSVI算法最優(yōu)．

與其他POMDPs近似求解算法相比較，基于點的 POMDPs算法具有較高的效率和較快的收斂．但是，無論使用何種基于點的POMDPs值迭代算法，都不可能在有限時間遍歷整個可達(dá)信念狀態(tài)空間．因而，離線算法只能夠適用于較小規(guī)模模擬問題，對于大規(guī)模實際問題中無法實現(xiàn)算法收斂．

3 在線算法

POMDPs離線算法是求解全局最優(yōu)策略或者全局近似最優(yōu)策略，分為策略規(guī)劃和策略執(zhí)行兩個階段．在線算法是求解當(dāng)前最優(yōu)策略或者當(dāng)前近似最優(yōu)策略，它根據(jù)時間約束條件，將整個策略規(guī)劃和策略執(zhí)行分成若干個小的規(guī)劃和執(zhí)行．由于在線算法只考慮當(dāng)前信念狀態(tài)空間下的最優(yōu)策略，因此，可達(dá)信念狀態(tài)空間很小，利用已有的基于點的迭代算法可以很快求解值函數(shù)．兩類算法的比較如圖3所示．

圖3 在線與離線方法比較

在線算法將整個決策周期分為若干個小的時間片，每個時間片內(nèi)分別進(jìn)行策略規(guī)劃和策略執(zhí)行．在規(guī)劃階段，根據(jù)當(dāng)前信念狀態(tài)計算出最優(yōu)執(zhí)行動作，可分為兩個步驟．第一步是建立可達(dá)信念狀態(tài)與或樹（AND-OR Tree），如圖2所示．在與或樹中，根節(jié)點為當(dāng)前信念狀態(tài)，孩子節(jié)點為可達(dá)信念狀態(tài)點，可達(dá)信念狀態(tài)點使用公式（4）來計算．信念結(jié)點為OR結(jié)點，其輸出弧權(quán)重為 RB(b,a)．兩層信念點之間的結(jié)點為 AND結(jié)點，其輸出弧權(quán)重為 P (z|b,a)．第二步是使用公式（6）計算當(dāng)前信念狀態(tài)的值函數(shù)，計算過程是通過邊緣結(jié)點的向上傳播算法實現(xiàn)．在執(zhí)行階段，根據(jù)當(dāng)前的信念狀態(tài)執(zhí)行最優(yōu)動作，并根據(jù)觀察更新當(dāng)前信念狀態(tài)和與或樹．

定理1的證明參見文獻(xiàn)[5]．從圖1與或樹可知，評估可達(dá)信念狀態(tài)的時間復(fù)雜度為由于 g ? [ 0,1)，當(dāng)D?￥時，定理 1的誤差將收斂到 0．因此，在線算法與離線算法的區(qū)別在于D的取值．在線算法對時間要求很苛刻，遍歷所有的可達(dá)信念狀態(tài)點是不可能的．需要在盡可能長地遍歷信念狀態(tài)點使誤差盡可能小與盡可能快地求解近似最優(yōu)解之間做出權(quán)衡．因此，在線算法必須對可達(dá)信念狀態(tài)點進(jìn)行裁剪，使之對策略求解最有用．目前存在三類在線算法：蒙特卡羅采樣算法、分支界限裁剪算法和啟發(fā)式搜索算法．

評價在線算法主要有2個指標(biāo)，一個是要滿足系統(tǒng)實時性的要求，盡可能快地求解近似最策略；另一個是滿足誤差最小化目標(biāo)，盡可能降低平均折扣報酬值與原始報酬值之間的誤差．針對第二個評價指標(biāo)，本文采用文獻(xiàn)[5]的誤差分析方法論，定義誤差降低比率EBR(b)和下界誤差值LBI(b)．最佳的在線算法應(yīng)該是使EBR(b)和LBI(b)平均值最大的算法．其中，在與或樹T上定義(b)的上下界分別為UT(b)和 LT(b)，定義邊緣結(jié)點集合 F (T)的上下界分別為 U (b)和 L (b)：

本文實驗對象是RockSample[7,8][11]，時間約束為每秒執(zhí)行一個動作，下界值計算統(tǒng)一采用 PBVI方法，上界值計算統(tǒng)一采用QMDP方法，這樣可以更加公平地評價算法本身的優(yōu)劣．表2的結(jié)果是經(jīng)過20次重復(fù)實驗，取它們的平均值．本文的仿真平臺為Matlab R2010a，運(yùn)行環(huán)境為32位Windows7，Intel(R) Core(TM) i3 CPU：3.07GHz，RAM：4GB．

從表2可知，在報酬值指標(biāo)上，AEMS2[5]、BI-POMDPs[10]和 HSVI-BFS[11]3種算法基本相同．在EBR和LBI指標(biāo)上，AEMS2和HSVI-BFS兩種算法基本相同．信念狀態(tài)結(jié)點數(shù)主要是衡量算法的空間復(fù)雜度的，根據(jù)實驗結(jié)果可知，RTBSS算法最小，其他算法都比較大，主要原因在于RTBSS采用分支界限裁剪算法．在結(jié)點重用率指標(biāo)上，AEMS2最優(yōu)，RTBSS算法每次計算都是重新計算，沒有重用已經(jīng)計算過的信念狀態(tài)．在計算時間指標(biāo)上，RTBSS算法耗時較小，因為它計算的信念狀態(tài)點較少．

表2 不同在線算法幾種參數(shù)的比較

4 POMDPs應(yīng)用情況

由于 POMDPs能夠客觀地描述真實世界模型，使其在實際中得到越來越廣泛的應(yīng)用，成為計算機(jī)、控制和管理等學(xué)科研究的熱點和難點．在科學(xué)應(yīng)用領(lǐng)域，科學(xué)家主要將其應(yīng)用到自主機(jī)器人控制上[12,13]，例如：在太空中的漫步機(jī)器人、機(jī)器人導(dǎo)航、炸彈拆除、放射性廢物回收、深海探礦、管道網(wǎng)絡(luò)的檢修和維護(hù)等；在工業(yè)應(yīng)用領(lǐng)域[14]，例如機(jī)器生產(chǎn)和維護(hù)；在商業(yè)應(yīng)用領(lǐng)域，例如網(wǎng)絡(luò)故障查找和排除；在管理領(lǐng)域[15]，管理最優(yōu)化問題；在醫(yī)療領(lǐng)域[16]，醫(yī)療診斷；在軍事領(lǐng)域，例如：移動目標(biāo)的查找、跟蹤和拯救；目標(biāo)的辨認(rèn)；武器的使用分配等．

Wolf等人提出一種在線MC-RTBSS算法[17]，該算法是基于蒙特卡羅采樣算法對觀察結(jié)點進(jìn)行裁剪，并在無人飛機(jī)導(dǎo)航上進(jìn)行應(yīng)用，實驗表明該算法就有良好的實時性．He等人提出一種基于后驗信念概率分布的在線PBD算法[18]，該算法在科學(xué)探索和目標(biāo)監(jiān)控領(lǐng)域得到很好的應(yīng)用．Naveen等人將 POMDPs成功地應(yīng)用到無線傳感器網(wǎng)絡(luò)應(yīng)用中[19]，使該系統(tǒng)具有較高的低碳、高穩(wěn)定性等特性．Zhang等人對POMDPs信念狀態(tài)空間進(jìn)行壓縮[20]，降低求解問題的規(guī)模，并在治療前列腺上得到較好地應(yīng)用．

5 未來研究方向

目前，POMDPs規(guī)劃理論和算法雖然已經(jīng)取得了很多令人鼓舞的研究進(jìn)展，但對于實際工程中日益增加的復(fù)雜優(yōu)化決策問題，仍然需要在理論和算法方面開展創(chuàng)新研究，以進(jìn)一步提高算法在大規(guī)模連續(xù)空間問題中的快速收斂與泛化性能，并且在完善理論分析的同時，推進(jìn)POMDPs在實際系統(tǒng)中的廣泛應(yīng)用．其中，有待進(jìn)一步研究解決的重要課題包括：

1）高維信念狀態(tài)空間有效降維理論和方法

處理大規(guī)模高維數(shù)據(jù)是計算機(jī)技術(shù)發(fā)展的必然趨勢，探索高維數(shù)據(jù)的內(nèi)部特性，發(fā)掘其低維本質(zhì)表示是目前的研究方向．近十年來，《Science》和《Nature》雜志分別刊登多種高維降維新方法[21-27]，推動了降維方法的研究與發(fā)展．針對高維信念狀態(tài)空間，目前的研究結(jié)果中結(jié)構(gòu)化分解是一種有效方法[28-30]．然而，現(xiàn)有研究成果僅限于動態(tài)貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)為已知條件下有效．對于復(fù)雜的模型不確定的動態(tài)系統(tǒng)，其結(jié)構(gòu)往往是未知的，即狀態(tài)之間的獨立關(guān)系未知．如何采用未知的結(jié)構(gòu)進(jìn)行結(jié)構(gòu)化分解是目前尚需研究的重要課題．

在進(jìn)行信念狀態(tài)空間壓縮的同時，必須滿足壓縮后的信念狀態(tài)空間仍然能夠準(zhǔn)確地描述原來的客觀世界，也就是說根據(jù)壓縮后的信念狀態(tài)空間進(jìn)行的決策與根據(jù)壓縮前的信念狀態(tài)空間進(jìn)行的決策是一樣的．如何保證壓縮后的信念狀態(tài)空間是無損失的；或者如何保證壓縮后的損失信息不影響智能體做出正確的決策，這是進(jìn)行信念狀態(tài)空間壓縮時必須要解決的問題．目前關(guān)于這方面的文獻(xiàn)很少，現(xiàn)有信念狀態(tài)空間降維算法也很少涉及此類問題，所得結(jié)論具有一定的保守性．

2）基于點的POMDPs在線值迭代理論與方法

基于點的離線值迭代方法是在可達(dá)信念狀態(tài)空間單純體上求解值函數(shù)，可達(dá)信念狀態(tài)點隨著規(guī)劃時間的增加而成指數(shù)形式增長．另外，可達(dá)信念狀態(tài)點的采集是選擇一個信念狀態(tài)子集，使其既要克服計算難而充分小，又要滿足為獲得好的近似值函數(shù)而充分大．因而，如何采集可達(dá)信念狀態(tài)點，使之滿足以上條件是基于點的POMDPs值迭代算法所面臨的共同難題．

在線算法可以解決“歷史災(zāi)”問題，提高決策的實時性．但是，在線算法是以犧牲性能為代價．因此，可以將在線算法看成一種“短視”決策方法．將基于點的離線值迭代方法應(yīng)用到在線算法中，將會提高在線方法信念狀態(tài)與或樹遍歷的深度，從而更加逼近最優(yōu)值函數(shù)和最優(yōu)策略．

3）模型不確定情況下的 POMDPs規(guī)劃理論與方法

POMDPs規(guī)劃算法中，假設(shè)狀態(tài)轉(zhuǎn)移函數(shù)、觀察函數(shù)和報酬函數(shù)都是已知的，且為穩(wěn)態(tài)的．但是，在實際的動態(tài)系統(tǒng)中，狀態(tài)轉(zhuǎn)移函數(shù)通常是未知的，且為動態(tài)變化的，這種模型在實際的應(yīng)用中最為常見．如果使用穩(wěn)態(tài)模型描述動態(tài)系統(tǒng)，則會造成對動態(tài)系統(tǒng)建模的失真，在理論上也無法保證獲得真實近似最優(yōu)值函數(shù)和最優(yōu)策略．針對于此，需要智能體能夠在與動態(tài)不確定環(huán)境交互中進(jìn)行學(xué)習(xí)．然而，學(xué)習(xí)參數(shù)個數(shù)巨大，是一個典型的指數(shù)規(guī)模問題[31,32]．另外，在全部后驗信念狀態(tài)空間上求解規(guī)劃問題將遭遇更大的“維數(shù)災(zāi)”[33-36]．以上兩個難題使得目前的模型不確定情況下的POMDPs算法只能夠求解小規(guī)模問題（10-20個狀態(tài)），無法實現(xiàn)大規(guī)模問題的在線規(guī)劃和學(xué)習(xí)．如何克服不確定帶來的更大“維數(shù)災(zāi)”是目前研究的挑戰(zhàn)難題．

雖然POMDPs規(guī)劃的研究已經(jīng)取得了若干重要的進(jìn)展，并且在一些實際系統(tǒng)中逐步得到推廣應(yīng)用，但是仍然存在一系列理論和技術(shù)挑戰(zhàn)．隨著新的POMDPs規(guī)劃和學(xué)習(xí)理論與方法的建立和完善，作為復(fù)雜動態(tài)系統(tǒng)理想模型的POMDPs必將在實際工程中得到廣泛的應(yīng)用．

[1] Littman M L. A tutorial on Partially Observable Markov Decision Processes[J]. Journal of Mathematical Psychology, 2009，53（3）：119-125．

[2] Cao Xi-Ren, Guo Xian-ping. Partially Observable Markov Decision Processes With Reward Information:Basic Ideas and Models [J]. IEEE Transactions on Automatic Control, 2007，52（4）：677-681．

[3] Ross S, Pineau J, Chaibdraa B, et al. A Bayesian Approach for Learning and Planning in Partially Observable Markov Decision Processes[J]. Journal of Machine Learning Research, 2011，12：1729-1770．

[4] Paquet S. Distributed Decision-Making and Task Coordination in Dynamic Uncertain and Real-Time Multiagent Environments[D]. Québec: Laval University, 2006：56-92．

[5] Ross S, Pineau J, Paquet S, et al. Online Planning Algorithms for POMDPs[J]. Journal of Artificial Intelligence Research, 2008，32（6）：663-704．

[6] Robert K. Point-Based POMDP Solvers: Survey and Comparative Analysis[D]. Montreal: McGill University, 2010：34-78．

[7] Roy N, Gordon G. Finding Approximate POMDPs Solutions Through Belief Compression[J]. Journal of Artificial Intelligence Research, 2005，23（9）：1-40．

[8] Sondik E. The Optimal Control of Partially Observable Markov Decision Processes[D]. California:Stanford University, 1971：56-68．

[9] Pineau J, Gordon G, Thrun S. Anytime point-based approximations for large POMDPs[J]. Journal of Artificial Intelligence Research, 2006，27：335-380．

[10] Washington, R. BI-POMDPs: bounded incremental partially observable Markov model planning[C]//Steel S, Alami R. Proceedings of the 4th European Conference on Planning. Toulouse: Springer, 1997：440-451．

[11] Smith T, Simmons R. Point-based POMDPs algorithms:improved analysis and implementation[C]//Bacchus F,Jaakkola T. Proceedings of the 21th Conference on Uncertainty in Artificial Intelligence. Edinburgh: AUAI Press, 2005：542-547．

[12] Li Yan-jie, Yin Bao-qun, Xi Hong-sheng. Partially Observable Markov Decision Processes and Performance Sensitivity Analysis[J]. IEEE Transactions on Systems,Man & Cybernetics: Part B, 2008，38（6）：1645-1651．

[13] Lin R, Kraus S, Wilkenfeld J, et al. Negotiating with Bounded Rational Agents in Environments with Incomplete Information Using an Automated Agent[J].Artificial Intelligence, 2008，172（6-7）：823-851．

[14] Sotelo M A, Oca?a M, Bergasa L M, et al. Low Level Controller for a POMDPs Based on WiFi Observations[J]. Robotics & Autonomous Systems, 2007，55（2）：132-145．

[15] Krishnamurthy V, Dejan V. Optimal Threshold Policies for Multivariate POMDPs in Radar Resource Management[J]. IEEE Transactions on Signal Processing, 2009，57（10）：3954-3969．

[16] Williams J D., Young S. Partially Observable Markov Decision Processes for Spoken Dialog Systems[J].Computer Speech & Language, 2007，21（2）：393-422．[17] Wolf T B, Kochenderfer M J. Aircraft Collision Avoidance Using Monte Carlo Real-Time Belief Space Search[J]. Journal of Intelligent and Robotic Systems,2011，64：277-298．

[18] HE Rui-jie, Brunskill E, Roy N. Efficient Planning under Uncertainty with Macro-actions[J]. Journal of Artificial Intelligence Research, 2011，40：523-570．

[19] Naveen K P, Kumar A. Relay Selection for Geographical Forwarding in Sleep-Wake Cycling Wireless Sensor Networks[J]. IEEE Transactions on Mobile Computing,2011，10（12）：1-9．

[20] Zhang Jing-yu. Partially Observable Markov Decision Processes for Prostate Cancer Screening[D]. North Carolina: North Carolina State University, 2011：35-69．

[21] Lee D D, Seung H S. Learning the parts of objects by non-negative matrix factorization[J]. Nature, 1999，401：788-791．

[22] Tenenbaum J B, Silva V D, Langford J C. A global geometric framework for nonlinear dimensionality reduction. Science, 2000，290（5500）：2319-2323．

[23] Hinton G E, Salakhutdinov R R. Reducing the dimensionality of data with neural networks[J].Science, 2006，313（5786）：504-507．

[24] Evans J A, Foster J G. Metaknowledge[J]. Science,2011，331（6018）：721-725．

[25] Frey B J, Dueck D. Clustering by passing messages between data points [J]. Science, 2007，315（5814)）：972-976．

[26] Baraniuk R G. More is less: signal processing and the data deluge[J]. Science, 2011，331（6018）：717-719．

[27] Roweis S, Saul L. Nonlinear dimensionality reduction by locally linear embedding[J]. Science, 2000，290（5500）：2323-2326．

[28] Delgado K V, Sanner S, Barros L N d. Efficient solutions to factored MDPs with imprecise transition probabilities[J]. Artificial Intelligence, 2011，175：1498-1527．

[29] Boutilier C, Dearden R, Goldszmidt M. Stochastic dynamic programming with factored representtations[J]. Artificial Intelligence, 2000，121：49-107．

[30] Guestrin C, Koller D, Parr R, et al. Efficient solution algorithms for factored MDPs[J]. Journal of Artificial Intelligence Research, 2003，19：399-468．

[31] Tan V Y F, Anandkumar A, Willsky A S. Learning high-dimensional Markov forest distributions: analysis of error rates [J]. Journal of Machine Learning Research,2011，12：1617-1653．

[32] Poupart P, Vlassis N. Model-based Bayesian reinforcement learning in partially observable domains[C]//Padgham L, ParkesD. In Proceedings of the International Joint Conference on Autonomous Agents and Multi Agent Systems. New York: ACM Press, 2008：1025-1032．

[33] Andrieu C, Doucet A, Holenstein R. Particle Markov chain Monte Carlo methods [J]. Journal of the Royal Statistical Society. Series B, 2010，72（3）：269-342．

[34] Poupart P, Vlassis N, Hoey J, et al. An analytic solution to discrete Bayesian reinforcement learning[C]// Cohen W,Moore A. In Proceedings of the 23rd international conference on Machine learning. New York: ACM Press,2006：697-704．

[35] Wang Y, Won K S, Hsu D, et al. Monte Carlo Bayesian reinforcement learning[C]// Langford J, Pineau J. In Proceedings of the 29th International Conference on Machine Learning. Edingburgh Scotland: Omni Press,2012：1135-1142．

[36] 徐昕，沈棟，高巖青，等．基于馬氏決策過程模型的動態(tài)系統(tǒng)學(xué)習(xí)控制：研究前沿與展望[J]．自動化學(xué)報，2012，38（5）：673-687．