水樹藻

[拼音]：celüe diedaifa

[英文]：policy iteration method

動態規劃中求最優策略的基本方法之一。它藉助於動態規劃基本方程，交替使用“求值計算”和“策略改進”兩個步驟，求出逐次改進的、最終達到或收斂於最優策略的策略序列。

例如，在最短路徑問題中，設給定M個點1，2，…，M。點M是目的點，сij>0是點i到點j的距離i≠j，сij=0，i，j=1，2，…，M，要求出點i到點M的最短路。記ƒ(i)為從i到M的最短路長度。此問題的動態規劃基本方程為

(1)

其策略迭代法的程式如下：選定一初始策略u0(i)，在這問題中，策略u(i)的意義是從點i出發走一步後到達的點，而且作為策略，它是集{1，2，…，M-1}上的函式。由u0(i)解下列方程組求出相應的值函式ƒ0(i)：

再由ƒ0(i)求改進的一次迭代策略u1(i)，使它是下列最小值問題的解：

然後，再如前面一樣，由u1(i)求出相應的值函式ƒ1(i)，並由ƒ1(i)求得改進的二次迭代策略u2(i)，如此繼續下去。 可見求解(1)的策略迭代法的程式由下列兩個基本步驟組成：

（1）求值計算由策略 un(i)求相應的值函式ƒn(i)，即求下列方程的解：

（2）策略改進由值函式ƒn(i)求改進的策略，即求下列最小值問題的解：

式中規定，如un(i)是上一問題的解，則取un+1(i)=un(i)。

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

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

(2)

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

（1）求值計算由策略un(x)求相應的值函式 ƒn(x)，即求方程

之解，n=0，1，2…。

（2）策略改進由值函式ƒn(x)求改進的策略un+1(x)，即求最優值問題

的解。

對於滿足適當條件的方程(2)和初始策略，上述兩個步驟的解存在，並且在一定條件下，當n→

時，所得序列{ƒn(x)}與{un(x)}在某種意義下分別收斂於(2)的解和最優策略。

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

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

；式中ƒ∈V，對所有 γ∈Γ:r(γ)∈V，γ為 V→V的線性運算元，Γ為這種運算元的族，而V 則是由指標值函式所構造的函式空間。假設

當 ƒ(γ)是方程 r(γ)＋γƒ＝0 的解時， 它是對應於策略γ的指標值函式。最優策略 γ

定義為最優值問題

的解。這時由策略迭代法所求得的序列 {ƒn}和{γn}滿足下列關係

其中

為 γn+1的逆運算元。當σ是加託可微時， γn+1是σ在ƒn處的加託導數。於是，上面的關係恰好表達了牛頓迭代法在運算元方程中的推廣。