[강화학습7] MC(Monte Carlo Methods)와 TD(Temporal Difference Learning)

 

이번 포스팅에서는 MC와 TD에 대해서 알아보도록 하자. 두 방법 모두 model-free일 때 가치 추정을 할 수 있게 해 준다.

model-based와 model-free

이번 포스팅에서는 에이전트가 MDP의 구조를 알지 못할 때 어떻게 가치를 추정하는지에 대해 이야기해보려고 한다. '에이전트가 MDP를 모른다'는 것은 에이전트가 자신의 행동에 대해 환경이 어떻게 반응할지 알지 못한다는 의미이다. 이런 상황을 model-free라고 부르며, 반대로 에이전트가 MDP를 알고 있는 상황은 model-based라고 부른다.

몬테카를로 방법(Monte Carlo Methods, MC)

100원짜리 동전을 던졌을 때 앞면이 나온다면 동전을 갖고 뒷면이 나오면 가질 수 없다고 가정해 보자. 우리는 정확한 확률은 모르지만, 예컨대 10번 던져서 앞면이 3번 나왔다면 기댓값은 30원이라고 볼 수 있다. 만약 10번 던져서 나온 기댓값이 충분히 정확하지 않다고 판단된다면 100번, 1000번 혹은 그보다 더 많이 던져보면 된다. 즉, 시행 횟수가 많아질수록, 표본평균은 모평균에 가까워지며, 얼핏 당연하게 느껴지는 이것을 큰 수의 법칙이라고 한다. 몬테카를로 방법은 우리가 생각할 수 있는 가장 간단한 방법으로 큰 수의 법칙을 활용해, 관측된 누적 보상을 바탕으로 가치를 추정하는 방법이다. 이에 근간이 되는 식은 다음과 같다.

$$ v_\pi(s_t) = \mathbb {E}_\pi [G_t]$$

가치를 추정하는 데는 단순히 누적 보상을 평균 내는 방법 외에 업데이트하는 방식이 있다. ^[각주:1]

$$V(s_t) \leftarrow V(s_t) + \alpha(G_t - V(s_t))$$ 

일반적으로 업데이트 방식을 사용할 경우 Robbins-Monro 조건^[각주:2]을 만족하도록 설정하게 된다. 조건을 만족하는 학습률로 업데이트할 경우 다음과 같은 이점이 있다.

1. 학습이 진행될수록 학습률이 점차 줄어드는 형태가 되고, 현재 정책에 대해 안정된 추정치로 수렴한다.

2. 평균방식에 비해 계산이 간편하고, 학습률을 시간, 성능, 기타 조건에 따라 조절가능한 유연성을 갖추었다

3. 학습초기에는 높은 학습률로 인해  초기 정책들에 대한 가치평가가 빠르게 희석된다. 따라서(다음포스팅에서 다룰 내용이지만) 학습초기의 빈번한 정책변경으로 인해 가치추정이 불안정해지는 문제를 어느 정도 해소할 수 있다.

Temporal Difference Learning(TD)

MC에는 치명적 단점이 하나 있다. 바로 업데이트를 하려면 에피소드가 끝날 때까지 기다려야 한다는 점이다. 업데이트를 위해서는 누적보상이 필요한데 누적보상은 에피소드가 끝나기 전까지는 계산할 수 없기 때문이다. 따라서 종료하지 않는 MDP(Non-Episodic MDP)에서는 MC를 사용한 가치추정이 불가능하다. 이를 해결하기 위한 TD의 접근 방식은 다음과 같다.

추측을 추측으로 업데이트하자 ^[각주:3]

즉, 현재 상태의 가치 추정을 하는 데 있어서 다음상태의 가치를 이용하는 것이다. 이에 근간이 되는 식은 다음과 같다

$$v_\pi(s_t) = \mathbb {E}_\pi [r_{t+1} + \gamma v_\pi(s_{t+1})]$$

 

---

$v_\pi(s_t) = \mathbb {E} _\pi [G_t]$

                $= \mathbb {E} _\pi [r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots]$

                $= \mathbb {E} _\pi [r_{t+1} + \mathbb {E} _\pi [ \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots]]$^[각주:4]

                $= \mathbb {E} _\pi [r_{t+1} + \mathbb {E} _\pi [ \gamma(r_{t+2} + \gamma r_{t+3} + \cdots) ]]$

                $= \mathbb {E} _\pi [r_{t+1} + \gamma \mathbb {E} _\pi [r_{t+2} + \gamma r_{t+3} + \cdots ]]$^[각주:5]

                $= \mathbb {E} _\pi [r_{t+1} + \gamma v _\pi (s_{t+1})]$

---

