[ch.2] Markov Decision Process

<아래 내용은 '바닥부터 배우는 강화학습' 도서를 읽고 정리한 글입니다.>

 

두번째 내용은 Markov Decision Process 이다 (=MDP)

 

Markov Decision Process를 해결하는 것을 reinforcement learning이라고 할 수 있다.

MDP를 설명하기에 앞서 두 가지 개념을 먼저 설명하고 MDP로 넘어가도록 하겠다.

 

1. Markov Process ≡ (S,P)

앞으로 MP로 줄여서 말하도록 하겠다.

MP는 앞으로 일어날 event들에 대한 순서를 확률로 모델링 하는 것이다.

필요로 하는 원소는 State와 transition probability 이다. (S,P)

여기서 말하는 state는 말 그대로 지금 상황을 나타내는 것이며 transition probability는 'state s에서 s'으로 가게 될 확률' 이라고 설명할 수 있다.

 

아이가 잠에 드는 상황을 Markov Process로 도식화해보자.

아이가 잠에 드는 상황을 MP로 도식화하면 위와 같이 표현된다.

또한 MP로 모델링을 하려면 state가 Markov Property여야 하며 단일 상태 정보로도 충분하도록 state를 잘 구성해야 한다.

여기서 Markov Property 란 다음 state로 가게 될 확률을 계산하려면 현재의 state가 무엇인지만 주어지면 충분한 상황을 말한다.

가령, 체스를 두고 있는 어느 시점t에 사진을 찍어서 사진만 보여주고 체스를 두라고 해도 손쉽게 어떤 수를 둘지 정할 수 있는 상태 즉, 현재 상황에서 해야하는 일과 과거 경기 양상이 어떠했는지의 여부는 아무런 관련이 없는 상태를 'Markov한 상태' 라고 말할 수 있다.

반대로 운전하고 있는 운전자의 상태의 어느 시점t에 사진을 찍어서 사진만 보여주고 운전을 해야 한다고 한다면?

우리는 그 사진만 보고 브레이크를 밟아야 할지, 엑셀을 밟아야할지 전혀 알 수 없다. 이러한 상태는 'Markov하지 않은 상태' 라고 한다.

 

2. Markov Reward Process ≡ (S, P, R, γ )

앞서 설명한 MP에서는 state s 에서 s' 으로 가게될 확률에 대해서는 알려주고 있지만 그게 얼마나 가치있는 행동인지는 알 수 없다. 그렇기때문에 MRP에서는 state의 transition에 따른 reward를 추가해준다.

그렇기에 필요한 원소는 state,transition probability, reward, gamma(discount factor) 가 되겠다.

여기서 gamma가 나타내는건 무엇일까?

일단 gamma 즉, discount factor에 대한 설명을 하기 위해서는 return에 대한 개념 설명을 먼저 해야될 것 같다.

 

앞 장에서 말했듯이 reinforcement learning의 목적은 reward를 최대화 하는 것이다.

좀 더 정확하게 말하자면 reward 값을 모두 합친 return의 값을 최대화 하는 것이라고도 설명할 수 있을 것 같다.

즉, return 이란 t 시점부터 미래에 받을 reward의 합 이다.

Return의 수식

다음 식을 보면 t+1에서의 reward값부터 미래의 reward값까지 더해주는 것을 볼 수 있다. 각각의 reward 앞에 gamma가 곱해져있는 것을 볼 수 있는데

여기서 gamma는 discount factor라고도 하는데 미래에 받을 reward의 값과 당장 얻는 reward중 어떤 것을 더 중요하게 여길 것인지를 나타내는 파라미터 이다. 또한 이 값은 0~1 사이의 숫자이기 때문에 discount factor의 값이 0에 가까울 수록 미래에 얻을 reward의 값도 0에 가까워지기때문에 현재 당장 얻을 수 있는 reward를 중요시 하겠다고 나타낼 수 있다. 이러한 상황을 greedy하다 라고 한다.

 

