강화학습 강의 (CS234) 4강 - MC / SARSA / Q-learning

Lecture 4 : Model Free Control

- 본 포스팅은 CS234 4강의 내용을 정리합니다.

 

오늘의 목차

이번 강의에선,

- Generalized Policy Iteration

- Importance of Exploration

- Monte Carlo Control

- Temporal Difference (TD) Methods for Control

- Maximization Bias

등에 대해 배운다.

 

On-policy, Off-policy learning

On-policy learning이란 직접 경험한 내용을 바탕으로 policy를 예측하고, 개선해 나가는 과정이다.

즉, Agent가 직접 행한 내용에 대해서만 학습을 하는 것이다.

 

Off-policy learning은 그와 달리 이미 알고 있는 내용들을 바탕으로 아직 실행하지 않은 내용까지 예측해서 policy를 개선해 나가는 것이다.

가령, 다음과 같은 state와 action에 대한 policy를 생각해보자:

s1, a1, s1, a1

s1, a2, s1, a2

off-policy learning의 경우엔 위의 두 가지 policy를 조합하여

s1, a1, s1, a2

의 policy도 수행할 수 있게 된다.

 

Policy Iteration

이제 Policy Iteration이 뭔지 다시 한번 불러와 보자.

Policy Iteration이 뭐였느냐 한다면...

우선 Vπ를 계산해 준 다음,

그 값과 Reward model R, dynamics P를 바탕으로 policy를 개선해 나가는 과정이었다.

(자세한 내용은 2강에서 확인하도록 하자.)

 

그런데, Policy Iteration의 경우엔, 정확한 Reward model과 dynamics(~~가 일어날 확률)가 필요했다. 

그래서 저번 강의에서는 model-free policy evaluation에 대해 설명했었는데,

이걸 한번 Policy Iteration에 써먹어 보도록 하자.

 

Model-Free Policy Iteration

그래서 나온 것이 Model Free Policy Iteration이다.

아이디어는 그냥 Reward model과 dynamics를 Q function으로 합쳐버려서

Qπ를 계산하고 이 π를 개선해 나가면 되지 않을까? 하는 생각인 것이다.

 

MC for On Policy Q Evaluation

이번엔 Monte Carlo for On Policy Q Evaluation에 대해 알아보자.

이는 저번에 배웠던 Monte Carlo for on policy value evaluation과 매우 유사한데,

원래 value evaluation에서는 N(s), G(s)를 썼지만,

Q Evaluation에서는 N(s, a) 와 G(s, a)를 사용한다.

(사실 어느 정도 당연한 이야기인데... Q는 state뿐만 아니라 action 또한 사용하는 function이기 때문이다.)

즉, 원래는 State만을 사용하던 것에서 벗어나서, State, action 쌍을 사용하는 것이다.

 

 

Model-free Generalized Policy Improvement

이 방식으로, Policy Improvement를 더욱 간단히 만들 수 있다.

그냥 Qπ(s, a)의 argmax를 취하면 그게 다음 policy가 되는 것이다.

 

Model-free Policy Iteration

그리고 이 방식을 사용하면 Policy Iteration을 매우 간단하게, 그리고 Model-free하게 만들 수 있다.

하지만, 아직 신경써야 할 부분이 있다. 바로 Qπ를 compute하는 부분이다.

만약 policy가 Deterministic 할 때는 policy 안에 특정 action이 존재하지 않는다면, 그 action에 대한 Q function은 절대로 계산하지 못한다.

(결국엔 Deterministic 하다면 policy에 있는 action만 따라가니깐..)

 

Policy Evaluation with Exploration

이를 해결하고 model-free한 Qπ를 계산하기 위하여, Exploration을 해야 한다!

 

e-greedy Policy

이 때 사용할 수 있는 방식이 ε-greedy policy라는 것이다.

매우 간단한 아이디어인데,

1 - ε 의 확률로는 그냥 argmax Qπ(s, a)를 따르고,

ε의 확률로는 그냥 action a (랜덤한 action)를 따르는 것이다.

즉, 그냥 대충 확률적으로 딴 길로 샌다는 것이다.

 

Check Your Understanding - MC for On Policy Q Evaluation

그럼 지금까지 배운 내용을 확인해보자. (맨 아래 답이 이미 나와있는 것은 못본 걸로 하자.)

지금 까지의 예제와 비슷하게 Mars Rover의 예제를 사용한다.

그런데, a1의 경우엔 [1 0 0 0 0 0 10]의 reward를, a2의 경우엔 [0 0 0 0 0 0 5]의 reward를 갖는다.

또한, ε = 0.5이고, Trajectory = (s3, a1, 0, s2, a2, 0, s3, a1, 0, s2, a2, 0, s1, a1, 1, terminal) 이다.

