기술 요약: 일반화를 위한 계획에서의 학습과 탐색

문제 정의

결합적 일반화는 심층 강화 학습 (DRL) 의 핵심 과제로 남아 있으며, 여기서 정책이나 가치 함수는 공통 문제 구조로 정의된 분포 외 시나리오에 일반화되어야 합니다. 고전적 계획은 기본 관계 구조 (술어와 행동 스키마) 가 고정되고 명시적이지만, 인스턴스는 개체 수, 초기 상태, 목표가 다양하게 변하기 때문에 이 문제를 테스트하기 위한 이상적인 장을 제공합니다.

그러나 표준 DRL 접근법은 희소 보상 계획 도메인에서 어려움을 겪습니다. LRTA* 또는 RTDP 와 같은 RL 알고리즘에서 일반적인 실시간 탐색 (반복적인 상태 간 전이) 은 이러한 설정에서 계획을 찾는 데 비효율적입니다. 반면, 고전적 계획기는 최우선 탐색 (예: A*, WA*) 을 사용하지만 수동으로 설계된 휴리스틱에 의존합니다. 최근 연구는 일반 정책이나 휴리스틱을 학습하려는 시도를 했으나, 기존 방법들은 종종 실시간 탐색, 전문가 시연에 대한 지도 학습, 또는 사후 재표시 (hindsight relabeling) 에 의존하여, 다양한 문제 크기에 걸쳐 제로샷 일반화를 달성하기 위해 탐색과 학습이 서로를 강화하는 자기 개선 루프를 확립하지 못했습니다.

방법론: 계획에 대한 일반화된 탐색 (GSP)

저자들은 학습된 일반 행동 가치 함수 ($Q_\theta$) 를 학습하기 위해 최우선 탐색과 Q-러닝을 결합한 자기 개선 프레임워크인 GSP를 제안합니다.

핵심 루프

1. 탐색 유도 학습: 실시간 탐색 대신 GSP 는 훈련 인스턴스를 해결하기 위해 가중 A (WA)**를 사용합니다. 탐색은 현재 학습된 $Q_\theta(s, a)$ 값에 의해 안내됩니다.
2. 데이터 생성: WA* 가 노드를 확장함에 따라 전이 (transitions) 의 재생 버퍼를 생성합니다. 중요한 점은 탐색이 표준 RL 이 lacking 하는 감독 신호를 제공한다는 것입니다:
   • 목표 경로: 목표에 도달하면 알고리즘은 백트래킹하여 솔루션 경로상의 쌍에 실제 목표까지의 반환 값을 할당합니다.
   • 죽은 길 (Dead-Ends): 상태가 적용 가능한 행동이 없는 죽은 길인 경우, 부모 쌍에 고정된 페널티 반환 값을 할당합니다.
   • 하한선: 탐색은 솔루션 경로에서 마주친 모든 상태 - 행동 쌍에 대한 최적 반환 값의 하한선을 제공합니다.
3. Q-러닝 업데이트: $Q_\theta$ 네트워크는 이러한 탐색에서 파생된 타겟을 사용하여 업데이트됩니다. 목표 경로 쌍의 경우, 타겟은 $\max(R, \hat{y})$이며, 여기서 $R$은 탐색에서 파생된 하한선이고 $\hat{y}$는 표준 부트스트랩 타겟입니다. 이는 가치 추정이 탐색이 이미 달성 가능하다고 증명한 값 아래로 떨어지는 것을 방지합니다.
4. 인스턴스 선택: 학습 효율성을 최적화하기 위해 프레임워크는 (해결되지 않은, 해결된, 만족스러운) 세 가지 인스턴스 풀을 유지하며, 지수적으로 증가하는 가중치로 이를 샘플링합니다. 이는 가장 유익한 업데이트를 제공하는 인스턴스 (예: 비최적 솔루션을 가진 것들) 를 우선시합니다.

표현: 관계형 GNN

다른 수의 개체와 목표에 대한 일반화를 보장하기 위해 $Q_\theta$는 **관계형 그래프 신경망 (R-GNN)**으로 표현됩니다.

• 입력: 상태 $s$와 목표 $g$는 기본 원자 (ground atoms) 집합으로 인코딩됩니다. 적용 가능한 행동은 보조 "행동 개체"와 원자를 도입하여 명시적으로 표현되므로, 네트워크가 상태의 맥락 내에서 특정 행동 선택을 평가할 수 있습니다.
• 아키텍처: 네트워크는 관계 구조를 통해 메시지 전달을 사용합니다. 술어별 MLP 는 인자 역할에 기반하여 메시지를 생성하며, 이는 치환 불변 함수를 통해 집계됩니다.
• 출력: 공유된 읽기 (readout) MLP 는 특정 행동 개체의 임베딩과 상태 및 목표의 풀링된 요약물을 결합하여 Q-값을 생성합니다. 이 아키텍처는 모델이 각 스키마마다 별도의 예측기를 학습하는 대신, 고정된 행동에 대한 공통 점수 원칙을 학습하도록 보장합니다.

주요 기여

