검색 - Search Technique

Experience를 얻기 위해 시행한 매우 다양한 trial에서 state 결과를 효과적으로 찾는 방법에 대해 알아보자

 

---

이전 글 : 모델결합 학습

[Artificial Intelligence/Reinforcement Learning] - 모델결합 학습 - Integrating Learning and Planning

모델결합 학습 - Integrating Learning and Planning

 

 

Simulation based search

시뮬레이션 기반의 search 는 어떻게 할까? 기본적으로 Tree search 에서 출발한다.

강화학습의 가장 큰 기본 전제가 Markov property 였음을 잘 알고 있을 것이다. 현재 state 에서 판단 해볼때 이전 과정의 history 는 무도 무시하고 앞으로의 action 과 reward 에만 집중하는 Markov property 덕분에 우리는 현재 state 와 이후의 상황에만 관심을 가지면 된다.

이를 tree 관점에서 본다면, 현재 state 를 root로 하여 이후의 state 를 깊이든, 너비든 탐색 해나간다는 아이디어를 얻을 수 있다. “핵심은 이전에 일어났던 일은 관심 밖이다!” 라는 사실을 기억하자.

즉, 전체 MDP 중에 지금의 state 까지 온 MDP 영역은 제외해도 되고, 앞으로의 sub MDP에 대해서만 탐색해 나간다.

 Forwad search 패러다임은 sample based planning을 설명한다고 할 수 있다. 이전 정리에서 소개한 real experience 와 simulated experience를 각각 떠올려 보자. 기본적으로 존재하는 enviroment에서 여러 action pair를 실제로 수행 해본후 얻은 real experience로 Model을 만들었었다. 그 다음은 실제 모델을 정확히 모른다고 가정하므로 simulation 을 위한 sample episode를 뽑은 뒤 이것들을 기반으로 Model Free control 하는 것이 바로 simulation based-search의 핵심이다.

Simulation 과정은 아래와 같이 설명 가능하다.

$M_\eta$는 real experience 를 통해 학습한 approximated model 되고, 이 Model 을 기반으로 Reward를 발생시키고, 새로운 state로 transition 하는 과정을 거치는데, 이것을 K번 수행 하면 시뮬레이션 된 experience를 만들어 낼 수 있다.

이렇게 하면 Model Free MDP 문제로 변환되는데, Model Free control 때 주로 사용 해왓던 Monte-Carlo control 기반의 MC search와 Time-difference control 기반의 Sarsa 를 사용한 TD search를 생각 해 볼 수 있다.

 

MC search

Real experience로 학습된 모델 $M_\eta$ 과 시뮬레이션 할 policy 초기화 값이 주어진 simulation policy $\pi$ 를 생각해보자. 또한 모든 action $\alpha$는 액션 집합 $A$에 속한다고 가정하자.

현재의 real state $s_t$에서 $K$ episode를 수행한다고 하면, 아래와 같은 수식으로 표현 할 수 있다.

[1] 이는 real state 에서 가능한 모든 action에 대해서 동일 작업을 반복 수행 하는 것으로, action paire 인 s,a를 제외 한 term은 모두 시뮬레이션 된 값들임을 의미한다. s,a pair들은 approximated Model $M_\eta$에 실제로 입력을 해본 것이 된다. 이것은 즉, 시뮬레이션 할 샘플 pair를 K개 만드는 과정인 것이다.

[2] 이제는 MC evaluation을 생각해보자. k번 수행 해본 평균 return 을 가지고 action 을 평가해볼 수 있는데, 이 것은 시뮬레이션을 해봤더니 이 action을 해봤을때, 이 기대값이 나오는 구나…라는 상상의 결과임을 의미한다.

return $G_t$는 pair의 K번 에피소드들에 대한 평균 리턴을 가지고 action value function을 결정 한다는 뜻이다.

[3] 이제 이 action value function을 max로 만들어 주는 real action 을 고르자.

그중에 Q값이 가장 큰 것을 선택하는 policy 를 선택하는 이 과정이 바로 MC search 인 것이다.

 

MC Tree Search (Evaluation)

이 과정에서 의 simulation policy $\pi$를 생각해보자. policy 를 고려한다면, 앞에서는 모든 가능한 action에 대해 모두 다 고려해보고 수행 해보았는데, 이제는 simulation policy 를 따르는 하나의 action에 대해서만 반복 할 수 있다는 아이디어에 도달하게 된다.

action $a$ 가 simulation policy 를 따른 action 인 $A^k_t$ 로 바뀌었다. 이는 즉, simulation 한 policy 를 따른 action이기 때문에 모든 샘플을 다 고려 하지 않고, 확률이 높은 샘플을 먼저 고려하겠다는 의미가 된다.

이 시퀀스를 토대로 방문한 state 와 선택된 action 을 search tree 로 그린 후, 역시 같은 과정으로 evaluation 을 해보자.

이것은 역시 episode s,a 의 pair set에 대한 평균 리턴을 가지고 maximum action value function 을 찾는 문제가 된다.

이 시뮬레이션이 모두 끝나면, 역시 이 action value function을 max로 만들어 주는 real action 을 고른다.

 

MC Tree Search (Simulation)

현재 state 에서 K episode를 계속 수행 해나가는 과정에서 분명 시뮬레이션이 반복 되면서 시뮬레이션 policy 역시 계속 업데이트 (improve)될 것이다. 시뮬레이션 과정에서 매 시뮬레이션은 in-tree와 out-of-tree 라는 두가지 개념으로 나뉘게 된다.

in-tree는 현재 state에서 이미 방문하여 experience화 된 node를 뜻하고, out-of-tree는 아직 방문 하지 않아서 experience화 되지 않은 것을 의미하며 full tree에서 보면 leaf 로 남아있는 node 를 뜻한다.

