8 强化学习从零学教程系列之动态规划之值迭代算法
在上一篇教程中,我们探讨了动态规划的基本思想和框架,为我们后续学习强化学习打下了坚实的基础。在本篇中,我们将深入了解动态规划的一种具体实现——值迭代算法。这一算法在解决马尔可夫决策过程(MDP)中的最优策略时,提供了一种有效的计算手段。
值迭代算法概述
值迭代算法是一种在给定状态空间和动作空间的条件下,通过递归地更新状态价值,从而逐步收敛到最优值函数的动态规划方法。值迭代不仅可以用于求解最优价值函数,还能获取最优策略。
算法步骤
值迭代算法的主要步骤如下:
- 初始化:为所有状态初始化一个任意的价值函数,通常是将所有状态的价值设为0。
- 更新价值函数:根据贝尔曼方程更新每个状态的价值函数:
$$
V_{i+1}(s) = \max_{a \in A} \sum_{s’ \in S} P(s’|s, a)[R(s, a, s’) + \gamma V_i(s’)]
$$
其中,$V_i(s)$ 是状态$s$ 在第$i$次更新时的价值,$P(s’|s, a)$ 是在状态$s$下采取动作$a$后转移到状态$s’$的概率,$R(s, a, s’)$ 是在此转移中获得的奖励,$\gamma$ 是折扣因子。 - 收敛判断:不断迭代更新价值函数,直到价值函数的变化小于定义好的阈值(如0.01)。
- 获取策略:依据最终的价值函数,推导出最优策略:
$$
\pi^*(s) = \arg \max_{a \in A} \sum_{s’ \in S} P(s’|s, a)[R(s, a, s’) + \gamma V(s’)]
$$
示例:网格世界
为更好地理解值迭代算法,我们通过一个简化的示例——网格世界来说明。
问题描述
假设我们有一个$4 \times 4$的网格世界,智能体在每个状态(网格单元)中可以选择向上、向下、向左或向右移动。目标是使智能体尽快到达目标状态(右下角),并且每次移动都要消耗$1$的奖励。目标状态的奖励为$0$,其他状态的奖励均为$-1$。
设置参数
- 状态空间$S$:包含所有的$16$个网格。
- 动作空间$A$:包含
up
、down
、left
、right
。 - 折扣因子$\gamma$:取$0.9$。
值迭代实现
1 | import numpy as np |
在以上代码中,我们通过一个简单的数组V
来维持各状态的价值。每次我们都会更新状态价值,直到所有状态的价值收敛。最终返回的V
就是每个状态对应的最优价值。
策略提取
一旦获取到最终的价值函数,我们可以根据上述策略公式,从每个状态推导出最优策略。
1 | def extract_policy(V): |
在策略提取的过程中,我们遍历每个状态,选择能够带来最大价值的动作,并形成最终的policy
。每个动作可以用数字表示,比如0
代表up
,1
代表down
,2
代表left
,3
代表right
。
总结
本文详细介绍了值迭代算法的工作机制,并通过实践案例展示了如何在一个简单的网格世界中实现它。值迭代是动态规划的重要组成部分,广泛应用于强化学习中。掌握了这一算法后,我们将在下一篇教程中进一步探讨动态规划的另一个经典算法——策略迭代算法。希望大家能在实践中不断探索并深化对强化学习的理解!
8 强化学习从零学教程系列之动态规划之值迭代算法