免规则采集器列表算法( 基于树的搜索（tree-search），不能的研究目的有两个)

　　免规则采集器列表算法(

基于树的搜索（tree-search），不能的研究目的有两个)

　　

　　这个文章的研究内容是：具有规划能力的agent。

　　在此之前，许多研究都使用了基于树的规划方法。然而，在实际的业务应用中，动态控制/仿真环境往往是复杂且未知的。

　　这篇文章文章 提出了一种算法：MuZero，它通过将基于树的搜索与学习模型相结合，在不了解环境底层动态的情况下可以很好地执行。这很好。

　　这里的学习模型实际上是迭代应用的，可以预测与计划最相关的奖励、行动选择策略和价值函数。

　　所以，总而言之，MuZero 的研究目标有两个：

　　下面就开始看具体的作品吧！

　　1 算法简介1.1 背景

　　基于前瞻搜索的规划算法有很多应用。然而，这些规划算法都依赖于精确的模拟器和严格的规则，无法直接用于现实世界。

　　我们知道强化学习算法分为基于模型和无模型。一般来说，我们的研究侧重于无模型方法，即直接从与环境的交互中估计最优策略和价值函数。这些方法在某些视频游戏中运行良好，例如 Atari。但是，无模型在需要精确和复杂前瞻的领域（例如围棋或国际象棋）中效果较差。

　　在一般的基于模型的强化学习方法中，模型实际上是一个概率分布，也就是构建一个真实的环境，或者说是一个完整的观察。首先从环境的动态中学习一个模型，然后根据学习到的模型进行规划。但在 Atari 游戏实验中，性能不如 Model-based。

　　本文文章介绍了一种新的基于模型的强化学习方法MuZero，它不仅可以在视觉复杂的Atari上表现出色，而且在精确规划任务中也表现出色。这很好，

　　MuZero 算法基于 AlphaZero 强大的搜索和基于搜索的策略算法，在训练过程中加入了一个学习模型。

　　除此之外，MuZero 将 AlphaZero 扩展到更广泛的环境，包括单个代理域和中间时间步长的非零奖励。

　　小总结：

　　规划（planning algorithm）是一个难点研究。众所周知的 AlphaGo 是一种基于树的规划算法，但此类算法需要完美的环境模型，这在现实世界中很难满足。

　　DeepMind 的 MuZero 算法是基于模型的 RL 领域的里程碑式成就，在促进强化学习解决现实问题方面迈出了新的一步。1.2 理解算法的思想

　　首先介绍一下MuZero算法的思想：

　　MuZero算法的主要思想是构造一个抽象的MDP模型，在这个MDP模型上，预测与Planning直接相关的未来数据（策略、价值函数和奖励），并在此基础上预测数据进行规划。

　　那么为什么要这样做，为什么它会起作用？让我们将论文中的内容“分解”和“粉碎”来理解算法的思想：

　　1.2.1 为什么要抽象

　　我们知道，大多数基于模型的强化学习方法都会学习对应于真实环境的动态模型。

　　但是，如果是用于 Planning，我们并不关心 Dynamics Model 是否准确地还原了真实环境。

　　只要这个 Dynamics Model 给出的未来每一步的价值和回报接近真实环境中的价值，我们就可以将其作为 Planning 中的模拟器。

　　MuZero 算法是首先将真实环境中通过编码器（表示函数）获得的状态转换为没有直接约束的抽象状态空间（abstract state space）中的隐藏状态（hidden state）。状态并假设循环迭代的下一个动作）。

　　然后在这个抽象的状态空间中，学习Dynamics Model和价值预测，预测每个隐藏状态上的策略（这就是和本文的区别），得到Policy Prediction Network。

　　然后，使用蒙特卡洛树搜索，使用 Dynamics Model 作为模拟器，在抽象状态空间中做 Planning，预测接下来几个步骤的策略、价值函数和奖励。

　　这里的隐藏状态是不适合真实环境的。取而代之的是，在抽象状态空间中训练的 Dynamics Model 和价值预测网络可以预测在初始隐藏状态和执行接下来的 k 步后接下来 k 步的价值和奖励，以及通过搜索得到的价值和奖励在真实环境中。观察到的奖励尽可能接近。

　　简单来说，就是先在虚拟状态空间中学习一个环境模型，然后在不与真实环境过多交互的情况下，根据学习到的环境模型进行规划。

　　1.2.2 为什么有效

　　那么我们如何保证抽象MDP中的规划与真实环境中的规划是等价的呢？

　　这种等价是通过确保价值等价来实现的。

　　也就是说，从相同的真实状态开始，通过抽象 MDP 的轨迹累积奖励与真实环境中轨迹的累积奖励相匹配。

　　2 型号图解说明

　　首先，整体数据是模型的数学表达式：

