Theoretical Analysis of Behavior Cloning

How can we provide a theoretical analysis of the supervised learning method in Behavior Cloning (Imitation Learning)? 

Above figure is about learning driving style for parking. 

Problem setting

: There exists an experts whose state distribution is '$d_{\pi^*}$' and action distribution (policy) is '$\pi^*(s)$'. From such distributions, one can obtain a training dataset consists of state-action pairs. Finally, from the state-action pairs, one can train a policy '$\pi$' which minimizes a loss function '$l(s, a, \pi)$'. Suppose that the empirical error of the learned policy '$\pi$' is 

$$\epsilon = E_{s \sim d_{\pi^*}, a \sim \pi^*(s)} [ l(s, a, \pi) ]. $$

Theorem (Ross and Bagnell, 2010) Let '$\epsilon = E_{s \sim d_{\pi^*}, a \sim \pi^*(s)}[l(s, a, \pi)]$'. If '$l$' upper bounds the '$0-1$' loss, and '$C$' is bounded in '$[0, C_{max}]$', then

$$J(\pi) \le J(\pi^*)+ C_{max}T^2 \epsilon.$$

위의 식은 우리가 학습시킨 policy '$\pi$'가 학습 데이터를 형성하는데 사용된 전문가의 policy '$\pi^*$'에 비해서 얼마나 성능이 차이가 나는지 (나쁜 쪽으로)를, 그 bound를 계산해준다. 즉 만약 우리가 '$T$' time horizon 만큼 prediction을 해야하는 sequential prediction을 하고 있다면, 우리가 학습시킨 policy의 성능은 최대 '$C_{max}T^2\epsilon$'만큼 나쁘다는 의미이다. 예측하는 시간에는 quadratic하게, empirical error에는 linear하게 성능이 나빠진다는 것을 알 수 있다. 

Proof:

Let '$d_t$' be a state distribution at time '$t$' while executing the learning policy '$\pi$'. 

Let '$p_t$' be the probability that learned policy '$\pi$' picked the same action as an expert '$\pi^*$' until time '$t$'. 

'$p_t$'는 '$t$'까지 우리가 학습시킨 policy가 expert와 계속 같은 행동을 했을 확률이다. 

Then, '$d_t$' can be expressed as follows

$$d_t = p_{t-1} d_t^{(c)} + (1-p_{t-1})d_t^{(e)}$$

where '$d_t^{(c)}$' is the state distribution at time '$t$' if the learning policy '$\pi$' picked the same action as '$\pi^*$' until time '$t$' and '$d_t^{(e)}$' is a state distribution of all complementary cases. 

Similarly, let '$d_t^*$' be the state distribution at time '$t$' of the expert while executing the expert policy '$\pi^*$'. Then '$d_t^*$' can be expressed as 

$$ d_t^* = p_{t-1}d_t^{(c)} + (1-p_{t-1}) d_t^{*(e)} $$

where '$d_t^{*(e)}$' is the state distribution of the expert at time '$t$' conditioned on the actions picked by the expert '$\pi^*$' and learned policy '$\pi$' differ from each other at least more than once.

 

여기서 주의할 점은 모든 policy가 stochastic 하다는 점이다. 전문가도 그렇고, 우리가 학습한 policy 역시 그렇다. 이러한 증명 테크닉은 몬가 신선하다. 키 아이디어는 어떤 식으로든 시간 '$t$'까지 '$\pi$'와 '$\pi^*$'가 같은 행동을 했을 때와, 다른 행동을 한번이라도 했을 때는 분리시키는 것 같다. 

Now during training, learner is trained under the distribution '$\frac{1}{T}\sum_{t=1}^T d^*_t$'. Let '$\epsilon_t$' the probability that '$\pi$' picks a different action that '$\pi^*$' in the state distribution '$d^*_t$'. By definition of '$\epsilon$', we have

$$ \frac{1}{T}\sum_{t=1}^T \epsilon_t \le \epsilon $$ where

$$ \epsilon = E_{s \sim d_{\pi^*}, a \sim \pi^*(s)}[l(s, a, \pi)].$$

'$\epsilon$'의 의미가 무엇일까? 학습 단계에서 에러를 뜻한다. 

'$\epsilon_t$'의 의미는 시간 '$t$'에서 우리가 학습한 policy가 전문가의 policy와 다른 행동을 할 확률이다. 이렇게 할 경우에 '$l(s, a, \pi)$'는 1을 return하게 될 것이다. 

그래서 '$\epsilon_t$'를 평균을 내게 될 경우 정의에 의해서 0-1 loss의 loss function의 '$l$'의 평균과 같고, 앞에서 '$l$'이 0-1 loss의 upper bound이기 때문에 '$\le$'가 된다. 

Now, let '$\epsilon_t^{(c)}$' be the probability that '$\pi$' picks different a different action than '$\pi^*$' in the state distribution '$d_t^{(c)}$' and let '$\epsilon_t^{*(e)}$' be the probability that '$\pi$' picks different a different action than '$\pi^*$' in the state distribution '$d_t^{*(e)}$'. Then we have

$$ \epsilon_t = p_{t-1}\epsilon_t^{(c)} + (1-p_{t-1}) \epsilon_t^{*(e)}. $$

