基于環境狀態分布優化的POMDP 值迭代求解算法

摘 要： "基于點的值迭代算法是一類解決 POMDP 問題的有效算法，PBVI 是基于點集的經典算法，但是其算法效率較為低下。FSVI使用內在的 MDP 最優策略來降低算法復雜度，但求解大規模問題的效果較差。為解決上述問題，提出了基于環境狀態分布優化的前向搜索值迭代算法（PBVI-OSD），通過基于權重值的 QMDP 選出最佳的動作，基于信念狀態和轉換函數選取最大可能的狀態，基于動作和狀態從觀察中隨機選取一個觀察概率大于閾值的觀察，由此獲得更具探索價值的后繼信念點集，提升值迭代收斂的質量。在四個基準問題上的實驗表明，相比于 FSVI 和 PBVI，PBVI-OSD能保證收斂效率，特別是在大規模問題上能收斂到更好的全局最優解。

關鍵詞： "部分可觀測馬爾可夫決策過程； 可達信念空間； 智能體規劃

中圖分類號： "TP18 """文獻標志碼： A

文章編號： "1001-3695（2022）02-008-0374-05

doi：10.19734/j.issn.1001-3695.2021.08.0310

Probability-based value iteration on optimal state "distribution algorithm for POMDP

Zhu Rongxin1，2， Wang Xuan3， Liu Feng3， Zhao Zhihong3，4

（1.School of Cyberspace Security， Hainan University， Haikou 570208， China; 2.Nanjing Normal University of Special Education， Nanjing 210038， China; 3.Software Institute， Nanjing University， Nanjing 210093， China; 4.Nanjing Tech University， Nanjing 211816， China）

Abstract： nbsp;Point-based value iteration methods are a class of practical algorithms for solving the POMDP model. PBVI is a classical point-based value iteration method with low efficiency. FSVI can reduce the complexity and improve efficiency significantly by using the optimal strategy of the underlying MDP. However， it is not efficient in the large-scale POMDP problems. The paper proposed a probability-based value iteration on optimal state distribution algorithm for POMDP （PBVI-OSD）. Du-ring the exploration， PBVI-OSD used the alias method to sample the action "a * based on weighted "QMDP "function and sample the state based on "b "and the transition function. Then PBVI-OSD selected the observation "z "whose probability was greater than the threshold， and got the successor point "b "with great value from "a * and "z ， which ensured the effect of value iteration. Experiment results of four benchmarks show that PBVI-OSD can achieve better global optimal solutions than FSVI and PBVI， especially in large-scale problems.

Key words： "partially observable Markov decision process （POMDP）; reachable belief space; agent planning

0 引言

部分可觀察馬爾可夫決策過程（partially observable Markov decision processes，POMDP）提供了一個強大的數學框架，解決在不確定環境中的順序決策問題，可應用于較多復雜的場景，如機器人探索任務［1］、反隱身探測任務［2］和癌癥檢測［3］等。然而，精確求解POMDP復雜度太高，導致POMDP在很長一段時間內難以應用到實際問題的處理，因此，出現了很多近似求解POMDP的方法［4］?；邳c的POMDP算法從信念空間中取樣出具有代表性的信念點集，在可達信念點集上進行值函數迭代，直至收斂［5］。盡管基于點的算法是近似算法，但顯著降低了值迭代的代價，使得可以做更多次有效迭代，從而能夠提升全局的效率，因此成為了當前研究的熱點。

基于點的POMDP方法的關鍵是如何采樣信念點集 B 。PBVI是經典的基于密度標準擴展探索點集的算法，對于當前探索點集 B中的每個b，選取其后繼中距B最遠的b *進行探索［4］，使得從可達信念空間中選取的信念點盡可能分散。然而，PBVI算法在擴展信念點集中計算代價大。因此出現了HSVI［6］和GapMin［7］等基于值函數的近似求解方案，這些方案根據最優值函數上界來選擇最優動作探索最優可達信念點集，保證收斂到全局最優［8］。然而這些方案在大規模問題上存在收斂效率不高的缺陷，因此難以應用到在線問題的求解中。FSVI［9］等基于MDP的近似解法根據MDP的策略在信念空間獲得的最優動作構建求解降低了復雜度，從而在很大程度上提升了效率。然而，現有FVSI方法沒有利用模型的環境信息，在無峰值狀態的問題中會退化為隨機策略，使得FSVI很難應用到實際的大規模問題中。近年來，HHVI［10］嘗試雜合PBVI和HSVI探索的標準，但也不能避免維護上下界值函數的開銷。

