Markov Process(MP)

강화 학습을 시작했다면 가장 먼저 이해해야 할 모델은 MDP(Markov Decision Process)입니다. 하지만 MDP를 이해하기 전에 MP(Markov Process) 모델부터 알아야 합니다.

 

먼저, MC는 이산 확률 프로세스(discrete sochastic process)입니다. 여기서 확률 프로세스란 확률 분포를 가진 랜덤 변수가 일정한 시간 간격으로 값을 발생시키는 것을 모델링하는 것을 의미합니다. 

위와 같은 그림을 Markov Chain이라고 합니다. 각각의 state로 움직일 때의 확률이 나와있고, 이 그림 같은 경우에 시간이 무한대로 흐른다면 모두 sleep으로 수렴하게 될 것입니다. 그리고 더 이상 변화가 없기 때문에 stationary distribution이라고 합니다. MC에서는 action을 할 확률과 action을 해서 어떤 state로 갈 확률이 주어지게 됩니다.

 

MC는 MP를 가진 랜덤변수의 수열이고, 현재의 상태가 주어졌을 때의 미래 상태의 조건부 확률 분포가 과거 상태와는 독립적으로 현재 상태의 의해서만 결정되는 것을 MP라고 합니다.

 

MP 모델은 딱 두 가지 속성으로 표현 가능합니다. 

• $X$ : (유한한)상태 공간(state space)의 집합.
• $P$ : 전이 확률(transition probability). 모든 상태(state) X 사이의 전이 확률을 의미.
• 이를 $MP(X, P)$와 같이 표기.

그다지 어려운 점은 없고 주어진 문제를 위의 두 가지 요소로만 기술한다고 생각하면 됩니다.  이 두 가지로 표현할 수 없는 문제는 당연히 MP로 해결할 수 없습니다. 따라서 일단 MP로 처리 가능한 문제에 대해서만 집중해 보도록 하겠습니다.

스텝(Step)

각 상태의 전이는 이산 시간(discrete time)에 이루어지며, 상태 집합 X에 속하는 어떤 임의의 상태에 머무를 때의 시간을 스텝(step)이라고 정의합니다. 만약 현재 스텝을 n이라 하면, 다음 스텝은 n + 1라고 생각할 수 있습니다.

 

이때의 상태 전이 확률 값을 간단하게 기술해 보겠습니다.

• $p_{ij}$는 상태 $i$에서 $j$로 전이될 확률 값을 의미.
• $X_n$은 스텝 $n$에서 머물러있는 상태(state)를 의미하며 정확히는 해당 상태(state)에 대한 랜덤 변수를 의미.

$p_{ij} = p(X_{n+1}=j | X_n = i) $       ∀ ${i,j} \in X$

 

중요한 것은 상태 $i$를 방문했을 때, 그 이전에 어떤 상태에 방문했는지 상관없이 상태 $i$에서의 다음 상태 $j$로의 전이 확률 값은 언제나 동일합니다. 이것은 MDP의 기본 속성이며 모델을 단순하게 만들어줍니다. 또한 이를 무기억성 속성이라고도 합니다. 수식으로 표현하면 다음과 같습니다.

 

$p_{ij} = p(X_{n+1} | X_n = i_n, X_{n-1}, ....X_0 = i_0) = p(X_{n+1} | X_n = i_n)$

 

이러한 특성(다음 상태의 확률이 오로지 전 상태에만 영향을 받는 특성)을 마르코프 속성(Markov Property)이라고 부릅니다. 추가적으로 전이 확률의 조건은 다음과 같습니다.

$p_{ij} \ge 0$

 

$\sum_{j \in X}p_{ij} = 1$           ∀ ${i,j} \in X$

 

이것은 전이 함수가 확률 함수이기 때문에 당연히 만족해야 하는 식입니다. 

 

이제 MP를 그래프로 표현하는 방법을 살펴보도록 해봅시다. 일반적으로 상태(state) X는 원(circle)으로 표기하고, 전이 확률 $P$는 상태 사이의 화살표로 표현하게 됩니다.

이제 스텝 n인 상황에서 현재까지 진행된 결과에 대한 확률 값을 표현해 봅시다. 현재 상태에서의 확률 함수는 다음과 같이 나타낼 수 있습니다.

$p(X_0 = i_0, X_1 = i_1,....., X_n = i_n)$

시작 시점부터 현재 상태까지 진행된 결과에 대한 확률값을 표현하고 있다. 이를 베이즈 룰을 이용하여 전개합니다.

$p(X_0 = i_0, X_1 = i_1,....., X_n = i_n)$

$=p(X_n = i_n | X_0 = i_0,....., X_{n-1} = i_{n-1})p(X_0 = i_0,....., X_{n-1} = i_{n-1})$

$= P_{i(0),i(1)}P_{i(1),i(2)},....., P_{i(n-1),i(n)}$

이를 n-step 전이 확률이라고 합니다.

 

다음으로 임의의 상태 $i$에서 출발하여 다른 상태 $j$로의 n-step 전이 확률을 나타내 봅시다. 여기서는 상태 $i$로부터 정확히 $n$회 이동을 하여 상태 $j$에 도달하는 경우를 말한다. 이때의 함수를 $r$로 표기합니다.

$r_{ij}(n) = p(X_n = j | X_0 = i)$

이를 전개하면,

$r_{ij}(n) = \sum_{k=1}^{k} r_{ij}(n-1)p_{kj}$

 

위아 같이 $r$ 함수에 대해 재귀적으로 표현 가능하고 다시 확률 함수로도 전환 가능합니다.

$r_{ij}(1) = p_{ij}$

$r_{ij}(2) = \sum_{k=1}^{k}r_{ik}(1)p_{kj} = \sum_{k=1}^{k}p_{ik}p_{kj} = p_{ij}^{(2)}$

위 식에서 $p^{2}$에 기술된 지수값 $(2)$는 제곱을 의미하는 것이 아니라 총 2-step임을 나타내는 요약식입니다. 즉, 2단계를 거쳐 $i$에서 $j$까지 이동하는 확률 값을 의미하게 됩니다. 이제 이 표현 방법을 일반화하여 $r_{ij}(n) = p_{ij}^{(2)}$와 같이 기술할 수 있게 됩니다. 물론 이 식은 RL과 직접적인 관계가 있는 것은 아니지만 개념을 잡기 위해서는 알아둬야 할 필요가 있습니다.

 

---

이 글은 아래 세 개의 글을 재구성하여 작성한 글입니다.

https://passi0n.tistory.com/80

https://norman3.github.io/rl/docs/chapter01.html  http://contents.kocw.or.kr/contents4/document/lec/2013/Konkuk/Honghyeoncheol/8.pdf

---

이 글은 PC에 최적화 되어 있습니다. 모바일로 접속시 [여기] 로 접속해 주세요