마르코프 프로세스(Markov Process, MP)

마르코프 프로세스는 마르코프 특성(markov property)을 지니는 이산 시간 확률 과정입니다.

위의 마르코프 프로세스 모델은 6개의 상태와 각 상태에서 다음 상태로 전이될 확률을 가지고 있습니다. 또한 시간의 흐름에 따라 상태가 전이됩니다. 그 과정을 살펴보면 Pause 에서 시작하여 Stage 1 로 상태가 전이될 확률은 0.7, 가만히 있을 확률은 0.3입니다. 여러 과정을 거쳐 Stage 2 에서 0.7의 확률로 Win 으로 전이되고 1.0의 확률로 종료 상태(terminal state)인 Stop 에 도달하여 프로세스는 종료됩니다.

마르코프 프로세스는 상태의 집합 $S$ 와 전이 확률 행렬 $P$ 로 정의할 수 있습니다.

$MP \equiv (S,P)$

상태의 집합 $S$ 는 유한한 상태들의 집합입니다.

$S = \{s_0, s_1, s_2, \dots\}$ 

전이 확률 행렬 $P$ 는 다음과 같습니다.

$P_{ss'} = \mathbb{P}[S_{t+1} = s' | S_t = s]$

어떤 상태 $s$ 에서 다음 상태 $s'$ 로 변화하는 것을 상태 전이(state transition)라고 하며 그 확률을 전이 확률(transition probability)이라고 합니다. 또한 어떤 상태에서 다음 상태 전이 확률들의 합은 100% 입니다.

마르코프 프로세스의 상태 집합 $S$ 에 대한 전이 확률 행렬(transition probability maxtrix)은 다음과 같습니다. 

마르코프 특성(Markov Property)

마르코프 특성은 다음과 같이 정의됩니다.

$\mathbb{P}[s_{t+1}|s_t]=\mathbb{P}[s_{t+1}|s_1, s_2, ..., s_t]$

미래는 현재에 의해서만 결정된다는 의미로 마르코프 프로세스에서 다음 상태가 $s_{t+1}$ 이 될 확률은 현재 상태 $s_t$ 로 충분하며 $s_t$ 이전에 방문했던 상태 $s_1, s_2, ...$ 에 대한 정보는 다음 상태 $s_{t+1}$ 에 도달하는 데 영향을 주지 못한다는 것입니다.

동전 던지기를 예로 들어보면 동전을 던져 앞면이 5번 연속으로 나왔다고 가정합니다. 다음에 동전을 던지면 뒷면이 나올 확률이 높을 것 같지만 항상 뒷면이 나올 확률은 50% 입니다.

이것과 같이 마르코프 특성을 만족하는 상태를 마르코프한 상태라고 합니다.

이번에는 반대의 예를 들어봅니다. 운전을 하는 환경에서 운전자 시점의 사진 한장이 주어집니다. 그런데 현재 상태에서 사진 한장의 정보로는 차가 앞으로 가는지 뒤로 가는지 알 수 없습니다. 이 같은 상황은 마르코프하지 않은 상태로 볼 수 있습니다. 이전 사진들의 정보도 같이 주어진다면 조금 더 마르코프한 상태로 만들 수 있을 것입니다.

마르코프 보상 프로세스(Markov Reward Process, MRP)

마르코프 프로세스에 보상 함수 $R$ 과 감쇠 $\gamma$ 라는 개념이 추가되면 마르코프 보상 프로세스를 정의 할 수 있습니다. 

$MRP \equiv (S,P,R,\gamma)$

마르코프 보상 프로세스 모델은 각 상태에 도달하게되면 보상을 받습니다.

보상 함수 $R$ 은 어떤 상태 $s$ 에 도달했을 때 받는 보상으로 정의합니다.

$R=\mathbb{E}[R_t|S_t=s]$

MRP 에서는 연속된 상태 전이 과정을 통해 다음과 같은 궤적(trajectory)이 만들어 질 것입니다.

$s_t, R_t, s_{t+1}, R_{t+1}, s_{t+2}, R_{t+2}, \dots, s_T, R_T $

이러한 시점 $t, \dots, T$ 의 과정을 에피소드(episode)라고 하며 환경에 따라 종료되는 에피소드를 다루는 작업을 에피소딕 작업(episodic task), 주식과 같이 에피소드가 종료되지 않는 경우는 연속적인 작업(continuous task)이라고 합니다.

시점 $t$ 이후에 연속된 보상을 $R_{t+1}, R_{t+2}, R_{t+3}, \dots$ 으로 나열하고 이를 이용해서 누적 보상을 나타내는 리턴(return)을 정의하면 다음과 같습니다.

$G_t \doteq R_{t+1} + R_{t+2} + R_{t+3} + \cdots + R_T $ 

위의 식은 그대로 사용하기에는 무리가 있습니다. continuous task 인 경우 값이 계속 더해지면 무한히 커지는 문제도 있고 미래에 대한 불확실성과 같은 요소를 표현할 수 있는 감쇠(discounting)라는 개념이 나오게 됩니다. 이를 이용하여 다시 한번 정의하면 다음과 같습니다.

$G_t \doteq R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots = \displaystyle \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$

