强化学习（Reinforcement Learning, RL）是一种机器学习范式，其核心思想是智能体（Agent）通过与环境（Environment）的交互来学习最优行为策略，以最大化长期累积奖励（cumulative reward）。与监督学习（依赖标注数据）和无监督学习（发现数据结构）不同，强化学习依赖于试错（trial-and-error）和延迟奖励信号。

🔹 定义：
形式化地，强化学习建模为一个马尔可夫决策过程（MDP），由五元组 ⟨S, A, P, R, γ⟩ 构成：

• S：状态集合（state space）
• A：动作集合（action space）
• P(s′|s,a)：状态转移概率（dynamics model）
• R(s,a,s′) 或 R(s,a)：奖励函数（reward function）
• γ ∈ [0,1)：折扣因子（discount factor），用于权衡当前与未来收益

智能体的目标是寻找一个策略 π(a|s)（从状态到动作的概率映射），使得期望回报（expected return）最大化：
  J(π) = 𝔼_π[∑_{t=0}^∞ γ^t R_t]

🔹 策略评估（Policy Evaluation）：
给定固定策略 π，计算其对应的状态值函数 V^π(s) 或动作值函数 Q^π(s,a)，即在该策略下从状态 s（或状态-动作对）开始的期望累积折扣奖励。
常用方法包括：

• 动态规划：迭代策略评估（Iterative Policy Evaluation）
• 蒙特卡洛方法：基于完整回合（episode）的采样平均
• 时序差分（TD）学习：如 TD(0)，单步自举（bootstrapping），更新公式：
    V(s_t) ← V(s_t) + α [R_{t+1} + γ V(s_{t+1}) − V(s_t)]

🔹 策略优化（Policy Optimization）：
目标是改进策略以提升性能。分为两类主流路径：

1. 基于值的方法（Value-based）：先学习最优值函数（如 Q*(s,a)），再导出贪心策略 π*(a|s) = argmax_a Q*(s,a)。代表算法：Q-learning、Deep Q-Network（DQN）。
2. 基于策略的方法（Policy-based）：直接参数化策略 π_θ(a|s)，通过梯度上升优化目标函数 J(θ) = 𝔼_{s∼d^π, a∼π_θ}[Q^π(s,a)]。代表算法：REINFORCE、Actor-Critic（如 A2C、PPO）。
3. Actor-Critic 混合方法：同时学习策略（Actor）和值函数（Critic），兼顾偏差与方差，提升训练稳定性。

# 简化版 TD(0) 策略评估伪代码（tabular case）
def policy_evaluation(pi, env, gamma=0.9, theta=1e-4, max_iter=1000):
    V = {s: 0.0 for s in env.states}
    for _ in range(max_iter):
        delta = 0
        for s in env.states:
            v_old = V[s]
            # 对策略π采样动作（或求期望）
            V[s] = sum(pi[a|s] * (env.R(s,a) + gamma * sum(P(s'|s,a)*V[s'] for s' in env.states)) 
                       for a in env.actions)
            delta = max(delta, abs(v_old - V[s]))
        if delta < theta:
            break
    return V

策略迭代（Policy Iteration, PI）与值迭代（Value Iteration, VI）均为求解有限状态/动作马尔可夫决策过程（MDP） 最优策略的经典动态规划算法，二者均保证收敛到唯一最优策略 π* 和最优值函数 V*，但路径、收敛速度与单步计算开销存在本质差异：

🔹 核心思想对比

• 策略迭代：交替执行两个步骤——
  (1) 策略评估（Policy Evaluation）：对当前策略 πₖ 精确（或近似）求解其值函数 V^πₖ（通常需多次迭代直至收敛）；
  (2) 策略改进（Policy Improvement）：基于 V^πₖ 执行贪心更新，生成新策略 πₖ₊₁(s) = argmaxₐ ∑ₛ′ P(s′|s,a)[R(s,a,s′) + γV^πₖ(s′)]。
  → 保证每轮后策略严格改进（除非已最优），最终在有限步内收敛（因策略空间有限）。

• 值迭代：直接迭代更新值函数，将策略改进“内嵌”于值更新中：
  Vₖ₊₁(s) ← maxₐ ∑ₛ′ P(s′|s,a)[R(s,a,s′) + γVₖ(s′)]
  → 每次更新隐式对应一次贪心策略提升，无需显式存储或评估完整策略。

🔹 收敛性关键区别

🔹 计算效率关键区别

✅ 补充说明：

• 二者均要求已知完整MDP模型（P, R），属“model-based”方法；
• 实践中常采用截断策略迭代（Truncated PI） 或 异步值迭代 平衡精度与效率；
• 在深度RL中，二者思想分别演化为：PI → Actor-Critic框架（显式策略+值估计），VI → Q-learning类算法（隐式值优化）。

# 简化策略迭代（截断版，避免无限PE）
def policy_iteration(env, gamma=0.9, max_policy_iter=50, pe_iter=20):
    pi = {s: np.random.choice(env.actions) for s in env.states}  # 随机初始策略
    for _ in range(max_policy_iter):
        # 截断策略评估：仅运行pe_iter轮TD-like更新
        V = 
        (pi, env, gamma, pe_iter)
        # 策略改进（确定性贪心）
        pi_new = {}
        for s in env.states:
            q_vals = [sum(P(s_p|s,a)*(R(s,a,s_p) + gamma*V[s_p]) 
                         for s_p in env.states) for a in env.actions]
            pi_new[s] = env.actions[np.argmax(q_vals)]
        if pi_new == pi: break
        pi = pi_new
    return pi, V