Markov Decision Process

1. 마르코프 프로세스 (Markov Process)

Room 1 $S_0$ 에서 시작해 최종적으로 Treasure $S_n$까지 가는 다양한 루트가 있다고 가정해봅니다. 

 

$S_0$에서 부터 다음방으로 넘어가는 작업은 다음 상태로 이전하는 상태 전이 (State transition)라고 표현됩니다. 그리고 Treasure($S_n$)은 n 번째 방으로 terminate state를 의미합니다. 마르코프 프로세스는 최종적으로 terminate state에 도착하는것을 목표로 합니다. 

 

다시 말해 마르코프 프로세스란 사전에 정의된 어떤 확률분포 (그림에서는 0.4, 0.1 등)에 따라서 상태와 상태를 전이 해 가며 최종적으로 바라는 목적지로 이동하는 일련의 동작 과정을 의미 합니다. 

 

그림에서는 $S_2$ 에서 $S_3$으로 이동할 확률은 0.6 이 되겠네요 Trap으로 이동할 확률은 0.1 입니다. 

 

이 과정을 수식으로 다음과 같이 표현 됩니다. 

State : $S:S = \left\{S_0,S_1,...,S_n \right\}$

State transision probability : $P_{s_{x},s_{x+\alpha}} :P_{s_{x},s_{x+\alpha}} = P\left [ S_{t+1} =s_{x+\alpha}|S_t = s_x  \right ] $

 

위 처럼 상태 집합 $S$는 이동가능한 방의 집합 (상태의 집합)을 의미하고 State transition Probability(상태 전이 확률)은 어떤 상태$S_t$에서 다음 상태 $S_{t+1}$로 이동할 확률입니다. 

 

마르코프 성질 (Markov property)

 

마르코프 프로세스의 모든 상태는 마르코프 성질을 따릅니다. 

 

$P\left [ S_{t+1}|S_t \right ] = P[S_{t+1}|S_0,S_1,S_2,...,S_n]$

 

다시 말해 어떤 상태 $S_t$에서 다음 상태 $S_{t+1}$로의 전이 확률을 계산 하기 위해서는 이 전에 어떤 상태가 선행되었든지 관계 없이 현재의 상태 $S_t$만으로 추정 할 수 있다는 것 입니다. 

 

 

2. 마르코프 리워드 프로세스 (Markov Reward Process)

 

마르코프 프로세스에 각 상태로 전이 될때 마다 적절한 보상이 부여 되는 경우에 Markov reward process 가 됩니다. 

 

위 그림에서와 같이 각 방으로 넘어갈때 마다 서로 다른 reward가 부여 되고 있음을 확인 할 수 있습니다. 

 

그리고 보상의 사전적 의미와 일관되게 각 방을 이동하는 Agent는 이 보상을 최대화 하기위해 노력해야 합니다. 

 

Agent가 획득 할 수 있는 보상은 예상되는 기댓값으로 다음과 같이 표현됩니다. 

 

Reward Function : $R : R = E\left [ R_t|S_t = s \right ]$

 

Reward는 어떤 상태에 도착 했을떄 Env로 부터 Agent가 얻을 수 있는 수치 입니다. 여기서 $E$는 기댓값인데 이전 상태나 과거의 동작 이력에 따라 Agent가 얻을 수 있는 reward가 관련 equation으로 부터 서로 다를 수 있기 때문입니다. 

 

하지만 보상을 그 자체로 받아 들으면 최적의 보상을 받기 어려울 수 있습니다. 

당장에 일부 보상의 손해를 감수 하더라도 추후에 받을 보상의 기댓값이 높은 방향으로 Agent가 움직이기를 바라기 때문입니다. 

 

이에 감쇠율을 통해 추후 보상과 현재 보상사이의 중요도를 결정합니다. 

 

Final reward

최종 (누적) 보상을 최대화 하는 방향으로 Agent가 전이 하기를 바라므로 우리는 보상을 다음과 같이 일반화 할 수 있습니다.

$G_t = \sum_{n=1}^{\infty}\gamma^nR_{t+n}$

여기서 보면 상태의 전이가 반복될 수록 $\gamma$가 지수적으로 늘어나는것을 확인 할 수 있습니다. 

이를 통해 현재의 보상과 미래의 잠재적 보상에 대한 decay를 통해 최종 보상의 기대값을 가늠할 수 있습니다.

 

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

 

이제 Agent가 주체적으로 상태 전이를 결정한다고 생각해 봅시다. 

기존에는 확률에 따라서 알아서 전이 했을텐데 이제는 Agent가 확률에 대한 사전 지식이 있음을 가정하고 action을 수행하는 것으로 바뀝니다. 

$S$는 상태 공간으로 정의 되는 전이 가능한 상태들의 집합입니다. 

$A$는 action 공간으로 정의되는 행동의 집합들입니다. 

$P_a$는 어떤 상태에서 다음 상태로 전이할 확률입니다. 

$R_a$는 상태를 전이 한 후 action에 의해 Agent가 즉각적으로 받을 수 있는 보상입니다.