强化学习入门

大多数对机器学习主题深感兴趣的人认为它与神经网络是同义词。在当前的形态中，神经网络似乎是通用的工具。通过选择正确类型的神经网络，相同的工具，稍作变化，可能就能够解决大多数问题。但这并不意味着神经网络是解决特定问题的最佳（甚至正确的）工具。

在本文中，我们将着眼于一种问题类型，以一个小游戏为例，这种问题可以使用另一种称为强化学习的技术轻松解决。我们将研究需求、实现以及模型的优势。

游戏

这个游戏可以用铅笔和纸玩，在用程序解决问题之前，最好先获得第一手经验。这是一个赛车游戏，在游戏中，赛道被尽可能快地穿过，同时保持“汽车”在赛道上。赛道和汽车的位置在方格网格上指定。在游戏的任何时刻，汽车都有一个位置和速度。速度包括（与物理学中速度的定义一致）方向。移动规则最容易用图形解释。

图片来源

opensource.com

在这两种不同的情况下，汽车的当前位置用红色方块表示，其先前位置用橙色方块表示。这两个方块之间的距离定义了汽车的速度——在一种情况下为 (4,-1)，在另一种情况下为 (4,0)——给定一个坐标系，其中第一维从左到右，第二维从下到上。

速度通过 曼哈顿距离 测量，方法是将两个值的绝对值相加：|4|+|-1|=5 和 |4|+|0|=4。

下一步的规则是：速度向量的长度必须最多改变一个单位，向上或向下，并且速度向量的分量的值必须各自最多改变一个单位。因此，汽车在下一步最多可以移动到七个可能的位置，这些位置在图表中用绿色方块表示。如果当前速度为 1，则汽车可能会停下来，但这没有用，因为目标是尽可能快地完成赛程。这可以通过不允许速度为零来避免，这减少了在这种情况下可能的新的位置数量。

赛道是另一个限制。汽车不得离开赛道，并且鉴于汽车的速度，一些（或全部）可能的新的位置可能是无效的。赛道不必由直线和规则曲线定义，它可以看起来像下图（甚至更复杂）。

图片来源

opensource.com

对于这个练习，我们必须在赛道上定义一条起跑/终点线。汽车从这条线上的某个位置开始，初始速度为 1（即，水平或垂直一步），并且它必须从另一侧穿过这条线。在示例代码中，赛道和起跑线位置编码在一个无损图像文件中。起始位置单独给出为起跑线上的线。

任何成功的比赛都将穿过起跑/终点线而不会离开赛道。最佳解决方案是需要最少步骤的解决方案。在大多数情况下，可能存在多个可能的解决方案，但这取决于赛道和起始条件。

寻找解决方案

如果我们考虑一种传统方法，即我们从开始时给定的状态确定解决方案，我们很快就会遇到问题。可能性实在太多了。

问题在于，要计算下一步，必须考虑所有可能的未来步骤。某种形式的封闭公式可能无法制定。这就留下了递归搜索，除非赛道非常短，否则递归搜索很快就会变得不切实际。组合工作将是令人望而却步的。

对于非平凡的赛道，因此可能有必要接受概率结果。

可用信息

理论上，可以在途中的所有步骤中提供有关所有未来步骤的信息。正如上一节所述，这样做成本高昂。为了决定下一步，我们应该将自己限制在该信息的子集内——理想情况下，是非常小的子集。这显然不能保证我们能够立即找到最佳解决方案，但这正是机器学习技术发挥作用的地方。

Q-学习

在这里，我们正在研究一种称为 Q-学习 的机器学习技术，这是一种特定的强化学习技术。它允许学习动作-价值函数，这正是我们在这里想要的：我们想知道，在任何情况下，如何改变速度，而该移动的质量就是价值。决定使用 Q-学习本身并不能决定如何计算价值；这仍然由数据科学家决定。

我们在这里不深入探讨 Q-学习背后的理论细节。只需说它能够为大量问题找到最优函数（对于那些感兴趣的人，可以对所有马尔可夫决策过程进行建模）。没有必要拥有环境模型（即，在这种情况下，没有必要对整个赛道进行建模）。我们只需查看汽车在步骤前后紧邻的附近，并为每个步骤确定表示值或奖励。

