[RL] MDP(Markov Decision Process)

이 포스팅은 학교수업과 노승은 저자의 "바닥부터 배우는 강화 학습"을 바탕으로 정리했다.

 

학교 수업또한 저자 책을 바탕으로 수업을 받기 때문에 강의자료(요약에 가까운)와 책을 보며 정리했다.

개념

---

MDP는 마르코프 결정 프로세스의 약자로 의사결정 과정을 모델링하는 수학적인 틀을 제공한다. 

 

MDP의 Agent와 Reward를 통하여 마지막에 가장 큰 보상을 위한 상태를 찾아나선다.

 

우선 MDP를 알기위해 MP와 MRP에 대해 설명하겠다.

 

MP (Markov Process)

---

 

$$MP ≡ (S, P)$$

flow chart를 좀 형편없이 그린 감이 없지않아 있지만...

 

설명하자면 시작부터 도착까지 확률 P만 존재할 때 위의 그림과 같이 표현할 수 있다.

 

여기서 P를 전이확률이라고 하며, 이 전이확률을 행렬로 나타낼 수 있다.

전이확률행렬

전이확률행렬은 시작 지점부터 도착까지 모든 상태에 존재하는

 

한 "상태"에서 다른 "상태"로 갈 때의 확률을 행렬로 나타낸 것이다.

 

	시작	상태A	상태B	상태C	상태D	도착
시작		0.4	0.6
상태A	0.4
상태B	0.6
상태C		0.55	0.7			1
상태D		0.45	0.3			1
도착				1	1

 

상태A에서 C갈 확률도 있지만 위의 표는 상태 s에서 s'으로 한 번 갈 때의 확률임을 명심해야한다.

 

마르코프 성질

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

다음 상태 $S_{t+1}$을 계산하려면 현재 상태 $S_t$만 주어지면 충분하다.

이전 상태들$(S_1, S_2, … , S_{t−1})$은 영향을 주지 못한다는 성질을 가지고 있다.

 

 

MRP(Markov Reward Process)

---

자, 이제 위에 정리했던 전이 확률에 Reward라는 개념이 생겨난다.

 

말 그대로 어떤 상태에 도착하면 Reward가 주어진다.

 

게임으로 치면 s→s' 갈때마다 reward가 쌓이는 것을 롤의 랭크점수로 생각해도 될 거 같다.

 

다만 실제 MRP에서 계산과정은 약간 어려울 수 있다.

 

시작에서 도착지점에 갈때까지 reward라는 포켓주머니를 챙겨야 한다.

 

나라는 객체가 있다고 가정할 때, 나는 보상이 높은 곳으로 가기를 원할 것이다.

 

그러기 위해서는 어느 경로에 가느냐에 따라 보상의 누적정보가 있어야 할 것이다.

 

$$MRP ≡ (S, P, R, γ)$$

 

$S$ : $MP$에서의 상태집합과 동일하다.

 

$P$ : $MP$에서의 전이확률과 동일하다.

 

$R = E[R_{t+1}|S_t=s] $  : 어떤 상태에 도착했을 때 받게 되는 보상이다. 

 

다만 특이한 점은 누적된 합이긴 하지만 기댓값이 적용된 누적된 합이다.

 

기댓값을 사용하는 이유는 확률적 요소에 의해 다음 상태가 정해지므로 𝑡 시점 기준으로 

 

다음 도달 상태들이 매번 달라질 수 있고, 그에 대한 보상이 달라지므로

 

보상의 합인 리턴값이 매번 바뀌기 때문이다.

 

$γ$:  감쇠인자라고 하는데 만약 상태가 많아지면 보상의 누적합도 커지기 때문에 

 

얻는 보상에 $γ$를 곱해주어서 어느정도 숫자의 크기를 낮춰주는 것이다.

 

$γ$ = 0  미래의 보상은 모두 0으로 현재의 보상만 생각한다.

0 < $γ$ < 1 여러 번 곱하면 0에 가까워 진다. 현재의 보상이 100 스텝 후 받는 보상보다 훨씬 더 큰 값이 된다.
$γ$  = 1: 현재와 미래의 보상이 동등, 장기적인 시야를 갖는 보상이다.

 

상태 s에서 마지막 에피소드까지 보상의 누적합은 다음과 같이 나타낼 수 있다.

 

$G_{t} = R_{t+1} + γR_{t+2} + γ^2R_{t+2} ...$

 

상태A에 있다는 가정하에 도착까지 가는 에피소드들의 보상관계에 대한 값을 G라고 생각하면된다.

 

이전까지의 누적 기댓값은 R인 거고 앞으로의 보상을 받게 될 값을 G라고 생각하는 게 좋다.

상태 가치 함수(State Value Function)

결론적으로 MRP에서 얻을 수 있는 건 상태 가치 함수이다.

 

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

 

상태 s에서 마지막 까지가는 에피소드는 하나만이 아니라 여러 경로가 존재한다.

 

