马尔可夫决策过程

在 20世纪初，数学家安德烈马尔科夫研究了无记忆的随机过程，称为 马尔可夫链。这样的过程具有固定数量的状态，并且在每一步都从一种状态随机演化到另一种状态。它从状态s演化到状态s '的概率是固定的，它只取决于对（s , s '），而不取决于过去的状态（这就是我们说系统没有记忆的原因）。

图 18-7显示了具有四个状态的马尔可夫链的示例。

图 18-7。马尔可夫链的例子

假设该过程从状态s 0开始，并且有 70% 的机会在下一步保持该状态。最终它必然会离开那个状态并且永远不会回来，因为没有其他状态指向s 0。如果它进入状态s 1，那么它很可能进入状态s 2（90% 的概率），然后立即返回状态s 1（100% 的概率）。它可能会在这两种状态之间交替多次，但最终会落入状态s 3并保持永远存在（这是一个终端状态）。马尔可夫链可以有非常不同的动力学，它们被大量用于热力学、化学、统计学等等。

1950 年代，Richard Bellman 首次描述了马尔可夫决策过程。12它们类似于马尔可夫链，但有一点不同：在每一步，代理可以选择几种可能的动作之一，而转移概率取决于所选动作。此外，一些状态转换会返回一些奖励（正面或负面），并且代理的目标是找到一种策略，随着时间的推移将奖励最大化。

例如，图 18-8 中表示的 MDP具有三种状态（用圆圈表示）和每一步最多三个可能的离散动作（用菱形表示）。

图 18-8。马尔可夫决策过程示例

如果它从状态s 0开始，代理可以在动作a 0、a 1或a 2之间进行选择。如果它选择动作a 1，则它只是确定地保持在状态s 0 中，并且没有任何奖励。因此，如果它愿意，它可以决定永远留在那里。但是如果它选择动作a 0，它有 70% 的概率获得 +10 的奖励并保持状态s 0。然后它可以一次又一次地尝试以获得尽可能多的奖励，但在某一时刻，它最终会改为状态s 1。在状态s1它只有两个可能的动作：一个0或一个2。它可以选择通过重复选择动作a 0来保持原状，也可以选择继续前进到状态s 2并获得 –50 的负奖励（哎哟）。在状态s 2 中，它别无选择，只能采取行动a 1，这很可能会导致它回到状态s 0，并在途中获得 +40 的奖励。你得到了图片。通过查看这个 MDP，你能猜出随着时间的推移哪种策略会获得最多的回报吗？在状态s 0很明显，动作a 0是最佳的选择，并且在状态小号2代理别无选择，只能采取行动一个1，但在状态小号1这不是明摆着的代理是否应该留在原地（一0）或经火（一2） .

贝尔曼发现以估计的方式最佳状态值的任何状态小号，注意到V *（小号），这是所有贴现的未来的总和奖励代理可以平均预期其达到状态之后小号，假定它的作用最佳。他表明，如果代理人采取最佳行动，那么该贝尔曼最优性方程适用（见公式18-1）。这个递归方程表示，如果智能体采取最优行动，那么当前状态的最优值等于它在采取一个最优行动后平均得到的奖励，加上该行动可能导致的所有可能的下一个状态的预期最优值到。

在这个等式中：

