价值迭代

• 20 min read • 3849 words
Tags: MDP Re-Le
Categories: Introduction to Artificial Intelligence

价值迭代

价值迭代 (Value Iteration) 是一种经典的动态规划算法，用于在已知的马尔可夫决策过程中，计算所有状态的最优价值函数 V∗(s)V^*(s)。其核心思想是通过迭代的方式，不断更新每个状态的价值，直到价值收敛为止。

1. 核心思想

算法通过引入“时间限制”的概念，从一个有限的未来开始，逐步扩展到无限的未来，最终得到最优价值。

a.a. 时间限制价值

我们定义 Vk(s)V_k(s) 为在状态 ss 出发，且还剩下 kk 步时所能获得的最大期望效用。

  • 当 k=0k=0 时，意味着游戏立即结束，不能采取任何行动，也无法获得任何奖励。因此，对于所有状态 ss，初始值 V0(s)=0V_0(s) = 0。
  • 随着 kk 的增加，Vk(s)V_k(s) 的计算会考虑更长远的未来，从而越来越接近真正的最优价值 V∗(s)V^*(s)。

b.b. 迭代更新规则

价值迭代通过重复应用以下更新规则，从 VkV_k 计算 Vk+1V_{k+1}，直到价值收敛（即 Vk+1(s)≈Vk(s)V_{k+1}(s) \approx V_k(s) 对所有状态 ss 成立）。

对于每一个状态 ss，更新规则如下：

Vk+1(s)←max⁡a∑s′T(s,a,s′)[R(s,a,s′)+γVk(s′)]V_{k+1}(s) \leftarrow \max _{a} \sum _{s'} T(s, a, s') [ R(s, a, s') + \gamma V_k(s') ]

这个公式的含义是：

  1. 在状态 ss 尝试所有可能的行动 aa。
  2. 对于每个行动 aa，计算其期望效用。这个期望效用是所有可能的后继状态 s′s' 的（即时奖励 + 未来折扣奖励）的加权平均，权重是转移概率 T(s,a,s′)T(s, a, s')。
  3. 未来的奖励 Vk(s′)V_k(s') 需要用折扣因子 γ\gamma (gamma) 进行折算。
  4. 选择那个能够带来最大期望效用的行动 aa，并将其结果作为状态 ss 的新价值 Vk+1(s)V_{k+1}(s)。

这个更新规则与贝尔曼方程非常相似，但它们有本质区别。贝尔曼方程描述的是最优性条件（即 V∗V^* 应该满足的等式），而价值迭代的更新规则是一种 计算方法，通过迭代使其最终满足贝尔曼方程。

c.c. 贝尔曼算子

为了简化表达，我们经常使用贝尔曼算子 BB 来表示上述更新过程：

Vk+1←BVkV_{k+1} \leftarrow B V_k

其中，算子 BB 的定义就是更新规则的右半部分。可以证明，贝尔曼算子是一个以 γ\gamma 为系数的收缩映射。这意味着，每次应用贝尔曼算子，不同价值函数之间的差距都会以 γ\gamma 的比例缩小。

因为 γ∈(0,1)\gamma \in (0, 1)，所以反复应用该算子最终必然会收敛到一个唯一的不动点 (Fixed Point)，这个不动点就是最优价值函数 V∗V^*，此时 V∗=BV∗V^* = B V^*。

2. 策略提取

当我们通过价值迭代计算出最优价值函数 V∗(s)V^*(s) 后，我们的最终目标是找到最优策略 pi∗(s)\\pi^*(s)。策略提取的过程非常直观：在任何状态 ss，我们应该选择那个能够导向最大期望效用的行动。

最优策略 π∗(s)\pi^*(s) 的计算公式如下：

π∗(s)=arg⁡max⁡a∑s′T(s,a,s′)[R(s,a,s′)+γV∗(s′)]\pi^*(s) = \arg\max _{a} \sum _{s'} T(s, a, s') [ R(s, a, s') + \gamma V^*(s') ]

这本质上是在对所有可能的行动进行一次“向前看一步”的计算，然后选择最好的那个。

3. Q-价值迭代

除了直接计算状态价值 V(s)V(s)，我们也可以直接迭代计算Q值 Q(s,a)Q(s, a)。其更新规则如下：

Qk+1(s,a)←∑s′T(s,a,s′)[R(s,a,s′)+γmax⁡a′Qk(s′,a′)]Q_{k+1}(s, a) \leftarrow \sum _{s'} T(s, a, s') [ R(s, a, s') + \gamma \max _{a'} Q_k(s', a') ]

这个公式与价值迭代非常相似，关键区别在于 max⁡\max 操作的位置。因为Q值本身就与特定动作 aa 绑定，所以在计算后继状态 s′s' 的未来价值时，我们需要从 s′s' 出发，选择能使其Q值最大的动作 a′a'。

使用Q-价值迭代的好处是，一旦收敛得到最优Q值 Q∗(s,a)Q^*(s, a)，策略提取会变得非常简单，无需再考虑转移概率 TT 和奖励 RR：

π∗(s)=arg⁡max⁡aQ∗(s,a)\pi^*(s) = \arg\max_{a} Q^*(s, a)

值迭代的 max⁡\max 在最外面。意思是：“为了评估 ss 这个格子，我先试一下从这里出发的所有动作，分别计算出每个动作的平均回报，然后选那个最好的动作所对应的回报，作为这个格子的最终价值。”

Q值迭代的 max⁡\max 在里面。意思是：“我正在评估在 ss 格子执行 aa 这个特定动作的价值。我不用在当前比较哪个动作好，因为动作 aa 已经定了。我只需要计算执行 aa 之后，可能会落到哪些点 s′s'，并假设我到了那些点之后，总能做出最明智的下一步选择 (max⁡a′\max _{a'}), 然后把这些乐观的未来价值加权平均，就是我当前这个动作 a 的价值。”