預測狀態表示綜述

摘 要:預測狀態表示是描述離散時間有限狀態的動態系統的新方法。使用動作—觀測值序列的預測向量表示系統狀態在將來時刻發生的概率，能解決現有動態系統決策過程中計算復雜的問題。綜述了預測狀態表示的基本原理，介紹了預測狀態表示的建模過程和規劃算法，對已有的建模方法和規劃方法進行總結分析和比較，指出了該研究領域的發展方向，最后提出了研究面臨的挑戰。

關鍵詞:動態系統; 預測狀態表示; 發現核心測試; 學習模型參數; 規劃算法

中圖分類號:TP18

文獻標志碼:A

文章編號:1001-3695(2010)02-0401-04

doi:10.3969/j.issn.1001-3695.2010.02.001

Survey of predictive state representations

LEI Zhu， LIU Feng， ZHAO Zhi-hong

(School of Software Engineering， Nanjing University， Nanjing 210093， China)

Abstract:Predictive state representations(PSRs) are new models for discrete-time finite action and observation stochastic systems. Because a PSR represents the system’s state as a set of predictions of the observable outcomes of tests performed in the system， it can solve the computing problems in exist stochastic decision systems. This paper introduced the principles of PSR models， surveyed the PSR model and planning techniques， analyzed and compared the fundamental principles behind the modeling and planning algorithms of PSR， pointed out the development trend， and gave the challenges that the research of PSR was facing.

Key words:stochastic systems; predictive state representations(PSR); discovery core-test; learning parameters; planning

預測狀態表示(PSR)[1，2]是表示離散時間有限狀態的動態系統中狀態的新方法。在離散時間有限狀態的動態系統中，執行一系列的動作，就會產生對應的觀測值。把已發生的動作—觀測值序列稱為歷史(history)，將要發生的動作—觀測值序列稱為測試(test)。PSR從所有的測試中尋找一組能表示系統狀態的核心測試(core-test)，并通過學習求得用核心測試來表示系統狀態的模型參數，這樣動態系統所有的狀態都可以通過核心測試和模型參數來表示。PSR通過實用核心測試和模型參數來表示系統的狀態概率分布。

PSR作為POMDP的替代模型由Littman等人提出[1]，并被Singh擴展到離散時間有限狀態的動態系統中[2]。與現有的動態系統模型相比，基于歷史的K階馬爾可夫鏈模型記錄過去發生的事情，基于隱含狀態的部分可觀測馬爾可夫決策模型(POMDP)和隱馬爾可夫模型(HMM)記錄系統狀態的概率分布，而PSR通過預測表示系統的狀態在將來時刻發生的概率。PSR不需要假設系統中存在隱含狀態，只用觀測值的概率分布來表示系統狀態，避免了求解POMDP中隱含狀態帶來的維數災難的問題，使得問題更容易求解。

PSR預測向量的每個分量都與某些測試相關，這組測試組成核心測試集。這樣構造PSR模型涉及到兩個問題:尋找核心測試和學習核心測試的參數。迄今為止，有多種解決方案，包括基于斜率的方法、重置方法、差分學習方法、約束的梯度下降方法等，將這些方法應用在POMDP實驗中，取得了比較理想的效果。有學者應用PSR來選擇動作，稱為規劃問題。例如，增量剪枝算法和Q-學習算法，其重點是構造和計算系統的獎賞值。另外，很多學者對PSR進行了擴展，如與memory結合使用，將PSR應用于大規模系統中和將PSR拓展到連續空間等。本文將介紹上述PSR相關方法并進行比較。

1 基本原理

考慮離散時間有限狀態的動態系統。定義動作集合a∈A，觀測值集合o∈O，從當前時間到第k步的時間序列t1，t2，…，tk，從起始時間到第k步的時間序列t1，t2，…，tk。系統可表示為動作—觀測值序列a1o1a2o2…，產生的動作—觀測值序列標記為歷史h=a1o1a2o2…anon，未來k時間步的動作觀測值序列標記為測試t=a1o1…akok。在歷史h下產生測試t的概率p(t|h)為

p(t|h)=p(oj+1=o1，…，oj+k=ok|h，aj+1=a1，…，aj+k=ak)

1.1 動態系統矩陣

