마르코프 결정 과정 (Markov decision process) 이해하기

마르코프 결정 과정 (Markov decision process) 이해하기

강화학습을 본격적으로 공부하기에 앞서 우리는 순차적 행동 결정 문제(Sequential Decision Making Problem)에 대해 이해해야 할 필요가 있다. 순차적 행동 결정 문제란 에이전트가 장기적인 보상을 최대화하기 위해 환경과 상호작용하며 단계별로 최적의 행동을 선택하는 문제를 의미한다. 그리고 이 순차적 행동 결정 문제는 마르코프 결정 과정 (Markov decision process)으로 수학적으로 모델링되며, 상태(State), 행동(Action), 보상(Reward), 상태 전이 확률(State Transition Probability)을 통해 최적 정책을 찾는 문제로 표현된다.

 

이번 글에서는 이 MDP에 대해서 살펴보도록 하겠다.

 

MDP

MDP는 앞서 언급한 것처럼, 상태(State), 행동(Action), 보상(Reward), 상태 전이 확률(State Transition Probability)로 구성된다. 이 MDP는 순차적으로 행동을 결정하는 문제를 정의한 것으로, 에이전트가 문제를 이해하고 결정을 내릴 수 있도록 한다.

 

이 중에서 상태, 행동, 그리고 보상의 집합이 유한한 경우를 유한 마르코프 결정 과정(Finite MDP)이라고 한다. 이는 강화 학습에서 많이 연구되는 모델로, 특정 상태에서 특정 행동을 했을 때 다음 상태와 보상이 확률적으로 결정되는 과정이다. 즉, 유한한 개수의 상태와 행동을 가지며, 확률적인 전이와 보상 구조를 따르는 MDP를 의미한다.

 

p(s′,r|s,a)≐PrSt=s′,Rt=r|St−1=s,At−1=a

 

위 식에서 p(s′,r|s,a)는 상태 s에서 행동 a를 했을 때, 다음 상태가 s′이고 보상이 r일 확률을 의미하여 우변의 확률 표현 PrSt=s′,Rt=r|St−1=s,At−1=a로 정의된다. 즉, 현재 상태 St−1=s에서 행동 At−1=a를 선택했을 때, 다음 상태가 St=s′이 되고 보상이 Rt=r일 확률을 나타내며, 현재 상태에서 특정 행동을 했을 때 다음 상태와 보상이 확률적으로 결정됨을 의미한다.

 

그리고 이때, 상태 집합 S와 보상 집합 R이 유한하므로 모든 가능한 다음 상태 s′과 보상 r에 대해 확률을 합하면 1이 된다. 이는 MDP가 모든 행동에 대해 확률적으로 다음 상태(같은 상태일 수도 있음)로 전이하며, 보상도 항상 주어지는 성질을 가지고 있기 때문이다.

 

∑s′∈S∑r∈Rp(s′,r|s,a)=1, for all s∈S,a∈A(s)

 

정책

이와 같이 MDP를 통해 에이전트가 상호작용 할 수 있는 환경(Environment)을 정의했다. 이제 이 환경에서 에이전트가 어떻게 행동을 결정하게 되는지를 알아보자. 에이전트는 환경으로부터 상태를 입력받아 다음 행동을 출력한다. 이때 사용되는 함수를 정책(Policy)이라고 한다. 이 정책에는 수많은 정책이 존재하며, 에이전트가 강화학습을 통해 학습해야 하는 것은 이중 최적의 정책을 찾는 것이다. 최적 정책은 Deterministic 하지만, 학습 중에는 Stochastic 하게 진행되어 다양한 상황에 대해 학습할 수 있게 된다.

 

π(a|s)=P[At=a|St=s]

 

위 수식은 시간 t에 상태가 s일 때 행동 a를 선택할 확률을 나타내며, 이를 π를 이용해서 표기한다. 에이전트는 이를 이용해 MDP로 정의된 환경(정확히는 순차적 행동 결정 문제)과 상호작용하며, 현재 상태에서 앞으로 받게 될 보상 합이 최대가 되도록 행동을 결정하게 된다. 이때 앞으로 받을 것이라 예상되는 보상을 가치함수(Value function)라고 하며, 에이전트는 실제로 받게 된 보상을 토대로 가치함수와 정책을 바꿔나가며 학습하게 된다.

 

즉, 정책이 주어진 행동을 선택하는 방법이라면, 가치함수는 그 정책을 따를 때 얻을 수 있는 기대 보상을 나타낸다. 이 가치함수에는 할인율(Discount Factor)이라는 개념이 적용되어 해당 보상이 어느 시점만큼 뒤에 올지를 반영하여 보상의 크기를 결정하게 된다. 다음 글에서는 이 내용에 대해서 다뤄보도록 하겠다.