在使用遗传局部搜索算法的局部可观测强化学习中，优化基于势能的奖励自动机

《Engineering Applications of Artificial Intelligence》：Optimizing potential-based reward automata in partially observable reinforcement learning using genetic local search

部分可观察强化学习环境下，提出基于遗传局部搜索的潜在奖励自动机方法，通过压缩探索轨迹优化自动机结构，提升学习效率与奖励积累，在七个基准环境中验证优于现有方法。

　　

朱正伟|陈志轩|朱晨阳|司文|王芳

中国常州市大学计算机科学与人工智能学院

摘要

部分可观测强化学习将强化学习框架扩展到代理对状态空间可见性有限的环境中，这使其在机器人技术和自动驾驶车辆导航等应用中尤为重要。然而，部分可观测强化学习的一个主要挑战是定义有效的奖励函数，以在部分可观测性的情况下指导学习过程。为了解决这一挑战，本文提出了一种利用遗传局部搜索方法构建基于潜力的奖励自动机的新方法。具体而言，我们的方法从压缩的探索轨迹表示中构建这些自动机，这些表示简洁地捕捉了关键决策点和必要的状态转换，同时消除了冗余步骤。通过优化轨迹样本并将代理轨迹缩短到其关键转换点，我们的技术显著降低了计算开销。形式上，我们将学习目标定义为一个优化问题，旨在最大化未来观测的对数似然性，同时最小化学习到的奖励自动机的结构复杂性。此外，通过结合基于价值的策略来估计奖励自动机内的潜在值，我们的方法提高了学习效率，并有助于识别最优奖励结构。我们在七个部分可观测的网格世界基准测试中对我们的方法进行了实证评估。实验结果表明，与现有的基于奖励自动机的技术相比，我们的方法具有更好的性能，表现出更快的学习速度和更高的累积奖励。此外，我们的遗传局部搜索算法在学习曲线和奖励积累方面始终优于比较的启发式方法。

引言

在许多现实世界场景中，代理在部分可观测的条件下运行，由于传感器限制、遮挡、环境不确定性或任务本身的复杂性，它们无法访问完整的系统状态。这种限制在包括自动驾驶、机器人技术和人机交互在内的广泛应用中普遍存在。例如，自动驾驶车辆在恶劣天气下经常面临能见度降低的问题（Valiente等人，2022年；Levinson等人，2011年）；执行搜索和救援任务的无人机必须在具有间歇性视觉反馈的非结构化环境中导航（Curtis等人，2023年）；仓库机器人必须在避开动态和遮挡障碍物的同时做出导航决策（Lauri等人，2022年）。在每种情况下，代理都必须根据不完整和噪声较大的观测数据进行推理和行动，这突显了专门为部分可观测环境设计的强化学习算法的必要性。

部分可观测强化学习（PORL）通过将环境建模为部分可观测马尔可夫决策过程（POMDP）来扩展传统的强化学习（RL）框架，以解决不确定性下的决策问题。然而，在POMDP中学习有效的策略存在几个挑战。首先，由于观测空间的非马尔可夫性质，代理必须使用历史信息来推断潜在状态（Toro Icarte等人，2023年）。这需要能够捕捉当前观测之外的时间依赖性的记忆机制。其次，在缺乏完整状态可见性的情况下，奖励函数的设计变得复杂得多。代理可能会错误地将观测与奖励关联起来，导致策略偏差，尤其是在奖励延迟或稀疏的环境中。例如，在一个代理必须依次收集钥匙来解锁房间的导航任务中，无法观察到环境的全局结构使得将当前行动与未来结果联系起来变得困难。如图1所示，代理必须探索未知的房间，按正确的顺序使用获取的钥匙，并返回起点，同时根据部分和延迟的反馈进行推理。

为了解决这些问题，我们提出了一种新的PORL框架，该框架直接从压缩的探索轨迹中学习基于潜力的奖励自动机（RA）。关键思想是使用压缩机制从轨迹数据中提取与决策相关的信息，从而在保留必要的状态-动作转换的同时减少内存使用。所得到的RA以结构化形式捕捉时间依赖性，并消除了手动设计奖励函数的需要。为了优化RA的结构，我们引入了一种遗传局部搜索算法，该算法在奖励表示的表达能力和自动机的复杂性之间取得了平衡。我们进一步结合了基于价值的估计技术，为RA状态分配潜在值，引导代理在不确定性下采取最优行为。学习过程被形式化为在最大化未来观测的对数似然性的同时惩罚自动机的复杂性，以防止过拟合。