그러나 뭔가 이상하지 않은가? 현재 상태의 가치추정을 하기 위해서는 다음상태의 가치를 알아야 한다. 즉, 모든 상태의 가치를 알아야만 각각의 상태 가치를 계산할 수 있다는 모순이 있다. 그러나, 다행히도 실제 가치함수를 알지 못하는 상황에서도, TD업데이트를 반복적으로 적용하면 특정 조건하에서 실제 가치함수에 점점 더 가까워진다는 것이 수학적으로 증명되었다.

$$V(s_t) \leftarrow V(s_t) + \alpha(r_{t+1} + \gamma V(s_{t+1}) - V(s_t))$$

TD와 MC비교

성능

TD가 MC보다 일반적으로 실제 가치함수에 더 빠르게 수렴하는 것으로 알려져 있는데, 이는 다양한 환경에서 이루어진 경험적 관찰을 통해 밝혀진 바이다. 이러한 빠른 수렴의 주된 이유는 MC와 다르게 TD가 에피소드가 완료될 때까지 기다릴 필요 없이 각 스텝에서 학습 결과를 즉시 업데이트하기 때문으로 보인다.

편향성(Bias) 비교

편향성은 추정값의 평균이 실제값에서 얼마나 떨어져 있는지를 나타내는 지표이다. MC의 경우 실제 보상을 기반으로 가치추정을 하며, 여러 개의 샘플이 모일수록 추청값의 평균은 실제값에 가까워진다. 따라서 MC는 편향되어 있지 않은(unbiased) 방법이다. 반면 TD는 가치추정치를 이용해 가치추정을 하는 부트스트래핑 방식이기 때문에 오차가 누적되어 편향성이 더 클 수 있다.

분산(Variance) 비교

TD는 한 스텝 뒤의 추정치와 현재 보상을 이용하여 현재 상태의 가치를 업데이트한다. 반대로, MC는 완료된 에피소드의 누적 보상을 사용하여 현재 상태의 가치를 업데이트하는데, 이로 인해 TD보다 상대적으로 분산이 클 수 있다. 이를 비유하자면, TD 방법은 마치 햄버거를 먹고 있는 사람의 현재 상태를 앞으로 5분 후의 다음 상태와 즉시 보상을 통해 예측하는 것과 유사하다. 이 경우, 이 사람에게 일어날 수 있는 가장 나쁜 일은 콜라를 몸에 쏟는 정도이고, 가장 좋은 일은 햄버거를 맛있게 다 먹는 것 정도일 것이다. 반면, MC 방법은 마치 햄버거를 먹고 있는 사람의 현재 상태를 그 사람의 인생 전체로부터 평가하는 것과 같다. 인생 전체의 관점에서 보면, 이 사람에게 앞으로 일어날 수 있는 최악의 시나리오와 최고의 시나리오는 보다 더 극단적일 것이다.

n-step TD

앞서 소개했던 TD는 현재 상태$s_t$에서 한스탭만큼 진행하여 실제 보상을 관찰하고, 도착한 상태 $s_{t+1}$의 가치를 평가했다. 여기서 생각해 볼 점은 꼭 한 스텝만 가서 평가해야 할 이유가 없다는 점이다. 

---

n=1 : $r_{t+1} + \gamma v_\pi(s_{t+1})$  

n=2 : $r_{t+1} + \gamma r_{t+2} + \gamma^2 v_\pi(s_{t+2})$

$\cdots$

n=N : $r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots + \gamma^n v_\pi(s_{t+n})$

종료 시점의 스텝을 T라고 할 때

n=∞ : $r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots + \gamma^{T-1} r_T$

---

n이 무한으로 갈 때 n-step TD는 리턴이 된다. 따라서 MC와 TD는 서로 다른 독립적인 방법이라기보다 한 방법론에서 양극단에 위치한 형태라고 생각할 수 있다.

1. 일반적으로 실제 가치함수는 소문자, 추정된 가치함수는 대문자로 표기한다. [본문으로]
2. 1. 학습률의 합이 무한대: $\sum_{t=1}^{\infty} \alpha_t = \infty
   $
   2. 학습률의 제곱합이 유한대 $\sum_{t=1}^{\infty} \alpha_t^2 < \infty$ [본문으로]
3. 이러한 방식을 부트스트래핑(Bootstrapping)이라고 하며, 추정치를 업데이트하기 위해 다른 추정치를 사용하는 것을 말한다. [본문으로]
4. a. $c$가 상수일 경우 $\mathbb {E}[X + c] = \mathbb {E}[X] + c$
    b. $\mathbb {E}[ X + Y] = \mathbb {E}[X]+  \mathbb {E}[Y]$ [본문으로]
5. $c$가 상수일 경우 $ \mathbb {E}[cX] = c \mathbb {E}[X]$ [본문으로]