Answer-Set-Programming-based Abstractions for Reinforcement Learning

문제 정의
강화 학습(RL)은 에이전트가 상호작용을 통해 정책을 학습할 수 있게 하지만, 실제 응용 분야에서는 거대한 상태 및 행동 공간으로 인해 단순한 학습 접근 방식으로는 다루기 불가능한 경우가 많습니다. Deep Q-Learning과 같은 근사 방법론은 일반화를 제공하지만, 방대한 양의 학습 데이터를 요구하거나 불안정성을 보일 수 있습니다. 관계형 강화 학습(Relational Reinforcement Learning, RRL)은 객체와 그 관계에 대한 1차 논리를 활용하여 이러한 한계를 해결하며, 유사한 상태 간의 일반화를 촉진합니다. 구체적으로, van Otterlo(2004)의 CARCASS(Compact Abstraction using Relational Conjunctions for Aggregation of State-action Spaces) 프레임워크는 논리적 추상화를 사용하여 마르코프 결정 과정(MDP)을 모델링합니다. 그러나 기존의 CARCASS 구현은 Prolog와 SLDNF-resolution에 의존하는데, 이는 원칙적으로는 선언적이지만 효율성을 위해 프로시저적 특징(예: 규칙 순서 또는 cut)을 필요로 하는 경우가 많으며, 비단조 추론(nonmonotonic inference), 최적화 및 선호도 처리에 대한 네이티브 지원이 부족합니다.

방법론
저자들은 ASP(Answer-Set Programming)를 사용하여 CARCASS 프레임워크를 재구현하는 일반적인 방법을 제안합니다. ASP는 비단조 추론, 최적화 및 제약 조건을 지원하는 완전 선언적 논리 기반 지식 표현 언어입니다.

1. ASP를 이용한 CARCASS 인코딩: 저자들은 추상 상태와 상태-행동 쌍을 기저 항(ground terms)에 매핑하는 라벨링 함수를 정의합니다. 이들은 다음과 같이 구성된 모듈형 인코딩을 구축합니다:

   • 프로그램($P_{\hat{s}_i}$): 리터럴로 구성된 규칙을 통해 개별 추상 상태를 인코딩하며, 이 규칙의 본문은 해당 추상 상태를 정의하는 리터럴로 구성됩니다.
   • 프로그램($P_{\hat{s}_i, \hat{a}_{i,j}}$): aCov 원자(atom)를 통해 구체적인 행동을 추상적 행동과 연결함으로써 추상 상태-행동 쌍의 피복 관계(covering relation)를 인코딩합니다.
   • 결정 리스트 메커니즘($P_{\hat{C}}$): 하나의 구체적 상태당 정확히 하나의 피복되는 추상 상태를 선택하기 위한 선택 규칙(choice rule)과, 선택이 정해진 순서(낮은 인덱스 우선)를 따르도록 보장하는 제약 조건을 사용합니다.
   • "빈" 추상 상태($\hat{s}_\infty$): 특정 규칙에 의해 커버되지 않는 모든 상태를 커버하는 가장 높은 인덱스를 가진 상태로, 기본 폴백(fallback) 역할을 수행합니다.

2. 온라인 학습 통합: 저자들은 이 인코딩을 온라인 Q-러닝 루프(알고리즘 2)에 통합합니다. 주어진 구체적 상태에 대해, ASP 솔버는 피복되는 추상 상태와 허용 가능한 추상 행동 집합을 결정하기 위해 최적의 answer set을 계산합니다. 그 후 에이전트는 선택된 추상 행동에 의해 커버되는 구체적 행동 집합에서 구체적 행동을 선택하고, 추상 상태-행동 쌍의 Q-값을 업데이트합니다.

3. 배경 지식: 이 프레임워크는 복잡한 속성(예: 경로 탐색, 타워 완결성)을 사전에 계산하거나 절차적으로 구현할 필요 없이, 추상화 과정 내에서 직접 추론할 수 있도록 배경 지식($P_B$)을 포함할 수 있게 합니다.

