2.3 最優策略及其性質

前一節我們為策略定義了價值函數。價值函數實際上給出了策略的一個偏序關系：對于兩個策略π和π'，如果對于任意s∈，都v_π(s)≤v_π'(s)，則稱策略π小于等于π'，記作π≤π'。本節將基于這個偏序關系來定義最優策略，并考慮最優策略的性質和求解。

2.3.1 最優策略與最優價值函數

·對于一個動力而言，總是存在著一個策略π_*，使得所有的策略都小于等于這個策略。這時，策略π_*就稱為最優策略（optimal policy）。最優策略的價值函數稱為最優價值函數。最優價值函數包括以下兩種形式。

·最優狀態價值函數（optimal state value function），即

·最優動作價值函數（optimal action value function），即

對于一個動力，可能存在多個最優策略。事實上，這些最優策略總是有相同的價值函數。所以，對于同時存在多個最優策略的情況，任取一個最優策略來考察不失一般性。其中一種選取方法是選擇這樣的確定性策略：

其中，如果有多個動作a使得q*(s,a)取得最大值，則任選一個動作即可。從這個角度看，只要求得了最優價值函數，就可以直接得到一個最優策略。所以，求解最優價值函數是一個值得關注的重要問題。

2.3.2 Bellman最優方程

最優價值函數具有一個重要的性質——Bellman最優方程（Bellman optimal equation）。Bellman最優方程可以用于求解最優價值函數。

回顧2.2節，策略的價值函數滿足Bellman期望方程，最優價值函數也是如此。與此同時，將最優函數的性質：

代入Bellman期望方程，就可以得到Bellman最優方程。

Bellman最優方程有以下兩個部分。

·用最優動作價值函數表示最優狀態價值函數，備份圖見圖2-4a：

·用最優狀態價值函數表示最優動作價值函數，備份圖見圖2-4b：

圖2-4 最優狀態價值函數和最優動作價值函數互相表示的備份圖

基于最優狀態價值函數和最優動作價值函數互相表示的形式，可以進一步導出以下兩種形式。

·用最優狀態價值函數表示最優狀態價值函數，備份圖見圖2-5a：

·用最優動作價值函數表示最優動作價值函數，備份圖見圖2-5b：

圖2-5 最優狀態價值函數和最優動作價值函數自我表示的備份圖

例如，對于表2-1的動力系統，我們可以列出其Bellman最優方程為：

v_π(餓)=max{q_π(餓,不吃),q_π(餓,吃)}

v_π(飽)=max{q_π(飽,不吃),q_π(飽,吃)}

q_π(餓,不吃)=1·(-2+γv_π(餓))+0

q_π(餓,吃)=(1-α)(-3+γv_π(餓))+α(+1+γv_π(飽))

q_π(飽,不吃)=β(-2+γv_π(餓))+(1-β)(+2+γv_π(飽))

q_π(飽,吃)=0+1·(+1+γv_π(飽))

用這個方程可以求得最優價值函數。

接下來我們用sympy求解這個方程。Bellman最優方程含有max()運算，可以通過分類討論來化解這個max()運算，將優化問題轉為普通線性規劃問題。如果用這種方法，可以將這個方程組分為以下4類情況討論，用代碼清單2-2求解。

代碼清單2-2 求解示例Bellman最優方程

from IPython.display import display
import sympy
from sympy import symbols
sympy.init_printing()
alpha, beta, gamma = symbols('alpha beta gamma')
v_hungry, v_full = symbols('v_hungry v_full')
q_hungry_eat, q_hungry_none, q_full_eat, q_full_none = \
        symbols('q_hungry_eat q_hungry_none q_full_eat q_full_none')
xy_tuples = ((1, 1), (1, 0), (0, 1), (0, 0))
for x, y in xy_tuples: # 分類討論
    system = sympy.Matrix((
            (1, 0, x-1, -x, 0, 0, 0),
            (0, 1, 0, 0, -y, y-1, 0),
            (-gamma, 0, 1, 0, 0, 0, 1),
            ((alpha-1)*gamma, -alpha*gamma, 0, 1, 0, 0, 2*alpha-3),
            (-beta*gamma, (beta-1)*gamma, 0, 0, 1, 0, -5*beta+3),
            (-2*gamma,  0, 0, 0, 0, 1, 2) ))
    result = sympy.solve_linear_system(system,
            v_hungry, v_full,
            q_hungry_eat, q_hungry_none, q_full_eat, q_full_none)
    print('==== x = {}, y = {} ===='.format(x, y))
    display(result)
    print('q_hungry_eat - q_hungry_none =')
    display(sympy.simplify(result[q_hungry_eat] - result[q_hungry_none]))
    print('q_full_eat - q_full_none =')
    display(sympy.simplify(result[q_full_eat] - result[q_full_none]))

代碼清單2-2求得以下4種情況的解如下。

情況I：q*(餓,不吃)≥q*(餓,吃)且q*(飽,不吃)≥q*(飽,吃)。這時v*(餓)=q*(餓,不吃)且v*(飽)=q*(飽,不吃)。這種情況的求解結果為：

其中△_I=2αγ²-αγ+γ+1。此時，q_*(餓,不吃)≥q_*(餓,吃)且q_*(飽,不吃)≥q_*(飽,吃)可以化簡為：

(αγ-2α-4γ+4)(2αγ²-αγ+γ-1)≥0

