마르코프 결정 과정

**마르코프 결정 과정**(MDP, Markov Decision Process)는 의사결정 과정을 모델링하는 수학적인 틀을 제공한다. 이 때 의사결정의 결과는 의사결정자의 결정에도 좌우되지만, 어느 정도 임의적으로 주어진다. 마르코프 결정 과정은 동적 계획법과 강화 학습 등의 방법으로 푸는 넓은 범위의 최적화 문제에 유용한 도구로 활용되며, 로봇 공학, 제어 자동화, 경제학, 제조업 등의 영역에서 폭넓게 사용되고 있다. 마르코프 결정 과정은 적어도 1950년대에 처음 고안되었으며, 마르코프 결정 과정에 대한 가장 핵심적인 연구는 1960년에 출판된 로널드 하워드의 책 《동적 계획법과 마르코프 과정》(*Dynamic Programming and Markov Processes*)이다.

더 정확히는, 마르코프 결정 과정은 이산 시간 확률 제어 과정(discrete time stochastic control process)이다. 어떤 시점에, 마르코프 결정 과정은 어떤 상태 s에 존재한다. 의사결정자는 해당 상태 s에서 어떤 행동 a를 취할 수 있으며, 다음 시점에서 마르코프 결정 과정은 확률적으로 새로운 상태 s'로 전이한다. 이 때 의사결정자는 상태 전이에 해당하는 보상 R_a(s, s')을 받는다. 기존의 상태 s에서 새로운 상태 s'로 전이하는 확률은 의사결정자의 행동에 영향을 받는다. 즉, 전이 확률 함수는 P_a(s, s')와 같이 주어진다. 따라서, 다음 상태 s'는 현재 상태 s와 의사결정자의 행동 a에만 영향을 받으며 이전의 모든 상태와는 확률적으로 독립적이므로, 마르코프 결정 과정의 상태 전이는 마르코프 속성을 만족한다.

마르코프 결정 과정은 마르코프 연쇄의 확장된 형태로 볼 수 있다. 마르코프 연쇄와의 차이점은 의사결정자의 선택이 개입된 행동이 존재한다는 것과, 의사결정자에게 동기를 부여하는 보상이 존재한다는 점이다. 바꾸어 말하면, 각 상태에서 오직 한 가지 행동만이 가능하며 모든 전이에 대한 보상이 같은 마르코프 결정 과정은 마르코프 연쇄와 동일하다.

