[CS234] Lecture 3 - Model Free Policy Evaluation 정리

Lecture 2가 Model(상태가 변할 확률, 보상 함수 등)이 주어졌을 때 행동지침의 평가에 대한 내용이었다면

이번 Lecture 3 강좌는 그런 것들이 주어지지 않았을 때 어떻게 행동지침을 세울 수 있는지에 대한 내용이다.

직관적으로 생각해보면, 상태가 변할 확률까지는 없어도 되겠다만

보상에 대한 정보 없이 행동지침을 세울 수 있는지 의문이다.

파블로프의 개만 하더라도 "맛있는 음식"이라는 보상이 있었기에

종소리에 침을 흘리는 행동지침을 세우지 않았나?

무슨 내용인지 좀 더 살펴보자. 

 

모델이 있을 때 행동지침을 평가하는 방법은 Dynamic Programming이었다.

이런식으로 아예 모델을 곱해가면서 반복 계산을 수행하는 것이었는데

모델이 없을 경우에는 이렇게 곱해주진 못한다.

 

모델이 없을 때 사용할 수 있는 첫 번째 방법은 Monte Carlo 이다. 

몬테 카를로는 원자폭탄을 설계한 사람들 중 하나인 엔리코 페르미가 고안해낸 방법으로

"큰 수의 법칙"과도 밀접하게 관련이 있다.

예를 들어 공대의 성비를 알고 싶은데, 정리된 자료가 마땅치 않다면

공대 입구 버스정류장에서 버스를 내리는 사람들을 관찰하면서 그 성비를 조사해도

공대 전체의 성비와 유사하게 확인될 것이라는 뜻이다. ("공대는 남자밖에 없군!")

 

바로 예시로 들어가서 몬테카를로 방법을 이해해보자.

사실 강의와 맞지 않는 부분이 바로 이런 방식이다. 

개념을 잔뜩 설명해주고 예제를 풀어보라고 하는데, 

도대체 개념이 머릿속에 들어와야 예제를 풀어볼 텐데 그러질 못하는 것이다.

예제를 잔뜩 준비해서 처음 몇 문제는 차근차근 풀어주며 개념을 설명하고

다음 예제는 같이 풀어보도록 수업을 진행하면 나에게 훨씬 맞았을 것 같다.

 

어쨌든 여기서는 보상 체계는 [1 0 0 0 0 0 10]으로 주어졌고,

각 상태에서 움직일 확률이 얼마나 되는지는 나오지 않았다.

discount factor가 1이므로 미래에 벌어질 일도 현재의 이익과 동일하게 계산하면 된다.

그간 움직인 행적이 $(s_3, a_1, 0, s_2, a_1, 0, s_2, a_1, 0, s_1, a_1, 1, 끝)$ 이라면

First Visit Monte Carlo 방법으로 추산해본 각 상태의 value는 얼마가 될까?

Every Visit Monte Carlo 방법으로 추산해본 $V(s_2)$는 얼마가 될까?

First Visit Monte Carlo 방법은 위와 같다.

알고리즘에 Mars Rover 사례를 그대로 대입해보자.

 

방문한 상태는 $s_3, s_2, s_1$ 로 총 세 가지이다. 

일단 움직인 행적은 하나만 주어졌으므로 i = 1일테고,

First Visit Monte Carlo는 모든 에피소드에서 각 상태가 몇 번씩 지나는지 세긴 세는데

한 에피소드에서 각 상태를 여러 번 지나더라도 한 번으로만 인정을 하므로

$N(s_3), N(s_2), N(s_1)$은 모두 1이 된다. 

 

강의자료에서는 N에 대한 설명이 너무 모호하게 적혀있어서 헷갈린다(나만 모호한가?).

First Visit의 경우는 각 에피소드에서, 해당하는 상태를 방문했는지를 O,X 를 카운트하면 되고

Every Visit의 경우에는 각 에피소드에서, 해당하는 상태를 몇 번 방문했는지 모두 더하면 된다. 

 

$G(s_3), G(s_2), G(s_1)$은 모두 1이므로,

결국 $V(s_3), V(s_2), V(s_1)$도 모두 1/1 = 1이 되고

지나지 않은 $s_4 ~ s_7$은 모두 0이 된다.

 

Every Visit Monte Carlo에서는 $N(s_2)$가 2가 되지만