1. 자기 개선 탐색 - 학습 루프: 이 논문은 최우선 탐색 (WA*) 이 하한선 및 죽은 길 신호를 포함한 고품질 훈련 데이터를 생성하여 학습된 휴리스틱을 업데이트하고, 이는 다시 더 효율적인 미래 탐색을 안내하는 프레임워크를 소개합니다.
2. 제로샷 일반화: 학습된 Q-함수는 훈련 중에는 보지 못한 훨씬 더 많은 개체와 다른 목표를 가진 인스턴스를 해결할 수 있는 일반 정책으로 기능하며, 많은 경우 테스트 시 탐색이 필요하지 않습니다.
3. 통합 프레임워크: 이 접근법은 2023 국제 계획 대회 (IPC) 벤치마크부터 결합 퍼즐 (Sokoban, The Witness) 및 PushWorld 도메인에 이르기까지 단일 아키텍처와 하이퍼파라미터 세트를 사용하여 다양한 도메인에 균일하게 적용됩니다.
4. 실시간 탐색에 대한 우위성: 이 연구는 희소 보상 및 높은 분기 계수를 가진 계획 도메인에서 성공을 위해 학습 루프 내 실시간 탐색을 최우선 탐색으로 대체하는 것이 중요함을 입증합니다.

실험 결과

저자들은 GSP 를 세 가지 범주의 벤치마크에서 평가했습니다:

• 2023 IPC 학습 트랙:

  • 탐욕적 실행 ($GSP_\pi$): Blocksworld, Miconic, Spanner 에서 100% 커버리지를 달성하여 Lifted HER, LAMA, AlphaZero 스타일 정책과 같은 베이스라인을 능가했습니다.
  • 탐색 유도 ($GSP_{WA^*}$): Sokoban 과 같은 퍼즐에서 커버리지를 14% 에서 32% 로 개선하는 등 혼합된 결과를 보였으나, 학습된 휴리스틱이 지역적 순위에는 좋지만 전역적 보정이 부족하여 Blocksworld 와 같이 거대한 분기 계수를 가진 도메인에서는 때로 커버리지를 감소시켰습니다.
  • 확장성: 30 개 미만의 블록으로 훈련된 휴리스틱은 탐색 없이 488 개의 블록을 가진 인스턴스를 성공적으로 해결했습니다.

• 결합 퍼즐 (Sokoban, The Witness, 24-Puzzle):

  • Sokoban에서 $GSP_{WA^*}$는 평균 207 번의 확장으로 인스턴스의 100% 를 해결하여 표준 휴리스틱을 가진 WA*(3298 회 확장) 와 DeepCubeA(1050 회 확장) 를 크게 능가했습니다.
  • The Witness에서 이 방법은 모든 인스턴스를 해결하여 죽은 길 상태에 대한 훈련의 가치를 입증했습니다.
  • 24-Puzzle에서 이 방법은 훈련 중 솔루션을 찾지 못했는데, 이는 초기 정보적 휴리스틱 없이 매우 어려운 고정 크기 퍼즐에서는 최소 하나의 솔루션을 찾아 학습을 부트스트랩하는 능력이 필요함을 강조합니다.

• PushWorld:

  • 레벨 0 에서 훈련된 모델은 레벨 1 로 일반화되었습니다. $GSP_{WA^*}$는 고전적 계획기 LAMA 보다 짧은 계획과 약 30 배 적은 확대로 레벨 1 인스턴스 63 개 중 48 개를 해결했습니다.
  • 탐욕적 정책으로서 DQN, PPO 와 같은 모델 프리 RL 베이스라인을 크게 능가했습니다.

중요성과 주장

이 논문은 전이 모델이 알려진 경우, 특히 실시간 탐색이 유익한 궤적을 발견하지 못하는 희소 보상 도메인에서 최우선 탐색이 일반화된 강화 학습을 위한 우월한 탐색 메커니즘이라고 주장합니다.

주요 중요성은 상호 강화 루프의 실증에 있습니다: 탐색은 휴리스틱이 개선되도록 허용하는 훈련 타겟 (하한선, 죽은 길) 을 제공하고, 개선된 휴리스틱은 후속 탐색을 더 효율적으로 만듭니다. 이를 통해 시스템은 탐색 없이 임의의 크기와 복잡성의 문제를 해결할 수 있는 일반 정책을 학습하거나, 탐색을 최적 솔루션으로 안내하는 고효율 휴리스틱을 학습할 수 있습니다.

저자들은 겸손하게 한계를 지적합니다: 학습된 Q-함수는 종종 강력한 지역 행동 순위 결정 메커니즘으로 작용하지만, 전체 탐색 프론티어 전반에 걸쳐 전역 보정이 부족할 수 있으며, 이는 극도로 큰 분기 계수를 가진 도메인에서 WA* 의 비최적 성능으로 이어질 수 있습니다. 그들은 향후 연구가 상태 간 가치 일반화를 개선하고, 최우선 탐색과 실시간 탐색 및 사후 경험 재표시의 보완적 강점을 결합하는 데 초점을 맞출 수 있다고 제안합니다.