该算法需要表示当前状态：汽车的位置和速度。我们想确定每个状态的动作，即新速度和新位置的结果。如上所述，我们需要为此分配一个值，用一个数字表示。我们得到的是所谓的 Q 函数

图片来源

opensource.com

我们一开始对该函数一无所知，我们可以最初为所有输入返回一个固定的、任意选择的值。根据稍后在学习阶段使用的值，初始值可能会对学习速度产生影响。

Q 的更好值是迭代确定的。此迭代步骤从给定状态开始，确定一个动作（如何完成将在下面讨论），并确定奖励。然后，此信息用于更新 Q 函数

图片来源

opensource.com

用文字翻译，这意味着 Q 对于状态 s_t 和动作 a_t 的更新方式是：将旧值乘以 1-α， 并加上 α 乘以步骤 r_t 的奖励与 γ 乘以 Q 的最大未来值（或其估计值）之和。对于最终状态，我们不必（而且绝不能）更新 Q；我们只需适当地设置奖励。分别与 1-α 和 α 相乘保证了 Q 的值受初始值的选择和最终状态的奖励限制。

值 γ 是学习算法的所谓超参数。在这种情况下，它是折扣因子，这是一个在类似情况（例如，金融数学）中使用的术语。这意味着，如果未来状态的奖励为 r，则其在当前状态的值必须被折扣，因为奖励只能在一个或多个额外的步骤后才能获得。每个步骤都以因子 0<γ<1 折扣。找到 γ 的正确值是开发模型的一部分。

有了这个描述，应该已经可以了解模型学习是如何发生的。我们从给定状态开始，选择一个动作，计算奖励，并确定从新状态开始的动作的最佳奖励。使用所有这些信息，我们更新当前状态的 Q 函数，并从那里继续。有几件事需要注意

• 在我们的示例中，每个状态最多有七个可能的动作；如果赛道限制了移动，则更少。因此，Q 的表示形式并没有特别的问题。
• 最初，Q 的所有值——除了最终状态——都是任意初始化的。因此，未来步骤的最大值在一开始并没有太大差异。只有下一步导致最终状态的状态才会最初找到很大的未来奖励。一遍又一遍地从头开始重复迭代，会将高奖励值传播到通往目标的路径上的早期状态。不通往目标的路径/状态永远不会有很高的未来奖励。

还有一个剩余的细节需要考虑：如何在学习阶段选择下一步。由于可能需要许多步骤才能达到目标，因此不希望随机选择下一步，因为这会使达到目标的概率很低。

Q 的高值可用于指导选择。但是，总是选择奖励最高的动作可能意味着永远不会探索更好的替代方案。因此，我们需要一种混合：在给定的概率 ε 下，我们选择一个随机的（有效的）下一个状态。否则，我们从 Q 值最高的可能状态中选择一个。ε 成为算法的另一个超参数，它选择发生多少探索与遵循已知的良好路径的程度。

或者，可以使用 Q 的初始值来鼓励探索。使用高值将确保最终探索状态，而那些不通往目标的状态随着时间的推移会看到它们的 Q 值降低。初始值的选择在这里至关重要，因为它绝不能被奖励值所掩盖。

一旦模型得到充分训练，我们就可以通过寻找奖励最高的动作来确定任何状态下的最佳步骤，然后继续这样做，直到达到目标。该算法保证最终找到最佳解决方案，但这可能需要时间，并且过早地测试解决方案可能不会导致正确的结果：即，当每次选择具有最佳 Q 值的动作 a_t 时，链 s₁→s₂→…→s_n 可能不会导致最终状态。这是在使用模型时需要记住的事情。

应用 Q-学习

现在我们准备将 Q-学习应用于汽车绕赛道比赛的问题。要应用该算法，我们需要一种计算奖励的方法。

• 如果下一步将离开赛道，则奖励最小。
• 更接近目标的新状态具有更高的奖励。
• 具有更高速度的新状态具有更高的奖励。

奖励的最后两个方面旨在在可以更快地达到目标的情况下给出更高的值，因为目标更近，速度更高，或者两者兼而有之。到目标的距离和速度的好处应该是累加的。