상태 s에서 가치함수는 모든 마지막 에피소드가 끝날때의 $G_t$를 더해 기댓값을 구하는 것이다.

 

MRP 개념에서 상태 s에 대한 보상이 주어지면 상태에 대한 가치 v를 얻을 수 있는 것이다.

 

 

 MDP(Markov Desion Process)

---

대망의 MDP이다. MDP에서는 Agent라는 개념이 도입된다.

 

Agent는 도착 지점에 가고 있는 '나'라고 생각하면 된다.

 

나는 길을 가면서 바닥에 떨어진 동전을 줍거나 신호등에 멈춰 설 수도 있다.

 

그러한 행동들을 action이라고 한다.

 

각각의 확률과 보상과 에이전트에 대한 확률값은 생략했다.

 

전체적인 느낌은 위와 같고 아래상황만 우선 고려해보자.

Agent가 위와 같이 어떤 상태 s에 가기전의 action을 하면 그에 따라 상태 s에 가는 것에 대한 확률이 달라진다.

 

즉,

a1 → s1 = 0.6 x 0.4 = 0.24

a1 → s2 = 0.6 x 0.6 = 0.36

a2 → s1 = 0.4 x 0.7 = 0.28

a2 → s2 = 0.4 x 0.3 = 0.12

 

내가 이상황에서 만큼은 큰 보상을 원한다면 걸어간 후 카페에 들르는 게 좋을 것이다.

 

그러면 a2이후 카페에 들르는 게 보상이 더 좋은데 그다음 마지막 도착지까지 최고의 보상을 얻으려면 어떻게 해야할까?

 

s가 많아지면 경우의 수가 너무 많아진다.

 

따라서 action 확률을 조절함으로써 최적의 보상을 얻을 수 있도록 학습할 수 있다.

 

여기서 초록색으로 표시된 확률($π$)이 action이고 함수에 따라 조절할 수 있다.

 

다만, 전이 확률 ($P$)은 바꿀 수 없는 값이다.

정책 함수(policy function)

$π(a|s) = P[A_t=a|S_t=s]$

 

각 상태에서 어떤 액션을 취할지 선택하는 함수이다.

 

강화학습을 통해 $π$은 계속 교정된다.

상태 가치 함수(state value function)

$v(s) = E_ π[R_{t+1} + γR_{t+2} + γ^2R_{t+2} ...|S_t=s] = E_π[G_t|S_t=s]$

 

위에서 설명한 것과 같지만 여기서는 MDP에서의 상태가치임으로 기댓값 E에 $π$표시가 추가되었다.

액션 가치 함수(state-action value function)

$q_π(s,a) = E_π[G_t|S_t=s, A_t=a]$

 

특정 정책 $π$를 따랐을 때,

 

어떤 상태 s에서 특정 액션 a를 취하고 그 이후에 얻을 수 있는 기대 리턴을 나타낸다.

 

하나의 특정 액션을 취했을 때의 가치를 판별하며,

 

그 액션을 취한 후 정책 $π$에 따라 이후의 행동을 취할 때 얻게 될 보상의 기대값을 의미한다.

 

상태 가치 함수와 차이점이 있다면...

 

상태가치함수는 $π$를 따랐을 때 어떤 상태 s에서 시작하여 얻을 수 잇는 누적 보상을 나타낸다.

 

그러니까 모든 가능한 액션들을 고려는 하지만 특정 정책에 따라 액션들이 선택되는 방식인거다.

 

결론적으론, 최적 정책 $π$와 최적가치 v를 찾을 때 MDP가 풀렸다고 말할 수 있다.

Prediction

정책 𝜋가 주어졌을 때 각 상태의 밸류를 평가하는 문제이다.

 Control

최적 정책 𝜋 를 찾는 문제, 모든 상태에 대해 밸류가 가장 큰 정책 𝜋

 

마르코프 결정 프로세스(MDP)에서 최적의 결정적 정책이 하나 이상 존재한다는 사실이 수학적으로 증명되어 d있다.

Grid World 예제

---

여기서 상태가치함수가 어떻게 다르게 나타나는지 비교해볼 것이다.

$v(s) = E_ π[R_{t+1} + γR_{t+2} + γ^2R_{t+2} ...|S_t=s] = E_π[G_t|S_t=s]$

 

보상:

10 (16일때)

-1 (16제외 나머지)

감마: $γ=1$ 

정책: 균등

 

이라고 할때

 

정책 $π$에 대한 상태가치함수는 다음과 같다.

 

$v_{π1} = 2.5 + 4.5 = 7$

11  → 14 → 15 → 16 =  $\frac{1}{2} * (-1) + (-1) + (-1) + (5) = 2.5$ 

11 → 12 →16 = $\frac{1}{2} * (-1) + (5) = 4.5$

 

$v_{π2} = 4.5 + 4.5 = 9$

11  → 15 → 16 =  $\frac{1}{2} * (-1) + (5) = 4.5$ 

11 → 12 →16 = $\frac{1}{2} * (-1) + (5) = 4.5$