모델프리 학습 - Model Free Learning - Prediction technique by MC, TD

Model Free MDP에서는 어떻게 Evaluation 을 하여 Prediction 문제를 풀 수 있을까?

---

이전 글 : 모델기반 학습

[Artificial Intelligence/Reinforcement Learning] - 모델기반 학습 - Model Based Learning - Value, Policy Iteration by Dynamic Programming

모델기반 학습 - Model Based Learning - Value, Policy Iteration by Dynamic Programming

 

Model Free based Learning

• Model based Learning

이전 장에서 살펴 본 문제는 Model based learning 기법이고, 이는 앞서 상세히 다뤄 본 바 있으나 간략히 정의 하면 아래의 두가지 가정을 전제로 한다.

• State transition Prabability 를 명확히 알고 있다
• Reward 를 정확히 알고 있다.

결국 이는 환경과 환경의 전이에 대한 모든 요소들이 map 과 같이 훤한 경우를 뜻하며, Dynamic Programming을 통해 이러한 MDP의 full knowledge 를 예측 하고 가정한다. 앞선 정의에서 Model based 는 Model을 ‘갖고 있다’ 라는 의미로도 해석하였다. 즉, 자신의 action에 따라서 environment가 어떻게 바뀔지 안다면 실제로 행동하기 전에 미리 변화를 예상 해보고 최적의 행동을 계획하여 실행 할 수 있는 것이다. 이와 같은 Planning 과정은 Model based learning 에서 optimal 한 behavior 를 찾는데 가장 중요한 기준이 되며 이러한 Planning을 통한 prediction 과 control 과정 전반은 full visibility를 기초로 하여 full knowledge를 알아 낼 수 있기 때문에 가능한 것이었다.

• Model Free Learning

하지만 보통의 세계는 그렇지 않다. environment의 정확한 model은 보통 알아내기 어렵거나 불가능하다. 혹시라도 model이 environment를 제대로 반영하지 못한다면 이 오류는 그대로 agent의 오류로 이어지게 되며 정확한 model을 만드는 것은 좋은 agent를 만드는 것 보다 어려운 일 일 수 도 있다. 이러한 환경에서의 Model Free Learning을 간략히 정의하면, MDP에서 모델이 주어지지 않았을 때 최적의 정책 함수를 찾아내는 것이라고 한다.

즉, 환경이 어떻게 동작되는지 알지 못한 상태에서 수동적으로 다음 상태와 보상을 얻게 되는 강화학습이다. 다시 말해서 주어진 상태 S에서 어떤 행동 a를 수행하고, “수동적으로” 환경을 알려 주는 다음 상태S’를 얻게 되는 것이다. 게임을 생각하면 이해가 쉬운데, 상태 S 모니터 스크린으로, 행동 a를 키보드 입력에 해당한다고 생각해 보자. 우리가 모니터를 보고 어떤 행동을 하게 되면 어떤 화면이 다음 번에 나타나고, 게임 스코어 등으로 보상을 받을 수 있다. Model based learning과 달리 우리는 더 이상 환경이 어떻게 동작하는지 알지 못한다. 그렇기 때문에 직접 해 보고 그 결과를 통해 정책 함수를 점차 학습시켜야 한다. 현재까지 알고 있는 사실을 좀 더 파고들어서 더 좋은 결과를 얻으려고 하는 것을 exploitation, 새로운 것들을 시도하는 것을 exploation라고 하고, 강화학습 1회차 포스팅에서 이미 소개 한 바 있다.

이러한 model free 환경에서 model을 사용하지 않는 agent를 model free agent라고 부르며, State transition probability 와 Reward를 정확히 모르고 있는 상태에서의 학습 기법을 Model Free learning 기법이라 한다. (계속 비슷한 말의 연속이지만, 핵심은 Model이 없는 상태에서 직접 해보고 결과를 학습한다! 이거다.)

Model Free learning 역시 Prediction 과 Contol 두가 지 문제로 나뉜다.

• Model Free Prediction
  • 알려지지 않은 MDP에 대한 value function을 estimation 한다.
  • MC 와 TD 기법이 활용 된다.
• Model Free Control
  • 알려지지 않은 MDP에 대한 value function과 policy를 optimize 한다.

---

 

Monte-Carlo (MC) Learning

