馬爾科夫過程

在機率論和統計學中，馬爾可夫決策過程提供了一個數學架構模型，用于面對部分随機、部分可由決策者控制的狀态下，如何進行決策，以俄羅斯數學家安德雷·馬爾可夫的名字命名。

0.引例 

假設我們有一個機器人處于狀态 s1s1， 它有多種動作選擇可以到達終止狀态 stst， 但是執行每個動作所帶來的收益不一樣。這時，我們需要做一個算法來幫助機器人選擇動作序列，來保證到達終止狀态 stst 時收益最高，這時就需要馬爾可夫決策過程了。 

⋆⋆ ⋆⋆ ⋆⋆ a3a3 表示執行該動作，有一定機率到達 s1s1, 也有一定機率到達 s2s2. 可參考機器人軌迹規劃中的不确定性，即将推出。。。

1.馬爾可夫性質 

馬爾可夫性質是機率論中的一個概念。當一個随機過程在給定現在狀态以及過去所有狀态的情況下，其未來狀态的條件機率分布僅依賴于目前的狀态；換句話說，在給定現在狀态時，它與過去狀态（即該過程的曆史路徑）是條件獨立的，那麼此随機過程即具有馬爾可夫性質。具有馬爾可夫性質的過程通常稱之為馬爾可夫過程。 

數學上，如果 X(t),t>0X(t),t>0 為一個随機過程，則馬爾可夫性質就是指 

Pr[X(t+h)=y|X(S)=x(s),s≤t]=Pr[X(t+h)=y|X(t)=x(t)],∀h>0.   (1)Pr[X(t+h)=y|X(S)=x(s),s≤t]=Pr[X(t+h)=y|X(t)=x(t)],∀h>0.   (1)

其中，x(t)x(t)表示目前的狀态值，x(s)x(s)表示曆史狀态值。 

馬爾可夫過程通常是（時間）齊次的，如果滿足： 

Pr[X(t+h)=y|X(t)=x(t)]=Pr[X(h)=y|X(0)=x(0)],∀t,h>0.   (2)Pr[X(t+h)=y|X(t)=x(t)]=Pr[X(h)=y|X(0)=x(0)],∀t,h>0.   (2)

除此之外則被稱為是（時間）非齊次的。齊次馬爾可夫過程通常比非齊次的簡單，構成了最重要的一類馬爾可夫過程。 

某些情況下，明顯的非馬爾可夫過程也可以通過擴充“現在”和“未來”狀态的概念來構造一個馬爾可夫表示。設 XX 為一個非馬爾可夫過程。定義一個新的過程 YY，使得每一個 YY 的狀态表示 XX 的一個時間區間上的狀态，用數學方法來表示，即，

Y(t)={X(s):s∈[a(t),b(t)]}.   (3)Y(t)={X(s):s∈[a(t),b(t)]}.   (3)

如果 YY 具有馬爾可夫性質，則它就是 XX 的一個馬爾可夫表示。 在這個情況下， XX 也可以被稱為是二階馬爾可夫過程。更高階馬爾可夫過程也可類似地來定義。

2.馬爾可夫過程的定義 

馬爾可夫過程可以用一個五元數(S,A,P(⋅,⋅),R(⋅,⋅),γ)(S,A,P(⋅,⋅),R(⋅,⋅),γ) 來描述，其中 

∙∙ SS 是一組有限的狀态集(a finite set of states)； 

∙∙ AA 是一組有限的動作集(a finite set of actions or AsAs is the finite set of actions available from state ss) 

∙∙ Pa(s,s′)=Pr(st+1=s′|st=s,at=a)Pa(s,s′)=Pr(st+1=s′|st=s,at=a) 表示在時間 tt 狀态 ss 采取動作 aa 可以在時間 t+1t+1 轉換到狀态 s′s′ 的機率 

∙∙ Ra(s,s′)Ra(s,s′) 表示通過動作 aa 狀态從 ss 轉換到 s′s′ 所帶來的及時收益（或者是預期及時收益） 

∙∙ γ∈[0,1]γ∈[0,1] 是折扣因子(discount factor)，表示未來收益和目前收益之前的差别，就是各個時間的收益所占的比重不同 

