剖析强化学习 - 第二部分

小灰灰 2022-05-26 23:06 336阅读 0赞

作者：Massimiliano Patacchiola

欢迎来到**剖析强化学习**系列的第二部分。如果您顺利完成了[第一部分，][Link 1]那么恭喜！您学会了强化学习的基础，即**动态编程**方法。正如我在第一部分中所承诺的那样，第二部分将深入进行无模型强化学习（用于预测和控制），对**Monte Carlo（MC）**方法进行概述。这篇文章与[第一][Link 1][部分][Link 1]（弱）相关，我将使用相同的术语，例子和数学符号。在这篇文章中，我将结合Russel和Norvig在“ **人工智能：一种现代方法”**和**Sutton和Barto**提出的传统**强化学习**文章中一些想法。我特别关注前者的第21章（第二版）和后者的第5章（第一版）。此外，您可以参加David Silver课程的[讲座][Link 2]4和[讲座][Link 3]5。对于开放版本的书籍，请查看资源部分。

![20180407213923848][]

好吧，现在以前一部分的思路，我将更进一步分析所有的概念。

## 超越动态编程 ##

[在第一篇文章中，][Link 1]我向您展示了计算最优策略的两个主要算法，即**值迭代**和**策略迭代**。我们将环境建模为马尔可夫决策过程（MDP），使用转移模型来描述从一个状态转移到另一个状态的概率。转移模型存储在一个矩阵`T`中，用于查找效用函数U\*和最佳策略π\*。在这里，我们必须**小心数学符号**，在Sutton和Barto的书中，效用函数被称为价值函数或状态值函数，并用字母V表示。为了保持一致，我将使用Russel和Norvig的符号，它使用字母U表示效用函数。这两个符号具有相同的含义，他们将状态的价值定义为从该状态开始期望的累积未来的折扣奖励。读者应习惯不同的符号。

现在我想对**无模型强化学习**，特别是**被动**和**主动**强化学习给出一个合适的定义。在无模型强化学习中，我们首先丢弃的是**转移模型**，实际上，无模型名称就代表无转移模型；我们丢弃的第二个就是**奖励函数** R(s)，即给予Agent与特定相关状态的奖励。在被动方法中，我们有一个**策略**π，Agent可以使用它在环境中移动，在状态s下Agent总是使用策略π给出的动作a。在**被动**强化学习中Agent的目标是学习效用函数 Uπ(s)，Sutton和Barto称这种MC场景为**预测**，在环境中移动时可以估计最佳策略。在这种情况下，我们正处于一个**积极的**情况，并且使用Sutton和Burto的话来说，我们将会使用MC来进行**控制**评估。在这里，我将再用在第一篇文章中使用**清洁机器人**的例子，但使用不同的设置。

![20180407213949504][]

该机器人处于4x3世界中，具有未知的转移模型，有关环境的唯一信息是**状态的可用性**。由于机器人没有奖励功能，因此不知道哪个状态包含充电站（\+1）以及哪个状态包含楼梯（\-1）。只有在被动的情况下，机器人才能遵循在世界中移动的**策略**。最后是**转换模型**，因为机器人不知道每次动作后会发生什么，所以只能给每个可能的结果提供未知的概率。总而言之，在**被动的**情况下，这就是我们所拥有的：

1.策略π

2.一组可能的状态：S=\{ s0,s1,...,sm\}

3.初始状态：s0

4. 可能的动作集合：A=\{ a0,a1,...,an\}

5.策略π

在被动强化学习中，我们的**目标**是使用可用的信息来**估计效用函数**。怎么做？

机器人可以做的第一件事是**估算转移模型**，在环境中移动并跟踪动作被正确执行的次数。一旦转移模型可用，机器人就可以使用值迭代或策略迭代来获得效用函数。从这个意义上说，有不同的技术可以找出利用贝叶斯规则和最大似然估计的转移模型。Russel和Norvig在第21.2.2章（贝叶斯强化学习）中提到了这些技术，这种方法的问题应该是显而易见的：**估算转移模型的值可能是昂贵的**。在我们的3x4世界中，它意味着估计一个12x12x4（状态x状态x操作）表格的值，此外某些动作和某些状态可能极不可能达到，因此难以估计转移表格中的值。在这里，我将关注另一种直接估算效用函数而不使用转移模型的技术，就是下面要谈论的**蒙特卡罗方法**。

## 蒙特卡洛方法 ##

蒙特卡罗（MC）方法在1930年首次由正在研究中子扩散的[Enrico Fermi][]使用。Fermi没有发表任何内容，现代版本归功于1940年代在洛斯阿拉莫斯发明它的[Stanislaw Ulam][]。MC背后的想法很简单：使用随机性来解决问题，例如，可以使用MC来估计多维定积分，这种技术称为[MC积分][MC]。在人工智能中，我们可以使用MC树搜索来找到游戏中的最佳动作。[DeepMind AlphaGo][]使用MC树搜索结合卷积网络和深度强化学习击败了围棋世界冠军李世石。在本系列的后面，我们会探索它如何成为可能。**MC方法优于动态规划方法**的**优点**如下：