給出一組測試序列T={t1，t2，…，tn}，在條件歷史h下，T發生的概率為一個行向量:

p(T|h)=p[p(t1|h)p(t2|h)…p(tn|h)]

給出一組歷史序列H={h1，h2，…，hn}T，測試t發生的概率為一個列向量:

p(t|H)=[p(t|h1)p(t|h2)…p(t|hn)]T

因此給定一組測試序列和一組歷史序列，可定義一個動態系統矩陣D=p(T|H)，其中Dij=p(tj|hi)=p(hitj)/p(hi)。如表1所示。該矩陣滿足如下性質:

a)i，o≤p(ti|hj)≤1;

b)t，a∈A，p(t)=∑o∈Op(o1，…，ok，o|a1，…，ak，a);

c)令T(a)為動作序列a產生的所有測試序列，則k，a∈Ak，∑t∈T(a)p(t)=1。

動態系統矩陣并非系統的建模，而是系統本身的一種表示方式，該矩陣的秩反映了動態系統的線性維度。

表1 動態系統矩陣

Dt1t2…ti…

φhp(t1|φh)p(t2|φh)…p(ti|φh)=p(Q|φh)mti…

h1p(t1|h1)p(t2|h1)…p(ti|h1)=p(Q|h1)mti…



hjp(t1|hj)p(t2|hj)…p(ti|hj)=p(Q|hj)mti…



1.2 預測狀態表示

對秩為K的矩陣D，存在K階線性無關的列向量。把一組K階線性無關的列向量組成向量集Q={q1，q2，…，qk}，稱該向量集為核心測試。把矩陣D中包含該列向量的子矩陣記為D(Q)，PSR模型中的核心狀態的概率為

p(Q|h)=[p(q1|h)，p(q2|h)，…，p(qk|h)]

矩陣D的第一行初始化為p(Q|φ)，φ為空歷史;p(Q|h)構成動態系統的狀態統計分布。定義參數函數f，使得p(t|h)=ft(p(Q|h))。因矩陣的所有列是Q的線性組合，對所有的測試t，存在一個長度為K的權值向量mt，能用D(t)=ft(D(t))=D(Q)mt重新構建D(t)。因此對所有的歷史h，有p(t|h)=p(Q|h)Tmt。于是得到狀態的更新表達式:

p(qt|hao)=p(aoqt|h)p(ao|h)=p(Q|h)Tmaoqtp(Q|h)Tmao

所以，該線性PSR的模型參數就是{maoq}和{mao}。如果把向量參數{maoq}和{mao}表示成非線性參數函數fq和fao，就可以定義非線性PSR。更新表達式改為

p(qt|hao)=faoqt(p(Q|h))fao(p(Q|h))

2 建模技術

用PSR模型描述真實世界，需要處理兩個子問題，即尋找核心測試以及學習模型參數。目前提出了多種解決方案，包括基于斜率的方法、重置方法、差分學習方法和約束的梯度下降方法等。若不作說明，以下方法都針對線性PSR而言。

一般來講，尋找核心測試的基本過程如下:

Q←search(ε，{})

search(t，s)

fora∈A，o∈O

如果aot與S線性相關

那么S←search(aot，S∪{aot})

返回S

Q初始為空，先在長度為1的測試集中找出線性無關的測試放入Q中，然后對Q中的測試進行進一步擴展，再找出線性無關的測試放入Q中，繼續拓展，直至無法選出線性無關的測試。

2.1 基于斜率的方法

Singh等人[3]最先提出了基于斜率的方法(gradient-based method)，該方法只處理學習問題，它假設核心測試已知，使用給定的策略選擇動作。每個測試都有權重向量mX，這樣mX就構成了模型參數。算法將參數m和向量p的預測值分別記為m^和p^。算法本身為一參數估算誤差函數，定義為

error(t)=∑x∈X[p(x|ht-1)-p^(x|ht-1)]2

該方法采用多步預測來定義誤差，使用梯度下降方法來推導學習過程，其中Xt是t時刻的所有拓展測試組成的集合。因梯度下降規則的計算相當復雜，采用一種近似的方法來學習。令Et表示t時刻所有拓展測試組成的集合，學習策略表示為

x∈Et，m^x←m^x+at1wπx，t[χx，t-p^Ttmx]p^t，

