기술 요약: 수렴 보장을 갖춘 증명 가능한 효율적 오프-폴리시 적대적 모방 학습

문제 정의

적대적 모방 학습(Adversarial Imitation Learning, AIL)은 에이전트가 전문가의 성능을 따라가도록 정책을 업데이트하는 동시에, 적대적 요소는 두 성능 간의 격차를 최대화하도록 보상 함수를 업데이트하는 이-플레이어 게임(two-player game)으로 모방 학습을 프레임화합니다. 표준 AIL 알고리즘은 보상 함수 업데이트 중에 기대 누적 보상을 평가하기 위해 온-폴리시 데이터(에이전트의 현재 정책에 의해 생성된 샘플)를 필요로 합니다. 이러한 요구 사항은 매 업데이트 단계마다 새로운 환경 상호작용을 필요로 하므로 샘플 비효율성을 초래하며, 상호작용 비용이 높거나 제한적인 설정에서 이 접근 방식을 비실용적으로 만듭니다.

오프-폴리시(off-policy) 방법들이 샘플 효율성을 높이기 위해 이전 정책으로부터 생성된 데이터를 재사용하는 방식이 제안되어 왔으나, 이는 데이터가 더 이상 현재 정책의 상태-행동 방문 분포와 완벽하게 일치하지 않기 때문에 **분포 변화 오류(distribution shift error)**를 유발합니다. 기존의 오프-폴리시 AIL 접근 방식은 중요도 샘플링(importance sampling)에 의존하여 높은 분산을 유발하거나, 목적 함수를 변경하는 복잡한 변수 변환에 의존하여 종종 이론적 수렴 보장을 포기합니다. 본 연구가 다루는 핵심 과제는 다음과 같습니다: 중요도 샘플링과 같은 명시적인 오프-폴리시 교정 기술에 의존하지 않고도 오프-폴리시 AIL의 수렴을 보장하고 샘플 효율성을 확보할 수 있는가?

방법론

저자들은 정책 업데이트를 위한 **모델 기반 미러 디센트(model-based mirror descent)**와 보상 업데이트를 위한 **오프-폴리시 투영 경사 상승법(off-policy projected gradient ascent)**을 결합한 오프-폴리시 AIL 알고리즘을 제안합니다. 핵심 혁신은 보상 업데이트 중에 재사용할 과거 정책의 수($N$)를 신중하게 선택함으로써 분포 변화 오류를 제어하는 데 있습니다.

1. 정책 업데이트

알고리즘은 모델 기반 미러 디센트 방식을 채택합니다.

• 모델 추정: 상태-행동 조우로부터 상태 전이 함수 $\hat{P}_h$를 경험적으로 추정합니다.
• 정책 최적화: 정책은 KL-다이버전스 정규화된 미러 디센트 단계(식 3)를 사용하여 업데이트됩니다. 추정된 Q-값으로부터 유도된 이 업데이트 규칙은 연속적인 정책 간의 총 변동(Total Variation, TV) 거리를 제한할 수 있을 만큼 정책 변화를 보수적으로 유지하도록 보장합니다. 이러한 안정성은 오프-폴리시 보상 업데이트에서의 분포 변화를 제어하는 데 매우 중요합니다.

2. 보상 업데이트

알고리즘은 현재 정책 $\pi_{k-1}$의 데이터만을 사용하는 대신, $N(k)$개의 가장 최근 정책으로부터 얻은 데이터의 혼합(mixture)을 활용합니다.

• 혼합 분포: 알고리즘은 혼합 분포 $d^{k-1, mix}_h = \sum_{n=1}^{N} \beta_n d^{k-n}_h$에서 샘플링하며, 여기서 $\beta_n$은 균등 가중치입니다.
• 목적: 보상 파라미터 $\mu$는 손실 $L(\pi^{k-1, mix}, \mu) = J(\pi_E, \mu) - \frac{1}{N}\sum_{n=1}^N J(\pi_{k-n}, \mu)$를 최대화하기 위해 투영 경사 상승법을 통해 업데이트됩니다.
• 오류 제어: 이론적 분석(Lemma 4.2 및 Theorem 4.3)은 정책 업데이트가 충분히 작게 유지된다면(단계 크기 $\sigma$에 의해 제어됨), 혼합 분포와 현재 정책의 분포 사이의 다이버전스가 유계(bounded)임을 입증합니다.

3. 이론적 프레임워크

AIL 알고리즘의 후회(regret)는 정책 후회와 보상 후회로 분해됩니다(Lemma 3.2). 저자들은 두 가지 모두에 대한 경계값을 도출합니다:

