算法基础（17） | 强化学习 | Markov决策过程

0. 简介

近年来，深度强化学习正在兴起。世界各地的研究人员和大众媒体都没有更多关注深度学习的其他子领域。在深度学习方面取得的最大成就是由于深度强化学习。

图1

图2

2014年，AI在Atari游戏中远远超过了人类的水平。其中，最令人惊奇的是，这些AI没有一个是由人类明确编程或教导如何解决这些任务，他们通过深度学习和强化学习的力量自学。

本文章的目标是为您提供必要的数学基础域。

图3

1 深度强化学习

深度强化学习可以概括为构建一个直接从与环境的交互中学习的算法。环境可能是现实世界，计算机游戏，模拟甚至是棋盘游戏，如围棋或国际象棋。与人类一样，AI 从其行为的后果中学习，而不是从明确的教导中学习。

图4

在深度强化学习中，代理由神经网络表示，神经网络直接与环境相互作用。它根据当前所处的环境，并根据对当前的状态和过去的经验，决定其行动（如移动左，右等）。然后，根据其所采取的行动，收到奖励。奖励金额决定了解决给定问题所采取行动的质量（例如学习如何行走）。代理人的目标是学习采取行动在任何特定情况下，随着时间的推移最大化累积奖励。

2 马尔可夫决策过程

Markov决策过程（MDP）是一个离散时间的随机控制处理。MDP是我们迄今为止为AI代理的复杂环境建模的最佳方法。代理旨在解决的每个问题可以被认为是状态序列S1，S2，S3，... Sn（状态可以是例如Go /象棋板配置）。代理执行操作并从一个状态移动到另一个状态。在下文中，您将学习确定代理在任何给定情况下必须采取的操作的数学。

2.1 马尔可夫过程

甲马尔可夫过程是描述可能的状态序列，其中，当前状态仅依赖于先前的状态的随机模型。这也称为Markov Property。对于强化学习，这意味着AI代理的下一个状态仅取决于最后一个状态而不是之前的所有先前状态。

式1

马尔可夫过程是一个随机过程。这意味着从当前状态s 到下一个状态s'的转换只能以某个概率Pss '发生。在马尔可夫过程中，被告知左转的代理人将仅以例如0.998的特定概率离开。由可能性很小的环境来决定代理的最终结果。

式2

Pss '可以被认为是状态转移矩阵 P中的条目，其定义从所有状态 s到所有后继状态 s'的转移概率。

式3

2.2 马尔可夫奖励程序

马尔可夫奖励过程是元组<S,P,R>。这里R是代理人希望在状态s中获得的奖励。该过程的动机是，对于旨在实现某个目标（例如赢得国际象棋游戏）的AI代理，某些状态（游戏配置）在策略和赢得游戏的潜力方面比其他状态更有前途。

式4

需要关注的是总奖励Gt，它是代理人将在所有州的序列中获得的预期累积奖励。每个奖励都由所谓的折扣因子γ∈[0,1]加权。折扣奖励在数学上是方便的，因为它避免了循环马尔可夫过程中的无限回报。除了折扣因素意味着我们未来越多，奖励变得越不重要，因为未来往往是不确定的。如果奖励是金融奖励，立即奖励可能比延迟奖励获得更多利息。除了动物/人类行为表明喜欢立即奖励。

式5

2.3 价值功能

另一个重要的概念是价值函数v（s）之一。值函数将值映射到每个状态s。状态s的值被定义为AI代理在状态s中开始其进展时将获得的预期总奖励。

式6

值函数可以分解为两部分：

• 代理接收的直接奖励R（t + 1）处于状态s
• 状态s之后的下一状态的贴现值v(s(t+1))

式7

图5

3.贝尔曼方程

3.1 马尔可夫奖励过程的Bellman方程

分解后的值函数(式8)也称为马尔可夫奖赏过程的Bellman方程。该函数可以在节点图中可视化(图6)，从状态s可以获得v(s)。在状态s中，我们有特定的概率Pss '到下一个状态s中结束。在这种情况下，我们有两个可能的状态。为了获得价值v(s)，我们可以将下一状态的v(s')乘以概率Pss‘，然后求和，再加上现阶段的直接奖励状态v(s)。

