MDP

MDP

Markov Decision Process

순차적 행동 결정 문제

MDP의 구성 요소

1. 상태(state)

2. 행동(action)

3. 보상(reward)

4. 정책(Policy)

상태

 S는 에이전트가 관찰 가능한 상태의 집합이다.

 S = {(x1,y1),(x2,y2),(x3,y3),(x4,y4),(x5,y5))}

어떤 t에서의 상태 St는 정해져 있지 않습니다. 이처럼 어떤 집합 안에서 뽑을 때마다 달라질 수 있는 것을

"확률변수"라고 합니다.

 "시간 t에서 상태 St가 어떤 상태 s다" St = s

행동

 에이전트가 상태 St에서 할 수 있는 가능한 행동의 집합은 A

 "시간 t에서 에이전트가 특정한 행동 a를 했다" At = a

At는 어떤 t라는 시간에서 집합 A에서 선택한 행동입니다.

t라는 시간에 에이전트가 어떤 행동을 할지 정해져 있는 것이 아니므로 확률변수 입니다.

만약, 어떤 시간 t에서 St에서 At를 하였을 때, 바람과 같은 예상치 못한 결과가 나올 수 있습니다.

이러한 상황을 고려해주는 것이 상태 변환 확률 입니다.

보상함수

보상은 에이전트가 학습할 수 있는 유일한 정보로서 환경이 에이전트에게 주는 정보입니다.

시간 t에서 상태가 St = s 이고, 행동이 At = a 에이전트가 받을 보상은

 R(a,s) = E[R(t+1) | St = s, At = a]

보상함수는 시간 t일 때 상태가 St=s 이고, 그 상태에서 행동 At = a를 했을 경우에 받을 보상에 대한 기댓값 E 입니다.

기댓값은 어떤 정확한 값이 아니라 나오게 될 숫자에 대한 예상입니다.

보상 또한 기댓값이어서 상태 s에서 행동 a를 했을 경우에 받을 거이라 예상되는 숫자입니다.

보상을 에이전트에게 주는 것은 환경이고, 환경에 따라서 같은 상태에서 같은 행동을 취하더라도 다른 보상을 줄 수도 있습니다.

이 모든 것을 고려해서 보상함수를 기댓값으로 표현합니다.

괄호 안의 "|"는 조건문에 대한 표현입니다. |을 기준으로 뒤에 나오는 부분들이 현재의 조건을 의미 합니다.

보상함수의 조건 혹은 입력은 상태와 행동입니다.

어떤 상태s에서 행동 a를 할 대마다 받는 보상이 다를 수 있으므로 기댓값의 표현인 E가 붙은 것입니다.

보상함수에서 특이한 점은 에이전트가 어떤 상태에서 행동한 것은 시간 t에서인데, 보상을 받는 것은 t+1이라는 것입니다.

이것은 보상을 에이전트가 알고 있는 것이 아니고 환경이 알려주는 것이기 때문입니다.

에이전트가 상태 S에서 행동 a를하면 환경은 에이전트가 가게 되는 다음 상태 s'과 에이전트가 받을 보상을 에이전트에게 알려줍니다.

환경이 에이전트에게 알려주는 것이 t+1 시점입니다. 따라서 에이전트가 받는 보상을 R(t+1)이라고 표현합니다.

에이전트는 환경으로 부터 하나의 시간 단위가 지난 다음에 보상을 받습니다. 이 시간 단위를 타임스텝이라고 하겠습니다.

상태 변환 확률

에이전트가 어떤 상태에서 어떤 행동을 취한다면 에이전트의 상태는 변할 것입니다.

에이전트가 앞으로 나아가는 행동을 하면 s보다 앞에 있는 s' 이라는 상태에 도달할 것입니다.

s'이라는 것은 다음 타임스텝에 에이전트가 갈 수 있는 어떤 특정한 상태를 의미 합니다.

하지만 꼭 앞에 있는 상태에 도달하지 못할 수도 있습니다.

옆에서 바람이 불 수도 있고, 갑자기 넘어질 수도 있습니다.

이처럼 상태의 변화에는 확률적인 요인이 들어갑니다.

이를 수치적으로 표현한 것이 상태 변환 확률 입니다.

P(a, s') = P[S(t+1)=s'|St=s,At=a]

P는 확률을 의미합니다.

