마르코프 결정 과정 문서 원본 보기

{{위키데이터 속성 추적}}
{{기계 학습}}
'''마르코프 결정 과정'''(MDP, Markov Decision Process)는 의사결정 과정을 모델링하는 수학적인 틀을 제공한다. 이 때 의사결정의 결과는 의사결정자의 결정에도 좌우되지만, 어느 정도 임의적으로 주어진다. 마르코프 결정 과정은 [[동적 계획법]]과 [[강화 학습]] 등의 방법으로 푸는 넓은 범위의 [[최적화 문제]]에 유용한 도구로 활용되며, [[로봇 공학]], [[제어 자동화]], [[경제학]], [[제조업]] 등의 영역에서 폭넓게 사용되고 있다. 마르코프 결정 과정은 적어도 1950년대에 처음 고안되었으며, 마르코프 결정 과정에 대한 가장 핵심적인 연구는 1960년에 출판된 [[로널드 하워드]]의 책 《동적 계획법과 마르코프 과정》(''Dynamic Programming and Markov Processes'')<ref name=":0">{{서적 인용|url=https://trid.trb.org/view.aspx?id=521429|제목=DYNAMIC PROGRAMMING AND MARKOV PROCESSES|성=HOWARD|이름=RONALD A|날짜=1960|출판사=Massachusetts Institute of Technology Press|확인날짜=|archive-date=2017-10-11|archive-url=https://web.archive.org/web/20171011181535/https://trid.trb.org/view.aspx?id=521429|url-status=}}</ref>이다.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

==== 값 반복법 (Value iteration) ====
값 반복법<ref>{{저널 인용|제목=A Markovian Decision Process|저널=Journal of Mathematics and Mechanics|성=Bellman|이름=Richard|url=http://www.jstor.org/stable/24900506?seq=1#page_scan_tab_contents|날짜=1957|출판사=Indiana University Mathematics Department}}</ref>은 역진 귀납법(backward induction)이라고도 불리며, <math>\pi</math> 함수를 사용하지 않는다. 대신, <math>\pi(s)</math>의 값은 필요에 따라 <math>V(s)</math> 안에서 계산된다. 확률 게임(stochastic games)에 관한 [[로이드 섀플리]]의 1953년 논문<ref>{{저널 인용|제목=Stochastic Games|저널=Proceedings of the National Academy of Sciences|성=Shapley|이름=L. S.|url=http://www.pnas.org/content/39/10/1095|날짜=1953-10-01|권=39|호=10|쪽=1095–1100|언어=en|doi=10.1073/pnas.39.10.1095|issn=0027-8424|pmid=16589380}}</ref>은 값 반복법을 마르코프 결정 과정을 푸는 방법의 특별한 경우로 소개했으나, 나중에서야 알려지게 되었다.<ref>{{서적 인용|url=https://link.springer.com/chapter/10.1007/978-1-4615-0805-2_2|제목=Finite State and Action MDPS|성=Kallenberg|이름=Lodewijk|날짜=2003|총서=International Series in Operations Research & Management Science|출판사=Springer, Boston, MA|쪽=21–87|언어=en|doi=10.1007/978-1-4615-0805-2_2|isbn=9781461352488}}</ref>

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

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

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

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

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

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

== 같이 보기 ==
* [[동적 계획법]]
* [[Q 러닝]]

== 각주 ==
{{각주}}

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