為了解決上述問題，本文提出一種新的基于環境狀態分布優化的前向搜索值迭代算法PBVI-OSD（probability-based value iteration on optimal state distribution）。該算法基于MDP優化策略，有效利用環境反饋的信息。首先，PBVI-OSD根據當前信念狀態和 QMDP 函數，計算出各個動作對應為最優動作的概率，由此使用別名方法采樣一個最優的動作 a *。其次，PBVI-OSD基于信念狀態 b 與狀態轉換函數的結果進行加權，選出最可能達到的狀態作為下一個狀態，即最有可能到達的狀態 s 。最后，PBVI-OSD在保證觀察概率大于閾值的基礎上隨機選擇觀察 z ，并把由此獲得的信念狀態作為后繼信念點，從而擴充探索信念點集 B 。PBVI-OSD根據權重選取更加合理的動作、狀態，以及在探索期間選擇更加合理的觀察，使得其能夠確保效率，提升算法的質量。實驗結果表明，PBVI-OSD在大規模問題上能收斂到更好的全局最優解，同時能夠保證收斂效率和性能。

1 POMDP模型及其求解

1.1 POMDP問題

POMDP對agent在不確定性環境下的決策問題進行建模，在此模型中，agent每一步執行一個動作，其得到的結果是隨機的，且其觀察也并不完備。POMDP模型可以被描述為一個八元組 （S，A，Z，b 0，T，O，R，γ），其中：S為一個隱含狀態的有限集合，表示系統所有可能處于的狀態；A 為一個agent能采取的動作集合； Z 為一個觀察的有限集合，表示agent所有可能的輸入； b 0為初始的狀態分布，表示初始時刻t 0系統在狀態集合S上的概率分布；T（s，a，s′）=P（s t+1=s′|s t=s，a t=a）為狀態到狀態的轉移概率函數，描述 agent在 狀態s采取動作a后到達狀態s′的概率；O（s′，a，z）=P（z t+1=z|a t=a，s t+1=s′）為觀察函數，表示執行a動作于t+1時刻轉移到s′狀態后觀察到z的概率；R（s，a）為回報函數，即在狀態s中采取動作a獲得的回報（效用值）；γ∈（0，1）為折扣因子，作用是淡化長期回報，并且保證無限步數的長遠回報得以 收斂。

POMDP模型中，由于agent只能從環境中獲取觀察，且不能確定其所屬狀態。所以，它必須根據歷史動作和觀察集合 {a 0，z 1，a 1，z 2，a 2，z 3，…，a t－1，z t}決定下一個動作［11］。因而需要引入充分統計信念狀態b，用來維護歷史信息。b定義為［12］b（s）=P（s t=s|z t，a t -1，…，z 1，a 0） 。

將原始問題映射到一個信念空間，可以把POMDP問題轉換為MDP問題來求解。 因為時刻t處的信念狀態b t只需要前一步的信念狀態b t－1，最近采取的動作a t－1和得到的觀察z t來獲得，其表達式如下 ［13］：

b t（s′）=τ（b t－1，a t－1，z t）= O（s′，a t－1，z t）∑ "s∈S T（s，a t－1，s′）b t－1（s） P（z t|b t－1，a t－1）

其中： Pr（z t|b t－1，a t－1）為歸一 因子［12］，表示agent在信念 點b t-1處采取動作a t－1后觀察到z t的 概率。

P（z t|b t－1，a t－1）=∑ ""O（s′，a t－1，s）∑ "s∈S T（s，a t－1，s′）b t－1（s）

POMDP中的策略是信念空間到動作的映射： π（b）→a。給定一個策略π，π 的長遠回報計算如下：

V π（b）=E［∑ T t=t o γt－t 0R（b t，π（b t））］

對于一個給定的POMDP模型，求解的任務就變成了計算最優 策略π*，使得能最大化長遠回報的期望。通過貝爾曼方程迭代可以求得最優策略［11］。Q值函數Q t+1（b，a）定義為在信念狀態b選定動作a且保證持續優化剩余的t 視野的動作值函數。