本文的主要贡献总结如下：

• •
  我们提出了一种从压缩轨迹构建基于潜力的奖励自动机的方法，使得在部分可观测环境中可以自动指定奖励并进行时间抽象。
• •
  我们设计了一种遗传局部搜索算法，该算法在策略性能和模型复杂性方面对RA结构进行了优化。该算法促进了高效的内存整合和特定任务的奖励建模。
• •
  我们引入了一种基于价值的潜在估计策略，在RA框架内塑造奖励，从而提高了学习效率，而无需访问完整的状态空间。
• •
  我们在七个部分可观测的网格世界环境中进行了全面实验，与现有的基于RA的方法相比，我们在收敛速度、稳定性和累积奖励方面表现更优。我们还分析了自适应$?$
  -衰减策略对平衡探索和利用的影响，这些策略在不同环境复杂性下发挥作用。

本文的结构如下。第2节描述了与PORL和强化学习中奖励函数相关的相关工作。第3节介绍了工作的初步内容。第4节描述了我们的框架，该框架使用遗传局部搜索从压缩轨迹构建RA。第5节将我们提出的方法与七种不同的部分可观测环境中的现有技术进行了比较。我们还展示了遗传局部搜索相对于其他基于遗传的算法的优势。最后，我们在第6节总结了我们的工作并概述了未来的工作。

部分可观测强化学习

强化学习在完全可观测的环境中得到了广泛研究，通常使用MDP和各种算法（如Q学习、SARSA和策略梯度）进行建模（Jin等人，2023年；Zanette等人，2020年）。然而，在信息不完整的环境中，RL被建模为POMDP（Laurent，2008年）。

在POMDP中进行规划和学习存在显著的计算复杂性挑战。即使已知POMDP参数，计算最优策略也是一个PSPACE完全问题（

初步知识

强化学习代理从经验中学习策略。在部分可观测的环境中，底层模型通常假设为POMDP，如定义3.1中所定义。

定义3.1 POMDP

标准的部分可观测马尔可夫决策过程定义为一个元组, 其中：

• •
  $S$
  是一个有限的状态集，其中每个状态$s$代表环境中的一个可能情况。

•

$O$

是一个有限的观测集，其中每个观测$o$代表

使用遗传局部搜索学习奖励自动机

本文介绍了一种在部分可观测环境中学习基于潜力的奖励自动机的方法，该方法利用遗传局部搜索策略应用于压缩的代理轨迹。整个框架如图2所示。核心思想是压缩探索轨迹以提取必要的转换和决策点，从而在保留关键行为模式的同时显著降低计算开销。

我们将RA的构建形式化为一个优化问题

实验设置

在本节中，我们在七个部分可观测的环境中实证评估了我们的方法。首先，我们比较了遗传局部搜索与基于潜力的奖励自动机（GLS-PRA）以及使用双DQN（Icarte等人，2018年）和深度QRM（Icarte等人，2018年）的策略的学习性能。此外，我们还评估了遗传局部搜索（GLS）、带重启的局部搜索算法（LS）（Toro Icarte等人，2022年）和禁忌搜索（TS）（Icarte等人）的有效性

结论与未来工作

在这项工作中，我们提出了一个用于在部分可观测环境中学习奖励机制的框架，解决了标准深度强化学习方法常常无法克服的挑战。借鉴POMDP和RA的理论，我们定义了在部分可观测性下基于RA的策略合成所需的关键属性。通过将RA学习视为一个离散优化问题，我们开发了一种高效的奖励塑造方法，提高了学习稳定性和收敛性。

CRediT作者贡献声明

朱正伟：撰写——原始草稿、方法论、概念化。陈志轩：撰写——原始草稿、软件、数据整理。朱晨阳：撰写——审阅与编辑、可视化、验证、监督、资金获取。司文：撰写——审阅与编辑、可视化、验证、形式分析。王芳：撰写——审阅与编辑、监督、项目管理、资金获取。

利益冲突声明

作者声明他们没有已知的竞争财务利益或个人关系可能影响本文报告的工作。