xEt，m^x←m^x

其中:p^t=p^(Q|ht-1)是t時刻的狀態估算向量;αt是步長參數;wπx，t是測試x在t時刻的取樣權重值。該樣本學習算法對執行過拓展測試的參數進行更新，對未被執行的測試則不更新。

基于斜率的方法效率比較高，每個時間步只需要O(|Q|2)的計算量。Singh等人用此方法在POMDP系統中進行實驗取得了成功。該方法忽略了輸入p^t本身變化的影響，使用近似的方法來代替原來的誤差函數，計算出的參數容易偏離實際情況。由于引進了步長參數，每次變更步長的時候都需要重新計算。

2.2 重置方法

James和Singh[4]在2004年提出了第一個能同時解決尋找問題和學習問題的重置方法(reset)。該方法需要系統具有重置功能使其恢復到初始狀態，通過多次重置，可搜集到多個測試序列，相當于做伯努利實驗。該方法分為兩部分:ADL算法(analysis discovery and learning algorithm)和DL算法(discovery and learning algorithm)。在ADL里假設對任何測試t和歷史h能精確計算p(t|h)，然后通過迭代法求得矩陣的秩，進而找出系統的核心測試。算法從第一維子矩陣開始迭代，逐漸擴大維數，兩次迭代中矩陣的秩不變則算法結束，求出此時的核心測試和核心歷史以及模型參數。DL算法去掉ADL中的假設，根據重置操作產生的數據估算p(t|h)。DL算法可以在系統重置后采取動作序列a1a2…ak，根據得到的觀察結果o1o2…ok，對包含在該動作—觀察值序列中的所有鄰近的歷史—觀察值對更新p(t|h)。DL算法的迭代過程與ADL算法相同，算法設置了一些措施來防止在估算過程中可能出現的問題。最后得到的系統參數為

m^ao=p^-1(Q^T|Q^H)p(ao|Q^H)，m^aot=p^-1(Q^T|Q^H)p(aot|Q^H)

重置方法通過伯努利實驗產生的結果來估算矩陣的秩和核心測試，得到近似的PSR模型。它要求系統具有重置功能，而實際中擁有重置功能的系統并不多，具有一定的局限性。

2.3 差分學習方法

Wolfe等人[5]提出了差分學習方法(temporal difference learning，TD)，其作為傳統的強化學習算法，被廣泛地使用。該方法是在線學習方法，假定核心測試是給定的，使用一步TD算法來估算預測錯誤并更新預測值。其基本思想是用未來時間步的估算值來估計當前值。例如對p(t|h)和t=a1o1a2o2a3o3，在觀察到h(設步長為k)之后，開始預測p(t|h)的估算值p^(t|h)。如果系統在時刻k+1執行動作a1，此時將系統反饋的觀測值ok+1與o1相比，然后得出延遲一步的(t|h):

(t|h)=p(a2o2a3o3|ha1o1)ok+1=o1

0ok+1≠o1

當ok+1=o1時，就可以計算出p(t|h)的值:

p(t|h)=E[(t|h)]=p(a1o1|h)p(a2o2a3o3|ha1o1)

該方法中的TD誤差為(t|h)-p^(t|h)。Wolfe將TD算法用于POMDP系統中，效果比較差。

2.4 約束的梯度下降方法

McCracken等人[6]提出約束的梯度下降方法(constrained gradient-ascent method)，該方法能在線學習，能解決尋找問題和學習問題，先假設核心測試已知，最后再求核心測試。

為能精確估算p(T|H)，McCracken對T和H作了限制。T包含Q和X并滿足兩個性質:a)如果tao∈T，則t∈T;

b)如果taoi∈T，則taoj∈T，oj∈O。H的維度大小被限制為N，記錄最近的N長度的歷史。

矩陣p(T|H)構造過程如下:每觀察到一對新的aioi，就估算并增加新的一行p(T|hi);矩陣的第一行初始化為某一平均值p(T|h0)。每加入一行分為兩個步驟:a)估算行。計算aioit∈T時的預測值p(t|hi)=p(aioit|hi-1)/p(aioi|hi-1)，然后計算aioitT時的p(t|hi)，并對所有的值進行規范化處理，這樣整行的值都被估算。b)梯度下降。所有在未來幾步觀察到的測試tao的預測值為