MC Learning은 간략히 말하면 경험의 에피소드(episode)로부터 직접 value function을 학습하며 에피소드 끝에만 보상을 받는다는 것을 의미 한다. 모델을 모르는 상황이므로, 환경과 직접적으로 상호작용을 하면서 Policy를 따라 직접 action을 수행 해보고 그 경험에 따라 받은 리워드들을 종합해서 판단 해본다는 episode of experience 기반 학습이며, episode of experience를 바탕으로 value fonction을 업데이트 한다. 이러한 MC Learning이 성립 하기 위해서는 아래의 전제와 학습 방식을 가진다.

• MC는 value function을 평균 값으로 업데이트 한다.
  • 현재 상태 St 에 대한 value function은 여러 갈래의 action a, a’, a’’ 등의 시행에 따른 return 들의 평균으로 업데이트 한다.
• episodic MDP 에만 적용 가능하며, 모든 episode는 terminal state 가 있어야 한다.

MC의 목적은 policy $\pi$가 episodes of experience 에 대해 주어졌을 때 이에 대한 $v_\pi$ 를 구하는 것으로 , 이 state value function 값은 곧 예상 되는 return의 기대값이며, return은 전체 discounted reward이다.

• $V(s) = \mathbb E[G_t|S_t = s]$
• return $G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2r_{t+3} ... + \gamma^{T-1}r_T$

단, 여기서 return 의 기대값이라고 표현하긴 하지만 MC자체가 trial 과 trial and error 를 통해 학습 하는 과정이므로 실제 수행한 결과에 대한 sample mean 이라는 관점에서의 평균이 좀 더 맞는 표현이라 할 수 있다. (emperical mean return VS expected return)

 

MC policy Evaluation - state 의 value를 evaluate 하기!

MC를 수행하면서 policy 를 학습 하기위해 state s 의 evaluate 하는 것은 곧 리턴의 sample mean 을 계산 하는 것과 같은 의미이고 이는 아래의 3단계의 process로 구분지을 수 있다.

 

Incremental MC Update - state 의 value function을 update 하기!

MC를 수행하면서 하나의 에피소드가 완료가 되면 점진적으로 value function을 업데이트 하게 된다. 즉, 실시간으로 매 에피소드 수행 시마다 업데이트 되는데 이전의 평균값과 현재 값을 이용해서 업데이트 하는 것이 핵심이다.

매 state $S_t$ 마다 return $G_t$를 받는다면,,

• 방문 횟수 업데이트 $N(S_t) \leftarrow N(S_t) +1$
• Value 업데이트 $V(S_t) \leftarrow V(S_t) + \frac{1}{N(S_t)}(G_t - V(S_t))$

이는 현재의 $V(S_t)$ 에 대하여 현재 받은 return 에서 현재의 Value function 값을 빼준 이전까지의 return 합계를 방문횟수 N으로 나눠 준 값을 $V(S_t)$ 에 더해주어 업데이트 하는 개념이 된다.

Incremental mean 최종 수식에서 위 value 업데이트 간소화 식의 개념을 대입 해보자면,

• $\mu_{k-1}$ 은 이전 state 의 평균을 의미,
• $x_{k}$ 는 현재 값
• $\mu_{lk-1}$ 은 역시 이전 state 의 평균을 의미 하므로, value 업데이트 간소화 수식의 흐름과 동일하게 된다.

만약 시간의 변화에 따라 통계적 특성이 변하여 시계열 데이터가 non-stationary 하다면, 평균 $\mu$ 가 함수가 될 수 없으므로, 러닝 레이트를 활용 한다.

• $V(S_t) \leftarrow V(S_t) + \alpha(G_t - V(S_t))$

즉, 평균 산출 시 이전의 횟수를 사용하는 것이 아니라 특별한 running mean을 적당히 작은 수로 세팅하여 과거에 시행 했던 데이터에 대해서는 가중치를 조금씩 줄여 나가는 것이다.

---

 

Temporal-Difference (TD) Learning

TD Learning은 경험의 에피소드(episode)로부터 직접 value function을 학습하며 에피소드 끝에만 보상을 받는다는 점과, model free 상황에서 사용하는 기법이라는 점은 같으나 incomplete episode 즉, terminal state 가 없어도 된다는 점에서는 더 범용적인 접근 방식이라 할 수 있다.

MC는 일단 에피소드가 한회차는 끝나야 state value function을 업데이트 가능 했기에 학습을 실시간으로 수행하기에는 어려운 단점이 있었다. TD를 활용하면 매시간 단계 (time step)마다 value funtion 을 업데이트 할 수 있다.