1.MC允许**直接从**与环境的**交互中**学习最佳行为；

2.**将** MC方法**集中在状态的****小子集**上很容易且很有效；

3.MC可以用于**仿真**（样本模型）

在这篇文章中，我将分析前两点，**第三点**不太直观。在许多应用中，很容易模拟episode，但使用动态编程技术构建所需的转移模型可能非常困难。在所有这些情况下，都由MC方法所主导。

现在让我们回到**清洁机器人**，看看在这种情况下应用MC方法意味着什么。像往常一样，机器人从状态（1，1）开始，并遵循其内部策略，在每一步都会记录获得的奖励，并保存所有访问状态的历史记录，直到达到终止状态。我们把从起始状态到终止状态的状态序列称为**episode**。现在让我们假设我们的机器人记录了以下三个episode：

![20180407214022859][]

机器人遵循其内部策略，但**未知的转移模型扰乱了轨迹**从而导致不好的状态。在第一和第二个episode中，机器人在一些波动之后最终达到终止状态，获得了积极的奖励。在第三个episode中，机器人沿着错误的路径移动到达楼梯并落下（奖励：\-1.0）。以下是这三个episode的另一种表现形式，如果您正在阅读该文章的pdf版本，则很有用。

![20180407214044655][]

在episode中每次发生的状态都称为**访问**(**visit)**。访问的概念很重要，因为它允许定义两种不同的MC方法：

1.**首次访问(First-Visit) MC**：Uπ(s)被定义为在一组episode中*首次访问*状态s的平均奖励。

2.**每次访问(Every-Visit) MC**：Uπ(s)被定义为在一组episode中*所有访问*状态s的平均奖励。

我将**只关注这篇文章中的首次访问****MC方法**。**回报****(return)**是什么意思？回报是折扣奖励的总和。当我介绍Bellman方程和状态的历史效用时，已经在第一篇文章中提出了回报。

![20180407215606248][]

公式没有新东西，其中包括折扣系数γ，奖励函数R(s)和到达时间t的状态St。我们可以计算第一个episode的状态（1,1）的回报，γ=0.9，如下所示：

![2018040721562543][]

第一个episode的回报是0.27，遵循相同的过程，我们在第二个episode中得到相同的结果，对于第三个episode，我们得到了不同的回报\-0.79。三个episode之后，我们拿出了三种不同的回报：0.27,0.27,0.79。**如何使用回报来估算效用？**现在我将介绍MC方法中使用的核心方程，它给出了策略π赋予一个状态的效用：

![20180407215703512][]

如果将此等式与用于计算回报的等式进行比较，则只会看到一个差异：为了获得效用函数，我们可以**对回报**计算[**预期**][Link 4]。是的，为了找到一个状态的效用，我们需要计算该状态回报的期望值。在我们的例子中，经过三个episode以后，状态（1,1）的近似效用是：（0.27 + 0.27-0.79）/3=-0.08。然而，仅基于三个episode的估计是不准确的，我们需要更多episode才能获得真正的价值。为什么我们需要更多episode？

**这时该MC登场了**。我们定义S t是一个[离散的随机变量][Link 5]，它能够以一定的概率来假设所有可用的状态，每当我们的机器人进入某个状态就好像我们为随机变量St选择一个值，对于每个episode的每个状态，我们可以计算回报并将其存储在列表中。重复这个过程很多次都可以**确保收敛到真正的效用**。这是如何实现的呢？这是一个被称为[大数定律的][Link 6]著名定理的结果。了解大数定律至关重要，滚动六面骰子会产生数字1,2,3,4,5或6其中的一个，每个具有相同的概率，[期望][Link 4]是3.5，可以作为算术平均值来计算：（1 + 2 + 3 + 4 + 5+ 6）/6=3.5。使用MC方法，我们可以获得相同的值，让我们在Python中完成：

import numpy as np
    
    # Trowing a dice for N times and evaluating the expectation
    dice = np.random.randint(low=1, high=7, size=3)
    print("Expectation (rolling 3 times): " + str(np.mean(dice)))
    dice = np.random.randint(low=1, high=7, size=10)
    print("Expectation (rolling 10 times): " + str(np.mean(dice)))
    dice = np.random.randint(low=1, high=7, size=100)
    print("Expectation (rolling 100 times): " + str(np.mean(dice)))
    dice = np.random.randint(low=1, high=7, size=1000)
    print("Expectation (rolling 1000 times): " + str(np.mean(dice)))
    dice = np.random.randint(low=1, high=7, size=100000)
    print("Expectation (rolling 100000 times): " + str(np.mean(dice)))

Expectation (rolling 3 times): 4.0
    Expectation (rolling 10 times): 2.9
    Expectation (rolling 100 times): 3.47
    Expectation (rolling 1000 times): 3.481
    Expectation (rolling 100000 times): 3.49948

正如你所看到的，期望的估计收敛于3.5的真实值。我们在MC强化学习中所做的是完全一样的，但在这种情况下，我们希望**根据每个episode的回报**来**估计每个状态的效用**。对于骰子，我们考虑更多的episode会产生更准确地估计。

