모델프리 학습 - Model Free Learning - Control technique on On-Policy

Model Free MDP에서는 어떻게 최적의 Value function을 찾고 Policy  를 찾아 Control 문제를 풀 수 있을까?

---

이전 글 : 모델프리 학습 Prediction

[Artificial Intelligence/Reinforcement Learning] - 모델프리 학습 - Model Free Learning - Prediction technique by MC, TD

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

 

Background Remind

이전 장에서 Model based MDP 외에 transition prabability 와 reward를 알 수 없는 (Model이 없는) Model Free MDP 에 대해 정리 했고, 이러한 환경에서는 어떻게 Prediction 을 할 수 있을 지에 대해 알아 보았다.

요약 하면 Model free Prediction 문제는 MC와 TD 기법을 활용하여 알려지지 않은 MDP에 대한 value function 을 estimation 하는 문제 였고 그 상세 기법들은 아래와 같이 정리 할 수 있다.

• MC Learning - policy evaluation
  • policy $\pi$ 가 주어지고 이 $\pi$를 따랐을때 얻을 수 있는 value funtion 의 기댓값인 $V_\pi$ 를 학습
  • 직접 모든 episode를 수행 해보고 total return 을 시행횟수로 나누어 sample mean을 통해 value 를 구하는 식으로 evaluation.
  • Terminal state 가 반드시 존재 해야하며, 리턴 역시 Terminal state 까지 진행 한 후의 리턴을 사용하여 value update.
  • $V(S_t) \leftarrow V(S_t) + \alpha(G_t - V(S_t))$
  • High variance / zero bias
• TD Leaning - policy evaluation
  • 동일한 Model Free 환경에서 MC와 동일하게 수행하나, terminal state 가 없는 상황에서도 수행 가능하며, 매시간 단계 (time step)마다 value funtion 을 업데이트 진행
  • $G_t$에 해당하는 실제 return값은 원래 terminal state 까지 가봐야 산출이 가능 한 값이 었는데, TD 상황에서는 terminal state 까지 가 볼 수 없으므로 정확힌 $G_t$를 알 수 없으므로 estimated 된 return 값인 $r_{t+1} + \gamma V(S_{t+1})$를 사용.
  • 이 estimated 된 return 값을 TD target 이라 하며, 이는 terminal 까지 가는 episode 가 끝나지 않았으므로 예측 밖에 할 수 없기 때문에 활용 하는 대체제로서의 역할 수행
  • High bias / some variance

아울러, Prediction 문제와 함께 최적의 Value funtion 과 Policy 를 찾아가는 Optimality 과정이 필요한데(Control), 우리는 먼저 살펴 본 Model based learning에서 policy iteration 과 value iteration 을 Greedy 하게 수행하여 반복적인 imporvement를 통해 최적의 Value funtion 과 Policy 로 수렴하는 과정도 보았다.

---

 

Control Problem on Model Free based Learning

우리는 이제 Model Free 환경에서의 Control 문제를 해결 해야 한다. 이는 알려지지 않은 MDP에 대한 value function 과 policy 를 OPTIMIZE 하는 문제이다.

Model Free 환경에서의 Policy Evaluation 은 이전 장에서 정리한 MC와 TD 기법을 통해 수행 하여 가치를 측정 할 수는 있으나, Policy Iteration 과정을 통한 Policy Improvement 는 일단 MDP에 대한 knowledge 가 없는 상태이므로 Greedy 하게 업데이트 시켜서 최적으로 수렴시키는 Model based learning의 방식을 쓸 수 없다.

이러한 문제를 해결 하기 위해 우리는 model based MDP 에서 정의 했던 Greedy Policy Improvement 수식을 조금 변형해서 사용 해야 한다.

 

Q function 을 통한 Policy Iteration with Improvement

model based MDP 에서 정의했던 Greedy Policy iteration 수식은 아래와 같다.

