Markov Decision Process


MDP를 배우기 전에 Markov 하다는 말의 정의와 Markov Chain, Markov Reward Process에 대해 알아보자.


[어떤 S(state), A(action)을 해왔을때(처음 어떠한 상태로부터 현재까지 지속) 현재상태까지 올 확률]


위와 같은 식이 아래와 같은 식으로 표현 된다면 state는 Markov 하다고 할수 있다.


[어떤 S(state), A(action)을 했을때(현재상태 바로 전 상태) 현재상태까지 올 확률]


스타크래프트를 예로 들면 어떤 게임 중간 상황은 그 상황이 일어나기 이전의 모든 상황들에 영향을 받아서 지금의 상황이 된 것이기 때문에,

지금 상황에 이전상황의 모든 정보가 담겨져 있다고 이해할 수 있다.



MDP는 state, action, station probability matrix, reward, discounted factor 로 이루어져 있다.


state 은 agent가 인식하는 자신의 상태를 말한다. 사람으로 치면 '나는 방에 있다' 라고 하면 여기서 '방'이 state이 된다.


action은 agent가 environment에서 특정 state으로 갈때 지시하는 것이다. 어느 쪽으로 움직일때 그것이 action이 되고 agent가 action을 취하면 실재로 오른쪽이나 왼쪽으로 움직이게 된다. 그리고 움직임으로써 state을 변화 시킨다.


State transition probability matrix 는 어떤 action을 취했을 때 state가 결정론적으로 딱 정해지는 것이 아니고 확률적으로 정해지게 되는데, 일종의 noise라고 생각해도 된다.

[state=s, action=a 일 때, state=s' 가 될 확률]


Reward는 agent가 action을 취하면 environment가 그에 따라 주는 보상이다. 게임같은 경우에는 'score', 바둑같은 경우에는 '승/패'가 된다.


[state=s, action=a 일 때, 받는 Reward의 기대값]


어떤 action을 취했을 떄 reward를 받게 됬을 때, 이 때 단순히 받았던 reward를 더해버리면 문제가 생긴다. reward를 각각 0.1, 1을 받는 경우가 있으면 시간이 무한대로 간다면 둘다 최종 reward 값은 무한대가 되므로 두 경우중 어떤 경우가 더 나은 건지 판단할수 없다. 또 한가지는 agent가 어떤 episode를 시작하자마자 1을 받은 경우와, 끝날 때(미래) 1을 받았을 경우, 둘다 최종 reward는 1이기 때문에 어떤 경우가 더 나은 건지를 판단 할 수 없다. 이렇기 때문에 discount factor 라는 개념이 등장한다.


Discount factor는 시간에 따른 reward의 가치를 달라지게 표현하는 방법이다. 보통 discount factor(γ)값은 0하고 1 사이이다. 

이 그림을 보면 이해하기 쉬울 것이다. 한단계씩 시간이 지날때 마다 γ 값의 승수가 늘어난다. 만약 γ 값이 0이라면 미래는 전혀 생각하지 않는 바로 앞 상황만을 보는 reward 값이 나올것이고, γ값이 1이라면 현재의 reward 가치와 미래에 나오는 reward값들의 가치는 같게 판단하므로 상당히 미래지향적이 될 것이다.


Markov Chain

MDP 에서 action과 reward 가 없다고 가정을 하면 state과 state 사이에는 transition matrix(전이 행렬)와 transition probability(전이 확률)가 있다.


이런 그림을 Markov Chain이라고 한다. 각각의 state로 움직일 때의 확률이 나와있고, 이 그림 같은 경우에 시간이 무한대로 흐른다면 모두 'Sleep'으로 수렴하게 될것이다. 그리고 더 이상 변화가 없기 때문에 'stationary distribution' 이라고 말한다. MDP에서는 action을 할 확률과 action을 해서 어떤 state로 갈 확률이 주어지게 된다.


Agent-Environment Interface

agent가 action을 취하고 state를 옮기고 reward를 받고 하면서 environment와 상호작용을 하는 것을 말한다.


agent가 observation을 통해서 자신의 state를 알게되면, 그 state에 맞는 action을 취하게 된다. 학습하지 않았을때는 random한 action을 취한다. 그러면 environment 에서는 agent에게 reward와 다음 state를 알려주게 된다.


Policy

말 그대로 '정책'이다. agent가 어떤 state에 도착하면 action을 결정하는데, 어떤 state에서 어떤 action을 할지 정해주는 것을 policy라고 한다. 결국 강화학습의 목적은 optimal policy(accumulative reward(누적된 보상) = retrun을 최대화 하는 policy)를 찾는 것이다.


[state=s 일 때, action=a를 할 확률]


MDP Graph

아까의 Markov chain 하고는 표현 방법이 다르다. 아까의 Markov chain에서는 state 사이에 transition이 있었지만, MDP Graph에서는 reward로 표현하게 된다.



+ Recent posts