p(tao|hi)=(1-α)p(tao|hi)+αp(t|hi)

其中，0≤α≤1為學習率，在學習過程中逐漸減小。

p(T|H)構造完畢后，就可尋找核心測試和學習模型參數。模型參數的求解與重置方法類似，模型參數為

m^ao=p^-1(Q^T|Q^H)p(ao|Q^H)

m^aot=p^-1(Q^T|Q^H)p(aot|Q^H)

其中需要用到矩陣的逆運算，對不滿秩的矩陣可填充一些較小的正數使其滿秩。McCracken采用參數閾值法尋找核心測試，該參數是矩陣的條件數。設定一閾值，核心測試集初始化為空，如果一個測試的條件數低于該閾值，則被添加為核心測試，該過程一直重復到沒有測試超過閾值被添加到矩陣中為止。

將該方法運用于POMDP系統中，取得了良好的運行結果。該算法能在線學習，數據量越多預測值越準確。該方法中閾值的選擇直接影響到方法的準確性，若長期運行，可能會收斂到局部最優。

2.5 各種方法比較

求解PSR建模中的尋找問題和學習問題的方法本質上都是盡可能精確地求解預測值p(t|h)，再從動態系統矩陣p(T|H)中尋找核心測試和學習模型參數。基于斜率的方法和差分學習方法在假設核心測試已知的情況下求解模型參數，而重置方法和約束的梯度下降方法能同時解決兩個問題。基于斜率的方法是第一個在假設核心測試已知的情況下求解模型參數的方法，它求解較短核心測試的模型參數表現良好，但針對較長的核心測試而言性能將顯著下降。重置方法需要系統通過多次重置操作來提高p(T|H)的精確度，而實際中擁有重置功能的系統并不多，屬于理論研究模型。差分學習方法不要求系統具有重置功能，理論上可以應用到所有的動態系統中，但由于缺乏對具體環境的特定限制和優化，使得算法運算的效率和準確性并不高，求出的模型結果不太理想，可以考慮將單步TD方法擴展到多步TD方法，或者與函數估計結合使用。約束的梯度下降方法在求解p(t|h)時對T和H作了限制，計算p(T|H)的過程中也使用了數據填充和規范化處理等手段，保證計算出來的p(T|H)貼近真實的值，能在線學習，因此數據量越多預測值越準確，但其可能會收斂到局部最優是其不足之處，對歷史長度的限制也使它的應用規模受到約束。

3 規劃算法

PSR模型通過尋找核心測試和學習模型參數來描述真實的動態系統，因此可以通過PSR規劃算法來確定最優的動作序列，該動作序列即為動態系統的最優策略，可以為動態系統進行隨機決策提供重要依據。

用r表示觀測值o的獎賞，測試t的表達形式改為t=a1(r1o1)…ak(rkok)，歷史h的表達形式改為h=a1(r1o1)…ak(rkok)。用ht表示歷史h中的測試t，對動作a，觀察結果(r，o)發生的概率為pT(Q|ht)ma，(r，o)。ht中的動作a的瞬間獎賞為

R(ht，a)=∑r∈Rrp(r|ht，a)=

∑r∈RrPT(Q|ht)∑o∈Oma，(r，o)=PT(Q|ht)na

其中:na為一個(n×1)獎賞參數向量(a∈A)，它是模型參數向量的線性組合。對給定的一個動作，期望的瞬間獎賞是一個關于預測向量的線性函數。

通過規劃算法可以計算出ht中動作a的獎賞值，進而可以衡量采取一系列動作之后的獎賞值，求出獎賞值最大的動作序列就是該系統的最優策略。目前的規劃算法主要有增量剪枝規劃算法和Q-學習規劃算法等。

3.1 增量剪枝規劃算法

James等人[7]提出了增量剪枝算法PSR-IP(PSR-incremental pruning)[7]。PSR-IP需要使用策略樹，在PSR中，策略樹被定義成一個關于PSR預測向量的線性相關的函數，能夠計算所有的PSR預測向量的期望獎賞。給定一個初始動作為a的策略樹ρ和針對所有觀察o的策略樹ρo，在歷史h條件下策略樹ρ的期望獎賞為Vρ(h)=p(Q|h)T(na+γ∑o∈OMa，owρo)。

