Epistemic Exploration for Generalizable Planning and Learning inNon-Stationary Settings 在非平稳环境中，用于泛化规划和学习的认知探索
https://ojs.aaai.org/index.php/ICAPS/article/download/31489/33649
关键见解是，与其他方法不同，这种学习方法不等待随机探索生成p区分策略，而是通过利用关于模型中不准确部分的信息，积极鼓励探索
摘要
本文介绍了一种在关系型、非平稳随机环境中持续规划和模型学习的新方法。这种能力对于在不确定且不断变化的现实世界中部署序列决策系统至关重要。在具有未知（且非平稳）转移系统和变化任务的实际环境中，所提出的框架模拟了代理当前知识状态中的差距，并利用这些差距进行有针对性的调查性探索。使用这些探索收集的数据用于学习可泛化的概率模型，以解决当前任务，尽管环境动态不断变化。在几个非平稳基准领域的实证评估表明，这种方法在样本复杂性方面显著优于规划和强化学习基线。理论结果表明，当平稳性成立时，系统表现出理想的收敛特性。
1 引言
本文解决了在未知领域动态的非平稳随机环境中进行规划的问题。特别是，我们考虑了目标导向的代理未被提供一个封闭形式的模型来描述执行某个动作后可能产生的状态概率的问题。此外，这些概率可以在代理执行环境中的潜在未知时间步长时发生变化。这种环境在现实世界的规划系统中很常见。例如，一个自主仓库机器人应该能够在某些走廊因溢出物被阻塞或存储架布局因库存配置变化而改变时，通过不同的路径继续实现目标。目前，这些变化需要领域专家重新建模，从而限制了自动化规划方法的范围和可部署性。
由于需要在检测到差异时正确建模代理的知识不确定性，并进行有针对性的探索以改进代理的后续规划知识，这些环境在技术上具有挑战性。先前的工作研究了随机探索在解决非平稳性中的作用。例如，如果引入非平稳性的新颖事件的发生率相对于每个平稳动力学时期可用于学习的时间步长足够低，那么诸如带有ϵ-贪婪探索变体的Q-Learning等强化学习（RL）技术可以保证逐步收敛到最优策略。然而，这些方法可能会在样本效率上表现不佳，因为新数据的收集不容易集中在环境变化的部分。
我们提出了一个在非平稳环境中持续学习和规划的新框架（第3.1节），为这一范式开发了解决算法（第3.3节），并根据动态变化是否对代理已知以及代理是进行全面重新学习还是基于需求的学习，评估了它们在各种问题形式中的性能（第4节）。
我们的方法通过自主的数据收集、规划和模型学习过程解决了上述挑战。它从标准强化学习代理可用的输入开始（一个模拟器、动作名称和奖励生成器），但不是学习策略，而是与环境交互，首先学习一个面向解决当前目标的关系概率规划模型，然后使用它来计算解决方案策略。当检测到差异时，它会标记当前学习模型中不再准确的部分，并使用自动生成的认知引导策略进行调查性探索，以重新学习可能已变化的部分。
计算有用的调查性策略的问题是非平凡的。这被简化为一个完全可观察的非确定性（FOND fully-observable nondeterministic）规划问题（Cimatti, Roveri, and Traverso 1998），并在不与模拟器交互的情况下解决。然后执行计算出的调查性策略，并使用结果数据学习更准确的模型。尽管这些执行不专注于当前任务的策略学习，但它们用于学习和维护关系概率规划域描述语言（PPDDL）风格的模型。我们表明，（i）这显著提高了学习的可转移性和泛化性，（ii）由此产生的范式大大优于最先进的强化学习和现有的基于模型的强化学习范式。
我们的主要贡献是已知的第一个利用基于逻辑的内部概率模型在认知不确定性方面的信息来创建探索策略、学习更好的模型，并在转移系统变化时计算规划的方法。此外，这也是第一个将主动学习与认知探索交织在一起，以发现适合非平稳环境中任务转移的随机符号模型的方法。对基准领域的非平稳版本的实证分析表明，在这种环境中，我们的方法（i）显著降低了样本复杂性，相比最先进的基线；（ii）能够快速适应环境动态的变化；（iii）表现非常接近一个预先知道环境变化所有信息的预言机。
2 背景
关系马尔可夫决策过程（RMDPs）
关键见解是，与其他方法不同，这种学习方法不等待随机探索生成p区分策略，而是通过利用关于模型中不准确部分的信息，积极鼓励探索。我们将在第3.1节讨论如何注释这些组件。这导致了在收敛到模型M ≡ δ（即M转化为转移函数δ的封闭形式规范）时提高了样本效率。一旦识别出p区分策略，就可以通过执行策略η次来使用最大似然估计（MLE）估计概率，其中η是一个可配置的超参数，表示采样频率。
vanilla AQML有两个困难。首先，为了保证正确性，完整模型在一次传递中学习。其次，该框架假设模拟器的平稳性，并且查询合成过程在模型学习循环期间对环境动态变化不具有弹性。因此，当转移系统的只有小部分发生变化时，AQML无法有效利用学习到的信息来更新模型。
3 我们的方法：自适应模型学习
我们采用主动学习方法，因为它可以应对非平稳性。使用主动学习的现有方法样本效率低下，因为它们是全面学习者，从头开始重新学习。在基于主动查询的模型学习框架（AQML Active Querybased Model Learning framework）（Verma, Karia, and Srivastava 2023）的基础上，我们开发了一个可以在非平稳性存在的情况下工作的范式。现在我们首先描述我们解决的问题，然后详细概述我们的方法。
上述问题设置捕捉了许多现实世界场景，其中环境动态经常在情境中发生变化，即在代理主动解决一系列任务时，且不通知代理。例如，影响其摩擦力的夹持器上的液体溢出、导航路径被阻塞等事件是机器人无法控制的，并且可以随时任意变化。隐含地，这转化为代理间接优化一个具有相同目标但不同转移系统的新RMDP任务。总体目标是使所有任务都能以样本高效的方式解决，因此学习和转移知识至关重要。一个学习固定环境模型或无法检测到这种变化的代理可能会表现得很差或危险。
我们考虑了以下在非平稳性下持续规划的方法分类；（a）自适应与非自适应学习者，其中自适应学习者可以自动适应转移系统中的未知变化，而后者则不能，需要被告知变化已经发生，并且在某些情况下需要被告知具体发生了什么变化；（b）全面与基于需求的学习者，前者完全从头开始学习新模型，而后者仅对与当前模型不一致的转移进行更新。
我们通过不断学习和更新环境的PPDDL模型并使用它来完成任务，将规划和学习结合起来。我们开发了一个主动的、基于需求的学习者，可以自动检测并适应转移系统的变化。我们的方法主动监控模拟器执行，并在转移与当前模型不一致时通过定向探索进行样本高效主动学习。现在我们描述促进规划持续学习的组件。
3.1 非平稳性感知模型学习
我们显著改变了AQML框架，使其即使在模型学习过程中转移系统发生变化（因为使用模拟器生成策略轨迹）时也能工作，并使其能够选择性地正确学习与所学模型不一致的信息。我们通过始终监控模拟器的执行来实现这一点。如果一个转移τ = (s, a, s′)与所学模型M不一致，即τ ⇌ M，那么我们同时更新模型学习过程，因为现在需要合成一个新查询来解决不一致性。为此，我们识别动作a的先决条件（或效果）中与模型不一致的谓词p↑，然后将p↑添加到a的先决条件（或效果）中以重新学习。这也适用于作为模型学习过程一部分生成的策略轨迹中识别的不一致性。新的FOND问题将不会在动作a的任何形式的先决条件（或效果）中包含p↑，因此规划器需要为当前查询计算一个替代解决方案。
示例 如果一个谓词¬p↑ ∈ Prea，p ∈ s 且 s = s′，这意味着动作在模拟器上成功执行，并且先决条件¬p↑在当前学习模型M↑a中错误地表示，必须重新学习。然后我们将M+alpre和Ma⊗lpre添加到查询合成过程需要再次考虑的模型列表中。
3.2 拟合优度测试
在非平稳环境中操作时的另一个关键困难是，当转移本身在先决条件和效果方面是一致的，但来自显著不同的分布时。例如，两个具有相似先决条件和效果但仅在效果概率上不同的动作模型会影响代理解决任务的能力。
示例 在我们滑溜夹持器的运行示例中，随着滑动概率的增加，最优策略可能会切换到导航到人类操作员并与他们沟通以拾取物体。
如果仅使用MLE估计来计算概率，这种变化无法迅速反映，因为这些估计可能难以适应新分布。我们通过在规划和学习循环中包含拟合优度测试来缓解这一问题，这些测试主动监控分布是否发生了变化，并可以及时重新启动MLE估计过程。
我们使用皮尔逊卡方检验（Pearson 1992）来检测o.o.d.效果，如下所示。一旦为动作学习了模型Ma↑（或指定了新任务），我们为每个效果Eff[i] ∈ Ma↑初始化一个表项Freqa↑ [i] = 0。每当使用模拟器获得一个新的M一致转移(s, a, s′)时，我们识别索引i使得s′ = s Eff[i]− ∪ Eff[i]+。然后我们增加Freqa↑ [i]并使用皮尔逊卡方检验进行拟合优度测试，自由度为0。
3.3 持续学习与规划（CLaP）
我们持续学习PPDDL模型的方法有两个关键优势。首先，由于我们学习模型，Eqn. 1可以用于计算任务的策略，而无需从模拟器中收集经验。其次，提升的PPDDL模型具有可泛化性，可以零样本转移到具有不同对象名称、数量和/或目标的任务中。例如，前面描述的相同pick-up↑(rx, lx, bx)动作可以被具有不同数量机器人、位置和/或包裹的不同RMDP任务重用。这种方法使我们的方法能够高效地解决任务。
算法1描述了我们持续学习与规划的总体过程。该算法以RMDP任务M、模拟器∆、模拟器预算∆S、学习模型M↑和超参数H、η、β、θ（分别表示水平、采样计数、失败阈值和置信阈值）作为输入。请注意，在算法1的上下文中，M仅指定任务的初始状态s0和目标g。由模拟器表示的转移系统可以随时任意变化，但代理仍然将其视为相同的任务。算法1尝试使用学习模型M↑（第2行）使用现成的RMDP求解器（如LAO*（Hansen和Zilberstein 2001））计算M的策略π。如果使用M↑导出的π的转移图没有通向目标的路径，或者在一定阈值内未达到目标（第4-5行），代理使用模拟器对状态空间进行探索，以找到一个与M不一致的转移。最初，当学习模型为空（所有动作的先决条件和效果为空）时，这一步允许代理快速发现可以进行有用学习的转移。我们在实验中使用长度为H的随机漫步来进行这一探索步骤。如果在探索过程中发现不一致的转移，则使用第3.1节中的方法将几个需要考虑的模型添加到模型学习器中。这将导致模型学习被调用以解决不一致性并更新学习模型M↑（第7行）。我们注意到，如第3.1节所述，如果在模型学习期间识别出新的不一致性，它们也会被解决。由于模型已更新，计算新的策略（第8行）。
一旦完成任何学习步骤并计算出π，我们在模拟器上执行动作a = π(s)（第9-10行）。如果(s, a, ∆(s, a)) ⇌ M，则执行拟合优度测试以改进概率估计，如第3.2节所述（第13行）。不一致的转移总是为需要模型学习器解决的不一致性添加新模型（第15行）。如果达到目标或超过水平，模拟器重置为初始状态，并相应地增加总失败次数（第16-17行）。最后，一旦预算耗尽（第3行），返回学习模型（第20行），可用于解决未来的任务。
3.4理论结果
4 实验
我们在Python 3中实现了我们的方法（算法1），并在四个基准领域上进行了实证评估，使用单核Xeon E5-2680 v4 CPU，主频2.4 GHz，内存限制为8 GiB。我们发现，与基线相比，我们的方法显著提高了迁移性能。我们描述了用于进行实验的实证设置，随后讨论了获得的结果（第4.1节）。
领域 我们使用了四个基准领域，这些领域在各种国际概率规划竞赛（IPPC）中使用过。我们使用这些基准领域，因为它们的地面真值模型可用，并且我们使用这些领域合成了模拟器。我们简要描述了以下使用的领域。我们将每个领域称为D↑(|P↑|, |A↑|)，以指示领域中谓词和动作的总数。
Tireworld(4, 2) 是一个在多个IPPC中使用的流行领域。该IPPC基准的目标是从初始位置驾驶到目标位置（考虑到可能随机发生的爆胎）。
FirstResponders(13, 10) 是一个受紧急服务启发的领域。目标是扑灭所有火灾并治疗所有受害者。为此，规划代理需要能够计划到达火灾地点并扑灭火焰（根据需要重新装水），并治疗受害者，如果伤势太严重，则将他们运送到医院。
Elevators(9, 10) 是确定性Miconic（Long和Fox 2003）领域的随机扩展，其中有几个新目标，如收集硬币，以及限制导航的元素，如井道和门。
Blocksworld(5, 4) 是一个环境，目标是安排积木以特定的配置。IPPC变体是ExplodingBlocks，其中在堆叠积木时桌子可能会被摧毁。我们尝试为ExplodingBlocks生成问题，但未能成功，因此使用了遍历版本，其中堆叠积木有机会掉落在桌子上。尽管如此，我们引入的非平稳性（如下所述）通常会引入死端状态（即无法达到目标的状态）。
任务生成 基准套件中的所有任务共享一个转移系统，据我们所知，没有官方的问题生成器可以引入非平稳性并为其生成任务。因此，我们通过生成由更改先前生成的任务领域文件中随机选择的动作而获得的新领域文件来引入非平稳性。我们在所选动作的先决条件和效果中进行了0-3次更改，通过添加或删除谓词或修改动作模型中的现有谓词，并确保至少进行一次更改。这种引入非平稳性的方法导致最终任务的转移系统与基准任务显著不同，多个动作发生了变化。
任务设置 我们生成了五个不同的任务M0, . . . , M4，具有不同的初始状态和目标。M0是基准任务，其他任务使用广度优先搜索生成。我们对所有任务使用γ = 0.9和水平H = 40。
基线 我们使用Q-Learning作为非迁移强化学习基线。我们还使用了一个Oracle，它完全访问模拟器的封闭形式模型，并使用LAO∗计算策略。Oracle基线提供了任何算法可达到的性能上限。
我们利用QACE（Verma, Karia, and Srivastava 2023），一种最先进的随机模型学习器，作为基于AQML的模型学习算法来开发我们的第二个基线。我们修改了QACE以检测转移系统的变化，从而创建了一个名为Adaptive QACE的最先进自适应基线。当检测到不一致时，Adaptive QACE调用QACE从头开始重新学习模型。扩展版本（Karia et al. 2024）包括一个称为Non-adaptive QACE的消融，其中QACE在转移系统发生变化时被告知。
我们还考虑了ILM（Ng和Petrick 2019），因为它可以学习嘈杂的指示规则，但由于付出了巨大努力（并联系了作者），我们无法使用它。
我们将基线与我们的系统（CLaP）进行比较：一个实现算法1的主动、自适应、基于需求的学习者。
超参数 我们对Q-Learning使用α = 0.3，对基于AQML的方法和CLaP使用η = 100。此外，我们对CLaP使用β = 10和θ = 0.05。
4.1 结果分析
如第2节所述，当达到目标状态时，我们认为任务已完成。我们对每个任务使用模拟器预算∆S = 100k。转移系统在∆S步内保持平稳。然后，模拟器加载新任务Mi+1和新转移系统δi+1。
图1显示了我们实验中获得的结果，使用了10个不同的随机种子。我们分析结果以回答以下问题。
a. CLaP是否样本高效？
b. CLaP解决方案是否高效？
c. CLaP解决方案是否可泛化？
评估指标 我们使用以下评估指标来回答上述问题；我们通过绘制学习曲线来回答（a），展示在学习过程中完成了多少任务；我们通过比较策略质量来回答（b），在每k = 100模拟器步骤中，我们冻结计算的策略并生成10个策略轨迹，每个轨迹从任务的初始状态s0开始，最大水平为40。这些模拟不计入模拟器预算。我们报告在此过程中获得的平均奖励；我们通过计算自适应延迟（Balloch et al. 2022）来回答（c），该延迟衡量在环境中的多少步后，稳态性能收敛到Oracle的性能。我们将稳态性能定义为在环境中所需的步数，之后每集的性能始终在Oracle的2σ范围内。
从图1可以清楚地看出，我们持续学习与规划（CLaP）的方法在样本效率上优于非迁移（Q-Learning）和基于模型的重新学习（Adaptive QACE）。
(a) 样本效率 我们在图1(a)中的结果显示，CLaP的样本复杂性远优于基线。FirstResponders、Elevators和Blocksworld的学习曲线表明，我们的方法可以完成比基线多得多的任务。Q-Learning不学习和转移任何知识，因此需要收集大量经验来解决任务。
当转移系统变化时，Adaptive QACE无法高效地修正模型，因为它需要重新学习所有动作以收敛。这种全面学习者的缺点在Elevators领域的结果中得到了突出，即使Q-Learning也优于Adaptive QACE。对于Elevators领域，转移系统的变化使得一些任务无关的动作可以从只能通过非常长的水平到达的状态执行。Adaptive QACE耗尽了模拟器预算，试图重新学习这些任务无关的动作，因此无法解决任务。另一方面，CLaP仅在必要时懒惰地评估是否学习模型的一部分，并能够快速修正学习模型并计算出可以解决任务的策略。这些趋势也可以在FirstResponders中看到，每当观察到不一致时，Adaptive QACE必须从头开始重新学习10个动作。
(b) 更好的任务性能 图1(b)显示，CLaP策略的平均奖励非常接近Oracle的。这表明我们学习的模型通常是转移系统良好的近似。CLaP的策略在我们评估的所有任务中收敛到Oracle的策略。
(c) 更好的可泛化性 我们的方法具有显著更低的自适应延迟（图1(c)），即CLaP能够比基线更高效地利用和转移学习到的知识，基线需要大量样本才能收敛到Oracle的性能。例如，CLaP在Blocksworld任务M1和M2之间零样本转移（自适应延迟为0），无需学习即可解决任务M2，同时匹配Oracle的性能。在需要适应的情况下（例如，Blocksworld任务M0、M1和M2、M3之间），CLaP少样本学习所需的知识，以实现与Oracle相似的策略质量来完成任务。总的来说，CLaP的自适应延迟在所有基线中是最好的。
我们还进行了一项定向实验，以评估我们的方法对变化分布的适应性。为此，我们从一个两臂老虎机领域生成两个任务。拉动任何一个杠杆都会随机将代理带到目标。因此，最优策略是反复拉动到达目标概率最高的杠杆。在第一个任务中，第一个（第二个）杠杆的成功概率为0.8（0.2）。在第二个任务中，分别为0.1（0.9），先决条件和效果不变。CLaP利用拟合优度测试，因此能够适应这种分布变化，并在任务一（二）中选择杠杆1（2）。Adaptive QACE无法适应这种变化，继续在任务二中使用杠杆1。这导致其策略比CLaP的策略差9倍，总体上仅实现了约950个目标，而CLaP实现了约1550个（每个任务∆S = 1000，η = 10）。图表可在扩展版本（Karia et al. 2024）中找到。
局限性和未来工作 目前，CLaP在模型学习过程中不考虑任务目标（算法1的第7行）。关于目标对模型进行乐观估计可能允许模型学习器花费更少的样本来学习一个可以完成任务的模型。我们没有考虑可能提前提供的转移系统变化或目标。CLaP可以利用这些信息来制定课程，以便优先学习有用且不太可能改变的动作，即使它们不贡献于当前任务的目标。
PPDDL模型具有表达性限制，例如难以建模外源性效应。未来的工作可以使用归纳逻辑编程等技术来学习比PPDDL模型更具表达性的模型。
PPDDL models have expressiveness limitations such as difficulty in modeling exogenous effects. Future work could use techniques like inductive logic programming to learn models that are more expressive than PPDDL models.
何时从头开始学习 与Adaptive QACE相比，Tireworld领域没有太多性能提升。这是因为Tireworld是一个只有2（4）个需要学习的动作（谓词）的小领域。设计启发式方法来评估从头开始学习是否比修正模型更容易是一个有趣的问题，我们将其留给未来的工作。
5 相关工作
在强化学习（RL）中，已有大量关于迁移（Mnih et al. 2013; Schulman et al. 2017）和非平稳性（在RL文献中通常称为新颖性）的工作。我们关注的是在RMDP任务之间进行迁移的方法。Tadepalli, Givan, and Driessens (2004) 提供了关系强化学习方法的广泛概述。
基于模型的强化学习 Dyna框架（Sutton 1990）构成了几种基于模型的强化学习（MBRL）方法的基础。Ng和Petrick（2019）使用合取的一阶特征来学习模型和可泛化的策略，这些策略可以转移到相关的RMDP类中。他们的方法不执行引导探索来解决模糊性。REX（Lang, Toussaint, and Kersting 2012）使MBRL能够自动自主地学习任务。这种方法的一个挑战是学习准确的模型，因为使用REX时探索可能很稀疏。V-MIN（Mart´ınez et al. 2017）通过在无法找到预期值大于某个阈值的策略时向教师请求演示，将模型学习和规划与RL结合起来。教师的可用性限制了这种方法的迁移能力。Taskable RL（TRL）（Illanes et al. 2020）和RePReL（Kokel et al. 2023）展示了如何使用选项框架的分层强化学习（HRL）进行TRL。他们使用符号计划来指导RL过程。这种方法需要作为输入提供的模型，而不是学习的。相比之下，我们通过主动学习过程生成自己的数据来学习模型。
非平稳环境下的模型学习 GRL（Karia and Srivastava 2022）训练神经网络来学习反应策略，这些策略可以转移到具有不同状态空间的同一领域的问题中。他们的方法仅限于状态空间的变化，无法适应转移动态的变化。Nayyar, Verma, and Srivastava（2022）和Musliner et al.（2021）学习PDDL模型，而像Sridharan和Meadows（2018）以及Sridharan, Meadows, and Gomez（2017）这样的方法使用Answer Set Prolog来表示领域知识。这些方法在非平稳环境中工作，可以集成到交错学习和规划循环中。然而，它们只学习确定性模型。Bryce, Benton, and Boldt（2016）解决了在给定用户心理模型的先验知识的情况下，使用粒子滤波学习用户更新心理模型的问题。然而，他们假设被建模的实体可以在需要时告诉学习系统学习模型中的缺陷。Eiter et al.（2010）提出了一种更新以图形形式表示状态空间的动作法的框架。他们假设变化只能发生在效果中，并且关于状态空间和可能发生变化的效果的知识可以提前获得。在开放世界环境中，有许多关于适应符号模型以适应RL新颖性的工作（Goel et al. 2022; Balloch et al. 2023; Sreedharan and Katz 2023; Mohan et al. 2023）。这些方法仅限于确定性设置，或者只能从被动收集的数据中学习新模型。
6 结论