式8

图6

式9

3.2 马尔可夫决策过程 - 定义

马尔可夫决策过程是马尔可夫奖励过程的决策。马尔可夫决策过程由一组元组<S，A，P，R>描述，A是代理可以在状态s中采取的一组有限的可能动作。因此，现阶段s的及时奖励R也依赖于现阶段所采取的行动a（式10）。

式10

3.3 政策

在这一点上，我们将讨论代理如何决定在特定状态下必须采取哪些行动。这由所谓的政策π（式11）决定。从数学角度讲，政策是对给定的所有行动的分配。策略确定从状态s到代理必须采取的操作a的映射。

式11

该策略导致状态值函数v(s)的新定义（式12），我们现在将其定义为从状态s开始的预期返回，然后遵循策略π。

式12

3.4 行动价值功能

除状态值函数之外的另一个重要功能是所谓的动作值函数q(s,a)（式13）。动作值函数是我们通过从状态s开始，采取行动a然后遵循策略π获得的预期回报。请注意，对于状态s，q（s，a）可以采用多个值，因为代理可以在状态s中执行多个操作。Q(s,a)的计算是通过神经网络实现的。由于状态s作为输入，网络计算该状态下每个可能动作的质量作为标量（图7）。更高的质量意味着在给定目标方面采取更好的行动。

图7

行动价值函数告诉我们在特定状态下采取特定行动有多好。

式13

以前，状态值函数v（s）可以分解为以下形式：

式14

相同的分解可以应用于动作值函数：

式15

在这一点上，我们讨论v（s）和q（s，a）如何相互关联。这些函数之间的关系可以在图中再次可视化：

图8

在这个例子中处于状态s允许我们采取两种可能的动作a。根据定义，在特定状态下采取特定动作会给我们动作值q(s，a)。值函数v（s）是在状态s（式16）中采取动作a的概率加权的可能q(s，a)的总和（其不是策略π除外）。

式16

现在让我们考虑图9中的相反情况。二叉树的根现在是一个我们选择采取特定动作的状态。请记住，马尔可夫过程是随机的。采取行动并不意味着您将以100％的确定性结束您想要的目标。严格地说，你必须考虑在采取行动后最终进入其他状态的概率。在采取行动后，这个特殊的情况下，一个你可以在两个不同的下一个状态结束了S'：

图9

要获得动作值，您必须采用由概率Pss'加权的贴现状态值，以最终处于所有可能的状态（在这种情况下仅为2）并添加即时奖励：

式17

现在我们知道了这些函数之间的关系，我们可以将式17中的v(s)带入式16中，从而获得式18。即当前q(s,a)和下一个动作值q(s',a')之间存在递归关系。

式18

这种递归关系可以再次在二叉树中可视化（图10）。我们从q(s,a)开始，以一定概率Pss'结束在下一个状态s'，我们可以用概率π采取动作a'，我们以动作值q结束(s', a')。为了获得q(s,a)，我们必须在树中上升并整合所有概率，如公式18所示。

图10

3.5最优政策

深度强化学习中最重要的主题是找到最优的动作-值函数q*。查找q*表示代理确切地知道任何给定状态下的动作的质量。此外，代理商可以决定必须采取哪种行动的质量。让我们定义q*的意思。最佳的动作值功能是遵循最大化动作值的策略的功能：

式19

为了找到最好的策略，我们必须在q（s，a）上最大化。最大化意味着我们只选择q（s，a）具有最高值的所有可能动作中的动作a。这为最优策略π产生以下定义：

式20

3.6 Bellman最优性方程

可以将最优策略的条件插入到式18中。因此为我们提供了Bellman最优性方程：

式21

如果AI代理可以解决这个等式，那么它基本上意味着解决了给定环境中的问题。代理人在任何给定的状态或情况下都知道关于目标的任何可能行动的质量并且可以相应地表现。

微信群&交流合作