蒙特卡洛树搜索(MCTS)是一类用于序贯决策的算法,将有选择的树探索与对可能结果的统计评估相结合。它从当前情境出发,反复模拟后续过程,记录模拟结果,再据此决定哪些备选方案值得进一步考察。与穷举搜索不同,它通常只构建整个可能决策树中的一小部分,而且对各部分的探索深度并不均衡。
MCTS 因在计算机围棋中的应用而受到广泛关注。在围棋中,合法落子数量众多,中间局面又难以评估,这些因素限制了传统博弈程序方法的成效。此后,MCTS 成为 AlphaGo 及相关系统的核心组成部分,也被应用于规划、调度、优化和自动推理等领域。它的标志性贡献在于自适应地分配计算资源:有潜力的行动会得到更多关注,而结果尚不确定的备选行动仍有机会得到探索。
其名称源于它使用了通过采样来估计数值的蒙特卡洛方法,不过,现代实现往往以学习得到的评估来替代随机模拟至对局结束的做法。因此,将 MCTS 理解为一种搜索框架,而非某个固定算法,更为恰当。它的行为取决于状态的表示方式、选择规则、模拟或评估过程、对不确定性的处理方式,以及可用的计算预算。
历史发展与计算机围棋的挑战
在蒙特卡洛树搜索出现之前,许多成功的博弈程序依赖于极小化极大算法搜索、Alpha–Beta剪枝以及精心设计的局面评估函数。这些技术在国际象棋中尤为有效,因为子力对比、王的安全性和局面特征都能在对局结束前为评估提供有用的依据。围棋则面临另一组相互交织的难题。标准围棋棋盘有361个交叉点,在开局阶段往往有数百种合法落子选择。一块棋的价值可能取决于遍及全盘的相互作用,因此很难仅凭局部情况进行数值评估。
蒙特卡洛方法提供了另一条路径:从某一步棋出发,多次模拟后续对局,并根据结果估计这步棋的价值。早期探索包括伯恩德·布吕格曼(Bernd Brügmann)于1993年开展的蒙特卡洛围棋研究。一种简单的实现方式是为每个候选着法分配模拟次数,再比较其平均结果。这样就不必依赖准确的静态评估函数,但如果明显较差的着法与看似可行的着法得到同样多的关注,计算资源的分配就会十分低效。此外,这种方法也无法构建细致的应对树,明确考察对手采取强有力应对后的结果。
2006年的两项进展奠定了现代框架。雷米·库隆(Rémi Coulom)描述了一种方法,在逐步扩展搜索树的同时,将模拟对局所得的信息沿树向上回传,并将其命名为蒙特卡洛树搜索。同年,莱文特·科奇什(Levente Kocsis)和乔鲍·塞派什瓦里(Csaba Szepesvári)提出了将置信上界应用于树的方法,即UCT(Upper Confidence Bounds applied to Trees)。UCT将树内的动作选择视为一系列多臂老虎机问题,为在探索尚不确定的着法与利用已显现优势的着法之间取得平衡,提供了有理论依据的机制。
Crazy Stone和MoGo等程序证明,这些思路能够显著提升计算机围棋的水平。它们的实力并非来自完全均匀随机的下法:实际系统加入了选择合理着法、处理战术棋形以及在相关局面之间共享信息的规则。因此,蒙特卡洛树搜索的历史意义,并不在于发现仅凭随机性就能取代领域知识,而在于建立了一个让采样、选择性搜索与领域知识相互促进的框架。
第二次重大转变伴随深度学习而来。2016年发表的AlphaGo论文描述了一个结合策略网络、价值网络与蒙特卡洛树搜索的系统;该程序于2016年3月以四比一击败李世石。2017年的AlphaGo Zero在训练中摆脱了对人类棋谱的依赖,随后AlphaZero将相关方法应用于国际象棋、将棋和围棋。这些系统改变了模拟的作用:搜索树越来越多地用于统筹学习得到的预测,而不再主要依赖随机续弈至终局。
决策模型、状态与搜索目标
一个 MCTS 问题首先需要定义状态的表示方式、可用动作的集合、生成后继状态的机制以及目标。在棋盘游戏中,状态包括棋盘布局、轮到哪一方行动,以及与规则有关的历史信息。在调度问题中,状态可能包括已完成的作业、资源可用情况和仍需满足的约束。搜索结构通常被称为博弈树,但这种方法并不要求问题一定是游戏,也不要求存在对抗性对手。
对于随机序贯决策,一种有用的形式化框架是马尔可夫决策过程。令 表示时刻 的状态, 表示动作, 表示由此产生的奖励。时间跨度为 的折扣回报为
其中, 为折扣因子。搜索估计的是选择某个动作、随后按某种后续策略行动所获得的期望值,即期望回报。在仅于终局给予奖励的有限博弈中,这一表达式通常简化为胜、平、负等最终结果。
搜索目标随交互模型而变化。在单智能体问题中,搜索通常以最大化该智能体的期望回报为目标。在双人零和博弈中,每位玩家都要最大化自己的收益,因此向上回传价值时必须考虑双方利益的对立。随机环境会引入偶然事件,这些事件应按其发生概率进行采样,而不应被视为敌对方作出的决策。多人博弈可能需要使用效用向量,并明确描述每位玩家如何选择动作。
一个关键前提是能够使用可行的状态转移模型。在游戏中,规则通常可以提供精确的模拟器。在其他应用中,模型可能是物理模拟器、通过学习得到的预测模型,或对可能结果进行采样的程序。MCTS 本身不能仅靠搜索就发现准确的动态规律。如果模拟器对环境的描述存在系统性偏差,增加模拟次数可能只会让算法对一个错误问题的估计变得更加精确。因此,需要区分有限搜索造成的不确定性与所搜索模型本身的误差。
搜索树也不必与实际状态一一对应。两个不同的动作序列可能到达同一个状态,从而形成转置。反过来,两个看起来完全相同的局面,也可能因重复局面规则或未显式呈现的历史信息而有所不同。正确的状态表示必须保留所有与未来状态转移和奖励有关的信息。在无法完全观测环境的情况下,仅搜索可观测到的局面通常并不足够;状态表示必须考虑对底层状态的不确定性,或各参与者所能获得的信息。
四阶段搜索循环
一次常规的 MCTS 迭代包含四个阶段:选择、扩展、模拟和反向传播。不同实现对各阶段的划分有所不同,但这四个阶段描述了每一份新增证据如何进入搜索过程。搜索树以当前决策状态为根节点。每次迭代都会沿现有节点构成的路径向下遍历,在搜索前沿添加信息,评估后续过程,并更新所经路径上的统计量。反复执行这一过程,搜索树便会逐渐集中于那些看起来较为重要的决策。
在选择阶段,树策略从根节点开始选择动作,直到到达应当进行扩展或评估的节点。每条状态—动作边通常存储访问次数 、累计回报 ,以及在访问次数非零时的平均价值:
选择时通常会将价值估计与探索项结合起来。仅仅选择当前平均价值最大的动作并不可靠,因为某个动作可能只是凭借少数几次运气较好的采样,就显得优于真正更好的备选动作。
在扩展阶段,算法添加一个或多个后继节点。基本实现会添加一个此前尚未探索过的动作。其他实现则可能一次性创建所有合法子节点,或者随着父节点访问次数增加而逐步引入子节点。扩展既涉及表示方式的选择,也涉及统计方面的选择:在规模较小的棋盘局面中,创建所有可能的子节点开销不大;但当动作包含连续控制参数或任意字符串时,这种做法就不切实际了。
在模拟阶段(也称 rollout),默认策略从搜索前沿继续执行,直到到达终止状态或满足其他停止条件。默认策略可以在合法动作中进行均匀随机选择,也可以遵循特定领域的规则,或使用学习得到的策略。截断的模拟需要对其终点进行评估,这通常由启发式评估函数或学习得到的价值模型完成。在神经网络 MCTS 中,价值预测可以完全取代模拟,因此,与早期实现相比,此时“模拟”一词已不再那么贴合其字面含义。
在反向传播阶段,利用所得回报更新选定路径上每条相关边的统计量。这里的“反向传播”不同于神经网络中的反向传播:它通常指统计量更新,而非求导。奖励的约定必须始终保持一致。在双方交替行动的双人零和博弈中,如果价值是从当前行动方的视角存储的,那么每次行动方交替时,价值的正负号都要改变;如果固定采用根节点一方的视角,则需要让对手节点相应地选择对根节点一方不利的结果。计算预算耗尽后,通常会选择根节点下访问次数最多的动作作为实际执行的动作,不过也有采用最高平均价值等规则的做法。最终动作的选择规则不必与搜索内部使用的探索规则相同。
UCT、探索与统计保证
UCT 将基于置信上界的动作选择方法应用于搜索树。一种常见形式是选择使下式最大化的动作:
其中, 是父节点的访问次数, 用于控制探索程度。对于尚未访问的动作,通常会显式尝试一次,或赋予一个能确保其获得首次访问的分数。第一项偏向估计回报较高的动作,第二项则偏向采样次数相对较少的动作。随着父节点的访问次数增加,先前受到忽视的子节点会变得越来越有吸引力。
这一公式与彼得·奥尔、尼科洛·切萨-比安基和保罗·费舍尔于 2002 年分析的 UCB1 有关。在经典的多臂老虎机问题中,决策者需要在奖励分布未知的多个选项之间反复做出选择。利用是选择被认为表现良好的选项,而探索则是收集可能改善后续选择的信息。UCT 在每个内部节点上应用这一思想,使各处的局部选择都能随着证据的积累而调整。探索系数取决于奖励的尺度:适用于回报范围为 的参数设置,不能直接照搬到未经归一化的货币奖励上。
不过,将其类比为相互独立的老虎机臂并不完全准确。在通常的多臂老虎机分析中,一般假设每个臂的奖励分布保持不变。而在树搜索中,随着树中更深层的策略得到改进,执行某个动作后观测到的回报也会发生变化。某一步棋最初可能看起来很差,只是因为搜索尚未发现其后强有力的续着。因此,树节点接收到的证据来自一个不断演变的过程。对 UCT 的分析必须考虑这种递归依赖关系,而不能仅仅在每个节点上独立套用不涉及树结构的多臂老虎机结论。
在奖励有界、满足适当的有限时域条件等假设下,UCT 具有一致性方面的理论结果:增加计算量,可以使其在根节点的选择趋近最优决策。这类保证并不意味着算法能迅速得出有用的决策。某些树结构会使决定性的后续路径极难被发现;即使算法在渐近意义上正确,在实际计算预算下仍可能表现不佳。探索常数、模拟策略、动作分支数量以及奖励结构,都会影响其在有限样本下的表现。
另一个区别在于探索的目标。在搜索过程中,模拟的价值通常不在于其自身获得的即时奖励,而在于找出一个适合随后执行的动作。因此,简单遗憾,即最终推荐动作所对应的损失,尤其值得关注。相比之下,经典的多臂老虎机方法往往着眼于优化所有选择的累积遗憾。因此,用于识别最优动作的算法可以在根节点采用不同的采样规则。此外,不应直接将 UCT 的探索奖励项理解为某一步棋的博弈论价值所对应的、经过校准的置信区间,因为这种解释所需的假设,在自适应树搜索中通常无法原封不动地成立。
模拟续演设计、信息共享与选择性扩展
MCTS 估计的质量很大程度上取决于后续过程的生成方式。均匀随机的模拟续演容易实现,但生成的行动序列可能与高水平对弈相去甚远。某个局面面对随机行动时可能是胜势,但面对精准应对时却可能是败势。融入领域知识的模拟续演会优先选择战术性应对、避免明显无效的走法,或采用学习得到的策略,以使模拟更贴近高水平对弈。不过,更强的模拟续演策略并不一定更好:它可能运行更慢、多样性更低,或存在系统性偏差,从而扭曲候选行动之间的比较。
一种颇具影响力的信息共享技术是快速行动价值估计(Rapid Action Value Estimation,简称 RAVE)。其思路是:某个行动即便出现在模拟的较后阶段,也能为更早采取该行动提供初步依据。与之配套的“所有走法视为首步”(all-moves-as-first)统计量,可以在常规边访问计数尚不足以支持可靠估计时,提供有用的估计。典型的融合方式是在早期赋予这种共享估计较大的权重,并随着直接证据的积累逐渐降低其权重。这种方法在围棋中效果良好,因为在相近的落子顺序下,某些走法的效果具有相关性;但当行动时机至关重要时,其假设的适用性就会减弱。
先验知识也可以通过初始值、虚拟观测、走法排序或渐进偏置引入。启发式方法可以在某些子节点尚未被大量模拟访问之前,就让搜索优先考虑它们;随着实证证据的积累,启发式方法的影响则逐渐减弱。这些方法区分了两种做法:利用知识分配计算资源,以及将知识当作已获证明的事实。硬剪枝可能永久排除最优行动;逐渐衰减的偏置通常限制较少,因为其他选项始终可供探索。
庞大或连续的行动空间需要另一种调整。渐进拓宽根据访问次数限制已扩展子节点的数量,通常采用如下形式的规则:
其中, 是当前的子节点集合。搜索起初只比较少量采样得到的行动,随后随着证据的积累引入更多行动。双重渐进拓宽则对随机环境中的后继结果施加类似限制。若不加这种限制,结果连续变化的模型可能几乎每次模拟都会产生一个新的后继节点,导致任何一条后续路径都无法得到足够的重复分析。
另一些变体则改变了反向回传本身。Mark Winands 及其合作者于 2008 年提出的 MCTS-Solver,会在足够多的后代节点已被求解时,向上传递已获证明的博弈结果。这样,已确定的必胜结果就可以优先于不确定的统计平均值。混合系统还可以在选定节点上执行战术性的极小极大搜索。这些技术针对不同的弱点:共享统计量加快早期学习,拓宽机制控制分支数量,精确推断则防范仅靠平均值可能无法暴露的错误。它们的效果取决于新增信息是否契合具体问题的结构。
神经网络引导与基于搜索的强化学习
神经网络引导的 MCTS 将树搜索与人工神经网络相结合,由网络预测有潜力的动作、局面价值,或同时预测两者。策略输出 给出对各个合法动作的先验偏好,而价值输出 则估计最终结果或回报。搜索利用这些预测来确定重点扩展的方向并评估前沿节点,再通过显式考察动作后果来改进这些预测。网络提供跨局面的泛化能力,搜索树则提供针对当前局面的计算。
AlphaGo 类系统中广泛使用的一种选择规则通常称为 PUCT。其一种典型形式为
与标准 UCT 不同,这个表达式通过策略先验来调节探索激励。先验概率较高的动作会较早得到考察,但动作的经验价值可能改变它最终受到的重视程度。不同系统采用的具体公式和常数各不相同,因此 PUCT 指的是一组相关的选择机制,而非一个普遍固定的方程。如果先验实际上排除了某个关键动作,那么实际搜索可能在预算耗尽之前始终无法重新发现它。
最初的 AlphaGo 结合了策略网络、价值网络和模拟对局评估。AlphaGo Zero 则使用一个同时输出策略和价值的网络,不再依靠一直模拟到对局结束来进行评估。在自我对弈训练中,搜索生成的动作分布优于网络未经搜索辅助的策略,而最终的对局结果则提供了价值学习的目标。其一种典型目标函数为
其中, 为对局结果, 为根据搜索访问次数得出的目标分布。这三项分别用于提高价值预测的准确性、使策略与搜索结果保持一致,以及对参数进行正则化。
这在强化学习中形成了一个反馈循环。更好的网络预测可以改善搜索,而更强的搜索又能为后续网络训练生成更好的目标。由此形成的过程与近似策略迭代有关,但搜索是在运行时在线执行的,而不只是由一个固定的已学习策略来体现。自我对弈还需要能够产生多样化经验的机制;例如,AlphaGo Zero 在训练期间向根节点的先验分布加入了狄利克雷噪声。这种探索噪声的作用,与评估时选择最终落子不同。
2019 年推出的 MuZero 进一步扩展了这一方法:它在学习得到的潜在动力学模型中进行搜索,而不再要求搜索树使用显式提供的游戏模拟器。其模型预测规划所需的量,包括奖励、策略和价值,而不一定要详细重建观测。这将 MCTS 与世界模型和表征学习联系起来,但也引入了另一种失效模式:搜索可能利用所学动力学模型中的误差。因此,神经网络引导改变了证据的来源和获取成本,却没有消除评估模型误差的必要性,也无法排除计算资源被引向误导性预测的可能。
随机环境与不完全信息
随机性和隐藏信息带来的挑战并不相同。在具有随机性但完全可观测的环境中,智能体知道当前状态,但未来结果仍不确定。转移模型可以对需求到达、设备故障或掷骰结果进行采样。正确的搜索必须按照环境中的概率对这些结果求平均。如果把随机事件当作可控动作,就等于假设智能体能够选择自己的运气;如果把它当作对手的动作,通常又会导致过于悲观、缺乏依据的决策。
在部分可观测环境中,智能体连当前状态本身也无法确知。因此,决策所依据的可能是一个关于状态的信念分布,并根据观测不断更新。部分可观测马尔可夫决策过程对这种情形进行了形式化描述。戴维·西尔弗和乔尔·维内斯于2010年提出的 POMCP,将蒙特卡洛规划与信念的粒子表示相结合。它在动作—观测历史上进行搜索,并可利用模拟器生成轨迹,而不必显式枚举所有可能的底层状态。
隐藏信息博弈还会带来策略上的复杂性,因为其他玩家同样掌握私有信息,并可能采取行动来隐藏或透露这些信息。一种颇具吸引力的方法称为确定化:对完整的隐藏状态进行采样,然后针对每个采样状态执行普通的完全信息搜索。例如,纸牌游戏程序可以采样出与已观察到的牌相符的各家手牌。这种做法很方便,但由此得出的计划可能依赖于玩家实际上并不掌握的信息。
其中一个核心问题是策略融合。在不同的采样世界中,搜索可能根据哪个隐藏世界是真实的,选择不同的后续动作,尽管玩家在所有这些世界中面对的可观测历史都相同。将这些计划合并,可能会高估在没有额外信息的情况下所能取得的效果。另一个相关难点是:采样得到的隐藏状态,未必能反映对手此前的选择所透露的、关于其可能持牌或意图的信息。仅仅增加确定化采样的次数,并不能消除信息模型中的结构性错误。
信息集蒙特卡洛树搜索(ISMCTS)围绕信息集组织搜索,而不是将每个采样世界都视为可独立观测的世界。不同变体的区别在于:以谁的观测来定义搜索树,以及在模拟过程中如何处理私有信息。这些方法可能很有效,但对于一般的不完全信息博弈,它们并不会自动给出均衡策略。反事实遗憾最小化则着眼于不同的目标,通过降低各信息集上的遗憾值来求解,并已在扑克领域发挥了重要作用。应当采用哪种框架,取决于任务究竟是针对已建模对手进行在线规划、在不确定性下稳健对弈,还是近似求解博弈论均衡。
数据结构、并行执行与计算成本
实现通常会为节点或边存储记录,其中包含访问次数、价值总和、动作标识符以及指向后继节点的链接。采用神经网络的变体还会存储策略先验,并可能缓存评估结果。如果选中路径的平均深度为 ,那么一次迭代大致需要 的树遍历和更新工作,此外还需承担扩展与评估的成本。模拟推演较长时,可能占据大部分运行时间;使用大型模型评估搜索前沿状态时,神经网络推理则可能成为主要耗时环节。因此,脱离模拟器和评估器,不存在一个统一且有实际意义的时间复杂度表达式。
内存用量通常近似随已扩展节点的数量增长,而不是随理论上整棵树的规模增长。尽管如此,长时间搜索仍可能耗尽内存。实现可以限制树的大小、丢弃低优先级分支、压缩记录,或重建树的某些部分。执行一个动作后,可以将对应的子节点设为新的根节点,从而保留相关统计信息。复用时必须考虑视角的变化、状态是否相同,以及是否有搜索设置导致旧统计信息与新统计信息不兼容。
可以使用以状态表示为键的哈希表来识别转置,即不同路径到达同一状态的情况。这样可以将表面上的树结构部分转化为有向图,并避免重复评估。然而,共享节点会使统计信息的处理变得复杂:经由一个父节点收集的证据,并不总能与经由另一个父节点收集的证据互换,尤其是在历史会影响动作合法性、奖励或重复局面的判定时。对于环路,必须采取明确的处理措施,例如设置深度限制或检测重复状态。基于图的实现不能简单地假定,每次递归深入都会更接近终止状态。
并行计算可以通过多种方式分配工作。根并行化会构建多棵独立的树,再合并各棵树根节点的统计信息。叶并行化会从搜索前沿出发,评估多条后续路径。共享树并行化则允许多个工作线程在同一结构中执行选择和更新。这些方法需要在通信开销与信息共享带来的收益之间权衡。共享树实现必须谨慎进行同步,以免统计信息受损,但过多的锁操作可能抵消增加工作线程带来的加速效果。
一种常用技术是虚拟损失:在某个工作线程评估选中的路径期间,暂时降低该路径的吸引力,避免其他工作线程重复执行相同任务。评估结果返回后,必须撤销或修正这一临时更新。神经网络系统还会将叶节点评估组成批次,交给图形处理器处理,以提高硬件利用率,但这也会延迟向搜索树反馈结果。因此,增大批次可以提高评估吞吐量,却会降低每次评估所带来的自适应调整能力。实际性能取决于搜索、模拟器、内存布局、调度与加速器使用方式的协同设计,而不仅仅取决于名义上的模拟次数。
传统棋盘游戏之外的应用
当一个问题可以表述为一连串选择,且能够用模拟器评估完整或部分解时,MCTS 就能发挥作用。在单人益智游戏中,树可以表示朝目标推进的各步操作;在调度问题中,树可以表示依次将作业分配给机器的过程;在路径规划中,树可以表示构建可行路径的过程。终局奖励可以反映成本、完成时间或约束满足情况。与直接操作完整解的通用优化器不同,MCTS 天然适合利用序贯分解结构:前面的选择会影响后续有哪些可能的选择。
在组合优化中,搜索目标往往不同于对抗性游戏。调度器需要的可能是搜索过程中发现的最佳完整调度方案,而不是在某种模拟策略下平均结果最好的动作。因此,一些变体会记录观测到的最大奖励、维护当前最优解,或将树搜索与局部改进过程结合起来。奖励的尺度也很重要:如果大多数模拟候选解都违反约束,并受到相同惩罚,搜索就很难获知哪些局部选择有用。针对具体领域设计的解补全方法,可以让评估结果更具区分度。
在机器人与控制领域,基于采样的规划可以比较不确定动力学条件下的动作序列。连续动作通常需要动作提议机制或渐进拓宽,而实时性要求则会限制树的深度和模拟次数。控制器可以只执行计划中的第一个动作,并在收到新的观测后重新搜索,这种安排与模型预测控制有关。不过,在模拟器中最大化奖励,本身并不能保证现实中的物理安全。如果失效会造成严重后果,可能还需要硬约束、经过验证的控制器或独立的安全机制。
MCTS 也被用于自动定理证明和程序构造的研究。在这些场景中,一个动作可以是应用一条推理规则、选择一种证明策略,或扩展一个尚未完成的表达式。完成的证明可以由证明助手检查,因此,相较于仅依靠学习得到的评分来判断的任务,最终结果是否正确有更明确的判定标准。困难往往在于反馈稀疏:在可用的计算预算内,大多数尚未完成的证明路径都无法产出定理。通过学习得到的动作提议和中间状态评估,可以帮助确定各分支的探索优先级;而检查器则能区分真正找到的证明与仅仅看似合理的文本。
围绕大语言模型构建的系统,同样可以对候选推理步骤、程序或工具交互进行树搜索。这类应用需要明确区分搜索结构与普通的重复生成。真正的 MCTS 实现会维护并更新可重复利用的决策分支上的统计信息;生成多个答案再从中选出一个,并不一定属于树搜索。此外,不可靠的评估器可能会奖励那些看似有说服力、实则错误的后续内容。在条件允许时,可执行测试、约束检查和形式验证能提供更可靠的信号,但搜索无法将缺乏可靠依据的评分函数变成正确性保证。
局限性、评估与未解问题
MCTS 的一个主要弱点在于,其效果取决于采样得到的后续行动与未来高水平行为之间的关联。在对抗性博弈中,一步棋可能击败几乎所有随机应对,却败于某个特定的战术序列。因此,即使这步棋的博弈论价值很低,它在搜索初期的平均收益也可能极高。如果只需几步就能找到使其落败的应对,这类情形通常称为浅层陷阱。精确的战术搜索可以迅速揭示这些陷阱,而采样则可能需要投入大量计算,才能充分覆盖那种决定性的应对。
长规划时域和稀疏奖励也会带来类似的发现难题。如果一种有效策略需要先采取许多单独看来没有前景的行动,之后才能获得奖励,搜索树可能不会为其分配足够的计算资源,从而无法发现这种策略。学习得到的价值函数可以减轻这一负担,但也会引入近似误差;当搜索访问的状态不同于训练时遇到的状态时,还可能出现分布偏移。如果评估器存在缺陷,延长搜索时间并不总是有益:搜索可能找到利用评估器错误的行动序列,而非真正改善目标的行动序列。当所优化的信号偏离预期目标时,这就与奖励黑客有关。
随机性任务还需要明确何为“好”。最大化平均回报,可能会使系统偏好一种有小概率造成严重损失的行动,而不是平均回报略低但更安全的行动。风险敏感型变体可以采用效用函数、尾部风险度量或显式的失败约束。这些变化既影响回传规则,也影响行动选择。仅凭样本均值,无法证明对罕见事件的估计已经足够充分,尤其是在模拟器产生此类事件的概率极低时。
实证评估应区分模拟效率与计算效率。如果一种方法使用了规模大得多的神经网络评估器,或成本更高的模拟推演,那么在迭代次数相同的条件下进行比较并不公平。在实际运行时间、硬件、内存和训练资源相同的条件下比较,可能得出不同的结论。在博弈实验中,使用随机种子、交替担任不同对局角色、进行足够多场比赛,以及估计不确定性,都有助于将真正的改进与采样波动区分开来。对于优化任务,应在多个问题实例上衡量解的质量,而不是根据少数有利示例作出推断。
消融研究尤为重要,因为实际系统结合了许多相互影响的组件:先验、探索规则、模拟推演策略、搜索树复用、并行机制,以及学习得到的评估器。被归功于搜索的改进,实际上可能来自额外的训练数据或更强的推理硬件。尚待研究的问题包括:如何在搜索深度与广度之间最优地分配计算资源,如何在后续策略不断变化时获得可靠的不确定性估计,如何借助学习得到的模型进行稳健规划,以及如何在严格的时间限制内找出根节点的最佳行动。答案取决于具体的决策问题:渐近一致性、战术可靠性、低延迟和样本效率是不同的性质,并不一定会同步改善。