DAgger : A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning (2011)

항목	내용
제목	A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning
저자	Stéphane Ross, Geoffrey J. Gordon, J. Andrew Bagnell
발표	AISTATS 2011 (Proceedings of the 14th International Conference on Artificial Intelligence and Statistics)
소속	Carnegie Mellon University
핵심 알고리즘	DAgger (Dataset Aggregation)

---

Main Idea

문제: 분포 이동과 오류의 제곱적 복합

순차 예측(sequential prediction)이란 시간 $t = 1, 2, \ldots, T$에 걸쳐 현재 상태 $s_t$를 관측하고 행동 $a_t$를 선택하는 과정이다. 전통적인 지도학습 기반 모방 학습은 전문가(expert) $\pi^*$가 방문하는 상태 분포 $d_{\pi^*}$ 위에서 정책 $\hat{\pi}$을 학습한다. 즉, 전문가 궤적에서 (상태, 행동) 쌍을 수집하고 지도학습으로 정책을 학습하는 것이다.

그러나 실행 시(test time)에는 $\hat{\pi}$ 자신이 유도하는 분포 $d_{\hat{\pi}}$에서 행동해야 한다. $\hat{\pi}$가 전문가와 조금이라도 다른 행동을 하면, 그 이후로 전문가가 방문하지 않던 새로운 상태에 진입하게 되고, 그 상태에서 또 오류를 범하며 더욱 낯선 상태로 벗어난다. 이것이 오류의 복합(compounding errors) 문제다.

정량적으로, 전문가 분포 하에서 학습된 정책의 시간당 평균 오류가 $\epsilon$이라면, 실행 시 실제 비용은 최대 다음과 같이 증가한다:

여기서 $T$는 궤적 길이(horizon), $u$는 하나의 실수가 미래에 미치는 최대 추가 비용, $\epsilon$은 전문가 분포 하에서의 최선 모방 오류다. 즉, 단순 지도학습은 $T^2$ 수준의 제곱적 성능 저하를 피할 수 없다.

이 문제를 해결하려는 기존 접근법들은 각각 고유한 한계를 가졌다.

방법	정책 유형	이터레이션 수	성능 보장
지도학습 (Supervised)	결정론적 정상	1	$J(\pi^*) + uT^2\epsilon$
Forward Training	비정상(T개 분리)	$T$	$J(\pi^*) + uT\epsilon$
SMILe / SEARN	확률적 정상(혼합)	$O(T^2 \log T)$	$J(\pi^*) + uT\epsilon$
DAGGER	결정론적 정상	$\tilde{O}(T)$	$J(\pi^*) + uT\epsilon_N$

Forward Training은 $T$가 크거나 미리 정의되지 않으면 비현실적이다. SMILe과 SEARN은 성능 보장을 선형으로 개선하지만, 반복마다 이전 정책들을 혼합하는 확률적(stochastic) 정책을 학습하므로 실행 시 불안정하고, 과도하게 많은 이터레이션($O(T^2 \log T)$)이 필요하다.

해결: No-Regret 온라인 학습으로의 환원

DAGGER의 핵심 통찰은 위 문제를 온라인 학습으로의 환원(reduction)으로 재해석하는 것이다.

원래 목표는 다음의 비볼록(non-convex) 문제를 푸는 것이다:

이것이 비볼록인 이유는 목적함수의 입력 분포 $d_\pi$ 자체가 최적화 변수 $\pi$에 의존하기 때문이다. $\ell(s, \cdot)$이 볼록이더라도 $\mathbb{E}_{s \sim d_\pi}[\ell(s,\pi)]$는 볼록이 아니다.

DAGGER는 이 문제를 다음과 같이 우회한다. 이터레이션 $i$에서 분포를 고정시키고, 고정된 분포 $d_{\pi_i}$ 위에서의 손실을:

로 정의한다. 이 손실은 $\pi$에 대해 볼록(convex)이다(분포가 $\pi$에 독립적이므로). 이제 각 라운드에서 볼록 손실이 주어지는 온라인 학습 게임으로 환원되었으므로, Follow-The-Leader(FTL) 등 임의의 no-regret 알고리즘을 적용할 수 있다.

No-regret 조건은 다음과 같이 표현된다:

이 온라인 학습의 후회(regret)가 0에 수렴하면, DAGGER는 목표 최적화 문제의 해에 점근적으로 도달한다.

---

Introduction

문제 설정과 동기

모방 학습(imitation learning)의 전통적인 접근은 전문가(expert)의 시연 데이터를 수집하고, 이를 지도학습으로 학습하여 정책(policy)을 만드는 것이다. 그러나 이 접근에는 근본적인 결함이 있다. 학습 시 사용한 전문가 시연의 상태 분포 $d_{\pi^*}$와, 학습된 정책 $\hat{\pi}$가 실제 실행 시 방문하는 상태 분포 $d_{\hat{\pi}}$가 서로 다르기 때문이다.

이 문제를 직관적으로 이해하면 다음과 같다. 자율주행 정책이 학습 시 한 번도 보지 못한 차선 이탈 상황에 처하면, 그 상황에서 어떻게 복구해야 하는지 전혀 학습하지 못했으므로 추가적인 실수를 범하고, 이 실수가 또 다른 전문가가 방문하지 않은 상태를 만들며 오류가 연쇄적으로 복합된다. $T$스텝 문제에서 이 복합 효과는 최악의 경우 비용을 $T^2$ 배로 증폭시킨다.

기존 접근법의 한계

논문은 기존 해결책들을 세 가지로 정리하고 각각의 한계를 명확히 진단한다.

• 지도학습(Supervised Approach): 가장 단순하지만 distribution shift로 인해 $T^2\epsilon$ 오류를 피할 수 없다.