## Python实现 ##

像往常一样，我们将使用Python实现该算法。我写了一个类`GridWorld`，它包含在`gridworld.py`模块中，在[我的GitHub存储库中][GitHub]可以找到。使用这个类可以创建任意大小的网格世界并添加障碍物和终止状态。根据特定的策略，清洁机器人将在网格世界中移动，让我们来到4x3世界：

import numpy as np
    from gridworld import GridWorld
    
    # Declare our environmnet variable
    # The world has 3 rows and 4 columns
    env = GridWorld(3, 4)
    # Define the state matrix
    # Adding obstacle at position (1,1)
    # Adding the two terminal states
    state_matrix = np.zeros((3,4))
    state_matrix[0, 3] = 1
    state_matrix[1, 3] = 1
    state_matrix[1, 1] = -1
    # Define the reward matrix
    # The reward is -0.04 for all states but the terminal
    reward_matrix = np.full((3,4), -0.04)
    reward_matrix[0, 3] = 1
    reward_matrix[1, 3] = -1
    # Define the transition matrix
    # For each one of the four actions there is a probability
    transition_matrix = np.array([[0.8, 0.1, 0.0, 0.1],
                                  [0.1, 0.8, 0.1, 0.0],
                                  [0.0, 0.1, 0.8, 0.1],
                                  [0.1, 0.0, 0.1, 0.8]])
    # Define the policy matrix
    # 0=UP, 1=RIGHT, 2=DOWN, 3=LEFT, NaN=Obstacle, -1=NoAction
    # This is the optimal policy for world with reward=-0.04
    policy_matrix = np.array([[1,      1,  1,  -1],
                              [0, np.NaN,  0,  -1],
                              [0,      3,  3,   3]])
    # Set the matrices 
    env.setStateMatrix(state_matrix)
    env.setRewardMatrix(reward_matrix)
    env.setTransitionMatrix(transition_matrix)

用我们的例子的属性使用几行代码定义了一个网格世界。如我们在第一篇文章中看到的那样，该策略是奖励为\-0.04的最佳策略，现在开始重置环境（将机器人移动到起始位置）并使用`render()`方法来显示世界。

#Reset the environment
    observation = env.reset()
    #Display the world printing on terminal
    env.render()

运行上面的代码片段，会在屏幕上显示以下内容。

-  -  -  * 
     -  #  -  * 
     ○  -  -  -

我使用\-代表自由位置，\*代表两个终止位置，\#代表障碍，○代表机器人。现在我们可以使用for循环运行一个episode：

for _ in range(1000):
        action = policy_matrix[observation[0], observation[1]]
        observation, reward, done = env.step(action)
        print("")
        print("ACTION: " + str(action))
        print("REWARD: " + str(reward))
        print("DONE: " + str(done))
        env.render()
        if done: break

考虑到转移矩阵和策略，脚本的最可能输出将是这样的：

-  -  -  *      -  -  -  *      ○  -  -  *
     -  #  -  *      ○  #  -  *      -  #  -  *
     ○  -  -  -      -  -  -  -      -  -  -  -
    
    
     -  ○  -  *      -  -  ○  *      -  -  -  ○
     -  #  -  *      -  #  -  *      -  #  -  *
     -  -  -  -      -  -  -  -      -  -  -  -

您可以在[GitHub存储库中][GitHub]找到完整的示例。如果您熟悉[OpenAI Gym，][OpenAI Gym]您会发现我的代码有很多相似之处，我用同样的结构实现了相同的方法`step()` `reset()`和`render()`，其中`step()`方法在t + 1时向前移动并返回**奖励**，**观察**（机器人的位置）和一个变量，这个变量称为`done``，`当为`True`时表明episode完成（机器人到达终止状态）。

现在我们有了所需的全部**MC方法**。这里我将使用折扣因子γ = 0.999，最优策略π \*和上一篇文章中使用的相同的转移模型。请记住，使用当前的转移模型，只有80％的情况下，机器人才会朝着想要的方向前进。首先我写了一个函数来估计回报率：

def get_return(state_list, gamma):
        counter = 0
        return_value = 0
        for visit in state_list:
            reward = visit[1]
            return_value += reward * np.power(gamma, counter)
            counter += 1
        return return_value

该函数`get_return()`将包含元组`(position, reward)`的列表和折扣因子`gamma`作为输入，输出是表示对应于该action列表的回报。我们将在下面的循环中使用`get_return()`函数，以便获得每个episode的回报并估算效用。以下部分至关重要，我添加了许多注释以使其更具可读性。