Q t+1（b，a）=∑ "s∈S b（s）R（s，a）+γ∑ "z∈Z P（z|b，a）V* t（τ（b，a，z））

V* t+1（b）= max "a∈A "Q t+1（b，a）

對應的最優策略表示為 π* t+1（b ）=argmax "a∈AQ t+1（b，a）。雖然b在|S|－1維的連續 單空間內有無限個取值，Smallword［15］等證明對于任意的有限視野 t ，值函數為信念空間上的分段線性凸函數，表示為一個向量集合。

τ t={α 0，α 1，…，α |τ t|，V t（b）= max "α∈|τ t| b·α}

從 Γ t更新到Γ t+1，可以在整個信念空間上精確求解來獲得。然而，其更新的復雜度近似為O（|S|2|A||Z||B||Z| ），POMDP 的精確值迭代算法存在維度災和歷史災問題。盡管有些算法，如Witness［14］和增量裁剪算法［15］對精確求解的算法有所改進，但它們還是不能降低在極端場景下的算法復雜度。

1.2 基于點的值迭代

由于精確計算POMDP問題的復雜度是指數級的，且值函數向量集的向量數目增加較快，導致了精確求解難以應用于實際問題的求解［16］，所以研究人員提出了很多有效的近似求解算法。對于大部分的POMDP問題，agent所能到達的信念點集合 B 往往只是信念空間的一小部分［17］，因此可以用基于點的算法來求得其誤差在一定范圍之內的近似解，避免精確求解中計算笛卡爾積的巨大計算量，從而通過增加迭代次數保證算法效果。基于點的算法有信念子集 B 的擴張，以及實現信念點集上的值函數更新的backup操作兩個主要部分。

backup函數在點 集B上計算從Γ t到Γ t+1的復雜度近似為O（|S|2|A||Z||B|2）。雖然基于點的算法只會更新可達信念點集的向量集，但是可以保證獲得一個誤差范 圍可控的近似解。

基于點的方法在終止條件之前反復執行兩個步驟：探索新的信念點以擴張信念點 集合B；在B上更新值函數Γ。而基于點的值迭代 方法的主要差別在于不同的信念點集探索方法［18］。

1.3 前向搜索值迭代算法

前向搜索值迭代算法（FSVI）簡化了agent和環境之間的交互，基于狀態來貪婪探索信念空間，FSVI算法探索的過程如算法1所示。

算法1 FSVI exploration

輸入： b，s 。

輸出： V 。

if "s "is not a goal state then

a *←argmax "a∈AQMDP（s，a ）

sample "s ′ from "T（s，a*，* ）

sample "z "from "O（s′，a*，* ）

FSVIExploration（ bz a*，s ′）

end if

V←V ∪backup（ b，V ）

算法1中，FSVI通過使用信念狀態采 樣s，模擬在環境中的狀態，使用信念狀態b來 表示agent的當前狀態，維護這樣一個狀態—信 念狀態對（s，b）。首先基于狀態s 得到POMDP下的最優動作 a*，接著基于狀態轉移函數T（s，a，s′）隨機選取下一個狀態s′，再通過觀察函數得到隨機觀察值z，由此可根據信念狀態轉移函數得到下一個信念點b′ ，backup函數用于生成信念點集的最優向量［9］，算法持續搜索直到agent到達某一個目標狀態或其他結束條件［19］。

FSVI基于內在的MDP最優策略，選取最優動作非常的快速，只需 要探索O（|A|） 個MDP的 Q 值函數。因此，該方法極大地降低了算法的復雜度。相比其他的如PBVI等廣度優先的探索算法，FSVI通過深度優先的探索能夠獲取一個更高效的結果；相比于同為深度優先的HSVI［20］等算法，FSVI在探索過程中隨機獲取狀態和觀察，降低了計算的復雜度。

然而，FSVI過于簡化了采樣動作和狀態的過程，使得其在某些場景表現得并不是很好。主要有兩方面的缺陷：首先是選取動作的過程，其只基于MDP優化的策略選擇，而沒有考慮到全局的狀態分布情況，FSVI的方案不能保證選擇全局最佳的動作，因而使FSVI易陷入局部最優方案［21］；其次，FSVI隨機取樣狀態提升了效率，但是難以適用于稀疏狀態的POMDP問題。而實際的POMDP問題通常具有大規模的狀態，其狀態的分布也很分散［22］。

2 "基于環境狀態分布優化的POMDP值迭代求解算法

2.1 算法思想

因POMDP應用于不確定的環境，agent不能精確確定其所屬狀態，必須充分利用信念狀態 b，根據環境的反饋選擇最佳策略。因此，本文探討了在信念探索中，當前信念狀態對動作、狀態和觀察選擇的作用，提出了結合QMDP以及當前信 念狀態，通過加權期望選取動作和狀態的采樣算法。

信念狀態是表示agent在各個狀態上的概率分布。因此，在選取最優動作的過程中，可以根據信 念狀態和QMDP函數計算各個動作作為最優動作的加權概率，I表示當前動作是否為取得的最大QMDP對應的動作值。用actionPr i表示每個動作被選擇的概率值。然后根據概率分布通過別名算法加權取樣出最佳的動作a* ，如式（1）（2）所示。

actionPr i←∑ "s∈S b（s）I a i= argmax "a（QMDP（s，a））， where "I a=b= 1 a=b """0 a≠b """"""""（1）

a *←AliasMethod（ {actionPr 1，actionPr 2，…，actionPr |A|}） ""（2）

在對下一時刻的狀態進行采樣時，結合信念狀態 b和狀態轉換函數T的結果進行加權，結果用nextStatePr i表示下一個狀態可能出現的加權概率值。貪婪選出最有可能達到的狀態s ，如式（3）（4）所示。

nextStatePr i←∑ s∈S b（s）T（s，a*，s′） ""（3）

s′← max （{nextStatePr 1，nextStatePr 2，…，nextStatePr |S|}） ""（4）

當選擇觀察 z 時，PBVI-OSD設置了一個閾值 ε來 過濾那些可能性過低的觀察，獲得后繼點集successors（ b ），然后使用別名方法從這個后繼信念點集中選取下一個信念點 b ，如式（5）（6）所示。

successors （b）←{ba，z|O（s′，a*，z）gt;ε} ""（5）

b ′←AliasMethod（successors（ b ）） "（6）

2.2 PBVI-OSD算法步驟描述

PBVI-OSD形式化描述見算法2，PBVI-OSD首先由盲目策略（算法3）初始化值函數 V，值函數V是一系列向量。接著從一個初始信念點B={b 0}開 始。通過PBVIOSDExplore（算法4）方法探索信念點集并進行值迭代，直至達到目標狀態或者迭代到限定步長時，算法才會終止。

算法3的盲目策略用于初始化值函數 V 。算法4 PBVIOSD- Explore，基于信念狀態和 QMDP函數計算各個動作作為最優動作的概率，然后根據概率分布通過別名算法加權取樣出最佳的動作a*；結合信念狀態b和狀態轉換函數的結果進行加權，別名方法選出最有可能達到的狀態s；選擇觀察z時，設置閾值過濾可能性低的觀察，不斷擴充信念點集，直至某一個目標狀態或其他結束條件，算法 流程如圖1所示。

算法2 PBVI-OSD

輸入 ：POMDP 。

輸出： V 。

V ←BlindPolicy（）

B={b 0}

repeat

V ←PBVIOSDExplore （b 0，B ）

until convergence

算法3 blind policy

輸入： POMDP。

輸出： "V a（s ）。

V a（s）← "min "a，s′R a（s′） 1－γ "s，a

repeat

V a（s）←R a（s）+γ∑ s′∈s T（s，a，s′）V a（s′） s，a

until convergence

算法4 PBVIOSDExplore

輸入： b，B 。

輸出： V 。

action Pr s←{∑ "s∈S b（s）I a i =argmax "aQMDP（s）|a i∈A}

a* ←AliasMethod（ actionPr s）

NextStatePr s←{∑ "s∈S b（s）T（s，a*，s i）|s i∈S}

s′ ←max（{ nextStatePr 1，nextStatePr 2，…，nextStatePr |S|} ）

if "sgoalState "then

successors（ b）←{ba，z|O（s′，a*，z）gt;ε}

b ′←AliasMethod（successors（ b ））

B new←B∪{b′ }

PBVIOSDExplore（ b′，B new ）

end if

V←V ∪backup （b，V ）

通過求 解QMDP函數獲得狀態到最優動作選擇的映射。對某一信念狀態點b，計算最優動作的過程中，通過式（1）計算某個動作的選擇概率的時間復雜度為O（|S||A|）。式（2）使用別名方法選取最優動作的時間復雜度為O（|A|）。式（3）計算下一個狀態的分布概率的時間復雜度為O（|S|2），式（4）選取狀態的時間復雜度為O（|S|）。后繼信念點的選擇首先根據設置的閾值過濾掉概率小于閾值的觀察，式（5）選擇觀察的時 間復雜度為|S||A||Z|。同樣，式（6）的時間復雜度為O（|S|）。 因此，一次擴張過程的時間復雜度為O（|S|2|A||Z|+|S|2|A|+ O（|S|3）） 。

3 實驗及結果分析

本文在Hallway2［23］和不同規模的RockSample［19］問題上進行基準測試，在其上分別運行PBVI-OSD、FSVI和PBVI三個算法。Hallway2是一個經典的迷宮問題。RockSample模擬了agent采樣礦石的科學考察任務，它是一個可擴展的問題，agent要接觸某一區域的巖石并對巖石采樣以獲得回報，agent到達最右邊的出口也會獲得回報。RockSample規?？蓴U展，為了分析算法的性能特性，故選擇的數據集規模較大，選取的數據集包括RockSample［7，8］、RockSample［10，10］和RockSample［11，11］。各個POMDP基準測試的參數特征描述如表1所示，其中屬性| S|代表了狀態的數目，屬性|A|代表了動作的數目，屬性|Z|代表了觀察 的數目。

Hallway2是一個擁有較小規模的狀態集合、中等規模的觀察集合，以及較大規模的動作集合的數據集。RockSample有一個規模較大的狀態集合，但是它的觀察集合很小。這些數據集能夠覆蓋大部分實際應用的場景。

實驗環境為臺式工作站，內存為16 GB，CPU為Core i7-9700，基于Java語言實現。在所有的實驗中，折扣因子 γ=0.95，收斂閾值ε=0.01 。分別用FSVI、PBVI-OSD和PBVI三種算法在四個數據集上運行，其中FSVI和PBVI的實驗設計基于文獻[17]。每次update獲得一個值函數后，策略模擬運行100步計算得到折扣回報值，通過反復500次的模擬來計算平均折扣回報（average discounted reward，ADR）。當到達預設的時間或者指定的步長時，實驗將會終止。表2列出了每個算法最高的ADR，表3列出了每個算法收斂的時間。實驗表明，PBVI-OSD相對其他兩種算法而言，能較快地收斂，并在RockSample［7，8］、RockSample［10，10］、RockSample［11，11］上ADR值較高?？梢婋S著問題規模的增大，其在取得最高ADR以及收斂時間所表現出來的優勢愈發明顯。

圖2展示了PBVI-OSD、FSVI和PBVI三個算法在四個不同問題上，ADR與迭代時間的對比。表 中X軸表示算法的迭代時間，Y軸 表示ADR的值。圖中使用實線表示FSVI，圓點線表示PBVI，PBVI-OSD表示短畫線。

在Hallway2和RockSample［7，8］問題上，由于PBVI-OSD引入了基于信念狀態快速選取動作、狀態和后繼信念點，其收斂效率表現得不如FSVI，特別是在狀態較少的Hallway2問題上，PBVI-OSD的收斂速度比FSVI慢了三倍。PBVI-OSD和PBVI在Hallway2和RockSample［7，8］的問題上，收斂效率接近，PBVI-OSD的收斂效率略高于PBVI。由于狀態規模較小，FSVI和PBVI-OSD最后獲得相似的ADR值。這也表明了PBVI-OSD在處理中等規模的問題時，相比于FSVI并不占優勢。PBVI基于距離尋找全局最優解，其在狀態規模較小的Hallway2問題上取得ADR值高于FSVI和PBVI-OSD，而在RockSample［7，8］問題上的ADR值則略低于其他兩種算法，PBVI在狀態規模稍大的問題上實用性不高。

在規模較大的RockSample［10，10］和RockSample［11，11］問題中，PBVI-OSD的收斂效率明顯較高，PBVI-OSD在這兩個問題上表現出穩定性。PBVI-OSD在RockSample［10，10］問題上的收斂效率比FSVI和PBVI算法分別快1.2倍和1.73倍；在RockSample［11，11］的問題上，由于狀態數規模大，基于MDP的近似解法PBVI-OSD和FSVI在值迭代的初始化階段耗費了一段時間，初期收斂效率不如基于信念點集探索的算法PBVI。如圖2（d）所示，隨著初始化的完成，PBVI-OSD和FSVI的ADR值明顯高于PBVI，且由于有效利用了狀態分布的信息，PBVI-OSD表現更佳。PBVI-OSD收斂速度比FSVI和PBVI兩個算法分別快1.28倍和2.67倍。這說明在大規模問題上，PBVI-OSD比FSVI和PBVI能夠更快收斂，并能夠提供更加穩定的ADR提升。

綜合上述分析，PBVI-OSD根據當前信念狀態基于環境狀態分布優化的算法，選取最優動作、狀態，然后探索得到下一個信念點，從而保證了取樣的有效性。在Hallway2、RockSample［7，8］、RockSample［10，10］和RockSample［11，11］四個基準問題上的實驗表明，相比于FSVI和PBVI，PBVI-OSD能保證收斂效率，特別是在大規模問題上能收斂到更好的全局最優解。

4 結束語

本文提出了一個基于環境狀態分布優化的POMDP值迭代算法PBVI-OSD。PBVI-OSD能夠有效利用環境的反饋，基于信念狀態快速選取動作、狀態和后繼信念點，彌補了前向搜索值迭代算法僅依據MDP進行隨機采樣的缺陷，避免了無峰值狀態的問題中退化為隨機策略。一方面，PBVI-OSD根據當前信念狀態基于權重的標準選取最優動作、狀態，有效利用了環境狀態分布的信息。另一方面，PBVI-OSD基于選取出的動作和狀態，從觀察中隨機選取一個觀察概率大于閾值的觀察，由此獲得后繼信念點，從而保證了取樣的有效性。這些改進措施能夠幫助PBVI-OSD有效利用環境狀態來作出更佳的決策，而不僅僅依賴內在的MDP。實驗結果表明，PBVI-OSD在大規模的問題上能夠取得更佳的全局最優解。

通過改進前向搜索值迭代算法的不足之處，PBVI-OSD在大規模問題上取得了一定的改進，但PBVI-OSD仍然需要提升。因此，下一步工作仍會集中在探索更加有效地解決大規模狀態引起稀疏的方案，以及嘗試解決隨著迭代時間的增長，動作和狀態取樣復雜度高的問題。

參考文獻：

[1] "Delamer J A， Watanabe Y， Chanel C P C. Safe path planning for UAV urban operation under GNSS signal occlusion risk［J］. Robotics and Autonomous Systems ，2021， 142 ：103800.

［2] 萬開方，高曉光，李波，等.基于部分可觀察馬爾可夫決策過程的多被動傳感器組網協同反隱身探測任務規劃［J］.兵工學報，2015， 36 （4）：731-743.（Wan Kaifang， Gao Xiaoguang， Li Bo， "et al . Mission planning of passive networked sensors for cooperative anti-stealth detection based on POMDP［J］. Acta Armamentarii ，2015， 36 （4）：731-743.）

［3] Ebadi M， Akhavan-Tabatabaei R. Personalized cotesting policies for cervical cancer screening： a POMDP approach［J］. Mathematics ，2021， 9 （6）：679.