• Forward Training: 각 타임스텝 $t$마다 별도의 정책 $\pi_t$를 순차 학습하여 비정상(non-stationary) 정책을 만든다. 이론적으로 성능 보장이 있으나 $T$가 크거나 미리 정해지지 않으면 비현실적이며, $T$개의 정책을 모두 저장하고 실행해야 한다.

• SMILe / SEARN: 반복마다 새 정책을 이전 정책들과 혼합(mix)하여 점진적으로 학습 분포를 개선한다. 그러나 두 가지 근본적 한계가 있다. 첫째, 반환되는 정책이 여러 정책의 확률적 혼합(stochastic mixture)이므로, 실행 중 무작위로 나쁜 정책을 선택할 가능성이 상존한다. 둘째, 이론적 보장을 위해 $O(T^2 \log T)$번의 이터레이션이 필요하다.

DAGGER의 위치

이러한 배경에서 DAGGER는 다음 목표를 동시에 달성한다.

• 결정론적 정상 정책: 실행 시 무작위성이 없는 단일 정책
• 선형 성능 보장: $J(\hat{\pi}) \leq J(\pi^*) + uT\epsilon_N$ ($u$는 환경 상수, $\epsilon_N$은 학습 오류)
• 효율적 이터레이션: $\tilde{O}(T)$ 이터레이션으로 충분
• 단순한 구현: 기존 지도학습 알고리즘을 블랙박스로 재사용 가능

---

2. Preliminaries

기본 표기법과 문제 정의

논문은 다음 설정 하에서 순차 예측을 정의한다.

• 상태 공간 $\mathcal{S}$: 입력 상태(이미지, 텍스트 컨텍스트 등)
• 행동 공간 $\mathcal{A}$: 정책의 출력(조향값, 다음 문자 등)
• 정책(policy) $\pi: \mathcal{S} \to \mathcal{A}$: 상태를 행동으로 매핑하는 함수
• 지평선(horizon) $T$: 예측 스텝 수
• 비용 함수 $C: \mathcal{S} \times \mathcal{A} \to [0, 1]$: 각 스텝의 즉각적 비용
• 전문가 정책 $\pi^*$: 최적 또는 근사 최적 참조 정책

정책 $\pi$의 총 기대 비용은

이고, 여기서 $d_\pi^t$는 정책 $\pi$가 $t$번째 스텝에서 방문하는 상태의 분포이다. $d_\pi = \frac{1}{T}\sum_{t=1}^T d_\pi^t$를 정책 $\pi$의 평균 상태 방문 분포(average state visitation distribution)로 정의하면

로 간결하게 쓸 수 있다. 대리 손실(surrogate loss) $\ell: \mathcal{S} \times \mathcal{A} \to [0, 1]$은 $C$를 상한(upper bound)하도록 선택되며, 0-1 분류 오류가 대표적인 예이다.

정책 클래스 $\Pi$ 내에서 DAGGER가 달성하려는 목표는

이다. 이 문제가 직접 풀기 어려운 근본 이유는 목적함수의 입력 분포 $d_\pi$ 자체가 최적화 변수 $\pi$에 의존하기 때문이다. $\ell(s, \pi)$이 $\pi$에 대해 볼록이더라도 $\mathbb{E}_{s \sim d_\pi}[\ell(s, \pi)]$은 비볼록(non-convex)이 된다. 두 정책 $\pi_A$와 $\pi_B$의 볼록 결합 $\pi_\lambda$에 대해 $d_{\pi_\lambda} \neq \lambda d_{\pi_A} + (1-\lambda)d_{\pi_B}$이므로 표준 볼록 최적화 도구를 직접 적용할 수 없다.

Theorem 2.1 (Ross and Bagnell, 2010) Theorem 2.2를 통해 전문가 Q-함수와 대리 손실 간의 연결이 확립된다. $\pi$와 $\pi^*$ 사이의 행동 차이로 인한 미래 누적 비용 증가분이

를 만족하는 상수 $u$가 존재하면, 정책 $\pi$의 기대 총 비용은

로 바운드된다. 이 결과는 DAGGER가 $\mathbb{E}_{s \sim d_\pi}[\ell(s, \pi)]$를 최소화하는 것이 곧 $J(\pi)$를 $J(\pi^*)$에 가깝게 만드는 것임을 보장한다.

2.1 Supervised Approach to Imitation

지도학습의 오류 복합 분석

가장 단순한 모방 학습은 전문가가 방문하는 상태에서 행동 데이터를 수집하고 지도학습을 수행하는 것이다:

이 방법의 문제를 수식으로 이해하면 명확하다. 학습된 정책이 달성하는 전문가 분포에서의 손실을 $\epsilon$이라 하면 $\mathbb{E}_{s \sim d_{\pi^*}}[\ell(s, \hat{\pi})] \leq \epsilon$이다. 그러나 우리가 실제로 원하는 것은 자신의 분포에서의 성능 $\mathbb{E}_{s \sim d_{\hat{\pi}}}[\ell(s, \hat{\pi})]$이다.

두 분포 $d_{\pi^*}$와 $d_{\hat{\pi}}$ 사이의 차이를 TV 거리로 측정하면 최대 $T$까지 증가할 수 있다. 이를 활용하면

이고, 최악의 경우 $\|d_{\hat{\pi}} - d_{\pi^*}\|_1 = O(T\epsilon)$이 되어 (정책이 각 스텝에서 $\epsilon$ 확률로 실수하고 실수 후 분포가 완전히 달라지는 경우)

이 된다. 이것이 논문이 “Quadratic growth”라 부르는 오류 복합 현상이다. $T=100$인 시스템에서 지도학습이 $\epsilon=0.01$의 손실을 달성해도 실제 비용은 $100^2 \times 0.01 = 100$ 배 증가할 수 있다.

Theorem 2.1이 이를 정식화한다: 지도학습으로 학습된 정책 $\hat{\pi}$가 $\epsilon = \mathbb{E}_{s \sim d_{\pi^*}}[\ell(s, \hat{\pi})]$를 달성하면

