价值迭代

价值迭代是一种算法，用于求解以马尔可夫决策过程（MDP）表示的序贯决策问题。它反复更新对可实现的最佳长期回报的估计，直到这些估计趋近最优价值函数，随后便可从中提取决策规则。该方法属于动态规划，也是强化学习中的一种基本规划方法。其经典形式假设转移概率和奖励已知，而不是直接通过交互来学习它们。(incompleteideas.net)

数学设定

考虑一个有限马尔可夫决策过程，其状态集合为 $S$ ，可用动作集合为 $A(s)$ ，转移概率为 $P(s'\mid s,a)$ ，即时奖励的期望为 $r(s,a)$ ，折扣因子为 $0\leq\gamma<1$ 。对于每个状态—动作对， $P(\cdot\mid s,a)$ 都是后继状态上的概率分布。马尔可夫性质意味着，当前状态和动作包含了确定下一状态分布所需的信息。(web.stanford.edu)

策略（强化学习）规定了如何选择动作。其折扣价值是累积奖励的期望值：

V^\pi(s)= \mathbb E_\pi\!\left[ \sum_{t=0}^{\infty}\gamma^t R_{t+1} \,\middle|\,S_0=s \right].

当奖励有界时，折扣使这一无穷级数绝对收敛。最优价值 $V^*(s)=\sup_\pi V^\pi(s)$ 满足贝尔曼方程的最优性形式：

V^*(s)=\max_{a\in A(s)} \left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V^*(s')\right].

这个方程将即时奖励与后续可实现的最佳价值分开表示。(web.stanford.edu)

更新规则与策略提取

将贝尔曼最优性算子 $T$ 定义为

(TV)(s)=\max_{a\in A(s)} \left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V(s')\right].

从任意各分量均为有限值的初始价值向量 $V_0$ 出发，价值迭代应用如下递推关系：

V_{k+1}=TV_k.

每次更新都通过向前展望一步来评估所有可用动作，并保留其中的最大结果。这是一种完全备份：它对所有可能的后继状态求加权平均，而不是仅使用一次采样得到的转移。(inst.eecs.berkeley.edu)

在同步价值迭代中， $V_{k+1}$ 的每个分量都仅根据 $V_k$ 计算。典型实现会将价值初始化为零，反复完整遍历所有状态，并在满足指定的精度标准时停止。若采用零初始化， $V_k$ 也表示终止收益为零、时域长度为 $k$ 步时的最优回报。因此，连续迭代相当于不断延长规划时域。(inst.eecs.berkeley.edu)

对于计算得到的价值函数 $V$ ，贪心策略选择

\pi_V(s)\in\operatorname*{arg\,max}_{a\in A(s)} \left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V(s')\right].

当 $V=V^*$ 时，任何这样的策略都是最优策略。若多个动作并列达到最大值，则可能存在不止一个最优动作；始终按照固定规则选择其中一个，就能得到确定性策略。(wanghemath.github.io)

收敛性与停止准则

核心收敛结论是：在最大范数 $\|V\|_\infty=\max_s|V(s)|$ 下， $T$ 是一个压缩映射：

\|TV-TW\|_\infty\leq\gamma\|V-W\|_\infty.

因此，巴拿赫不动点定理保证存在唯一的不动点 $V^*$ ，并且从任意初始向量出发的迭代都会收敛到它。价值误差满足

\|V_k-V^*\|_\infty \leq\gamma^k\|V_0-V^*\|_\infty.

这是几何收敛，但随着 $\gamma$ 趋近于 1，收敛速度会变慢。(wanghemath.github.io)

由于 $V^*$ 未知，实际实现通常会监测贝尔曼残差：

\delta(V)=\|TV-V\|_\infty.

它给出了一个可计算的误差上界：

\|V-V^*\|_\infty\leq\frac{\delta(V)}{1-\gamma}.

对于同步迭代， $\delta(V_k)=\|V_{k+1}-V_k\|_\infty$ 。因此，当这个差值不超过 $(1-\gamma)\varepsilon$ 时停止，就能保证 $V_k$ 在最大范数下的误差不超过 $\varepsilon$ 。判断相邻两轮遍历之间的微小变化时，必须结合折扣因子。价值估计的精度与贪心策略的性能是不同的量；在数值尚未完全收敛之前，所选策略就可能已经达到最优。(wanghemath.github.io)

计算成本与变体

对于具有 $n$ 个状态、每个状态至多有 $m$ 个动作的情况，若转移模型是稠密的，则每轮遍历需要进行 $O(n^2m)$ 次算术运算，这里使用的是大O记号。如果每个状态—动作对至多有 $d$ 个可能的后继状态，计算成本就降为 $O(nmd)$ 。价值向量需要 $O(n)$ 的存储空间，模型本身所需的存储空间另计。因此，稀疏性会显著影响计算复杂性。(cs.cmu.edu)

原地更新会立即复用刚计算出的价值。异步变体只更新选定的状态，而不是均匀遍历所有状态。在折扣设定下，只要每个状态都持续得到更新，就可以保持收敛性；使用延迟信息的实现还需要对延迟施加适当限制。这类方法可以将计算集中在状态空间中相关的区域。(incompleteideas.net)

参考来源

3 Value Iteration — Introduction to Artificial Intelligenceinst.eecs.berkeley.edu
Value Iterationcs.cmu.edu
11 Value Iteration — Reinforcement Learning: A Mathematical Introductionwanghemath.github.io
Algorithm 2 discounted value iterationweb.stanford.edu
CertRL: Formalizing Convergence Proofs for Value and Policy Iteration in Coqarxiv.org
Machine Learning — Lecture 17see.stanford.edu
The Divergence of Reinforcement Learning Algorithms with Value-Iteration and Function Approximationarxiv.org
An Empirical Algorithm for Relative Value Iteration for Average-Cost MDPsweb.stanford.edu

数学设定

更新规则与策略提取

收敛性与停止准则

计算成本与变体

相关方法与局限

参考来源