강화학습은 sequential decision making 문제를 해결하기 위한 알고리즘입니다. MDP는 이를 수학적으로 모델링하는 프레임워크입니다.
이번 글에서는 MDP를 다루기 전에 Markov process, Markov reward process를 우선 다루겠습니다.
MDP는 이름대로 markov property에 기반합니다.
Markov Property는 stochastic process에서 특별한 성질을 담고 있는 경우를 의미합니다.
markov property는 아래의 식으로 표현 가능합니다.
$P[S_{t+1}|S_t] = P[S_{t+1}|S_1,...,S_t] $
일반적으로 미래를 예측하기 위해서는 과거의 정보가 필요합니다. 예를 들어 다음날 주가를 예측하기 위해서는 오늘의 주가만 아는 것보다 과거의 주가를 모두 안다면 더 신뢰성 높은 예측이 가능합니다.
이렇듯 보편적인 경우에서 예측에는 과거의 정보가 필요하지만 markov property는 미래가 오직 현재의 정보에만 의존적인 경우를 말합니다. 이는 현재의 정보가 과거의 정보를 충분히 잘 표현하고 있어 필요 없는 경우를 의미합니다.
위 수식을 글로 적는다면 t시점 상태가 주어진 후 t+1 시점 상태에 대한 예측은 1,..., t시점의 상태를 모두 알고 예측하는 것과 같은 예측임을 의미합니다. 즉 말한 것처럼 t+1의 상태를 예측하기 위해서는 t시점 상태만 알더라도 충분하게 됩니다.
위 식은 아래와 같이 변형 가능한데
$P[S_{t+1}|S_t] = P[S_1,...,S_t,S_{t+1}] / P[S_1,...,S_t]$
$P[S_{t+1}|S_t]P[S_1,...,S_t]/P[S_t] = P[S_1,...,S_t,S_{t+1}]/P[S_t]$
$P[S_{t+1}|S_t]P[S_1,...,S_{t-1}|S_t] =P[S_1,...,S_{t-1},S_{t+1}|S_t]$
위 식은 t가 주어진 세계관에서는 t+1 시점의 상태와 1부터 t-1 시점까지 상태와는 서로 독립임을 의미합니다. 조건부독립, 조건부독립위키
수식은 다르게 했지만 결국 같은 얘기입니다. 현재의 정보만 주어진다면 과거의 state들은 미래 시점에 영향을 주지 못한다는 의미입니다.
t+1 시점의 변수의 condition에 t시점에 해당하지 않는 변수는 다 지울 수 있습니다. markov property의 가장 큰 특징인 memoryless 한 특성으로 인해 계산을 쉽게 만들어 주는 장점이 있습니다.
이러한 markov property를 이용하는 가장 간단한 stochastic process는 Markov Process입니다. (markov chain이라고도 함)
말 그대로 stochastic process가 markov property를 만족한다면 markov process입니다.
하나의 markov process를 특정 짓기 위해서는 state의 집합 S와, state transition matrix 두 가지 요소가 필요합니다.
S는 말 그대로 우리가 다루고자 하는 모든 상태들의 집합입니다.
state transition matrix는 어떤 상태 s가 다음 step에서 상태 s'이 될 확률에 대한 정보를 담고 있는 matrix입니다.
(transition은 state의 변화를 의미합니다.)
일반적으로 t시점의 s에서 t+1 시점이 s'으로 변화는 경우를 아래 식의 좌변과 같이 표기합니다. 좌변의 P의 밑에서 왼쪽이 시작 시점의 상태, 오른쪽이 도달한 상태를 의미합니다.
$P_{ss'}=P[S_{t+1}=s'|S_t=s]$
따라서 $P_{ab}$는 상태 a에서 시작해 b에 도달할 확률을 의미합니다.
당연한 얘기지만 t시점에서 상태가 1번 상태로 주어진다면 t+1 시점에 가능한 s'의 모든 확률의 합은 1이 됩니다.
위의 표기를 따라 표기하면 아래와 같습니다.
$P_{11}+P_{12}+...+P_{1n}=1$
2번 상태로 시작하였을 때도 마찬가지 아래의 식을 성립시킵니다.
$P_{21}+P_{22}+...+P_{2n}=1$
이렇게 1부터 n까지 나열한 것을 행렬의 표기법에 맞춰 적어준다면 이것이 state transition matrix가 됩니다. 당연한 얘기지만 state transition matrix는 정방행렬입니다.
아래는 회색글은 넘기셔도 됩니다.
david silver의 강의는 markov chain을 아주 간략하게 다루는데 간략하게 마르코프 체인 정상분포(stationary distribution)에 대해 언급해 보겠습니다. 정상 stationary의 의미는 시간에 따라 변하지 않음을 의미합니다. (t와 t+1 시간의 transition matrix가 같다는 것을 의미합니다.) 정상 분포를 나타내는 행벡터인 상태벡터를 pi라고 하면 시간에 따라 변하지 않으므로 아래 식을 만족합니다.
$\pi=\pi P=\pi P^2=...=\pi P^n, ||\pi||_1 = 1$
n이 충분히 커지면 P의 각 행은 pi로 수렴
정상분포는 markov chain이 특정한 조건을 만족할 때 존재합니다. 해당 조건을 만족한다면 P의 전치행렬(P^T)의 고유벡터 중 고윳값 1에 해당하는 고유벡터가 정상분포가 됩니다. 이 고유벡터는 합이 1이 되어야 합니다. transition matrix는 모든 열의 합이 1이므로 항상 고유 값 1을 갖고 특정한 정상 상태를 갖게 됩니다.
선형대수적 관점에서 고유공간이 2차원 이상이 되면 정상분포가 존재하지 않습니다.
간단한 예제를 보겠습니다.
ex1) 매년 도시 1에 거주하는 사람 중 20%는 도시 2로 이사를 간다. 매년 도시 2에 사는 사람 중 40%는 도시 1로 이사를 간다. 이러한 경우 도시 1, 도시 2의 인구가 [1,1] , [2,1](만 명)인 경우에 대해 1년 뒤, 그리고 10년 뒤의 도시별 인구를 구해라.
transition matrix를 구하기 위해 생각해 보면
1년 뒤 도시 1에는 원래 거주하던 사람의 80%는 남게 되고 도시 2의 사람 중 20%가 더 들어옵니다.
도시 2에서는 60%의 인구가 남고 도시 1의 20%의 인구가 유입이 됩니다.
초기값 $x_0 = [1 1]$ 인 경우에 대해 풀어보면 아래와 같습니다.
위처럼 마르코프 체인의 경우 transition matrix를 알고 있는 경우에 시점 0부터 n step 뒤에 대해서 아래와 같이 구할 수 있습니다.
$X_n = X_0 P^n$
그럼 두 번째 경우인 [2,1]인 경우는 사실 몇 년이 지나더라도 [2,1]입니다.
처음 경우에서 [1,1]에서도 시간이 충분히 흐른다면 [1.33,0.67]로 수렴해 2:1의 비율을 유지합니다.
그럼 $P^100$을 구해보면 두 행이 모두 [2/3,1/3]을 갖게 됩니다.
마르코프 체인이 어떤 특성을 만족하는 경우에 t가 매우 커진다면 모든 행이 같아지는 rank 1의 행렬을 갖게 됩니다. 이는 from과 to의 관점에서 생각하면 이 state가 어디서 시작하든 다음 step에서 도달하는 곳의 확률 분포는 같은 분포를 갖게 됨을 의미합니다.
stationary에 대해 더 자세한 내용은 markov chain과 convergence, ergodicity, stantionary 등을 키워드로 찾아보시면 더 많은 내용을 찾을 수 있습니다.
다음은 Markov Reward Process(MRP)입니다.
reward의 개념이 추가되었습니다. reward는 스칼라 값이며 강화학습에서 유일학게 좋고 나쁨을 판별하는 인자이므로 reward를 이용해 목적함수를 설정합니다.
일반적인 지도학습에서는 모델의 예측과 정답간의 손실함수를 통해 objective(목적)를 설정합니다. 훈련 데이터 전체에 대해 loss function을 최소화하는 목적식을 갖습니다.
하지만 강화학습은 주어진 학습 데이터가 없습니다. 따라서 환경과 에이전트의 상호작용을 통해 스스로 데이터를 만들어야 합니다. 이러한 특성 때문에 trial and error가 강화학습의 중요한 키워드가 됩니다.
david silver의 강의 자료에서는 아래와 같이 설명합니다.
이전의 markov process는 tuple (S, P)로 정의되었지만 MRP는 (R, gamma)가 추가되었습니다.
우선 S, P는 이전에 정의했으니 우선 R에 대해서 알아보겠습니다.
R은 reward function으로 어떤 state에서 얻을 수 있는 reward의 기댓값입니다.
$R:S\to \mathbb{R} $
reward는 random variable이며 state를 떠날 때 얻는 값입니다. MDP에서는 어떤 state에서 action을 취할 때 받게 되므로 떠날 때 받는 것이라고 생각하는 게 좀 더 편할듯합니다.
예를 들어 할머니댁에 가서 용돈(reward)을 받지만 그 금액이 매번 같지는 않더라도 평균은 가질 수 있습니다.
reward는 random variable이지만 reward function은 reward를 기댓값을 이용해 랜덤 하지 않도록 만들어줍니다.
그리고 reward는 그냥 어떤 state마다 대응되는 값이라고 생각해도 크게 문제는 없을 것 같습니다.
다음으로 disconut factor, gamma는 return의 연산에 이용됩니다.
우선 finite process와 terminal state, episode에 대해 짧게 얘기해 보겠습니다.
terminal state는 한번 들어가면 나올 수 없는 state입니다. 이 경우 시간이 계속 흐르더라도 transition이 불가하므로 process가 끝나는 state입니다. transition matrix의 대각 성분 중 1이 있다면 해당 state에 들어간 뒤로부터는 탈출하지 못하게 됩니다.
(특정 조건을 만족하지 못해 아까 말했던 stationary distribution은 아닙니다.)
episode는 transition의 sequence입니다. 우리는 markov process를 각 time step마다 state를 state transition matrix를 통해 smapling 할 수 있습니다. 그리고 sampling 된 일련의 sequence를 episode라고 합니다.
episode의 길이를 horizon이라고 하는데 horizon이 infinite냐 혹은 finite이냐에 따라서도 나눌 수 있습니다.
어떤 episode를 샘플링하더라도 terminal state가 있다면 어느 시점에는 process는 종료되게 됩니다. 만약 terminal state가 없다면 episode는 무한히 길어집니다. 그럴 경우 임의로 episode길이의 최대 값을 두어 finite으로 만들 수도 있습니다.
아마도 당분간은 terminal state가 존재하는 mdp에 대해서만 다룰듯합니다.
return은 샘플링된 에피소드에서 time step t로부터의 reward의 총합이고 수식으로는 아래와 같이 표현합니다.
강화학습에서 에이전트는 이 보상의 합을 최대로 많이 받고 싶어 하도록 설정합니다.
$G_t = R_{t+1}+\gamma R_{t+2}+... = \Sigma_{k=0} \gamma^k R_{t+k+1}$
$= R_{t+1}+\gamma(R_{t+2}+\gamma R_{t+3}+...) = R_{t+1}+\gamma G_{t+1}$
gamma는 discounting factor로 retrun을 계산하는 데 사용됩니다.
discount factor를 사용하는 가장 큰 이유는 수학적 편리성과 return의 발산을 막기 위해서라고 합니다. 에피소드의 길이가 너무 무한대가 될 경우 discount factor가 없다면 return이 발산하게 됩니다. 만약 episode의 길이가 무한대가 되지 않는다면 gamma를 1로 설정해도 된다고 합니다.
discount factor의 값이 0에 가까울수록 return이 즉각적인 reward를 더 크게 반영하는 것이고 1에 가까울수록 먼 시점의 reward도 함께 고려하는 것입니다. 또 추가적으로 사람이 먼 시점의 보상보다 당장의 보상을 선호하는 경향등 여러 가지 이유가 붙어있지만 가장 큰 이유는 수학적 편리성이라고 합니다.
다음은 강화학습에서 꽤 많이 중요한 value function입니다.
value function(가치함수)은 return에 대한 기댓값입니다. 현재는 state만 있는 MRP이므로 먼저 상태 가치함수 state value function만 다루겠습니다.
state value function은 특정 state에서 얻을 수 있는 return의 기대 값입니다. return도 결국엔 에피소드를 sampling 하면서 얻게 되는 랜덤변수이지만 이에 기댓값을 취함으로써 함수의 형식을 갖습니다.
$v(s) = \mathbb{E}[G_t |s_t=s]$
v(s)>v(s')이라면 agent는 s에서 s'보다 보상의 총합을 더 많이 얻는다고 기대할 수 있습니다.
아래 예제에 대해서 return을 구해보겠습니다.
여기서 terminal state는 sleep입니다. gamma는 0.5 start state s0는 항상 c1이라고 가정합시다.
episode1 : C1 FB FB C1 C2 Sleep $-2 -1\times 0.5 -1\times 0.5^2 -2\times 0.5^3 -2\times 0.5^4 = -3.125$
episode2 : C1 C2 C3 Pass Sleep $-2 -2 \times 0.5 -2\times 0.5^2 -10\times 0.5^3 =-2.25$
마지막으로 bellman equation(벨만 방정식)입니다. 벨만 방정식을 통해서 정의된 MRP의 value function을 구할 수 있습니다.
아까의 value function 식과 return의 식을 섞으면
$v(s) = \mathbb{E}[R_{t+1} + \gamma G_{t+1} |s_t=s]$
기대 값의 덧셈은 분해가 가능하므로 보상 함수의 정의에 따라 아래와 같이 변환 가능하고
$v(s)=R(s) + \gamma \mathbb{E}[G_{t+1}|s_t=s ] $
나머지 기댓값은 아래식으로 변형 가능합니다.
오른쪽 평균에서 감마를 제거해서 살펴보겠습니다.
아래식 좌변에 law of total expectation을 적용시키면 우변의 형태가 됩니다.
$ E[G_{t+1}|s_t=s] = E[E[G_{t+1}|s_t=s,s_{t+1}=s']|s_t=s]$
expectation의 condition에 markov property를 적용시키면
$=E[E[G_{t+1}|s_{t+1}=s']|s_t=s]=E[v(s')|s_t=s] $
$=\Sigma_{s'} v(s') P[s_{t+1}=s'|s_t=s]$
$\therefore \ v(s)=R(s)+\gamma\Sigma_{s' \in S} P_{ss'}v(s')$
이 v에 대한 점화식이 bellman equation입니다.
위 식은 수식으로 이해하는 것보다 아래의 그래프로 보면 더 이해가 쉽습니다.
s의 return의 기댓값(value)은 다음과 같이 표현해도 무방합니다. s에서 value는 state s를 떠나면 s에 해당하는 reward와 s에서 이동할 수 있는 state로 v(s')의 기댓값(평균)의 합으로 해석 가능하므로 value function v(s) 식이 나온다고 이해하는 게 더 쉬울듯합니다. 실제로 전개과정에서 수식이 의미하는 내용과 의미적으로 동일합니다.
만약 R과 v를 각 state에 정보들을 담는 vector처럼 정의한다면.(state transition matrix처럼)
model을 알고 있다는 것은 P와 R을 알고 있다는 것이므로 아래의 수식을 통해 value function을 직접적으로 구할 수 있습니다.
$v = R + \gamma Pv$
$(I_n-\gamma P)v = R$
$v=(I_n-\gamma P)^{-1} R$
역행렬을 구하는데 시간복잡도가 O(n^3)만큼 소요되어 보통 다른 방법(td, mc, dp)을 통해 풀게 됩니다.
다음에는 MDP를 다뤄보겠습니다.
Reference
https://www.youtube.com/watch?v=E3f2Camj0Is
https://www.youtube.com/watch?v=lfHX2hHRMVQ&t=323s