# Markov Decision Process에 관하여 / + Markov Chain

 

Markov Decision Process에 관하여

 

인생은 B와 D 사이에 C라는 말이 있다. Birth 와 Death 사이의 Choice를 하는 것처럼 현재 상태에서 선택을 하는 것은 아주 중요하며, 이를 모델링 하는 것이 Markov Decision Process (마르코브 의사 결정)이다. 먼저 용어에서 두려움을 느끼는 사람들(나를 포함해서) 을 위해서 의미를 조급 쉽게 생각해보겠다.

 

• Markov : 다음 미래를 고려할 때, 과거는 싹다 잊고 현재만 생각하라는 Markov Property에서 왔다. 이게 없다면 의사 결정 시, 과거의 기록까지 전부 들춰봐야 한다. 마르코프라는 무서운 이름과는 다르게 아주 착한 일을 해준다.
• Decision: 위에서 말한 현재 상태에서 선택을 결정하는 것이다. MDP에서 말하는 선택이란 행동을 선택하는 것이다.
• Process: 프로세스는 시간에 따라서 변화하는 것을 지칭한다. 예를 들어서 공을 뻥 차면 점점 멀리 날아가는데 이것도 프로세스이고, 매월 줄어드는 혹은 늘어나는 내 통장 잔고도 프로세스이다.

 

세 가지를 모두 한 번에 고려하면, Markov Decision Process는 현재를 기준으로 행동을 선택하는 과정이다.

그런데 우리가 선택하는 상태를 생각하면 서로다른 무한히 많은 경우가 존재한다. 예를 들어서, 꿀벌이 방을 날아다니는데, 똑같은 곳에 꿀벌이 위치할 확률은 거의 0에 가깝다. MDP에서는 동전 던지기처럼 유한한 상태 (앞면과 뒷면) 만 있어도 설명하기에 충분하다.

 

왼쪽 꿀벌의 비행은 자유자재로 움직이는 꿀벌이 돌아다니면서 수많은 위치를 지난다. 반면에 오른쪽 동전 던지기에서는 딱 2개의 상태밖에 없다. 앞면 혹은 뒷면, 몇 번을 던저도 마찬가지이다. 

 

 

조금더 Formal한 정의를 살펴보기 전에 다음 예시를 보자. 서울에는 많은 대학이 있고 모든 대학을 모두 다닐 수 없지만, 단순히 방문하는 것이라면 연세대도 갔다가 고려대도 가는 방식으로 방문이 가능하다. Markov Process 이런 식으로 상태를 오가는 것으로 이해할 수 있다. 한 가지 추가되는 점은 상태를 바꾸기 위해서 행동을 선택한다는 것이다. 대학 방문의 경우, 걸어갈지, 버스를 탈지, 지하철을 탈지 정할 수 있기에 적절히 좋은 행동을 골라야 빠른 시간에 도착할 수 있다. 혹은 좋은 경치를 보는 게 목적이라면, 이에 맞춰서 이동수단을 선택하면 된다. 특정 시간 $t$ 에 대해서, MDP는 상태에 대하여 Random Variable $X_t$ 를 이용하여 표현한다.

 

[Random Variable $X_t$가 나타나는 게 불편할 수 있지만, 사실 이는 $t$ 시간의 상태를 표현하는 효율적인 방법이다. 우리는 해당 시간에 어떤 대학에 있을지 알 수 없으며, 여러 번 반복한다면 사실 모든 대학에 위치할 수 있기 때문이다. 물론 $t$ 시간에 모든 상태를 방문하지 못할 수도 있다. 예를 들어서, 내가 서강대 기숙사에 있고 학교 방문을 진행한다면, $t=1$ 시간에 나는 무조건 서강대에 있게 된다. + MDP에서 이런 strick한 가정에 대해서 어떻게 반응하는지 나도 잘 모르겠다.]

---

---

 

Markov Decision Process vs Markov Chain

 

Markov chain은 Markov Process라고도 불린다. (출처 위키: https://en.wikipedia.org/wiki/Markov_chain) 따라서 두 개의 차이는 Decision 단어의 여부에 달려있다. MDP와 MC는 다음과 같은 관계가 있다.

 

$$MDP = MC + Action$$

 

MDP는 MC에서 Action이 추가된 것에 불과하다! 실제로 수식으로 본다면 다음이 성립한다.

 

$$Pr(s_{t+1} = s' | s_t = s , a_t =a ) \cdot Pr(a_t = a) = Pr(s_{t+1} = s' | s_t = s )$$

 

여기서 왼쪽의 state transition distribution은 MDP에서 오른쪽의 state transition distr0ibution의 MC에서 사용되는 것이다. 만일 행동이 state와 독립 (indepdendent)이면,  MDP는 MC와 완전히 똑같아진다. 

 

 

 

---

To Be Continueeeed ...

 

* Recurrent / Transient 

* Positive Recurrent / Null Recurrent 

* Irreducible 

* Periodic / Aperiodic