[확률적 시스템] 마르코프 결정 프로세스 기본 (Markov Decision Process)

동적 계획법(Dynamic Programming) 또는 베이즈 이론(Bayes Theorem)을 다루다보면 결정적 시스템(Deterministic Process)에서 벗어나 확률적 시스템(Stochastic System)에 들어가게 된다. 

 

결정적 시스템이란 어떤 상태(s)에서 행동(a)를 선택할 때 결과가 한 가지로 정해져있는 시스템이라고 할 수 있다

 

아쉽게도 현실의 대부분은 결정적 시스템이 아닌 확률적 시스템이다.

같은 행동을 하더라도, 다른 결과가 나올 수 있다. 

쉽게 예를 들면, 내가 시속 100km로 1시간 주행했을 때, 어떤 날은 100km를 갈수도 있지만, 교통체증이 심각하거나 교통 사고라도 발생한 날엔 50km도 못갈 수 있다. 행동 하나를 하더라도 다른 결과를 초래할 수 있는 것이 확률적 시스템이다.

 

강화학습은 기본적으로 확률적 시스템을 채택한다.

주어진 상태, 환경에서 어떤 행동을 했을 때, 그 결과를 통해 이득인지 손실인지를 반복적으로 학습하는 방식이다.

결국 이 원리가 Q-학습까지 이어진다.

 

따라서 강화학습을 최소한으로 이해하기 위해서라면, 수학적으로 너무 딥한 수준은 아니더라도 베이즈 확률과 같은 확률론과 마르코프 결정 프로세스에 대해 알고 넘어가는 것이 필요하다.

 

만약 확률과 친숙하지 않다거나, 게임 이론 또는 고등미시경제학을 경험해보지 못한 분들이라면 다음에 설명할 내용이 조금은 지루하고 왜 배워야하는지 의문점이 드는 경우가 많으리라 생각한다. 

 

상태 천이 확률 (state transition probability)

확률적 시스템에서의 상태 천이 확률에 대해 알아보자. 기본적으로 확률적 시스템내에서의 상태 천이 확률은 조건부 확률로 표기할 수 있습니다.

• \(P(s_{t+1} | s_t, a_t) = p_{s_{t+1}, s_t, a_t}\) 
• t시점에서의 행동: \( a_t \)
• t시점에서의 상태: \( s_t \)
• 즉 위 수식은 't 시점에서 어떠한 상태가 주어졌고, 그 상태에 액션을 취했을 때, 다음 시점 (t+1)의 상태가 될 확률'이라고 해석할 수 있습니다.

 

만약에 세 가지 상태를 갖는 시스템을 가정한다면, 다음과 같은 상태 천이 확률 행렬(state transition probabillity matrix)로 나타낼 수 있습니다. 

\( p_{(다음 상태, 현재 상태)} \)은 현재 상태에서 다음 상태로 갈 확률을 의미합니다.

즉 위 상태 천이 확률 행렬을 그래프로 묘사하자면 아래의 그림과 같습니다.

마르코프성(Markov Property)과 마르코프 결정 프로세스(MDP)

위 상태 천이 확률을 이해하셨다면, 마르코프성에 대해서 이해할 준비가 되었다고 생각합니다.

마르코프 성은 어떤 변수가 1시점 이전의 변수로부터만 영향을 받고, 확률적으로 변화하는 성질을 가질 때, 이 연속열이 마르코프성을 갖는다고 가정하는 것입니다. 

 

마르코프성은 다음과 같은 식이 성립합니다.

$$P(s_{t+1} | s_t, s_{t-1}, ..., s_1) = P(s_{t+1}| s_{1:t}) = P(s_{t+1} | s_t)$$

 

다시 말하면, 과거 모든 사건을 함께 따져도 시점 t에서의 변수의 값을 결정하는 확률 분포가 1시각 이전의 변수의 값으로부터만 영향을 받음을 의미합니다.

 

이것을 가정하면 확률이 굉장히 간단해집니다. 

또한 지금은 t 시점만 고려하여 t+1 시점의 상태의 확률을 표현을 했는데, 한 개의 시점만 고려했기때문에 1차 마르코프성(1st order Markov Property)이라고 표현을 합니다. 

 

그 외에도 2차, 3차, ..., n차 마르코프성을 가정할 수 있습니다. (하지만 계산 대비 기대 이익이 너무 낮다는 평가를 받습니다. 따라서 1차만 가정해도 굉장히 큰 효과를 누릴 수 있다고 합니다)

 

또한 마르코프성을 기초로 하는 마르코프 모형과 마르코프 과정이 있습니다.

• 마르코프성을 갖는 상태 천이 모형을 마르코프 모형(Markove Model)이라고 합니다.
• 마르코프 모형으로 생성되는 상태 천이 연속열을 마르코프 과정(Markov Process)이라고 합니다 (또는 Markov Chain으로 설명할 수도 있음)

마르코프 모형은 결국 확률 변수 사이에서 영향을 주고 받는 관계로 생각할 수 있습니다.

따라서 그래프 모형으로 관계를 도식화한다면, 조금 더 직관적으로 확률 변수간의 관계를 이해할 수 있습니다.

그래피컬 모형을 사용하면 결국 시간방향의 천이 외에도 다양한 변수 사이의 상호관계를 나타낼 수 있다는 장점이 있죠.

아래의 그림처럼 상태공간 외에도 액션 공간(action space)를 고려하는 경우가 대표적이라고 할 수 있습니다.

위 그림처럼 행동 \(a_t\)에도 의존하여 상태 \(s_{t+1}\)이 결정되는 확률적 시스템, P(s_{t+1} | s_t, a_t)을 마르코프 결정 프로세스(Markov Decision Process, MDP)라고 합니다.

 

그리고 MDP에서 어디까지의 변수를 무시할 수 있는가를 알기위해서 확률 모형 식을 그래피컬 모형으로 변형하면 알기 쉬운데요. 바로 마르코프 블랭킷(Markov blanket, \(\partial A\))를 확인하면 됩니다. 아래의 그림을 보겠습니다.

 

마르코프 블랭킷

마르코프 블랭킷은 빨간색 점선안에서 A노드를 제외한 모든 부분이라고 보면 되는데요. 

간단하게 말해서 A노드의 부모 노드, A노드의 자식노드, A노드의 자식노드의 부모노드를 포함한다고 할 수 있습니다.

 

이렇게 되면 A의 확률을 구할 때, 마르코프 블랭킷이 주어져있다는 조건 하에서만 고려하여 확률값을 구할 수 있기 때문에, 좋은 성질을 이용할 수 있습니다.