• T ( s , a , s ') 是从状态s到状态s '的转移概率，假设智能体选择了动作a。例如，在图 18-8 中，T ( s 2 , a 1 , s 0 ) = 0.8。

• R ( s , a , s ') 是智能体从状态s到状态s '时获得的奖励，假设智能体选择了动作a。例如，在图 18-8 中，R ( s 2 , a 1 , s 0 ) = +40。

• γ是贴现因子。

这个方程直接导致了一个算法，可以精确估计每个可能状态的最佳状态值：首先将所有状态值估计初始化为零，然后迭代更新它们使用值迭代算法（参见公式 18-2）。一个显着的结果是，如果有足够的时间，这些估计可以保证收敛到与最优策略相对应的最优状态值。

在该方程中，V ķ（小号）为推定值状态的小号在ķ次的迭代算法。

会心最佳状态值可能很有用，特别是在评估策略时，但它不会为我们提供代理的最佳策略。幸运的是，Bellman 找到了一种非常相似的算法来估计最佳状态-动作值，通常称为Q-Values（质量值）。状态-动作对 ( s , a )的最优 Q 值，记为Q *( s , a )，是智能体在达到状态s并选择动作a后平均可以期望的折扣未来奖励的总和，但是在它看到这个动作的结果之前，假设它在那个动作之后采取了最佳行动。

这里它是如何工作的：再一次，您首先将所有 Q 值估计值初始化为零，然后使用Q 值迭代算法更新它们（参见公式 18-3）。

一旦你有了最优 Q 值，定义最优策略，记为π *( s )，是微不足道的：当代理处于状态s 时，它应该为该状态选择具有最高 Q 值的动作：${\mathrm{<font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;"><font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;">\pi </font></font>}}^{<font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;"><font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;">*</font></font>}<font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;"><font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;">(</font></font>\mathrm{<font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;"><font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;">秒</font></font>}<font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;"><font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;">)</font></font><font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;"><font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;">=</font></font>\underset{\mathrm{<font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;"><font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;">一种</font></font>}}{<font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;"><font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;">最大参数</font></font>} {\mathrm{<font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;"><font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;">问</font></font>}}^{<font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;"><font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;">*</font></font>}<font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;"><font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;">(</font></font>\mathrm{<font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;"><font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;">秒</font></font>}<font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;"><font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;">,</font></font>\mathrm{<font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;"><font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;">一种</font></font>}<font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;"><font\; style="box-sizing:\; border-box;\; vertical-align:\; inherit;">)</font></font>$.

让我们将此算法应用于图 18-8 中表示的 MDP 。首先，我们需要定义 MDP：

transition_probabilities = [ # shape=[s, a, s']
        [[0.7, 0.3, 0.0], [1.0, 0.0, 0.0], [0.8, 0.2, 0.0]],
        [[0.0, 1.0, 0.0], None, [0.0, 0.0, 1.0]],
        [None, [0.8, 0.1, 0.1], None]]
rewards = [ # shape=[s, a, s']
        [[+10, 0, 0], [0, 0, 0], [0, 0, 0]],
        [[0, 0, 0], [0, 0, 0], [0, 0, -50]],
        [[0, 0, 0], [+40, 0, 0], [0, 0, 0]]]
possible_actions = [[0, 1, 2], [0, 2], [1]]

例如，要知道在执行动作a 1后从s 2到s 0的转移概率，我们将查找（即 0.8）。同样，要获得相应的奖励，我们会向上查找（即+40）。为了获得s 2中可能的动作列表，我们将查找（在这种情况下，只有动作a 1是可能的）。接下来，我们必须将所有 Q 值初始化为 0（除了不可能的操作，我们将 Q 值设置为 –∞）：transition_probabilities[2][1][0]rewards[2][1][0]possible_actions[2]

Q_values = np.full((3, 3), -np.inf) # -np.inf for impossible actions
for state, actions in enumerate(possible_actions):
    Q_values[state, actions] = 0.0  # for all possible actions

现在让我们运行 Q 值迭代算法。它将公式 18-3重复应用于所有 Q 值，针对每个状态和每个可能的操作：

gamma = 0.90 # the discount factor

for iteration in range(50):
    Q_prev = Q_values.copy()
    for s in range(3):
        for a in possible_actions[s]:
            Q_values[s, a] = np.sum([
                    transition_probabilities[s][a][sp]
                    * (rewards[s][a][sp] + gamma * np.max(Q_prev[sp]))
                for sp in range(3)])

就是这样！生成的 Q 值如下所示：

>>> Q_values
array([[18.91891892, 17.02702702, 13.62162162],
       [ 0.        ,        -inf, -4.87971488],
       [       -inf, 50.13365013,        -inf]])

例如，当代理处于状态s 0并且它选择动作a 1 时，折扣未来奖励的预期总和约为 17.0。

对于每个状态，让我们看看具有最高 Q 值的动作：

>>> np.argmax(Q_values, axis=1) # optimal action for each state
array([0, 0, 1])

当使用 0.90 的折扣因子时，这为我们提供了此 MDP 的最佳策略：在状态s 0 中选择动作a 0；在状态s 1 中选择动作a 0（即原地不动）；并且在状态s 2 中选择动作a 1（唯一可能的动作）。有趣的是，如果我们加大折扣系数0.95，最优的政策变化：在状态小号1最佳动作变成一个2（经火！）。这是有道理的，因为你越重视未来的回报，你现在就越愿意为了未来的幸福而忍受一些痛苦。