　　给定一个隐藏状态和一个候选动作，动态模型需要生成一个即时奖励和一个新的隐藏状态。策略和价值函数是由预测函数从输入中计算出来的。操作是从搜索策略中采样的。环境收到一个动作以产生新的观察和奖励。

　　接下来通过图文结合的方式，具体讲讲如何使用学习到的模型进行策划、演戏、训练。

　　2.1 MuZero中模型的组成

　　MuZero 如何使用该模型进行规划？我们看图A：

　　

　　所谓模型由以下3个相互关联的部分组成：

　　2.2 MuZero 如何与环境交互并做出决策

　　图 A 中描述的是，在每一步中，隐藏状态执行蒙特卡洛树搜索到下一个动作。

　　那么 MuZero 是如何在环境中做出决策的呢？

　　下图是横看各招的情况：

　　

　　对于子图1描述的情况（一黑一白），使用蒙特卡洛树搜索对其建模得到一个策略网络，并对策略网络进行采样选择可执行动作，这个动作与访问量成正比MCTS 根节点的每个操作的计数。

　　执行动作后，得到奖励，得到下一时刻的观察（子图2），同样使用MCTS进行建模，得到策略网络，选择可执行动作。

　　环境接受动作，产生新的观察和奖励，产生子图 3。

　　这样，轨迹数据在剧集结束时存储在重放缓冲区中。这是一个决定。

　　2.3 MuZero 如何训练模型

　　那么 MuZero 是如何训练模型的呢？让我们看看下面的过程：

　　

　　对 Replay Buffer 中的轨迹数据进行采样，选择一个序列，然后针对该轨迹运行 MuZero 模型。

　　在初始步骤中，编码器表示函数接受来自所选轨迹的过去观察。

　　随后，模型展开一个 K 步循环。

　　在第 k 步中，*敏*感*词*动力学函数接收上一步的隐藏状态和实际动作。

　　编码器表示函数、*敏*感*词*动力学函数、预测器预测函数的参数可以通过backpropagation-through-time的端到端联合训练来预测，可以预测三个量：

　　其中是样本回报，例如棋盘游戏中的最终奖励，或 Atari 中 n 步的奖励。

　　3 MuZero算法详解3.1 价值网络和策略网络

　　MuZero 是一种机器学习算法，因此很自然地首先要了解它是如何使用神经网络的。

　　简而言之，该算法使用了 AlphaGo 和 AlphaZero 的策略和价值网络：

　　

　　政策网络和价值网络的直观含义如下：

　　根据策略网络，可以预测每一步的动作；依靠价值网络，可以选择价值最高的动作。结合这两个估计可以得到更好的结果。

　　3.2 MuZero中的蒙特卡洛树搜索3.2.1 MCTS简介

　　MuZero 还使用 MCTS（蒙特卡洛树搜索）聚合神经网络来预测和选择当前环境中的下一个动作。到达终点后，树中的每个节点都会存储一些相关的参数，包括访问次数、轮数、前一个动作的概率、子节点以及是否有对应的隐藏状态和奖励。

　　蒙特卡洛树搜索是一个迭代的、最佳优先的树搜索过程。目标是帮助我们弄清楚要采取哪些行动来最大化长期利益。

　　Best first，这意味着搜索树的扩展取决于搜索树中的值估计。

　　与常见的深度优先和广度优先相比，最佳优先搜索可以利用深度神经网络的启发式估计，在非常大的搜索空间中找到最优解。

　　蒙特卡洛树搜索有四个主要阶段：

　　通过重复这些阶段，MCTS 每次都在节点可能的未来动作序列上逐步构建搜索树。在这棵树中，每个节点代表一个未来状态，节点之间的线代表从一个状态到下一个状态的动作。

　　3.22 MuZero算法中MCTS的四个阶段

　　接下来我们对应MuZero算法中的蒙特卡洛树搜索，看看上面四个阶段分别对应什么：

　　

　　我们先来看看模拟。

　　模拟过程与蒙特卡罗方法类似，推导速度快。为了得到某个状态的初始分数，让游戏随机玩到最后，记录模拟次数和获胜次数。

　　接下来是选择。

　　虽然 Muzero 不知道游戏规则，但它知道该采取哪些步骤。在每个节点（状态 s），使用评分函数比较不同的动作，并选择得分最高的最佳动作。

　　

　　每次选择一个动作时，我们都会为 UCB 缩放因子 c 和后续动作选择增加其关联的访问计数 N(s,a)。

　　模拟沿着树向下进行到尚未扩展的叶子。此时，应用神经网络对节点进行评估，将评估结果（优先级和值估计）存储在节点中。

　　然后是扩展。

　　选择动作 A 后，在搜索树中生成一个新节点，对应动作 A 执行后前一个状态的情况。

　　最后回溯。