［4] Burks L， Ahmed N， Lo E G， "et al . Collaborative human-autonomy semantic sensing through structured POMDP planning［J］. Robotics and Autonomous Systems ，2021， 140 （11-12）：103753.

［5] Khonji M， Jasour A， Williams B. Approximability of constant-horizon constrained POMDP［C］//Proc of the 28th International Joint Confe-rence on Artificial Intelligence Main Track.2019：5583-5590.

［6] Akbarinasaji S， Kavaklioglu C， Basar A， "et al . Partially observable Markov decision process to generate policies in software defect mana-gement［J］. Journal of Systems and Software ，2020， 163 ：110518-110518.

［7] Poupart P， Kim K E， Kim D. Closing the gap： improved bounds on optimal POMDP solutions［C］//Proc of the 21st International Confe-rence on Automated Planning and Scheduling.2011.

［8] 劉全，翟建偉，章宗長.深度強化學習綜述［J］.計算機學報，2018， 41 （1）：3-29.（Liu Quan， Zhai Jianwei， Zhang Zongzhang. A survey on deep reinforcement learning［J］. Chinese Journal of Compu-ters ，2018， 41 （1）：3-29.）

［9] 劉峰，王崇駿，駱斌.一種基于最優策略概率分布的POMDP值迭代算法［J］.電子學報，2016， 44 （5）：1078-1084.（Liu Feng， Wang Chongjun， Luo Bin. A probabilitybased value iteration on optimal policy algorithm for POMDP［J］. Acta Electronica Sinica ，2016， 44 （5）：1078-1084.）

