Laplacian Representations for Decision-Time Planning

문제 정의
모델 기반 강화 학습(Model-based RL)은 모델 프리(model-free) 방식에 비해 샘플 효율성, 일반화, 적응성 측면에서 잠재적인 이점을 제공한다. 그러나 함수 근사(function approximation)가 필요한 환경에서 학습된 모델을 이용한 계획(planning)을 수행할 때, 핵심적인 과제는 누적 오차 문제(compounding error problem)에 의해 방해를 받는다는 점이다. 에이전트가 불완전한 모델을 사용하여 장기 호라이즌(long-horizon) 궤적을 시뮬레이션할 때, 작은 예측 오차들이 축적되어 상상된 궤적이 실제와 크게 달라지게 된다. 이 문제는 의사 결정 시점의 계획(decision-time planning)에서 특히 두드려지는데, 여기서는 상태 표현(state representation)이 국소적 비용 계산을 지원하는 동시에 장기적인 시간적 구조를 보존해야 하기 때문이다. 계층적 계획(hierarchical planning)은 저수준 행동과 장기 목표를 분리할 수 있지만, 이를 위해 하위 목표(subgoal)로 작업을 효과적으로 분해할 수 있는 다중 시간 척도(multiple time scales)에 걸친 상태 공간 거리를 표현할 수 있는 잠재 공간(latent space)이 필요하다.

방법론
본 논문은 **라플라시안 표현(Laplacian representation)**이 의사 결정 시점 계획을 위한 효과적인 잠재 공간을 제공한다고 제안한다. 이 표현은 환경의 역학(dynamics)에 의해 유도된 그래프 라플라시안의 고유벡터(eigenvectors)로 정의된 공간에 상태를 임베딩한다. 이 표현의 주요 특성은 다음과 같다:

• 다중 척도 구조(Multi-scale Structure): 고유벡터는 시간 척도에 따라 정렬된다. 초기 고유벡터는 전역적 구조(예: 영역)를 인코딩하고, 후기 고유벡터는 국소적 구분을 포착한다.
• 도달 가능성 및 기하학(Reachability and Geometry): 스케일링된 라플라시안 공간에서의 유클리드 거리는 두 상태 사이를 무작위 보행(random walk)을 통해 왕복하는 데 기대되는 단계 수를 측정하는 **교환 시간 거리(Commute Time Distance, CTD)**를 근사한다. 이는 이 공간이 CTD와 등거리(isometric)임을 의미하며, 계획에 적합한 기하학적 구조를 제공한다.
• 하위 목표 발견(Subgoal Discovery): 이 표현은 환경을 잘 연결된 영역으로 자연스럽게 분할하며, 이는 병목 지점(bottlenecks)에서 하위 목표를 식별하기 위한 스펙트럴 클러스터링(spectral clustering)에 이상적이다.

이러한 특성을 바탕으로, 저자들은 계층적 의사 결정 계획 알고리즘인 **ALPS (Augmented Laplacian Planning with Subgoals)**를 도입한다. ALPS는 두 단계로 작동한다:

1. 사전 훈련(Pre-training):
   • 라플라시안 학습(Laplacian Learning): 정확한 고유값 분해(eigendecomposition)의 $O(|S|^3)$ 계산 비용을 피하기 위해, 증강 라그랑주 라플라시안 목적 함수(Augmented Lagrangian Laplacian Objective, ALLO)를 사용하여 오프라인 데이터셋으로부터 고유벡터와 고유값을 학습한다.
   • 순방향 모델(Forward Model): 오차 축적을 줄이기 위해 원래의 상태 공간에서 다단계 자기회귀(auto-regressive) 순방향 모델을 학습한다.
   • 행동 사전 확률(Behavior Prior): 행동 샘플링을 편향시켜 수렴을 가속화하기 위해 결정론적인 목표 조건부 정책($\pi_{prior}$)을 학습한다.
   • 클러스터 그래프(Cluster Graph): 스케일링된 라플라시안 공간($\psi$-공간)에서 $k$-평균 클러스터링을 수행하여 하위 목표(클러스터 중심)를 정의하고, 클러스터 간 전이를 나타내는 그래프를 구축한다.