감쇠 인자는 $0<\gamma<1$ 의 범위를 가지며 보상은 1로 하여 식을 전개하면 감쇠된 리턴값은 유한하다는 것을 알 수 있습니다.

$G_t = \displaystyle \sum_{k=0}^\infty \gamma^k = { 1 \over 1-\gamma }$

감쇠 인자 $\gamma$ 는 $0<\gamma<1$ 범위를 가지며 현재 상태에서 미래에 얻을 보상에 대해 얼마나 더 중요하게 여길 것인지를 나타내는 파라미터입니다.

또한 리턴을 이용해 상태에 대한 가치(state value)를 정의할 수 있으며 이를 함수로 표현한 것을 상태 가치 함수(state value function)라고 합니다. 상태 가치 함수는 입력으로 상태를 넣으면 가치를 출력해주는 함수이며 상태 $s$ 에서 시점 $t$ 이후로 얻는 리턴의 기댓값으로 정의됩니다.

$v(s)=\mathbb{E}[G_t|S_t=s]$

상태 $s$ 의 가치는 상태 $s$ 에서부터 여러 경로의 에피소드를 통해 나온 리턴들의 합으로 구할 수 있는 것입니다.

마르코프 결정 프로세스(Markov Decision Process)

앞에서 알아본 MP 와 MRP 에서는 시간의 흐름에 따라 상태 전이가 자동으로 이루어 집니다.

MRP 에서 행동의 집합 $A$ 의 개념이 추가되면 MDP 를 정의할 수 있습니다.

$MDP \equiv (S,A,P,R,\gamma)$

MDP 모델은 행동이 추가되었기 때문에 행동을 선택하며 학습을 하는 주체인 에이전트를 포함할 수 있게 됩니다. 에이전트는 각 상태마다 행동을 취하고 그 행동에 의해 상태가 전이되며 보상을 받습니다.

MRP 와 비교하여 추가된 행동으로 인해 전이 확률은 $P_{ss'}^a$ 로 나타내며 현재 상태 $s$ 에서 에이전트가 행동 $a$ 를 취하여 다음 상태 $s'$ 로 전이될 확률을 나타냅니다. 또한 보상 함수는 $R_s^a$ 로 나타내어 상태 $s$ 에서 행동 $a$ 를 취해서 받는 보상으로 정의합니다. 

$P_{ss'}^a = \mathbb{P}[S_{t+1} = s' | S_t = s, A_t = a]$

$R_s^a = \mathbb{E}[R_{t+1} | S_t = s, A_t = a]$

강화 학습의 목적은 누적 보상을 최대화하는 것이고 각 상태마다 누적 보상이 최대가 되는 방향으로 행동을 선택해야 할 것입니다. 각 상태에 따라 행동을 선택하는 것을 정책(policy)이라는 개념을 통해 나타낼 수 있습니다. 

$\pi(a|s)=\mathbb{P}[A_t=a|S_t=s]$

이는 입력으로 상태 $s$ 와 행동 $a$ 를 넣으면 $a$ 를 선택할 확률을 출력하는 함수입니다.

상태와 행동은 MDP 모델에 정의되어 있는 정보지만 정책은 에이전트에 정의되어 있는 것으로 학습을 통해 개선되어야 하는 것입니다. 

정책을 개선(improvement)하기 위해서는 먼저 평가(evaluation)를 해야합니다.

그렇다면 정책을 어떻게 평가할 수 있을까요? 

바로 상태 가치 함수를 통해 정책을 평가할 수 있습니다.

$v_\pi(s)=\mathbb{E}_\pi[G_t|S_t=s]$

상태 $s$ 에서 정책 $\pi$ 에 의해 얻는 리턴의 기댓값입니다. MRP 에서 알아본 가치 함수 $v(s)$ 와는 다른 것입니다. $v(s)$ 는 MRP 에 정의되어 있는 전이 확률에 의해 발생되는 여러 에피소드의 리턴을 이용하여 기댓값을 구하지만 $v_\pi(s)$ 는 행동 정책 $\pi$ 에 의해서 얻은 리턴들의 기댓값을 구하는 것입니다. 따라서 가치 함수 $v_\pi(s)$ 는 정책 $\pi$ 에 의존적인 것으로 $v_\pi(s)$ 를 구하는 것으로 정책을 평가할 수 있는 것입니다. 단순하게 상태 $s$ 에서 상태 가치가 $v_{\pi_1}(s) < v_{\pi_2}(s)$ 라면 정책을 $\pi_2$ 로 수정하는 것으로 정책이 개선되었다고 할 수 있는 것입니다.

또한 행동에 대한 가치 함수인 상태 행동 가치 함수(state action value function)를 정의할 수 있습니다.

$q_\pi(s,a)=\mathbb{E}[G_t|S_t=s,A_t=a]$

이는 정책 $\pi$ 에 의한 상태 $s$ 에서 행동 $a$ 에 대한 리턴의 기댓값으로 각 상태에서 취할 수 있는 행동에 대한 가치를 계산하는 것입니다. 이를 통해 얻을 수 있는 이점은 특정 상태 $s$ 에서 행동 가치가 높은 행동 $a$ 를 선택한다면 최선의 선택일 것입니다.