　　模拟结束后，从子节点开始沿着刚刚下的路径返回，沿途更新每个父节点的统计信息。每个节点都持有其下所有价值估计的连续平均值，这使得 UCB 公式可以随着时间的推移做出越来越准确的决策，确保 MCTS 收敛到最优动作。

　　3.2.3 中级奖励

　　

　　事实上，在 MCTS 的过程中，也收录了对中间奖励 r 的预测。

　　在某些情况下，游戏完全结束后需要输赢反馈，这可以通过价值估计来建模。但是在频繁反馈的情况下，从一种状态到另一种状态的每次转换都会得到奖励 r。

　　因此，奖励直接通过神经网络预测建模并用于搜索。在 UCB 策略中引入中间奖励：

　　其中是在状态 s 执行动作 a 后观察到的奖励，折扣因子是对未来奖励的关注程度。

　　由于在某些环境中奖励是无界的，因此可以将奖励和价值估计归一化到 [0,1] 期间，然后与先验知识相结合：

　　其中 和 分别是在整个搜索树中观察到的最大和最小估计值。

　　3.3 总体说明

　　基于过去的观察和未来的行为，对于给定步骤中的每一步，使用带有参数的模型在每个时间步进行预测。

　　该模型预测 3 个数量：

　　其中是地面实况观察奖励，是策略，是折扣因子。

　　说白了就是获取过去的观察数据，编码成当前的隐藏状态，然后给出未来的动作，然后在隐藏状态空间进行规划。

　　3.4 步分解

　　在每个步骤中，模型由表示函数、动力学函数和预测函数组成：

　　使用这样的模型，可以根据过去的观察来搜索虚拟的未来轨迹。

　　例如，可以简单地选择 k 步动作序列来搜索最大化价值函数。

　　也可以使用类似于 AlphaZero 搜索的 MCTS 算法来获取策略和估计值，然后从策略中选择动作。此外，执行操作并生成中间奖励和状态空间。

　　在第 k 步，通过联合训练模型的所有参数，将策略、价值和奖励与实际观察到的目标值图像进行匹配。

　　模型的所有参数都经过联合训练，使得每个假设步 k 的策略、值和奖励与 k 个实际时间步后观察到的相应目标值完全匹配。

　　使用 MCTS，可以使用三个改进的策略目标：

　　最后加上L2正则化项得到最终的损失函数：

　　4 总结

　　强化学习分为两类：基于模型的和无模型的。

　　其中，基于模型的强化学习方法需要构建环境模型。通常，环境模型由马尔可夫决策过程（MDP）表示。该过程由两部分组成：

　　模型通常针对选定的动作或时间抽象的行为进行训练。一旦模型建立，MDP 规划算法（例如：值迭代、蒙特卡洛树搜索 MCTS）可以直接用于计算 MDP 的最优值或最优策略。

　　因此，在复杂环境或局部观察的情况下，很难构建模型应该预测的状态表示。因为Agent没有办法优化“有效规划的目的”的表示和模型，这就导致了表示学习、模型学习和规划之间的分离。

　　另一方面，MuZero 是一种完全不同的基于模型的强化学习方法，专注于端到端的预测函数。主要思想是构造一个抽象的MDP模型，使抽象MDP中的规划等价于真实环境中的规划。

　　这种等价是通过保证价值等价来实现的，即从相同的真实状态开始，通过抽象MDP获得的轨迹累积奖励与真实环境中的轨迹累积奖励相匹配。

　　预测器首先引入价值等价模型来预测价值而无需采取行动。

　　虽然底层模型是 MDP，但它的变换模型不需要匹配环境中的真实状态，只需将 MDP 模型视为深度神经网络中的隐藏层即可。展开的 MDP 被训练，例如通过时间差异学习，以将累积奖励的预期总和与实际环境的预期值相匹配。

　　然后，将价值等价模型扩展为以行动优化价值。TreeQN 学习一个抽象的 MDP 模型，以便在该模型上的树搜索（由树结构的神经网络表示）近似于最优值函数。值迭代网络学习一个局部 MDP 模型，使得该模型上的值迭代（由卷积神经网络表示）接近最优值函数。

　　价值预测网络更接近于 MuZero：根据实际动作学习一个 MDP 模型；对展开的 MDP 进行训练，以使奖励的累积总和（以简单前向搜索产生的实际动作序列为条件）与真实环境匹配一致。如果没有策略预测，则搜索仅使用值预测。

　　通过论文的学习，虽然理解了MuZero算法的思想，但是在实际项目中使用MuZero还是比较困难的。

　　比如如何设计表示、动态、预测等，这些都需要在对代码实现非常熟悉的情况下结合具体的业务场景来实现。

　　提供基于pytorch的muzero算法实现：

　　如果有时间，我会继续研究代码并尝试复现论文。

　　结束