2.1.2 貪心策略和最優(yōu)策略

根據(jù)回溯圖可以看到，從一個初始狀態(tài)s出發(fā)，采取一定的策略可以以一定的概率到達一個新的狀態(tài)s′，并且獲得對應(yīng)的獎勵r。在強化學(xué)習(xí)的問題中，初始狀態(tài)和最終到達的狀態(tài)都不是智能體所能控制的，智能體能夠控制的只有這里的策略π。為了能夠評估策略的好壞，可以按照策略獲得獎勵的期望對策略的效果進行評估，也就是定義一個策略的函數(shù)（或者準確一點，可以稱為泛函，因為策略本身也是一個函數(shù)），這個函數(shù)通過給定一個策略和對應(yīng)的決策環(huán)境，可以告訴我們這個策略能夠獲取多少預(yù)期的獎勵。我們可以粗略地用式（2.4）來對這個函數(shù)進行描述，也就是求在策略π下的獎勵r的期望。雖然這個公式看起來比較簡單，但是這個公式蘊含的一個信息很重要：強化學(xué)習(xí)的最終的目的是為了找到一個策略，讓這個策略對應(yīng)獎勵的期望最大，如式（2.5）所示，這里用π?來表示找到的最優(yōu)策略。

為了得到這個最優(yōu)策略，需要根據(jù)一定的方法確定策略間的排序關(guān)系。因為狀態(tài)價值函數(shù)反映了智能體在某一狀態(tài)下未來可能獲取的獎勵的期望，所以假如有兩個策略π₁和π₂，且π₁≥π₂，可以得到對于任意狀態(tài)s，有。有了這種策略排序關(guān)系，可以定義一個最優(yōu)策略π?，也就是對于任意其他的策略π，在任意狀態(tài)s的情況下，均有。在這種情況下，由于對應(yīng)的價值函數(shù)永遠是最大的，可以簡單選擇使價值函數(shù)最大的狀態(tài)s′，作為智能體決策的下一步，其對應(yīng)的狀態(tài)價值函數(shù)和狀態(tài)-動作價值函數(shù)被分別稱為最優(yōu)狀態(tài)價值函數(shù)和最優(yōu)狀態(tài)-動作價值函數(shù)。這種最簡單的策略被稱為貪心（Greedy）策略，在這種策略下，最優(yōu)狀態(tài)價值函數(shù)V?和最優(yōu)狀態(tài)-動作價值函數(shù)Q?如式（2.6）和式（2.7）所示（默認使用右上角的星號來代表對應(yīng)函數(shù)使用了貪心策略）。

簡單解釋一下式（2.6）和式（2.7）。首先對于式（2.6）來說，為了能夠得到最優(yōu)的策略，需要找到一個最優(yōu)的動作a_t，使得式（2.1）中的期望最大，也就是式（2.6）中第一個等號右邊的內(nèi)容，希望在最優(yōu)策略下采取某個動作得到的回報最大。將這個公式對應(yīng)的期望的內(nèi)容展開，結(jié)合式（2.3）的定義（其中策略部分對所有可能的動作求和在當前的最優(yōu)策略下變?yōu)橹豢紤]最優(yōu)的動作），就能得到式（2.6）中第二個等式的結(jié)果。對于式（2.7），第一個等號跟前面的敘述類似，這里不再贅述，而第二個等號之所以成立，是因為我們已經(jīng)把所有的動作從最優(yōu)狀態(tài)價值函數(shù)V?分離開來，形成了最優(yōu)狀態(tài)-動作價值函數(shù)Q?，這個函數(shù)的變量是t時刻不同的狀態(tài)s_t和動作a_t，因此函數(shù)在公式中只需要考慮下一步的動作a_t+1，并且取這個動作讓狀態(tài)-動作價值函數(shù)Q?取得最大值。

由于式（2.6）的和式（2.7）的出發(fā)點不同，對應(yīng)的回溯圖的結(jié)構(gòu)也不相同，圖2.2對應(yīng)地描述了這兩種不同的回溯圖。在式（2.6）的情況下，由于出發(fā)點是狀態(tài)s，所以整體的圖結(jié)構(gòu)和圖2.1類似，只不過對應(yīng)的策略選擇的原則是使后續(xù)的狀態(tài)函數(shù)相關(guān)的期望取得最大。同樣，在式（2.7）的狀態(tài)下，由于最優(yōu)狀態(tài)-動作價值函數(shù)和當前狀態(tài)下采取的動作相關(guān)，所以從當前的動作出發(fā)，可以看到需要選擇下一步的動作，使當前的狀態(tài)-動作價值函數(shù)的值最大。

圖2.2 最優(yōu)狀態(tài)價值函數(shù)的回溯圖（左）和最優(yōu)狀態(tài)-動作價值函數(shù)的回溯圖（右）