策略迭代法

動態規劃中求最優策略的基本方法之一。

例如，在最短路徑問題中，設給定M個點。點M是目的點,是點i到點j的距離要求出點i到點M的最短路。記為從i到M的最短路長度。此問題的動態規劃基本方程為

(1)

其策略迭代法的程序如下：選定一初始策略,在這問題中，策略的意義是從點i出發走一步後到達的點，而且作為策略，它是集上的函數。由解下列方程組求出相應的值函數：

再由求改進的一次迭代策略,使它是下列最小值問題的解：

然後，再如前面一樣，由求出相應的值函數，並由求得改進的二次迭代策略,如此繼續下去。

可見求解(1)的策略迭代法的程序由下列兩個基本步驟組成：

①求值計算　

由策略求相應的值函數，即求下列方程的解：

②策略改進　

由值函數求改進的策略，即求下列最小值問題的解：

式中規定，如 是上一問題的解，則取

在一定條件下，由任選的初始策略出發，輪換進行這兩個步驟, 經有限步N后將得出對所有i,這樣求得的uN(i)就是最優策略，相應的值函數。是方程(1)的解。

對於更一般形式的動態規劃基本方程

(2)

這裡ƒ，H，φ為給定實函數。上述兩個步驟變成：

①求值計算　

由策略求相應的值函數 ，即求方程之解，。

②策略改進　

由值函數求改進的策略，即求最優值問題的解。

對於滿足適當條件的方程(2)和初始策略，上述兩個步驟的解存在，並且在一定條件下，當 時，所得序列與在某種意義下分別收斂於(2)的解和最優策略。

策略迭代法最初是由R.貝爾曼提出的。1960年，R.A.霍華德對於一種馬爾可夫決策過程模型，提出了適用的策略迭代法，給出了相應的收斂性證明。後來，發現策略迭代法和牛頓迭代法在一定條件下的等價性，於是，從運算元方程的牛頓逼近法的角度去研究策略迭代法，得到了發展。

對於範圍很廣的一類馬爾可夫決策過程，其動態規劃基本方程可以寫成

式中，對所有 γ為的線性運算元,Γ為這種運算元的族，而V則是由指標值函數所構造的函數空間。 則是由指標值函數所構造的函數空間。假設當 ƒ(γ)是方程

的解釋, 它是對應於策略γ的指標值函數。

最優策略 γ定義為最優值問題的解。

這是由策略迭代法所求得的序列和 滿足下列關係，其中的逆運算元。

當σ是加托可微時, 是σ在處的加托導數。於是，上面的關係恰好表達了牛頓迭代法在運算元方程中的推廣。