(6αβγ²-3αβγ-3αγ+8βγ²-5β-8γ²+7γ+1)(2αγ²-αγ+γ-1)≥0

情況II：q_*(餓,不吃)≥q_*(餓,吃)且q_*(飽,不吃)<q_*(飽,吃)。這時v_*(餓)=q_*(餓,不吃)且v_*(飽)=q_*(飽,吃)。這種情況的求解結果為：

其中△_II=αγ²-αγ+βγ²-βγ-γ²+2γ-1。此時，q_*(餓,不吃)≥q_*(餓,吃)且q_π(飽,不吃)<q_π(飽,吃)可以化簡為：

-3αβγ+2α-4βγ+4γ-4≥0

6αβγ²-3αβγ-3αγ+8βγ²+4βγ+5β-8γ²+3γ-1>0

情況III：q_π(餓,不吃)<q_π(餓,吃)且q_π(飽,不吃)≥q_π(飽,吃)。這時v_π(餓)=q_π(餓,吃)且v_*(飽)=q_*(飽,不吃)。這種情況的求解結果為：

此時，q_*(餓,不吃)<q_*(餓,吃)且q_*(飽,不吃)≥q_*(飽,吃)可以化簡為：

αγ-2α-4γ+4>0

4βγ-5β-γ+1≤0

情況IV:q_*(餓,不吃)<q_*(餓,吃)且q_*(飽,不吃)<q_*(飽,吃)。這時v_*(餓)=q_*(餓,吃)且v_*(飽)=q_*(飽,吃)。這種情況的求解結果為：

其中△_IV=βγ²-βγ-γ²+2γ-1。此時，q_*(餓,不吃)<q_*(餓,吃)且q_*(飽,不吃)<q_*(飽,吃)可以化簡為：

-3αβγ+2α-4βγ+4γ-4<0

4βγ-5β-γ+1>0

對于給定數值的情況，更常將松弛為v_*(s)≥q_*(s,a)（s∈,a∈(s)），并消去q_*(s,a)以減少決策變量，得到新的線性規劃：

其中c(s)（s∈）是一組任意取值的正實數。Bellman最優方程的解顯然在線性規劃的可行域內。而由于c(s)>0（s∈），因此線性規劃的最優解肯定會讓約束條件中的某些不等式取到等號，使得Bellman最優方程成立。可以證明，這個線性規劃的最優解滿足Bellman最優方程。

例如，在之前的例子中，如果限定，我們用這個線性規劃求得最優狀態價值為

進而由最優狀態價值推算出最優動作價值為

2.3.3 用Bellman最優方程求解最優策略

在理論上，通過求解Bellman最優方程，就可以找到最優價值函數。一旦找到最優價值函數，就能很輕易地找到一個最優策略：對于每個狀態s∈，總是選擇讓q_*(s,a)最大的動作a。

例如，對于表2-1的動力系統，我們已經通過分類討論求得了Bellman最優方程。那么它的最優策略也可以通過分類討論立即得到：

情況I：q_*(餓,不吃)≥q_*(餓,吃)且q_*(飽,不吃)≥q_*(飽,吃)，即(αγ-2α-4γ+4)(2αγ²-αγ+γ-1)≥0且(6αβγ²-3αβγ-3αγ+8βγ²-5β-8γ²+7γ+1)(2αγ²-αγ+γ-1)≥0。這種情況的最優策略是

π_*(餓)=不吃,π(飽)=不吃

即一直不吃。

情況II：q_*(餓,不吃)≥q_*(餓,吃)且q_*(飽,不吃)<q_*(飽,吃)，即-3αβγ+2α-4βγ+4γ-4≥0且6αβγ²-3αβγ-3αγ+8βγ²+4βγ+5β-8γ²+3γ-1>0。這種情況的最優策略是π_*(餓)=不吃,π(飽)=吃

即餓了不吃，飽時吃。

情況II：q_*(餓,不吃)<q_*(餓,吃)且q_*(飽,不吃)≥q_*(飽,吃)，即αγ-2α-4γ+4>0且4βγ-5β-γ+1≤0。這種情況的最優策略是

π_*(餓)=吃,π(飽)=不吃

即餓了吃，飽時不吃。

情況IV：q_π(餓,不吃)<q_π(餓,吃)且q_π(飽,不吃)<q_π(飽,吃)，即-3αβγ+2α-4βγ+4γ-4<0且4βγ-5β-γ+1>0。這種情況的最優策略是

π_*(餓)=吃,π(飽)=吃

即一直吃。

對于一個特定的數值，求解則更加明顯。例如，當，2.3.2節已經求得了最優動作價值，此時最優動作價值滿足q_π(餓,不吃)<q_π(餓,吃)且q_π(飽,不吃)<q_π(飽,吃)。所以，它對應的最優策略為

π(吃|餓)=π(吃|飽)=1

π(不吃|餓)=π(不吃|飽)=0

但是，實際使用Bellman最優方程求解最優策略可能會遇到下列困難。

·難以列出Bellman最優方程。列出Bellman最優方程要求對動力系統完全了解，并且動力系統必須可以用有Markov性的Mar kov決策過程來建模。在實際問題中，環境往往十分復雜，很難非常周全地用概率模型完全建模。

·難以求解Bellman最優方程。在實際問題中，狀態空間往往非常巨大，狀態空間和動作空間的組合更是巨大。這種情況下，沒有足夠的計算資源來求解Bellman最優方程。所以這時候會考慮采用間接的方法求解最優價值函數的值，甚至是近似值。