기술 요약: 기초 정책 기반 다단계 계획에서의 도달 시간 동형성

문제 정의

본 논문은 기초 정책 학습을 위한 오프라인 목표 조건부 강화 학습 (RL) 의 과제를 다룹니다. 목표는 정적 궤적 데이터셋에서 재사용 가능하고 목표에 구애받지 않는 정책을 학습하여, 제로샷 방식으로 열린 목표 집합에 일반화할 수 있도록 하는 것입니다.

기존 오프라인 상태 표현 학습 접근법은 세 가지 범주로 나뉘며, 각각 다단계 계획에 있어 치명적인 한계를 지닙니다:

1. 후계자 측정 (Successor Measure) 방법: 비지도 학습 방식이지만, 종종 삼각 부등식을 만족하지 못해 중간 하위 목표를 통한 거리 조합을 불가능하게 만듭니다.
2. 도달 가능성 거리 방법: 이러한 방법들은 종종 거리 또는 준거리 구조를 부과하지만, 정책 학습을 위해 목표 조건부 감독에 의존하여 기초 정책에 필요한 목표 무관성 요구 사항을 위반합니다.
3. 도달 시간 (Hitting Time) 방법: 이러한 방법들은 삼각 부등식을 만족하고 비지도 학습을 지원하지만, 일반적으로 대칭적 유클리드 거리에 의존합니다. 이는 실제 환경의 지향적이며 비가역적인 시간 기하학을 포착하지 못해, 필요한 방향으로 도달 불가능한 하위 목표를 경유하는 비최적 계획으로 이어집니다.

저자들은 결여된 원시 요소 (primitive) 를 이산 전이 단계로 측정된 지향적 시간 기하학으로 식별합니다. 그들은 도달 시간이 잠재적 변위의 선형 함수가 되도록 방향과 척도를 모두 보존하는 표현을 학습하는 것을 목표로 하며, 이를 위해 기대 도달 시간을 회복해야 할 기본 양으로 제안합니다.

방법론: 동형 임베딩 학습 (IEL)

핵심 기여는 새로운 연산자 이론 프레임워크와 동형 임베딩 학습 (IEL) 알고리즘입니다.

1. 이론적 프레임워크: 도달 시간 동형성

저자들은 힐베르트 공간 내에서 환경을 제어 마르코프 과정 (CMP) 으로 형식화합니다. 잠재 특징 공간 $\phi$에서 전이 역학이 근사적으로 선형인 $\epsilon$-충분 CMP를 정의합니다.

• 도달 시간의 선형 표현: 잠재 역학이 선형적으로 닫히고 특정 수반 범위 조건이 충족된다는 가정 하에, 상태 $x$에서 목표 $g$까지의 기대 도달 시간 $V^\pi(x, g)$는 정확한 선형 표현을 가집니다:
  $$V^\pi(x, g) = \langle \phi(g) - \phi(x), \omega^\pi_g \rangle_H$$
  여기서 $\omega^\pi_g$는 힐베르트 공간 내의 작업 식별자 벡터입니다. 이는 도달 시간 함수가 유계 선형 동형을 제외하고 잠재적 변위와 동등함을 증명합니다.
• 식별 가능성: 본 논문은 이 도달 시간 기하학을 회복하는 모든 표현이 유계 선형 좌표 변환을 제외하고 유일하게 식별 가능함을 증명합니다 (정리 2.3). 이는 학습된 기하학이 임의의 좌표계가 아닌 환경의 실제 지향적 시간 구조를 반영함을 보장합니다.
• 오차 한계: 이론적 분석에 따르면, 전역 도달 시간 오차는 환경의 일시적 스펙트럼 반경에 의해 증폭된 1 단계 잠재 전이 오차에 의해 상한이 결정됩니다 (정리 3.3). 유한 표본 보장은 오차를 근사, 통계적 복잡성, 커버리지, 궤적 - 레이블 불일치 항으로 분해합니다 (정리 3.5).

2. IEL 알고리즘

IEL 은 다음 네 가지 구성 요소를 통해 이 이론을 실현합니다:

