A (Long) Peek into Reinforcement Learning -Part4

 

Part3 에서는 모델에 대해서 정보를 아는, DP에 대해서 다뤄보았고, 여태까지의 우리의 생각의 흐름은 이제 DP의 모든 정보를 알아야한다는 단점에서 벗어나 모델에 대해서 잘 몰라도 뭔가를 하고 싶다! 까지 도달하였다. 이는 모든 state의 업데이트가 아닌, 돌다리를 두드려보는, 여기저기 탐방해봐야하는 방법의 필요성으로 이어지고, 이제 agent가 직접 경험한 trajectory들을 토대로 업데이트하는 방법들에 대해서 알아볼 것이다. 

 

 

그 전에, 이제 sampling을 통해서 업데이트해 나아가는 방식으로 바뀌었으므로, 우리가 맞닥뜨리는 수식이 좀 달라진다. 앞으로의 수식은 다음과 같은 형태를 취할 것인데, 약간 gradient descent 생각하면 편할 것이다.

 

 

기존의 value를 추정한 것에다가, 새로운 experience가 더해진 것들을 타겟으로 놓고, 그 새롭게 얻은 정보들을 얼마나 반영할 것인지 alpha로 조절하면서, 차근차근 업데이트 해나아가는 것이다. 새로운 경험들이라고 해서 모두 optimal이 아니고, 좋을 수도 있고 안 좋을 수도 있기에 조금씩 반영해나간다고 생각한다.

 

---

 

MC와 TD, 그리고 Q-learning과 SARSA에 대해서 알아볼 것인데,

 

MC와 TD는 타겟을 구성하는 방법에 따라 다르다.

 

MC: 한 길을 일단 끝까지 가보고 그걸 타겟으로 삼자.

TD: 한 걸음 가보고 그걸 타겟으로 삼자.

 

수식을 보기 전 직관적인 이해가 될 것이다.

 

그리고 Q-learning과 SARSA는 TD 알고리즘에 속하면서 전자는 off-policy, 후자는 on-policy method가 되겠다.

 

---

 

 

Monte Carlo Method

 

MC에서는 target을, 한 길을 따라 끝까지 가보고 정한다. "한 길을 따라 끝까지" 라는 말은, episode가 끝날 때까지의 return을 모두 고려하겠다는 뜻이다. 어떤 policy에 따른 하나의 길이라고 생각하면 편한 episode는, 다음과 같다.

 

이렇게 되면, 한 어떤 시점 t에서 시작하여, 그 episode에 대한 return은 다음과 같이 표현할 수 있다.

 

그 episode가 terminal state로 갈 때까지 기다리는 것이다.

 

우리의 value function은 하나의 expectation이었다.

 

모델을 다 알고 있는 상태의 ground-truth 타겟인 G_t를, Empirical Mean으로 대체하겠다는 것이 MC의 core idea이다.

 

 

어떤 하나의 policy 하에서 N개의 trajectory를 sample하고, 그 N개에 대한 return을 다 더한 후 평균낸 값을 ground truth G_t라고 생각한다는 것이다. 

 

이렇게 되면 특정 policy가 그 state에서 대충 가치를 가지는지를, 에피소드 끝까지 가보는 여러 trajectory들의 평균값으로 추정할 수 있다. 

 

예시를 통해 한 번 보자.

 

한 policy 타우 아래에서 2개의 trajectory를 뽑아내보자. 감마값은 1로, 그냥 다 더하면 return이 나오는 걸로 하자.

 

그러면 각 trajectory당 state1, state2에서의 가치는 위와 같을 것이다. 그러면 아래와 같이 평균내주면 된다.

 

여기서 중요한 것은 우리가 타겟을 설정할 때 full return을 쓴다는 점이다. 그래서 full return까지 계산해야하므로 각 trajectory가 끝날 때까지 기다렸다가 업데이트를 해준다.

T까지 기다려주자.

 

이전에 강화학습 알고리즘에서의 단계는 보통 prediction과 control로 나뉘고, prediction은 state에서의 가치를 평가하는 것, 그리고 control은 새로운 policy로 improve하는 것이라고 서술한 적이 있다. 이렇게 empirical mean을 이용해 target을 만들어 prediction을 해줬으니, control까지 해주자.

 

 

MC에서는 에피소드가 끝날 때까지 기다려주었다. 하지만 TD는 1-step 업데이트라서, 기다려줄 필요없이 그냥 한 번만 갔다가 바로 업데이트 해버린다. 이제 MC와 TD의 차이를 알았으니, TD를 보자.

 

 

---

 

 

Temporal Difference Learning

 

 Monte Carlo method에서는, target을 complete episode까지, 즉 terminal state까지 기다려서 하나의 episode가 종료될 때까지 track해서 target을 만들었다. TD는 incomplete episode를 이용해서 target을 만드는데, 이를 TD target이라 한다. Temporal Difference learning은 강화학습에서 정말 중요한 개념이다. 얼마나 중요하냐면, 강화학습의 아버지 격인 Sutton & Barto (2017) 강화학습 책에서 “one idea … central and novel to reinforcement learning” 라고 언급했을 정도이다.

 