이 때, First visit MC on policy Q의 값은 무엇일까?

 

 

간단하게 생각하자.

우선 a1을 취한 경우를 생각하면,

(s3, a1, 0, s2), (s1, a1, 1, terminal)의 두 가지 경우밖에 존재하지 않는다.

그리고, 𝛾=1이므로 지나온 모든 states에 final reward 1을 넣어 Q(-, a1) = [1 0 1 0 0 0 0]이 나오게 된다.

이 때 s2의 경우엔 a1의 action을 취하지 않았기 때문에 0이 들어가게 된다.

 

그럼 a2를 취한 경우도 생각하면,

(s2, a2, 0, s1)밖에 존재하지 않는다. (First-visit이므로 두 번 지나간건 생각하지 않는다. 사실 그거나 그거나 𝛾=1이라..)

그렇다면 위와 비슷하게, Q(-, a2) = [0 1 0 0 0 0 0]이 나오게 된다.

간단하지 않은가?

 

 

Monotonic ε-greedy Policy Improvement

위는 ε-greedy Policy Improvement방식을 사용하면, policy는 제자리에 머무르거나 무조건 더 좋은 방향으로 갈 수 밖에 없다는 것을 증명한다.

그냥 공식으로 되어 있으니 딱히 쓸 말이 더 없을 것 같다...

 

GLIE

여기서 GLIE (Greedy in the Limit of Infinite Exploration)에 대하여 나온다.

GLIE는 Exploration을 효율적으로 만드는 것을 목적으로 한 일종의 전략인데,

간단히 말하면 모든 (s, a)를 무한히 지나고 나면 policy를 greedy하게 만드는 것이다.

 

이에 대한 간단한 예로, ε의 값이 조금씩 줄어드는 ε-greedy를 생각할 수 있다.

가령, ε = 1/i로 두는 것이다.

 

이러면 i가 무한대로 발산하면 ε=0으로 수렴하게 되고, 결국 1-ε가 1로 수렴하게 되어 언제나 greedy한 선택을 하게 된다.

이런 방식을 바로 GLIE하다고 하는 것이다.

(좀 더 간단히 말하자면, 그냥 무한히 exploration을 지나면 greedy해지는 알고리즘을 의미한다.)

 

Monte Carlo Online Control / On Policy Improvement

그리고 다음은 ε-greedy policy를 적용한 Monte Carlo Control 알고리즘의 의사 코드이다.

그냥 쭉쭉 읽어나가면서 이해하면 될 것 같고...

조금 신경쓸 부분만 짚어보자면,

 

2번째 줄. policy 를 ε-greedy(Q)로 initialize하고 있다.

 

6번째 줄. 위에선 First visit이라고만 적혀 있지만, Every-visit을 해도 된다.

 

7번째 줄. 원래 Monte Carlo면 N(s, a)가 아니라 N(s)였겠지만, On Policy Q Improvement 이므로 N(s, a)가 된다.

 

11번째 줄. GLIE하게 만들어 주기 위해서 ε = 1/k로 만들어준다.

 

Check Your Understanding : MC for On Policy Control

이제 예제로 한번 알아보도록 하자.

언제나와 같이 Mars Rover의 예시인데,

Q(-, a1) = [1 0 1 0 0 0 0], Q(-, a2) = [0 1 0 0 0 0 0] 일때

optimal policy π(s)는 무엇이고,

k = 3, ε = 1/k 일 때 ε-greedy policy는 무엇일까?

 

 

optimal policy는 argmax Q(s, a)이므로, [a1, a2, a1, tie, tie, tie, tie] 가 된다.

참고 : state s4 이후에는 모두 Q(-, a1), Q(-, a2)의 값이 0으로 같으므로 tie가 된다.
만약 tie가 나온다면 무조건 a1을 고르거나 a2를 고르는 등의 방식도 있고 랜덤으로 하나를 고르는 방식도 있는데, 일반적으로는 랜덤으로 하나를 고르는 방식이 더 효율이 좋다.

 

또한, k=3, ε=1/k라면 ε-greedy policy의 경우

2/3의 확률로는 [a1, a2, a1, tie, tie, tie, tie] 를 따르고,

1/3의 확률로는 그냥 아무데나 갈 것이다.

Model-free Policy Iteration with TD Methods

이번에는 MC 방식이 아닌 TD 방식을 생각해보자.

어떻게 하면 model-free하게 TD방식을 만들 수 있을까?

 

아이디어는 또 단순하다.

TD방식과 ε-greedy 방식을 같이 사용하여 Qπ를 계산한 후에, (Policy evaluation)

π = ε-greedy (Qπ)로 두어 policy를 개선한다. (Policy Improvement)

 

SARSA