# Defining an empty utility matrix
    utility_matrix = np.zeros((3,4))
    # init with 1.0e-10 to avoid division by zero
    running_mean_matrix = np.full((3,4), 1.0e-10) 
    gamma = 0.999 #discount factor
    tot_epoch = 50000
    print_epoch = 1000
    
    for epoch in range(tot_epoch):
        #Starting a new episode
        episode_list = list()
        #Reset and return the first observation
        observation= env.reset(exploring_start=False)
        for _ in range(1000):
            # Take the action from the action matrix
            action = policy_matrix[observation[0], observation[1]]
            # Move one step in the environment and get obs and reward
            observation, reward, done = env.step(action)
            # Append the visit in the episode list
            episode_list.append((observation, reward))
            if done: break
        # The episode is finished, now estimating the utilities
        counter = 0
        # Checkup to identify if it is the first visit to a state
        checkup_matrix = np.zeros((3,4))
        # This cycle is the implementation of First-Visit MC.
        # For each state stored in the episode list it checks if it
        # is the first visit and then estimates the return.
        for visit in episode_list:
            observation = visit[0]
            row = observation[0]
            col = observation[1]
            reward = visit[1]
            if(checkup_matrix[row, col] == 0):
                return_value = get_return(episode_list[counter:], gamma)
                running_mean_matrix[row, col] += 1
                utility_matrix[row, col] += return_value
                checkup_matrix[row, col] = 1
            counter += 1
        if(epoch % print_epoch == 0):
            print("Utility matrix after " + str(epoch+1) + " iterations:") 
            print(utility_matrix / running_mean_matrix)
    
    #Time to check the utility matrix obtained
    print("Utility matrix after " + str(tot_epoch) + " iterations:")
    print(utility_matrix / running_mean_matrix)

执行此脚本每1000次迭代打印效用矩阵的估计值：

Utility matrix after 1 iterations:
    [[ 0.59184009  0.71385957  0.75461418  1.        ]
     [ 0.55124825  0.          0.87712296  0.        ]
     [ 0.510697    0.          0.          0.        ]]
    
    Utility matrix after 1001 iterations:
    [[ 0.81379324  0.87288388  0.92520101  1.        ]
     [ 0.76332603  0.          0.73812382 -1.        ]
     [ 0.70553067  0.65729802  0.          0.        ]]
    
    Utility matrix after 2001 iterations:
    [[ 0.81020502  0.87129531  0.92286107  1.        ]
     [ 0.75980199  0.          0.71287269 -1.        ]
     [ 0.70275487  0.65583747  0.          0.        ]]
    
    
    ...
    
    Utility matrix after 50000 iterations:
    [[ 0.80764909  0.8650596   0.91610018  1.        ]
     [ 0.7563441   0.          0.65231439 -1.        ]
     [ 0.69873614  0.6478315   0.          0.        ]]

正如你所看到的效用值越来越精确，在趋近于无限时它收敛于真正的价值。在第一篇文章中，我们已经使用动态编程技术找到了这个特定网格世界的效用值，在这里，我们可以比较用MC获得的结果和用动态编程获得的结果：

![20180407221321779][]

如果你观察两个效用矩阵，你会注意到许多相似之处，但有两个重要的区别，状态（4,1）和（3,1）的效用估计为零。这可以被认为是MC方法的一个局限性，同时也是其中一个优点。我们正在使用的策略，转移概率以及机器人总是从相同位置（左下角）开始的事实，导致这些状态的错误估计。**从状态（****1,1）开始，机器人将永远不会达到这些状态，**并且它不能估计相应的效用值。这确实是一个问题，因为我们无法估计这些值，但同时这也是一个优势，在一个非常大的网格世界中，**我们可以只为我们感兴趣的状态估算效用值，**以节省时间和资源，并只专注于世界的特定子空间。

我们怎么估计每个状态的价值？一种可能的解决方案称为**探索开始****(exploringstarts)，**包括使机器人从所有可用的状态开始探索，这确保所有状态将在无限次数的情况下被访问。为了使在我们的代码中实现探索开始，唯一要做的就是将reset()函数中的参数exploring\_strarts设置为True，如下所示：

observation = env.reset(exploring_start=True)

现在，每当新episode开始时，机器人将从随机位置开始。再次运行该脚本将导致以下估计值：

Utility matrix after 1 iterations:
    [[ 0.87712296  0.918041    0.959       1.        ]
     [ 0.83624584  0.          0.          0.        ]
     [ 0.          0.          0.          0.        ]]
    
    Utility matrix after 1001 iterations:
    [[ 0.81345829  0.8568502   0.91298468  1.        ]
     [ 0.76971062  0.          0.64240071 -1.        ]
     [ 0.71048183  0.65156625  0.62423942  0.3622782 ]]
    
    Utility matrix after 2001 iterations:
    [[ 0.80248079  0.85321     0.90835335  1.        ]
     [ 0.75558086  0.          0.64510648 -1.        ]
     [ 0.69689178  0.64712344  0.6096939   0.34484468]]
    
    ...
    
    Utility matrix after 50000 iterations:
    [[ 0.8077211   0.86449595  0.91575904  1.        ]
     [ 0.75630573  0.          0.65417382 -1.        ]
     [ 0.6989143   0.64707444  0.60495949  0.36857044]]

这一次我们得到了状态（4,1）和（3,1）的正确值。到现在为止，都是假设有一个策略，我们用这个策略来估计效用函数。当我们没有策略时该怎么办？在这种情况下，我们可以使用其他方法，Russel和Norvig 称此场景为**主动**强化学习。遵循Sutton和Barto的定义，我将称这种情况为**无****模型蒙特卡罗控制**估计。

