值迭代與貝爾曼算子

壓縮迴圈

策略迭代在每次改進之前都把評估跑到收斂。但如果每次都只做一次評估掃描就改進呢？把它推到極限——把貪婪步驟直接折進回溯裡——你就得到 值迭代（value iteration）：一個同時進行評估與改進的單一更新。每次回溯不再對當前策略的動作取平均，而是對動作取最大值。

# Value iteration
V = {s: 0.0 for s in S}
repeat:
    delta = 0
    for s in S:
        v_old = V[s]
        # max over actions, not expectation over a fixed policy
        V[s] = max(
            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
# recover the optimal policy by acting greedily wrt V
pi_star = {s: argmax_a(...) for s in S}

貝爾曼最佳性方程

那個取最大值的回溯，正是把 貝爾曼最佳性方程（Bellman optimality equation）變成一個更新。它陳述了 最佳價值函數（optimal value function）必須滿足的自洽條件：一個狀態的價值，等於最佳動作的獎勵，加上該動作所通往之處的折扣後最佳價值。值迭代就是把這條方程式當作賦值來用，一遍又一遍。

貝爾曼最優方程化作一次更新：每個狀態取最優動作的期望獎勵加上折扣後的後繼狀態價值。

把貝爾曼算子當作一個映射

要理解它為何收斂，請別再盯著個別狀態，而是把整個價值函數看成一個大向量。這樣 貝爾曼回溯算子（Bellman backup operator）就是一個函數：吃進一個價值函數向量，吐出一個更新後的向量。值迭代不過就是把這個算子反覆套用到一個起始向量上。

把它表述成算子，就解鎖了一塊強大的數學：不動點理論。最佳價值函數正是這個算子的 不動點（fixed point）——也就是算子映射到自身的那個唯一向量。值迭代的收斂於是變成一個問題：反覆套用算子，是否會把任意起點推向那個不動點？

收縮：它為何必然收斂

這裡是拱心石。貝爾曼算子在最大範數（max-norm）下是一個 gamma-收縮（gamma-contraction）：把它套用到任意兩個價值向量上，兩者之間的最大差距至少縮小為原本的 gamma 倍（gamma 小於 1）。兩個估計只會越來越靠近，絕不會越離越遠。

最大範數下的壓縮性質：一次貝爾曼回溯使任意兩個價值向量之間的最大差距至少縮小到原來的 gamma 倍。

根據 Banach 不動點定理（收縮映射原理），一個收縮恰有唯一一個不動點，且從任何地方迭代它都會以幾何速度收斂到該點。因此值迭代不論初始猜測為何，都收斂到那個唯一的最佳價值函數，而每次掃描後的誤差都會被乘上 gamma。gamma 接近 1 意味著緩慢、需要耐心的收斂；較小的 gamma 則收斂快，但目標也更短視。