Markov Decision Process(마르코프 결정 과정) 이란?

마르코프 결정 과정(MDP)은 불확실한 환경에서 여러 결정이 순차적으로 이뤄지는 의사결정 문제를 수학적으로 모델링하는 프레임워크이며, 순서대로 상태 공간 ((S)), 행동 공간 ((A)), 초기 상태의 확률 분포 (( d_{0} )), 보상 함수 (( r )) , 전이 확률 분포 (( p )) , 할인률 (( \gamma ))이다. MDP는 순서쌍 (( ( S, A, r, d_{0}, p,  \gamma) )) 으로 정의된다고 말할 수 있다.

 MDP는 각 행동이 서로 다른 결과를 초래할 수 있는 환경에서 작동해야 하는 스마트 기계 또는 에이전트를 설계하는 데 이용한다.

 

즉, 다시 말해서 순차적 의사 결정 문제를 적당히 단순화하여 정의할 수 있게 만들어주는 틀이다. 그래서 다음과 같은 질문을 답하는데 도움을 준다.

• 에이전트는 어떤 행동을 해야 하는가
• 행동이 일어나면 무슨 일이 발생하는가
• 결과가 좋은가 나쁜가

1. 상태(((S))):  상태는 에이전트가 있을 수 있는 상황 또는 조건이다. 해당 에이전트가 가질 수 있는 상태나 상황이 여러 존재한다면, 이를 다 포함하는 것이다.
    (( S={s_{1}​,s_{2}​,…,s_{N}​},∣S∣=N ))
   N은 전체 상태의 개수를 나타낸다.
   
   
2. 행동(((A))): 행동이란 에이전트가 취할 수 있는 모든 것이다. 예를 들어, 위로 이동, 아래로 이동, 왼쪽으로 이동 또는 오른쪽으로 이동 등이 있다. 각 상태는 하나 이상의 가능한 행동을 가질 수 있게 된다.
   (( A={a_{1}​,a_{2}​,…,a_{K}​},∣A∣=K ))
   K는 전체 행동의 총 개수를 나타낸다.
   
   