마찬가지로 먼저 prediction에 해당하는, TD target을 어떻게 구성할건지에 대해서 보고, 그 뒤로 TD control인 Q-learning과 SARSA에 대해서 알아보자.

 

 

TD(0) 

 

 

일단 TD(0)이 기본이므로 TD(0)에 대해서 먼저 얘기하면, 아까 MC는 full-episode까지 기다렸다면, 이번에는 바로 다음 state로 넘어갈 때마다 value function을 업데이트 해주는, 1-step update이다. 

 

아까 위에서의 MC target은 다음과 같았다. G_t 부분이 바뀌는데, 이 부분을 주목하면 된다.

 

TD는 다음 state로, 한 step만 가본 후 업데이트 한다.

 

이게 바로 TD(0)이다. 

 

---

 

Bias Variance Trade-Off of MC & TD (매우 중요)

 

 

매우 중요하다. TD의 다른 방법들로 들어가기 전에 반드시 짚고 넘어가야 하는 부분이다. 이제부터의 TD 방법론들은 모두 MC와 TD의 장점을 합치려고 만드는, 뭔가의 절충안이다. 왜 자꾸 MC와 TD를 절충하려고 하는걸까?

 

직관적으로 생각하면, MC는 끝까지 다 가보고, TD는 한 스텝만 가보니까, 둘 다 뭔가 극단적이고 어설프다. 그래서 내놓은 방법들이 중간까지만 가보자 이런 식의 방법들이 제시될 것이다.

 

좀 더 수학적으로 생각하면, MC와 TD 둘 다 단점이 있다. Bias와 Variance trade-off가 바로 그것이다. 먼저 bias와 variance가 뭔지 짚고 넘어가보자.

 

 

빨간색으로 된 부분이 ground-truth 부분이고, 나머지는 예측한 부분이다. 간단하게 말해서, Bias가 높다는 것은 실제 데이터와 예측한 데이터가 잘 맞지 않는다, 오차가 크다는 것이고, Variance가 높다는 것은 예측한 결과물들이 일관적이지 않다는 것이다. 

 

이제 MC와 TD를 다시보자. 잊지 말아야할 것이, 우리가 MC와 TD에서 타겟을 만드는 이유는, 모델을 모르는 상태에서 ground-truth value function을 추정하기 위해서이다. 위의 상황과 같다고 볼 수 있다. 

 

MC의 경우, 

 

한 에피소드가 끝날 때까지 기다리고, 그 에피소드 안에 들어있는 모든 reward를 다 더한 것을 타겟으로 삼는다. 그런데 어떤 확률적인 policy를 여러 state에 걸쳐 적용했기 때문에 결과가 어떻게 나올지 예측하기가 점점 더 힘들어진다. 주사위를 여러 번 던져서 나오는 눈의 합을 예측하는데, 주사위를 여러 번 던지면 던질 수록 그 결과가 크게 달라질 것이다. 매번의 예측마다 값이 크게 달라질 것이므로, 일관적이지 않으며, High Variance를 가지고 있다.

 

하지만 우리는 업데이트할 때 episode 끝까지, 즉 여러 번의 경험을 가지고 업데이트함으로 실제 value function과 일치율이 높을 것이다. 실제로 MC는 unbiased한 method이다.

 

 

 

TD의 경우,

 

 

바로 다음까지만 고려한 것을 타겟으로 삼는다. 이건 딱 하나의 경험만 놓고 업데이트 해버리는 것이므로, 굉장히 imperfect한 걸 바탕으로 업데이트한 것을 타겟으로 삼는 것이다. 당연히 타겟이 ground-truth value function과는 좀 다를 수 있다. 실제 데이터와 오차가 크므로, TD는 High Bias를 가지고 있다고 생각할 수 있다.

 

하지만 TD는 한 번에 조금조금씩 나아가기 때문에, 내놓은 결과물들은 매 step마다 대부분 비슷할 것이다. 이렇게 되면 예측 자체에는 일관성이 있다고 볼 수 있고, 그래서 Low Variance를 가지고 있다.

 

 

---

 

 

n-step TD

 

 

TD와 MC를 약간 절충안이다. MC는 full episode까지 기다렸다가 업데이트, TD(0)은 1-step만 가보고 업데이트하는 방법이면, 뭔가 특정 수 n을 하나 정해놓고 n-step을 가는, 적당히 좀 더 갔다가 업데이트 하는 것은 어떤가?

 

이게 n-step TD이다.

 

 

n까지 기다렸다가 업데이트 하는 것이다.

 

 

TD(λ) and Eligibility Trace

 

 

