马尔可夫决策过程

在二十世纪初，数学家 Andrey Markov 研究了没有记忆的随机过程，称为马尔可夫链。这样的过程具有固定数量的状态，并且在每个步骤中随机地从一个状态演化到另一个状态。它从状态S演变为状态S'的概率是固定的，它只依赖于(S, S')对，而不是依赖于过去的状态（系统没有记忆）。

图 16-7 展示了一个具有四个状态的马尔可夫链的例子。假设该过程从状态S0开始，并且在下一步骤中有 70% 的概率保持在该状态不变中。最终，它必然离开那个状态，并且永远不会回来，因为没有其他状态回到S0。如果它进入状态S1，那么它很可能会进入状态S2（90% 的概率），然后立即回到状态S1（以 100% 的概率）。它可以在这两个状态之间交替多次，但最终它会落入状态S3并永远留在那里（这是一个终端状态）。马尔可夫链可以有非常不同的应用，它们在热力学、化学、统计学等方面有着广泛的应用。

图16-7

马尔可夫决策过程最初是在 20 世纪 50 年代由 Richard Bellman 描述的。它们类似于马尔可夫链，但有一个连结：在状态转移的每一步中，一个智能体可以选择几种可能的动作中的一个，并且转移概率取决于所选择的动作。此外，一些状态转移返回一些奖励（正或负），智能体的目标是找到一个策略，随着时间的推移将最大限度地提高奖励。

例如，图 16-8 中所示的 MDP 在每个步骤中具有三个状态和三个可能的离散动作。如果从状态S0开始，随着时间的推移可以在动作A0、A1或A2之间进行选择。如果它选择动作A1，它就保持在状态S0中，并且没有任何奖励。因此，如果愿意的话，它可以决定永远呆在那里。但是，如果它选择动作A0，它有 70% 的概率获得 10 奖励，并保持在状态S0。然后，它可以一次又一次地尝试获得尽可能多的奖励。但它将在状态S1中结束这样的行为。在状态S1中，它只有两种可能的动作：A0或A1。它可以通过反复选择动作A1来选择停留，或者它可以选择动作A2移动到状态S2并得到 -50 奖励。在状态S3中，除了采取行动A1之外，别无选择，这将最有可能引导它回到状态S0，在途中获得 40 的奖励。通过观察这个 MDP，你能猜出哪一个策略会随着时间的推移而获得最大的回报吗？在状态S0中，清楚地知道A0是最好的选择，在状态S3中，智能体别无选择，只能采取行动A1，但是在状态S1中，智能体否应该保持不动（A0）或通过火（A2），这是不明确的。

图16-8

Bellman 找到了一种估计任何状态S的最佳状态值的方法，他提出了V(s)，它是智能体在其采取最佳行为达到状态s后所有衰减未来奖励的总和的平均期望。他表明，如果智能体的行为最佳，那么贝尔曼最优性公式适用（见公式 16-1）。这个递归公式表示，如果智能体最优地运行，那么当前状态的最优值等于在采取一个最优动作之后平均得到的奖励，加上该动作可能导致的所有可能的下一个状态的期望最优值。

图E16-1

其中：

T为智能体选择动作a时从状态s到状态s'的概率
R为智能体选择以动作a从状态s到状态s'的过程中得到的奖励
$\gamma$ 为衰减率

这个等式直接引出了一种算法，该算法可以精确估计每个可能状态的最优状态值：首先将所有状态值估计初始化为零，然后用数值迭代算法迭代更新它们（见公式 16-2）。一个显著的结果是，给定足够的时间，这些估计保证收敛到最优状态值，对应于最优策略。

图E16-2

其中：

是在k次算法迭代对状态s的估计

该算法是动态规划的一个例子，它将了一个复杂的问题（在这种情况下，估计潜在的未来衰减奖励的总和）变为可处理的子问题，可以迭代地处理（在这种情况下，找到最大化平均报酬与下一个衰减状态值的和的动作）

了解最佳状态值可能是有用的，特别是评估策略，但它没有明确地告诉智能体要做什么。幸运的是，Bellman 发现了一种非常类似的算法来估计最优状态-动作值（state-action values），通常称为 Q 值。状态行动(S, A)对的最优 Q 值，记为Q(s, a)，是智能体在到达状态S，然后选择动作A之后平均衰减未来奖励的期望的总和。但是在它看到这个动作的结果之前，假设它在该动作之后的动作是最优的。

下面是它的工作原理：再次，通过初始化所有的 Q 值估计为零，然后使用 Q 值迭代算法更新它们（参见公式 16-3）。

图E16-3

一旦你有了最佳的 Q 值，定义最优的策略π*(s)，它是平凡的：当智能体处于状态S时，它应该选择具有最高 Q 值的动作，用于该状态： $\pi ^ * (s) =\arg \max_a Q^*(s, a)$ 。

让我们把这个算法应用到图 16-8 所示的 MDP 中。首先，我们需要定义 MDP：

nan=np.nan  #  代表不可能的动作 
T = np.array([  #  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], [nan, nan, nan], [0.0, 0.0, 1.0]],       
    [[nan, nan, nan], [0.8, 0.1, 0.1], [nan, nan, nan]],    ]) 
R = np.array([  #  shape=[s, a, s']        
    [[10., 0.0, 0.0], [0.0, 0.0, 0.0], [0.0, 0.0, 0.0]],        
    [[10., 0.0, 0.0], [nan, nan, nan], [0.0, 0.0, -50.]],        
    [[nan, nan, nan], [40., 0.0, 0.0], [nan, nan, nan]],    ]) 
possible_actions = [[0, 1, 2], [0, 2], [1]]

让我们运行 Q 值迭代算法

Q = np.full((3, 3), -np.inf)  #  -inf 对应着不可能的动作 
for state, actions in enumerate(possible_actions):    
    Q[state, actions] = 0.0  #  对所有可能的动作初始化为0.0
learning_rate = 0.01 
discount_rate = 0.95 
n_iterations = 100
for iteration in range(n_iterations):   
    Q_prev = Q.copy()    
    for s in range(3):        
        for a in possible_actions[s]:            
            Q[s, a] = np.sum([T[s, a, sp] * (R[s, a, sp] + discount_rate * np.max(Q_prev[sp]))  
            for sp in range(3)])

结果的 Q 值类似于如下：

>>> Q 
array([[ 21.89498982,  20.80024033,  16.86353093],       
        [  1.11669335,         -inf,   1.17573546],       
        [        -inf,  53.86946068,         -inf]]) 
>>> np.argmax(Q, axis=1)  #  每一状态的最优动作
array([0, 2, 1])

这给我们这个 MDP 的最佳策略，当使用 0.95 的衰减率时：在状态S0选择动作A0，在状态S1选择动作A2（通过火焰！）在状态S2中选择动作A1（唯一可能的动作）。有趣的是，如果你把衰减率降低到 0.9，最优的策略改变：在状态S1中，最好的动作变成A0（保持不变；不通过火）。这是有道理的，因为如果你认为现在比未来更重要，那么未来奖励的前景是不值得立刻经历痛苦的。