논문 요약: 활성 보상 머신 추론 (Active Reward Machine Inference)

1. 문제 정의 (Problem Statement)

이 논문은 **보상 머신 (Reward Machines, RMs)**을 직접 학습하는 새로운 접근법을 제시합니다. 보상 머신은 다단계 작업 (multi-stage tasks) 을 수행하기 위해 필요한 메모리 구조를 자동자 (automaton) 형태로 표현한 것입니다.

• 기존 연구의 한계: 기존 보상 머신 학습 연구들은 대부분 상태에 대한 고수준 레이블 (labeling function) 이나 보상 신호, 혹은 머신 노드에 대한 정보를 전제로 합니다. 즉, 인간이 작업의 논리적 구조를 정의하거나 노이즈가 있는 레이블을 제공해야 합니다.
• 본 논문의 설정: 저자들은 어떤 보상 신호, 레이블, 또는 머신 노드 정보도 관찰할 수 없는 (information-scarce) 극단적인 상황을 가정합니다. 오직 **원시 상태 궤적 (raw state trajectories)**과 이를 통해 유도된 **히스토리 정책 (history policy)**만 주어졌을 때, 보상 머신의 구조 (전이 함수) 와 상태-레벨 매핑 (labeling function) 을 동시에 학습하는 문제를 다룹니다.
• 핵심 질문:
  1. 주어진 히스토리 정책의 깊이 (depth) $l^*$가 충분하다면, 정책과 동등한 (policy-equivalent) 보상 머신을 복원할 수 있는가?
  2. 만약 그렇다면, 최소한의 노드를 가진 보상 머신을 어떻게 찾을 수 있는가?

2. 방법론 (Methodology)

2.1 문제 형식화 및 동치성 (Equivalence)

• 히스토리 정책 ($\pi_h$): 상태 $s$와 과거 상태 궤적 $\tau$를 입력받아 행동을 결정하는 정책으로, 제품 MDP (Product MDP) 의 최적 정책을 상태만으로 표현한 것입니다.
• 정책 동치 (Policy Equivalence): 서로 다른 레이블된 보상 머신이 동일한 히스토리 정책을 유도하면, 두 머신은 정책적으로 동치라고 정의합니다. 이 논문은 이러한 동치 클래스 내에서 최소 노드 수를 가진 보상 머신을 찾는 것을 목표로 합니다.

2.2 SAT 기반 학습 프레임워크

학습 문제는 불만족 가능성 (SAT) 문제로 변환되어 해결됩니다.

• 학습 대상: 보상 머신의 전이 함수 ($\delta_u$) 와 레이블링 함수 ($L$).
• 부정 예제 (Negative Examples): 두 상태 궤적 $\tau, \tau'$가 동일한 현재 상태 $s$에서 다른 행동을 유도한다면 ($\pi_h(a|s, \tau) \neq \pi_h(a|s, \tau')$), 이 두 궤적은 보상 머신 상에서 서로 다른 노드로 이어져야 합니다. 이를 부정 예제로 간주하여 제약 조건으로 사용합니다.
• SAT 문제 구성:
  • 이진 변수를 사용하여 전이 함수와 레이블링 함수를 인코딩합니다.
  • 모든 부정 예제 쌍에 대해, 해당 궤적이 보상 머신에서 다른 노드로 수렴하도록 제약 조건을 부과합니다.
  • 충분한 깊이 (Sufficient Depth): 이론적으로 $l^* = |S| \cdot u_{max}^2$ (상태 수 $\times$ 최대 노드 수의 제곱) 이상의 깊이를 가진 히스토리 정책만 있다면, 더 깊은 데이터는 추가적인 제약 조건을 주지 않는다는 Proposition 1을 증명했습니다.

2.3 활성 확장 알고리즘 (Active Extension Algorithm)

전체 상태 궤적을 탐색하는 것은 상태 공간이 커짐에 따라 지수적으로 증가하여 계산 및 메모리 병목 현상을 일으킵니다. 이를 해결하기 위해 활성 학습 (Active Learning) 전략을 도입했습니다.