## 蒙特卡罗控制 ##

用于控制（主动）的MC方法与用于预测（被动）的MC方法略有不同。从某种意义上说，MC控制问题更为现实，因为**我们需要估计未给出的策略**。MC用于控制的机制与我们在动态编程技术中使用的机制相同，在Sutton和Barto的书中，它被称为**广义策略迭代**或**GPI**。第一篇文章的**策略迭代算法**很好地解释了GPI。策略迭代允许找到每个状态的效用值，及最优策略π \*。我们在策略迭代中使用的方法包括两个步骤：

1.策略评价：U→Uπ

2.策略改进：π → greedy(U)

在**第一步**，使效用函数与当前策略（评估）保持一致；在**第二个步**，使策略π 对当前效用函数*贪婪*（改进）。这两个变化相互对立，为另一个创造一个移动中的目标，但他们一起合作使策略和价值函数的方法达到最优。

![20180407221352879][]

在第二步中，我们注意到一个新词：贪婪。**贪婪在这里是什么意思？**[贪婪算法][Link 7]使得在每一步选择局部最优。在我们的案例下，贪婪意味着为每个状态采取最高效用的动作，并用该动作更新策略。然而，仅仅局部线索通常不会导致最佳解决方案。例如，在以下案例的每一步选择最高效用会导致负的回报。

![20180407221416881][]

**贪婪策略如何工作？** 它的工作原理是使用随时间调整的效用函数来评估局部选择。一开始，Agent将遵循许多次优路径，但过了一段时间，效用将开始收敛到真实价值，贪婪策略将带来积极的回报。所有强化学习方法都可以用策略迭代的术语进行描述，更具体而言可以用GPI来描述，牢记GPI理念将使您轻松理解控制方法。为了充分理解MC控制方法，我必须介绍另一个主题，即Q函数。

## 动作价值和Q函数 ##

到目前为止，我们使用的函数U称为效用函数（又名价值函数，状态值函数）作为估计一个状态的效用（价值）的一种方式，更确切地说，我们使用Uπ(s)根据策略π估计一个状态s的价值。现在引入一个名为Q的新函数（又名action-value函数），定义如下：

![20180407221450449][]

如上式所述，Q函数根据策略π在状态s下采取动作a并返回该状态\-动作(state-action)对的效用。Q函数被定义为从s开始的预期回报，执行动作a随后遵循策略π。

**为什么我们需要MC方法中的函数Q？**在无模型强化学习中，各状态的效用不足以提议一个策略，必须明确估计每个动作的效用，因此MC控制方法的主要目标是估计函数Q\*。我之前对GPI的描述也适用于动作\-价值函数Q，估计最优动作\-价值函数与估计效用函数没有区别。**用于控制的首次访问****(first-visit)MC方法使用**第一次访问特定的**状态****-动作对评估**平均回报。我们必须使用状态\-动作对的术语来思考，而不是根据状态来思考。当我们估计效用函数U时我们将效用值存储在具有相同维度的矩阵中。这里我们需要一种**新的方式**来**表示状态\-值函数**Q，因为必须考虑动作。我们可以一行表示一个动作，一列表示一个状态。设想将我们4x3网格世界的所有12个状态放在一行中，然后为所有四种可能动作（向上，向右，向下，向左）重复这个过程。产生的（空的）矩阵如下：

![20180407221521608][]

**状态-动作矩阵**存储在一个特定的状态下执行一个特定动作的效用，然后对矩阵执行一个查询，我们可以估算为获得最高的效用应该执行哪一个动作。在MC控制案例中，我们必须在分析一个episode时改变我们的想法，每个状态都有一个相关的动作，并且从该状态执行此动作会导致新的状态和奖励。在图形上，我们可以把状态和相应的动作进行配对来表示一个episode。

![20180407221541145][]

上面的episode与我们在MC中用于预测的例子是一样的，机器人从（1,1）开始并在七次访问后到达充电站。在这里，我们可以像往常一样计算回报，记住我们是在首次访问(first-visit)MC的假设下，因此我们将只更新状态\-动作对（1,2）\-UP的条目一次，因为这个状态\-动作对在该episode中出现两次。为了估计效用，我们必须分解这个episode并评估**第一次出现状态-动作对后**的**回报**。在我们的例子中，必须计算状态\-动作对（1,1）\-UP、（1,2）\-UP、（1,3）\-DOWN的回报，跳过状态\-动作对（1,2）\-UP （已更新）、（1,3）\-RIGHT等。在下图中，您可以看到该计算如何进行以及如何评估不同状态\-动作的收益：

![20180407221611188][]

**在这个episode之后，**我们可以更新包含状态\-动作效用值的**矩阵**。在我们的例子中，新矩阵将包含以下值：

![2018040722163236][]

第二个episode之后，我们将在表格中填写更多的条目，以这种方式继续下去，最终将导致一个完整的状态\-动作表格，其中包含所有条目，这一步就是GPI框架中所谓的**评估**。算法的第二步是**改进**，在改进中，我们采用随机初始化策略π并以下面的方式更新它：