在定义函数方面仍然有很多灵活性。以下是一种可能的方式。

def getr(d1, d2, va, Qgoal):
    if d1 < 0 or d2 < 0 or d1 - d2 > va:
        return None

    if d1 < d2:
        if d1 <= va and d2 > 5 * va:
            return Qgoal
        return (d1 - d2) - (va >> 1) / (d1 - d2)
    else:
        return (1 + d1 - d2) * va

即使是不熟悉 Python 的人也应该能够理解代码。参数 d1 和 d2 是当前和下一个位置到目标的距离，而 va 是当前速度。除了检查无效位置外，不使用绝对值。只有差值用于计算奖励值，因此这些值是如何定义的并不重要。它们只能使用本地信息。到目标线的方向是已知的，因为您知道最后一个位置，并且您可以计算在正确方向上采取了多少步。

对于赛道外的所有位置，d1 和 d2 的值为负数。如果检测到这一点（或在其他无效情况下），则返回值 None，表明此移动是不可能的，不必进一步调查。该公式考虑了新位置离目标更远的情况，但如果速度足够高，它仍然值得一些奖励。主要规则是最后一个，它根据到目标线的减少距离和速度来缩放奖励。此版本的评分绝不是理想的或唯一的。这只是一个例子。模型开发过程的一部分是尝试更多和不同版本的此函数。

对于汽车所处的不同状态，都会调用此函数。现在我们必须讨论如何确定这些不同的状态。

内部学习循环

在内部循环中，我们必须通过确定汽车在下一步可以拥有的七个可能速度中的哪一个，以及基于此和当前位置，确定赛道上可接受的位置来确定下一个状态。然后，我们使用上面讨论的算法来选择可能的下一步之一。生成的代码可能如下所示

  co = (start[0] + startspeed[0], start[1] + startspeed[1])
  speed = startspeed
  aspeed = absspeed(speed)
  nextspeeds = possible_speeds(speed)
  curdist = dist[co[0]][co[1]]
  scores = score[co[0]][co[1]]
  known = known_speeds(scores, nextspeeds)
  bestscore = Qfail
  bestspeeds = []
  for s in known:
    thisscore = scores[s]
    if thisscore == bestscore:
      bestspeeds.append(s)
    elif thisscore > bestscore:
      bestscore = thisscore
      bestspeeds = [ s ]
  if bestscore < Q0 and len(known) != len(nextspeeds):
    bestscore = Q0
    bestspeeds = set(nextspeeds) - set(known)
  path = [ ]
  reached_goal = False

  while True:
    path.append((speed, co))

    if random.random() < epsilon:
      nextspeed = random.sample(nextspeeds, 1)[0]
    else:
      # Pick according to current score
      nextspeed = random.sample(bestspeeds, 1)[0]

    nextco = (co[0] + nextspeed[0], co[1] + nextspeed[1])
    nextdist = dist[nextco[0]][nextco[1]]
    nextaspeed = absspeed(nextspeed)

    r = getr(curdist, nextdist, nextaspeed, Qgoal)
    if not r:
      # crash
      score[co[0]][co[1]][nextspeed] = Qfail
      break

    if curdist <= aspeed and nextdist > 10 * aspeed:
      nextbestscore = Qgoal
      reached_goal = True
    else:
      scores = score[nextco[0]][nextco[1]]
      speedspp = possible_speeds(nextspeed)
      known = known_speeds(scores, speedspp)
      bestscore = Qfail
      bestspeeds = []
      for s in known:
        thisscore = scores[s]
        if thisscore == bestscore:
          bestspeeds.append(s)
        elif thisscore > bestscore:
          bestscore = thisscore
          bestspeeds = [ s ]
        if bestscore < Q0 and len(known) != len(speedspp):
            bestscore = Q0
            bestspeeds = set(speedspp) - set(known)

    oldval = score[co[0]][co[1]][nextspeed] if nextspeed in
                score[co[0]][co[1]] else Q0
    score[co[0]][co[1]][nextspeed] = (1 - alpha) * oldval +
                                     alpha * (r + gamma * bestscore)

    if reached_goal or len(path) > 5 * tracklen:
      break

    co = nextco
    speed = nextspeed
    aspeed = nextaspeed
    nextspeeds = speedspp
    curdist = nextdist

