Markov Decision Processes(MDP)란?

1. Stochastic(random) Process

Stochastic Process는 time(St)로 Index되어지는 random variables들의 collection이라고 하고 주로 환경을 설명하기 위해 사용되는 개념입니다. 한글로 하면 시간의 흐름에 따라 변하는 확률 변수들의 모음이라고 할 수 있습니다. 확률 변수들은 시간에 따라 변화하며 각각의 상태나 상황에서 다양한 결과를 생성할 수 있습니다. 예를들어 환경이 Stochastic Process인 경우, 로봇의 움직임이나 주변 조건이 항상 동일하지 않습니다. 따라서 로봇이 같은 명령을 받더라도 바람이나 센서등에 의해 로봇의 움직임이 랜덤하게 변할 수 있습니다. 

 

2. State Transition Probability Matrix

state $ s $와 successor state $ s` $이 존재할 때 state transition probability는 다음과 같이 정의됩니다.

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

풀어서 써보자면 t시점의 state $ S_t $에서 t+1시점의 state $ S_{t+1} $로 전이(transition)될 확률을 뜻합니다. 이런 모든 state에 대한 transition probability를 모아놓은 matrix를 State Transition Matrix라고 합니다. 위의 그림에서는 $ S_0 $에서 $ S_1 $로 transition 될 확률 0.4, 반대의 경우 0.1 등등을 모두 모아놓은 matrix라고 보면 되겠습니다.

각각의 row, 즉 하나의 state에 대해서 해당 state에서 다른 state로의 transition 확률을 다 더하면 1의 확률을 갖게됩니다.

• from $ S0 $ to $ S1 $ = 0.4
• from $ S0 $ to $ S2 $ = 0.6
• 더하면 총 1의 확률을 갖는다.

3. Markov Property

MDP의 중요한 개념중 하나는 Markov Property입니다. 마르코프 성질이라고도 하며 현재의 상태는 과거와는 독립이고, 바로 이전의 상태에서만 영향을 받는다고 가정합니다. 수식으로 보자면

$$ \mathbb{P}[S_{t+1}|S_t] = \mathbb{P}[S_{t+1}|S_1,S_2,...,S_t] $$

입니다.

 

4. Markov Process(chain)

Markov Process는 Stochastic Process 중에 특별히 Markov Property를 가정한 process입니다. 따라서 Markov process는 memoryless random process라고 할 수 있습니다. 

 

Markov Process는 두가지 속성으로 표현 할 수 있습니다.

$$ MP(S,P) $$

• S : Finite set of states (유한한 state의 집합)
• P : State transition probability matrix // $ P_{ss'} =  \mathbb{P}[S_{t+1} = s'|S_t = s] $

5. Markov Reward Processes

Markov Reward Process는 Markov Process에 values 혹은 rewards가 추가된 process입니다.

 

Markov Reward Process는 4가지 속성이 있습니다.

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

 

• S : Finite set of states (유한한 state의 집합)
• P : State transition probability matrix // $ P_{ss'} =  \mathbb{P}[S_{t+1} = s'|S_t = s] $
• R : reward 함수 // $ R_s = E[R_{t+1} | S_t = s ] $
• $ \gamma $ : 0과 1 사이의 discount factor (감쇠인자) $ \gamma \in [0,1] $

 

6. Episode and Sampling

Episode는 process의 스토리입니다. process의 시작부터 종료 state까지를 episode라고 합니다.

$$ s_0,R_0,s_1,R_1...,s_T,R_T $$

 

Sampling은 episode들 중에서 하나를 가져오는 것을 말합니다.

7. Return

강화학습의 목적은 'Return'을 maximize하는 것이지 'Reward'를 maximize하는 것이 아닙니다.

Return $ G_t $는 시간 t에 대하여 앞에서 나온 discount factor를 통해 t 시점 이후의 total reward를 discount한 값입니다.

$$ G_t = R_{t+1} + \gamma R_{t+2} + ... = \sum_{k=0}^{\infty }\gamma^kR_{t+k+1} $$

• $ \gamma $ 가 0에 가까우면 가까운 미래를 더 반영한다.
• $ \gamma $ 가 1에 가까우면 먼 미래 까지 반영한다.

 

 

8. Markov Decision Process 

드디어 나온 MDP는 위에서 나온 Markov Reward Process에 action이 추가된 것을 말합니다.

 

Markov Decision Process는 5가지 속성이 있습니다.

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

 

• S : Finite set of states (유한한 state의 집합)
• A : Finite set of actions (유한한 action의 집합) // action은 agent의 선택된 행동을 말한다.
• P : State transition probability matrix // $ P_{ss'} =  \mathbb{P}[S_{t+1} = s'|S_t = s] $
• R : reward 함수 // $ R_s = E[R_{t+1} | S_t = s ] $
• $ \gamma $ : 0과 1 사이의 discount factor (감쇠인자) $ \gamma \in [0,1] $

 

 

9. State Value Function

state value function v(s)는 state s의 long-term value를 말합니다.

$$ v(s) = E[G_t|S_t=s] $$

• v(s)는 시점 t의 state에서 return의 기댓값
• 기댓값이기 때문에 sample을 많이 뽑아서 계산해야 한다.

10. MDP는 결국?

1. MDP는 $ MDP(S,A,P,R,\gamma) $를 설명할 수 있어야 합니다.
2. 거의 모든 RL 문제는 MDP로 공식화 할 수 있습니다.

11. Policy

Policy는 주어진 상태에서 agent가 어떤 행동을 취할지 알려주는 지침서라고 할 수 있습니다.

 

만약 주어진 상태에서 무조건 어떤 행동을 취해야 한다면 Deterministic 한 policy라고 합니다.

$$ \pi(s) = a $$

그렇지 않고 확률적으로 행동을 취한다면 stochastic policy라고 합니다.

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

해석하자면 t시점의 state s에서 action a를 할 확률을 뜻합니다.

• policy는 agent의 모든 행동을 정의해야한다.
• MDP정책은 history가 아니라 현재 상태에 의해 결정되어야 한다.
• Policy는 stationary해야 한다.