![201804072216543][]

就这样，我们采取策略**贪婪****(greedy)**选择出现在episode中的每个状态s及最大Q值的动作。例如，如果我们考虑状态（1,3）（网格世界的左上角），我们可以更新策略矩阵中的条目，采取状态\-动作表格中具有最高值的动作。我们的案例中，在第一个episode之后，具有最高值的动作是RIGHT，其具有0.74的Q值。

![20180407221720747][]

在MC控制中，**保证所有状态-动作对的统一探索**是很重要的。遵循策略π可能会发生相关的状态\-动作对永远不会被访问,没有回报，该方法不会改进。解决方案是使用**探索开始(exploring starts)，**指定每个episode的第一步从一个状态\-动作对开始，并且每个这样的状态\-动作对具有被选择的非零概率。现在是时候使用Python来实现算法了。

## Python实现 ##

我将再次使用`get_return()`函数，但是这次输入将是包含`(observation, action,reward)`元组的列表：

def get_return(state_list, gamma):
       """ Get the return for a list of action-state values. @return get the Return """ 
       counter = 0
       return_value = 0
       for visit in state_list:
          reward = visit[2]
          return_value += reward * np.power(gamma, counter)
          counter += 1
       return return_value

我将使用另一个新函数update\_policy()，它将使当前状态\-动作函数的策略变得贪婪：

def update_policy(episode_list, policy_matrix, state_action_matrix):
      """ Update a policy The function makes the policy greedy in respect of the state-action matrix. @return the updated policy """ 
      for visit in episode_list:
        observation = visit[0]
        col = observation[1] + (observation[0]*4)
        if(policy_matrix[observation[0], observation[1]] != -1):
          policy_matrix[observation[0], observation[1]] = \
              np.argmax(state_action_matrix[:,col])
      return policy_matrix

`update_policy()`函数是GPI改进步骤的一部分，它是为了收敛到最优策略的基础。我还将使用已经在前一篇文章中使用过的函数`print_policy()`，以便在终端上使用符号^、>、v、<、\*、＃打印策略。在`main()`函数中，我初始化了一个随机策略矩阵，`state_action_matrix`包含每个状态\-动作对的效用，矩阵可以初始化为零或随机值，这并不重要。

# Random policy matrix
    policy_matrix = np.random.randint(low=0, high=4, 
                                      size=(3, 4)).astype(np.float32)
    policy_matrix[1,1] = np.NaN #NaN for the obstacle at (1,1)
    policy_matrix[0,3] = policy_matrix[1,3] = -1 #No action (terminal states)
    
    # State-action matrix (init to zeros or to random values)
    state_action_matrix = np.random.random_sample((4,12)) # Q

最后在主循环执行算法，与用于MC预测的循环没有太大区别：

for epoch in range(tot_epoch):
    # Starting a new episode
    episode_list = list()
    # Reset and return the first observation
    observation = env.reset(exploring_starts=True)
    is_starting = True
    for _ in range(1000):
        # Take the action from the action matrix
        action = policy_matrix[observation[0], observation[1]]
        # If the episode just started then it is
        # necessary to choose a random action (exploring starts)
        if(is_starting): 
            action = np.random.randint(0, 4)
            is_starting = False      
        # Move one step in the environment and gets 
        # a new observation and the reward
        new_observation, reward, done = env.step(action)
        #Append the visit in the episode list
        episode_list.append((observation, action, reward))
        observation = new_observation
        if done: break
    # The episode is finished, now estimating the utilities
    counter = 0
    # Checkup to identify if it is the first visit to a state-action
    checkup_matrix = np.zeros((4,12))
    # This cycle is the implementation of First-Visit MC.
    # For each state-action stored in the episode list it checks if 
    # it is the first visit and then estimates the return. 
    # This is the Evaluation step of the GPI.
    for visit in episode_list:
        observation = visit[0]
        action = visit[1]
        col = observation[1] + (observation[0]*4)
        row = action
        if(checkup_matrix[row, col] == 0):
            return_value = get_return(episode_list[counter:], gamma)
            running_mean_matrix[row, col] += 1
            state_action_matrix[row, col] += return_value
            checkup_matrix[row, col] = 1
        counter += 1
    # Policy Update (Improvement)
    policy_matrix = update_policy(episode_list, 
                                  policy_matrix, 
                                  state_action_matrix/running_mean_matrix)
    # Printing
    if(epoch % print_epoch == 0):
        print("")
        print("State-Action matrix after " + str(epoch+1) + " iterations:") 
        print(state_action_matrix / running_mean_matrix)
        print("Policy matrix after " + str(epoch+1) + " iterations:") 
        print(policy_matrix)
        print_policy(policy_matrix)
    # Time to check the utility matrix obtained
    print("Utility matrix after " + str(tot_epoch) + " iterations:")
    print(state_action_matrix / running_mean_matrix)

如果我们将以下代码与MC中用于预测的代码进行比较，我们会注意到一些重要差异，例如以下条件：