각 두가지 tree에 각각 다른 policy 를 부여 한다면 어떻게 될까?

• Tree Policy : 이 것은 in-tree 에 적용 되는 것으로 Q(s,a)를 max로 만들어 주는 action 을 pick 한다. 이것이 가능한 이유는 방문했던 state는 Q값을 저장해서 알고 있으므로 그것을 기반으로 action을 선택 할 수 있기 때문인 것이다.
• Default Policy : 이 것은 out-off-tree에 적용 하는 것으로, experience가 없으므로 단순히 random하게 action 을 선택 하게 한다.

이 시뮬레이션을 계속 반복하면 policy 도 계속 업데이트 되는데, 앞에서 봤던 MC evaluation 을 통해 action value function인 Q(s,a) 를 도출하고 이 Q는 $\epsilon$-Greedy 와 같은 방법을 통해 tree policy 를 계속 improve 해 나갈 수 있다. 이것이 바로 시뮬레이션을 통해 policy 를 학습 하는 메카니즘이 되며, 반복을 거듭하다보면 결국 최적의 search tree 를 통해 최적의 $Q_* (S,A)$에 수렴하게 된다.

 

이러한 MCTS 전체 과정을 통해 결국 MCTS는 simulated experience를 사용해서 Q와 Policy를 계속 업데이트 하면서 하나의 optimal 한 Q를 만들어 나가는 것이라는 것을 알아보았다. action은? 이것을 기반으로 선택하여 수행 만 하면 된다.

 

MCTC의 전반적인 과정에 대해 한번 더 요약 해보자.

[1] 첫번째 에피소드에 대해 현재 state 에서 하나의 action a선택

[2] approxiation 한 모델 기반으로 다음 state로 넘어가고 이때 reward 수령

[3] 이렇게 에피소드가 끝날때까지 진행

[4] 터미널 state 로 도착

[5] 두번째 에피소드 시작

  : 두번째 에피소드 시작시 start point 로 돌아 오는데, 이때 이미 지나갔기 대문에 Q를 알고 있고, \epsilon-Greedy 를 사용해서 action을 선택 할때 어저다 한번식은 다른 것을 선택 해 본다.

 

이렇다 보니 시행 횟수 N이 늘어날 수록 평가 Q값이 정교해지는 효과를 얻을 수 있다.

또한, 여러 에피소드를 시행 할대, 같은 state라도 현재 상황이 달라서 평가도 다흔 것을 잘 반영해주고, 샘플링을 함으로서 차원의 저주 문제 역시 피해 갈 수 있다.

computation power 역시 효과적으로 사용할 수 있으며, 언제든지 병렬처리가 가능하다.

 

 

Temporal-Difference Search

앞서 정의 해온 것 과 같이 TD 는 MC에 비해 리턴 $G_t$ (에피소드 종료시 한번에 받을 수 있는 전체 return)대신 TD target 이라는 time step 별로 받을 수 있는 단기 return 을 사용 해왔다.

TD Search 역시 Simulation based search 이고, MC 대신 TD 계열의 Sarsa 를 활용하여 Control (Sarsa로 Q업데이트 하기) 하는 기법이라 보면 된다.

즉, MC tree search 에서는 현재 state 이후의 sub-MDP 전체에 MC control 기법을 적용했었다면, TD search 에서는 현재 state 이후의 sub-MDP 전체에 Sarsa를 적용한다.

즉, Q값을 업데이트 할때 터미널에서 받는 return 의 평균 대신에, TD target 으로 업데이트 한다는 TD의 기본 관념이 그대로 적용 된 것이다.

그렇게 업데이트 된 action value function을 기반으로 action 을 선택 하게 되는데 MC search 와 같이 여기서도 $\epsilon$-Greedy 기법을 주로 사용한다.

---

 

 

Model Learning and Search 요약

지금까지 정리 과정을 거쳐오면서 결국 모델 자체를 학습 하는 방법까지 문제를 확장하여 정리 해 보았다.

이 과정을 종합 하자면,

[1] 모델에 대한 parameter 를 만들 어 놓고, 에피소드를 실제로 진행 하면서 real experience를 얻었다.

[2] 그 후에는 이 real experience를 기반으로 그때까지의 실제로 받았던 reward와 state transition probability 를 true label로 지정 하였고

[3] 이 true label 을 토대로 1. reward function을 지도학습으로 학습, 2. state transition probability 를 확률 분포 기반 density estimation 기법으로 학습 하였다.

[4] 이렇게 구성되어 학습된 모델을 기반으로 샘플링을 수행하여 simulation 을 해보고 simulated experience를 얻는다. 이것은 상상 속에서 실제로 모델을 따라 가면서 새로운 에피소드들을 상상으로 진행 하는 것을 의미하

[5] 학습 과정을 종합 하면 real experience와 simulated experience를 가지고 Planning 이 핵심이다. 즉, 새로운 value function 과 policy 를 구해 나가는 과정이라 할 수 있다.

[6] 이 후 MCTC, TD search를 통해 어떻게 이 시뮬레이션 된 experience를 만들어 가면서 동시에 policy, state action value function 값을 업데이트 하는 지 알아 보았다.

 

 

 

---

Model 학습에 대한 정리와 Tree search 의 내용은 사실 하나의 주제로 바라보고 연속성을 가져가는게 좋은데, 내용이 너무 길어져서 Tree search 에 대한 내용은 별도의 챕터로 분리해서 정리하였다.

다음 정리에서는 강화학습 포스팅 초반에 아주 대충 알아보았던 exploration 과 exploitation 의 상세 기법과 trade-off 관계 및 action 선택시 이 두관념을 잘 조절하여 선택 할수 있는 방법론에 대해 살펴 보고자 한다.