基于回答集编程的强化学习抽象

# 基于回答集编程的强化学习抽象方法
来源：https://arxiv.org/html/2605.31444

###### 摘要

强化学习（RL）使自主智能体能够从经验中学习策略，但现实问题通常涉及巨大的状态空间，导致学习和泛化面临挑战。因此，抽象和近似至关重要。关系强化学习（RRL）提供了一种对对象及其关系进行推理的方法，Martijn van Otterlo提出的CARCASS框架展示了如何利用逻辑表示对一阶领域中的马尔可夫决策过程（MDP）进行建模。CARCASS最初用Prolog实现，利用领域知识创建强大的抽象。我们探索了回答集编程（ASP）——一种比Prolog更丰富且完全声明性的建模语言——来实现CARCASS的抽象。我们在两个领域（积木世界和MiniGrid）的案例研究中评估了基于ASP的实现。结果表明，使用ASP的CARCASS为构建强化学习抽象提供了一种有前景的方法，特别是在领域知识可用的情况下。¹¹我们的实现可在https://github.com/rbankosegger/RLASP-core获取。更多材料（数据、编码、扩展文档）见：https://www.bankosegger.at/iclp26/。

###### 关键词：关系强化学习，ASP，状态-动作空间抽象

## 1 引言

*强化学习*（RL）[Sutton and Barto2018 (https://arxiv.org/html/2605.31444#bib.bib37)]已成为人工智能的核心范式，为智能体通过与环境的交互学习行为提供了原则性框架。通过将序列决策形式化为马尔可夫决策过程（MDP），RL使智能体能够通过试错改进行为，以累积奖励最大化为导向。尽管这一范式已在重要实际应用中取得了显著成果，但现实问题通常涉及巨大的状态和动作空间，使得朴素学习方法难以处理。因此，应对这种维度灾难的有效技术（如抽象和近似）不可或缺。近似方法（例如深度Q学习[Mnihet al.2015 (https://arxiv.org/html/2605.31444#bib.bib130)]）旨在学习期望长期奖励的紧凑表示，通常使用深度神经网络，从而实现在大型或连续状态空间上的泛化。然而在实践中，这通常需要大量训练数据，且学习可能不稳定[Sutton and Barto2018 (https://arxiv.org/html/2605.31444#bib.bib37), 第11.3章]。

*关系强化学习*（RRL）通过使用一阶逻辑引入针对复杂问题领域的强抽象，解决了部分局限性。其核心思想是将表示扩展到一阶设置，从而能够自然地用对象及其关系描述环境[van Otterlo2005 (https://arxiv.org/html/2605.31444#bib.bib103)]。这种方法的主要优势在于支持跨相似状态的泛化，甚至可以将学到的知识迁移到相关任务。一种根植于逻辑编程的RRL方法是由Martijn van Otterlo (2004 (https://arxiv.org/html/2605.31444#bib.bib102))提出的CARCASS框架（即“基于关系合取的状态-动作空间紧凑抽象”）。CARCASS旨在通过将抽象状态表示为一阶文字（可能附加背景知识）的合取，并将其与一组可行动作相关联，来抽象状态-动作空间。因此，一个抽象是一个有序规则列表，形式为*状态* → {动作1, ..., 动作n}，每条规则描述一个由状态和可用动作刻画的情境。例如，规则 clear(X), clear(Y), on(Y,0) → {move(X,Y), move(Y,X)} 表示一个抽象的积木世界状态，其中两个积木X和Y是清空的，并且可以互相堆叠。然后可以通过例如在抽象状态-动作空间上进行Q学习[Watkins and Dayan1992 (https://arxiv.org/html/2605.31444#bib.bib125)]来学习*策略*（在给定状态下选择什么动作）。

CARCASS的关键优势之一是其能够在抽象规则中利用领域知识，从而减少状态-动作空间的有效大小，并支持跨相关情境的泛化。该框架最初用Prolog实现，利用SLDNF-解析来处理状态和动作上的一阶推理[van Otterlo2009 (https://arxiv.org/html/2605.31444#bib.bib113)]。在此基础上，我们探索了回答集编程（ASP）[Brewkaet al.2011 (https://arxiv.org/html/2605.31444#bib.bib88)]——一种丰富且完全声明性的建模语言——来重新审视CARCASS。²²纯净Prolog在原则上是声明性的，但实际中许多实现依赖于过程性特性（如失败即否定、截断或规则排序）来达到效率。ASP是一种基于逻辑的知识表示与推理框架，具有简洁但表达力极强的建模语言。与Prolog不同，ASP程序的意义独立于规则顺序以及规则体中的文字顺序。它支持非单调推理、不完全知识下的推理、偏好与优化表达，以及动作与变化的建模，因此特别适合描述RRL中的状态抽象。

用ASP重新实现CARCASS凸显了几个实际优势。可接受的状态、转移和优化标准可以在高层声明性地指定，无需显式的过程性搜索策略。默认值和完整性约束得到了自然支持，从而允许简洁且鲁棒的编码，而如果用Prolog实现，则需要更多算法性和控制密集型的实现。这也使得能够直接表示复杂的推理模式，包括部分可观测性、非确定性和基于偏好的选择，领域约束直接表达在规则中。在本工作中，我们引入了一种通用的ASP抽象编码方法，并通过两个案例研究进行评估。第一个案例是积木世界，一个经典的规划问题，涉及堆叠积木以达到期望配置；第二个是MiniGrid，一套网格世界导航任务，包含不同的子任务（如收集钥匙和开门以到达目标）。这两个领域的状态空间在无抽象的情况下都大得不可行。因此，我们的主要贡献总结如下：

1.  我们引入了一种通用的ASP编码CARCASS抽象的方法，展示了完全声明性且表达力强的建模语言如何实现关系状态-动作抽象；
2.  此外，我们展示了如何将基于ASP的CARCASS抽象用于在线学习；
3.  我们在两个案例研究（积木世界和MiniGrid）中评估了基于ASP的实现。实验表明，在抽象表示上使用Q学习，可以一致地学习到高质量策略。与不使用抽象相比，这些策略也可以在显著更少的样本中获得。

总之，我们的结果表明，使用ASP的CARCASS为构建强化学习抽象提供了一种有前景的方法，特别是在领域知识可用的情况下。

本文其余部分组织如下。在第二节 (https://arxiv.org/html/2605.31444#S2) 的预备知识之后，我们在第三节 (https://arxiv.org/html/2605.31444#S3) 介绍基于ASP的CARCASS抽象编码方法。第四节 (https://arxiv.org/html/2605.31444#S4) 和第五节 (https://arxiv.org/html/2605.31444#S5) 致力于案例研究，随后在第六节 (https://arxiv.org/html/2605.31444#S6) 进行实证评估（包括设置、结果和讨论），其中还涉及ASP与Prolog之间的建模差异。在第七节 (https://arxiv.org/html/2605.31444#S7) 中，我们回顾相关工作，并在第八节 (https://arxiv.org/html/2605.31444#S8) 总结并展望未来工作方向。

## 2 预备知识

接下来我们回顾逻辑编程（SLDNF-解析和ASP）、强化学习（关系MDP和Q学习）以及CARCASS框架的相关概念。

### 2.1 逻辑编程

我们假设一个一阶语言，包含常量c、函数项f(t̄)和谓词原子p(t̄)，基于PL1-签名Σ=(Func, Pred)和一个变量集合Var={V1,...,Vm}，其中t̄=t1,...,tn是与f或p的元数匹配的项列表。一个*naf-文字*是原子p(t̄)或带有失败即否定的表达式not p(t̄)。一个*正规规则*形式为 h ← b1,...,bn.，其中h是原子，b1,...,bn是naf-文字。一个*正规程序* P={r1,...,rn}是一组正规规则。*替换* θ: Var→Term 从变量集到项集的应用按通常方式定义。不含变量的句法对象称为*基的*。给定程序P和一个*正规目标* ← b1,...,bn.，则P∪{← b1,...,bn.}的*SLDNF-反驳*记为 P ⊢_{SLDNF} b1,...,bn [Nienhuys-Cheng and de Wolf1997 (https://arxiv.org/html/2605.31444#bib.bib83), 第8章]。

基于签名Σ=(Func, Pred)，我们用U(Σ)表示在Func上的Herbrand全域，用B(Σ)表示在U(Σ)和Pred上的Herbrand基，用I(Σ)=2^{B(Σ)}表示Herbrand解释的集合。在一个解释I∈I(Σ)中，原子p(t̄)为*真*如果p(t̄)∈I，为*假*如果p(t̄)∉I。我们将ASP程序视为*ASP-Core-2输入语言格式* [Calimeriet al.2020 (https://arxiv.org/html/2605.31444#bib.bib35)] 中定义的，具有通常的特性如强否定、析取规则头和优化。特别地，我们的编码使用了选择规则、聚合和弱约束。程序P的所有回答集的集合记为AS(P)。

### 2.2 强化学习

强化学习[Sutton and Barto2018 (https://arxiv.org/html/2605.31444#bib.bib37)]是一个离散时间的随机控制过程，由*任务环境*的动态和学习*智能体*的动作驱动。在每个时间点t，智能体感知环境的当前*状态* S_t，并采取一个*动作* A_t。环境基于动作的效果转移到一个新状态 S_{t+1}，并获得一个*奖励* R_{t+1}。结果是一个交互历史 H=(S_0, A_0, R_1, S_1, A_1, R_2, S_2, ...)。智能体的性能通过*γ折扣回报* G_t ≐ ∑_{k=0}^{∞} γ^k R_{t+k+1} 衡量。

任务环境形式化为一个*关系马尔可夫决策过程（RMDP）* [van Otterlo2009 (https://arxiv.org/html/2605.31444#bib.bib113), p. 168]。给定PL1-签名Σ=(Func, Pred_S ∪ Pred_A)，一个RMDP包含状态集S ⊆ I((Func, Pred_S))（这些状态是Herbrand解释）、动作集A ⊆ B((Func, Pred_A))（每个动作是一个原子）、以及奖励集R ⊆ R。对于每个状态s∈S，定义可行动作集A_s。可接受的状态-动作对集合为Ψ ≐ {(s,a) | s∈S, a∈A_s}。环境的*动态*由转移到状态s'并获得奖励r的概率p(s', r | s, a)定义，即在状态s执行动作a后，有 S_{t+1}, R_{t+1} ~ p(· | S_t, A_t)。结合折扣率γ，一个RMDP因此是一个元组 M = (S, A, R, Ψ, p, γ)。我们进一步定义逻辑程序 P_s ≐ { p(t̄). | p(t̄)∈s } 和 P_{A_s} ≐ { p(t̄). | p(t̄)∈A_s }。

###### 例1 (积木世界). 考虑一个3积木世界设置 [Slaney and Thiébaux2001 (https://arxiv.org/html/2605.31444#bib.bib80)]，如图1 (https://arxiv.org/html/2605.31444#F1) 所示。状态使用谓词 on(B,L) 表示积木B在位置L之上；以及 goal(B,L) 表示智能体的任务，即必须达到一个状态使得B在L之上。所有动作基于 move(B,L)，表示将积木B移动到新位置L。可行动作对应于可执行的移动，例如 A_{s1} = {move(2,1), move(1,2), move(1,table)}。对于这个特定的RMDP，move动作的效果是确定性的，并根据标准积木世界动态导致on原子的插入和删除。goal原子属于每个状态，且不受移动影响。RMDP的任务通过奖励结构编码：当达到所有积木按升序堆叠的状态（即s2）时奖励为99，否则为-1。折扣率γ=1。

（图1 caption翻译：
s1 = {on(0,table), on(1,0), on(2,table), goal(0,table), goal(1,0), goal(2,1)}
a1 = move(2,1)
s2 = {on(0,table), on(1,0), on(2,1), goal(0,table), goal(1,0), goal(2,1)}
图1：一个3积木世界RMDP。在状态s1中采取动作a1导致转移到s2。）

一个*策略* π(a|s) 定义了在状态s下选择动作a的概率。策