## 정의
대체글=마르코프 결정 과정의 예시|섬네일|세 개의 상태(연두색 원)와 두 개의 행동(붉은색 원) 및 두 개의 보상(붉은색 화살표)가 있는 간단한 마르코프 결정 과정의 예시.
마르코프 결정 과정은 (S, A, P(\cdot,\cdot), R(\cdot,\cdot),\gamma)의 5중쌍으로 표현되며, 각 원소의 의미는 다음과 같다.
* S는 상태의 유한집합이다.
* A는 의사결정자가 취할 수 있는 행동의 유한집합이다. (상태 s에서 취할 수 있는 행동의 유한 집합 A_s로 표현할 수도 있다.)
* P_a(s,s') = \mathrm{Pr}(s_{t+1}=s'\ |\ s_t=s,a_t=a)는 어떠한 시점 t에 상태 s에서 행동 a를 취할 경우 다음 시점 t+1에 상태 s'으로 전이할 확률이다.
* R_a(s,s')는 상태 s에서 행동 a로 인해 상태 s'로 전이할 경우 받게 되는 즉각적인 보상(혹은 즉각적인 보상의 기댓값)이다.
* \gamma \in [0,1]는 할인인자(discount factor)로서, 현재 얻게 되는 보상이 미래에 얻게 될 보상보다 얼마나 더 중요한지를 나타내는 값이다.
(주: 마르코프 결정 과정 이론 자체는 S와 A가 유한하다는 제한을 두지 않으나, 마르코프 결정 과정을 다루는 기본적인 알고리즘은 이들이 유한집합이라는 가정을 가지고 있다.)

## 문제
마르코프 결정 과정의 핵심적인 문제는 의사결정자의 의사결정 정책(policy) \pi를 구하는 것이다. \pi는 상태 s에서 의사결정자가 취할 행동 \pi(s)=a를 지정하는 함수이다. 일단 의사결정자의 정책 \pi가 결정되면, 각 상태에서 행동이 결정된 마르코프 결정 과정은 사실상 마르코프 연쇄와 같이 동작한다.

문제의 목표는 확률적으로 주어지는 보상의 누적합을 최대화시키는 정책 \pi를 구하는 것이다. 보상의 누적합은 일반적으로 다음과 같이 무한한 시간에서 할인된 보상의 총계의 기댓값으로 계산한다.

\sum_{t=0}^\infty \gamma^t R_{\pi(s_t)}(s_t,s_{t+1})

일반적으로 할인인자 \gamma는 1에 가까운 수로 정해진다. 예를 들어 할인율이 r일 경우 \gamma=1/(1+r)과 같이 정한다.

마르코프 속성 때문에, 이 문제에 대한 최적해는 오직 초기 상태 s에 대한 함수로 표현될 수 있다.

## 알고리즘
마르코프 결정 과정은 선형 계획법 혹은 동적 계획법을 사용하여 풀 수 있다. 다음에서 서술하고 있는 것은 동적 계획법에 관련된 것이다.

상태 전이 함수 P와 보상 함수 R을 알고 있을 때, 할인된 보상의 총계의 기댓값을 최대화하는 정책을 구하는 것을 목표로 한다.

이러한 최적의 정책을 구하는 기본적인 알고리즘들은 상태를 첨자로 가지는 두 개의 배열을 필요로 한다. 첫 번째 배열 V는 각 상태의 기댓값을 저장하며, 두 번째 배열 \pi는 각 상태에서 취할 행동을 저장한다. 알고리즘이 종료된 후에 \pi는 최적의 정책을, V(s)는 상태 s에서 출발하여 최적의 정책을 따라 이동했을 때 얻을 수 있을 것으로 기대되는 할인된 보상의 총계를 저장하고 있게 된다.

알고리즘은 재귀적으로 정의되는 다음의 두 단계로 이루어진다.

\pi(s):=\arg\max_a\bigg\{\sum_{s'} P_a(s,s') \bigg(R_a(s,s')+\gamma V(s')\bigg)\bigg\}

V(s):=\sum_{s'} P_{\pi(s)}(s,s')\bigg(R_{\pi(s)}(s,s')+\gamma V(s')\bigg)

이 두 단계는 값이 수렴할 때까지 모든 상태에 대해 반복된다.

두 식이 계산되는 순서는 알고리즘의 종류에 따라 다르다. 또한 어떤 알고리즘은 모든 상태에 대해 한꺼번에 계산을 할 수도 있고, 혹은 각 상태마다 계산을 할 수도 있다. 모든 상태에서 두 단계의 계산이 계속 일어난다면 알고리즘은 결국에는 올바른 최적해에 도달하게 된다.

### 중요한 알고리즘의 종류

#### 값 반복법 (Value iteration)
값 반복법은 역진 귀납법(backward induction)이라고도 불리며, \pi 함수를 사용하지 않는다. 대신, \pi(s)의 값은 필요에 따라 V(s) 안에서 계산된다. 확률 게임(stochastic games)에 관한 로이드 섀플리의 1953년 논문은 값 반복법을 마르코프 결정 과정을 푸는 방법의 특별한 경우로 소개했으나, 나중에서야 알려지게 되었다.

\pi(s)의 계산을 V(s) 안에 대입하면 다음과 같은 식을 얻게 된다.

V_{i+1}(s) := \max_a \bigg\{\sum_{s'} P_a(s,s') \bigg(R_a(s, s') + \gamma V_i(s')\bigg)\bigg\}

여기서, 첨자 i는 반복 차수를 의미한다. 알고리즘은 i=0에서 시작하며, V_0은 값 함수에 대한 초기 추측이다. 모든 상태에 대하여 위의 식을 계속 계산해 나가면, 식의 좌변과 우변의 값이 같아진다. 즉, V의 값이 수렴한다.

#### 정책 반복법 (Policy iteration)
정책 반복법에서 \pi(s)를 계산하는 첫 번째 단계는 한 번만 수행되며, V(s)를 계산하는 두 번째 단계가 수렴할 때까지 반복된다. 그 이후에 다시 첫 번째 단계가 수행되고, 다시 두 번째 단계가 반복된다.

두 번째 단계를 수렴할 때까지 반복하는 대신 연립일차방정식으로 바꾸어 계산할 수도 있다.

이 방법은 뚜렷한 종료 조건이 있다는 장점을 가지고 있다. 만약 첫 번째 단계를 계산하는 과정에서 모든 상태에 대해 \pi가 바뀌지 않을 경우, 알고리즘을 끝내면 된다.

## 같이 보기
* 동적 계획법
* Q 러닝

## 각주

분류:기계 학습
분류:마르코프 과정
분류:최적 결정