n-step TD는, TD와 MC의 장점을 합쳐놓은 방법이긴 하지만, 우리가 n을 직접 정해줘야 했었다. 그럼 또 여기서 적절한 n은 얼마인가의 문제가 생기기 시작한다. 여기서 한 단계 더 나아가서 n을 직접 정하지말고, 시간에 비례해서 과거의 step들에는 좀 decay된 weight를 부여해서 자동으로 n이 결정되게끔 하는 것은 어떤가? 라는 아이디어에서 출발한다.

 

최근에 방문했던 state에 대해서는 좀 더 가중치를 부여하고, 과거에 방문했던 state에 대해서는 좀 더 낮은 비율의 가중치를, 그리고 자주 방문하는 state에 대해서도 좀 더 높은 가중치를 부여하는 식으로 진행된다.

 

여기서 n을 결정할 필요가 없는게, λ 하나로 모든걸 결정할 수 있다. λ가 0일 경우가 바로 TD(0), 그리고 λ를 늘려서 무한대에 가까워질 수록 MC에 가까워진다.

 

이 부분을 이해하는 구조는, 우리의 목표는 TD(λ)를 하는 것이고, 이를 달성하기 위한 방법으로 Eligibility Trace를 한다는 것이다.

 

 

 

우리의 목표인 TD(λ)는 다음과 같다.

 

target인 G_t를 다음과 같이 구성하자.

 

 

이게 목표이긴 한데.. 몇 가지 애로사항이 있다.

 

• n = 1, 2, 3....T-t 각각에서 n+t의 시간만큼 매번 기다려야 식의 Rt+n을 구할 수 있다.
• 그리고 그걸 앞에 (1-λ)를 이용해서 weight하고 다 더해야된다.
• 위의 과정을 episode에 있는 모든 t에 대해서 다 해야된다. 이러면 future reward와 value estimate을 전부 저장해놔야되고, n에 대해서 loop을 episode 끝까지 돌리고, 전부 다하고 마지막에 V(s)가 업데이트 된다.

 

Eligibility Trace는 이걸 incrementally하게 달성할 수 있도록 해주는 방법이다. 위의 식은 Forward-View인데, 모든 n에 대한 infinity sum 계산으로, 아주 끔찍하다. Eligibility Trace를 검색해보면 Backward-View라는 단어를 봤을 것이다. 

 

Backward-View인 이유는, 우리가 방문 빈도를 반영하는 어떤 trace variable을 만든 후, 이걸 모든 state s에 적용할 것이기 때문이다. "뒤의 모든 state로 퍼진다" 라고 생각하면 될 것이다.

 

우선 원래의 수식을 보자.

 

1-step TD error를 게산하고, 이걸 trace variable과 alpha를 통해 비율을 조절해서 모든 state에 대한 업데이트를 시켜주는 것이다. 가장 왼쪽에 보면 V(s_t+1)이 아니라 그냥 그대로 V(s)인 것을 볼 수 있다.

 

 

 

이게 어떻게 모든 state에 대해 퍼지는지는 예시를 같이 보자.

 

우리는 분명 현재 state인 V(C)와, 다음 state인 V(D)만 고려하는 1-step 업데이트를 할 건데, 그 전의 state들인 A,B,C 들이 다 업데이트 되는 모습을 볼 수 있을 것이다. 핵심은, 1-step 업데이트만 하지만, 매번의 1-step 업데이트에서 "그 전의 state들의 value도 자동으로 full-λ return" 으로 업데이트 된다는 것이다. 여기 볼드체인 문장이 eligibility trace의 핵심 해석이다. 이것만 잘 기억하고 수식들을 보자.

 

일단 세팅은 다음과 같이 하자. 현재가 C, 그리고 다음 step이 D다. 딱 다음 한 스텝인 D까지 고려한 결과가 T이고, 이걸 target으로 놓고 (1-step target), 현재의 estimate와의 차이를 계산해 error 델타를 구했다.

 

그 다음에 trace varibale을 세팅해줄 것이다.

 

이렇게 trace를 만들고, 

 

지금부터 뒤로 3스텝 동안 방문한 state들이 각각 C, B, A라고 해보자. 그럼 trace variable은 다음과 같이 계산될 것이다.

 

그리고 모든 state A, B, C에 대해 업데이트 해준다. 아까 우리가 계산한 델타가 있고, 뒤에 trace variable도 있다.

그러면 우리는 분명히 1-step 업데이트를 했지만, 이전 state들의 value도 incrementally update되는 것을 볼 수 있다. 이게  Backward-View Eligibility trace 방법이다.

 

 

 

모든 state의 value들이 점진적으로 full-λ return으로 업데이트되며 나아가는 모습을 볼 수 있다.

 

---

 

 

다음 게시물에서는 TD learning의 control 부분 (policy improvment) 인 SARSA와 Q-learning에 대해서 알아보자. SARSA는 On-policy method이고, Q-learning은 Off-policy method이기 때문에, 이 두 가지의 차이를 중점으로 다루게 될 것이다.