策略改進與策略迭代

從價值到更好的策略

假設你已經評估完一個策略，現在知道它的價值函數。你能做得更好嗎？策略改進（policy improvement）說：可以，幾乎總是可以。在每個狀態，用動作價值函數（action-value function）往前看一步——也就是採取每個動作、之後再遵循舊策略的價值——然後切換到看起來最好的那個動作。這個總是挑選最高價值動作的新策略，就是對那些價值而言的貪婪策略（greedy policy）。

\pi'(s) = \arg\max_a \sum_{s',r} p(s',r \mid s,a)\left[r + \gamma V^\pi(s')\right]

策略改进：在每个状态选择使一步前瞻价值最大的动作。

這感覺簡單到不太可信——一次只在一個狀態貪婪地切換動作，難道不會適得其反嗎？畢竟改變你在這裡的做法，會改變之後能抵達的地方？這篇的深刻結論是：它從不會適得其反。

策略改進定理

策略改進定理（policy improvement theorem）保證貪婪策略在每一個狀態都至少和原策略一樣好——在任何地方都不會更差。而且如果貪婪策略在任何地方都沒有嚴格更好，那麼這兩個策略就都已經是最佳的了。因此每一輪「先評估、再貪婪」要嘛改進策略，要嘛證明你已經完成。

q_\pi\bigl(s,\pi'(s)\bigr) \ge v_\pi(s) \quad\Longrightarrow\quad v_{\pi'}(s) \ge v_\pi(s)\ \ \forall s

策略改进定理：若贪心动作在每个状态都不更差，则新策略处处优于旧策略。

策略迭代：評估—改進迴圈

策略迭代（policy iteration）就只是交替執行這兩個步驟，直到策略不再變化。因為確定性策略的數量有限，而每一輪都嚴格改進（否則停止），所以它會在有限次迭代內抵達最佳策略（optimal policy）——而且次數往往出乎意料地少。

初始化一個任意策略。
策略評估：計算當前策略的價值函數（第 2 篇的掃描）。
策略改進：把新策略設為對該價值函數貪婪。
若策略沒有改變，停止——它是最佳的。否則回到步驟 2。

\pi_0 \xrightarrow{\;E\;} v_{\pi_0} \xrightarrow{\;I\;} \pi_1 \xrightarrow{\;E\;} v_{\pi_1} \xrightarrow{\;I\;} \cdots \xrightarrow{\;I\;} \pi_* \xrightarrow{\;E\;} v_*

策略迭代：交替进行评估（E）与改进（I），策略与价值一同攀升至最优的 (π*, v*)。

廣義策略迭代

這裡是一個比 DP 本身更長壽的統合觀念。你不需要在改進之前把策略完全評估好。廣義策略迭代（generalized policy iteration, GPI）是任意評估過程與任意改進過程彼此拉扯的鬆散之舞——做幾次評估掃描、做一次部分的貪婪更新，以任何粒度反覆進行。只要兩者都持續朝一致性推進，這對組合就會收斂到最佳價值函數與最佳策略。