Markov Decision Process (MDP)

 

https://hollygrimm.com/rl_mdp

 

 

 

Definition

 

마르코프 의사결정과정(Markov Decision Process. 이하 MDP)는 꽤 오랜 역사를 가지고 있지만, 실제적으로 인공지능 연구에 활용되기 시작한 것은 1990년대가 조금 지나서라고 합니다. 특히 의사결정과 그 보상에 대한 모델을 제시해 준다는 점에서 강화학습 (Reinforcement Learning)에 활용되고 있습니다.

 

강화학습은 컴퓨터가 환경과 상호작용하면서 받는 보상을 통해 더 나은 결정을 내릴 수 있도록 도와주는 모델입니다. 

어떤 문제를 컴퓨터가 해결하기 위해서는 그 문제가 수학적으로 정의되어 있어야 하는데 MDP가 이 의사 결정 모델의 틀을 제공하여 수학적으로, 다시 말해서 코드화 할 수 있도록 도와줍니다.

 

 

 

컴퓨터는 환경과 상호작용하면서 얻는 보상을 통해 학습을 진행해 나간다. 

 

 

보상은 컴퓨터(Agent)가 환경과 상호작용 하는 과정에서 특정 시점(timestep)에 특정 상태(state)에서 받게 되는 스칼라 값을 의미합니다. 컴퓨터는 이 보상들에 적절한 가중치를 곱하고 더한 값을 통해서 보상을 최대화 하는 방향으로 학습을 하게 되는 것입니다.

 

 

MDP를 조금 수학적으로 접근해 보겠습니다. 이전 포스팅에서 마르코프 체인(Markov Chain, Markov Process)에 대해서 살펴보았습니다. 간단하게 요약하자면, 어떤 모델이 마르코프한 성질(Markov Property)를 가지고 있다는 것은 그 모델의 다음 상태를 결정하기 위해서는 오직 현재 상태만 필요할 뿐, 그 이전 상태는 의미를 가지지 않는다는 것이었습니다.

 

 

어떤 모델이 마르코프한 성질을 가지고 있다는 것은 강화학습에서 굉장히 유용한 정보인데, 이전 상태를 저장하거나, 다시 계산할 필요가 없이 오직 현재의 상태를 가지고만 다음 상태를 계산할 수 있어 연산과 메모리 사용의 효율성을 높여주기 때문입니다.

 

 

" 현재 상태만으로 미래의 보상(Reward)를 최대화할 가능성이 충분하다 "

 

 