• 정책 후회: 미러 디센트 업데이트를 사용하여 $\tilde{O}(\sqrt{H^4 S^2 A K})$로 유계됩니다.
• 보상 후회: 표준 후회, 오프-폴리시 업데이트로 인해 발생하는 오류 항, 그리고 추정 오류 항으로 구성된 항으로 유계됩니다(Theorem 4.4).
• 주요 결과 (Theorem 4.5): 재사용되는 정책의 수 $N(k)$가 $o(\sqrt{K})$의 속도로 스케일링된다면, 전체 후회는 반복 횟수 $K$에 대해 아선형(sublinear)입니다. 구체적으로, $N$이 고정된 경우 최적의 스케일링은 $N^* = \tilde{O}((S/(HAB))^{1/3})$입니다.

주요 기여

1. 교정 없는 수렴 보장: 본 논문은 중요도 샘플링과 같은 오프-폴리시 교정 기술을 요구하지 않는 오프-폴리시 AIL 알고리즘에 대한 최초의 이론적 수렴 보장을 제공합니다.
2. 샘플 효율성 분석: 저자들은 $o(\sqrt{K})$개의 가장 최근 정책으로부터 샘플을 재사용하는 것이 수렴을 저해하지 않음을 입증했습니다. 그들은 특히 상태 공간의 크기($S$)가 호라이즌($H$) 및 행동 공간($A$)에 비해 클 때, 분포 변화 오류가 데이터 가용성 증가의 이점에 의해 압도된다는 것을 증명했습니다.
3. 실질적 검증: 제안된 알고리즘은 이산 공간인 MiniGrid 태스크와 연속 공간인 OpenAI Gym (MuJoCo) 벤치마크 모두에서 검증되었으며, 오프-폴리시 변형($N > 1$)이 온-폴리시 변형($N=1$)보다 더 빠르게 수렴하고 더 적은 샘플을 필요로 함을 보여주었습니다.

실험 결과

• MiniGrid (이산): 다양한 크기($3\times3, 5\times5, 9\times9$)의 EmptyRoom 태스크에서 $N=32$인 오프-폴리시 알고리즘은 약 1,000회의 상호작용만으로 전문가 수준의 성능을 달성한 반면, 온-폴리시 알고리즘($N=1$)은 수렴을 위해 전체 10,000회의 상호작용 호라이즌이 필요했습니다. 이 결과는 더 큰 상태 공간이 더 큰 $N$의 이점을 얻는다는 점을 확인시켜 주었습니다.
• MuJoCo (연속): HalfCheetah, Hopper, Walker2d 태스크에서 오프-폴리시 알고리즘은 온-폴리시 베이스라인보다 일관되게 우수한 성능을 보였습니다. 최적의 $N$은 환경마다 달랐지만, 작은 $N$(예: $N=4$ 또는 $N=16$)에서도 상당한 이득이 관찰되었습니다.
• 관찰 사항: 실험은 오프-폴리시 AIL이 우수한 샘플 효율성을 달-성할 수 있다는 이론적 주장을 뒷받침하며, 오프-폴리시 데이터로 인해 발생하는 "오류"가 데이터 가용성 증가에 따른 통계적 이점에 의해 상쇄된다는 점을 보여줍니다.

의의 및 주장

본 논문은 이론적 이해와 실질적 적용 사이의 간극을 메운다고 주장합니다. 이전 연구들이 오프-폴리시 AIL의 실질적인 성공을 보여주었으나 엄격한 수렴 증명이 부족했던 것과 달리, 본 연구는 다음을 입증합니다:

• 이론적 지원: 보수적인 정책 업데이트와 재사용되는 정책 수의 제한을 통해 분포 변화를 제어함으로써 오프-폴리시 AIL의 수렴을 보장할 수 있습니다.
• 샘플 효율성: 오프-폴리시 데이터로 인해 발생하는 "오류"는 특히 고차원 상태 공간에서 더 많은 데이터를 보유함으로써 얻는 통계적 이점에 의해 이론적으로 상쇄됨이 입증되었습니다.
• 단순성: 제안된 방법은 중요도 샘플링과 같은 복잡한 분산 감소 기술을 피하며, 이는 실제 샘플 효율성에 대한 경험적 관찰과 일치하는 더 단순하고 이론적 근거가 확실한 대안을 제공합니다.

저자들은 본 연구의 이론적 분석이 테이블(tabular) 설정을 가정하고 있으며(부록에서 선형 MDP로 확장됨), 딥 RL(MuJoço)에서의 최적 $N$이 신경망 파라미터화로 인해 이론적 최악의 경계값과 완벽하게 일치하지 않을 수 있지만, 성능 추세는 여전히 이론과 일치한다고 겸허히 언급하였습니다.