2. 의사 결정 시점 계획(Decision-Time Planning):
   • 고수준(High-Level): 시작 상태와 목표 상태가 주어지면, 알고리즘은 각각의 클러스터를 식별하고 클러스터 그래프에서 다익스트라(Dijkstra) 알고리즘을 사용하여 하위 목표 경로를 찾는다.
   • 저수준(Low-Level): 각 하위 목표에 대해, 교차 엔트로피 방법(Cross-Entropy Method, CEM) 플래너가 행동 시퀀스를 생성한다. CEM은 행동 사전 확률를 사용하여 초기화되며, $\psi$-공간에서의 거리(CTD 근사)와 행동 크기에 기반한 비용 함수를 최소화하도록 최적화된다.

핵심 기여

• 계획을 위한 라플라시안 표현: 본 논문은 라플라시안 표현이 다양한 시간 척도에서 상태 공간 거리를 효과적으로 포착하며, 장기 호라이즌 문제를 하위 목표로 자연스럽게 분해하고 누적 오차를 완화함을 입증한다.
• ALPS 알고리즘: 라플라시안 기반의 하위 목표 식별과 모델 기반 궤적 최적화(CEM) 및 행동 사전 확률를 통합한 새로운 계층적 계획 알고리즘이다.
• 경험적 검증: 저자들은 모델 프리 방식이 지배적이었던 일련의 작업들인 OGBench(오프라인 목표 조건부 RL 벤치마크)에서 ALPS를 평가한다.

결과
실험은 Maze2D—PointMass 환경과 로코모션(pointmaze, antmaze, humanoidmaze) 및 조작(cube, scene)을 포함하며 상태 기반 및 픽셀 기반 관측치를 모두 사용하는 다양한 OGBench 작업에서 수행되었다.

• 성능: ALPS는 대부분의 OGBench 작업에서 흔히 사용되는 모델 프리 베이스라인들(GCBC, IQL 변형, QRL, CRL, HIQL 포함)을 통계적으로 유의미하게($p < 0.001$) 능가한다.
• 강건성: ALPS는 메이즈의 크기와 오프라인 데이터셋의 품질에 대해 강건함을 보여준다. 특히 저품질의 높은 커버리지를 가진 '탐색(explore)' 데이터셋에서 탁월한 성능을 보이는데, 이는 계층적 분해를 통해 고수준 플래너가 제한된 저수준 호라이즌을 보완할 수 있기 때문이다.
• PcLast와의 비교: Maze2D 작업에서 ALPS(라플라시안 표현 사용)는 대조 학습 잠재 상태(contrastive latent states)를 사용하는 PcLast보다 우수한 성능을 보였으며, 이는 거리 추정과 하위 목표 식별 모두에 있어 라플라시안 메트릭의 유용성을 강조한다.
• 한계점: 논문은 ALPS가 '텔레포트(teleport)' 메이즈에서 어려움을 겪는다고 언급한다. 이는 라플라시안 목적 함수에 내재된 대칭화(symmetrization)로 인해 텔레포터 입구와 출구가 함께 클러스터링되어, 에이전트를 빠져나올 수 없는 영역으로 유도할 가능성이 있기 때문이다. 또한, 라플라시안 표현의 전역적 특성이 객체 상태 간의 조건부 독립성을 포착하지 못해 멀티 오브젝트 조작 작업(예: double-cube)에서 성능이 저하된다.

의의
본 논문은 라플라시안 표현이 학습된 모델을 이용한 성공적인 계획을 위한 유용한 구성 요소로서, 장기 호론 미션의 핵심 과제인 누적 오차 문제를 해결한다고 주장한다. 환경의 역학적 구조를 본질적으로 포착하는 잠재 공간을 제공함으로써, ALPS는 오직 사전 수집된 오프라인 데이터셋만을 사용하여 연속적이고 고차원적인 상태 공간에서 효과적인 계층적 계획을 가능하게 한다. 이 연구는 환경의 스펙트럴 특성을 활용하는 것이 복잡하고 장기적인 목표 조건부 RL 문제에 모델 기반 방식을 적용할 때 겪었던 역사적 어려움을 극복할 수 있음을 시사한다.