因wρ=(na+γ∑o∈OMa，owρo)是(n×1)向量，所以Vρ(h)是一個關于p(Q|h)的線性函數。該方法還針對預測向量p提出了一些約束，它們必須滿足有效的動態系統行為的有關概率理論的等式。使用這些約束條件就能使得增量剪枝算法更有效地運行，使用這些針對動態向量的約束是PSR的值迭代算法的核心。

3.2 Q-學習規劃算法

James等人[7]還提出通過使用預測向量作為狀態表示的Q-學習算法。預測向量連續分布于多維度空間，需采用CMACs[8]作為動作的近似函數。CMACs是基于網格的方法，將若干個互相重疊的網格覆蓋整個空間，每個網格將空間分為大小相等的部分。預測向量p和動作a的動作值是所有網格上該預測向量動作值的和:Q(p，a)=∑gvg，a(ig(p))。其中:ig(p)表示p是否在第g個網格上，vg，a(i)是在其上的值。

Q-學習算法過程如下:給出當前的預測向量p、動作a、獎賞r和下一個預測向量p′，令δ=r+γmax a′Q(p′，a′)-Q(p，a)，每個g中的更新表達式為vg，a(ig(p))=vg，a(ig(p))+αδ。其中，α定義為學習速率。此表達式是在線更新的， 使用ε-貪婪策略[9]選擇動作。該算法的執行就是使用PSR預測向量作為狀態表示的Q-學習方法的直接應用。實驗結果表明PSR中的Q-學習算法可以使得策略的選擇達到或者近似地達到最優。

3.3 規劃算法比較

增量剪枝算法屬于值迭代算法，其算法的效果依賴于限定的約束條件，是它的一個局限性。Q-學習方法需要對所有的預測向量p中的動作a進行值運算，計算復雜度比增量剪枝算法要高。文獻[7]中的實驗結果表明這兩個算法的性能相似，實驗結果都比較理想。

4 其他研究方向

許多學者拓展了PSRs模型，由于各自關注的模型特點不同，研究的重點也有所側重。有學者通過使用memory中的觀測值來提高模型的效率;有學者提出了非線性PSRs模型，可降低模型復雜度;有學者對動態系統矩陣進行了改進，提出了近似PSRs模型，可應用到較大規模的系統中;有學者根據PSR建模的思想將PSRs模型拓展到了延續空間，使PSR更方便地遷移到實際問題的求解上來。

1)與memory結合

為了能利用memory中的觀測值，James等人[10]提出了memory-PSRs(mPSRs)。Memory中包含能夠體現當前系統惟一性的觀測值，稱為landmarks。當mPSR從樣本數據中學習到模型之后，可識別出landmarks，并用它重新表示模型，這樣能更加準確地描述系統的狀態。實驗數據表明，與只包含預測狀態的PSR相比具有更好的效率，因mPSRs用歷史數據重新表達模型，具有K階馬爾可夫模型的優點。

2)非線性PSRs

Rudary等人[11]提出了非線性PSRs，它可以把系統的復雜度進行壓縮。他們指出必然存在一組測試Q={q1，q2，…，qc}，可用非線性組合預測測試的條件概率p(t|h)=ft(p(Q|H))，ft是非線性函數。算法引入了新的概念e-tests(end-tests)，e=a1a2…akok，即一連串的動作加上一個觀測值。非線性PSR的更新式為

p(ei|hao)=p(aoei|h)/p(ao|h)=p(aei|h)=p(QV|h)mae

其中:QV為非線性PSRs的動態矩陣。尋找核心測試的過程與線性PSRs相似。Singh證明了動態系統存在非線性維度，并且比線性維度指數級的小。

3)將PSRs拓展到較大規模系統

Wolfe等人[12]于2008年提出近似PSRs模型，該模型在一定的誤差限制下用近似的預測向量表示觀測結果，能把PSR拓展到較復雜的系統中。該方法定義了一套表示符號，M為真實模型，M^為近似模型，p為真實概率，p^為近似概率，為處理后的符合規范的近似概率。在t時刻，近似過程如下:設M^為atot的近似模型，t-1時刻p在經過模型M^后得到(Q|ht)，由于p^(Q|ht)不滿足需求的格式，需轉換成(Q|ht)，即對近似狀態σ^t和t，需要滿足D(σt‖)-D(σt‖σ^≤ε)，ε為允許的錯誤率。經該處理后，建模過程如下，定義一組函數{gi:1≤i≤n}使得對應此觀測值向量的第i維有