즉, MC와 비교해서 TD의 목적 역시 policy $\pi$가 episodes of experience 에 대해 주어졌을 때 이에 대한 $v_\pi$ 를 구하는 것임은 같으나 time step t별 업데이트, terminal state 가 없어도 된다는 점만 다른 것이다.

• $V(S_t) \leftarrow V(S_t) + \alpha(G_t - V(S_t))$

$G_t$에 해당하는 실제 return값은 원래 terminal state 까지 가봐야 산출이 가능 한 값이 었는데, TD 상황에서는 terminal state 까지 가 볼 수 없으므로 정확힌 $G_t$를 알 수 없으므로 estimated 된 return 값인 $r_{t+1} + \gamma V(S_{t+1})$를 사용한다.

• $V(S_t) \leftarrow V(S_t) + \alpha(r_{t+1} + \gamma V(S_{t+1}) - V(S_t))$

이 estimated return 을 TD target 이라 하고, terminal 까지 가는 episode 가 끝나지 않았으므로 예측 밖에 할 수 없기 때문에 활용 하는 대체제로서의 역할을 하는 셈이다.

러닝레이트 뒤에 붙은 $(r_{t+1} + \gamma V(S_{t+1}) - V(S_t))$ 이 term 전체를 TD error 라고 하고, 학습은 이 TD error 를 추정해 가는 식으로 이루어 진다.

TD와 MC를 비교하면 MC의 경우 return을 알 수 있을 때까지 episode 를 계속 진행 하여 기다려야 하지만, TD는 바로 업데이트를 진행 할 수 있다는 장점이있다.

---

 

MC vs TD

TD 상황에서는 매 time step t마다 value function의 업데이트가 발생 할 수 있다는 점, episode 끝까지 시행 될때 까지 기다릴 필요가 없다는 점에 대해 언급 하였지만, Bais와 Variance 관점에서 좀 더 practical 한 비교가 가능하다.

MC는 평균 return인 $G_t$ 가 무수히 많은 시행이 있다면 $V_\pi(S_t)$ 로 수렴 한다는 점에서 zero bias 의 장점이 있다. 이것은 곧 머신러닝의 가장 큰 숙제 중 하나라고도 할 수 있는 initail value 선정의 모호함에서 자유롭다는 뜻이다. 결국 수렴하기 때문에 이 initail value에 민감하지 않고 전체적으로 직관적인 수행 반복이 이루어지므로 가단하고 쉽게 수행이 가능하다.

단, 많은 random action, transition, reward 가 발생하고 전체 episode를 다 해봐야 하기 때문에 high variance 경향을 보인다.

TD는 TD target 자체가 estimated 된 return 을 의미하므로 $V_\pi(S_t)$ 역시 어느정도 정확도의 문제가 발생 할 수 있다. 이러한 some bias 문제로 인해 initial value 에 상대적으로 민감하게 동작하는 경향이 있다. 하지만 time step t 별 value update 하는 동작 방식으로 인해 하나의 random action, transition, reward 가 발생하므로 variance 가 낮다. 통상적으로 TD가 MC보다는 효율적으로 사용되고 있다.

MC와 TD의 tree search 상황에서의 동작 방식을 비교하면 아래의 도식으로 설명 할 수 있다.

지금까지 살펴본 DP, MC, TD 방식의 prediction 과정을 model 과 학습 방식 상황별 매트릭스로 표현해 보면 아래와 같이 정리 된다.

• full backup 은 MDP를 모두 알고 있는 model based learning 에서 적용 할 수 있는 기법인데, 모든 가지 case 에 대해 DP 같은 iteration 연산 없이 일일이 계산하는 Exhaustive search 는 비현실적인 기법이다. 알고리즘을 공부해본 사람들은 바로 느낌이 오겠지만 매우 간단한 N qeen 문제만 봐도 시간 복잡도 문제로 메모리가 터지기 마련이다.
• sample backup 은 MDP를 모르는 model free learning 기법들인데, episode terminal 까지 가보는 MC와 time step 별 업데이트 만 수행하는 TD의 차이점을 볼 수 있다.

 

---

지금까지 Model based 문제와 Model Free 문제에 대해 상세히 비교해보고, Model Free 상황에서의 대표적인 Prediction 기법인 MC와 TD에 대해 알아보았다.

다음 정리에서는 Model Free 환경에서의 Control 문제 중 on-policy learning 상황과 off-policy learning 상황에 대해 각각 어떻게 접근 할지에 대해서 알아본다.