• 핵심 아이디어: 모든 궤적을 확인하지 않아도, 후보 해 집합을 가장 빠르게 줄일 수 있는 정보성 높은 궤적 쌍을 선택적으로 질의 (query) 합니다.
• 알고리즘 흐름:
  1. 초기 깊이에서 SAT 문제를 풀어 후보 보상 머신 집합을 생성합니다.
  2. 후보 집합 내의 모델들이 궤적 쌍 $\{\tau, \tau'\}$에 대해 어떻게 반응하는지 시뮬레이션합니다.
  3. 품질 지표 (Quality Metric): 특정 궤적 쌍을 통해 후보 집합의 절반은 같은 노드로, 나머지 절반은 다른 노드로 이동하게 만드는 쌍을 찾습니다 (이진 분할).
  4. 가장 품질이 높은 쌍을 선택하여 실제 히스토리 정책에서 확인 (Query) 하고, 부정 예제로 발견되면 SAT 문제를 점진적으로 업데이트합니다.
  5. 이 과정을 후보 집합이 수렴할 때까지 반복합니다.

3. 주요 결과 (Results)

논문의 방법은 Grid World 환경 (Pick & Drop, PatrolABCD) 에서 실험되었습니다.

• 정확한 복원: 원시 상태 궤적만 사용하여 지상 진실 (Ground Truth) 보상 머신과 레이블링 함수를 완벽하게 복원했습니다 (노드 이름 재배열 제외).
• 활성 학습의 효율성:
  • 메모리 절감: 전체 궤적 (Exhaustive) 을 사용하는 방식은 깊이 9 에서 약 4 억 1 천만 개의 부정 예제를 생성하여 24.76 GB 의 메모리가 필요했으나, 활성 확장 방식은 깊이 13 에서도 약 0.292 백만 개의 예제만 사용하여 0.147 GB로 메모리 요구량을 약 100 배 (2 차수) 줄였습니다.
  • 계산 시간 단축: 전체 탐색 방식은 SAT 풀이에 7,100 초 이상이 소요되었으나, 활성 방식은 평균 3,544 초로 약 2 배의 속도 향상을 보였습니다.
  • 수렴 속도: 무작위 샘플링 기반의 베이스라인은 깊은 깊이에서도 해를 찾지 못했으나, 활성 학습은 적은 수의 질의로 빠르게 지상 진실 해 집합으로 수렴했습니다.

4. 주요 기여 (Key Contributions)

1. 정보 부족 환경에서의 학습: 보상, 레이블, 머신 구조에 대한 사전 지식 없이 오직 상태 궤적만으로 보상 머신과 레이블링 함수를 동시에 학습하는 최초의 프레임워크를 제안했습니다.
2. 이론적 충분 조건: 히스토리 정책의 깊이가 특정 임계값 ($l^*$) 이상이면 추가 데이터가 불필요함을 수학적으로 증명했습니다.
3. 활성 확장 전략: 계산 및 메모리 병목을 해결하기 위해, 후보 해 공간을 효율적으로 축소하는 활성 학습 알고리즘을 개발했습니다.
4. 실증적 검증: 다양한 다단계 작업에서 제안된 방법이 메모리 및 계산 효율성을 크게 개선하면서도 정확한 모델을 복원함을 입증했습니다.

5. 의의 및 결론 (Significance)

이 논문은 로봇이 복잡한 다단계 작업을 수행할 때 필요한 **메모리 구조 (Reward Machine)**를 데이터로부터 자동으로 발견할 수 있는 길을 열었습니다.

• 실용성: 인간이 작업의 논리적 구조를 수동으로 정의하거나 복잡한 레이블링 함수를 설계할 필요성을 줄여주어, 로봇의 자율성을 높이는 데 기여합니다.
• 확장성: 제안된 활성 학습 전략은 상태 공간이 큰 실제 로봇 응용 분야에서도 계산 자원을 효율적으로 사용할 수 있게 합니다.
• 미래 방향: 현재는 이산 상태 공간과 최적 정책에 기반하고 있으나, 부분 관측 (POMDP) 이나 연속 상태 공간으로 확장하고, 추정 오차를 고려한 통계적 방법과 결합하는 것이 향후 연구 과제로 제시되었습니다.

결론적으로, 이 연구는 보상 머신 추론 분야에서 데이터 효율성과 계산 효율성을 동시에 달성한 중요한 이정표로 평가됩니다.