［10] Liu Feng， Hua Xia， Jin Xin. A hybrid heuristic value iteration algorithm for POMDP［C］//Proc of the 28th International Conference on Tools with Artificial Intelligence.Piscataway，NJ：IEEE Press，2016：304-310.

［11] 劉海濤，洪炳熔，樸松昊，等.不確定性環境下基于進化算法的強化學習［J］.電子學報，2006， 34 （7）：1356-1360.（Liu Haitao， Hong Bingrong， Pu Songhao， "et al . Evolutionary algorithm based reinforcement learning in the uncertain environments［J］. Acta Electronica Sinica ，2006， 34 （7）：1356-1360.）

［12] Bang-Jensen J， Gutin G， Yeo A. When the greedy algorithm fails［J］. Discrete Optimization ，2004， 1 （2）：121-127.

［13] "Jazwinski A H. Stochastic processes and filtering theory［M］//Mathema-tics in Science and Engineering.[S.l.]：Academic Press，1970：1-376.

［14] "Cassandra A R， Littman M L， Zhang N L. Incremental pruning： a simple， fast， exact method for partially observable Markov decision processes［EB/OL］.（2013-02-06）.https：//arxiv.org/abs/1302.1525.

［15] Cassandra A R， Kaelbling L P， Littman M L. Acting optimally in partially observable stochastic domains［C］//Proc of the 20th AAAI National Conference on Artificial Intelligence.Palo Alto，CA：AAAI Press，1994：1023-1028.

