Skip to main content

Iteration

Value Iteration​

  • 核心思想: 直接应用贝尔曼最优算子

vk+1(s)=max⁡a∑s′p(s′∣s,a)[r(s,a,s′)+γvk(s′)]v_{k+1}(s) = \max_a \sum_{s'} p(s'|s, a) [r(s, a, s') + \gamma v_k(s')]

  • 值迭代的收敛性: lim⁡k→∞vk=v∗\lim_{k \to \infty} v_k = v^*
  • 收敛速度分析: 误差界 ∣∣vk−v∗∣∣≤γk1−γ∣∣v1−v0∣∣||v_k - v^*|| \leq \frac{\gamma^k}{1-\gamma} ||v_1 - v_0||
  • 算法伪代码

Policy Iteration​

  • 两步交替过程
    1. 策略评估 (Policy Evaluation): 给定策略, 求解 vπv_\pi
    2. 策略改进 (Policy Improvement): π′(s)=arg⁡max⁡aqπ(s,a)\pi'(s) = \arg\max_a q_\pi(s, a)
  • 策略改进定理 (Policy Improvement Theorem)
  • 策略迭代的有限步收敛性

Truncated Policy Iteration​

  • 广义策略迭代 (Generalized Policy Iteration, GPI)
  • 截断策略评估: 不求精确解, 只迭代有限步
  • 值迭代和策略迭代都是截断策略迭代的特例

Comparison​

方法策略评估策略改进特点
策略迭代精确求解贪婪改进每轮改进保证
值迭代单步更新隐式改进计算效率高
截断策略迭代有限步迭代贪婪改进灵活平衡