[Deep Learning] 5. 마코프 의사결정 과정 (Markov decision process, MDP)

출처 1 : http://rfriend.tistory.com/184

출처 2 : http://secom.hanbat.ac.kr/or/chapter1/right04.html

출처 3 : https://brunch.co.kr/@kakao-it/73

먼저 마코프 의사결정 과정을 살펴보기에 앞서, 이 개념이 왜 딥러닝에서 필요한지 알 필요가 있다. 예를 들어 자율주행 자동차에 들어갈 알고리즘을 만든다고 치자. 이 때 가장 중요한 문제 중 하나는 확률계(Stochastic System)에서 순차적 의사결정(Sequential Decision) 문제를 푸는 것이다. 자동차를 제어할 때 빗길이라던지 비포장 도로 등의 원인으로 인해 우리가 원치 않는대로 움직일 수 있다. 이 때 예상과 일치하지 않는 상황을 확률계라 한다. 안전하게 운전하기 위해서는 매 순간, 연속적인 결정들을 내리고, 일련의 결정들의 결과로 얻어지는 상태들이 모두 안전해야한다. 그래서 이러한 알고리즘을 개발하기 위해 필요한 "강화학습(Reinforcement Learning)"은 확률적 의사결정 문제를 푸는 방법론들을 지칭한다. 

강화학습이란 ?

강화학습을 배우기 전에 앞서 지도학습을 먼저 떠올려 봐야한다. 지도학습은 학습 데이터를 통해서 유의미한 정보를 얻어내는 기계 학습 방법론에 속한다. 입출력 데이터가 주어졌을 때 새로운 입력에 대한 출력을 에측하는 방법론을 지칭하며, 입출력 데이터가 모두 주어진 상태에서 학습을 한다고 하여 지도학습이라고 한다. 

이 때와 반대대는 비지도학습은 강화학습이다. 즉, 학습데이터가 주어지지 않는다. 그 대신 강화학습에서는 보상 함수(Reward Function)이 주어진다. 강화학습은 미래에 얻어질 보상값들의 평균을 최대로 하는 정책 함수를 찾는 것이다. 

여기서 "미래"라는 것과 "기대값" 이라는 것에 주목해야한다. 연구자들은 이 강화학습 문제를 풀기위해서 수학적 모델인 마코프 의사결정 과정(Marcov Decision Process, MDP)를 차용하였다. 

마코프 의사결정 과정 (markov decision process, MDP)

불확실한 상황하에서 의사결정을 하려면 "확률"에 기초하여 분석을 해야한다. 어떤 사건이 발생할 확률 값이 시간에 따라 변화해 가는 과정을 확률적 과정(Stochastic Process)라고 하며, 확률적 과정 중에서 한 가지 특별한 경우가 마코프 과정(Markov Process) 이다. 

마코프 과정은 어떤 상태가 일정한 간격으로 변하고, 다음 상태는 현재상태에만 의존하며 확률적으로 변하는 경우의 상태의 변화를 뜻한다. 즉, 현재 상태에 대해서만 다음 상태가 결정되며, 현재 상태에 이르기까지의 과정은 전혀 고려할 필요가 없다.

마코프 과정에서 연속적인 시간 변화를 고려하지 않고, 이산적인 경우만 고려한 경우를 마코프 연쇄(Markov Chain) 이라고 한다. 마코프 연쇄는 각 시행의 결과가 여러개의 미리 정해진 결과 중의 하나가 되며, 각 시행의 결과는 과거의 역사와는 무관하며 오직 바로 직전 시행의 결과에만 영향을 받는 특징을 가지고 있다.

최적 정책 함수(Optimal Policy Function)를 찾는 방법

강화학습을 푸는 가장 기본적인 방법 두 가지는 값 반복(Value Iteration)과 정책 반복(Policy Iteration)이다. 이를 설명하기 위해서는 먼저 값을 정의할 필요가 있다. 만약 우리가 특정 상태에서 시작했을 때, 얻을 수 있을 것으로 기대하는 미래 보상의 합을 구할 수 있다면 해당 함수를 매번 최대로 만드는 행동을 선택할 수 있을 것이고, 이렇게 최적의 정책함수를 구할 수 있게 된다. 

바로 이 미래에 얻을 수 있는 보상들의 합의 기대 값을 값 함수(Value Function)이라고 한다. 이 함수는 바로 현재 상태 뿐만 아니라 미래의 상태들, 혹은 그 상태에서 얻을 수 있는 보상을 구해야 하기 때문에 직관적으로 정의할 수는 없다. 일반적으로 강화학습에서는 이 값 함수를 구하기 위해 벨만 이퀘이션(Bellman Equation)을 활용한다. 자세한 식은 참고자료를 참고하기 바란다.