위의 식이 의미하는 것은 '$t$'에서 우리가 구한 policy와 expert가 다른 선택을 할 확률은 지금까지 잘 하다가 갑자기 문제가 생길 확률 '$p_{t-1}\epsilon_t^{(c)}$'과 지금까지 잘못하다가 다시 잘못할 확률 '$(1-p_{t-1}) \epsilon_t^{*(e)}$'을 더한 것이라는 것이다. 

Since '$\epsilon_t^{*(e)} \ge 0 $', then

$$  \epsilon_t \ge p_{t-1}\epsilon_t^{(e)}. (*) $$

'$t$'에서 문제가 생길 확률은 이전까지 잘해오다가 '$t$'에서 갑자기 문제가 생길 확률보다는 당연히 크다. 

Additionally, 

$$ (1-p_t) = (1-p_{t-1}) + p_{t-1}\epsilon_t^{(c)}. (**) $$

위 식에서 좌변은 '$t$' 이전에 단 한번이라도 문제가 생겼을 확률이다. 

우변은 '$t-1$'까지 한번이라도 문제가 생겼을 확률에 '$t-1$'번째까지는 잘하다가 '$t$'번째에서 문제가 생겼을 확률을 더한 것이다. 즉 좌변과 우변은 같다. 

Combining '$(*)$' and '$(**)$', 

$$ (1-p_t) \le (1-p_{t-1}) +\epsilon_t. $$

위의 식에서 좌변은 '$t$'까지 한번이라도 문제가 생겼을 확률이고, 우변은 '$t-1$'까지 한번이라도 문제가 생겼을 확률에 '$t$'번째에서 문제가 생겼을 확률을 더하는 것이다. 우변에서 더해진 '$\epsilon_t$'는 '$t-1$'까지 잘하다가 '$t$'에서 갑자기 문제가 생길 확률과, 지금까지 한번이라도 잘못하다가 다시 문제가 생길 확률을 더한 것이기 때문에 우변이 좌변보다는 크다. 

Solving this recurrence, we have 

$$ (1-p_t) \le \sum_{i=1}^t \epsilon_i. $$

위 식의 의미는 꽤나 중요하다. '$t$'까지 한번이라도 문제가 생겼을 확률은 각 경우에 문제가 생겼을 확률의 합 보다는 작다는 것이다. 사실 굉장히 당연한 결과를 도출하기 위해서 많이 돌아온 느낌이 없지 않아 있다. 

Using all these facts, now consider the expected total cost '$J(\pi)$' of executing the policy '$\pi$'. Let

'$C_t$': expected immediate cost of executing '$\pi$' in state distribution '$d_t$' 

'$C_t^{(c)}$': expected immediate cost of executing '$\pi$' in state distribution '$d_t^{(c)}$'

'$C_t^{(e)}$': expected immediate cost of executing '$\pi$' in state distribution '$d_t^{(e)}$'.

We have 

$$ J(\pi) = \sum_{t=1}^T C_t$$

and

$$ C_t = p_{t-1}C_t^{(c)} + (1-p_{t-1})C_t^{(e)}. $$

'$C_t$'는 우리가 갖고 있는 policy '$\pi$'로 행동했을 때, state의 분포인 '$d_t$'에서 얻어지는 immediate cost이다. '$d_t$'자체가 '$d_t = p_{t-1} d_t^{(c)} + (1-p_{t-1})d_t^{(e)}$'로 분리되므로, '$C_t$' 역시 '$C_t = p_{t-1}C_t^{(c)} + (1-p_{t-1})C_T^{(e)}$' 이렇게 표현될 수 있다. 

Now since '$C \in [0, C_{max}]$', then '$C_t^{(e)} \le C_{max}$'.

Additionally, consider the immediate cost '$C_t^*$' and '$C_t^{*(c)}$' of executing '$\pi^*$' in state distribution '$d_t^*$' and '$d_t^{(c)}$'. Then '$J(\pi^*) = \sum_{t=1}^T C_t^*$' and because costs are non-negative, we must have '$C_t^* \ge p_{t-1}C^{*(c)}_t$'.

이제 전문가의 policy '$\pi^*$'를 수행했을 때 expected total cost '$J(\pi^*)$'에 대해서 생각해보자. 먼저 '$d_t^*$'가 '$\pi^*$'를 수행했을 때의 state distribution인 것을 기억하면, 그리고 '$C_t^*$'가 '$d_t^*$'에서 '$\pi^*$'를 수행했을 때 immediate cost임을 고려할 때, '$J(\pi^*) = \sum_{t=1}^T C_t^*$'는 당연하다. 게다가 '$d_t^* = p_{t-1}d_t^{(c)} + (1-p_{t-1}) d_t^{*(e)}$'이므로, '$C_t^* \ge p_{t-1}C^{*(c)}_t$'이다. ('$d_t^{(c)}$'에서 '$\pi^*$'를 수행하면 '$C_t^{*(c)}$'를 얻는다!)

마지막 식의 의미를 살펴보면 '$t$'에서 전문가의 행동으로 얻어지는 immediate cost는 우리가 갖고 있는 policy가 '$t-1$'까지 계속 옳은 행동을 한 후에 '$t$'번째에서 얻이지는 cost보다 크다이다. 당연한 소리이다. 일단 '$t_{t-1}$'이 엄청 작은 수일텐데..