Markov Decision Process(MDP)

확률 프로세스의 확장

MP(Markov Property) 모델에다가 새로운 개념인 액션(action)을 추가해 보도록 하겠습니다. 이제 각 상태(state)에서 다른 상태(state)로의 이동시, 발생하는 작업 행위를 액션(action)이라고 정의합니다. 그리고 이 때 어떤 상태에 있느냐에 따라 취할 수 있는 액션이 다를 수 있습니다.

 

상태 $x$에서 취할 수 있는 액션을 $A(x)$라 하면 $A(x) \in A$입니다. 하지만 액션 자체가 상태에 종속적인 개념은 아니니 혼동하지 마세요. 특정 상태에서만 사용 가능한 한정된 액션이 정의되어 있고, 이러한 액션을 모두 묶어놓은 전체 액션 집합을 정의할 수 있습니다. 그리고 앞서 정의한 전이 확률 함수에 액션에 대한 속성이 포함되게 됩니다.

 

$P_{xy}^a = p(y | x,a)$

 

이는 상태 $x$상태 $y$로 액션 $a$를 취한 뒤 다른 상태로 이동할 확률을 의미하고, 이때, $x,y \in X$이고 $a \in A(x)$가 됩니다. 따라서 어떤 액션을 취하는가에 따라 전이 확률이 달라질 수 있습니다.

 

이번 글에서 가장 중요한 내용은 바로 이겁니다. 사실 이 액션의 존재 유무가 MP와 MDP를 구분하는 핵심 요소이기 때문이죠.

 