2.2 Forward Training

비정상 정책의 순차 학습

Forward Training은 distribution shift 문제를 우회하기 위해 각 타임스텝에 독립적인 정책을 학습한다. 구체적으로, 스텝 $t$의 정책 $\pi_t$는 이전에 학습된 정책들 $\pi_1, \ldots, \pi_{t-1}$을 실행하여 수집한 상태 분포 $d^t_{\pi_{1:t-1}}$에서 지도학습으로 학습된다.

이 접근의 이론적 보장은 다음과 같다. 각 정책 $\pi_t$가 자신의 학습 분포에서 $\epsilon_t$의 손실을 달성하면

지도학습의 $T^2\epsilon$ 대비 선형 $uT\epsilon$으로 개선된다.

한계: 첫째, $T$개의 서로 다른 정책 $\pi_1, \ldots, \pi_T$를 학습하고 보관해야 한다. 둘째, 실행 시점 $t$를 알아야 올바른 $\pi_t$를 선택할 수 있다. 셋째, $T$가 미리 정해지지 않거나 가변적인 경우 적용 불가능하다. 이 세 가지 이유로 Forward Training은 비정상(non-stationary) 정책이라는 근본 한계를 갖는다.

2.3 Stochastic Mixing Iterative Learning

SMILe과 SEARN의 구조

SMILe(Stochastic Mixing Iterative Learning)과 SEARN은 반복적으로 정책을 개선하면서 distribution shift 문제를 완화한다. 기본 아이디어는 학습된 정책 $\hat{\pi}_i$와 전문가 $\pi^*$를 혼합하여 다음 이터레이션의 탐색 정책을 만드는 것이다.

SMILe의 핵심 절차를 요약하면 다음과 같다.

• 이론적 보장: SMILe은 $uT\epsilon$ 수준의 선형 보장을 달성하지만, 반환하는 정책이 확률적 혼합(stochastic mixture)이라는 근본 문제가 있다.
  구체적으로 $N$번 이터레이션 후 반환 정책은 $\sum_{i=1}^N w_i \hat{\pi}_i$로, 매 스텝마다 어느 $\hat{\pi}_i$를 실행할지 무작위로 선택한다. 단 하나의 나쁜 $\hat{\pi}_i$가 혼합 내에 남아있으면 그 이터레이션이 선택될 때마다 나쁜 결정이 내려진다.

SEARN은 구조화 예측 맥락에서 유사한 아이디어를 구현한다. 두 방법 모두 보장을 얻으려면 $\alpha$가 충분히 작아야 하는데, 이는 $O(T^2 \log T)$번의 이터레이션을 요구한다. $T$가 큰 경우 이는 비현실적으로 많은 반복 횟수다.

---

3. Dataset Aggregation

핵심 아이디어: 데이터셋 집계

DAGGER의 직관은 다음 질문에서 출발한다: "정책이 방문하는 상태에서 전문가 레이블을 수집하여 훈련 데이터에 추가하면 어떻게 될까?"

점진적으로 정책의 유도 분포 $d_{\hat{\pi}}$를 커버하는 데이터가 축적되면서, 결국 정책이 자신이 방문하는 모든 상태에서 올바른 행동을 학습하게 된다.

알고리즘은 다음과 같다.

• 입력: 전문가 정책(Expert Policy) $\pi^*$, 정책 클래스(Policy Class) $\Pi$, 혼합 비율 스케줄(Mixing Ratio Schedule) $\{\beta_i\}$ ($\beta_i \in [0,1]$)

• 출력: 검증 성능 기준 최선 정책 $\hat{\pi}_i$

• 초기화: 데이터셋 $D \leftarrow \emptyset$, $\hat{\pi}_1 \leftarrow \Pi$에서 임의 선택반복 수행 ($i = 1, 2, ..., N$):

Step 1. 혼합 정책(Mixture Policy) 구성
$\pi_i = \beta_i \cdot \pi^* + (1-\beta_i) \cdot \hat{\pi}_i$
(매 시간 스텝마다 독립적으로: $\beta_i$ 확률로 전문가 행동 선택, $1-\beta_i$ 확률로 현재 학습 정책 행동 선택)

위 수식은 궤적(Trajectory) 전체를 전문가나 학습자 중 한 명에게 온전히 맡기는 방식이 아니다. 매 시간 스텝(Time Step)마다 독립적으로 동전을 던져 누구의 행동(Action)을 따를지 결정한다.

• 이론적 의미: $T$ 스텝 전체에서 단 한 번도 전문가가 개입하지 않을 확률은 $(1-\beta_i)^T$이다. 알고리즘의 오차 한계를 수학적으로 증명할 때, 매 스텝 분리되어 확률적으로 개입한다는 이 가정이 핵심적으로 쓰인다.

• 실무적 적용: 10분짜리 주행 테스트를 할 때, 매 초마다 주사위를 굴려 베테랑 강사가 핸들을 잡을지 초보자가 핸들을 잡을지 결정하며 주행 데이터를 생성하는 것과 같다. 일반적으로 학습 횟수 $i$가 증가할수록 $\beta_i$의 값을 0에 가깝게 줄여나가면서 초보자(학습 정책)가 스스로 판단하는 비중을 점진적으로 높인다.

Step 2. $\pi_i$ 실행하여 $T$-스텝 궤적(Trajectory) 수집
방문 상태: $s_1, s_2, ..., s_T$

Step 3. 방문 상태에 전문가 레이블(Expert Label) 부여
$D_i = \{(s, \pi^*(s)) : s \in \{s_1,...,s_T\}\}$(실제로 취한 행동과 무관하게 $\pi^*$를 레이블로 사용)

데이터셋을 구성할 때, 방문한 모든 상태(State) $s$에 대해 당시의 실제 행동 주체가 누구였는지와 무관하게 오직 전문가 정책 $\pi^*(s)$의 행동만을 정답 레이블로 기록한다.