1. 작업 식별자 학습: 대비 학습 접근법 (InfoNCE 손실) 은 목표 상태를 작업 식별자로 변환하는 매핑 $\omega_\psi(g)$를 학습합니다. 이는 잠재 공간 내에서 지향 축을 확립하여 비대칭 도달 시간 계산을 가능하게 합니다.
2. 도달 시간 회귀: 알고리즘은 오프라인 궤적에서 중간 점을 샘플링하고 기대량 회귀 (expectile regression) 를 수행하여 도달 시간 진행을 예측합니다. 이는 기하학을 분포 내의 더 짧은 거리 쪽으로 편향시킵니다.
3. 시간차 (TD) 학습: 긴 시간 범위 데이터의 부족을 처리하기 위해 IEL 은 도달 시간 공식을 HILP 스타일 목적 함수와 연결합니다. 변환을 통해 지향적 편향을 도입합니다:
   $$V^\pi(x, g) \approx \|\phi(g) - \phi(x)\| \exp(\beta(1 - \cos(\xi_{x \to g, g})))$$
   여기서 $\xi$는 임베딩 차이와 작업 식별자 사이의 각도입니다. 이는 대칭적 방법에서 결여된 부드러운 지향 제약으로 작용하여 각도 불일치를 패널티화합니다.
4. 그래프 기반 다단계 계획: 테스트 시점에 IEL 은 잠재 상태의 코어셋 위에 유방향 그래프를 구성합니다. 엣지 비용은 학습된 비대칭 도달 시간 점수에 의해 정의됩니다. 탐색은 역방향 그래프에서 단일 출발점 최단 경로 (SSSP) 검색을 수행하여 지역적 시간 예측을 전역적 제로샷 탐색 계획으로 변환합니다.

주요 기여

• 이론적: 충분한 CMP 에서 도달 시간에 대한 변위 - 선형 표현의 존재와 식별 가능성을 증명하여 연산자 이론과 도달 시간 함수 간의 엄밀한 연결을 확립합니다.
• 알고리즘적: 비지도 정책 학습, 지향적 거리, 그리고 삼각 부등식을 동시에 만족하는 최초의 기초 정책 학습 알고리즘인 IEL을 도입합니다.
• 실용적: 임베딩 기하학에 지향적 비대칭성을 통합하는 것이 대칭적 기준선보다 다단계 계획 능력을 현저히 향상시킨다는 것을 입증합니다.

실험 결과

저자들은 D4RL 데이터셋 (AntMaze 및 Kitchen 스위트) 의 여섯 가지 오프라인 목표 조건부 RL 벤치마크에서 IEL 을 평가했습니다.

• 기준선: 기초 정책에 대한 주요 기준선인 HILP 와 GC-IQL, GC-CQL 에 대한 비교가 수행되었습니다.
• 성능:
  • 비대칭 그래프 계획을 사용하는 IEL 은 antmaze-ultra-diverse(79.0 대 39.8) 및 antmaze-large-diverse(71.8 대 68.0) 와 같은 환경에서 HILP 와 재귀적 중점 계획보다 현저히 뛰어난 최첨단 결과를 달성했습니다.
  • IEL 의 대칭 변형(대칭 거리를 사용하지만 동일한 그래프 계획을 적용) 도 종종 HILP 의 재귀적 중점 전략을 능가하여, 그래프 기반 계획 메커니즘 자체의 유효성을 입증했습니다.
  • 비대칭 변형은 여섯 개 환경 중 네 개에서 추가적인 향상을 제공하여 복잡한 탐색을 위한 지향적 기하학의 필요성을 확인시켰습니다.
• 효율성: IEL 의 학습 비용은 HILP 와 비교 가능합니다. 비대칭 그래프 계획은 재귀적 중점 계획과 유사한 속도로 실행되며, 대칭 변형은 그래프 재사용성으로 인해 약 세 배 더 빠릅니다.

중요성 및 주장

본 논문은 IEL이 다단계 계획을 위한 기초 정책에 필요한 세 가지 핵심 능력 (비지도 학습, 지향적 거리, 삼각 부등식) 을 충족하는 최초의 프레임워크를 제공한다고 주장합니다.

저자들은 연산자 이론에 기반한 지향적 시간 기하학으로 대칭적 거리 휴리스틱을 대체함으로써, 에이전트가 증명 가능한 효율성으로 복잡하고 비가역적인 환경을 탐색할 수 있다고 주장합니다. 그들은 이 작업이 모방 학습에 대한 의존에서 보상 기반 정책 학습으로의 전환을 위한 수학적 기초를 제공하며, 잠재적으로 더 자율적이고 신뢰할 수 있는 범용 로봇을 가능하게 할 것이라고 제시합니다. 이 프레임워크는 전역 일관성 보장이 결여된 거리 기반 모델에 대한 엄밀한 대안으로 제시됩니다.