Gurugail Algorithm/Markov Decision Process
Algorithm

Markov Decision Process

의사결정트리(Decision Tree)는 주어진 자료들에 대한 분류 및 판단을 하기 위한 인공지능의 알고리즘의 하나인데 MDP(Markov Decision Tree)도 유사하게 주어진 자료나 상황들에 대한 결정(Decision)을 내리기 위한 또 다른 알고리즘을 제공한다. 쉽게 설명하면 주어진 환경에서 최적의 판단이나 행동을 결정해야 할 때 사용되는 알고리즘이다. 가령 격자 월드에서의 동물이 먹이와 적이 있을 때 어떻게 먹이와 적을 대응할 때 가장 생존률이 높게끔 행위를 결정하고자 할 때 사용될 수 있다.

MDP 정의

MDP는 상태(S, State)와 액션(A, Action), 전이(T, Transition) 그리고 상태 전이에 따른 외부 환경으로부터의 보상(R, Reward)로 구성된다. 상태 전이는 확률 기반으로 가능하다. 튜플(tuple)로 간결하게 표현하면 아래와 같다.

(S, A. T, R) where

  • S : 상태란 MDP 알고리즘에 의해 구현되는 시스템에 있어 구별될 수 있는 논리적 상황을 말함
  • A : 액션
  • T : S \times A \rightarrow P(S). P(s) 는 조금 더 수식적 표현을 하면 P(s' | s, a) 처럼 나타낼 수 있음
  • R : 상태 전이에 따른 보상으로 S와 A에 대한 함수로 표현 가능함, R(s, a)

[출처 : gameai.net]

찾고자 하는 문제 (problem)

위와 같은 MDP 가 구성될 때, 해결하고자 하는 문제는 무엇인가? 주어진 상태들에서 보상을 최대로 할 수 있는 액션들을 결정하는 것이라 할 수 있다. 어떤 상태에서 어떤 액션을 해야 하는 것인가 이 의문에 대한 답일 것이다. 해를 찾았다고 하면, policy \pi 에 의하여 다음과 같이 진행할 수 있으며, 결국 해법인 셈이다. 

 1. 현재 상태 S를 결정
 2. 상태 S에서 가능한  \pi  (S)를 행함
 3. 위 단계 1을 반복

그러나 policy \pi 를 찾고자 할 때 단순히 보상할 경우, 상태 전이를 반복하다 보면 계속 보상이 되어 결국 무한값이(infinite value) 될 것이다. 따라서 보상을 조절할 필요가 있다. 보통 discounting 방법을 사용한다. 간단히 설명하면, 상태 전이가 진행됨에 따라 보상을 \gamma ^ n 와 같이 줄여 가는 방식이다. (0 < \gamma < 1) 현재 상태에서의 보상은 그대로 보상을 받을 수 있지만, 다음 상태에서의 보상은 급격히 줄어들게 되는 것이다.

알고리즘

최대의 보상들을 찾을 수 있는 액션을 선택하는 문제는 아래 두 가지 중요 요소가 있다. \pi (s) 와 V(s)로 표현된다. 

  \pi  (s) = 상태 s에서 최대의 기대 보상(expected rewards)을 주는 액션
 V (s) = 상태 s에서  \pi 에 의한 액션으로 받을 수 있는 기대 보상으로 상태 전이들의 확률과 보상들에 의해 구해질수 있음

결국 주어진 상태에서 대하여 여러 가지의 가능한 액션들이 있고, 그런 액션들이 행해지면 상태 전이가 되면서 보상들이 주어진다. 그러한 보상들은 discounting의 방법으로 상태에서의 전이들에 대해서 미리 전이되지 않고서도 액션들에 대한 기대 보상을 예측할 수 있고, 기대 보상들이 예측되면 \pi (s) 인 액션을 결정할 수 있게 되는 것으로 이해하면 된다.

참고