• 이론적 의미: 이 단계에서 가장 중요한 것은 해당 상태 $s$가 방문되었다는 사실 자체다.
  학습 모델이 아직 미숙하여 엉뚱한 상태 영역으로 벗어났더라도, 그 낯선 상태에서 어떻게 행동해야 하는지 전문가의 정답을 쿼리하여 데이터셋에 추가한다.
  이를 통해 모방 학습 특유의 분포 이동(Distribution Shift) 문제를 교정한다.

• 실무적 적용: 운전 연수 중 초보자가 실수로 차를 중앙선 부근까지 몰고 갔다고 가정한다.
  중앙선을 밟을 뻔한 아찔한 상황(상태 $s$)을 만든 원흉은 초보자이지만, 오답 노트(데이터셋)에는 '중앙선 부근에 위치했을 때의 정답 = 강사의 신속한 차선 복귀 핸들링($\pi^*(s)$)'이라고 기록하는 것과 같다.
  당시에 실제로 강사가 핸들을 뺏었는지, 초보자가 당황해서 브레이크를 밟았는지 등은 데이터 기록에 전혀 영향을 주지 않는다.

Step 4. 데이터셋 누적 집계
$D \leftarrow D \cup D_i$

Step 5. 집계된 전체 $D$에서 지도 학습(Supervised Learning)
$\hat{\pi}_{i+1} = argmin_{\pi \in \Pi} E_{(s,a) \in D}[\ell(s,\pi)]$

• 종료: 검증 성능 기준 최선 $\hat{\pi}_i$ 반환

β 스케줄의 설계

혼합 비율 $\beta_i$의 선택이 알고리즘의 거동을 결정한다. 이론적 요구 조건은 단 하나다:

이를 만족하는 다양한 스케줄이 가능하며, 논문은 세 가지를 구체적으로 분석한다.

스케줄 1: $\beta_i = \mathbb{I}(i=1)$

첫 번째 이터레이션에서만 $\beta_1 = 1$ (순수 전문가), 이후에는 $\beta_i = 0$ (순수 학습 정책). 이 설정은 파라미터가 전혀 없고, 실전에서 대부분의 경우 가장 좋은 성능을 보인다. 이론적으로도 보정 항(correction term)이 $\frac{2\ell_{\max}}{N}$으로 가장 빠르게 사라진다.

스케줄 2: $\beta_i = p^{i-1}$ (기하급수적 감소)

$p \in (0, 1)$을 파라미터로 하며, $p=0.5$이면 이터레이션마다 전문가 비율이 절반씩 줄어든다. 초반에 전문가가 적극적으로 개입하여 다양한 상태를 탐색하게 한 후 점차 학습 정책으로 이행한다. SMILe/SEARN의 $\beta$ 스케줄과 구조적으로 동일하지만, DAGGER는 혼합 정책이 아닌 집계 데이터 위에서 단일 결정론적 정책을 학습한다는 점에서 결정적으로 다르다.

$n_\beta$를 $\beta_{n_\beta} > \frac{1}{T}$를 만족하는 마지막 이터레이션 인덱스로 정의하면, $\beta_i = (1-\alpha)^{i-1}$에서

이고, $n_\beta$ 이후의 $\beta_i$ 합산은

이므로 보정 항 전체는 $\tilde{O}\!\left(\frac{\log T}{N\alpha}\right)$이 된다.

스케줄 3: 상수 $\beta_i = \beta$

이 경우 $\bar{\beta}_N = \beta \not\to 0$이므로 이론적 보장이 성립하지 않는다. 그러나 $\beta$가 충분히 작으면 실용적으로 잘 작동할 수 있으며, SMILe의 설정과 유사하다.

반환 정책 선택

논문은 두 가지 동등한 반환 전략을 제시한다. 첫째, 별도 검증 데이터에서 가장 좋은 $\hat{\pi}_i$를 선택한다. 둘째, $\hat{\pi}_1, \ldots, \hat{\pi}_N$ 중 균등 랜덤으로 하나를 선택한다. 두 번째 전략이 동일한 이론적 보장을 제공하는 이유는 Section 4에서 설명한다.

DAGGER가 결정론적 정상 정책을 반환하는 이유

이것이 SMILe/SEARN 대비 가장 중요한 차별점이다. SMILe은 $\sum_i w_i \hat{\pi}_i$를 반환하는데, 이는 실행 시 매 스텝마다 어느 $\hat{\pi}_i$를 사용할지 무작위로 선택하는 확률적 정책이다. 반면 DAGGER는 집계 데이터셋 $D = \bigcup_{i=1}^N D_i$ 전체로 학습한 단일 정책 $\hat{\pi}_i$를 반환한다. 이 정책은 완전히 결정론적이며, 실행 시 무작위성이 없다.

레이싱 게임처럼 단 한 번의 잘못된 판단이 돌이킬 수 없는 결과를 낳는 환경에서, 확률적 정책이 “운 나쁘게” 나쁜 서브 정책을 선택하는 상황이 발생하지 않는다는 것이 결정론적 정책의 핵심 이점이다.

---

4. Theoretical Analysis

분석의 전체 구조

이론 분석의 목표는 DAGGER가 반환하는 정책 $\hat{\pi}$의 성능

이 얼마나 작은지 바운드하는 것이다. 이를 달성하기 위해 두 가지 핵심 요소가 결합된다. 하나는 혼합 정책 $\pi_i$와 학습 정책 $\hat{\pi}_i$ 사이의 분포 차이를 연결하는 Lemma 4.1이고, 다른 하나는 온라인 학습 알고리즘의 no-regret 성질이다.

Lemma 4.1 (분포 이동 바운드)

혼합 정책 $\pi_i = \beta_i \pi^* + (1-\beta_i)\hat{\pi}_i$가 유도하는 분포와 학습 정책 $\hat{\pi}_i$가 유도하는 분포 사이의 TV 거리는

