策略評估：這個策略有多好？

問題本身

策略評估（policy evaluation）只回答一件事：對一個固定的策略而言，它的狀態價值函數（state-value function）是什麼——也就是若你永遠遵循該策略，從每個狀態出發所能獲得的期望折扣回報？這是預測問題。我們並不是在問這個策略在某種絕對意義上好不好；我們是在計算那個精確的數值，告訴你在此策略之下，每個起始狀態值多少總獎勵。

貝爾曼期望方程（Bellman expectation equation）說：一個狀態的價值，等於期望即時獎勵，加上折扣因子 gamma 乘以下一個狀態的期望價值。這等於是每個狀態一條方程式——一個龐大的線性方程組。你可以用線性代數直接解它，但除了寥寥幾個狀態的情形之外，這並不實際。因此我們改用迭代。

v_\pi(s)=\sum_a \pi(a\mid s)\sum_{s',r} p(s',r\mid s,a)\,\bigl[r+\gamma\,v_\pi(s')\bigr]

贝尔曼期望方程：在策略 π 下，一个状态的价值等于期望即时奖励加上下一状态的折扣价值。

迭代式策略評估

迭代式策略評估（iterative policy evaluation）從任意猜測開始（常用全零），反覆對該策略套用貝爾曼回溯。每掃過所有狀態一次，就是一次掃描（sweep）。關鍵在於自舉：每個新的價值都建立在鄰近狀態的當前估計值上，而不是建立在真實回報上。一開始估計是錯的，但每一次掃描都會縮小誤差。

# Iterative policy evaluation for a fixed policy pi
# Inputs: states S, policy pi(a|s), model p(s', r | s, a), discount gamma
V = {s: 0.0 for s in S}            # initial guess
repeat:
    delta = 0
    for s in S:
        v_old = V[s]
        # full backup: expectation over actions and next states
        V[s] = sum(
            pi(a, s) * sum(
                p(s_next, r, s, a) * (r + gamma * V[s_next])
                for (s_next, r) in transitions(s, a)
            )
            for a in actions(s)
        )
        delta = max(delta, abs(v_old - V[s]))
until delta < theta            # stop when no value moves much
return V                       # approx v_pi

每個狀態一次回溯，反覆執行直到價值不再明顯變動（theta 是一個很小的容忍度）。

原地更新還是雙陣列？

執行掃描有兩種做法。教科書上的「同步」版本保留兩份價值陣列——從舊的讀、寫入新的——使得一次掃描中的每個狀態都從同一份快照更新。原地更新（in-place）版本則邊走邊覆寫同一個陣列，因此掃描中較晚的狀態已經看得到剛更新好的較早狀態。原地更新只用一半的記憶體，而且通常收斂更快，因為好的資訊在單次掃描內就傳播開了，不必等到下一次掃描。

何時停止

理論上，價值只有在無限多次掃描的極限下才收斂到真實的價值函數。實務上，你會在一整次掃描中任一狀態的最大變動量降到某個小門檻以下時停止。值得注意的是，不論你從哪裡開始，這個迭代都保證收斂到唯一一個答案——這個事實源自我們將在第 4 篇遇到的收縮性質。

\Delta=\max_{s}\,\bigl|v_{k+1}(s)-v_k(s)\bigr|<\theta

当任一状态的最大价值变化降到很小的容差 θ 以下时停止扫描。