［16] Smallwood R D， Sondik E J. The optimal control of partially observable Markov processes over a finite horizon［J］. Operations Research ，1973， 21 （5）：1071-1088.

［17] Shani G， Pineau J， Kaplow R. A survey of point-based pomdp solvers［J］. Autonomous Agents and Multi-Agent Systems ，2013， 27 （1）：1-51.

［18] Liu Feng， Song Zebang. A probabilistic greedy search value iteration algorithm for POMDP［C］//Proc of the 28th International Conference on Tools with Artificial Intelligence.Piscataway，NJ：IEEE Press，2016：926-929.

［19] Shani G， Brafman R I， Shimony S E. Forward search value iteration for POMDPs［C］//Proc of the 20th International Joint Conference on Artificial Intelligence.2007：2619-2624.

［20] Pineau J， Gordon G， Thrun S， "et al . Point-based value iteration： an anytime algorithm for POMDPs［C］//Proc of the 18th International Joint Conference on Artificial Intelligence.2003：1025-1032.

［21] Gefner H， Bonet B. Solving large POMDPs using real time dynamic programming［C］//Proc of Working Notes Fall AAAI Symposium on POMDPs.Palo Alto，CA：AAAI Press，1998.

［22] Liu Bingbing， Kang Yu， Jiang Xiaofeng， "et al . A fast approximation method for partially observable Markov decision processes［J］. Journal of Systems Science amp; Complexity ，2018， 31 ：1423-1436.

［23] Littman M L， Sutton R S， Singh S. Predictive representations of state［C］//Proc of the 14th International Conference on Neural Information Processing Systems：Natural and Synthetic.2001：1555-1561.