Toward Learning POMDPs Beyond Full-Rank Actions and State Observability

기술 요약: 풀 랭크(Full-Rank) 액션 및 상태 관측성을 넘어선 POMDP 학습을 향하여

문제 정의
본 논문은 에이전트가 은닉 상태(hidden states)를 가진 시스템을 학습하고 추론할 수 있도록 하는 과제를 다루며, 특히 이러한 시스템을 이산적 부분 관측 마르코프 결정 과정(POMDP)으로 모델링합니다. 에이전트는 액션 공간과 관측 공간은 제공받지만, 상태 공간, 전이 역학(transition dynamics), 또는 관측 모델에 대한 사전 지식은 갖지 못합니다. 목표는 무작위 탐색을 통해 수집된 일련의 액션과 관측으로부터 은닉 상태의 개수와 명시적인 전이 및 관측 행렬을 추정하는 것입니다.

Predictive State Representations(PSR)와 같은 스펙트럼 방법은 미래의 결과를 예측하기 위한 충분 통계량(sufficient statistics)을 학습할 수 있지만, 이는 블랙박스 모델로 작동합니다. 즉, 명시적인 전이 및 관측 가능도(likelihoods)를 산출하지 않으므로, 전체 시스템을 다시 학습하지 않고 새로운 계획 작업(예: 보상 함수 변경)을 위해 모델을 조작하기가 어렵습니다. 반대로, 완전한 POMDP 모델을 복구하려는 기존의 텐서 분해(tensor decomposition) 방법들은 대개 엄격한 가정을 따릅니다: 즉, 전이 행렬이 풀 랭크여야 하며, 모든 상태가 모든 액션에 대해 고유한 관측 분포를 가져야 한다는 가정입니다. 이러한 가정은 상태 에일리어싱(state aliasing, 서로 다른 상태가 동일한 관측 분포를 공유하는 현상)이나 액션이 확률적으로 실패할 수 있는 경우가 발생하는 많은 실제 환경에서는 적용되기 어렵습니다.

방법론
저자들은 더 완화된 가정 하에서 POMDP 파라미터를 학습하기 위해 스펙트럼 분해와 텐서 분해를 결합한 방법을 제안합니다. 이 접근 방식은 세 가지 주요 단계로 진행됩니다:

1. 행켈 행렬(Hankel Matrix) 구축 및 PSR 학습:
   방법은 관측된 액션-관측 궤적으로부터 행켈 행렬을 구축하는 것으로 시작합니다. 이 행렬은 과거와 미래 관측의 결합 가능도를 인코딩합니다. 이 행렬에 대해 특이값 분해(SVD)를 통한 랭크 인수 분해(rank factorization)를 수행함으로써, 알고리즘은 선형 Predictive State Representation(PSR)을 도출합니다. 이를 통해 미지의 유사 변환(similarity transform) $P$까지의 시스템 역학을 나타내는 선형 업데이트 행치($M_{ao}$), 초기 벡터($m_0$), 그리고 최종 벡터($m_\infty$)를 얻습니다. 이 구성 요소들은 시스템 역학을 나타냅니다.

2. 유사 변환(Similarity Transform)의 복구:
   명시적인 전이($T^a$) 및 관측($O_{ao}$) 행렬을 복구하기 위해, 알고리즘은 유사 변환 $P$를 추정해야 합니다. 저자들은 $P$를 추정하기 위해 텐서 분해 기법을 재구성합니다.

• 먼저, 관측치를 주변화(marginalize)하여 변환까지의 전이 행렬을 얻습니다: $\sum_o M_{ao} = P T^a P^{-1}$.
• 전이 행렬이 풀 랭크인 액션들에 대해, 곱 $M_{ao} M_a^{-1} = P O_{ao} P^{-1}$를 계산합니다.
• $O_{ao}$는 대각 행렬이므로, 이 곱들의 고윳값(eigenvalues)은 대각 성분에 대응합니다. 중복된 고윳값으로 인한 모호함(모든 풀 랭크 액션에 대해 상태가 동일한 관측 분포를 공유할 때 발생)을 해결하기 위해, 방법론은 이 행렬들의 가중 합에 대한 공동 대각화(joint diagonalization)를 사용합니다. 고유한 관측 분포를 가진 상태들에 대해 고윳값이 거의 확실하게(almost surely) 구별되도록 무작위 가중치를 샘플링합니다.