$$ \pi'(s) = \argmax_aR_s^a + P^a_{ss'}V(s') $$

Policy 를 Improvement 하기 위해 Policy에 따른 Value function $V(s)$를 계속해서 개선해 나갔던 것이 Model based MDP에서의 접근이었다면, Model Free 상황에서는 $R_s^a +P^a_{ss'}V(s')$ 이 unknown 이므로 이것을 변형 해줘야 한다.

$$ \pi'(s) = \argmax_aQ(s,a) $$

이 $Q(s,a)$은 state action value function으로서, 이제는 이 action value function 으로 policy 를 iteration 한다는 것을 의미한다. 이 function 을 Q-function 이라하며,

model based MDP 에서 $V = V^\pi \rightarrow V^* , \pi^$ 와 같이 value function 을 통해 optimality로 수렴시키는 문제가 model free MDP 에서는 $Q = q^\pi \rightarrow q^, \pi^*$ 와 같이 Q 값을 통해 optimality 로 수렴시키는 문제로 바뀌었다.

Policy Iteration 의 기준값이 V에서 Q로 evaluation 단계에서부터 바뀌었다. 그렇다면 Improvement는 어떻게 될까?

 

$\epsilon$-Greedy Exploration

본 강화학습 정리 1강의 용어 정리 부분에서 Exploration 과 Exploitation 을 소개 한 바이다. 명확한 정의가 기억이 나지 않는다면 1강으로 돌아가보자. $\epsilon$-Greedy 는 매번 최적화 된 action 을 선택 하는것이 아니라 임의성 확률적으로 부여 하여 학습결과가 local minimum에 빠지거나 overfit 되는 현상을 방지한다. 일반적인 Greedy 기법에서는 항상 최적 대안을 선택하므로 금방 비슷한 패턴의 결과를 학습해 버려 풍부한 대응 전략을 고려 하지 못하게 된다. 이를 방지하기 위해 0~1사이의 $\epsilon$ 값을 부여하여 random 하게 다른 action 을 선택 해보는 행위를 뜻한다

 

Model free Policy Iteration = Policy Evaluation + Policy Improvement

종합하면, model free 의 policy iteration 과정에서 Policy Evaluation 은 V가 아닌 Q기준으로 측정 되게 되고, Policy 에 대해 Improvement 하는 로직은 $\epsilon$-greedy policy improvement 방식을 이용하며, 모든 episode 마다의 Q를 incremental 하게 수행하므로 Q값은 $q\pi$ 값에 수렴한다. 이를 도식으로 표현하면 다음과 같으며, Every episode 마다의 incremental 수행 기법이 포함되고 안되고의 차이 역시 아래 두 도식의 차이점을 면 쉽게 이해 할 수 있다.

 

 

GLIE MC Control

앞서 소개한 $\epsilon$-Greedy Policy Improvement는 학습이 상당히 진행 된 상황에서도 항상 $\epsilon$의 확률로 임의의 행동을 하게 된다는 단점이 있다. 이때 $\epsilon$값을 학습이 진행 될 수록 줄여 준다면 결국 학습 횟수가 $\infty$로 증가한다면 결국 greedy policy 에 수렴하게 될 것이다. GLIE 가 성립하기 위해서는 두가지 조건을 만족 해야 한다.

• 모든 state-action pair는 무한히 많은 횟수로 exploration 되어야 한다.
• Policy는 결국 greedy policy 에 수렴한다.

이 두가지 조건을 만족하다면 Greedy in the Limit with Infinite Exploration (GLIE) 를 만족한다고 하며,

$\epsilon \leftarrow 1/k$ 와 같이 매 회차마다 $\epsilon$ 값을 줄여줘서 0으로 수렴시키는 테크닉을 사용해서 학습을 진행한다. 이는 원활한 학습 효과를 위해서 최소 1%는 랜덤한 action을 취해주어 야 하는데 이 1% 값 역시 매 회차마다 줄여나가서 결국 무한히 episode 를 시행 했을 때 $\epsilon \rightarrow 0$ 으로 수렴 시키는 것이다.

 

 

Monte Carlo 에서 Time-Difference로..

앞선 Model free Predictin 문제에서 소개 된 TD 기법의 경우, MC에 비해 몇가지 장점이 있었다.

 

첫째로, 시퀀스가 끝나지 않아도 사용가능 하므로 online 학습이 가능하다는 점,

둘째로, terminal state 가 없어도 estimated 된 return을 활용하여 학습이 가능 하다는 점,

셋째로, MC에 비해 variance가 낮다는 점이다.

 

Model free Control 문제에서도 MC기법 대시 TD 기법이 사용 될 수 있다.

위에 쭉 따라 내려온 MC 기반 Policy Iteration 과정 중 Policy evaluation 에서 TD를 Q-function 인 $Q(S,A)$에 적용 할 수 있고, Policy Improvement 는 동일하게 $\epsilon$-Greedy 기법을 적용 할 수 있다. 또한 하나의 episode 가 끝날때 까지 기다렸다가 업데이트 하는 것이 아니라 매 time-step 마다 policy 를 업데이트 하는 아이디어를 동일하게 적용 시킬 수 있다.

---

 

SARSA

SARSA란 일반적인 Policy Iteration 기법과 TD기법이 결합 된 정책 알고리즘 이다. 사실 앞서 쭉 설명한 Model Free MDP에서의 Policy iteration 과정은 이 SARSA까지 도달하기 위한 과정이었다고 보면 되고, 바로 뒤에 On-policy learning 과 Off-policy learning 의 소개가 나오겠지만, SARSA는 대표적인 On-policy Learning 알고리즘이라고 할 수 있다.

Policy Iteration 로직은 TD와 결합하여 하나의 time step 수행 후의 policy evaluation 만으로도 polish improvement를 이룩 할 수 있다고 이미 소개 한 바 있다. 이러한 관점에서 SARSA는 하나의 time step 이후 다음 state에서의 어떤 action 을 선택 했을때 현재의 action value function 이 되는 Q-funtion 즉, TD target 을 통해 현재의 action value function을 업데이트 한다는 의미를 담고 있다.

즉, SARSA는 TD를 활용한 policy control 알고리즘인 것이다.

SARSA는 현재 state S에서 어떤 action A을 선택한 상황에서 받는 reward R과, 이 상황으로 인해 전이할 state S’ 와 이 state A’ 에 대한 action value function 인 Q(S',A') 를 합산한 값에서 현재 state 의 action value function 인 Q(S,A) 를 빼준 값을 가지고 현재 state 를 정의 하는데 이 수식이 TD target 과 동일하다. SARSA라는 이름은 위에 나열된 state 의 전이 과정에서의 action 과 reward 의 나열로 네이밍 된 것이다.

위 psedo code는 SARSA 알고리즘의 흐름을 보여주는데, S와 a의 matrix인 look up table을 시작으로 흘러가는 이 코드의 흐름은 시간날 때 자세히 따라가보자. 외울 필요 없고 흐름만 이해하면 된다.

---

 

On-policy vs Off-policy Learning

• On-policy learning

우리가 경험하는 policy 와 update 하는 policy 가 같은 경우를 말하고 “Learn on the job” 이라는 표현으로 쉽게 설명된다. 무슨 뜻이냐면 간단히 동일 agent 가 행한 경험을 통해 policy $\pi$를 학습하고 이 policy를 적용하는 것으로, Data efficiency가 떨어지지만 구현이 쉽고 여러 종류의 정책에 적용 가능하다는 장점이 있다. 이는 policy update 에 실제로 action을 하고 있는 가장 최신의 policy 로 수집된 데이터만 사용해서 update 하는 기초적 형태의 학습 방법이며 MC나 SARSA 등이 이 범주에 속한다.

(학습을 하는 policy = 경험을 쌓는 policy), (behavior policy = targeting policy)

• Off-policy learning

현재의 policy 가 아니라 다른 agent 의 polish 를 가지고 학습 하는 경우를 말한다. 즉, 다른 agent 의 policy 로부터의 경험으로 학습한다는 뜻의 “Look over someone`s shoulder” 라는 표현으로 설명된다. 이는 policy 업데이트 과정에 어떤 데이터를 써도 상관 없는 학습 방법이며 Q-learning 이 이에 해당하는 대표적 알고리즘으로 분류된다.

지금까지 model based VS model free, on-polish VS off-policy 와 같이 상황과 학습 방법을 크게 분류하는 개념들이 나왔는데, 이를 굳이 도식화 하면 위와 같이 분류 된다.

 

 

 

---

지금까지 Model Free 환경에서의 Control 문제를 generalized policy iteration 관점에서 해결하는 접근 방식을 알아보았고, 이러한 일반적인 Control 해법에 TD 방식을 결합하여 on policy learning 중 대표적 알고리즘이라 할 수 있는 SARSA에 대해 정리 해보았다.

다음 정리에서는 Model Free 환경에서의 Control 문제 중 off-policy learning 상황에 대해 해법인 Q-learning 에 대해 알아보고자 한다.