值迭代与策略迭代

值迭代和策略迭代

1. 值迭代

值迭代的过程就是：先随便给每个状态一个初始价值，然后不断用 Bellman 最优方程对价值函数做整体更新：在每轮迭代中，对每个状态 $s$，枚举所有动作 $a$，用当前价值函数计算它们的期望回报

$$\sum_{s'} P(s' \mid s,a)\big[R(s,a,s') + \gamma V(s')\big],$$

取最大的作为新的 $V(s)$。这样反复迭代，直到所有状态的价值更新幅度都足够小（收敛），得到近似的最优价值函数 $V^\ast$，最后再用这个 $V^\ast$ 对每个状态选取使上述期望回报最大的动作，得到最优策略。

总结： 初始给定一个 $V_0(s)$ ，一般设置为0，然后根据$V_0(s)$ 计算出$V_1(s)$ ，比较$V_0(s)$ 和$V_1(s)$ 是否小于一个阈值，直到$V(s)$ 收敛。

输入：
    S      : 状态集合
    A      : 动作集合
    P      : 转移概率 P(s' | s, a)
    R      : 奖励函数 R(s, a, s')
    γ      : 折扣因子（0 < γ < 1）
    θ      : 收敛阈值（如 1e-6）
---------------------------------------------
# 1. 初始化价值函数
---------------------------------------------
选择任意初始价值函数 V_0，例如：
对每个状态 s ∈ S:
    V_0(s) ← 0            # 或任意初始值
令 k ← 0

---------------------------------------------
# 2. 值迭代：用 Bellman 最优方程迭代更新 V
---------------------------------------------
重复：                        # 外层：一轮轮迭代（k = 0,1,2,...）
    Δ ← 0                    # 本轮的最大变化量 Δ_k

    对每个状态 s ∈ S:       # 用 V_k 计算 V_{k+1}(s)
        # 计算状态 s 下，每个动作 a 的 Q_k(s, a)
        对每个动作 a ∈ A:
            Q_k(s, a) ← Σ_{s' ∈ S} P(s' | s, a) × [ R(s, a, s') + γ × V_k(s') ]

        # 根据 Bellman 最优方程更新 V_{k+1}(s)
        V_{k+1}(s) ← max_{a ∈ A} Q_k(s, a)

        # 该状态在本轮中的变化量
        δ_k(s) ← | V_{k+1}(s) − V_k(s) |

        # 本轮里的“全局最大变化量”
        Δ ← max( Δ, δ_k(s) )

    若 Δ < θ:                # 若本轮对所有状态的变化都很小
        跳出循环             # 认为 V_k 已经收敛（V_k ≈ V*）
    否则：
        k ← k + 1            # 进入下一轮：概念上 V_k ← V_{k+1}
        
---------------------------------------------
# 3. 根据收敛后的 V 提取最优策略 π*
---------------------------------------------
此时令 V(s) = V_k(s) 为最终收敛的价值函数近似

对每个状态 s ∈ S:
    # 在当前 V 下，对所有动作计算一次 Q(s, a)
    对每个动作 a ∈ A:
        Q(s, a) ← Σ_{s' ∈ S} P(s' | s, a) × [ R(s, a, s') + γ × V(s') ]

    # 在该状态下选择 Q 最大的动作作为最优动作
    π*(s) ← argmax_{a ∈ A} Q(s, a)
    
---------------------------------------------
输出：
    V   : 收敛后的价值函数（V ≈ V*）
    π*  : 最优策略（确定性策略：每个 s 选一个最优动作）
---------------------------------------------

2. 策略迭代

策略迭代的过程是：先随便初始化一个策略，然后在“策略评估”和“策略改进”两步之间反复交替。具体来说，在策略评估阶段，固定当前策略 $\pi$ 不变，反复利用 Bellman 方程

$$V^\pi(s) = \sum_{s'} P(s' \mid s,\pi(s))\big[R(s,\pi(s),s') + \gamma V^\pi(s')\big]$$

迭代更新每个状态的价值，直到 $V^\pi$ 收敛；接着在策略改进阶段，利用得到的 $V^\pi$，对于每个状态 $s$，在所有动作 $a$ 中选择使

$$\sum_{s'} P(s' \mid s,a)\big[R(s,a,s') + \gamma V^\pi(s')\big]$$

最大的动作作为新的策略动作，从而得到一个改进后的策略。不断重复“评估当前策略 → 用评估结果改进策略”这一过程，直到某一轮改进中策略不再发生变化，此时得到的就是最优策略。

总结： 初始一个策略 $\pi_0$ 和一个状态值 $V_0(s)$ ，首先固定 $\pi_0$ 更新 $V_1(s)$ 直至收敛（策略评估），然后根据 $V_1(s)$ 更新 $\pi_1$ （策略改进），然后判断 $\pi_0$ 和 $\pi_1$ 是否相等，如果不相等，继续循环，使用 $\pi_1$ 更新 $V_2(s)$ …

输入：
    S      : 状态集合
    A      : 动作集合
    P      : 转移概率 P(s' | s, a)
    R      : 奖励函数 R(s, a, s')
    γ      : 折扣因子（0 < γ < 1）
    θ      : 策略评估阶段的收敛阈值（如 1e-6）

------------------------------------------------
# 1. 初始化
------------------------------------------------
初始化策略 π：                             
    例如：对每个状态 s ∈ S，随机选一个动作 a ∈ A 作为 π(s)

初始化价值函数：
    对每个状态 s ∈ S:
        V(s) ← 0                          # 或任意初值

------------------------------------------------
# 2. 外层循环：策略迭代 = 策略评估 + 策略改进
------------------------------------------------
重复：                                      # 外层循环开始（策略迭代）

    ----------------------------------------
    # 2.1 策略评估（Policy Evaluation）
    #     在当前策略 π 下求 V^π
    ----------------------------------------
    重复：                                  # 内层循环：只更新 V，不改 π
        Δ ← 0

        对每个状态 s ∈ S:
            v_old ← V(s)
            a ← π(s)                        # 当前策略在状态 s 选择的动作

            # Bellman 方程：在固定策略 π 下更新 V
            V(s) ← Σ_{s' ∈ S} P(s' | s, a) * [ R(s, a, s') + γ * V(s') ]

            Δ ← max( Δ, |v_old - V(s)| )

    直到 Δ < θ                              # 内层循环终止条件：V 已收敛到 V^π

    ----------------------------------------
    # 2.2 策略改进（Policy Improvement）
    #     用 V^π 在每个状态选更好的动作，生成新策略
    ----------------------------------------
    policy_stable ← True                    # 标记：这一轮策略是否完全没变

    对每个状态 s ∈ S:
        old_action ← π(s)

        # 计算当前价值函数 V 下，所有动作的 Q 值
        对每个动作 a ∈ A:
            Q(s, a) ← Σ_{s' ∈ S} P(s' | s, a) * [ R(s, a, s') + γ * V(s') ]

        # 选 Q 最大的动作，作为新策略在 s 下的动作
        π(s) ← argmax_{a ∈ A} Q(s, a)

        若 old_action ≠ π(s):              # 如果这个状态的动作发生了变化
            policy_stable ← False           # 说明策略还在改进

    ----------------------------------------
    # 2.3 外层循环终止条件
    ----------------------------------------
    若 policy_stable 为 True:              # 整个一轮中，所有状态的动作都没变
        跳出外层循环                        # 策略已经收敛到 π*，算法结束

直到结束                                     # 实际退出点就是上面的 “跳出外层循环”

输出：
    π  : 当前策略（此时为最优策略 π*）
    V  : 当前价值函数（此时为 V^{π*}）