반대로 discount factor의 값이 1에 가까울 수록 미래에 얻을 reward의 값도 1에 가까워지기때문에 당장 얻을 수 있는 reward 뿐만 아니라 미래에 얻을 수 있는 reward도 중요시하겠다. 라고 나타낼 수 있다.

 

자! 이렇게 해서 MRP에 필요한 원소들에 대해 모두 알아보았다. 

아이가 잠에 드는 상황을 Marvok Reward Process로 도식화해보자.

위 그림을 보면 아까 MP로 도식화한 것과는 다르게 각 state에 따른 reward 값이 추가되어있는 것을 확인할 수 있다.

엇!! 그렇다면 각 state에 따른 reward 값을 알 수 있기에 우린 State Value를 계산할 수 있게 된다.

 

state value function이란 주어진 state로부터 미래에 얻을 return의 expectation 이다.

여기서 왜 return의 expectation을 계산하느냐에 대한 대답은 각각의 state에서 다음 state로 넘어가게될 때 어느 state로 가게될지 아무도 모른다.

위 그림을 예시로 보면 s2의 상황에서 s3로 가게될지 s4로 가게될지는 env의 state transition에 따른 변화이기 때문에 return의 값은 절대적이지 않다. 그렇기 때문에 expectation을 구하는 것 !!!!!

 

그로 인해 MRP의 state value function의 수식은

다음과 같다.

 

3. Markov Decision Process ≡ (S, A, P, R, γ )

자! 드디어 왔다 !! MDP~~!!!

여기에서는 전에 MD, MRP에서는 없었던 action을 하는 주체인 agent가 추가 된다. agent는 각 state마다 action을 취하고 그에 따른 reward를 받게 된다.

필요한 원소는 state, action, transition probability, reward, discount factor 이다.

그런데 ! 여기서 나타내고 있는 transition probability는 앞에 나온 probability와는 살짝 다른 개념이다.

 

MP와 MRP에서는 state s에서 s'으로 가게될 확률 이었다면 MDP에서는 agent가 action을 하기 때문에 state s에서 action a를 하였을 때 state s'으로 가게 될 확률 을 뜻한다.

이쯤에서 policy에 관련한 설명을 추가해보도록 하겠다!

policy란 MDP에서 state s에서 어떤 action을 할 것인지 mapping해주는 함수이다. 그냥 쉽게 말해서 s에서 어떤 a를 취할 것인지 정해주는 걸 policy 라고 하고 수식으로는 𝝅 로 나타낸다. (3.14와는 전혀 관련없음!!)

 

이 그림을 추가하면 조금 더 이해가 쉬워질 듯 하다.

MDP에서의 policy와 transition probability

MDP에서의 state transition을 도식화하면 이렇다.

즉! 일단 policy로 action이 정해진다. 하지만 그 이후로는 env의 transition probability로 인하여 state가 변화된다. 총 두 번의 과정을 통해 state transition이 일어난다.

아무튼 책에서 policy와 transition probability를 헷갈리지 말라고 하였다 ,,,,

 

아이가 잠에 드는 상황을 Markov Decision Process로 도식화해보자.

자. 앞에서 계속 해왔던 아이가 잠에드는 상황을 MDP로 도식화하면 위와 같이 표현된다.

MRP와는 다르게 state가 아닌 action에 대한 reward가 표시되어 있는 것을 확인할 수 있다.

 

그럼 여기서도 우린 state value와 함께 action이 추가 되었기에 action value도 계산할 수 있다.

MDP에서의 state value 계산식

먼저 state value는 다음과 같은 식으로 나타낼 수 있다. 

MDP에서의 action value 계산식

action value 또한 다음과 같은 식으로 나타낼 수 있다.

 

여기까지가 Markov Decision Process에 관한 내용이었다.

개인 기록용이라 뭔가 자세하게는 쓰지 못한 것 같다 .. 그리고 머리로는 알겠는데 글로 표현하려니 너무 어려운 것 같다ㅠㅠ