CS234 4강 Summary
CS234 강의 중 Lecture 4(Model-Free Control)을 듣고 정리해보자
본 포스팅은 Stanford Univ의 CS234:Reinforcement Learning 강의를 듣고 정리한 글입니다.
우리는 지금까지 RL의 4가지 핵심적인 요소 중 Delayed consequences 즉, Planning을 배웠고, 이제부터는 Optimization과 Exploration에 대해서 배워볼 것이다.
On-policy vs Off-Policy
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도 수행할 수 있게 된다.
Model-Free Policy Iteration
Model-Free Policy Iteration에 대해 다루기 전에 2강에서 다루었던 Policy Iteration이 뭔지 다시 Recall 해보자.
Policy Iteration은 $V^{\pi}(s)$를 계산해 준 다음, 그 값과 Reward model R, dynamics P를 바탕으로 policy를 개선해 나가는 과정이었다.
그런데, Policy Iteration의 경우엔, dynamics/transition 이 일어날 확률이 필요했다.
그래서 저번 강의(3강)에서는 Model-free policy evaluation에 대해 설명했었는데, 그 내용을 Policy Iteration에 활용한 것이 Model Free Policy Iteration이다.
이러한 Model Free Policy Iteration는 Reward model이나 Dynamics를 알지 못하는 상황에서도 동일한 일을 수행하기 위해 Reward model과 Dynamics를 Q function으로 합쳐버려서 $Q^{\pi}$ 를 계산하고 이 정책($\pi$)를 개선해 나가면 되지 않을까? 라는 생각으로부터 나오게 되었다.
Model-Free Policy Iteration with MC Methods
우선 저번 시간에 배웠던 MC 방식을 이용하여 Model-Free한 상황에서도 최적의 Policy를 찾는 방법에 대해 알아보자.
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)를 사용한다. 즉, 원래는 State만을 사용하던 것에서 벗어나서, State, action 쌍을 사용하는 것이다. (당연히 Q는 s와 a에 관한 함수니까..)
방법은 모든 s,a에 대해 $Q^{\pi_{i}}(s,a)$가 주어져 있을 때
\[\pi_{i+1}(s) = \underset{a}{\operatorname{argmax}} Q^{\pi_{i}}(s,a)\]위의 식처럼 $Q^{\pi_{i}}(s,a)$ 의 argmax를 취하면 그게 다음 policy가 되는 것이다. 이 방식을 사용하면 Policy Iteration을 매우 간단하게, 그리고 Model-free하게 만들 수 있다.
하지만, 아직 신경써야 할 부분이 있다. 바로 $Q^{\pi}$를 계산하는 방법이다.
만약 policy가 Deterministic 할 때, policy 안에 특정 action이 존재하지 않는다면, 그 action에 대한 Q function은 절대로 계산하지 못한다. (Deterministic 하다면 policy에 있는 action만 따라가기 때문이다.)
이를 해결하고 model-free한 $Q^{\pi}$ 를 계산하기 위하여, Exploration을 해야 한다.
$\epsilon$-greedy Policy
이 때 사용할 수 있는 방식이 $\epsilon$-greedy Policy이다.
이는 매우 간단한 아이디어인데, $1-\epsilon$ 의 확률로는 $\underset{a}{\operatorname{argmax}} Q^{\pi}(s,a)$ 를 따르고, $\epsilon$ 의 확률로는 $\epsilon$을 A로 나눈 랜덤한 action a 를 따른다. (확률적으로 아무 길로나 간다는 것이다.)
이러한 $\epsilon$-greedy Policy Improvement방식을 사용하면, policy는 제자리에 머무르거나 무조건 더 좋은 방향으로 갈 수 밖에 없다는 것을 위 그림을 통해 증명할 수 있다.
GLIE
GLIE(Greedy in the Limit of Infinite Exploration) 는 Exploration을 효율적으로 만드는 것을 목적으로 한 일종의 전략인데, 간단히 말해서 모든 (s,a)를 무한히 지나고 나면 policy를 greedy하게 만드는 것이다.
간단한 예로, $\epsilon$의 값이 조금씩 줄어드는 $\epsilon$-greedy를 생각할 수 있다. 가령, $\epsilon$ = 1/i로 두는 것이다.(i는 iteration을 의미)
이러면 i가 무한대로 발산하면 $\epsilon = 0$ 으로 수렴하게 되고, 결국 $ 1- \epsilon = 1$ 로 수렴하게 되어 언제나 greedy한 선택을 하게 된다.
이런 방식을 GLIE라고 한다. (즉, 무한히 exploration을 지나면 greedy해지는 알고리즘을 의미한다.)
Monte Carlo Control 알고리즘
위 그림은 $\epsilon$-greedy policy를 적용한 Monte Carlo Control 알고리즘의 의사 코드이다.
1번째 줄에서 Q(s,a)와 N(s,a)를 초기화 하고,
2번째 줄에서 policy를 $\epsilon$-greedy(Q)로 초기화했다.
5번째 줄의 for문에서 3장에서 배운 Incremental Monte Carlo 수식을 통해 Q를 업데이트 해주었으며,
11번째 줄에서 GLIE하게 만들어 주기 위해서 $\epsilon $ = 1/k로 만들어주었다.
12번째 줄에서 업데이트 된 Q값을 이용해 Policy를 Improvement시킨다.
참고로 6번째 줄에서 First visit 대신 Every-visit을 사용해도 된다.
Example 1
지금까지 배운 내용을 확인해보자.
a1의 경우엔 [1 0 0 0 0 0 10]의 reward를, a2의 경우엔 [0 0 0 0 0 0 5]의 reward를 가지며, 위 그림과 같은 $\epsilon$, $\gamma$, Trajectory를 가진다고 하자.
이 때, First visit MC on policy Q의 값은 무엇일까?
우선 a1을 취한 경우를 생각하면, $(s_{3},a_{1},0,s_{2})$,($s_{1},a_{1},1$,terminal$)$ 의 2가지 경우 밖에 존재하지 않는다.
그리고, $\gamma = 1 $이므로 모든 states에 Final reward 1(state $s_{1}$에 위치했을 때 reward)을 넣어
Q(-, $a_{1}$) = [1 0 1 0 0 0 0] 이 된다. (이 때 s2의 경우엔 a1의 action을 취하지 않았기 때문에 0이 들어가게 된다.)
다음으로, a2를 취한 경우도 생각하면, $(s_{2},a_{2},0,s_{1})$ 밖에 존재하지 않는다. (First-visit이므로 두 번 지나간건 생각하지 않는다.)
그렇다면 위와 비슷하게 Final reward 1를 넣어 Q(-, $a_{2}$) = [0 1 0 0 0 0 0] 이 된다.
Example 2
Example 1에서 구한대로 Q(-, $a_{1}$) = [1 0 1 0 0 0 0], Q(-, $a_{2}$) = [0 1 0 0 0 0 0]일 때 optimal policy $\pi$(s)는 무엇이고,
k=3, $\epsilon$ =1/k 일 때, $\epsilon$-greedy policy는 무엇일까?
먼저,optimal policy는 $\underset{a}{\operatorname{argmax}} Q(s,a)$ 이다. 따라서 우리는 최대 보상값을 주는 action a를 찾아주어야 한다.
따라서 state $s_{1}$에서는 action $a_{1}$을, state $s_{2}$에서는 action $a_{2}$을, state $s_{3}$에서는 action $a_{1}$을 취해야 하고, state $s_{4}$이후부터는 Q(-, $a_{1}$), Q(-, $a_{2}$) 모두 0이므로 tie가 된다. (여기서 tie란 두 가지 이상의 행동(action)이 동일한 가치를 가질 때를 의미한다.)
즉, optimal policy 는 [$a_{1}$, $a_{2}$, $a_{1}$, tie, tie, tie, tie] 가 된다.
만약 tie가 나온다면 무조건 $a_{1}$을 고르거나 $a_{2}$를 고르는 등의 방식도 있고 랜덤으로 하나를 고르는 방식도 있는데, 일반적으로는 랜덤으로 하나를 고르는 방식이 더 효율이 좋다.
다음으로 $\epsilon$-greedy policy의 경우
$1 - \epsilon$ 즉, 2/3의 확률로는 최대 보상값을 주는 optimal policy인 [$a_{1}$, $a_{2}$, $a_{1}$, tie, tie, tie, tie] 을 따르고,
$\epsilon$ 즉, 1/3의 확률로는 그냥 아무 action을 취해 랜덤한 곳으로 갈 것이다.
Model-Free Policy Iteration with TD Methods
이번에는 MC 방식이 아닌 TD 방식에 대해 생각해보자.
어떻게 하면 model-free하게 TD방식을 만들 수 있을까? 방법은 다음과 같다.
3강에서 배웠던 TD Learning 방식과 이번 포스팅에서 배운 $\epsilon$-greedy 방식을 같이 사용하여 $Q^{\pi}$를 계산(Policy Evaluation)한 후에, $\pi$ = $\epsilon$-greedy($Q^{\pi}$)로 두어 policy를 개선한다. (Policy Improvement)
이렇듯 TD methods에 $\epsilon$-greedy policy를 적용한 것을 SARSA(states action reward states action)라고 한다.
SARSA는 TD Control 중에서도 on-policy에 속한다. 위에서도 언급했지만, on-policy learning은 직접 경험한 내용을 기반으로 policy를 예측하고 업데이트해 나가는 과정으로, 현재 action을 샘플링한 policy와 improvement하는 policy가 같다.
간단히 SARSA가 뭔지 설명하자면 현재 state에서 action을 취한 뒤에, 다음 state에서 action을 취하고 나서 Policy Improvement가 이루어지는 것이다.
다시 말해, 현재 $(s_{t},a_{t})$ 쌍에서의 상태를 관찰한 뒤에, 다음 state $s_{t+1}$에서 action $a_{t+1}$을 취하고 나서, 그 뒤에 관찰한 값을 바탕으로 현재 policy인 $\pi$ 를 update 하는 것이다.
참고로 7번째 줄에 적혀있는 $\alpha$는 learning rate이다.
이 방법의 장점은(TD의 장점이기도 하다) 모든 episode를 다 돌지 않아도 금방금방 policy improvement를 진행할 수 있다는 것이다. 그렇기 때문에, 만약 episode 하나하나가 매우 길다면, 이 방식이 매우 효율적이게 될 것이다. 한 time step에서의 (s,a) 쌍이 주어진다면 바로바로 policy improvement가 가능하기 때문이다.
위 그림에서 2 가지 조건을 만족하는 learning rate $\alpha$를 선택하면 SARSA는 무조건 수렴한다는 것인데, 실제 상황에서는 저런 값은 잘 선택하지 않고, 그냥 하나하나 경험적으로 집어넣어 본다고 하니 이런것이 있다고 알아두기만 하고 그냥 넘어가도록 하자.
Q-Learning
Q-Learning은 위에서 배웠던 SARSA에서 아주 약간만 바꾼 방식이며, SARSA와 달리 TD Control 기법 중에서도 off-policy에 해당한다. 즉, 샘플링한 policy와 학습으로 improvement하는 policy가 다르다.
즉, Q-Learning은 원래 SARSA에서 다음 state와 action인 $(s_{t+1},a_{t+1})$ 이였던 것을 $\underset{a^{\prime}}{\operatorname{max}} Q(s_{t+1},a^{\prime})$으로 바꾸어 준 것이다.
그러니까, 다음 action을 고를 때 그냥 아무거나 고르는 것이 아니라, Q의 값이 최대가 되는 action을 고른다는 얘기이다.
여기서 Q는 2강에서도 언급했지만 state-action value function으로 어떤 상태에서 어떤 행동이 얼마나 좋은지 알려주는 함수이다.
Q-learning with $\epsilon$-greedy Exploration
그리고 Q-learning에도 $\epsilon$-greedy Exploration을 적용할 수 있다.
SARSA랑 매우 비슷한데 위에 언급했던 것처럼 SARSA에서 $(s_{t+1},a_{t+1})$ 이였던 것이 $\underset{a^{\prime}}{\operatorname{max}} Q(s_{t+1},a^{\prime})$가 된 것 뿐이다.
또한, Monto Carlo 경우와 마찬가지로 $\epsilon$-greedy policy를 Q-learning에 적용할 때도, GLIE함을 만족하여야 optimal $Q^* $ 와 optimal $\pi^* $를 수렴하여 최적이 되는 Q와 $\pi$(Policy)를 구할 수 있다.
그런데, 원래는 unbias한 Q function을 사용하더라도, max연산을 하면 π의 예측값의 value V는 bias해질 수도 있다. 왜 그러는지는 위 그림에서 교수님..께서 적어주신 수식 부분을 참고하면 될 것 같다.
참고로 1번째 줄에서 2번째줄로 넘어가는 수식에서 부등식이 생기는 이유는 옌센 부등식을 참고하면 될 것 같다.
Double Learning
이를 보완하기 위해서 고안된 방법이 바로 Double Learning이다.
이는 예측치의 최댓값이 실제 값의 최댓값의 예측치로 사용되는 것을 피하기 위해서 고안되었다. (예측치의 최댓값 <= 실제 값의 최대값의 예측치 이므로)
그래서 Q를 하나를 쓰는게 아니라 두 개 $ Q_{1} , Q_{2}$ 로 나누어 사용한다.
그 중 $ Q_{1}$은 의사 결정(Decision Making)을 위한 max action $a^* $ 를 선택하는데 사용하고, $ Q_{2}$는 값의 추정 즉, $a^ *$의 값을 예측하는데 사용한다.
이렇게 하면, estimator가 bias해지는 것을 방지할 수 있다.
위 그림은 Double Q-Learning의 작동 과정을 간단히 나타낸 것이다.
물론 Double Q-Learning은 Q-Learning보다 메모리 및 연산이 더 많이 필요하지만 특정 상황에서 Double Q-learning은 Q-learning보다 훨씬 더 빠르게 optimal한 값에 수렴할 수 있게 된다.
교수님께서 시간 관계상 Double Q-Learning 부분을 약간 대충 설명하셨다. Double Q-Learning 관련 내용은 나중에 따로 공부해보는 것이 좋을 듯 싶다.
댓글남기기