[CS234] Lecture 4: Model Free Control 정리

 

지난 lecture 3에서는 행동지침을 어떻게 평가하는지를 배웠고,

이번 시간에는 행동지침 평가 방식을 통해 좋은 행동지침을 구별할 수 있다면

그걸 어떻게 배울 것인지에 관한 내용을 배울 것이다. 

중요한 개념이 하나 나오는데, On Policy 와 Off Policy라는 것이다.

Monte Carlo On Policy, Monte Carlo Off Policy 같은 용어로 쓰인다.

지금 배우고 있는 것이 모델이 주어지지 않은 상태에서

과거의 경험만으로 행동지침을 세우는 방식이기 때문에

On Policy라 함은, 과거의 경험 그대로 행동지침을 세우는 것을 뜻하고

Off Policy는 과거의 경험과는 다른 방식을 선택하는 것을 뜻한다.

 

$$ (s_1, a_1, s_2, a_2) \\ (s_1, a_2, s_1, a_1) $$ 

같은 경험을 했는데, 요것 그대로 행동지침을 세우면 On Policy이고, 

$$(s_1, a_1, s_2, a_1)  $$

같은 식으로 응용을 하면 Off Policy가 된다.

 

먼저 모델이 주어졌을 때 Policy Iteration을 하는 방법을 복습해보자면

해당하는 공식에 주어진 모델을 때려넣고 반복 계산을 돌리는 식이었다.

모델이 없을 때는 State Value:=V 대신에 State Actoin Value:= Q를 사용하게 된다. 

Q를 사용하는 첫 번째 방법은 역시 몬테카를로이다.

조금 만만하게 접근할 수 있는 방법인가보다. 

알고리즘 역시 지난 시간에 배웠던 Value function evaluation과 크게 다르지 않다.

몇몇 표기 방식이 N(s) 에서 N(s, a)로 바뀌었을 뿐이다.

이렇게만 알고리즘이 짜여진다면 이번 강좌는 참 쉽겠군.

하지만 역시 그렇게 쉽게 끝나지 않는다.

몬테카를로 방식은 과거에 진행했던 경험 그대로 행동지침을 설정해야 한다는 것이다.

예제에서도 보았듯이, 한 번 방문했던 상태 A에서의 보상값이 0이면

V(A)가 0으로 설정되어버려서 다시 방문할 유인이 전혀 없기 때문이다.

실제로는 0, 1, 0, 1 하는 식으로 보상이 주어질 지도 모르는 일이다.

 

그래서 $\epsilon$-greedy 방식을 사용하게 된다. (e greedy 혹은 epsilon greedy 라고 읽는다)

전체 선택지가 A개이고, epsilon이 0.2라고 하면,

80%의 확률로 기존 경험에서 가장 뛰어났던 행동을 취하고

20% 확률로 랜덤한 행동을 취하는 것이다.

다만 본 강의에서는 80% + 0.2/A의 확률로 가장 뛰어난 행동을 취하고

남은 확률로 랜덤한 행동을 취한다고 하는데, 이는 나중에 증명을 위해 필요한 것 같다.

0.2/A의 값이 무척 작으므로 간편하게 전자와 같이 생각하는게 좋을 듯 하다.

 

그럼 자신감을 가지고 예제를 풀어보도록 하자.

앞서 나왔던 Mars Rover와 설정은 똑같다.

다만 action 2가 가능해져서, 이에 해당하는 보상 값이 [0 0 0 0 0 0 5] 로 주어졌다.

N은 에피소드가 1이므로 역시 1이니, G값만 잘 구하면 Q를 구할 수 있다.

$G(s_3, a_1) = 1$이고,  $s_3$에서는 $a_2$를 사용한 적이 없으므로 $G(s_3, a_2) = 0$이 된다.

$G(s_2, a_1)$은 마찬가지로 0이고, $G(s_2, a_2) = 1$ 이 된다.

마지막으로 $G(s_1, a_1) = 1, G(s_1, a_2) = 0$이다. 

나머지 상태는 방문한 적이 없으므로 자동 0이 된다.

 

너무 간단하지 않은가? 한 상태에서 한 가지 행동만 취했기 때문이다.

이래놓고 시험 문제 같은 곳에서는 꼭 두 가지 행동을 모두 취하는 것이 나오기 때문에 주의해야 한다.

강의에서는 이 뒤에 $\epsilon-greedy$ 방식이 

행동지침을 평가하는데 사용할 수 있는 근거에 대해 설명한뒤, ㅎ

한참동안 학생들의 질문이 나온다.

이 부분은 잘 이해하기 어렵고, 굳이 이해할 필요도 없을 것 같아 패스했다.

$\epsilon-greedy$방식이 잘 작동하는 근거가 있구나, 하고 넘어간 후에

남으로부터 "그거 왜 작동하는 거야?"하는 질문을 받으면 인터넷을 찾아서 보여주면 그만이다.

일단 $\epsilon-greedy$를 잘 써먹기만 하면 된다.

 

다시 Mars Rover 사례로 돌아가보자.

최적의 행동지침은 $a_1, a_2$ 중 가장 좋은 성과를 내는 방법을 골라서,

$[a_1, a_2, a_1, -, -, -, -]$ 일 것이다. (- 는 뭘 하든 상관 없음)

 

이제 모델 없이 행동지침을 학습하는 두 번째 방법, TD Learning이다.

Value Iteration에서의 TD-Learning은 에피소드를 (S, A, R, S') tuple로 나누어서 사용했다.

Policy Iteration에서는 행동까지도 고려해야하므로, (S ,A, R, S', A')을 사용하게 되고

이것을 SARSA라고 부른다.

SARSA에서는 다음 상태에서 취할 행동까지도 반영해서

현재 Q를 정해줘야 하는 번거로움을 피하기 위해 

그냥 최적의 행동을 할 것이라고 가정해도 좋다.

그것이 바로 Q-Learning이다. 

아타리 벽돌깨기를 우수한 실력으로 해치웠던 알고리즘이기에 

지금까지 강의 중에서 가장 중요한 내용이 아닐까 싶다.

 

 Q Learning은 잘 작동하기는 하지만, 편향(bias)이 생긴다는 문제가 있다.

어떤 편향인지는 잘 이해하지 못했지만, 상관없다. 하여튼 무슨 문제가 있다.

그래서 도입된 게 Doulbe Q Learning인데, 

기존처럼 하나의 Q 함수를 쓰는 대신에, 두 개의 Q 함수를 사용해서

하나는 가장 적합한 행동이 무엇인지 추산하는 것에 쓰고, 

다른 하나는 그 행동을 평가하는 데 쓰는 것이다. 

 

구체적으로 어떻게 사용되는 알고리즘인지는 강의에서도 휙 자나가버려서 잘 모르겠지만

효과는 엄청난 것으로 보인다.

나중에 실제로 사용할 때가 오면, Q-Learning의 방법만 알고 있더라도

그 때 가서 찾아보면 잘 이해할 수 있을 것 같다.