기술적 요약: 최소 정보로 흔적에서 들썩인 행동 모델 학습

문제 정의

최근 연구들은 들썩인 STRIPS 모델이 행동 흔적만으로 효율적으로 학습될 수 있음을 입증했으며 (SIFT 알고리즘), STRIPS+ 모델 (암시적 행동 인수를 허용) 이 완전히 관찰 가능한 상태 - 행동 흔적에서 학습될 수 있음을 보였습니다 (SYNTH 알고리즘). 그러나 이러한 접근법은 실용적인 한계에 직면해 있습니다:

1. SIFT는 인수가 명시적인 완전한 STRIPS 행동 흔적을 요구하며, 이는 종종 행동 선택에 불필요한 매개변수를 포함합니다 (예: 슬라이딩 타일 퍼즐에서 행동이 "왼쪽으로 이동"인 경우에도 타일의 현재 위치를 명시적으로 전달해야 함).
2. SYNTH는 모든 상태 술어의 완전한 관찰 가능성을 가정하는데, 이는 부분적으로 관찰 가능한 환경에서 작동하는 에이전트에게는 비현실적입니다.

본 논문은 행동 인수와 상태 정보 모두 부분적으로 관찰 가능한 흔적에서 STRIPS+ 행동 도메인을 학습하는 문제를 다룹니다. 구체적으로 저자들은 흔적이 최소한의 정보를 전달할 때 동등한 도메인을 학습할 수 있는 조건을 조사합니다: 일부 행동 인수가 생략되고, 상태 술어는 완전히 관찰 불가능하거나, 완전히 관찰 가능하거나, 현재 상태와 관련된 객체에 대해서만 국소적으로 관찰 가능 (관찰 가능) 합니다.

방법론

제안된 솔루션인 **SYNTH+**는 SIFT 와 SYNTH 의 기능을 확장하고 통합하는 통합 알고리즘입니다. 이는 확장된 흔적 (행동 시퀀스와 부분 상태 관찰의 연속) 에서 작동하며 두 가지 핵심 메커니즘에 의존합니다:

1. 뮤텍스 특징 (SIFT 의 확장)

상태 관찰 가능성 없이 누락된 행동 인수를 처리하기 위해 저자들은 뮤텍스 특징을 도입합니다.