if(is_starting): 
        action = np.random.randint(0, 4)
        is_starting = False

这种情况确保满足探索开始。只有**确保探索开始**，MC算法才会收敛到最优解。在用于控制的MC中，选择随机起始状态是不够的，在迭代过程中，只有所有动作的选择概率都为非零时，算法才会改进策略。从这个意义上讲，当episode开始时，我们必须选择一个随机动作，这**只能在开始状态下完成**。

还有一个我们必须分析的细微差别，在代码里我区分observation和new\_observation分别表示在时间t和时间t \+ 1的观察。在episode列表中必须存储t时刻的观察，t时刻采取的动作以及在t \+ 1时刻获得的奖励。请记住，我们对在特定状态下采取某种动作的效用感兴趣。

现在我们运行该脚本并查看获得的内容。在记住特殊的4x3世界之前，我们已经知道最优策略。如果你回到第一篇文章，你将会看到，如果奖励等于\-0.04（对于非终止状态），并且在80-10-10％概率的转换模型的情况下我们找到了最优策略，这个**最优策略**如下：

Optimal policy:
    
     >   >   >   * 
     ^   #   ^   * 
     ^   <   <   <

在最优策略中，机器人将在状态（4,2）处远离楼梯移动，并将通过最长路径到达充电站。现在，我将向您展示一旦我们运行MC控制评估脚本时策略的演变：

Policy after 1 iterations:
     ^   >   v   * 
     <   #   v   * 
     v   >   <   >
    
    ...
    
    Policy after 3001 iterations:
     >   >   >   * 
     >   #   ^   * 
     >   >   ^   < 
    
    ...
    
    Policy after 78001 iterations:
     >   >   >   * 
     ^   #   ^   * 
     ^   <   ^   <
    
    ...
    
    Policy after 405001 iterations:
     >   >   >   * 
     ^   #   ^   * 
     ^   <   <   <
    
    ...
    
    Policy after 500000 iterations:
     >   >   >   * 
     ^   #   ^   * 
     ^   <   <   <

在开始时，MC方法使用随机策略进行初始化，并不意外第一个策略是完全无意义的。经过3000次迭代后，该算法找到一个**次优策略**，在这个策略中，机器人靠近楼梯以便到达充电站，正如我们在前一篇文章中所说的，这是有风险的，因为机器人可能会掉下来。在迭代78000时，该算法找到了另一个总是次优的策略，但它比前一个稍好。最后在**迭代****405000处，算法找到最优策略**并坚持到最后。

该**MC方法不会收敛到任何次优的策略**，仔细看看GPI设计，这显而易见。如果算法收敛到次优策略，那么效用函数最终会收敛到该策略的效用函数，并且反过来会导致策略发生变化，只有在**策略和效用函数都是最优**时才能达到**稳定**。收敛到这个最佳固定点似乎是不可避免的，但尚未得到正式证明。

## 结论 ##

我想**回顾一下****MC算法的美妙之处**。在用于控制的MC中，该方法可以估计没有任何内容的最佳策略，机器人在环境中尝试不同的动作来行走，并接受这些动作的结果直到结束。就是这样，机器人不知道奖励函数，不知道转移模型，也没有任何策略要遵循，然而，该算法会持续改进直到达到最优策略。

小心**MC的方法并不完美**。例如，我们必须在更新效用函数之前保存整个episode，这是一个很强的限制，这意味着如果你想训练机器人驾驶汽车，你应该等到机器人撞到墙上以更新策略。为了克服这个问题，我们可以使用另一种称为**时间差分（****TD）学习的**算法。使用TD方法我们可以获得与MC方法相同的结果，但是我们可以在一步之后更新效用函数。在下一篇文章中，我将介绍TD方法，这是Q-Learning和Deep Reinforcement Learning的基础。

## 索引 ##

1. [\[第一篇][Link 1]\]马尔科夫决策过程，贝尔曼方程，值迭代和策略迭代算法。

2.  **[\[第二篇][Link 8]\]**蒙特卡罗概念，蒙特卡洛方法，预测与控制，广义策略迭代，Q函数。

3.  [\[第三篇\]][Link 9]时间差分概念，动物学习，TD(0),TD(λ)和资格痕迹，SARSA，Q-learning。

4.  [\[第四篇\]][Link 10]Actor-Critic方法背后的神经生物学，计算Actor-Critic方法，Actor-only和Critic-only方法。

5.  [\[第五篇\]][Link 11]进化算法介绍，强化学习中的遗传算法，遗传算法的策略选择。

6.  [\[第六篇\]][Link 12]强化学习应用，多臂老虎机，山地车，倒立摆，无人机着陆，难题。

7.  [\[第七篇][Link 13]\]函数逼近概念，线性逼近器，应用，高阶逼近器。

8. **[\[第八篇\]][Link 14]** 非线性函数逼近，感知器，多层感知器，应用，政策梯度。

## 资源 ##

·   The **complete code** for MC predictionand MC control is available on the [dissecting-reinforcement-learning][GitHub] officialrepository on GitHub.

