Markov Decision Process

이전 포스트를 요약하자면,

RL은 agent의 action이 미래의 환경, 즉 state distribution과 reward distribution을 함께 바꾸는 sequential decision problem에서 보상을 최대화하도록 학습하는 방법이다. 여기서 "환경이 어떻게 변하는가"가 자연스럽게 질문으로 발전할 수 있다.

이렇게 환경을 formal하게 표현한 것 중 가장 대표적인 것이 Markov Decision Process (MDP)며, 이번 포스트는 MDP에 대해서 알아보고자 한다.

 

우선 MDP를 이해하기 이전에, Markov Property에 대해서 이해해보자.

순수 확률과정 관점에서의 Markov Property의 정의는 다음과 같다:

$$ \text{A state } S_t \text{ is Markov if and only if} P(S_{t+1} | S_t) = P(S_{t+1} | S_1 , ..., S_t). $$

즉 미래는 현재의 상태에만 의존적이며, 그 이전의 상태에 대해서는 영향을 받지 않는다는 것을 의미한다. 이러한 Markov Property가 time step t에 대해서 전부 다 적용되는 경우 Markov Process 또는 Markov Chain이라 한다.

 

RL의 MDP에서는 Markov Process에 action과 reward가 추가된다.

• Action이란 t 시점에서 주어진 state에 대해서 할 수 있는 행동의 집합을 의미하며,
• Reward는 t 시점에서 주어진 state에서 어떠한 action으로 인해 얻을 수 있는 보상의 조건부 기대값을 의미한다. 즉, $R(s,a)  = E(R_{t+1}|S_t = s, A_t=a)$이다.

이제 MDP에 대해서 다룰 수 있다. MDP란 Markov process에 action과 reward가 추가된 형태로, environment dynamics, 즉 미래의 state와 reward는 현재의 state와 action에만 의존한다. 이 Markov Property는 다음과 같이 표현된다:

$$ P(S_{t+1}, R_{t+1} | S_t, A_t) = P(S_{t+1}, R_{t+1} | S_1, A_1, ..., S_t, A_t) $$

즉 과거의 모든 history는 current state-action pair로 표현되며, 이 joint distribution $P(S_{t+1}, R_{t+1} | S_t, A_t)$ 자체가 MDP의 transition dynamics를 정의한다.

 

RL은 sequential decision problem에서 단순히 현재의 보상을 최대화하는 것으로만 정의되지 않는다. 이를 위해서 Goal이라는 것을 추가해주자. Goal $G_t$는 time step t 이후부터 받는 보상 $R_{t+1}, R_{t+2}, ...$의 합을 의미한다. 종료 시점이 존재한다고 가정하면,

$$ G_t = R_{t+1} + R_{t+2} + \cdots + R_{T} $$

가 된다. 그러나 종료 시점이 존재하지 않는 경우를 고려하지 않을 수 없으며, 자연적으로 미래의 가치를 현재의 가치로 계산할 필요성 또한 생긴다. 이를 해결하기 위해 discount factor $\gamma\in[0,1]$를 추가적으로 둔다. 이렇게 goal $G_t$는

$$ G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots $$

으로 정의된다.

 

여기서 $\gamma$ 값이 0에 가까워질수록 현재의 보상에 조금 더 많은 비중을 가하게 되고, 1에 가까워질수록 미래의 보상에 더 많은 고려를 함을 알 수 있다. 또한 reward는 유계한다고 가정하며, 따라서 geometric series에 의해서 $\gamma$가 1보다 작은 경우 수렴이 보장된다.

여기서 $\gamma$가 1이 되는 경우, finite horizon을 다루는 경우 reward의 유계성 안에서는 그 합이 유계한다. 그러나 infinite horizon을 다루는 경우는 실질적으로 핸들링이 불가능하다고 하며, 이 상황에서는 average reward로 objective를 바꾼다고 한다. 즉

$$ \lim_{T\rightarrow\infty}\frac{1}{T}\sum_{t=0}^{T-1}R_t $$

가 된다.

 

이제 environment dynamics가 정의되었으니, 실제로 이 환경 안에서 행동을 하는 주체인 policy $\pi(a|s)$에 대해 알아보자. Policy란 주어진 state $s$에 대해서 가능한 action $a$에 대한 확률분포를 나타내는 함수이다.

여기서 이제 몇가지 추가적으로 이해를 해보자.

• Deterministic Policy란 주어진 state에 대하여 특정한 행동을 할 확률이 1인 policy를 의미한다. 주어진 많은 가능한 action들 중에 반드시 하나만 선택한다.
• Stochastic Policy란 action space 상에서 여러 action이 0보다 큰 확률을 가질 수 있는 확률분포 형태의 policy를 의미한다. 즉 동일한 state에서도 매번 다른 action이 나올 수 있다.

 

MDP라고 해서 policy가 반드시 Markov Property를 따라야 하는 것은 아니다. MDP는 environment transition이 Markov하다는 가정이지, agent의 policy 형태에 대한 제약은 아니다. 따라서 policy는 이전 state, 이전 action 등 history에 기반한 non-Markov 형태일 수도 있다.

다만 environment dynamics가 완전히 알려져 있고 state representation이 이미 Markov한 형태라면, Markov-stationary deterministic policy 중에서도 optimal policy가 항상 존재함이 알려져 있다(즉 non-Markov policy가 더 유리할 수 없다). 하지만 실제 RL에서는 dynamics가 unknown이고 exploration / partial observability / function approximation 등의 요소가 존재하기 때문에 상황에 따라 stochastic policy나 non-Markov policy가 오히려 더 유리하게 작동할 수 있다.