기술 요약: 언제 멈출지 학습하기: 임의의 동역학 변화 하의 선택적 모방 학습

1. 문제 정의

본 논문은 테스트 환경의 전이 동역학 (transition dynamics) 이 훈련 환경과 임의적으로 상이한 상황에서의 모방 학습 (Imitation Learning, IL) 과제의 난제를 다룹니다. 고전적인 오프라인 IL 에서 학습자는 소스 환경 $M$의 전문가 시연으로 훈련된 후, 타겟 환경 $N$에 배포됩니다. $M$과 $N$의 상태 지지집합 (state supports) 이 서로 소거 (disjoint) 되거나 크게 이동한 경우, 표준 정책은 훈련 데이터가 더 이상 신뢰할 수 있는 지침을 제공하지 않는다는 사실을 인식하지 못해 임의적으로 열악한 성능을 보일 수 있습니다.

저자들은 선택적 모방 학습 (Selective Imitation Learning) 프레임워크를 제안합니다. 여기서 학습자는 훈련 데이터의 신뢰할 수 있는 지지집합 밖의 현재 상태를 감지할 때, 실행을 중단 (abstain) 할 옵션을 부여받습니다. 목표는 두 가지 상충되는 목표를 만족하는 선택적 정책 $(\pi, \tau)$을 학습하는 것입니다. 이는 기본 정책 $\pi$와 정지 시간 $\tau$로 구성되며, 다음과 같은 목표를 가집니다:

1. 완전성 (Completeness): 정책은 훈련 환경 $M$에서 거의 중단하지 않아야 합니다 (즉, $\alpha_M(\pi, \tau) \le \epsilon$).
2. 정합성 (Soundness): 정책은 정지하기 전까지 테스트 환경 $N$에서 낮은 후회 (regret) 를 기록해야 합니다 (즉, $Regret_N(\pi, \tau) \le \epsilon$).

이 설정은 다음에 대한 접근을 가정합니다:

• 레이블이 지정된 훈련 롤아웃: 환경 $M$의 전문가 $\pi^\star$로부터의 상태 - 행동 쌍 $(s, a)$.
• 레이블이 없는 테스트 롤아웃: 환경 $N$의 전문가 $\pi^\star$로부터의 상태만 포함된 궤적. 이 비대칭성은 행동 원격 측정 데이터가 비용이 많이 들거나 독점적인 실제 세계 시나리오 (예: 조향 명령이 없는 자율 주행 대시캠 영상) 를 모델링합니다.

2. 방법론: SeqRejectron

핵심 알고리즘인 SeqRejectron은 선택적 분류 (Goldwasser et al., 2020) 의 Rejectron 알고리즘을 순차적 의사결정으로 일반화합니다. 핵심 통찰은 각 시간 단계에서 독립적인 결정을 내리는 것 (이는 시간 지평에 의존하는 샘플 복잡도로 이어짐) 대신, 희소 (sparse) 한 검증자 정책 (validator policies) 집합을 사용하여 전체 궤적 접두사 (trajectory prefixes) 를 인증한다는 것입니다.

핵심 메커니즘

1. 기본 정책: 학습자는 훈련 데이터와 일관된 기본 정책 $\pi_0$를 선택합니다 (예: 최대 우도 추정).
2. 검증자 집합: 알고리즘은 버전 공간 (훈련 데이터와 일관된 정책) 에서 추출된 소수의 "검증자" 정책 $\Phi$를 구성합니다.
3. 정지 규칙: 학습자는 $\pi_0$를 실행하며 $\Phi$ 내의 모든 검증자가 $\pi_0$와 동의하는 동안만 계속 진행합니다. 첫 번째 불일치 지점이 발생하면 정지 (중단) 가 트리거됩니다.
4. 희소 검증자 분포: 중요한 이론적 기여는 희소한 검증자 집합 (크기가 시간 지평 $H$와 무관함) 이 안전성을 보장하기에 충분함을 증명하는 것입니다. 이는 "도전자"(경쟁 정책을 선택) 와 "검증자"(검증자 집합을 선택) 간의 제로섬 게임에 대한 미니맥스 (minimax) 논증을 통해 달성됩니다.

다양한 설정을 위한 변형

본 논문은 이 프레임워크를 점점 더 일반적인 세 가지 설정에 적용합니다:

• 결정론적 정책:

  • 메커니즘: 이진 불일치 테스트를 사용합니다. 정지 시간 $\tau$는 어떤 검증자 $\pi \in \Phi$라도 $\pi_0$와 불일치하는 첫 번째 단계입니다.
  • 구현: 검증자 분포는 후회 없는 동역학 (no-regret dynamics) 을 사용하여 구성됩니다 (구체적으로, 가중치 실현 가능 다중 인스턴스 학습으로의 오라클 효율적 축소).
  • 결과: 희소 비용 하에서 시간 지평이 없는 샘플 복잡도 $\tilde{O}(\sqrt{\log|\Pi|/n})$를 달성합니다.