• 개념: 뮤텍스 특징 $f = \langle k, A, D \rangle$는 $k$-번째 인수가 처음 $k-1$개의 인수에 의해 암시적으로 결정되는 $k$-항 술어를 나타냅니다.
• 메커니즘: 추가 및 삭제 패턴이 동일한 항수를 갖는 표준 특징과 달리, 뮤텍스 특징은 삭제 패턴이 $k-1$항을 갖도록 허용합니다. 이는 행동 (예: drop()) 이 해당 객체를 행동 흔적에서 명시적으로 언급하지 않고도 현재 들고 있는 객체에 기반하여 술어 (예: holding(o)) 를 삭제한다는 제약을 포착합니다.
• 일관성: 뮤텍스 특징은 흔적 그래프 전체에서 모든 기본 원자 $f(o)$가 단일 진리값을 받고, 동일한 상태 내의 두 참 원자 $f(o)$와 $f(o')$에 대해 마지막 인수가 다르다면 ($o_k \neq o'_k$), 적어도 하나의 선행 인수 또한 달라야 할 때 ($어떤 i < k$에 대해 $o_i \neq o'_i$) 일관성이 있습니다.

2. 쿼리 합성 및 통합 (SYNTH 의 확장)

SYNTH+ 는 술어 "발명" (SIFT 를 통해) 과 암시적 인수 추론 (SYNTH 를 통해) 을 반복 루프에서 통합합니다:

1. 입력: 확장된 흔적의 레이블이 지정된 그래프와 완전히 관찰 가능한 술어 집합 $P_\omega$.
2. 반복:
   • SIFT+ 단계: 명시적 인수와 현재 알려진 암시적 인수에 대한 행동 패턴을 사용하여 새로운 뮤텍스 특징과 일반 특징을 발명합니다. 이러한 특징은 새로운 술어와 그 효과를 나타냅니다.
   • SYNTH 단계: 새로 발명된 술어 (및 관찰 가능한 술어) 를 사용하여 상태의 고유한 객체에 암시적 변수 ($z_i$) 를 바인딩하는 쿼리 (하위 쿼리 $Q_i$) 를 정의합니다.
   • 업데이트: 그래프가 새로운 암시적 인수와 이를 정의하는 쿼리로 업데이트됩니다.
3. 종료: 고정점에 도달하거나 최대 깊이 제한 ($d_{max}$) 을 초과할 때까지 이 과정이 계속됩니다.

3. 국소 관찰 가능성

이 프레임워크는 국소 관찰 가능성을 처리하는 **LOCAL SYNTH+*로 확장됩니다. 이 설정에서 술어는 "국소" 객체 (현재 행동의 인수로서 나타나는 객체) 에 대해서만 관찰 가능합니다. 알고리즘은 전제 조건을 테스트할 때 비국소 원자가 거짓이라고 가정하도록 일관성 테스트 절차 (TEST) 를 수정하여, 관찰되지 않은 상태 부분이 암시적 인수 학습을 무효화하지 않도록 합니다.

주요 기여

1. SYNTH+ 알고리즘: 행동과 상태의 부분 관찰 가능성을 가진 흔적에서 STRIPS+ 도메인을 학습하는 일반적인 알고리즘입니다. 이는 SIFT 의 술어 발명과 SYNTH 의 암시적 인수 해결을 통합합니다.
2. 뮤텍스 특징: 마지막 인수가 다른 인수에 기능적으로 의존하는 술어를 학습할 수 있게 하는 새로운 형식주의로, 완전한 상태 관찰 없이 생략된 행동 인수를 복원할 수 있게 합니다.
3. 완전성 결과: 알고리즘이 완전한 조건에 대한 이론적 기준이 확립되었습니다:
   • SIFT+ (상태 관찰 없음): 숨겨진 STRIPS+ 도메인이 잘 형성되어 있고, 강하게 연결되어 있으며, 의존성 그래프 (노드는 술어와 암시적 변수) 에서 비순환적이어야 합니다.
   • SYNTH+ (부분 상태 관찰): 관찰 불가능한 술어로 제한된 의존성 그래프가 비순환적이어야 합니다.
   • LOCAL SYNTH+: 핵심 술어 (암시적 인수만 포함하는 전제 조건에 있는 술어) 가 완전히 관찰 가능하고 다른 술어가 국소적으로 관찰 가능할 때, 국소 관찰 가능성 하에서 완전함이 증명되었습니다.
4. 일반화: 이 연구는 SIFT 와 SYNTH 가 각각 $P_\omega = \emptyset$과 $P_\omega = P$인 경우의 SYNTH+ 의 특수한 경우임을 보여줍니다.

실험 결과

저자들은 숨겨진 STRIPS+ 모델에서 생성된 확장된 흔적을 사용하여 표준 계획 도메인 (예: 블록, 배달, 그리드, 소코반, 물류) 에서 SIFT+ 와 SYNTH+ 를 평가했습니다.

• SIFT+ 성능: 모든 테스트된 도메인에서 행동 흔적만으로 올바른 도메인을 성공적으로 학습했습니다 (100% 검증률). 흔적에서 생략된 행동 인수 중 평균 55% 를 복원했습니다.
• SYNTH+ 성능: SYNTH 보다 훨씬 적은 관찰 가능한 술어를 사용하여 올바른 도메인을 학습했습니다.
  • 배달에서 SYNTH+ 는 에이전트의 위치 (at(x)) 와 정적 인접성만 관찰하여 도메인을 학습한 반면, SYNTH 는 모든 유동적 술어가 필요했습니다.
  • 소코반과 물류*에서 SYNTH+ 는 정적 술어만 관찰된 도메인을 학습했는데, 이는 SYNTH 나 SIFT+ 모두 성공할 수 없는 시나리오였습니다.
• 효율성: 알고리즘은 표준 하드웨어에서 효율적으로 실행되었습니다 (초에서 분 단위). 수천 개의 흔적 단계를 가진 도메인으로 확장되었습니다.

중요성과 주장

본 논문은 **SYNTH+**가 "자연스러운" 흔적에서 동적 모델을 학습할 수 있게 함으로써 모델 기반 강화 학습에 대한 실용적인 들썩인 대안을 제공한다고 주장합니다. 이러한 흔적은 최소한의 정보를 요구합니다:

• 형식적인 STRIPS 인코딩에 필요한 모든 인수 (예: 언스택되는 블록의 현재 위치) 를 나열할 필요가 없습니다.
• 완전한 상태 관찰이 필요하지 않습니다. 특정 술어의 부분적 또는 국소적 관찰 가능성으로 충분합니다.

저자들은 이 접근법이 종종 완전한 관찰 가능성을 가정하는 이론적 모델 학습과 에이전트가 제한된 지각을 가진 실제 응용 사이의 격차를 해소한다고 강조합니다. 학습이 가능한 정확한 조건 (의존성 그래프의 비순환성) 을 규명함으로써, 이 연구는 부분적으로 관찰 가능한 설정에서 들썩인 행동 모델 학습의 엄격한 범위를 확립합니다. 결과는 복잡한 도메인이 전체 상태 설명이 아니라 행동 선택에 필요한 정보만 전달하는 흔적에서도 재구성될 수 있음을 시사합니다.