증명의 핵심은 $T$스텝 궤적에서 $\hat{\pi}_i$만 사용되는 사건의 확률이 $(1-\beta_i)^T$라는 사실이다. 이로부터

여기서 $\tilde{d}$는 전문가가 적어도 한 번 개입했을 때의 조건부 분포이다. 따라서

마지막 부등식은 베르누이 부등식 $(1-\beta)^T \geq 1 - \beta T$에서 온다. 이 바운드가 trivial bound인 2보다 유용하려면 $\beta_i \leq \frac{1}{T}$이어야 한다. 이것이 $n_\beta$의 역할이다: $n_\beta$ 이후의 이터레이션에서만 Lemma 4.1이 의미 있는 개선을 제공한다.

이 Lemma를 통해 데이터 수집 시 사용한 분포 $d_{\pi_i}$에서의 손실과, 실제로 원하는 $d_{\hat{\pi}_i}$에서의 손실을 연결할 수 있다:

4.1 Online Learning

온라인 학습으로의 환원

DAGGER의 이론적 핵심은 비볼록한 모방 학습 문제를 볼록 손실의 온라인 학습 문제로 환원하는 것이다.

각 이터레이션 $i$에서 손실함수를 다음과 같이 정의한다:

이 정의의 핵심은 분포 $d_{\pi_i}$가 현재 이터레이션에서 고정되어 있다는 점이다. 따라서 $\ell_i(\pi)$는 $\pi$에 대해 볼록이다 ($d_{\pi_i}$가 $\pi$에 독립적이므로 $\ell(s, \cdot)$의 볼록성이 그대로 전파된다). 이로써 매 라운드에 볼록 손실을 받는 표준 온라인 학습 설정이 된다.

DAGGER의 각 이터레이션에서 FTL(Follow-The-Leader)을 적용하면, 이터레이션 $i+1$에서의 정책은

이다. 이것이 정확히 “집계된 데이터셋 전체에서 지도학습(ERM)을 수행”하는 것과 동일하다. $\ell_j(\pi)$의 경험적 추정이 이터레이션 $j$에서 수집된 데이터의 평균 손실이기 때문이다.

FTL의 No-Regret 성질

FTL은 일반적인 온라인 학습에서 불안정성 문제가 있을 수 있지만, 손실함수 $\ell(s, \cdot)$이 강볼록(strongly convex)한 경우 $O(\log N / N)$의 평균 후회(average regret)를 달성한다. 0-1 손실처럼 일반적인 경우에도 FTL은 다음을 보장한다:

이때 no-regret 알고리즘으로 임의의 방법(OGD, FTRL 등)을 사용해도 동일한 분석 구조가 적용된다는 점이 중요하다. 논문은 특정 온라인 학습 알고리즘에 의존하지 않고, 임의의 no-regret 알고리즘이 DAGGER와 결합하면 성능 보장을 달성함을 보인다.

4.2 No Regret Algorithms Guarantees

Theorem 4.1: 핵심 성능 보장 (무한 샘플)

Lemma 4.1과 FTL의 no-regret 성질을 결합하면 다음 정리가 도출된다.

Theorem 4.1: DAGGER가 $N$번 이터레이션 후 반환하는 최선 정책은

를 만족한다. 여기서

• $\epsilon_N = \min_{\pi \in \Pi} \frac{1}{N}\sum_{i=1}^N \ell_i(\pi)$: 모든 방문 분포의 혼합 위에서 최선 정책의 평균 손실 (표현력 한계)
• $\gamma_N$: 온라인 학습 알고리즘의 평균 후회 (이터레이션이 증가하면 0으로 수렴)
• 마지막 항: $\beta_i$ 스케줄로 인한 분포 이동 보정 항

증명의 단계별 전개는 다음과 같다.

Step 1: 보조 정리(Lemma 4.1)를 이용한 손실(Loss) 변환
평가 분포($d_{\hat{\pi}_i}$)에서의 손실을 훈련 분포($d_{\pi_i}$)에서의 손실로 변환한다.

$\mathbb{E}_{s \sim d_{\hat{\pi}_i}}[\ell(s, \hat{\pi}_i)] \le \mathbb{E}_{s \sim d_{\pi_i}}[\ell(s, \hat{\pi}_i)] + 2\ell_{max} \cdot \min(1, T\beta_i) = \ell_i(\hat{\pi}_i) + 2\ell_{max} \cdot \min(1, T\beta_i)$

Step 2: 시퀀스(Sequence) 평균 취하기
여러 번 학습을 반복하여 얻은 정책들의 평균을 계산한다. '최솟값은 항상 평균보다 작거나 같다'는 기본 성질을 이용한다.
$\min_{\hat{\pi} \in \hat{\pi}_{1:N}} \mathbb{E}_{s \sim d_{\hat{\pi}}}[\ell(s,\hat{\pi})] \le \frac{1}{N} \sum_{i=1}^N \mathbb{E}_{s \sim d_{\hat{\pi}_i}}[\ell(s,\hat{\pi}_i)]$

위 식에 Step 1의 결과를 대입하여 전개한다.
$\le \frac{1}{N} \sum_{i=1}^N \ell_i(\hat{\pi}_i) + \frac{2\ell_{max}}{N} \sum_{i=1}^N \min(1, T\beta_i)$

이를 항에 따라 정리하면 다음과 같다.
$= \frac{1}{N} \sum_{i=1}^N \ell_i(\hat{\pi}_i) + \frac{2\ell_{max}}{N}\left[n_\beta + T\sum_{i>n_\beta} \beta_i\right]$