这就是创建从固定起点 (start) 和起始速度 (startspeed) 到越过目标线或汽车离开赛道的路径的所有代码。在循环准备阶段，计算了一整套变量。发生这种情况是因为，在循环的第二部分中，这些变量是为下一步计算的。我们可以重用这项工作。

变量 nextspeeds（是下一步可能速度的列表）和 bestspeeds（是导致得分最高状态的速度列表）是所需的主要初始化。

在循环中，首先将新位置记录在 path 中。接下来是根据游戏规则确定可能的速度，确保速度不会降至零。所有可能的新速度都存储在列表 nextspeeds 中。

从此列表中，选择一个速度。以 epsilon 表示的概率，选择一个随机值。否则，选择得分最高的下一个状态之一。这也是多种可能性之间的选择，以防有多个状态具有相同的分数。

epsilon 的值必须足够小，以便尝试改进先前找到的良好序列。沿着这个思路，前 n 个最佳分数（因为没有做出随机选择）的概率为 (1 - ε)ⁿ，对于 ε=5%，这意味着 1000 次尝试中有 6 次成功完成。如果必须发现长路径，这可能不够。ε 是一个重要的超参数。

一旦选择了新速度，汽车的下一个坐标将在 newco 中计算。

之后，更新当前位置的分数。score 变量由坐标和选定的速度索引。奖励通过调用 getr 计算，我们在上一节中看到了这一点。如果坐标落在赛道外，我们分配一个负分并终止循环。用于负奖励的值也是一个超参数。

接下来是我们上面看到的 Q 函数更新的实现。我们从所有可能的下一个状态中确定得分最高的状态，然后使用超参数 α 和 γ 来更新分数。唯一的复杂之处在于速度值在 score 数组中尚不为人所知，然后我们必须使用值 Q0。

讨论

这就是全部。解决这个问题不需要编码任何问题知识。将实现与问题联系起来的唯一细节是 getr 函数的实现，该函数提供环境信息。正如我们所看到的，使用的信息是本地的；没有使用关于问题的全局信息。该实现使用了每个状态中只有少量动作是可能的这一事实，因此该实现可以依赖于字典实现。对于您可能希望使用此机器学习算法的所有可能问题，情况可能并非如此。除此之外，该实现可以重用。

以下是运行 400 万次后实现的输出。

图片来源

opensource.com

赛道的轮廓清晰可见。在内部，使用不同的灰度级别，显示了赛道上各个位置之间的最佳分数。这种表示形式省略了很多信息，因为赛道上每个位置的动作可能包含许多不同的速度，并且只显示一个值。该图形仍然有用。

红色点（在这里几乎不可见，但您可以在此项目的 GitHub 中的图像上放大）构成了我们正在寻找的“解决方案”的最佳路径。除非算法无限期运行，否则不能保证它是最佳解决方案。随着时间的推移，解决方案肯定会变得更好——并且示例中的解决方案看起来还不错。编写一个特定的算法来更好地解决这个问题并不容易。要查看算法的进展，我们可以查看程序在运行次数较少后的状态，例如在下面仅运行 20,000 次的情况。

图片来源

opensource.com

我们可以看到已经找到了一个解决方案，但它并不是真的很好。采取的步骤不是直线或规则曲线。相反，红线会产生各种曲线。这是可以理解的，因为在开始时，算法基本上执行随机游走，如果某些步骤没有立即导致崩溃，它们将获得正分。完成此操作后，算法主要（由 ε 确定）遵循已知的良好路径。算法只是偶尔会偏离这些“良好”路径并尝试其他方法。如果这些步骤恰好在正确的方向上，它们将很容易压倒先前的良好路径，并且汽车采取的整个路径将变得越来越直。

亲自尝试

有很多方法可以影响学习算法，从像 ε、α、γ 等超参数，到 getr 函数的不同实现。您可以从本文中显示的代码开始亲自尝试，该代码可以从 GitHub 上的 track-rl 下载