마르코프 결정 과정 (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) \doteq Pr{S_t=s', R_t = r | S_{t-1}=s, A_{t-1} = a}$$
위 식에서 $p(s',r|s,a)$는 상태 $s$에서 행동 $a$를 했을 때, 다음 상태가 $s'$이고 보상이 $r$일 확률을 의미하여 우변의 확률 표현 $Pr{S_t=s', R_t = r | S_{t-1}=s, A_{t-1} = a}$로 정의된다. 즉, 현재 상태 $S_{t-1}=s$에서 행동 $A_{t-1}=a$를 선택했을 때, 다음 상태가 $S_t=s'$이 되고 보상이 $R_t=r$일 확률을 나타내며, 현재 상태에서 특정 행동을 했을 때 다음 상태와 보상이 확률적으로 결정됨을 의미한다.
그리고 이때, 상태 집합 $\mathcal{S}$와 보상 집합 $\mathcal{R}$이 유한하므로 모든 가능한 다음 상태 $s'$과 보상 $r$에 대해 확률을 합하면 1이 된다. 이는 MDP가 모든 행동에 대해 확률적으로 다음 상태(같은 상태일 수도 있음)로 전이하며, 보상도 항상 주어지는 성질을 가지고 있기 때문이다.
$$\sum_{s'\in \mathcal{S}}\sum_{r\in \mathcal{R}} p(s',r|s,a)=1, \texttt{ for all }s\in \mathcal{S},a\in \mathcal{A}(s)$$
정책
이와 같이 MDP를 통해 에이전트가 상호작용 할 수 있는 환경(Environment)을 정의했다. 이제 이 환경에서 에이전트가 어떻게 행동을 결정하게 되는지를 알아보자. 에이전트는 환경으로부터 상태를 입력받아 다음 행동을 출력한다. 이때 사용되는 함수를 정책(Policy)이라고 한다. 이 정책에는 수많은 정책이 존재하며, 에이전트가 강화학습을 통해 학습해야 하는 것은 이중 최적의 정책을 찾는 것이다. 최적 정책은 Deterministic 하지만, 학습 중에는 Stochastic 하게 진행되어 다양한 상황에 대해 학습할 수 있게 된다.
$$\pi(a|s) = P[A_t=a | S_t=s]$$
위 수식은 시간 $t$에 상태가 $s$일 때 행동 $a$를 선택할 확률을 나타내며, 이를 $\pi$를 이용해서 표기한다. 에이전트는 이를 이용해 MDP로 정의된 환경(정확히는 순차적 행동 결정 문제)과 상호작용하며, 현재 상태에서 앞으로 받게 될 보상 합이 최대가 되도록 행동을 결정하게 된다. 이때 앞으로 받을 것이라 예상되는 보상을 가치함수(Value function)라고 하며, 에이전트는 실제로 받게 된 보상을 토대로 가치함수와 정책을 바꿔나가며 학습하게 된다.
즉, 정책이 주어진 행동을 선택하는 방법이라면, 가치함수는 그 정책을 따를 때 얻을 수 있는 기대 보상을 나타낸다. 이 가치함수에는 할인율(Discount Factor)이라는 개념이 적용되어 해당 보상이 어느 시점만큼 뒤에 올지를 반영하여 보상의 크기를 결정하게 된다. 다음 글에서는 이 내용에 대해서 다뤄보도록 하겠다.