마르코프 결정 과정

마르코프 결정 과정(MDP, Markov Decision Process)는 의사결정 과정을 모델링하는 수학적인 틀을 제공한다. 이 때 의사결정의 결과는 의사결정자의 결정에도 좌우되지만, 어느 정도 임의적으로 주어진다. 마르코프 결정 과정은동적 계획법과강화 학습등의 방법으로 푸는 넓은 범위의최적화 문제에 유용한 도구로 활용되며,로봇 공학,제어 자동화,경제학,제조업등의 영역에서 폭넓게 사용되고 있다. 마르코프 결정 과정은 적어도 1950년대에 처음 고안되었으며, 마르코프 결정 과정에 대한 가장 핵심적인 연구는 1960년에 출판된로널드 하워드의 책 《동적 계획법과 마르코프 과정》(Dynamic Programming and Markov Processes)이다.
더 정확히는, 마르코프 결정 과정은이산 시간확률 제어 과정(discrete time stochastic control process)이다. 어떤 시점에, 마르코프 결정 과정은 어떤 상태s{\displaystyle s}에 존재한다. 의사결정자는 해당 상태s{\displaystyle s}에서 어떤 행동a{\displaystyle a}를 취할 수 있으며, 다음 시점에서 마르코프 결정 과정은 확률적으로 새로운 상태s′{\displaystyle s'}로 전이한다. 이 때 의사결정자는 상태 전이에 해당하는 보상Ra(s,s′){\displaystyle R_{a}(s,s')}을 받는다. 기존의 상태s{\displaystyle s}에서 새로운 상태s′{\displaystyle s'}로 전이하는 확률은 의사결정자의 행동에 영향을 받는다. 즉, 전이 확률 함수는Pa(s,s′){\displaystyle P_{a}(s,s')}와 같이 주어진다. 따라서, 다음 상태s′{\displaystyle s'}는 현재 상태s{\displaystyle s}와 의사결정자의 행동a{\displaystyle a}에만 영향을 받으며 이전의 모든 상태와는 확률적으로 독립적이므로, 마르코프 결정 과정의 상태 전이는마르코프 속성을 만족한다.
마르코프 결정 과정은마르코프 연쇄의 확장된 형태로 볼 수 있다. 마르코프 연쇄와의 차이점은 의사결정자의 선택이 개입된 행동이 존재한다는 것과, 의사결정자에게 동기를 부여하는 보상이 존재한다는 점이다. 바꾸어 말하면, 각 상태에서 오직 한 가지 행동만이 가능하며 모든 전이에 대한 보상이 같은 마르코프 결정 과정은 마르코프 연쇄와 동일하다.
마르코프 결정 과정은(S,A,P(⋅,⋅),R(⋅,⋅),γ){\displaystyle (S,A,P(\cdot ,\cdot ),R(\cdot ,\cdot ),\gamma )}의 5중쌍으로 표현되며, 각 원소의 의미는 다음과 같다.
(주: 마르코프 결정 과정 이론 자체는S{\displaystyle S}와A{\displaystyle A}가 유한하다는 제한을 두지 않으나, 마르코프 결정 과정을 다루는 기본적인 알고리즘은 이들이 유한집합이라는 가정을 가지고 있다.)
마르코프 결정 과정의 핵심적인 문제는 의사결정자의 의사결정 정책(policy)π{\displaystyle \pi }를 구하는 것이다.π{\displaystyle \pi }는 상태s{\displaystyle s}에서 의사결정자가 취할 행동π(s)=a{\displaystyle \pi (s)=a}를 지정하는 함수이다. 일단 의사결정자의 정책π{\displaystyle \pi }가 결정되면, 각 상태에서 행동이 결정된 마르코프 결정 과정은 사실상 마르코프 연쇄와 같이 동작한다.
문제의 목표는 확률적으로 주어지는 보상의 누적합을 최대화시키는 정책π{\displaystyle \pi }를 구하는 것이다. 보상의 누적합은 일반적으로 다음과 같이 무한한 시간에서 할인된 보상의 총계의 기댓값으로 계산한다.
∑t=0∞γtRπ(st)(st,st+1){\displaystyle \sum _{t=0}^{\infty }\gamma ^{t}R_{\pi (s_{t})}(s_{t},s_{t+1})}
일반적으로 할인인자γ{\displaystyle \gamma }는 1에 가까운 수로 정해진다. 예를 들어 할인율이r{\displaystyle r}일 경우γ=1/(1+r){\displaystyle \gamma =1/(1+r)}과 같이 정한다.
마르코프 속성 때문에, 이 문제에 대한 최적해는 오직 초기 상태s{\displaystyle s}에 대한 함수로 표현될 수 있다.
마르코프 결정 과정은선형 계획법혹은동적 계획법을 사용하여 풀 수 있다. 다음에서 서술하고 있는 것은 동적 계획법에 관련된 것이다.
상태 전이 함수P{\displaystyle P}와 보상 함수R{\displaystyle R}을 알고 있을 때, 할인된 보상의 총계의 기댓값을 최대화하는 정책을 구하는 것을 목표로 한다.
이러한 최적의 정책을 구하는 기본적인 알고리즘들은 상태를 첨자로 가지는 두 개의 배열을 필요로 한다. 첫 번째 배열V{\displaystyle V}는 각 상태의 기댓값을 저장하며, 두 번째 배열π{\displaystyle \pi }는 각 상태에서 취할 행동을 저장한다. 알고리즘이 종료된 후에π{\displaystyle \pi }는 최적의 정책을,V(s){\displaystyle V(s)}는 상태s{\displaystyle s}에서 출발하여 최적의 정책을 따라 이동했을 때 얻을 수 있을 것으로 기대되는 할인된 보상의 총계를 저장하고 있게 된다.
알고리즘은 재귀적으로 정의되는 다음의 두 단계로 이루어진다.
π(s):=arg⁡maxa{∑s′Pa(s,s′)(Ra(s,s′)+γV(s′))}{\displaystyle \pi (s):=\arg \max _{a}{\bigg \{}\sum _{s'}P_{a}(s,s'){\bigg (}R_{a}(s,s')+\gamma V(s'){\bigg )}{\bigg \}}}
V(s):=∑s′Pπ(s)(s,s′)(Rπ(s)(s,s′)+γV(s′)){\displaystyle V(s):=\sum _{s'}P_{\pi (s)}(s,s'){\bigg (}R_{\pi (s)}(s,s')+\gamma V(s'){\bigg )}}
이 두 단계는 값이 수렴할 때까지 모든 상태에 대해 반복된다.
두 식이 계산되는 순서는 알고리즘의 종류에 따라 다르다. 또한 어떤 알고리즘은 모든 상태에 대해 한꺼번에 계산을 할 수도 있고, 혹은 각 상태마다 계산을 할 수도 있다. 모든 상태에서 두 단계의 계산이 계속 일어난다면 알고리즘은 결국에는 올바른 최적해에 도달하게 된다.
값 반복법은 역진 귀납법(backward induction)이라고도 불리며,π{\displaystyle \pi }함수를 사용하지 않는다. 대신,π(s){\displaystyle \pi (s)}의 값은 필요에 따라V(s){\displaystyle V(s)}안에서 계산된다. 확률 게임(stochastic games)에 관한로이드 섀플리의 1953년 논문은 값 반복법을 마르코프 결정 과정을 푸는 방법의 특별한 경우로 소개했으나, 나중에서야 알려지게 되었다.
π(s){\displaystyle \pi (s)}의 계산을V(s){\displaystyle V(s)}안에 대입하면 다음과 같은 식을 얻게 된다.
Vi+1(s):=maxa{∑s′Pa(s,s′)(Ra(s,s′)+γVi(s′))}{\displaystyle 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{\displaystyle i}는 반복 차수를 의미한다. 알고리즘은i=0{\displaystyle i=0}에서 시작하며,V0{\displaystyle V_{0}}은 값 함수에 대한 초기 추측이다. 모든 상태에 대하여 위의 식을 계속 계산해 나가면, 식의 좌변과 우변의 값이 같아진다. 즉,V{\displaystyle V}의 값이 수렴한다.
정책 반복법에서π(s){\displaystyle \pi (s)}를 계산하는 첫 번째 단계는 한 번만 수행되며,V(s){\displaystyle V(s)}를 계산하는 두 번째 단계가 수렴할 때까지 반복된다. 그 이후에 다시 첫 번째 단계가 수행되고, 다시 두 번째 단계가 반복된다.
두 번째 단계를 수렴할 때까지 반복하는 대신 연립일차방정식으로 바꾸어 계산할 수도 있다.
이 방법은 뚜렷한 종료 조건이 있다는 장점을 가지고 있다. 만약 첫 번째 단계를 계산하는 과정에서 모든 상태에 대해π{\displaystyle \pi }가 바뀌지 않을 경우, 알고리즘을 끝내면 된다.