• 확률론적 정책:

  • 과제: 이진 불일치 테스트는 너무 거칠 수 있습니다. 분포가 단일한 경각심을 불러일으키는 불일치 없이 각 단계에서 "부드럽게" 다를 수 있기 때문입니다.
  • 메커니즘: 이진 테스트를 누적 헬링거 거리 (cumulative Hellinger distance) 정지 시간으로 대체합니다. 학습자는 $\pi_0$와 어떤 검증자 간의 누적 제곱 헬링거 거리가 임계값 $\theta$를 초과할 때 정지합니다.
  • 결과: 정지된 궤적의 헬링거 거리에 대한 유한 샘플 경계를 제공합니다. 논문은 단일 단계 확률론적 설정에서 레이블이 지정된 샘플 복잡도에 대한 $\Omega(1/\epsilon^3)$ 하한을 수립하여, 비용 주도 영역에서 $1/\epsilon$에 대한 3 차 의존성이 불가피함을 보여줍니다.

• 오지정된 정책 클래스:

  • 과제: 전문가 $\pi^\star$가 학습자의 정책 클래스 $\Pi$ 내에 있지 않을 수 있습니다.
  • 메커니즘: 하드 버전 공간 제약을 대칭적으로 정규화된 게임으로 대체합니다. 검증자는 소스 데이터에서 기본 정책과 불일치할 수 있지만, 이러한 불일치는 패널티를 받습니다.
  • 결과: 보장은 오지정 정도 (최적 클래스 내 오지정 오차 $\Delta$로 측정) 에 따라 우아하게 저하됩니다.

3. 주요 기여 및 결과

이론적 보장

• 시간 지평이 없는 복잡도: 결정론적 정책의 경우, 샘플 복잡도는 시간 지평 $H$와 무관합니다 (총 비용 규모 $C_{max}$를 제외하고), $\tilde{O}(\sqrt{\log|\Pi|/n})$로 스케일링됩니다. 이는 $O(H^2)$ 패널티를 겪는 단순한 단계별 축소에 비해 개선된 것입니다.
• 희소 검증: 논문은 상태 공간, 행동 공간, 또는 시간 지평과 무관한 크기 $O(1/\epsilon)$ 집합에 지지된 검증자 분포의 존재를 증명합니다.
• 하한: 저자들은 확률론적 단일 단계 설정에서 레이블이 지정된 샘플 복잡도에 대한 $\Omega(1/\epsilon^3)$ 하한을 증명하여, 비용 주도 영역에서 $1/\epsilon$에 대한 3 차 의존성이 불가피함을 보여줍니다.
• 오지정 강건성: 이 프레임워크는 전문가가 클래스에 포함되지 않는 무지 (agnostic) 설정으로 확장되며, 후회 경계는 오지정 오차의 제곱근에 비례하여 스케일링됩니다.

실증 평가

저자들은 LunarLander-v3 환경에서 SeqRejectron 을 평가합니다.

• 설정: 훈련은 바람이 없는 환경에서 수행되고, 테스트는 다른 초기 충격이 있는 바람이 부는 환경에서 수행됩니다.
• 발견: 알고리즘은 분포 외 (out-of-distribution) 동역학을 성공적으로 감지합니다. 안전 임계값 $\theta$를 조정함으로써, 저자들은 분포 내 (훈련) 데이터에서는 최소한으로 중단하는 반면 분포 외 (테스트) 데이터에서는 신뢰할 수 있게 중단하여 치명적인 실패를 방지하는 트레이드오프를 보여줍니다. 검증자의 수는 강건한 것으로 나타났으며, 성능은 빠르게 포화되었습니다.

4. 중요성 및 주장

본 논문은 모방 학습에서 예상치 못한 동역학 변화에 대한 원칙적이고 이론적으로 근거된 대응으로서 중단 (abstention) 을 확립한다고 주장합니다.

• 휴리스틱을 넘어: 동역학 변화의 성질에 대한 가정이나 테스트 분포에 대한 온라인 접근이 필요한 견고한 RL 또는 도메인 무작위화 접근법과 달리, SeqRejectron 은 오프라인 데이터만을 사용하여 분포 무관 PAC 보장을 제공합니다.
• PQ 학습의 순차적 유사체: 이 작업은 자신을 PQ 학습 프레임워크 (Goldwasser et al., 2020) 의 순차적 유사체로 위치시키며, 중단 능력을 단일 예측에서 전체 궤적 접두사로 확장합니다.
• 안전 메커니즘: 무엇을 할 것인지와 언제 멈출 것인지의 결정을 분리함으로써, 이 프레임워크는 훈련 데이터가 무의미할 때 학습자가 시스템을 해결 불가능한 상태로 몰아넣지 않도록 방지하는 안전 메커니즘을 제공합니다.

저자들은 한계를 인정하며, 확률론적 설정은 현재 오라클 효율적인 계산적 축소가 부족하다는 점 (결정론적 경우와 달리) 과 확률론적 정책에 대한 분산 주도 샘플 복잡도율이 상한과 하한 사이의 열린 간격으로 남아 있음을 지적합니다. 또한 향후 작업은 테스트 측 정지율을 강화하기 위해 부분 구조적 지식 (예: 유계 TV 거리) 을 통합할 수 있다고 제안합니다.