• MP(Markov Process) : $p(s'|s)$ : 상태의 이동 제약 조건에 이전 상태만 영향을 받는다.
• MDP(Markov Decision Process) : $p(s'|s,a)$ : 상태의 이동 제약 조건에 이전 상태와 행해진 액션에 영향을 받는다.

이것이 바로 MP와 MDP의 차이점입니다.

 

그리고 MDP는 액션을 취했을 때 얻어지는 보상(reward)을 정의합니다. 즉, 어떤 상태 $x$에서 액션 $a$를 취했을 때 얻어지는 보상을 $R(x,a)$로 기술합니다. 이 값을 다음과 같이 표기하기도 합니다.(즉, 보상은 실수 값이어야 합니다.)

 

$X$ x $A(x)\rightarrow \mathbb{R}$

 

표기법이 좀 낯설 수도 있는데, 상태 $X$와 이 상태에서 취할 수 있는 액션$A(x)$에 대해 정의된 보상 값이 있다는 이야기입니다. 모든 상태에 대해 가용한 액션마다 보상이 정의되어 있다는 말이죠.

Policy

policy는 MDP에서 가장 자주 등장하는 용어입니다. policy($\pi$라고 표기)란 스텝(step) 시퀀스에서 각각의 상태(state)들과, 그 상태들에 매핑(mapping)된 액션(action)의 집합이다.

 

$\pi = {\pi_t | \pi_t; X \rightarrow A(x), t = {0, 1,...., H - 1}}$

 

policy는 그냥 간단히 생각하여 policy $\pi$를 어떤 특정한 함수, 또는 하나의 자료구조 덩어리라고 생각하면 됩니다. 이제 $\pi_0(x)$라 함은 0번째 스텝(step)에서 임의의 상태 $x$에서 사용되는 액션 $A(x)$를 의미하게 됩니다. 이때 상태 $x$는 임의의 상태를 지칭하는 랜덤 변수로 생각해도 됩니다.

 

위 내용은 policy에 대한 내용을 간략하게 정의한 개념입니다. 어떤 경우에는 $\pi$가 상태(state)들에 매핑된 고정된 액션(action)$a$를 의미하는 것이 아니라, 상태에 매핑된 액션에 대한 확률 함수(probabillity function)로 정의할 수도 있습니다. 즉, 앞서 $[s,a]$에서 $a$가 특정 값이 아닌 $p(a|s)$확률 함수를 가지는 랜덤 변수로 취급될 수 있다는 말입니다. 따라서 특정 상태 $x$에 대한 출력 값은 실수가 아닌 액션에 대한 확률 함수가 반환하게 됩니다. 

 

결론적으로 policy를 크게 두 가지로 나누어 생각할 수 있습니다.

 

• Determinitic policy
• Stochastic policy

Deterministic policy

Deterministic policy 상황에서는 policy 를 $\pi(x) = a$로 정의할 수 있습니다. 임의의 $\pi$를 하나의 함수로 생각하여 특정 $\pi$를 따르는 시퀀스에서 특정 시점 $t$에 대해 상태$x$를 대입하면 그 때에 사용될 정확한 액션을 얻을 수 있습니다. 만약 policy 가 모든 $t$에 대한 내요을 포함하고 있는 경우 식에서 $t$를 생략해도 상관 없습니다. $\pi(x) = a$를 그림으로 나타내면 아래와 같습니다.

위 그림을 나타내는 policy 하나를 정의해봅시다.

$\pi_{sample} = {\pi_0(V) = a, \pi_1(W) = c, \pi_1(Z) = d, \pi_2(P) = a, \pi_2(G) = a}$

즉, 특정 스텝 $t=0$ 에서 사용될 액션이 무조건 정해져 있고 이에 따른 경로가 선택되어 집니다. $t=0$인 상황 하에 상태 $V$에서 사용 가능한 모든 액션 집합은 ${a,b}$이다. 하지만 주어진 policy $\pi_{sample}$에서는 $t=0$ 스텝이고 상태 $V$인 경우 액션 $a$를 선택하도록 기술되어 있습니다.

 

그런데 왜 $\pi_0(W)$같은 것은 정의가 되어 있지 않을까요? 사실 $t=0$에 대해 모든 상태에 대해 사용될 액션이 $\pi$에 다 정의되어 있어야 합니다. 즉, 임의의 스텝 $t$에서 모든 상태 $x$에 대한 액션 값이 정의되어 있어야 한다는 의미입니다. 하지만 해당 시점(즉, 여기서는 $t=0$ 일 때 절대 도달할 수 없는 상태입니다. 따라서 생략이 가능합니다.)

Stochastic policy

stochastic policy 모델에서는 $\pi$를 사용하는 형태가 조금 다릅니다. deterministic policy 에서는 $\pi$자체를 함수 식처럼 사용하게 되는데, 여기서는 추가로 이 식을 조건 확률식처럼 표기하게 됩니다. 즉, 액션도 확률적으로 취하게 됩니다. 이로 인해 $\pi$는 조건부 확률 함수가 됩니다.

$\pi(a|x) = p(A = a | X = x)$,     ∀$a \in A(x)$, ∀$x\ in X$

 

또는 다음과 같이 표기하기도 합니다. 출력 결과로 액션에 대한 확률 함수가 반환된다고 생각하면 쉽습니다.

 

$\pi(a,x) = p(A = a | X = x)$

 

이 모델은 특정 상태에서 선택될 액션이 확률 함수로 주어집니다. 따라서 determinisic policy 모델에 비해 좀 더 복잡한 형태를 취합니다.

$\pi = {\pi_0(v) = {a,b}, \pi_1(w) = c, \pi_1(z) = d, \pi_2(P) = a, \pi_2(G) = a}$

사실 주어지는 문제 혹은 도메인에 따라 어떤 모델을 사용할지 결정되는 경우가 많습니다. 하지만 일단 여기서는 deterministic policy 모델만을 염두해 두고 정리를 진행하도록 하겠습니다.

MDP

MDP는 state, action, station probability matrix, reward, discounted factor 로 이루어져 있습니다.

 

state는 agent가 인식하는 자신의 상태를 말합니다. 체스로 예를 들어 보면 말이 놓인 '위치'를 생각해 볼 수 있습니다.

 

action은 agent가 environment에서 특정 state으로 갈 때 지시하는 것입니다. 어느 쪽으로 움직일 때 그것이 action이 되고 agent가 action을 취하면 실제로 상하좌우로 이동하게 됩니다. 그리고 이동함으로써 state를 변화 시키는 겁니다.

 

State transition probability matrix 는 어떤 action을 취했을 때 state가 결론적으로 닥 정해지는 것이 아니고 확률적으로 정해지게 되는데, 일종의 noise라고 생각해도 됩니다. 

 

Reward는 agent가 action을 취하면 environment가 그에 따라 주는 보상이다. 체스를 예로 들면 승/패 가 됩니다.

 

이제 $X_t^\pi$를 정의해 봅시다. $X_t^\pi$는 랜덤 변수로 상태 $X$가 특정 스텝 $t$에서 policy를 따르는, 상태 $X$대한 랜덤 변수로 취급됩니다. MDP에서 중요한 것중 하나는 비용(reward)입니다. 여기서 어떤 action을 취했을 때 reward를 받게 됐을 때, 단순히 reward를 더해버리면 문제가 생깁니다. reward를 각각 0,1,1,1을 받는 경우가 있다면 최종 reward 값은 무한대가 되어버리므로 어떠한 경우가 더 나은지 알 수 없게 된다. 또 한가지는 agent가 어떤 episode를 시작하자마자 1을 받은 경우와 끝날 때(미래) 1을 받았을 경우, 둘다 최종 reward는 1이기 때문에 어떤 경우가 더 아능 건지를 판단 할 수가 없게 됩니다. 이러한 문제를 해결하기 위해 discount factor라는 개념이 등장하게 됩니다.

이 그림을 보면 이해하기 쉬울 것입니다. 한 단계씩 시간이 지날 때마다 $\gamma$값이 승수가 늘어납니다. 만약 $\gamma$값이 0이라면 미래는 전혀 생각하지 않는 바로 옆 상황만을 보는 reward 값이 나올 것이고, $\gamma$값이 1이라면 현재의 reward 가치와 미래에 나오는 reward값들의 가치는 같게 판단하므로 상당히 미래 지향적이 될 것입니다.

 

사전 정의된 policy를 가진 프로세스에서 $H$스텝(step) 이후에 발생된 비용을 계산하면 아래와 같이 됩니다. 물론 여기에 discount factor가 적용되어 있습니다.

 

$\sum_{r=0}^{H-1}r_tR(X_t^\pi, \pi_1(X_t^\pi))$

 

위 식을 글로 풀어써보면, 어떤 policy를 따르는 프로세스에 각 단계의 상태에서의 액션을 수행 뒤 얻어지는 보상의 총합을 계산하자는 뜻입니다. 그리고 앞서 상태 사이의 전이 확률도 $p(y|x,a)$와 같은 형태로 표현했었는데 아래와 같은 표기법으로 다시 작성할 수도 있습니다.

 

$p(X_{i+1}^\pi = y|X_t^\pi = x, A = \pi_t(X_t^\pi)) p_{xy}^{\pi^t(x)}$

 

사실 policy는 순차적으로 어떤 상태를 방문하여 특정 액션을 선택하는 방식처럼 보이기도 합니다.

 

$h = s(1)a(1)s(2)a(2)...$

 

위와 같이 실제 프로세스가 진행되어 얻어진 시퀀스를 $History$라고 합니다. 

MDP Graph

MDP Graph는 Markov Chain 하고는 표현 방법이 다릅니다. Markov chain에서는 state사이에 transition이 있었지만, MDP Graph에서는 reward로 표현하게 됩니다.

---

출처

https://passi0n.tistory.com/80

https://norman3.github.io/rl/docs/chapter04

 

이 글은 PC에 최적화 된 글입니다. 모바일은 [여기]에서 확인해 주세요.