주요 기여

1. 일반 인코딩 방법: 본 논문은 CARCASS 추상화를 ASP로 인코딩하는 체계적인 방법을 소개하며, 어떻게 완전한 선언적 언어가 관계적 상태-행동 추상화를 실현할 수 있는지 보여줍니다.
2. 온라인 학습 적응: 저자들은 동적인 추상 상태 및 행동 선택을 처리하면서 ASP 기반 CARCASS 추상화를 온라인 Q-러닝 환경에서 활용하는 방법을 보여줍니다.
3. 경험적 평가: 구현된 모델은 두 가지 서로 다른 도메인에서 평가되었습니다:
   • Blocks World: $n$-블록 쌓기 작업으로, 추상화는 $n$의 크기와 상관없이 상태-행동 공간을 상수 크기로 축소합니다.
   • MiniGrid: 그리드 월드 내 탐색 작업 세트(예: Door Key, Multi Room)로, 배경 지식을 사용하여 경로 상의 다음 노드를 기준으로 추상 상태를 구축합니다.

결과
경험적 평가는 20-blocks world와 세 가지 MiniGrid 환경에서 추상 Q-러닝과 구체적 Q-러닝을 비교합니다.

• 안정성: 추상 Q-러닝은 초기 학습 후 중앙값 수익(median returns)과 사분위 범위가 높게 유지되며 일관된 안정성을 보인 반면, 구체적 Q-러닝은 복잡한 환경에서 상당한 변동을 보이거나 수렴에 실패했습니다.
• 품질: 추상 Q-러닝은 높은 성공률(예: MiniGrid 작업의 마지막 500 에피소드에서 거의 100%)을 달却하였으며, 이는 동일한 시간 내에 양의 수익을 달성하지 못한 구체적 Q-러닝을 크게 상회하는 결과입니다.
• 샘플 효율성: 추상 방식은 구체적 방식에 비해 고품질 정책을 학습하는 데 훨씬 적은 에피소드가 필요했습니다. 예를 들어, 20-blocks world에서 추상 학습은 에피소드 376에서 양의 중앙값 수익을 달성한 반면, 구체적 학습은 여전히 베이스라인의 음수 수익에 머물러 있었습니다.
• 모델링 차이: MiniGrid 케이스 스터디의 경우, ASP 인코딩은 경로 탐색 및 제약 조건을 압축적이고 선언적으로 명시할 수 있게 한 반면, 대응하는 Prolog 구현은 명시적인 알고리즘 탐색(너비 우선 탐색)을 필요로 했습니다. 이는 문제 명세와 제어 로직을 분리하는 데 있어 ASP의 이점을 강조합니다.

의의 및 주장
본 논문은 ASP로 구현된 CARCASS가 특히 도메인 지식이 가용한 경우, RL에서 추상화를 구축하는 유망한 접근 방식임을 결론짓습니다. 저자들은 ASP 기반 추상화가 다음과 같은 기능을 지원함으로써 Prolog 기반 CARCASS의 유연한 대안이 될 수 있다고 주장합니다:

• 일반화: 관계적 표현을 통한 일반화.
• 행동 제한: 선언적 제약 조건을 통한 제한.
• 문제 분해: 복잡한 추론 패턴(경로 탐색이나 타워 분석 등)을 규칙에 직접 인코딩.
• 고급 추론: 비단조 추론, 최적화 및 불완전한 지식 하에서의 추론 포함.

저자들은 학습된 정책이 수용 가능한 품질이며 더 적은 샘플로 학습되지만, 일반적으로 최적 정책으로의 수렴을 보장하지는 않으며, 추상화 자체가 NP-hard 플래닝 문제(Blocks World 사례에서 최적성을 희생하고 트랙터빌리티를 취한 것처럼)에 대해 최적 정책을 보존한다는 보장은 없다고 조심스럽게 언급합니다. 본 연구는 정교한 정책 학습을 지원하는 관계형 RL을 위한 지식 기반 프레임워크를 향한 단계로서 자리매김하고 있습니다.