動態規劃尋找最優策略之policy evaluation(策略估計)

05-03

一、總括

首先給出本講的關鍵，動態規劃求解最優策略。指的是在了解整個MDP的基礎上求解最優策略，也就是清楚模型結構的基礎上：包括狀態行為空間、轉換矩陣、獎勵等。動態是個非常實用的思想，也很博大精深，這裡不詳細討論這個。直接給出在MDP中的應用。

具體的數學描述是這樣：

For prediction 預測：給定一個MDP $<S, A, P, R, gamma>$ 和策略 $pi$ ，或者給定一個MRP $<S, P^{pi}, R^{pi}, gamma>$ ，要求輸出基於當前策略π的價值函數 $V_{pi}$ 。

For control 控制：給定一個MDP $<S, A, P, R, gamma>$ ，要求確定最優價值函數 $V_{*}$ 和最優策略 $pi_{*}$

本周最關鍵的內容為：

本次總結Policy Evaluation的知識點

Policy Evaluation策略評估的問題就是說給定一個MDP和一個策略 $pi$ ，我們來評價這個策略有多好？

如何來判斷這個策略有多好呢？根據基於當前策略 $pi$ 的價值函數 $V_{pi}$ 來決定，所以我們的關鍵就是給定一個MDP和一個策略 $pi$ ,如何求出價值函數 $V_{pi}$ ？不要怕，馬上告訴你如何求解？

問題形式化定義如下：

問題：評估一個給定的策略π，

解決方案：反向迭代應用Bellman期望方程

具體方法：同步反向迭代，即在每次迭代過程中，對於第 $k+1$ 次迭代，所有的狀態s的價值用v_k(s) 計算並更新該狀態第 $k+1$ 次迭代中使用的價值 $v_{k}(S)$ ，其中s』是s的後繼狀態。

此種方法通過反覆迭代最終將收斂至 $V_{pi}$ 。收斂性在後面會進行證明~

完整slides如下：

其中迭代更新的公式如下：

解釋如下：

在一次迭代過程中，狀態s的價值等於前一次迭代該狀態的即時獎勵與所有s的下一個可能狀態s 的價值與其概率乘積的和，如圖所示：

還是跟之前一樣，矩陣形式如下：

狀態空間S：如圖。S1 - S14非終止狀態，ST終止狀態，灰色方格所示兩個位置；

行為空間A：{n, e, s, w} 對於任何非終止狀態可以有東南西北移動四個行為；

轉移概率P：任何試圖離開方格世界的動作其位置將不會發生改變，其餘條件下將100%地轉移到動作指向的狀態；

即時獎勵R：任何在非終止狀態間的轉移得到的即時獎勵均為-1，進入終止狀態即時獎勵為0；

折扣因子γ：1；

當前策略π：Agent採用隨機行動策略，在任何一個非終止狀態下有相等的概率採取任一移動方向這個行為，即π(n|?) = π(e|?) = π(s|?) = π(w|?) = 1/4。

完整slides如下：

在上面這個例子中，等價於下面形式化：

問題：評估在這個方格世界裡給定的策略。

該問題等同於：求解該方格世界在給定策略下的（狀態）價值函數，也就是求解在給定策略下，該方格世界裡每一個狀態的價值，也就是我們求出每一個非終止狀態的價值即可。

採取迭代法求解

下圖來自於葉強童鞋的文章圖示，非常贊：

葉強：《強化學習》第三講動態規劃尋找最優策略?

zhuanlan.zhihu.com

迭代過程如下：

這裡要注意的一點就是，比如在算k=2時候的迭代，-1.7狀態的價值的計算的時候，該狀態的下一狀態的價值應該看k=1時刻的價值函數，-1,-1,-1,而不是看k=2時刻的-1.7,-2.0,-2.0，下圖箭頭所示：

狀態價值在第153次迭代後收斂（葉強童鞋的實驗結果），於是迭代後的每個狀態的價值就是我們對該策略的評估，如下：

本講講了對策略的評估問題，下一講總結Policy Iteration問題。

參考：

David Silver深度強化學習課程第3課 - 動態規劃?

v.youku.com葉強：《強化學習》第三講動態規劃尋找最優策略?

zhuanlan.zhihu.com
推薦閱讀：