3. 보상(((R))): 보상은 에이전트가 행동을 취한 후 주어지는 숫자이다. 보상이 양수이면 행동의 결과가 좋았다는 의미이고, 음수이면 결과가 나빴다는 의미이다. 이는 에이전트가 무엇이 좋고 나쁜지 학습하는 데 도움을 준다.
    여기서 보상 함수는 특정 상태에서 취한 행동의 좋고 나쁨을 나타내는 함수이다. 각 방법론마다 보상 함수의 정의역이 조금씩 다르긴 하지만, 가장 보편적인 보상함수는 상태 ((s))에서 행동 ((a))에 대해서 보상을 부여한다. 다음으로 많이 사용되는 정의는 상태 ((s))에서 행동 ((a))를 취하여 상태가 ((s^{'}))으로 바뀐 것에 대해서 보상을 부여한다.
   
   
4. Trajectory와 전이 함수, 전이 확률 분포(((T))): 초기 상태 확률 분포 ((d_{0}))는 환경이 가질수 있는 초기 상태의 확률 분포이다. 각 상태마다 환경이 해당 상태를 초기 상태로 가질 확률이 정의되어 있는 함수로 해석할 수 있기 때문에 (( d_{0} : S \rightarrow  [0, 1] )) 로 적어준다. 해당 ((d_{0}))는 각 상태를 0과 1사이의 값으로 보내는 함수라고 읽으면 된다. 초기 상태, 즉 첫 번째 시점에서의 환경의 상태를 ((s_{0} ~ d_{0}))로 적어준다. 환경의 첫 번째 상태 ((s_{0}))는 초기 상태 확률 분포 ((d_{0}))에서 샘플링되었다는 의미이다.
   
   환경의 초기 상태 ((s_{0}))에서 시작해, 에이전트는 행동을 취하기 시작한다. 에이전트가 ((s_{0}))에 대해 취한 행동을 ((a_{0})), 받은 보상을 ((r_{0} = r(s_{0},a_{0})))이라고 표기한다면, t 시점에서의 보상 함수는 (( r_{t} = r(s_{t},a_{t}) ))이 된다. 이런 일련의 과정을 아래와 같이 나타낼 수 있다.
    
   (( \tau=(s_0, a_0, r_0, \, s_1, a_1, r_1, \ldots, \, s_{T-1}, a_{T-1}, r_{T-1}, \, s_T), ))
   
   이 일련의 과정 ((\tau))을 trajectory라고 부른다. 상태 ((s_{0}))부터 시작하여 ((T))번의 행동을 취하고 상태 ((S_{T}))에 방문하며 하나의 trajectory가 완성된다.
   만약 ((t))시점에서 어떤 상태가 발생할지 알고 싶으면 다음과 같은 조건부 확률 분포를 고려해야 한다.
   
   ((p(s_t|s_0,a_0,s_1,a_1,\ldots,s_{t-1},a_{t-1})=p(s_t|s_{t-1},a_{t-1}))) 
   
   여기서 MDP가 ((t))시점의 상태를 ((t-1))시점의 상태와 행동에 의해서만 결정된다고 가정하여 문제를 단순화시킨다. 해당 문제를 단순화 시켜 위의 식으로 가정을 하는 것이며, 이 가정이 성립할 경우 해당 순차적 의사 결정 문제가 Markov property(마르코프 성질)를 만족한다고 말한다. 다른 말로, 다음 상태는 현재 상태와 행동에만 의존하는 성질이다. 순차적 의사 결정 문제가 Markov property를 성립한다고 가정하기 때문에 Markov decision process라고 부르는 것이다.
   
   전이 함수(transition Function)는 에이전트가 특정 상태에서 어떤 행동을 했을 때, 다음 상태가 무엇이 될지 결정하는 함수이다. 상태 ((s))에서 행동 ((a))를 하면 어디로 가는가에 대한 답을 해준다. 환경이 결정론적(deterministic) 일 경우, 같은 상태에서 같은 행동을 하면 항상 동일한 다음 상태로 이동한다. 이때 전이 함수는 다음과 같이 정의된다.
   
   (( T: S \times A \rightarrow  S ))
   
   그러나 현실의 환경은 대부분 확률론적(stochastic) 이다. 같은 상태에서 같은 행동을 하더라도 다음 상태가 달라질 수 있다. 이를 표현하기 위해 전이 확률 분포를 사용한다.
   
   전이 확률 분포 (transition probability distribution) ((p))는 상태 ((s))에서 행동 ((a))를 취했을 때 여러 외부 환경과 상호작용으로 그 이후 상태가 ((s^{'}))으로 전이할 확률을 나타낸다.
   
   (( p : S \times A \times S \rightarrow [0, 1] ))
   
   해당 함수에서 각 함수값마다 확률이 부여되어 있다. 조건부 확률로써의 정의는 아래와 같다.
   
   (( p(s,a,s')=\text{Pr}[s'|S_t=s,A_t=a] ))
   
   직관성을 위해 ((p(s,a,s^{'})))대신 ((p(s'|s,a)))으로 표기해준다.
   ((p(s'|s,a)))는 확률 분포이므로, 어떤 상태 ((s))에서 행동 ((a))를 취했을 때 가능한 모든 다음 상태로의 전이 확률의 합은 반드시 1이어야 한다.
   
   (( \sum_{s' \in S} p(s' \mid s, a) = 1, \quad \forall s \in S, a \in A))
   
   
5. 할인률(discount factor): 할인률은 (( \gamma \in [0,1]  )) 은 0과 1사이의 값을 갖는 실수값이며, 더 나중에 받은 보상일수록 더 낮은 가중치를 부여하는 역할을 한다. 이는 미래 보상을 현재 가치로 환산할 때 얼마나 중요하게 볼 것인가를 결정하는 하이퍼파라미터다.
   강화학습에서 에이전트의 목표는 단순히 즉각적인 보상(reward)을 최대화하는 것이 아니라, 누적 보상(cumulative reward)을 최대화하는 것이 목표이다. 
    이 할인률이 필요한 이유로는 미래의 보상은 현재의 보상보다 불확실하다는 점과 에피소드가 끝나지 않는 환경(무한 horizon)에서는 보상의 합이 무한대로 발산할 수 있다는 점에 있어서 해당 할인율을 적용한다.
   
   t 시점이 계속 지날 수록, 할인률 때문에 해당 미래 보상에 대한 가치를 결정할 수 있기 때문에, 레이싱게임을 비유하면, 목표지점으로 빠르게 간 에이전트에게 미래에 대한 보상값을 더 많이 줄 수 있는거고, 너무 느리게 도착한 에이전트에게는 더 적은 미래에 대한 보상값을 주는 등 예시를 들 수 있겠다.
   
   예를 들어, (( trajectory \quad \tau = (s_0, a_0, r_0, s_1, a_1, r_1, \ldots) ))가 주어졌을 때, 이 trajectory에서 받은 총 누적 보상을 계산할 때 단순하게 더해주는 대신 다음과 같이 가중합을 하는 것이다.
   
   (( r_0 + \gamma r_1 + \gamma^2 r_2 + \gamma^3 r_3 + \ldots ))
   
   시간 ((t)) 에서의 누적 할인 보상(Return) ((G_{t}))​는 다음과 같이 정의된다
   
   ((G_t = r_{t} + \gamma r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \dots = \sum_{k=0}^{\infty} \gamma^k r_{t+k}))
   
   이를 재귀적으로 표현하면 다음과 같다.
   
   ((G_t = r_{t} + \gamma r_{t+1} ))
   
   이 재귀 표현은 나중에 벨만 방정식(Bellman Equation) 의 핵심이 된다.
   여기서 ((G_t))라고 표기한 것은, ((t))시점부터 받은 보상들의 할인된 누적 합이다. 이를 ((Return \ G_{t}))라고 한다. 즉 특정 ((t))시점의 반환값이다. 환경이 확률론적(stochastic)이기 때문에 ((G_t))​는 확률변수이고, 따라서 에이전트의 학습 목표는 다음과 같이 기댓값을 극대화하는 정책 ((\pi))를 찾는 것이다. 해당 반환값들의 평균(기댓값)을 극대화하는 방향으로 학습을 이어나가도록 해야한다.

((\gamma)) 값에 따른 의미

(( \gamma)) 값	의미	특징
(( \gamma ))= 0	오직 현재 보상만 고려	근시안적(myopic) 에이전트
0< (( \gamma ))<1	미래 보상을 점차 감소시켜 고려	일반적으로 사용하는 범위
(( \gamma )) = 1	미래 보상을 현재와 동일하게 고려	에피소드가 반드시 종료되어야 함

 

 

https://hiddenbeginner.github.io/Deep-Reinforcement-Learnings/book/Chapter1/2-markov-decision-processes.html

2. Markov Decision Process (MDP) — 심층강화학습

https://www.geeksforgeeks.org/machine-learning/markov-decision-process/

Markov Decision Process - GeeksforGeeks

 

https://www.geeksforgeeks.org/machine-learning/what-is-markov-decision-process-mdp-and-its-relevance-to-reinforcement-learning/