h，t:p(t|h)∏ni=1p(gi(t)|h)

通過維護預測值p(gi(t)|h)就可以計算出預測狀態p(Q|h)。該算法的優點在于事先對數據進行了預處理，使其符合需要的PSR預測值的格式，避免了直接計算核心測試矩陣Q。

4)將PSRs拓展到連續空間

Wingate等人[13]將PSRs模型拓展到連續空間上，其動作和觀測值是連續的，并且定義了系統動態分布，設置了連續PSRs的五大要素:歷史和測試、連續的系統動態向量、系統動態分布、充分統計和狀態。通過該五大要素，可以使用信息理論來定義一個足夠隨機的狀態，并從數據集中學習到近似的系統動態分布，然后使用信息理論的工具來設計算法求解核心測試和學習模型參數。

5 結束語

對動態系統的建模和隨機決策的研究是人工智能領域的一個重要分支，根據描述動態系統及所處的環境和目標求解最優策略一直是研究的難點所在。PSR模型作為描述動態系統的新方法，避免了隱含狀態模型所帶來的計算復雜度呈指數增長的問題，更加形象地描述了系統的核心狀態和概率分布，通過對每個測試中的動作獎賞值的計算也更容易求解系統的最優動作序列。目前PSR面臨兩大問題，即動態系統矩陣求解和大規模離散系統及連續系統的建模問題。對于求解問題，可以在求解矩陣時設置一些約束條件和進行數據預處理工作，盡量使求得的概率值接近真實值;對于建模問題，在許多應用領域中，需要修正PSR模型，提出新的解決方案使其符合實際問題的求解。以上兩種問題的解決是PSR未來研究的主要方向。

參考文獻:

[1]LITTMAN M， SUTTON R， SINGH S. Predictive representations of state[C]//Proc of the Advances in Neural Information Processing Systems. Cambridge:MIT Press， 2002:1555-1561.

[2]SINGH S， JAMES M， RUDARY M. Predictive state representations:a new theory for modeling dynamical systems[C]//Proc of the 20th Annual Conference on Uncertainty in Artificial Intelligence. 2004:512-519.

[3]SINGH S， LITTMAN M， JONG N. Learning predictive state representations[C]//Proc of the 20th International Conference on Machine learning. 2003:712-719.

[4]JAMES M， SINGH S. Learning and discovery of predictive state representations in dynamical systems with reset[C]//Proc of the 21st International Conference on Machine Learning. 2004:53-60.

[5]WOLFE B， JAMES M， SINGH S. Learning predictive state representations in dynamical systems without reset[C]//Proc of ACM International Conference Proceeding Series. New York:ACM Press， 2005:985-992.

[6]McCRACKEN P， BOWLING M. Online discovery and learning of predictive state representations[C]//Proc of the Advances in Neural Information Processing Systems. 2006:875-882.

[7]JAMES M， SINGH S， LITTMAN M. Planning with predictive state representations[C]//Proc of International Conference on Machine Learning and Applications. 2004:304-311.

[8]ALBUS J S. A theory of cerebellar function[J]. Mathematical Biosciences，1971， 10(1-2):25-61.

[9]SUTTON R， BARTO A. Reinforcement Learning: an introduction[M]. Cambridge:MIT Press， 1998.

[10]JAMES M， WOLFE B， SINGH S. Combining the memory and landmarks with predictive state representations[C]//Proc of the 19th International Joint Conference on Artificial Intelligence. 2005:734-739.

[11]RUDARY M， SINGH S. A non-linear predictive state representation[C]//Proc of the Advances in Neural Information Processing Systems. 2003:791-798.

[12]WOLFE B， JAMES M， SINGH S. Approximate predictive state representations[C]//Proc of the 7th International Conference on Autonomous Agents and Multiagent Systems. 2008:363-370.

[13]WINGATE D， SINGH S. On discovery and learning of models with predictive representations of state for agents with continuous actions and observations[C]//Proc of International Conference on Autonomous Agents. 2007.