$G(s_2)$역시 1+1이 되므로 2/2 = 1이 될 것이다.

설명이 좀 개떡같고, 예제도 좀 별로여서

이런 알고리즘을 어디에 쓸 수나 있을까 싶었는데

알파고에 딱 몬테카를로 방법이 쓰였다고 한다.

굉장히 분산이 크고 에피소드 형태의 업무에만 적용가능하다는 단점이 있지만

그래도 실제로 구현할 때는 잘 작동하는 모양이다. 

 

모델이 없이 행동지침을 평가하는 몬테카를로 이외의 방법으로는 TD Learning이 있다.

TD Learning은 에피소드가 끝날 때까지 기다려야하는 몬테카를로와 달리

에피소드 중간에도 행동지침을 평가할 수 있으며

에피소드 형태가 아니라 끝나지 않는 업무에도 적용할 수 있다는 장점이 있다.

역시 예제를 통해 방법을 확인해보도록 하자. 

 

앞서 몬테카를로 방법과 동일한 예제이다. 

TD Learning에서는 하나의 에피소드를 최소 단위인 tuple로 나누어서 학습에 활용한다.

즉 다음과 같은 tuple의 집합이 탄생한다.

$$(s_3, a_1, 0, s_2) \\ (s_2, a_1, 0, s_2) \\ (s_2, a_1, 0, s_1) \\ (s_1, a_1, 1, 끝)$$

$V^\pi(s_1)$ 부터 구해보기 위해, 위에 나와있는 공식에 그대로 대입해보자

 

처음 tuple에서는  $V(s_3)$를 구할 수 있다. 

하지만 그래봤자, $V(s_3) = 0 + 1* 0$ 이므로 0이고

두 번째 tuple에서 구한 $V(s_2)$ 역시 0이다.

세 번째 tuple은 $V(s_2)$를 다시 구하는데 역시 0이다.

네 번째 tuple이 $V(s_1)$를 구하며, 드디어 $V(s_1) = 0 + 1*(1-0)$이 되어 1의 값을 가진다.

그러므로 TD-Learning으로 구한 평가는 [1 0 0 0 0 0 0]이 되겠다.

 

TD-Learning은 또 너무 간단해서 어떻게 실전에서 사용되는지 궁금하다.

과제를 얼른 풀어보면서 코드를 짜보고 싶군. 

Dynamic Programming, Monte Carlo, TD-Learning을 비교한 표인데

각 항목을 충분히 생각해보고 비교해보면 특성 파악에 도움이 될 듯 하다.

각 알고리즘의 장단점이 명확해서 가지고 있는 데이터셋의 특성에 따라

잘 작동하는 알고리즘 역시 달라질 수 있다.

두 번째 예제이다. 이번에는 여덟 개의 에피소드가 나왔다.

$$(A, 0, B, 0) \\ (B, 1) \\ (B, 1) \\ (B, 1) \\ (B, 1) \\ (B, 1) \\ (B, 1)\\ (B, 0) $$

먼저 몬테카를로 방법으로 Policy Evaluation을 해보자.

어차피 각 상태는 에피소드마다 한 번씩 방문되었으므로 First Visit과 Every Visit이 차이가 없을 테다.

A는 딱 한 번 나왔는데 0이었으므로 V(A) = 0일 것이고

B는 여덟번 모두 나왔으므로 N = 8, G = 6이다. 그래서 V(B) = 3/4이다.

 

TD-Learning에서는 어떨까? 

TD(0)라 함은 TD 공식에서 $\alpha$가 1인 경우를 뜻한다.

이번 TD-Learning은 Offline TD Learning이라고 하여 

tuple을 계속해서 반복하는 종류이다. 

이렇게 함으로써 데이터를 좀 더 효율적으로 쓸 수 있다.

Batch TD Learning에서는 tuple을 공식에 그대로 대입하는 것이 아니라

위와 같이 그래프를 통해 나타내어 풀이하는 게 좋다.

문제는 강의에서 제대로 설명해주지 않는다. 옳게 이해한 것인지도 불명확하다.

 

그래도 위 도식대로 풀어주면,

B는 75%의 확률로 1, 25%의 확률로 0이 되므로, V(B) = 0.75이고

A는 100%의 확률로 B로 넘어가므로, 공식에 대입하면 

V(A) = $\alpha$*(r + V(B) )이므로, 0 + 0.75가 되어 0.75의 값을 가진다.