·        Dadid Silver’s course (DeepMind) in particular **lesson 4** [\[pdf\]][pdf][\[video\]][video]and **lesson 5** [\[pdf\]][pdf 1][\[video\]][video 1].

·        **Artificialintelligence: a modern approach. (chapters 17 and 21)**Russell, S. J.,Norvig, P., Canny, J. F., Malik, J. M., & Edwards, D. D. (2003). UpperSaddle River: Prentice hall. [\[web\]][web] [\[github\]][github]

·        **Reinforcement learning:An introduction.** Sutton, R. S., & Barto, A. G. (1998). Cambridge: MITpress. [\[html\]][html]

·        **Reinforcement learning:An introduction (second edition).** Sutton, R. S., &Barto, A. G. (in progress). [\[pdf\]][pdf 2]

## 参考 ##

Russell, S. J., Norvig, P., Canny, J. F., Malik, J. M., &Edwards, D. D. (2003). Artificial intelligence: a modern approach (Vol. 2).Upper Saddle River: Prentice hall.

Sutton, R. S., & Barto, A. G. (1998). Reinforcementlearning: An introduction (Vol. 1, No. 1). Cambridge: MIT press.

[Link 1]: https://blog.csdn.net/wilbertzhou/article/details/79822237
[Link 2]: https://www.youtube.com/watch?v=PnHCvfgC_ZA
[Link 3]: https://www.youtube.com/watch?v=0g4j2k_Ggc4
[20180407213923848]: /images/20220527/247a289e85614e3dbb6d4b47bfbc2001.png
[20180407213949504]: /images/20220527/5470a7914e6b427b8fda3183c49d22df.png
[Enrico Fermi]: https://en.wikipedia.org/wiki/Enrico_Fermi
[Stanislaw Ulam]: https://en.wikipedia.org/wiki/Stanislaw_Ulam
[MC]: https://en.wikipedia.org/wiki/Monte_Carlo_integration
[DeepMind AlphaGo]: https://deepmind.com/research/alphago/
[20180407214022859]: /images/20220527/4abc54e6ed4141739eff8854e063bf04.png
[20180407214044655]: /images/20220527/9bb801939a924bf28dbed42b80a8daec.png
[20180407215606248]: /images/20220527/08655dac68e445dcb6f9219dbcc740fb.png
[2018040721562543]: /images/20220527/f94bb69c749e4d67b995d1d912e4df3a.png
[20180407215703512]: /images/20220527/4129380912b147fcbea0c5dec9b2e213.png
[Link 4]: https://en.wikipedia.org/wiki/Expected_value
[Link 5]: https://en.wikipedia.org/wiki/Random_variable
[Link 6]: https://en.wikipedia.org/wiki/Law_of_large_numbers
[GitHub]: https://github.com/mpatacchiola/dissecting-reinforcement-learning
[OpenAI Gym]: https://gym.openai.com/
[20180407221321779]: /images/20220527/9f98ade97e8a43a4918acdfe0688f3e2.png
[20180407221352879]: /images/20220527/fea705e18815437ebd443e35d3778b34.png
[Link 7]: https://en.wikipedia.org/wiki/Greedy_algorithm
[20180407221416881]: /images/20220527/e0eaa076dd0941fab48280c937e77b8f.png
[20180407221450449]: /images/20220527/64af8736771a4cc1af9039798ec7b2eb.png
[20180407221521608]: /images/20220527/2127864ca2e148bdad5f8b34fb3ea151.png
[20180407221541145]: /images/20220527/ea5193f986ae4c3098292cd8eefbd806.png
[20180407221611188]: /images/20220527/6a0ec04d4ed14222aca56d27d86a7479.png
[2018040722163236]: /images/20220527/dbd1229444f341df83dbfb179f936e32.png
[201804072216543]: /images/20220527/dea938d0d8284066b058876f0ab4feec.png
[20180407221720747]: /images/20220527/9164a097b838492192da99bd9bd2bc94.png
[Link 8]: https://blog.csdn.net/wilbertzhou/article/details/79845415
[Link 9]: https://blog.csdn.net/wilbertzhou/article/details/79953950
[Link 10]: https://blog.csdn.net/wilbertzhou/article/details/80041495
[Link 11]: https://blog.csdn.net/wilbertzhou/article/details/80113538
[Link 12]: https://blog.csdn.net/wilbertzhou/article/details/80187257
[Link 13]: https://blog.csdn.net/wilbertzhou/article/details/80260205
[Link 14]: https://blog.csdn.net/wilbertzhou/article/details/86743877
[pdf]: http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/MC-TD.pdf
[video]: https://www.youtube.com/watch?v=PnHCvfgC_ZA&t=438s
[pdf 1]: http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/control.pdf
[video 1]: https://www.youtube.com/watch?v=0g4j2k_Ggc4&t=2s
[web]: http://aima.cs.berkeley.edu/
[github]: https://github.com/aimacode
[html]: https://webdocs.cs.ualberta.ca/~sutton/book/ebook/the-book.html
[pdf 2]: https://webdocs.cs.ualberta.ca/~sutton/book/bookdraft2016sep.pdf