Step 3: 후회 방지(No-regret) 성질 적용
온라인 학습(Online Learning)의 후회 방지 알고리즘 특성을 적용하여, 학습 모델의 누적 손실 평균 상한을 정의한다.
$\frac{1}{N} \sum_{i=1}^N \ell_i(\hat{\pi}_i) \le \min_{\pi} \frac{1}{N} \sum_{i=1}^N \ell_i(\pi) + \gamma_N = \epsilon_N + \gamma_N$실무적 이해: 학습을 계속 반복할수록, 우리가 만든 모델의 평균 손실은 결국 '가장 이상적인 완벽한 정책의 손실($\epsilon_N$)'에 '온라인 학습 과정에서 필연적으로 발생하는 평균 후회($\gamma_N$)'를 더한 값 이하로 수렴한다는 의미다.

Step 4: 결과 결합 (Theorem 4.1 도출)
Step 2의 수식에 Step 3의 결과를 대입하여 최종적인 성능 상한을 도출한다.

$\min_{\hat{\pi}} \mathbb{E}_{s \sim d_{\hat{\pi}}}[\ell(s,\hat{\pi})] \le \epsilon_N + \gamma_N + \frac{2\ell_{max}}{N}\left[n_\beta + T \sum_{i>n_\beta} \beta_i\right]$

균등 랜덤 선택의 동치성: 최솟값 대신 정책을 균등 무작위(Uniform Random)로 선택하더라도 동일한 성능 보장을 받는다.

그 이유는 Step 2의 첫 번째 부등식 우변(시퀀스 평균) 자체가 전체 정책들의 기대 성능을 나타내기 때문이다.

무작위 추출 전략의 기댓값은 시퀀스의 평균과 일치하므로, 평균이 바운드 상한선 내에 있다면 무작위 선택 역시 동일한 상한선을 가진다.

Theorem 4.2: 유한 샘플 보장

실제 학습에서는 각 이터레이션마다 유한한 $m$개의 궤적만 수집할 수 있다. 유한 샘플 설정에서는 $\ell_i(\pi)$의 경험적 추정과 실제 기댓값 사이의 편차가 발생하며, 이를 마팅게일 집중 부등식으로 제어한다.

Theorem 4.2: 이터레이션당 $m$개의 궤적을 수집하면, 확률 $1-\delta$로

추가 항 $\ell_{\max}\sqrt{\frac{2\log(1/\delta)}{mN}}$이 통계적 오차를 포착한다.

이 항이 등장하는 구조를 이해하기 위해 확률변수 $Y_{ij}$를 정의한다:

$Y_{ij}$는 이터레이션 $i$의 $j$번째 궤적에서 발생하는 경험적 손실과 기댓값 손실의 차이다.

이 변수들이 마팅게일(martingale)을 형성하는 이유는, $\hat{\pi}_i$가 이터레이션 $i$ 이전의 데이터로부터 학습되어 현재 샘플링과 독립적이기 때문이다. 따라서 $\mathbb{E}[Y_{ij} \mid Y_{11}, \ldots, Y_{i,j-1}] = 0$이 성립한다.

$|Y_{ij}| \leq \ell_{\max}$이므로 Azuma-Hoeffding 부등식을 적용하면, 확률 $1-\delta$로

이 마지막 항이 $O(1/T)$ 이하가 되려면 $mN = O(T^2\log(1/\delta))$가 필요하다.

$m=O(1)$이면 $N = O(T^2\log(1/\delta))$이터레이션이 필요하여 무한 샘플 케이스의 $\tilde{O}(T)$보다 $T$ 배 더 많다.

논문은 손실함수가 강볼록인 경우 Kakade and Tewari (2009)의 결과를 활용하여 이를 $\tilde{O}(T\log(T/\delta))$로 개선할 수 있다고 언급하지만 해당 증명은 미래 작업으로 남긴다.

이론의 세 가지 항 해석

전체 바운드를 구성하는 세 가지 항은 각각 독립적인 의미를 지닌다.

항	의미	제어 수단
$\epsilon_N$	정책 클래스 $\Pi$의 표현력 한계, 최선 정책의 근사 오차	더 표현력 있는 $\Pi$ 선택
$\gamma_N$	온라인 학습 알고리즘의 수렴 속도	이터레이션 수 $N$ 증가
보정 항	전문가 혼합으로 인한 분포 이동의 잔여 효과	$\beta_i$ 스케줄 및 $N$ 조절

$N$이 충분히 크고 $\beta_i \to 0$이면 $\gamma_N$과 보정 항 모두 0으로 수렴하며, 결국 DAGGER는 $\epsilon_N$에 의해서만 제한되는 정책을 학습한다. 이는 정책 클래스의 표현력이 허용하는 한 최선의 결과임을 의미한다.

이를 Theorem 2.2와 결합하면 임의의 비용 함수 $C$에 대한 최종 보장이 된다:

$N \to \infty$ 극한에서 DAGGER가 반환하는 정책의 비용은 $J(\pi^*) + uT\epsilon_N$에 수렴한다.

이것이 기존 지도학습의 $J(\pi^*) + uT^2\epsilon$보다 $T$ 배 개선된 선형 보장이다.

---

5. Experiments

논문은 세 가지 서로 다른 특성을 가진 환경에서 DAGGER를 평가한다. Super Tux Kart는 복구 불가능한 실수가 있는 연속 제어 문제, Super Mario Bros.는 복잡한 장애물 회피가 필요한 이산 제어 문제, OCR 필기 인식은 순서 의존성이 있는 구조화 예측 문제이다. 세 실험 모두 동일한 비교 대상(지도학습, SMILe, SEARN)과 공정한 데이터 예산 하에서 평가된다.

공통 실험 설정으로, 기저 학습기(base learner)는 모두 선형 모델(linear classifier 또는 linear regressor)이며 DAGGER의 reduction 구조가 기존 지도학습 알고리즘을 블랙박스로 재사용한다는 점을 실증적으로 보여준다.

5.1 Super Tux Kart

실험 설계

