우리는 policy iteration을 policy evaluation과 policy improvemet를 통해서 다이나믹 프로그래밍을 이용해 계산을 하였다.

그런데, 대부분의 문제는 다이나믹 프로그래밍을 적용하기 어렵다.

그 이유는 state가 너무 많을 수 도 차원이 증가할 수록 계산복잡도가 기하 급수적으로 증가하기 때문이다.

그럼 다이나믹 프로그래밍 같은 방법 말고 다른 방법이 있을까?

실제 사람은 cpu와 같이 계산을 빠르게 할 줄도 모르는데 어떻게 학습을 하는지를 생각 해보면 된다.

바둑을 아예 모르는 사람을 예를 들면,

그 사람은 일단 바둑을 해볼 것이다.

그리고 자신을 평가하고,

평가한대로 자신을 업데이트 하면서 이과정을 계속 반복해 나갈 것이다.

일단 해본다고 했었는데 그것이 이번에 설명할 몬테카를로에 관련된 부분이다.

몬테카를로 근사

우리가 이렇게 생긴 A의 넓이를 어떻게 구할 수 있을까?

적분을 하면 매우 복잡해 질것이다.

따라서 몬테카를로 근사를 통해 넓이를 구할 수 있는데,

저 직사각형 선안에 무작위로 점을 찍는다. 이것을 나중에 sampling이라고 한다.

충분히 많은 sampling을 얻으면 우리는 A에 찍힌 점들의 갯수와 직사각형의 넓이만 알면 쉽게 A의 넓이의 근사치를 구할 수 있다.

A의 넓이 = 직사각형 넓이 * (A찍힌 점의 갯수 / 전체 찍은 점의 갯수)

몬테카를로 예측

우리는 아까 몬테카를로 근사를 이용해서 한반도의 넓이의 근사치를 구하는 식을 만들어 보았다.

그럼 이 몬테카를로 근사를 policy evaluation에서 가치함수의 근사치를 구할 수 도 있을것 같다.

우리가 한반도 넓이를 구할 때 점하나를 찍는것을 가지고 sampling이라고 하였다.

그럼 가치함수의 근사치를 구할때는 어떻게 sampling을 해야할까?

agent가 한번의 에피소드를 간것을 가지고 sampling의 기준을 세워보면 될것같다.

여러번의 에피소드를 하면 충분한 sampling을 얻을 것이다.

이 얻은 sample들의 평균으로 참 가치함수를 추정할 수 있는데, 이것을 가지고 우리는 몬테카를로 예측이라고 한다.

우리는 끝이 있는 에피소드를 가지고 sampling을 얻어서 가치함수를 추정할 것이라고 했다.

그러면 어떤 값을 확인해야할까?

V(s) = E[R_t+1 + γR_t+2 + γ² R_t+3 + ... | S_t = s]

이 식은 벨만 기대 방정식이다.

정책 이터레이션을 할때 우리는 이 식을 사용했다.

그런데 정책 평가를 할때 우리는 다이나믹 프로그래밍을 사용했기 때문에 기댓값으로 계산하였는데,

이제는 무작위 sampling의 평균으로 기댓값을 계산하지 않고 참 가치함수를 예측 할 수 있다.

그럼 어떤 특정한 값을 평균을 낸다는 것인가?

이 그림은 반환값(return)인 것인데, 한 에피소드에서의 각 state에 해당하는 future reward들의 합이라고 보면된다.

우리는 여러번의 에피소드를 돌려서 각 state에 해당되는 반환값의 평균을 낼 것이다.

계산의 편의를 위해 특정state의 반환값만 생각 한다고하면 아래와 같은 식이 나올 것이다.

N(s) 는 s 라는 특정 state 를 샘플링을 얻기 위해 여러 에피소드 동안 방문한 횟수라고 생각하면 된다.

그 뒤에는 시그마식은 여러 에피소드 동안 특정 state를 방문했을때의 그 해당 에피소드의 future reward의 총 합이라고 보면 된다.

그럼 충분한 샘플링을 통해 평균값이 나올 것이다.

기억해야 되는점은 이런 몬테카를로는 정책 발전을 절대로 하지 않는다는 것이다.

정책은 처음 설정한 그대로의 정책을 그대로 사용한다.

아래는 이 식들을 좀더 정리한 것들이다.

이렇게 간단히 식이 정리가 된다.

여기서 G(s) - V(s)를 보고 우리는 오차라고 하고 1/n을 보고 stepsize라고 한다.

일반적으로 이 stepsize를 α 라고 한다.

α는 일정할 수도 있고 아닐 1/n과 같을 수도 있다.

α가 일정하다는 말은 과거보다 현재 에피소드로 부터 얻은 값들을 더 중요시 여긴다는 말이된다.

여기서 이제 G(s)는 업데이트의 목표가 될것이다.

그리고 α(G(s) - V(s))는 업데이트의 크기가 될것이다.

시간차 예측

방금까지 했던 몬테카를로 예측의 단점이 무엇일까??

우리는 이 Return 값을 얻으려면 에피소드 하나를 끝내야 구할 수 가 있다.

만약 에피소드가 엄청 긴 문제같은 경우 또는 에피소드의 끝이 없는 문제 같은경우는 몬테카를로 예측을 사용하기 좀 그렇다.

그래서 나온게 시간차 예측 (temporal-difference prediction)이다.

예시를 하나 들어보자,

만약 바둑을 둘줄 모르는 한 사람이 학습을 할 때,

바둑을 두면서 학습을 할까? 아니면 바둑 게임을 다 끝내 놓고 나서 학습을 할까?

당연히 바둑을 두면서 학습을 할것이다. 이러한 개념을 적용한 것이 시간차 예측이라고 보면 된다.

이것이 바로 시간차 예측이다.

아까와 다르게 state가 대문자이다.

우리는 이것을 가지고 random variable 이라고 했다.

정해진 한 state에 대해서만 보는것이 아니라는 말이다.

여기서 말하는 R_t+1 + γV(S_t+1) 이 업데이트의 목표가 되겠고

α(R_t+1 + γV(S_t+1) - V(S_t)) 이 업데이트의 크기가 될것이다.

이와같은 시간차 예측을 사용하면 실시간으로 value값을 업데이트 할 수 있으며 몬테카를로 예측보다 효율적으로 빠른시간 안에 참 가치함수에 근접 한다고 한다.

제가 올린 글에서 잘못된 부분이 있으면 제 메일로 연락주세요!

Reference : 파이썬과 케라스로 배우는 강화학습

이승수의 저작물인 이 저작물은(는) 크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제 라이선스에 따라 이용할 수 있습니다.