Markov Process

Markov Process(MP)

 

Markov Process의 Wikipedia 정의는 확률론에서 마르코프연쇄는 메모리를 갖지 않는 이산 시간 확률 과정입니다.

 

• 확률 과정 : 시간이 진행 함에 따라 상태가 확률적으로 변화는 과정

임의의 값(random value)이 이산적인(discrete)한 시간(time interval)마다 값을 생성해내는 것을 의미합니다. 이때 시간(time interval)이 이산적(discrete)이고 현재의 상태(state)가 이전 상태(state)에만 영향을 받는 확률 과정입니다.

 

 

Markov Property(= Memoryless Property)

 

Markov property는 어떤 시간에 특정 상태(state)에 도달하든 그 이전에 어떤 상태(state)를 지나왔든 다음 상태(state)로 갈 확률은 항상 같다는 성질입니다.

t+1시간에 상태(state)에 도달할 확률이 0부터 t시간 까지와 바로 직전 t시간의 상태(state)가 같다는 것을 나타냅니다.

이것은 0부터 t-1시간까지의 정보는 이미 t시간의 상태(state)를 가지고 있다는 가정이 전제되어 있는 것입니다.

 

Markov Chain

 

위의 Markov Chain을 보면 한 상태(state)에서 다른 상태(state)로 이동할 확률의 합은 1을 유지한 상태로 여러 상태(state)들이 연쇄적으로 이어져 있습니다. Sleep 상태(state)는 말단 상태(terminal state)입니다. 말단 상태(terminal state)는 다른 상태(state)로 이동이 없는, 마지막 상태(state)로서 시간이 지나고 나면 말단 상태(terminal state)로 수렴하는 것을 Stationary Distribution 이라고 합니다.

 

State Transition Probability Matrix

 

상태(state)들 간에 이동하는 것을 전이(transition)이라고 하는데 이를 확률로 표현하게 됩니다. 이를 State Transition Probability Matrix라 부르고 수식은 다음과 같습니다.

위 그래프에 나온 transition probability를 아래와 같이 행렬의 형태로 정리한 것을 state transition probability matrix라고 합니다.

State Transition Probability Matrix

Markov Reward Process(MRP)

 

Markov Process에 보상(Reward)의 개념을 추가한 것 입니다. MP에서는 각 상태(state)별 전이(transition 확률이 주어져 있을 뿐이지, 상태(state)에서 다음 상태(state)로 가는 것이 얼마나 가치가 있는지 모릅니다. 

 

• 보상(Reward) : 상태(state) -> 상태(state) 의 가치를 정량화하기 위해 도입한 개념

이렇게 각 상태(state)별로 보상(reward)의 개념이 적용되어 해당 상태(state)가 얼마만큼 가치를 갖게 되는지 보이게 됩니다. 상태(state)를 받아 보상(reward)의 기댓값으로 mapping하는 함수를 ℛs로 표현할 때 다음과 같은 수식으로 표현할 수 있습니다.

이것은 바로 다음시간 t+1에 얻을 수 있는 보상(reward)이기 때문에 immediate reward라고 합니다.

 

Discounting Factor

 

상태(state)의 정확한 가치 구하기 위해 어느 시점에서 보상(reward)을 얻을지도 중요합니다.

'특정 상태(state)에 바로 도달하여 보상(reward)를 얻을 것인가? 아니면 후에 도달하여 보상(reward)를 얻을 것인가?'에 대한 가치 판단이 필요합니다.

 

실생활의 예로 보면 은행의 이자입니다. <현재 가치>에 <이자(현재가치 * 이자율)>을 더하면 <미래 가치>가 됩니다. 하지만 그만큼 시간이 지나고 그에 따른 이자가 붙어야지만 현재 가치와 동일해집니다.

 

• Discounting Factor, γ : <미래가치>를 현재시점으로 보면 <현재가치>보다 적습니다. 이를 수식적으로 반영한 것 (보통 γ는 0과 1사이의 값으로 하여 미래가치를 현재 시점에서의 가치로 변환합니다.)

그러면 우리는 immediate reward 뿐만 아니라 먼 미래에 얻을 수 있는 total reward에 대해서도 고려할 수 있게 됩니다. 

여기서 R은 위에서 언급한 immediate reward들이고, Gt는 각 시점에서의 immediate reward들을 현재 가치로 환산하여 합한 것입니다.

 

Value Function of MRP

 

상태(state)의 가치를 표현하는 함수를 value function 이라고 하며, 어떠한 상태(state)에서 미래에 얻을 수 있는 모든 reward를 더한 것의 기대(expectaion)입니다.

상태(state) s에서 이동 가능한 상태(state)들의 chain을 따라 그 상태(state)들의 보상(reward)에 discounting factor를 적용하여 모두 더한 값이 상태(state) s에서의 가치(V(s))가 됩니다.

 

Markov Decision Process(MDP)

 

MP에서 보상(reward) 개념을 추가한 것이 MRP라고 하면,

MDP는 MRP에 action이라는 개념이 추가되며 policy라는 개념이 등장합니다.

 

• 행동(Action) : 이 전에서 상태(state)가 변한다는 것은 transition probability에 따라 임의로 변했다면,                                      MDP에서는 상태(state)에서 action을 함으로써 상태(state)가 변하게 됩니다.

MP, MRP - MDP

• 정책 or 규칙(Policy) : 상태(state)에서 행동(action)을 mapping하는 함수,                                                                                    해당 상태(state)에서 어떤 행동(action)을 할 지를 정하는 것

강화학습의 목적은 Gt를 최대화 하는 policy를 찾는 것입니다.

 

Transition probability, Policy

 

• Transition probability : 다음 상태(state) s에서 다음 상태(state) s`로 취할 확률(전이할 확률)
• Policy : 상태(state) s에서 행동(action) a를 취할 확률

 

Transition probability, Policy 구분

또한 보상 함수(reward function)도 행동(action)을 추가해주면 됩니다.

 

MDP

 

 

 

참고 자료 : https://sumniya.tistory.com/3

내용이해 도움 자료 : https://setosa.io/ev/markov-chains/