그래프 희소 샘플링으로 연속 MDP 계획의 수평선 저주 극복

한줄 요약

연속 MDP 계획에서 트리 기반 탐색의 지수적 복잡도 문제를 해결하기 위해, 미래 시나리오를 공유하는 그래프 기반 희소 샘플링 알고리즘을 제안하고 이론적 성능 보장을 제공한다.

풀어야 하는 문제

연속 상태/행동 공간에서의 온라인 계획은 불확실성 하에서 이루어지며, MCTS와 같은 트리 기반 탐색 방법은 최악의 경우 lookahead 깊이에 따라 샘플링 예산이 지수적으로 증가할 수 있다. 특히 무한한 분기 구조를 가진 연속 공간에서는 어디를 탐색해야 할지 결정하기가 매우 어렵다.

접근 방법

Graph Sparse Sampling (GSS)은 각 후보 행동에 대해 별도의 후속 상태를 샘플링하는 대신, 여러 후보 결정에 걸쳐 샘플된 미래를 공유하는 온라인 계획 알고리즘이다. 이 분기 없는 그래프 구조는 GPU 친화적인 대규모 배치 처리를 가능하게 하며, 휴리스틱을 사용하여 계산을 집중시킨다. 또한, 유한 샘플 성능 보장을 이론적으로 증명한다.

결과·기여

연속 제어 시뮬레이션에서 GSS는 긴 수평선(horizon) 환경에서 트리 기반 플래너를 크게 능가하거나 근최적 성능을 달성한다. 이는 공유된 미래를 활용하면 트리 형태의 희소 샘플링이 가지는 지수적 수평선 의존성을 피할 수 있음을 공식적으로 입증하며, 온라인 제어를 위한 새로운 설계 원칙으로서 그래프 기반 계획의 가능성을 보여준다.