Super Tux Kart의 Star Track은 공중에 떠 있는 레이스 트랙으로, 트랙 가장자리에 방호벽이 없어 카트가 언제든지 트랙 밖으로 추락할 수 있다. 이 구조는 복구 불가능한 실수(unrecoverable mistake)를 만들어내어 오류 복합 문제가 가장 극단적으로 드러나는 환경이다.

• 입력 특징: 800×600 원본 이미지를 25×19로 리사이즈한 LAB 색공간 값 (1,425개 실수 특징)
• 출력: $[-1, 1]$ 범위의 연속 조향값 (회귀 문제)
• 전문가: 게임 내 내장 AI 컨트롤러
• 평가 지표: 랩당 평균 추락 횟수 (Average Falls Per Lap, 낮을수록 좋음)
• 비교 대상: DAGGER ($\beta_i = \mathbb{I}(i=1)$), SMILe ($\alpha=0.1$), 지도학습

결과 분석

결과는 DAGGER의 우월성을 가장 명확하게 보여준다. 지도학습은 데이터가 아무리 많아도 랩당 약 3~4회 추락에서 전혀 개선되지 않는다. 전문가 궤적만으로는 트랙 이탈 직전 상태나 위험한 조향 후 복구 상황을 학습할 수 없기 때문이다. SMILe은 일부 개선을 보이지만 20 이터레이션 후에도 랩당 약 2회 추락이 남는다. 확률적 혼합 정책 내의 나쁜 서브 정책이 가끔 선택되면서 치명적인 실수를 유발한다.

반면 DAGGER는 약 5 이터레이션(~5,000개 데이터 포인트)만에 추락 횟수가 거의 0에 근접하고, 15 이터레이션 이후 완전히 0을 달성한다. 이 환경에서 오류 복합의 $u$ 값이 크기 때문에(트랙 이탈 시 비용이 매우 크고 복구 불가) 지도학습의 $T^2\epsilon$ 문제가 극명하게 드러나며, 동시에 DAGGER의 결정론적 정책이 이를 완전히 해결함을 보여준다.

5.2 Super Mario Bros.

실험 설계

Mario AI 경쟁 시뮬레이터를 사용하며, 학습 정책이 마리오를 제어하여 스테이지를 최대한 멀리 진행시키는 것이 목표다.

• 입력 특징: 마리오를 중심으로 한 22×22 셀 그리드에서 14개 이진 특징(지형/적/블록 유형) × 4 프레임 히스토리 + 6개 이전 행동 + 마리오 상태 = 총 27,152개 이진 특징
• 출력: {left, right, jump, speed} 4개 이진 버튼 조합 (분류 문제)
• 전문가: Robin Baumgarten의 A* 기반 플래너 (Mario AI 경쟁 우승 알고리즘)
• 평가 지표: 스테이지당 평균 이동 거리 (전체 스테이지 길이 약 4,200, 높을수록 좋음)
• 비교 대상: D0 ($\beta_i=\mathbb{I}(i=1)$), D0.5 ($\beta_i=0.5^{i-1}$), D0.9 ($\beta_i=0.9^{i-1}$), Se1 (SEARN $\alpha=1$), Se0.4 (SEARN $\alpha=0.4$), Sm0.1 (SMILe $\alpha=0.1$), Sup (지도학습)

결과 분석

이 실험은 $\beta_i$ 스케줄 간의 트레이드오프를 상세히 보여준다는 점에서 특히 흥미롭다.

지도학습(Sup)은 약 1,100~1,200 거리에서 정체된다. 장애물(적, 구덩이) 앞에서 멈추거나 제자리를 맴도는 상황을 학습하지 못했기 때문이다. D0 ($\beta_i=\mathbb{I}(i=1)$)는 약 2,980 거리를 달성하고 빠르게 수렴하지만, 첫 이터레이션에서 학습된 나쁜 정책이 마리오를 특정 장애물 앞에 반복적으로 멈추게 하여 해당 상황 데이터가 과다 수집되는 경향이 있다.

D0.5 ($\beta_i=0.5^{i-1}$)는 약 3,030으로 최고 성능을 달성한다. 초반에 전문가가 적극 개입하면서 다양한 상황을 탐색하여 더 균형 잡힌 데이터를 수집하기 때문이다. 이는 탐색-활용 트레이드오프(exploration-exploitation tradeoff)의 모방 학습 버전으로 해석할 수 있다. D0.9는 수렴이 매우 느려 20 이터레이션에서도 개선 중이며, $\beta_i$가 천천히 감소할수록 학습 정책으로의 전환이 늦어져 수렴이 지연됨을 보여준다.

Se1 (SEARN $\alpha=1$, 순수 정책 반복)은 매우 불안정하여 성능 편차가 크다. 새 정책으로 완전히 교체할 때 분포가 급격히 변화하여 발산 위험이 있기 때문이다. Se0.4는 비교적 안정적이지만 DAGGER 변형들 모두를 밑돈다. Sm0.1은 약 2,000 수준에 머물러 확률적 정책의 한계를 다시 한번 보여준다.

전반적으로 모든 DAGGER 변형($\beta_i$ 설정 무관)이 SMILe과 SEARN의 최선 설정을 상회한다.

5.3 Handwriting Recognition

실험 설계

OCR 필기 인식 실험은 DAGGER가 구조화 예측 문제에도 유효함을 보이기 위해 설계되었다. Taskar et al. (2003)의 데이터셋을 사용하며, 필기 단어를 구성하는 문자들을 순서대로 예측하는 문제다.

• 입력 특징: 각 문자는 128개 픽셀 특징 + 26개 이전 예측 문자 원-핫 인코딩 = 154개 특징 (이전 예측이 상태의 약 17%를 차지)
• 출력: 26개 알파벳 문자 중 하나 (분류 문제)
• 전문가: 올바른 이전 문자 레이블을 제공 (이상적 전문가)
• 평가 지표: 테스트 폴드 문자 정확도 (Character Accuracy, 높을수록 좋음)
• 비교 대상: DAgger ($\beta_i=\mathbb{I}(i=1)$), SEARN($\alpha=1$), SEARN($\alpha=0.8$), SEARN($\alpha=0.1$), SMILe($\alpha=0.1$), Supervised, No Structure