⋆⋆ 馬爾可夫決策過程并不要求 SS 或者 AA 是有限的，但基礎的算法中假設它們由有限的

3.馬爾科夫過程的描述 

MDP的關鍵問題在于尋找一個政策：在狀态 ss 選擇動作 π(s)π(s)， 組成一個動作函數 ππ. 我們的目的在于選擇一個動作函數 ππ 可以最大化累積收益 R(T)R(T)：

R(T)=∑t=1TγtRat(st,st+1)   (4)R(T)=∑t=1TγtRat(st,st+1)   (4)

s.t.   at=π(st),0≤γ<1s.t.   at=π(st),0≤γ<1

. 我們分三種情況來讨論： 

∙ T=1,∙ T=1, greedy case.greedy case. 這時算法是退化的，拿我們的例子而言，機器人隻會考慮下一步動作帶來的影響，而不會考慮之後一系列動作帶來的影響。但是這個算法卻在實際應用中起着重要作用，是很多機器人問題的最優解。因為它計算起來非常簡單。它的缺點也很明顯，容易陷入局部最優。很明顯，此時 γγ 的取值不影響結果，隻要滿足 γ>1γ>1 即可。 

∙ 1<T<∞,∙ 1<T<∞, finite−horizon case.finite−horizon case. 此時，一般會取 γ=1γ=1. 意思是說每個狀态轉換的收益權重是一樣的。有人會說這種 finite-horizon 的處理方式是最符合實際情況的。但事實上，這種 finite-horizon的情況處理起來比下邊提到的infinite-horizon更加複雜。因為我們要求的動作序列是時間的函數。也就是說，即便是從相同的狀态開始計算，由于時間參數 TT 不同，最後得到的最優動作序列會不同。課本裡的原話是， Near the far end of the time horizon, for example, the optimal policy might differ substantially from the optimal choice earlier in time, even under otherwise identical conditions (e.g., same state, same belief). As a result, planning algorithms with finite horizon are forced to maintain different plans for different horizons, which can add undesired complexity. 

∙ T=∞,∙ T=∞, infinite−horizon case.infinite−horizon case. 這種情況不會有上邊所提到的計算複雜度增加的問題，因為 TT 是無窮大的。在這種情況下， γγ的取值很重要，因為它需要保證計算結果是收斂的。假設 RatRat 是有界的，|Rat|≤rmax.|Rat|≤rmax. 那麼我們可以得到

R∞≤rmax+γrmax+γ2rmax+...=rmax1−γ   (5)R∞≤rmax+γrmax+γ2rmax+...=rmax1−γ   (5)

4.馬爾可夫過程的算法求解 

假設我們已知狀态轉移矩陣 PP 和收益函數RR, 我們需要最大化累積收益值。 

我們需要存儲兩個變量（都是狀态變量 ss 的函數），ππ 用來表示動作序列， VV 用來表示累計收益值。整個算法由兩步組成：

π(s):=arg maxa{∑s′Pa(s,s′)(Ra(s,s′)+γV(s′)},π(s):=arg maxa{∑s′Pa(s,s′)(Ra(s,s′)+γV(s′)},

V(s):=∑s′Pπ(s)(s,s′)(Rπ(s)(s,s′)+γV(s′)).   (6)V(s):=∑s′Pπ(s)(s,s′)(Rπ(s)(s,s′)+γV(s′)).   (6)

算法的求解以遞歸的形式進行。當整個計算過程中把所有狀态全包含時，則表示疊代完成。

5.變種算法–值疊代 

在求解過程中，我們可以把 π(s)π(s) 的計算整合到 V(s)V(s) 的計算中，得到

Vi+1(s):=maxa{∑s′Pa(s,s′)(Ra(s,s′)+γVi(s′))}   (7)Vi+1(s):=maxa{∑s′Pa(s,s′)(Ra(s,s′)+γVi(s′))}   (7)

其中，ii 是疊代次數。疊代過程從 i=0i=0 開始， V0V0 為指定的初始值，重複計算 Vi+1Vi+1 一直到收斂為止。

6.reference 

https://en.wikipedia.org/wiki/Markov_decision_process 

https://en.wikipedia.org/wiki/Markov_property 

Probabilistic Robotics.