[강화학습 기초] 몬테카를로와 시간차 예측

 

※ 본 글은 '[도서]파이썬과 케라스로 배우는 강화학습' 및 '[유튜브]혁펜하임의 트이는 강화학습'을 학습하고 작성한 글입니다. 

 

앞선 글을 통해 다이나믹 프로그래밍을 통해서도 최적 정책을 찾아갈 수 있음을 확인했다. 

다만 모든 상황, 행동에 대한 제어, 계산이 가능해야 하므로 현실의 문제에 적용하기에는 무리가 있었다.

 

실제 사람은 어떤 새로운 것을 배울 때,

'우선 시도 -> 결과 -> 다시 방법을 업데이트' 의 순서로 학습한다.

 

이러한 아이디어를 구현하는 강화학습의 기초가 되는, 몬테카를로 예측과 시간차 예측에 대해 알아보자. 

 

1. 몬테카를로 예측

몬테카를로 예측은 가치 함수를 추정할 때, 충분히 많이 수행한 후 평균을 계산하는 방법이다.

 

i번째 시나리오에서, 어떤 상태 s를 지난 후 반환 값을 $ G_i(s)$라고 하면, s의 가치 함수를 다음과 같이 추정할 수 있다.

 

$v_\pi(s) \sim \frac{1}{N}\sum_{i=1}^{N}G_i(s) $

몬테카를로 가치함수 추정

N을 무수히 크게한다면, 매우 정확하게 가치함수가 계산될 것이다. 

 

 

여기서 한가지 수정하자면, 전부 다 해본 후 평균을 내는 것보다, 매번 조금씩 평균에 근사하도록 수정해가는 것이 좋을 것이다.

따라서 위 식을 수정해보자.

 

 

$ \frac{1}{N}\sum_{i=1}^{N}G_i(s) = \frac{1}{N}(G_N + \sum_{i=1}^{N-1}G_i) $

 

먼저 $ G_1 \sim G_N$ 까지의 합은, $ G_N + G_1 \sim G_{N-1}$의 합과 같으므로, 위와 같이 나타낼 수 있다.

여기서 식을 아래와 같이 변형해도 유효하다.

 

$ \frac{1}{N}(G_N + \sum_{i=1}^{N-1}G_i) = \frac{1}{N}(G_N + (N-1)*\frac{1}{N-1}\sum_{i=1}^{N-1}G_i)$ 

 

여기서 $ \frac{1}{N-1}\sum_{i}^{N-1}G_i $이 $ V_{N-1}$ 임을 이용하면, 최종적으로 다음과 같은 형태로 정리할 수 있다. 

 

$  \frac{1}{N}(G_N + (N-1)*\frac{1}{N-1}\sum_{i=1}^{N-1}G_i) = \frac{1}{N}(G_N + (N-1)V_{N-1}) $

$ = \frac{1}{N}(G_N + NV_{N-1} - V_{N-1}) $

 

$ = V_{N-1} + \frac{1}{N}(G_N - V_{N-1}) $

몬테카를로 업데이트 수식

 

이렇게 수식을 변형함으로써, 매 시나리오마다 가치함수를 업데이트할 수 있다.

 

이를 조금 더 일반화 할 수 있다.

$ \frac{1}{N}$ 대신 스텝사이즈, $ \alpha$의 개념을 이용하자. 

스텝사이즈는, 변화량을 얼마나 받아들일지 결정하는 0과 1 사이의 수로 설정하면 된다. 

 

또, $ V_N 과 V_{N_1} $대신 업데이트를 의미하는 '$ \leftarrow $' 로 표기하자.

 

그럼 최종적으로 다음과 같은 일반식을 얻을 수 있다.

 

$ V(s) \leftarrow V(s) + \alpha(G(s) - V(s)) $ 

몬테카를로 업데이트 일반식

여기서 $ G(s) - V(s) $ 를 '오차' 라고 표현하기도 하며,

앞으로의 많은 알고리즘도 위 형태를 기반으로 하니, 잘 확인해두는 것이 좋다.

 

 

이때 몬테카를로 예측에서는 반환값을 어떻게 계산할까?

몬테카를로 예측은 직접 해본 후 근사하는 방법이므로, 실제 에피소드가 종료될 때 얻은 반환값을 통해 계산한다.  

즉, 실시간이 아니다.

 

이는 에피소드가 끝나는 시점까지 기다려야 한다는 의미이므로, 에피소드가 긴 문제의 경우 적절하지 않다.

또한 실제로 사람도 학습할 때, 모든 결과가 나온 후에야 다시 확인하지는 않는다.

 

예를 들어 바둑을 둘 때, 승부가 난 후에 모든 수를 복기하는 것이 아니라, 실시간으로 한수한수 자신의 수를 평가한다.

 

2. 시간차 예측

이를 해결할 수 있는 중요한 아이디어가 시간차 예측이다. 

 

$ V(s) \leftarrow V(s) + \alpha(G(s) - V(s)) $ 

몬테카를로 가치함수 업데이트 수식

 

다시 가치함수 업데이트 수식을 보면, 이번에 얻은 반환값과 가치함수의 차이를 통해 계속해서 가치함수를 조정해간다.

 

이 수식의 형태는 그대로 유지하되, 반환값을 실제 반환값이 아니라 다음 타임스탭의 값만 이용하게 된다.

정확히는, 보상과 다음 상태의 가치 함수를 이용한다. 

 

$ V(s) \leftarrow V(s) + \alpha(R_{t+1} + \gamma V(S_{t+1}) - V(s))  $

시간차 예측 가치함수 업데이트

 

앞선 글에서 반환값을 통해 가치함수를 정의할 때의 개념을 그대로 적용하면 된다. 

 

이렇게 업데이트를 수행하면, 에피소드가 마치기 전에 실시간으로 가치함수를 업데이트할 수 있다는 장점이 있다. 

 

다만 다음 타임스탭의 가치함수, $ R_{t+1} + \gamma V(S_{t+1}) $ 자체가 초기에는 정확하지 않은 상태이므로 '이렇게 해도 수렴할까?' 하는 의문이 들 수 있다.

이에 대해서는 충분히 많은 반복속에서, 수렴한다는 것이 증명되어 있다고 한다.

 

앞으로 다룰 대부분의 알고리즘에서는 시간차 예측을 이용할 것이다.

대표적으로 다음 글을 통해 SARSA와 큐러닝에 대해 알아보자.