MDP는 이 Markov Process에 액션과 보상이라는 개념을 더한 모델입니다. ( MP에 보상이라는 개념을 더한 MRP라는 모델도 있으나, MDP를 설명하는 과정에서 자연스럽게 포함될 것이라 생각해서 따로 언급을 하지는 않겠습니다.

 

 

 

 

Action & Policy

 

Actions은 말 그대로 행동을 의미합니다. 어떤 상태(state)에서 다른 상태로 전이할 때, 기존의 Markov Process에서는 상태 전이 확률(Transition probability)에 의해 임의로 상태가 전이되었지만,  MDP에서는 Action을 취함으로써 이 상태에 변화를 주게 됩니다. 다시 말해서 다음 상태를 명시적으로 결정할 수 있다는 의미입니다. 

 

 

reference : https://sumniya.tistory.com/3

 

 

 

이 액션이 가지고 있는 중요한 성질 중의 하나는 각 상태에 따른 액션들의 집합이 제한될 수 있다는 점입니다. 다시 말해 어떤 상태에 있느냐에 따라 취할 수 있는 액션이 달라진다는 의미인데, 학교에 가서 강의실에 앉아있는 상태와, 집에서 누워있는 상태가 있다고 했을 때, 두 상태에서 우리가 취할 수 있는 행동이 달라지는 것과 비슷합니다. 

이 액션을 적용했을 때, 상태 $x$ 에서 $y$로 전이할 때  $a$라는 행동을 취한 후 이동할 확률을 나타내며, Markov Process와는 다르게, 상태전이 함수(확률을 반환)에 action이 관여하고 있음을 확인할 수 있습니다. 즉, 상태의 이동 조건에 이전 상태와 행해진 액션이 관여하고, 그 액션을 취함으로써 얻어지는 보상을 적용하면서 진행해 가는 것입니다.

 

 

어떤 상태에서 어떤 액션을 취할 수 있는지에 대한 정보를 담고 있는 것을 Policy라고 합니다. 

앞서 언급했듯이, 어느 상태에서든지 모든 액션을 취할 수 없기 때문에, 특정 시점의 특정 상태에서 취할 수 있는 액션들의 집합을 모아놓게 되었고, 일을 Policy라고 정의합니다. 

 

 

 

" TimeStep에서 각각의 State들과, 그 State 들에 매핑된 Action들의 집합 "

 

 

모든 상태에 대해서 특정한 액션 하나하나가 정의된 자료구조의 느낌으로 이해하면 될 것 같습니다. 이 Policy도 내부적으로는 Deterministic Policy, Stochastic Policy의 2가지로 분류할 수 있는데, 이 부분에 대해서는 다음에 다루도록 하겠습니다.

이 Policy의 개념을 가지고 강화학습의 목표를 MDP 모델을 통해 다시 한번 정의하자면 다음과 같습니다.

 

 

" 컴퓨터가 어떤 상태를 만나서 행동을 취하고, 그 행동을 중심으로 가치 평가가 이루어지며, 가장 좋은 의사결정 정책(Policy)에 따른 가치의 합이 가장 큰 의사결정 정책을 찾아내는 것 "

 

 

 

 

Cost (Reward)

 

이처럼 MDP를 통해 강화학습에서 구하고자 하는 목표는 결국 보상을 최대화 하는 Policy(상태에 따른 액션들의 집합)을 찾아내는 것입니다.  보상을 최대화 하기 위해 특정 상태에서 사용할 액션들의 조합을 조정하는 것이라고 말 할 수도 있습니다. 이 Policy를 최적화 하기 위해서는 이 보상(Reward)에 대한 정의가 먼저 이루어져야 할 것입니다. 수식부터 살펴본다면 아래와 같습니다. 

 

$R$은 특정 timestep에서 발생하는 보상을 의미합니다. $G$는 앞으로의 step들에서 얻을 수 있는 모든 보상들을 적절한 discount factor(감가율)를 곱해서 더해준 값으로 특정 timestep에서 발생하는 보상의 총합을 의미합니다. 

다시 말해서 각 Step 마다 보상이 따라오게 되는 것입니다. 

 

discount factor는 바로 다음의 timestep과 저 먼 미래에 발생할 timestep의 중요도를 비교하여 설정합니다. 예를 들어 0이상 1이하로 설정된다면, 먼 미래일 수록 가중치를 적게 둔다는 의미가 되는 것입니다. 

 

 

Value Function

 

정의된 Cost를 가지고 총 보상을 계산하는 함수를 Value Function 이라고 합니다.  Cost의 정의에 따라서 각각의 상태에 따라 보상의 기댓값이 정해지기 때문에, Value Function도 현재 상태에 따라 정의할 수 있게 됩니다. 

 

이 식을 Cost의 정의에 따라서 재귀적으로 풀어서 쓰면 다음과 같이 되는데, 이를 벨만 방정식이라고 합니다. 이 식은 현재 상태의 가치 함수와, 다음 상태의 가치 함수의 관계를 식으로 나타낸 것으로, 재귀적으로 쓰여있기 때문에 최적화에 대한 단서를 준다는 점에서 굉장히 중요한 방정식입니다. (벨만 방정식에 대한 자세한 내용은 다음에 다루도록 하겠습니다.