[강화학습] 6. n-step Bootstrapping

n-step Bootstrapping

n-step Bootstrapping은 Temporal difference의 일반화된 버전이다. 

MC는 episode의 끝까지의 return을 학습하는 방법으로, variance가 크다. 왜냐하면 가능한 모든 episode들 중 sampling 한 것을 학습하기 때문이다.

반면 TD(0)는 bootstrapping 기반이라, 추정값을 이용해 추정한 값을 학습하고, 심지어 1-step만 학습하기때문에 bias가 크다.

n-step Bootstrapping은 MC와 TD(0)를 결합해 1-step TD를 n-step TD로 일반화 하여 bias를 줄이기 위한 학습 방법이며, n-step TD라고도 불린다. (추후에 나올 eligibility trace의 기본 idea가 된다. )

n-step TD가 bias를 줄일 수 있는 방법은 위 식에 잘 표현되어 있다.

bias의 핵심 원인은 추정값을 학습하는 bootstrapping인데, 위 n-step return을 잘 살펴보면, 최대한 (t+n-1)까지는 관측되는 실제 reward를 사용하고, 마지막에만 추정값을 사용하는 방법을 취하고 있다. 즉, bootstrap의 비중을 낮추고, MC와 같이 여러 스텝을 학습한다고 할 수 있다.

n-step TD Prediction

앞서 미리 소개했지만, n-step TD가 bootstrapping 할 때, TD(0)와 같이 one-step만 보는 것이 아니라 위와 같이 n-step을 확인하여 return을 구한다.

그럼 그 정의에 따라 n-step TD Prediction은 위와 같이 표현할 수 있다.

※ 참고로 V의 아래첨자는 iteration되면서 update되는 횟수라 이해하면 된다. (ex. V가 V0였다가 V1으로 update)

• G ← Σ γ ... 항에서 t+n-1 만큼은 Reward를 직접 쓰고
• if τ + n < T, then: G←G+γV(S) 항에서 마지막에만 추정값을 쓰는 것을 확인할 수 있다.

물론 앞서 배운 SARSA알고리즘을 적용해서 n-step SARSA로 구현할 수 있다.

SARSA를 적용하기 위해 Return을 아래와 같이 표현하면

아래와 같이 prediction function을 표현할 수 있다.

참고로 전체 action의 평균을 취해 expected Sarsa를 구하기 위해서는 return을 아래와 같이 구하면 된다.

n-step off-policy learning

off-policy learning은 on-policy learning에 비해 exploration을 계속하면서도 optimal한 policy를 학습할 수 있다는 것이었다.

이 것이 가능한 이유에 대해 알아보기 위해 importance sampling개념에 대해서 먼저 알아보자.

Importance sampling

importance sampling은 off-policy control에서 behavior policy ≠ target policy인데도 optimal 한 policy를 학습할 수 있다는 근거가 된다.

우리가 어떤 probability mass function(PDF) π(x)를 알고 있다고 했을 때, 어떤 사건이 일어날 expected확률은 위와 같이 구할 수 있다. 

그리고 π(x)를 근사화 하기위해 우리는 모집단에서 sampling을 몇개 해서 이게 모집단을 대표하길 기대해야한다. 이것이 바로 sample mean이고 sample이 무수히 많으면 optimal로 간다는 것이 큰수의 법칙(law of large numbers)이다.

마찬가지로 이걸 sample space가 아니라 functional space에서도 볼 수 있다.

즉, 무수히 많은 expected function g(x)를 구할 수 있다면 optimal function을 expect 할 수 있다는 것이다. 하지만 이 모든 과정은 π로 부터 sampling이 가능할때 이야기다.

만약 π로부터 sampling도 못한다면 이 때는 어떻게 해야할까? 이 때 사용하는 방법이 importance sampling이다.

importance sampling은 π(x)로 sampling이 어려울 때 사용하는 trick으로써, 새로운 분포 μ(x)에서 sampling한뒤 본래의 분포로 맞춰줌으로써 π(X)를 추정하는 방법이다.

즉, π(x)의 PDF는 알고 있지만 현실적으로 sampling하기 어려운 경우, sampling이 쉬운 근사 분포에서 대신 sampling하는 기법이다. 이 때 π(X) / μ(x)를 importance weight이라고 한다.

(우린 policy π는 expect 하지만, 자율주행문제를 실제로 수행해서 sampling을 할 순 없다.)

(하지만 신호를 위반했을 때 사고가 날 확률 μ의 분포는 알고 있다면, 두 분포를 비교할 수 있다.) 

off-policy learning은 importance sampling의 원리에 따라,

• behavior policy π는 greedy하게,

• target policy μ는 더 exploratory policy를 취하는 또 다른 분포를 사용한다.

그리고 두 분포의 상대적인 확률 importance weight(혹은 importance ratio)를 return에 곱(weight)하며, 어떤 정책 π에 의해 At, St+1 ... ST가 발생할 확률은 아래와 같다.

위 식은 state transition probability (dynamics의 변형 형태)이며, 결국 behavior policy - target policy에서 발생하는 상대적인 확률과 이를 활용해 value function를 추정하는 방법은 다음과 같다.

이 원리를 그대로 차용해 optimal policy를 control할 수 있다.

솔직히 이해를 했다가도 수학적으로 완벽하게 이해는 못하겠지만, 결국 위 과정을 통해 이야기 하고 싶은 것은,

Off-policy method는 On-policy method보다 더 exploring 된 optimal policy로 수렴한다는 것이 guarantee 된다는 것인것 같다.

Summary

• n-step TD는 delay of n time step before updating을 갖는다.

• 그래서 forever time step for updating이 될 수 있는 MC의 단점을 보완할 수 있었고,

• one-step 만 봄으로써 bias가 자칫 높을 수 있는 TD(0)의 단점을 보완했다고 할 수 있다.

• 그리고 대망의 Importance sampling 원리가 off-policy method에 적용되었고,

• 덕분에 exploring 된 optimal policy를 찾을 수 있다.