이렇듯 TD methods에 ε-greedy policy를 적용한 것을 SARSA (states action reward states action 라는 뜻ㅎ;;)라고 한다.

간단히 SARSA가 뭔지 설명하자면 현재 state에서 action을 취한 뒤에, 다음 state에서 action을 취하고 나서 policy improvement가 이루어지는 것이다.

다르게 말하자면, 현재 (st, at) 쌍에서의 상태를 관찰한 뒤에, 다음 state st+1 에서의 action at+1을 취하고 나서,

그 뒤에 관찰한 값을 바탕으로 현재 policy π를 update 하는 것이다.

 

 

그 외의 나머지 부분은 MC 방식과 비슷하게 위의 알고리즘을 그냥 읽으면 될 것 같다.

참고로, 7번째 줄에 적혀있는 α는 learning rate이다.

 

이 방법의 장점으로는, 모든 episode를 다 돌지 않아도 금방금방 policy improvement를 진행할 수 있다는 것이다.

그렇기 때문에, 만약 episode 하나하나가 매우 길다면, 이 방식이 매우 효율적이게 될 것이다.

그때 그때 (s, a)쌍만 주어진다면 바로바로 policy improvement가 가능하기 때문이다.

 

Convergence Properties of SARSA

이 부분은 조금 이론적인 부분인데,

위의 두 가지를 만족하는 α를 선택하면 SARSA는 무조건 수렴한다는 것인데,

실제 상황에서는 저런 값은 잘 선택하지 않고, 그냥 하나하나 경험적으로 집어넣어 본다고 한다.

(그러니까 그냥 이론적으로 알고만 넘어가라는 뜻 ㅎ)

 

Q-learning

Q-learning은 지금까지 배웠던 SARSA에서 아주 약간만 바꾼 방식이다.

원래 SARSA에서는 다음 state와 action 의 (st+1, at+1)의 쌍을 취해서 

원래 Q(s+1, at+1)였던 것을 max Q(st+1, a')으로 바꾸어 준 것이다.

그러니까, 다음 action을 고를 때 그냥 아무거나 고르는 것이 아니라, Q의 값이 최대가 되는 action을 고른다는 얘기이다.

Q-learning with ε-greedy Exploration

그리고 Q-learning에도 ε-greedy Exploration을 적용할 수 있다.

사실 SARSA랑 너무 똑같아서 딱히 할 말이 없다.

그냥 중간에 Q(st+1, at+1) 이었던 것이 max Q(st+1, a)가 된 것 뿐이다.

 

Q-learning with ε-greedy policy 

그리고 ε-greedy policy를 Q-learning에 적용할 때도, 위의 MC의 경우와 마찬가지로

GLIE함을 만족하여야 optimal Q*와 optimal π*를 구할 수 있다.

 

 

Maximization Bias

그런데, 원래는 unbias한 Q function을 사용하더라도, max연산을 하면 π의 예측값의 value V는 bias해질 수도 있다.

왜 그러는지는 위에 annotation으로 적혀있는 수식을 확인하면 될 것 같다.

(참고 : 1번째 줄에서 2번째줄로 넘어가는 수식에서 부등식이 생기는 이유 : 옌센 부등식 https://ko.wikipedia.org/wiki/%EC%98%8C%EC%84%BC_%EB%B6%80%EB%93%B1%EC%8B%9D)

 

Double Learning

이를 보완하기 위해서 고안된 방법이 바로 Double Learning이다.

예측치의 최댓값가 실제 값의 최댓값의 예측치로 사용되는 것을 피하기 위해서 고안되었다.

(예측치의 최댓값 <= 실제 값의 최대값의 예측치 이므로)

그래서 Q를 하나를 쓰는게 아니라 두 개 (Q1, Q2)로 나누어 사용한다.

그 중 Q1은 max action a*를 선택하는데 사용하고,

Q2는 a*의 값을 예측하는데 사용한다.

 

이렇게 하면, estimator가 bias해지는 것을 방지할 수 있다.

 

Double Q-Learning

위는 Double Q-Learning의 작동 과정을 간단히 나타낸 것이다.

물론 Double Q-Learning은 Q-Learning보다 메모리 및 연산이 더 많이 필요하게 될 것이다.

 

Double Q-Learning Figure

하지만 특정 상황에서 Double Q-learning은 Q-learning보다 훨씬 더 빠르게 optimal한 값에 수렴할 수 있게 된다.

 

 

후반부는 강의 내에서도 교수님이 그냥 후딱후딱 넘어가는 바람에 나도 설명 후딱후딱 해버렸다.

어째 지금까지 모든 강의가 다 시간이 부족해서 후반부는 빠르게 넘어가는 느낌이다.

아무튼, 다음 CS234 5강에서 보도록 하자.