Lecture 3: Dummy Q-learning (table)

이 내용은 Sung Kim 교수님의 모두를 위한 RL 강좌를 정리한 내용입니다.

https://youtu.be/Vd-gmo-qO5E

――――――――――――――――――――――――――――――――――――――――――――――――――――――

Q-Learning이란 Q function에 현재 State와 현재 취할 수 있는 Action들의 값을 넣었을 때 Q function의 값이 가장 큰 Action을 취하는 것을 말합니다. 다시말해 State마다 Q에게 물어봐서 길을 찾아갑니다. (안녕 Q야 S에서 상,하,좌,우 중 어디로 가야하니)

Q function이란 state-action value function 이라고도 합니다. state-action value function의 개념에 대해서는 Sung Kim 교수님의 강의에서는 깊게 다루어지지 않습니다. 제가 포스팅한 RL by David Silver의 강좌정리를 살펴보시거나 RL 서적을 찾아보시면 관련 내용이 존재합니다.

Q function은 입력으로 State, Action 을 받고 Quality(reward) 를 반환합니다.

Q(state, action) = Quality

Policy라는 개념이 있습니다. Policy는 쉽게 말해  어떤 State에서 Agent가 취할 수 있는 Action 입니다.

이는 Deterministic 하거나 Stochastic 할 수 있습니만 자세한 내용은 생략하겠습니다.

Policy는 다음과 같이 표기합니다.

예제를 보겠습니다.

다음 그림은 Q function을 어떻게 사용하는지를 보여줍니다.

Frozen Lake의 예제에서 선택할 수 있는 Action은 (LEFT, RIGHT, UP, DOWN) 이 전부였습니다.

현재 Agent가 S1 의 State에 있을 때 모든 Action들을 취했을 때 Q-function이 가장 큰 것을 골라야 합니다.

아래 예제에서는 Q(S1, RIGHT)가 가장 크니 RIGHT로 움직일 것입니다.

아래 그림의 argmax Q(S1,a) 는 Q(S1,a)를 가장 크게 만드는 Action을 반환합니다.

다음은 공식입니다.

Optimal 이라는 뜻은 최적 이라는 의미입니다. Optimal Policy는 최적의 Policy, 즉 최적의 Action, 다시말해 S에서 Q(S,A)가 가장 큰 Action을 의미합니다. Q-Learning의 핵심은 이 Optimal Policy를 찾는 일입니다.

그러나 Agent가 State를 이동하면서 Q에게 질문을 해서 올바른 답을 얻기 위해서는 Q가 이미 Goal에 도달하는 올바른 길을 알고있다는 전제가 필요합니다. 따라서 Q에게 Goal에 도달하는 올바른 길을 학습시켜주고 알려주어야 합니다.

다음은 Q를 학습시키는 방법입니다.

먼저 Q(s, a) 다음에 도달할 s' 에서의 Q(s', a')는 올바른 답을 알고있다고 믿습니다.(전제조건)

이때 Q(s, a) 는

Q(s, a) = r + max Q(s', a')

으로 나타내어질 수 있습니다. Q(s, a)에 대해 다시 정의를 하자면 

"State s 에서 Action a 를 취했을 때, 그로부터 Goal 까지 도달하는 모든 경우의 수들 중 reward의 총합이 가장 큰 경우의 총합이 Q(s, a)이다."

Environment에서의 상황을 표시하면 아래 그림과 같습니다.

시작점 부터 Goal까지 생기는  State, Action, Reward를 순서대로 나타낸 History는 다음과 같이 나타낼 수 있습니다.

아래 수식에서 R은 Q(s0, a0) 의 값을 나타냅니다. Rt는 t-1순간의 Q(St-1, At-1) 입니다.

rt+1 ~ rn 까지는 R(t+1)로 나타낼 수 있습니다. 또한 Optimal 한 Reward를 얻기 위해서는 매 선택에서 가장 큰  R을 선택하여야 합니다.

따라서 위 식은 다음과 같이 정리됩니다.

예제를 보겠습니다.

다음은 모든 Q value 들이 0으로 초기화된(reward가 아닙니다.) Env입니다. 이제 이 Env에서 움직일 것입니다.

Agent는 좌상단의 Start지점부터 이동을 시작합니다. 먼저 초기에 모든 Q는 0이므로  Agent는 랜덤하게 움직입니다. 그러나 항상 답해오는 r+Q(s', a')은 0입니다. 그렇게 무의미한 움직임을 하다가 Agent는 S14, 바로 Goal 직전에 다다르게 됩니다. 이때 Agent가 Right를 선택한다면, Q(S14, Right) 는 1이 됩니다. 왜냐하면 Goal의 reward는 1이니까요. 그리고 Q(S14, Right)를 1로 업데이트 한뒤 Goal에서 턴을 종료합니다.

자 이제 새로운 판입니다. Agent는 이전에 업데이트 되었던 판에서 새롭게 게임을 시작합니다. Agent는 이전판과 마찬가지로 랜덤하게 움직여봅니다. 그러다가 S13에 도착하게 되었습니다. 이 때 아래 그림의 수식에 따라 Q(S13, Right)이 가장 크기 때문에 Right를 선택하여 S14로 이동할 것이며, S14에서도 Right를 선택하여 Goal이 될 것입니다.

위 과정들을 계속하여 반복한다면 언젠가는 시작지점의 Q table 까지 업데이트가 될 것입니다.

자 이제 Agent는 Optimal Policy, 다시말해 Q(s, a)를 가장 크게 해주는 Action을  따라서 Goal 지점까지 갈 수 있게 되었습니다.

다음은 Q-Learning 알고리즘의 pseudocode 입니다. 여러가지 다양한 기법들을 적용한 Q-learning 알고리즘들은 다음 강의에서부터 계속 다루어집니다.

강좌에 나오는 코드는 다음 Github에 구현해 놓았습니다.

https://github.com/whitesoil/ReinforceLearningZeroToAll