学习强化学习的基本原理以及如何将值迭代应用于一个简单的示例问题
值迭代（VI）通常是在强化学习（RL）学习路径上介绍的首批算法之一。算法的底层细节介绍了强化学习的一些最基本的方面，因此掌握值迭代在进一步学习更复杂的强化学习算法之前是很重要的。然而，理解它可能会有些棘手。
本文旨在为初学者提供易于理解的值迭代介绍，假设读者对强化学习领域还不熟悉。让我们开始吧。
已经了解强化学习的基础知识？ → 跳到如何使用值迭代。
强化学习的基础知识
让我们从教科书上的定义开始，然后我会用一个简单的例子来解释。
强化学习是除了监督学习和无监督学习之外的三种关键机器学习范 Paradigms之一。强化学习不是一个单一的算法，而是一个涵盖了一系列技术和方法的框架，用于教导智能体在其环境中学习和做出决策。
在强化学习中，智能体通过采取各种行动与环境进行交互。当这些行动导致期望的状态时，智能体会受到奖励，当行动不符合期望时，智能体会受到惩罚。智能体的目标是学习一种策略，称为策略，以最大化随时间累积的奖励。这个试错的过程会改进智能体的行为策略，使其在新的、未知的环境中采取最佳或接近最佳的行为。
Richard S. Sutton和Andrew G. Barto的书《Introduction to Reinforcement Learning》被认为是该领域中最好的书籍，适合那些希望获得扎实的强化学习理解的人.. 而且它是免费的！
让我们定义一个示例问题
这个图像描述了高尔夫球比赛的最简形式。我们将使用这个例子，因为高尔夫球比赛有一个明确定义的目标 – 将球打入洞中。
在我们的例子中，高尔夫球可以处于三个位置之一：球道上、果岭上或洞中。我们从球道上开始，并且每一杆都希望离洞口更近，洞口位于果岭上。
在强化学习中，这些位置中的每一个都被称为环境的状态。你可以把状态看作是当前环境（高尔夫球场）的快照，也记录了球的位置。
在我们的游戏中，智能体击球，从球道上的球开始。智能体简单地指的是控制采取行动的实体。我们的游戏有三个可用的行动：击向球道、击向果岭和将球打入洞中。
当然，当你击球时，球可能不会去到你想要的位置。因此，我们引入了一个转移函数，将行动与状态以一定的概率联系起来。
例如，当我们从球道上开球并最终还停留在球道上时，我们可能会错过把球打进果岭的机会。在强化学习的背景下，如果我们处于球道上的球的状态并采取将球打入果岭的动作，有90%的概率我们会进入球在果岭上的状态，但有10%的概率我们会重新进入球道上的状态。
每当智能体采取一个动作时，我们将其称为对环境的一次步骤。根据刚刚采取的动作，智能体观察到它最终所处的新状态以及一个奖励。奖励函数是推动智能体朝着正确方向发展的激励机制。换句话说，我们设计奖励函数来塑造智能体的期望行为。在我们简化的高尔夫示例中，我们为将球打入洞中提供了10的奖励。
环境动态（转移和奖励函数）的设计并不是一项简单的任务。如果环境不能代表你尝试解决的问题，智能体将学习到针对错误问题的正确解决方案。我们在这里不会涉及这些设计元素，但这值得注意。
马尔可夫决策过程
为了让智能体理解问题，我们必须将其形式化为马尔可夫决策过程（MDP）。
MDP是一个数学模型，以结构化的方式描述我们的问题。它将智能体与环境的交互表示为一个连续的决策过程（即一个接一个的动作）。
它由环境动态组成（我将在这里添加一些数学符号以简化事情）：
- 有限状态集合 s ∈ S。
- 有限动作集合 a ∈ A。
- 转移函数 T(s′∣s,a) 返回在当前状态 s、当前动作 a 的情况下到达状态 s′ 的概率。
- 奖励函数 R(s,a,s′) 根据到达下一个状态 s′（在状态 s 中采取动作 a 后）给出一个标量奖励。
请注意，如果状态之间的转换存在不确定性或随机性（即在相同状态下采取相同动作两次可能会导致不同结果），我们将其称为随机MDP。我们也可以创建一个确定性MDP，其中转换和奖励完全可预测。这意味着当智能体在特定状态下采取一个动作时，动作与产生的下一个状态以及奖励之间存在一对一的对应关系。
将我们的高尔夫问题可视化为MDP，其形式与之前描绘的图像基本相同。我们将使用 S = {s1，s2，s3} 进行简写。
MDP的使用假设环境中接下来会发生的事情仅取决于当前状态和动作，而不取决于之前发生过的事情。这被称为马尔可夫性质，在强化学习中非常重要，因为它减少了计算复杂性。我稍后会对此进行更详细的解释。
价值迭代是什么？
价值迭代（Value Iteration，简称VI）是一种用于解决像上述高尔夫示例中那样具有MDP所有组件的RL问题的算法。它通过迭代改进对每个状态的“价值”估计来工作。在考虑不同可用动作时，它会考虑即时奖励和预期未来奖励。这些值使用一个价值表进行跟踪，并在每个步骤更新。最终，这一系列改进会收敛，产生一个最优策略，即状态→动作映射，智能体可以根据该策略在给定环境中做出最佳决策。
VI利用了动态规划的概念，将解决一个大问题分解为较小的子问题。在VI中，使用贝尔曼方程来指导迭代地更新每个状态的值估计，提供了一个递归关系，以邻近状态的值来表达一个状态的值。
现在这可能还不太清楚。学习VI的最简单方法是逐步分解，让我们来做吧。
值迭代算法如何工作？
下面的图像描述了算法的步骤。不要被吓到，它比看起来要简单。
首先，我们需要为训练定义一些参数。
- Theta θ 表示收敛的阈值。一旦达到 θ，我们可以终止训练循环并生成策略。它实际上只是一种确保我们创建的策略足够准确的方法。如果我们停止训练得太早，可能无法学习到最佳的行动。
- Gamma γ 表示折扣因子。这是一个值，决定了我们的代理人如何权衡未来奖励与即时奖励。较高的折扣因子（接近1）表示代理人更重视长期奖励，而较低的折扣因子（接近0）更重视即时奖励。
为了更好地理解折扣因子，考虑一个下棋的强化学习代理人。假设你有机会在下一步中捕获对手的皇后，这将带来显著的即时奖励。然而，你还注意到，通过牺牲一个价值较低的棋子，你可以设置一个未来的优势，可能会导致将军和更大的奖励。折扣因子帮助你平衡这个决策。
(1) 初始化：现在我们已经定义了参数，我们想要为所有状态的值函数 V(s) 进行初始化。通常意味着我们将所有值设置为0（或其他任意常数）的每个状态。将值函数视为一个表格，用于跟踪每个状态的值，经常更新。
(2) 外循环：现在一切准备就绪，我们可以开始迭代地更新值的过程。我们从外循环开始，直到满足收敛准则（直到 Δ < θ）为止。
在每次外循环的过程中，我们首先设置 Δ = 0。Delta Δ 用于表示所有状态的值估计变化，算法会持续迭代，直到这个变化 Δ 低于指定的阈值 θ。
(3) 内循环：对于 S 中的每个状态 s，我们：
- 将变量 v 设置为当前状态的值 V(s)，记住 – 这是从我们的值表中获取的（因此在第一次循环中，v = V(s) = 0）
- 执行贝尔曼方程来更新 V(s)
- 更新 Δ（我们将回到这里）
贝尔曼方程
算法的这一行是最重要的。它要求我们更新循环中正在查看的当前状态的值。通过考虑从该特定状态可用的所有操作（1步的展望），计算该值。当我们采取每个可能的行动时，它将呈现一组可能的下一个状态 s′ 和相应的奖励 r.
所以，对于每个下一个状态s′和相应的奖励r，我们执行p(s′, r|s, a)[r + γV(s′)]。让我们来分解一下：
- p(s′, r|s, a) 是处于状态s，采取行动a，并最终到达下一个状态s′的概率（这只是我们的转移函数）
- [r + γV(s′)] 是到达下一个状态s′的奖励r（从我们的奖励函数中获得）+ 折扣γ * 下一个状态s′的值（从我们的价值表中获得）
- 然后我们将这两部分相乘p(s′, r|s, a) * [r + γV(s′)]
请记住，这个计算只是针对一个下一个状态s′（树的第三层），我们需要重复这个过程，对每个可能的下一个状态s′在采取行动a之后。
完成这些步骤后，我们将对刚刚获得的所有结果求和Σₛ′, ᵣ p(s′, r|s, a) * [r + γV(s′)]。然后我们对每个行动a（树的第二层）重复这个过程。
完成这些步骤后，我们将为内循环中正在查看的当前状态的每个可能行动a关联一个值。我们使用maxₐ选择最高值，并将其设置为该状态的新值V(s)←maxₐ Σₛ′, ᵣ p(s′, r|s, a) * [r + γV(s′)]。
请记住，这个过程只涵盖了一个状态s（树的第一层）
如果我们要编写程序，对于树中的每个级别，我们需要3个for循环：
(3) 内循环（继续）：在进行内循环的下一次迭代之前，我们对当前的Δ值和此状态的前一个值v与刚刚计算出的新值V(s)之间的差异进行比较。我们更新Δ为这两个值中较大的一个：Δ ← max(Δ,| v – V(s)|)。这有助于我们追踪我们离收敛有多近。
好的，这个过程完成了内循环的一次迭代。在退出内循环并对收敛条件Δ < θ进行检查之前，我们对S中的每个s执行步骤（3）。如果满足此条件，我们退出外循环；否则，我们返回步骤（2）。
(4) 策略提取：到此时，我们可能已经通过外循环进行了多次迭代，直到收敛。这意味着我们的价值表已经更新，表示每个状态的最终值（换句话说，是“在每个状态中表现得有多好”）。现在我们可以从中提取策略。
请记住，策略π本质上是一个从状态→行动的映射，并且对于每个状态，它选择能够使我们获得最佳值的行动a。为了计算这个，我们执行与之前完全相同的过程，但是不是使用maxₐ来获得状态s的值，而是使用argmaxₐ来获得给我们最佳值的行动a。
就是这样！
策略迭代是另一种动态规划算法。它类似于值迭代，不同之处在于它在改善策略时会使其对当前价值函数贪婪，并评估策略的性能直到收敛，通常需要更少的迭代但每次迭代的计算量更大。
使用值迭代解决示例问题
值迭代在我们完成一个示例问题后应该会更加清晰，所以让我们回到我们的高尔夫MDP。我们已经将其形式化为MDP，但目前代理程序在打高尔夫时并不知道最佳策略，所以让我们使用值迭代来解决高尔夫MDP。
我们将首先使用相当标准的值定义我们的模型参数：
γ = 0.9 // 折扣因子θ = 0.01 // 收敛阈值然后，我们将为状态S中的状态初始化值表为0：
// 值表V(s0) = 0V(s1) = 0V(s2) = 0现在我们可以开始外部循环：
Δ = 0并为S中的每个状态进行三次内部循环：
// Bellman更新规则// V(s) ← maxₐ Σₛ′, ᵣ p(s′, r|s, a) * [r + γV(s′)]//******************* 状态 s0 *******************//v = 0// 在这里我们只看了一个动作，因为只有一个动作可以从s0执行// 我们知道其他动作不可能，并且因此总和为0V(s0) = max[T(s0 | s0, 击向果岭) * (R(s0, 击向果岭, s0) + γ * V(s0)) + T(s1 | s0, 击向果岭) * (R(s0, 击向果岭, s1) + γ * V(s1))]V(s0) = max[0.1 * (0 + 0.9 * 0) + 0.9 * (0 + 0.9 * 0)]V(s0) = max[0] = 0// Δ更新规则// Δ ← max(Δ,| v - V(s)|)Δ = max[Δ, |v - v(s0)|] = max[0, |0 - 0|] = 0//******************* 状态 s1 *******************//v = 0// 这里有两个可用的动作V(s1) = max[T(s0 | s1, 击向球道) * (R(s1, 击向球道, s0) + γ * V(s0)) + T(s1 | s1, 击入洞) * (R(s1, 击入洞, s1) + γ * V(s1)), T(s2 | s1, 击入洞) * (R(s1, 击入洞, s2) + γ * V(s2))]V(s1) = max[0.9 * (0 + 0.9 * 0) + 0.1 * (0 + 0.9 * 0), 0.1 * (0 + 0.9 * 0) + 0.9 * (10 + 0.9 * 0)]V(s1) = max[0, 9] = 9Δ = max[Δ, |v - v(s1)|] = max[0, |0 - 9|] = 9//******************* 状态 s2 *******************//// 终止状态，无法执行任何动作这给我们的值表带来了以下更新：
V(s0) = 0V(s1) = 9V(s2) = 0我们不需要担心s2，因为这是一个终止状态，意味着在此处无法执行任何动作。
现在我们退出内部循环并继续外部循环，在以下内容上执行收敛检查：
Δ < θ = 9 < 0.01 = False由于我们还没有收敛，我们进行外循环的第二次迭代：
Δ = 0再进行内循环的另外3次迭代，使用更新后的值表：
//******************* 状态 s0 *******************//v = 0V(s0) = max[T(s0 | s0, 击向绿地) * (R(s0, 击向绿地, s0) + γ * V(s0)) + T(s1 | s0, 击向绿地) * (R(s0, 击向绿地, s1) + γ * V(s1))]V(s0) = max[0.1 * (0 + 0.9 * 0) + 0.9 * (0 + 0.9 * 9)]V(s0) = max[7.29] = 7.29Δ = max[Δ, |v - v(s0)|] = max[0, |0 - 7.29|] = 7.29//******************* 状态 s1 *******************//v = 9V(s1) = max[T(s0 | s1, 击向公平地) * (R(s1, 击向公平地, s0) + γ * V(s0)) + T(s1 | s1, 击入洞) * (R(s1, 击入洞, s1) + γ * V(s1)), T(s2 | s1, 击入洞) * (R(s1, 击入洞, s2) + γ * V(s2))]V(s1) = max[0.9 * (0 + 0.9 * 7.29) + 0.1 * (0 + 0.9 * 9), 0.1 * (0 + 0.9 * 9) + 0.9 * (10 + 0.9 * 0)]V(s1) = max(6.7149, 9.81) = 9.81Δ = max[Δ, |v - v(s1)|] = max[7.29, |9 - 9.81|] = 7.29//******************* 状态 s2 *******************//// 终止状态，无可选动作在第二次迭代结束时，我们的值为：
V(s0) = 7.29V(s1) = 9.81V(s2) = 0再次检查收敛：
Δ < θ = 7.29 < 0.01 = False仍然没有收敛，因此我们继续以上相同的过程，直到 Δ < θ。我不会展示所有的计算，上面两个就足够理解过程了。
经过6次迭代，我们的策略收敛。这是我们的值和每次迭代时的收敛率：
迭代 V(s0) V(s1) V(s2) Δ 收敛1 0 9 0 9 False2 7.29 9.81 0 7.29 False3 8.6022 9.8829 0 1.3122 False4 8.779447 9.889461 0 0.177247 False5 8.80061364 9.89005149 0 0.02116664 False6 8.8029969345 9.8901046341 0 0.0023832945 True现在我们可以提取我们的策略：
// 策略提取规则// π(s) = argmaxₐ Σₛ′, ᵣ p(s′, r|s, a) * [r + γV(s′)]//******************* 状态 s0 *******************//// 我们知道从 s0 只有一个可能的动作，但还是进行一下计算π(s0) = argmax[T(s0 | s0, 击向绿地) * (R(s0, 击向绿地, s0) + γ * V(s0)) + T(s1 | s0, 击向绿地) * (R(s0, 击向绿地, s1) + γ * V(s1))]π(s0) = argmax[0.1 * (0 + 0.9 * 8.8029969345) + 0.9 * (0 + 0.9 * 9.8901046341)]π(s0) = argmax[8.80325447773]π(s0) = 击向绿地//******************* 状态 s1 *******************//π(s1) = argmax[T(s0 | s1, 击向公平地) * (R(s1, 击向公平地, s0) + γ * V(s0)) + T(s1 | s1, 击向公平地) * (R(s1, 击向公平地, s1) + γ * V(s1)), T(s1 | s1, 击入洞) * (R(s1, 击入洞, s1) + γ * V(s1)) + T(s2 | s1, 击入洞) * (R(s1, 击入洞, s2) + γ * V(s2))]V(s1) = max[0.9 * (0 + 0.9 * 8.8029969345) + 0.1 * (0 + 0.9 * 9.8901046341), 0.1 * (0 + 0.9 * 9.8901046341) + 0.9 * (10 + 0.9 * 0)]π(s1) = argmax[8.02053693401, 9.89010941707]π(s1) = 击入洞我们的最终策略是：
π(s0) = 击打到果岭π(s1) = 击打进洞π(s2) = 终止状态（无动作）因此，当我们的智能体处于“球在球道上”状态（s0）时，最佳动作是“击打到果岭”。这似乎很明显，因为那是唯一可用的动作。然而，在s1中，有两个可能的动作，我们的策略已经学会了“击打进洞”。现在我们可以将这个学到的策略传递给其他想打高尔夫球的智能体！
就是这样！我们刚刚使用值迭代方法解决了一个非常简单的强化学习问题。
动态规划的局限性
需要注意的是，值迭代方法以及其他动态规划算法都有其局限性。首先，它假设我们对MDP的动力学有完全的了解（我们称之为“基于模型的强化学习”）。然而，在现实世界的问题中，这很少发生，例如，我们可能不知道转移概率。对于这种情况，需要使用其他方法，例如Q学习（“无模型强化学习”）。
其次，对于更大的问题，随着状态和动作的数量增加，值表的大小呈指数增长（想一想试图定义所有国际象棋可能状态的问题）。这导致了“维度诅咒”问题，计算和内存需求迅速增加，使得在高维问题上应用动态规划变得具有挑战性。
然而，值迭代方法很棒，因为它介绍了强化学习的一些关键基础概念，这些概念构成了您可能继续学习的更复杂算法的基础。
谢谢阅读！
我希望这篇文章对强化学习和值迭代方法有一个易于理解的介绍。
如果您在这里学到了新东西，请给个👏并关注！
除非另有说明，所有图片均由作者创建。