3. 관측성 파티션(Observability Partitions)까지의 학습:
   본 논문은 풀 랭크 관측성 파티션(Full-Rank Observability Partition) 개념을 도입합니다. 만약 여러 상태가 모든 풀 랭크 전이를 가진 액션에 대해 정확히 동일한 관측 분포를 공유한다면, 순차적 데이터만으로는 이들을 구별할 수 없습니다. 알고리즘은 이 관측성 파티션까지 유사 변환 $P$를 복구합니다. 결과적으로, 학습된 모델은 개별 상태가 아닌 파티션 사이의 명시적인 전이 및 관측 행렬을 제공합니다. 단일 파티션 내의 상태들에 대해서는 모델이 집계된 역학(aggregate dynamics)을 학습합니다.

주요 기여

• 완화된 가정: 본 방법론은 상태가 에일리어싱될 수 있고(관측 분포를 공유), 전이 행렬이 모든 액션에 대해 반드시 풀 랭크일 필요는 없지만(순방향 및 역방향 행렬의 곱이 풀 랭크인 경우) 텐서 분해 접근 방식을 확장하여 POMDP를 학습합니다.
• 명시적 모델 복구: PSR과 달리, 이 방법은 (파티션까지의) 명시적인 전이 및 관측 행렬을 복구하여, 초기 학습 단계 이후에 새로운 보상 함수와 목표를 지정할 수 있게 합니다.
• 이론적 한계: 저자들은 단일 순차 데이터 궤적으로부터 관측성 파티션을 넘어선 전이 및 관측 역학을 학습하는 것이 불가능함을 증证明합니다. 그들은 서로 다른 내부 역학을 가졌음에도 모든 액션 시퀀스에 대해 동일한 관측 분포를 생성하는 두 개의 서로 다른 POMDP를 구성하여 식별 가능성(identifiability)의 이론적 한계를 입증합니다.

실험 결과
저자들은 "Sense-Float-Reset" 도메인(상태 에일리어싱 특징), Tiger 문제, T-Maze를 포함한 여러 도메인에서 방법을 평가합니다.

• 수렴성: 이 방법은 기저의 관측 모델과 파티션 수준의 전이 행렬을 성공적으로 복구하며, 탐색 상호작용의 수가 증가함에 따라 실제 값(ground truth)으로 수렴합니다. 이와 대조적으로, EM(Expectation-Maximization)은 관측은 올바르게 예측하지만 잘못된 모델 파라미터를 산출하는 지역 최적점(local minima)으로 수렴하는 경우가 많습니다.
• 계획 성능: 표준 플래너(PO-UCT)와 함께 사용할 때, 학습된 파티션 수준의 POMDP는 실제 모델 및 PSR과 유사한 계획 성능을 달성합니다.
• 보상 지정: "Noisy Hallway" 및 "Directional Hallway"라는 새로운 도메인에서, 저자들은 명시적인 전이 및 관측 가능도를 통해 에이전트가 (모호한 관측을 가진 중간 복도 상태와 같이) 특정 잠재 상태를 향하도록 유도할 수 있음을 보여줍니다. 이는 관측-액션 쌍이 아닌 상태에 보상을 할당함으로써 가능하며, 이는 표준 PSR이나 구조적 복구에 실패하는 EM 기반 모델에서는 불가능한 기능입니다.

의의 및 주장
본 논문은 자신의 방법이 PSR의 예측 능력과 명시적 POM 모델의 해석 가능성 사이의 간극을 메운다고 주장합니다. 관측성 파티션까지 학습함으로써, 이 방법은 이전의 텐서 기반 방법들보다 더 넓은 클래스의 실제 시스템(특히 액션이 실패하거나 상태가 에일리어싱될 수 있는 로봇 조작 분야)을 포괄할 수 있습니다.

저자들은 자신의 방법이 순차적 데이터로부터 에일리어싱된 상태의 정확한 내부 구조를 복구할 수는 없지만, 이론적으로 가능한 최대한의 정보를 복구한다고 겸손하게 주장합니다. 명시적인 보상 지정(explicit reward specification)을 통해 학습된 모델을 새로운 작업에 조작할 수 있다는 점이 블랙박스 예측 모델에 비해 갖는 주요 장점으로 강조됩니다. 이 연구는 많은 실질적인 응용 분야에서 관측성 파티션 사이의 역학을 학습하는 것이 효과적인 계획과 추론을 위해 충분하다는 점을 시사합니다.