No Structure 베이스라인은 이전 문자 정보를 전혀 사용하지 않고 독립적으로 예측하는 경우로, 이전 예측의 순서 의존성을 모델링하는 것의 가치를 확인하는 기준점이다.

결과 분석

No Structure는 82.0%, 지도학습은 83.6%로, 이전 문자 정보를 추가하는 것이 1.6%p 개선을 준다. 이는 이전 예측의 순서 의존성이 분명히 존재함을 보여준다. 그러나 지도학습은 훈련 시 항상 올바른 이전 문자를 조건으로 사용하지만 테스트 시에는 자신이 예측한 (오류 가능성 있는) 이전 문자를 사용한다. 이 훈련-테스트 불일치가 정확히 distribution shift 문제다.

DAGGER는 85.5%로 최고 성능을 달성하며, 약 5 이터레이션만에 빠르게 수렴한다. SEARN($\alpha=1$)과 SEARN($\alpha=0.8$)도 약 85% 수준에 도달하여 이 실험에서는 DAGGER와 격차가 작다. 이는 앞서 언급한 상태의 정책 의존 비율(17%)이 낮아 distribution shift가 완만하기 때문이다. 분포 이동이 작을수록 순수 정책 반복조차 안정적으로 작동할 수 있다.

반면 SEARN($\alpha=0.1$)과 SMILe($\alpha=0.1$)은 83~84% 수준으로 DAGGER보다 유의미하게 낮다. 작은 $\alpha$는 수렴 속도를 낮추고, 20 이터레이션 내에서 전문가 의존도를 충분히 낮추지 못하여 학습 정책이 자신의 분포에 적응할 시간이 부족하다.

문헌 비교 관점에서도 주목할 만하다. Taskar et al. (2003)의 M3N이 약 87%, Ratliff et al. (2007)의 SSVM이 약 86%인데, DAGGER는 단순한 greedy 디코딩(beam search 없이)만으로 85.5%를 달성한다. 디코딩 전략을 복잡하게 만드는 것보다 정책 자체가 자신의 분포에 적응하도록 학습하는 것이 더 효과적일 수 있음을 시사한다.

세 실험을 종합하면 다음과 같다.

실험	평가 지표	Supervised	SMILe (best)	SEARN (best)	DAGGER (best)
Super Tux Kart	랩당 추락 횟수 ↓	~3.5 (정체)	~2.0	N/A	0 (15iter 이후)
Super Mario Bros.	스테이지당 이동거리 ↑	~1,100	~2,000	~2,600	~3,030
OCR 필기 인식	문자 정확도 ↑	83.6%	~83.5%	~85.0%	85.5%

세 실험 모두에서 DAGGER가 기존 방법을 능가하거나 동등한 성능을 보였으며, 파라미터 없는 $\beta_i = \mathbb{I}(i=1)$ 설정이 대부분의 경우 경쟁력 있는 결과를 제공한다는 점이 실용성 측면에서 중요하다.

---

6. Future Work

논문은 여러 방향의 후속 연구를 명시적으로 제안한다.

역최적제어와의 결합

가장 직접적으로 언급하는 방향은 역최적제어(Inverse Optimal Control, IOC) 기법을 기저 분류기로 활용하는 것이다. 현재 DAGGER는 전문가 행동 $\pi^*(s)$를 레이블로 직접 모방하지만, IOC를 통해 전문가 데이터로부터 비용 함수 $C$를 역으로 학습하여 플래너(planner)에 제공하는 방식으로 확장할 수 있다. 이는 단순 행동 복제를 넘어 전문가의 의도(intent) 수준을 학습하는 것으로, 이후 GAIL(Ho and Ermon, 2016) 등의 연구로 구체화되었다.

강화학습으로의 확장

논문은 cost-to-go 추정치를 레이블로 활용하는 방향도 제시한다. 현재 DAGGER는 전문가의 즉각적 행동을 레이블로 사용하지만, 각 상태에서 전문가의 미래 누적 비용 $Q^{\pi^*}(s, a)$를 레이블로 활용하면 전문가가 놓친 더 나은 행동을 학습할 수 있다. 이는 이후 AggreVaTe(Ross and Bagnell, 2014)로 발전했으며, 수식으로 표현하면 DAGGER의 레이블 $\pi^*(s)$ 대신

를 사용하는 것으로, 전문가를 능가하는 정책 학습이 이론적으로 가능해진다.

온라인 강화학습 이해

논문의 마지막 문장에서 암시하는 방향으로, DAGGER와 유사한 기법이 온라인 강화학습 방법들의 성공을 이론적으로 설명하는 데 기여할 수 있다고 본다. 정책이 방문하는 분포에서 점진적으로 학습하는 구조가 강화학습의 정책 경사(policy gradient) 방법들과 본질적으로 유사하며, DAGGER의 no-regret 분석 틀이 이를 통합적으로 이해하는 언어를 제공한다.

샘플 복잡도 개선

유한 샘플 보장에서 이론과 실제의 간극($O(T^2)$ vs 실험에서의 $O(T)$ 수준)을 좁히는 것도 중요한 방향이다. 특히 강볼록 손실함수에서 $\tilde{O}(T \log(T/\delta))$ 이터레이션으로 개선할 수 있다는 주장의 완전한 증명이 필요하다.

쿼리 효율성

논문이 직접 명시하지는 않지만, 매 이터레이션마다 방문한 모든 상태에서 전문가를 쿼리하는 비용 문제가 자연스러운 후속 연구 방향이다. 불확실성이 높은 상태에서만 선택적으로 전문가를 쿼리하는 능동 학습(active learning) 전략과의 결합이 이후 SafeDAgger, HG-DAgger 등으로 발전하였다.