상태 변환 확률은 상태 s에서 행동 a를 취했을 때 다른 상태 s'에 도달할 확률입니다.

이 값은 보상과 마찬가지로 에이전트가 알지 못하는 값으로서 에이전트가 아닌 환경의 일부입니다.

상태 변환 확률은 환경의 모델이라고도 부릅니다.

환경은 에이전트가 행동을 취하면 상태변환 확률을 통해 다음에 에이전트가 갈 상태를 알려 줍니다.

감가율

에이전트가 항상 현재에 판단을 내리기 때문에 현재 가까운 보상일수록 더 큰 가치를 가집니다. 

보상의 크기를 100이라고 했을 때 현재 시각에 보상을 받을 때는 에이전트는 100의 크기 그대로 받아들입니다.

하지만 현재로부터 일정 시간이 지나서 보상 100을 받는다면, 그것을 100이라고 생각하지 않습니다.

에이전트는 그 보상이 얼마나 시간이 지나서 받는지를 고려해서 감가시켜 현재의 가치로 따집니다.

여러분이 복권에 당첨됐다고 해봅시다.

당첨금인 1억 원을 당장 받을 수 있고, 10년 뒤에 받을 수도 있습니다.

여러분은 어떤 선택을 할 것인가요?

당연히 당장 받는 것을 선호할 것입니다. 

우리는 나중에 받을 보상을 현재의 보상과 같게 하려고 "이자"라는 제도를 두고 있습니다.

이자는 나중에 받을 보상에 추가적인 보상을 더해 현재의 보상과 같게 합니다.

반대로 말하면 같은 보상이면 나중에 받을수록 가치가 줄어든다는 것입니다.

이를 수학적으로 표현하기 위해 우리는 "감가율"이라는 개념을 도입합니다.

감가율 γ는 0과 1사이의 값입니다. 따라서 보상에 곱해지면 보상이 감소합니다.

γ ∈ [0,1]

만약 현재의 시간 t로 부터 시간 k가 지난후에 보상을 R(t+k)를 받을 것이라고 하면,

현재 그 보상의 가치의 수식은 다음과 같습니다.

γ^(k-1)R(t+k)

정책

정책은 모든 상태에서 에이전트가 할 행동입니다.

상태가 입력으로 들어오면 행동을 출력을 내보내는 일종의 함수라고 생각해도 좋습니다.

정책은 각 상태에서 단 하나의 행동만을 나타낼 수도 있고,

확률적으로 a1 = 10%, a2 = 90%와 같이 나타낼 수도 있습니다.

에이전트가 강화학습을 통해 학습해야 할 것은 수많은 정책 중에서 최적 정책입니다.

최적 정책은 각 상태에서 단 하나의 행동만을 선택 합니다.

하지만 에이전트가 학습하고 있을 때는 정책이 하나의 행동만을 선택하기보다는 확률적으로 여러 개의 행동을 선택할 수 있어야 합니다.

그래야 에이전트가 다양한 상황에 대해 학습하고 최적 정책을 찾을 수 있을 것입니다.

π(a|s) = P[At=a|St=s]

시간 t에 St=s에 에이전트가 있을 때 가능한 행동 중에서 At = a를 할 확률을 나타 냅니다.

정책만 가지고 있으면 에이전트는 사실 모든 상태에서 자신이 해야 할 행동을 알 수 있습니다.

하지만 강화학습 문제를 통해 알고 싶은 것은 그냥 정책이 아니라 "최적 정책" 입니다.

최적 정책을 얻기 위해서 현재의 정책보다 더 좋은 정책을 학습해나가는 것이 강화학습입니다.

이처럼 MDP를 통해  순차적 행동 결정 문제를 정의했습니다.

에이전트가 현재 상태에서 앞으로 받을 보상들을 고려해서 행동을 결정합니다.

그러면 환경은 에이전트에게 실제 보상과 다음 상태를 알려줍니다.

이러한 과정을 반복하면서 에이전트는 앞으로 받을 것이라 예상했던 보상에 대해 틀렸다는 것을 알게 됩니다.

이때 받을 것이라 예상하는 보상을 가치함수라고 합니다.

그러한 과정에서 에이전트는 실제로 받은 보상을 토대로 자신의 정보와 그리고 정책을 바꿔나갑니다.

이러한 학습 과정을 무한히 반복한다면 가장 많은 보상을 받게 하는 정책을 학습할 수 있습니다.