[1차시] Markov process

서론

강화학습의 목표는 “현재 상황에서 어떤 행동을 해야 미래에 더 좋은 결과를 얻을 수 있는가?” 이라고 볼 수 있다.

이 질문을 다루려면 먼저 시간에 따라 상태가 어떻게 변할지를 표현해야 한다. 하지만 미래의 상태는 정확히 정해져 있지 않고 확률적으로 변한다.(예를 들어 로봇이 앞으로 가려고 해도 바닥의 상태나 주변 환경에 따라 실제 이동 결과가 달라질 수 있다. 왜냐하면 같은 상태에서 같은 행동을 하더라도 결과에 영향을 주는 불확실한 요소들이 존재하기 때문이다.)

이처럼 시간에 따라 확률적으로 변하는 현상을 표현한 것이 확률과정이다.

그러나 모든 과거 정보를 고려하면 문제를 계산하기가 매우 복잡해진다.

따라서 Markov 모델에서는 다음과 같은 제약을 둔다. 미래는 전체 과거가 아니라 현재 상태에 의해서만 결정된다.

이를 Markov property라고 하며, 이 성질을 만족하면서 시간과 상태가 이산적인 확률과정을 markov chain이라고 한다.

즉, 확률과정은 불확실한 미래를 표현하는 수학적 틀이고, 마르코프 성질은 그 미래를 계산할 수 있도록 단순화하는 가정이다. 강화학습은 이러한 구조 위에서 현재의 행동이 미래의 보상에 미치는 영향을 학습한다.

Stochastic process

확률변수 하나는 "한 번의 불확실한 사건"을 표현한다. 주사위 한 번, 동전 한 번. 그런데 우리가 다루려는 세계는 한 번으로 끝나지 않는다. 로봇은 매 순간 움직이고, 상태는 계속 변한다.

그래서 강화학습에서는 시간의 매 스텝마다 확률변수를 하나씩 배치하는 것을 Stochastic process라 한다.

수학적으로 말하면 시간 인덱스 t마다 확률변수 $X_t$가 하나씩 대응되는 확률변수들의 모임(collection of random variables)을 말한다. 시간이 이산인 경우 식은 아래와 같다.

\{X_t\}_{t \in T}, \quad T = \{0, 1, 2, \dots\}

미래의 상태를 예측할 때 지금까지 지나온 모든 과거 상태를 조건으로 사용하면 계산이 너무 복잡해진다.

예를 들어 가능한 상태가 $|S|$개이고, 지금까지 n번 상태가 변했다면 가능한 과거 경로의 수는 대략 $|S|^n$개로 지수적으로 증가한다.

시간이 길어질수록 기억해야 할 과거가 계속 늘어나므로 실제 계산과 학습이 어려워진다.

그래서 다음과 같이 문제를 단순화한다.

미래를 예측할 때 모든 과거를 기억하지 않고, 현재 상태만이 다음 상태에 영향을 가지고 가정하고 미래를 예측해보자. 라고 접근하며 이 가정이 바로 markov property의 출발점이다.

Markov property

현재 상태가 미래를 예측하는 데 필요한 모든 정보를 이미 담고있다!

P(x_{n+1}|x_n, x_{n-1}, x_{n-2}, ...,x_0) = P(x_{n+1}|x_n)

즉 미래는 현재에만 의존하고, 과거의 경로는 미래에 영향을 주지 않는다. 이러한 성질을 Markov property라고 한다.

Markov process

Markov property를 만족하는 Stochastic process을 markov process라고 부른다.

markov process는 시간과 상태가 각각 이산인지 연속인지에 따라 네 가지 조합이 있다.

강화학습은 스텝 단위 t=0, 1, 2, … 로 진행되므로 시간 이산 · 상태 이산인 경우를 기본으로 삼는다.

이 경우를 Markov chain이라 부른다.

정리하면 Markov property를 만족하는 Stochastic process을 markov process라하며 시간과 상태공간이 이산인 경우를 Markov chain이라고 한다.

Markov Chain

State transition matrix

미래는 현재 상태만으로 결정된다고 가정하므로, 각 상태에서 다음 상태로 이동할 확률만 알면 상태가 어떻게 바뀔지 표현할 수 있다.

따라서 현재 상태가 s일 때 다음 상태가 s'가 될 확률을 다음과 같이 표현한다.

P_{ss'} = P(S_{t+1} = s' \mid S_t = s)

상태가 유한개($|S|=n$)라면 이것을 행렬하나에 담을 수 있다.

\mathcal{P} = \begin{bmatrix}\mathcal{P}_{11} & \cdots & \mathcal{P}_{1n} \\\vdots & \ddots & \vdots \\\mathcal{P}_{n1} & \cdots & \mathcal{P}_{nn}\end{bmatrix}\\[10pt] \sum_{s'} \mathcal{P}_{ss'} = 1.

각 행은 그 상태에서 출발했을 때의 다음 상태 분포"이므로 행의 합은 항상 1이다.

그러면 이러한 전이확률을 가지고 1-step에서 시스템이 상태 J에 있을 확률을 구해보자

p_J^{(1)} = P(X_1 = J) = ?

$p_i^{t}$: 아래첨자 i는 현재 상태(state)이고 위 첨자 t는 시간(step)을 나타낸다.
예를들어 $p_2^{1}$은 1-step에서 상태 2에 있을 확률을 의미한다.

그런데 우리가 알고 있는 전이행렬만으로는 이 확률을 바로 구할 수 없다.

왜냐하면 전이행렬은 아래와 같이 예를들어 “현재 I상태가 주어졌을 때”의 조건부 확률만 알려주기 때문이다.

P_{IJ} = P(X_{t+1} = J \mid X_t = I)

($P_{IJ}=$ 상태 I에서 상태 J로 갈 전이 확률)

은 시점 1일때 상태 J에 있으려면, 시점 0에는 반드시 1에 도달가능한 상태 $1,2,\ldots,M$ 중 하나에 있었어야 한다. 따라서 상태 J에 도착할 수 있는 출발 상태에 대한 모든 경우를 각각 나누어 더하면 된다.

\begin{aligned} P(X_1 = J) = P(X_1 = J \cap X_0 = 1) + P(X_1 = J \cap X_0 = 2) +\dots + P(X_1 = J \cap X_0 = M)\end{aligned}

각 항은 결합확률이므로, 조건부확률로 풀어 쓸 수 있다: $P(A \cap B) = P(A \mid B) P(B)$

\begin{aligned} &= P(X_1 = J \mid X_0 = 1)\,P(X_0 = 1) + \cdots + P(X_1 = J \mid X_0 = M)\,P(X_0 = M) \\ &= \sum_{I=1}^{M} P(X_1 = J \mid X_0 = I)\; P(X_0 = I) \end{aligned}

위 식을 계산하기 위해서 무엇이 필요한지 봐보면

첫번째 항 $P(X_1 = J \mid X_0 = I)$는 전이행렬의 원소로 우리가 이미 배워서 알고있다.

그런데 두번째 항 $P(X_0=I)$는 0번째 스텝에서 I에 있었을 확률로 이를 초기상태 분포라고 한다.

우리는 초기 상태의 확률과 전이 확률을 함께 사용하면 한 단계 뒤의 상태 확률을 구할 수 있다.

Initial distribution

$P(X_0=I),\;I=1,...,M$ 임으로 벡터형태로 묶어 정의하면 수식은 아래와 같다.

p^{(0)} = \left( p_1^{(0)} \quad p_2^{(0)} \quad \dots \quad p_M^{(0)} \right), \quad p_I^{(0)} = P(X_0 = I)

$p^{(i)}$는 i-step에서의 시스템이 각 상태에 있을 확률분포
위 식의 경우 $p_1^{(0)}$는 0번째 스탭에서 첫 번째 상태에 있을 확률
$p_2^{(0)}$는 0번째 스탭에서 두 번째 상태에 있을 확률

최종적으로 처음 상태가 I일 때 다음 스탭 상태 J에 있을 확률은 다음과 같다.

p_J^{(1)} = \sum_{I=1}^{M} p_I^{(0)} P_{IJ}

1-step distribution

J에 있을 확률이 아닌 첫 번째 스탭의 상태확률 분포는 아래와 같이 표현하여 구할 수 있다.

p^{(1)} = p^{(0)} \cdot \mathcal{P}

왜 저렇게 되는지 예시를 들어 이해해보자.

Example

상태 S의 갯수가 3개인 0, 1, 2만 있다고 가정해보자. 그렇다면 전이행렬은 3×3이다.

\mathcal{P} = \begin{pmatrix} P_{00} & P_{01} & P_{02} \\ P_{10} & P_{11} & P_{12} \\ P_{20} & P_{21} & P_{22} \end{pmatrix}

그리고 이때 초기분포와 1-step 분포는 각각 세 성분짜리 행벡터를 가지게 된다.

p^{(0)} = \begin{bmatrix} p_0^{(0)} & p_1^{(0)} & p_2^{(0)} \end{bmatrix}, \quad p^{(1)} = \begin{bmatrix} p_0^{(1)} & p_1^{(1)} & p_2^{(1)} \end{bmatrix}

이제 $p^{(1)} = p^{(0)} \cdot \mathcal{P}$를 그대로 곱해서 봐보자

\begin{aligned} p^{(1)} &= \begin{bmatrix} p_0^{(0)} & p_1^{(0)} & p_2^{(0)} \end{bmatrix} \begin{pmatrix} P_{00} & P_{01} & P_{02} \\ P_{10} & P_{11} & P_{12} \\ P_{20} & P_{21} & P_{22} \end{pmatrix} \\ &= \begin{bmatrix} \underbrace{p_0^{(0)} P_{00} + p_1^{(0)} P_{10} + p_2^{(0)} P_{20}}_{p_0^{(1)}} , & \underbrace{p_0^{(0)} P_{01} + p_1^{(0)} P_{11} + p_2^{(0)} P_{21}}_{p_1^{(1)}} , & \underbrace{p_0^{(0)} P_{02} + p_1^{(0)} P_{12} + p_2^{(0)} P_{22}}_{p_2^{(1)}} \end{bmatrix} \end{aligned}

그럼 실제로 1-step에서 시스템이 상태 J=0에 있을 확률을 구해보자: $p^{(1)}_{J=0}$

p_0^{(1)} = p_0^{(0)} P_{00} + p_1^{(0)} P_{10} + p_2^{(0)} P_{20}

\begin{aligned} p_0^{(0)} P_{00} &= P(X_0 = 0) \cdot P(X_1 = 0 \mid X_0 = 0) = P(X_1 = 0 \cap X_0 = 0) \\ p_1^{(0)} P_{10} &= P(X_0 = 1) \cdot P(X_1 = 0 \mid X_0 = 1) = P(X_1 = 0 \cap X_0 = 1) \\ p_2^{(0)} P_{20} &= P(X_0 = 2) \cdot P(X_1 = 0 \mid X_0 = 2) = P(X_1 = 0 \cap X_0 = 2) \end{aligned}

세 항을 더하면

p_0^{(1)} = P(X_1 = 0 \cap X_0 = 0) + P(X_1 = 0 \cap X_0 = 1) + P(X_1 = 0 \cap X_0 = 2) = P(X_1 = 0)

가 된다.

쉽게 말하면 이는 상태 0으로 흘러들어오는 세 갈래 경로

0 → 0
1 → 0
2 → 0

가능한 확률을 전부 더하는 식이다.

따라서

$p^{(0)}_0P_{00}: $ 0-step에서 0상태에 있을 확률과 0상태에서 0상태로 갈 확률(전이확률)을 곱한 것
$p^{(0)}_1P_{10}: $ 0-step에서 1상태에 있을 확률과 1상태에서 0상태로 갈 확률(전이확률)을 곱한 것
$p^{(0)}_2P_{20}: $ 0-step에서 2상태에 있을 확률과 2상태에서 0상태로 갈 확률(전이확률)을 곱한 것

위 3가지의 확률을 합한 것이 $p^{(1)}_0$이고 이것이 1-step에서 0상태에 있을 확률이 된다.

그리고 1-step에서 1상태에 있을 확률 $p^{(1)}_1$과 1-step에서 2상태에 있을 확률 $p^{(1)}_2$를 나열하면 1-step에서 시스템이 각 상태가 있을 분포인 $p_{(1)}$를 구하게 되는 것이다.

p^{(1)} = p^{(0)} \cdot \mathcal{P}

우리는 위 수식처럼 $p_{(1)}$을 구하기 위해서는 0-step의 분포에 전이행렬을 곱하여 구했다.

마찬가지로 $p_{(2)}$ 를 구하기 위해서는 1-step분포 $p_{(1)}$에 전이행렬을 곱하면 알 수 있다.

Chapman-Kolmogorov Equation

미래 시점 n+m의 확률을 구할 때, 처음(0)부터 한 스텝씩 전이확률을 반복해서 곱해 갈 수도 있지만,

중간 시점 n까지의 전이확률과 남은 기간 m동안의 전이확률을 곱해서 한 번에 계산할 수도 있다:

\begin{aligned}p^{(2)} &= p^{(1)} \cdot \mathcal{P} = (p^{(0)} \cdot \mathcal{P}) \cdot \mathcal{P} = p^{(0)} \cdot \mathcal{P}^2 \\p^{(3)} &= p^{(2)} \cdot \mathcal{P} = p^{(0)} \cdot \mathcal{P}^3 \\&\vdots \\p^{(n)} &= p^{(0)} \cdot \mathcal{P}^n = p^{(n-1)} \cdot \mathcal{P}\end{aligned}

p^{(n+m)} = p^{(n)} \cdot \mathcal{P}^m

이것이 Chapman–Kolmogorov 방정식이다

Example

첫날이 Sunny일때 모레의 날씨는? 을 구하는 예시를 풀어보자.

상태는 두 개가 있다: $S=\{1=\text{sunny},\;2=\text{cloudy}\}$, 내일의 날씨는 오늘의 날씨에만 영향을 미친다고 가정하자(Markov Property)

\begin{aligned} \mathcal{P} &= \begin{pmatrix} \frac{2}{3} & \frac{1}{3} \\[6pt] \frac{1}{2} & \frac{1}{2} \end{pmatrix} \\[10pt] &\left( P_{11} = \frac{2}{3} : \text{오늘 Sunny일 때 내일도 Sunny일 확률, 각 행의 합 } = 1 \right) \end{aligned}

첫날이 Sunny라고 했음으로 초기 상태 분포는 아래와 같다.

p^{(0)} = \begin{pmatrix} 1 & 0 \end{pmatrix}

그리고 이를 Chapman–Kolmogorov 방정식을 활용해 구해주면

\begin{aligned}p^{(1)} &= p^{(0)}\mathcal{P} = \begin{pmatrix} 1 & 0 \end{pmatrix} \begin{pmatrix} \frac{2}{3} & \frac{1}{3} \\ \frac{1}{2} & \frac{1}{2} \end{pmatrix} = \begin{pmatrix} \frac{2}{3} & \frac{1}{3} \end{pmatrix} \\p^{(2)} &= p^{(1)}\mathcal{P} = \begin{pmatrix} \frac{2}{3} & \frac{1}{3} \end{pmatrix} \begin{pmatrix} \frac{2}{3} & \frac{1}{3} \\ \frac{1}{2} & \frac{1}{2} \end{pmatrix} = \begin{pmatrix} \frac{11}{18} & \frac{7}{18} \end{pmatrix}\end{aligned}

모레 Sunny일 확률은 11/18이고 Cloudy일 확률은 7/18인 모레날씨의 분포를 구할 수 있게 된다.

강화학습은 먼 미래의 분포를 알아야 한다.

강화학습의 목표는 “현재 상황에서 어떤 행동을 해야 미래에 더 좋은 결과를 얻을 수 있는가?” 이라고 이야기 했었다. 이 목표를 이루기 위해서는 각 상태에서 어떤 행동을 할지 정해둔 규칙, 즉 정책(policy)을 평가하고 개선하는 것이다.
여기서 특정 상태에서 어떤 행동을 하라고 정해진 규칙을 정책이라 하고 강화학습을 통해 정책의 좋음을 평가하고 개선하는 것이다.
여기서 정책이란 특정 상태에서 어떤 행동을 하라고 정해진 일종의 설명서다. 강화학습은 이 설명서를 점점 더 좋은 설명서로 고쳐 나가는 과정이다. 즉 정책 A를 따라 행동해 봤더니 어떤 결과가 나왔고, 이를 평가하여 정책을 개선해 정책 B를 만들고, 다시 정책 B를 따라 행동해 보고 평가하고 개선하고… 를 반복한다.
그럼 정책은 어떻게 평가해야할까?
정책을 하나 고정하면, 에이전트의 움직임은 하나의 마르코프 체인이 된다. 각 상태에서 무슨 행동을 할지 정책이 정해주고, 그 행동의 결과로 다음 상태가 확률적으로 정해지므로, "상태 → 다음 상태"의 전이확률이 결정되기 때문이다.
그렇다면 정책의 좋음은 정책을 오랫동안따랐을 때 "좋은 상태들 근처에서 시간을 많이 보내는" 정책이 좋은 정책이라고 할 수 있다.
이를 수학적으로 표현하면 n이 커질 때 $p^{(n)}=p^{(0)}\mathcal{P}^n$ 의 분포가 어떻게 되는지를 안다면 각 상태를 장기 적으로 얼마나 자주 방문하는지 알게 됨으로 정책을 평가할 수 있게 된다.
또한 정책의 장기적인 성능을 제대로 평가하려면, 에이전트(시스템, 로봇)가 어디에서 시작했는지와 관계없이 같은 결과에 도달해야 한다. 같은 정책인데도 출발 상태에 따라 장기적인 상태분포가 달라진다면, 그 결과는 정책 자체의 특성이라기보다 초기 상태의 영향을 크게 받은 것이기 때문이다.

그렇다면 우리는 다음과 같은 질문을 가지고 알아보자.

\lim_{n \to \infty} p^{(n)}\text{은 존재하는가? 존재한다면 } p^{(0)}\text{과 무관한가?}

Limiting distribution

Limiting distribution이란, 어떤 초기분포$(p(0))$로 시작했는지와 상관없이 시간이 무한히 흐르면(step $n \rightarrow \infin$) 도달하게 되는 확률분포를 말한다.

p^{(\infty)} = \lim_{n \to \infty} p^{(n)} = \lim_{n \to \infty} p^{(0)} \cdot \mathcal{P}^n

위 확률분포를 나타내기 위해서는 두 가지 조건이 성립해야 하는데 하나는 $n \rightarrow \infin$ 때의 극한이 존재해야한다는 것이고, 다른 하나는 그 값이 초기분포(출발점)와 무관해야 한다는 것이다.

그런데 행렬 $\mathcal{P}$를 n번 곱한 $\mathcal{P}^n$을 구하는 것은 쉬운일이 아니다. 이를 쉽게 하기 위해서 행렬 $\mathcal{P}$를 대각행렬로 만들면 행렬곱이 쉬워진다. 이는 Diagonalization(대각화)를 통해 가능하다.

\mathcal{P} = Q D Q^{-1}

여기서 D는 $\mathcal{P}$의 고윳값 $\lambda_1, \dots, \lambda_m$ 을 대각에 놓은 행렬이고, $Q = [v_1 \,\, v_2 \,\, \cdots \,\, v_m]$은 대응하는 고유벡터들을 열로 세운 행렬이다.

대각화한 $\mathcal{P}^2$을 계산하면:

\mathcal{P}^2 = (QDQ^{-1})(QDQ^{-1}) = QD \underbrace{(Q^{-1}Q)}_{= I} DQ^{-1} = Q D^2 Q^{-1}

$\mathcal{P}^n$도 계산해보면

\mathcal{P}^n = Q D^n Q^{-1} = Q \begin{pmatrix} \lambda_1^n & & \\ & \ddots & \\ & & \lambda_m^n \end{pmatrix} Q^{-1}

로 쉽게 계산될 수 있다.

그럼 행렬의 n곱 계산이 가능해졌으니 실제 예시를 통해서

$n \rightarrow \infin$ 때의 극한이 존재하는지
그렇게 극한으로 보냈을 때 초기분포(출발점)와 무관한지

를 알아보자.

Example

이를 알아보기 위해 날씨 예제를 사용한다.

\mathcal{P} = \begin{pmatrix} \frac{2}{3} & \frac{1}{3} \\[6pt] \frac{1}{2} & \frac{1}{2} \end{pmatrix}

EigenVector, EigenValue란?

$v$ 고유벡터는(eigenvector) 행렬을 곱해도 방향은 변하지 않고 크기만 변하는 0이아닌 벡터
$\lambda$ 고윳값(eigenvalue): 행렬을 어떤 0이 아닌 벡터 v에 곱했을 때 그 벡터의 방향은 유지한 채 크기를 변화시키는 스칼라 값

Av = \lambda v

위 식을 만족하는 $v$가 고유벡터, $\lambda$가 고윳값이다.

Q = [v_1 \,\, v_2 \,\, \cdots \,\, v_m], \quad D = \begin{pmatrix} \lambda_1 & & \\ & \ddots & \\ & & \lambda_m \end{pmatrix}

$v_i:$ 고유벡터(열벡터)
$\lambda_i$: 고윳값(스칼라)

고유벡터의 정의에 의해:

\mathcal{P}v = \lambda v

우변을 좌변으로 넘기면

\mathcal{P}v - \lambda v = 0

$\lambda$는 스칼라 임으로 행렬끼리의 뺄샘을 하기 위해

(\mathcal{P} - \lambda I)v = 0

$v$는 0이아닌 벡터여야 함으로 행렬 $(\mathcal{P} - \lambda I)$의 역행렬이 존재하면 안 된다.

왜냐하면 $(\mathcal{P} - \lambda I)$의 역행렬이 존재하면

\begin{align}&(\mathcal{P} - \lambda I)v = 0\\ &Bv = 0\\ &B^{-1}Bv = B^{-1}0\\&v=0 \end{align}

$v$가 0이되기 때문이다.

역행렬이 존재하면 안 됨으로 $\text{det}(\mathcal{P} - \lambda I) = 0$ 여야 한다.

$\det(\mathcal{P}-\lambda I) = \lambda^2-{}^{7}\!/\!_{6}\lambda+{}^{1}\!/\!_{6} = 0$ 를 풀면

\lambda_1 = 1, \quad \lambda_2 = \dfrac{1}{6}

임으로 $\mathcal{P} = Q D Q^{-1}$에서 D는:

D = \begin{pmatrix} 1 & 0 \\[6pt] 0 & \frac{1}{6} \end{pmatrix}

고유벡터는

$\text{i}) \lambda_1=1$ 인 경우

(\mathcal{P} - 1 \cdot I)v_1 = \begin{pmatrix} \dfrac{2}{3} - 1 & \dfrac{1}{3} \\[10pt] \dfrac{1}{2} & \dfrac{1}{2} - 1 \end{pmatrix} \begin{pmatrix} x_1 \\[10pt] x_2 \end{pmatrix} = \begin{pmatrix} -\dfrac{1}{3} & \dfrac{1}{3} \\[10pt] \dfrac{1}{2} & -\dfrac{1}{2} \end{pmatrix} \begin{pmatrix} x_1 \\[10pt] x_2 \end{pmatrix} = \begin{pmatrix} 0 \\[10pt] 0 \end{pmatrix}

연립방정식으로 쓰면

\begin{cases} -\dfrac{1}{3}x_1 + \dfrac{1}{3}x_2 = 0 \\[10pt] \dfrac{1}{2}x_1 - \dfrac{1}{2}x_2 = 0 \end{cases} \implies \begin{cases} -x_1 + x_2 = 0 \\ x_1 - x_2 = 0 \end{cases}

x_1 = x_2 \implies v_1 = c \begin{pmatrix} 1 \\ 1 \end{pmatrix} \quad (c \neq 0\text{인 아무 값})

$c=1$을 골라

v_1=\begin{pmatrix} 1 \\ 1 \end{pmatrix}

$\text{i}) \lambda_2=\frac{1}{6}$ 인 경우

(\mathcal{P} - \frac{1}{6}I) v_2 = \begin{pmatrix} \frac{2}{3} - \frac{1}{6} & \frac{1}{3} \\ \frac{1}{2} & \frac{1}{2} - \frac{1}{6} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} \frac{1}{2} & \frac{1}{3} \\ \frac{1}{2} & \frac{1}{3} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}

연립방정식으로 쓰면

\frac{1}{2}x_1 + \frac{1}{3}x_2 = 0 \implies x_2 = -\frac{3}{2}x_1

$x_1 =2$를 고르면

v_2=\begin{pmatrix} 2 \\ -3 \end{pmatrix}

정리하면

Q = [v_1 \quad v_2] = \begin{pmatrix} 1 & 2 \\ 1 & -3 \end{pmatrix}, \quad D = \begin{pmatrix} 1 & 0 \\ 0 & \frac{1}{6} \end{pmatrix}

마지막으로 $Q^{-1}$을 구하면

\begin{bmatrix} a & b \\ c & d \end{bmatrix}^{-1} = \frac{1}{ad-bc} \begin{bmatrix} d & -b \\ -c & a \end{bmatrix}

에 의해

Q^{-1} = \frac{1}{(1)(-3) - (2)(1)} \begin{pmatrix} -3 & -2 \\ -1 & 1 \end{pmatrix} = \frac{1}{-5} \begin{pmatrix} -3 & -2 \\ -1 & 1 \end{pmatrix} = \begin{pmatrix} \frac{3}{5} & \frac{2}{5} \\ \frac{1}{5} & -\frac{1}{5} \end{pmatrix}

$\mathcal{P}^n$을 계산하면

\mathcal{P}^n = QD^n Q^{-1} = \begin{pmatrix} 1 & 2 \\ 1 & -3 \end{pmatrix} \begin{pmatrix} 1^n & 0 \\ 0 & \left(\frac{1}{6}\right)^n \end{pmatrix} \begin{pmatrix} \frac{3}{5} & \frac{2}{5} \\ \frac{1}{5} & -\frac{1}{5} \end{pmatrix}

극한을 계산하면

\begin{align} \lim_{n \to \infty} \mathcal{P}^n = Q \left( \lim_{n \to \infty} D^n \right) Q^{-1} = Q \begin{pmatrix} \lim_{n \to \infty} 1^n & 0 \\ 0 & \lim_{n \to \infty} \left(\frac{1}{6}\right)^n \end{pmatrix} Q^{-1} \\[10pt]= Q \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} Q^{-1} \end{align}

\lim_{n \to \infty} \mathcal{P}^n = \begin{pmatrix} 1 & 2 \\ 1 & -3 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} \begin{pmatrix} \frac{3}{5} & \frac{2}{5} \\ \frac{1}{5} & -\frac{1}{5} \end{pmatrix}

앞에서부터 두 행렬을 계산하면

\begin{pmatrix} 1 & 2 \\ 1 & -3 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix}

최종적으로 계산하면

\lim_{n \to \infty} \mathcal{P}^n = \begin{pmatrix} 1 & 0 \\[6pt] 1 & 0 \end{pmatrix} \begin{pmatrix} \frac{3}{5} & \frac{2}{5} \\[6pt] \frac{1}{5} & -\frac{1}{5} \end{pmatrix} = \begin{pmatrix} 1 \cdot \frac{3}{5} + 0 & 1 \cdot \frac{2}{5} + 0 \\[6pt] 1 \cdot \frac{3}{5} + 0 & 1 \cdot \frac{2}{5} + 0 \end{pmatrix} = \begin{pmatrix} \frac{3}{5} & \frac{2}{5} \\[6pt] \frac{3}{5} & \frac{2}{5} \end{pmatrix}

가 되어 이 예제의 경우 첫 번째 조건인 극한이 존재한다는 것을 확인했다.

첫날이 Sunny 였음으로 초기분포 $p^{(0)} =(1\;\;0)$을 곱하면

\therefore p^{(\infty)} = p^{(0)} \left( \lim_{n \to \infty} \mathcal{P}^n \right) = \begin{pmatrix} 1 & 0 \end{pmatrix} \begin{pmatrix} \frac{3}{5} & \frac{2}{5} \\[6pt] \frac{3}{5} & \frac{2}{5} \end{pmatrix} = \begin{pmatrix} \frac{3}{5} & \frac{2}{5} \end{pmatrix}

이 결과의 의미는 긴 시간이 흐른 후에 Sunny일 확률이 $\frac{3}{5}$, Cloudy일 확률이 $\frac{2}{5}$

만약 초기 분포가 반대로 Cloudy였다면 초기분포 $p^{(0)} =(0\;\;1)$을 곱하면

p^{(\infty)} = \begin{pmatrix} 0 & 1 \end{pmatrix} \begin{pmatrix} \frac{3}{5} & \frac{2}{5} \\[6pt] \frac{3}{5} & \frac{2}{5} \end{pmatrix} = \begin{pmatrix} \frac{3}{5} & \frac{2}{5} \end{pmatrix}

임으로 따라서 두 번째 조건인 초기분포에 영향을 받지 않고 값이 동일함을 확인했다.

이러한 두 조건을 만족하는 $p^{(\infty)}$를 극한 분포라고 한다.

강화학습에서 정책의 평가 기준은 "그 정책을 장기간 따랐을 때 좋은 상태에 얼마나 머무는가"이다. 이를 알려면 장시간이 흐른 뒤의 상태 분포가 존재해야 하고, 그 분포가 초기 상태에 따라 달라진다면 정책이 아닌 출발점을 평가하는 셈이 되므로 초기분포와도 무관해야 한다. 이 두 조건 극한의 존재, 초기분포 무관을 만족하는 분포가 극한분포이며, 정책(이 만들어내는 마르코프 체인)을 하나의 값으로 평가할 수 있게 해주는 이론적 기반이 된다.

강화학습에는 정책의 장기 성능을 정의하는 방식에는 평균보상 방식, 할인 보상 방식 두 종류가 있다. 평균보상 방식은 에르고딕이라는 조건을 가정하에 동작하는데 에르고딕의 조건중 극한분포가 존재가 보장되어야 한다. 이 방식을 사용하는 알고리즘은 R-learning, Differential Q-learning, Differential SARSA 등이 있으며 할인 보상방식은 Q-learning, DQN, PPO 등 이 있다.

Stationary distribution

우리는 극한분포를 구하기 위해서는 고윳값, 고유벡터, 고유벡터의 역행렬을 구해야하며 이는 상태가 많아지면 즉 행렬의 크기가 커지면 연산하는 비용이 많이 복잡하다.

우리는 "상태를 어떤 분포에 곱해도 변하지 않는 어떤 분포는 무엇인가"라는 접근한다.

극한분포를 $\pi$라고 하면, 이미 장기적으로 안정된 분포이므로 한 번 더 상태전이행렬 $\mathcal{P}$를 곱해도 분포가 더 이상 변하지 않는다. (실제로 극한분포를 구하고 거기에 초기분포(1 0)과 (0 1)을 곱했을 때 극한분포가 변하지 않았다.)

또한 $\pi$는 확률분포임으로 확률의 합은 1이여야 한다. 이 두 성질을 수식으로 작성하면 아래와 같다.

\pi = \pi \mathcal{P} , \quad \sum_{i} \pi_i = 1

그리고 위 조건을 만족하는 $\pi$를 Stationary distribution(정상분포)라고 한다.

실제로 이 분포에서 전이행렬을 곱해 매 스텝을 이여(체인을 시작)나가면, 모든 시점의 분포가 모두

π로 고정(동일)된다.

p^{(0)} = \pi \implies p^{(1)} = \pi \mathcal{P} = \pi, \quad p^{(2)} = \pi \mathcal{P} = \pi, \ \dots

실제 날씨예제에서 $\pi =(\pi_1\;\;\pi_2)$로 놓고 풀어보자.

\begin{pmatrix} \pi_1 & \pi_2 \end{pmatrix} \begin{pmatrix} \frac{2}{3} & \frac{1}{3} \\[6pt] \frac{1}{2} & \frac{1}{2} \end{pmatrix} = \begin{pmatrix} \pi_1 & \pi_2 \end{pmatrix}

첫 번째 성분을 전개하면:

\frac{2}{3}\pi_1 + \frac{1}{2}\pi_2 = \pi_1 \implies \frac{1}{2}\pi_2 = \frac{1}{3}\pi_1 \implies \pi_2 = \frac{2}{3}\pi_1

$\pi_1 + \pi_2 = 1$과 연립하면:

\pi_1 + \frac{2}{3}\pi_1 = 1 \implies \pi_1 = \frac{3}{5}, \quad \pi_2 = \frac{2}{5}\\[10pt]\therefore \pi = \begin{pmatrix} \frac{3}{5} & \frac{2}{5} \end{pmatrix}

대각화를 통해 힘들게 구했던 극한분포 $\pi = \begin{pmatrix} \frac{3}{5} & \frac{2}{5} \end{pmatrix}$가 연립방정식으로 쉽게 구해졌다.

주의할 점은

극한 분포가 존재하면 정상 분포도 존재한다.
정상분포가 존재한다고 극한 분포가 존재한다는 보장은 없다.

전자는 이미 예시를 통해서 구해봤으니 후자만 예시를 들어 보겠다.

전이행렬이 아래와 같고 $\pi = \begin{pmatrix} \frac{1}{2} & \frac{1}{2} \end{pmatrix}$ 이라면

\mathcal{P} = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}

$\pi \mathcal{P} = \begin{pmatrix} \frac{1}{2} & \frac{1}{2} \end{pmatrix} = \pi$ 임으로 정상분포( $\pi = \begin{pmatrix} \frac{1}{2} & \frac{1}{2} \end{pmatrix}$)가 존재한다.

그런데 극한분포는 초기분포와 무관해야 함으로 만약 출발점이 $p^{(0)} = \begin{pmatrix} 1 & 0 \end{pmatrix}$라면

p^{(1)} = \begin{pmatrix} 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 1 \end{pmatrix},\quad p^{(2)} = \begin{pmatrix} 0 & 1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0 \end{pmatrix},\quad \dots

초깃값이 무엇이냐에 따라 결과가 달라지는 현상이 나타남으로 이 경우는 극한 분포가 존재하지 않는다.

Ergodicity

지금까지의 상황을 정리해 보면 우리는 정책을 평가를 위해 극한분포가 필요했고, 그것을 쉽게구하기 위해 $\pi = \pi\mathcal{P}$ 정상분포를 구하는 방법으로 극한분포를 구했다. 그런데 정상분포를 구했다고 해서 그것이 극한분포라는 보장이 없었다.
따라서 정상분포가 극한분포와 같아지도록 하는 에르고딕(ergodic)이라는 조건을 가정한다.
따라서 에르고딕 성질을 만족한다는 것은 "정상분포가 유일하게 존재하고, 그것이 곧 극한분포임"을 보장하는 조건이다.
정상분포는 여러 개를 가질 수 있다.
$\mathcal{P} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$인 경우 항등 행렬임으로 어떤 분포를 넣어도 성립한다.
$\begin{pmatrix} 1 & 0 \end{pmatrix} \mathcal{P} = \begin{pmatrix} 1 & 0 \end{pmatrix} \checkmark \\ \begin{pmatrix} 0 & 1 \end{pmatrix} \mathcal{P} = \begin{pmatrix} 0 & 1 \end{pmatrix} \checkmark \\ \\\begin{pmatrix} \frac{1}{2} & \frac{1}{2} \end{pmatrix} \mathcal{P} = \begin{pmatrix} \frac{1}{2} & \frac{1}{2} \end{pmatrix}\checkmark \\ \begin{pmatrix} 0.3 & 0.7 \end{pmatrix} \mathcal{P} = \begin{pmatrix} 0.3 & 0.7 \end{pmatrix} \checkmark$

Ergodic Theorem

1. Reducible / Irreducible

먼저 용어부터 알아보자

클래스(communicating class): 상태 i에서 j로 갈 수 있고 동시에 j에서 i로도 돌아올 수 있을 때(왕복 가능) 두 상태가 communicate 가능하다고 하고 이러한 상태들을 묶은 집합을 말한다.

Reducible

예를들어 다음과같이 상태가 4개가 있고 전이행렬이 아래와 같다.

S = \{1,\ 2,\ 3,\ 4\}\\[10pt] P = \begin{pmatrix} 1 & 0 & 0 & 0 \\ \frac{1}{3} & 0 & \frac{2}{3} & 0 \\ 0 & \frac{1}{3} & 0 & \frac{2}{3} \\ 0 & 0 & 1 & 0 \end{pmatrix}

이를 그림으로 표현하면 각 상태에 대한 체인을 연결하고 전이행렬의 확률을 표기했다.

이때 클래스는 $\{1\}$과 $\{2, 3, 4\}$가 된다. 이렇게 클래스의 집합이 분리되어 2개 이상인 경우를 reducible이라고 한다.

Irreducible

예를들어 다음과같이 상태가 4개가 있고 전이행렬이 아래와 같다.

S = \{1,\ 2,\ 3,\ 4\}\\[10pt] P = \begin{pmatrix} 0 & 1 & 0 & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 1 & 0 \end{pmatrix}

이를 그림으로 표현하면 각 상태에 대한 체인을 연결하고 전이행렬의 확률을 표기했다.

이때 클래스는 $\{1, 2, 3, 4\}$가 된다. 이 경우 클래스의 집합이 단 하나인 경우 irreducible이라고 한다.

이 의미는 모든 상태에서 어디든 도달가능하다는 뜻이다.

2. Recurrent/ transient

Recurrent: 되돌아올 확률이 1인 상태로 몇 번을 떠나도 반드시 되돌아오는 경우

Transient: 떠난 뒤 영영 못돌아올 가능성이 있는 경우

첫 번째 예시의 경우 상태 1은 Recurrent하다. 왜냐하면 반드시 자기자신으로 되돌아오기 때문이다. 그러나 2, 3, 4는 1/3의 확률로 1의 상태로 빠져버리면 다시는 2, 3, 4로 돌아올 수 없다.

따라서 $\{1\}$은 recurrent, $\{2, 3, 4\}$는 transient이다.

두 번째 예시의 경우 상태 1, 2, 3, 4 전부 자기 자신으로 되돌아올 수 있음으로 $\{1, 2, 3, 4\}$가 recurrent이다.

정리하면 communicate하는 상태들은 같은 communicate class에 있고 그 class에 속한 상태들은 전부 recurrent하거나 transient하다.

3. Aperiodic

상태 $I$의 주기(period)를 다음과 같이 정의한다.

d(I) = \gcd \{ n \ge 1 : \text{상태 } I\text{에서 출발해 } n\text{스텝 만에 } I\text{로 돌아올 수 있음} \}

쉽게말해 되돌아 올 수 있는 스텝 수들의 최대공약수로 주기성인지 아닌지를 판별한다.

$d(I) \ge 2 \rightarrow \text{periodic(주기적)}$: 특정 박자의 배수로만 돌아온다.
$d(I) = 1 \rightarrow \text{aperiodic(비주기적)}$: 돌아오는 시점에 공통 박자가 없다.

첫 번째 예시는 상태가 2개가 있고 아래와 같은 상태전이 행렬이 있다고한다면

\mathcal{P} \, = \, \begin{pmatrix} \frac{2}{3} & \frac{1}{3} \\[1.5ex] \frac{1}{2} & \frac{1}{2} \end{pmatrix}

이고 이를 그림으로 표현하면 아래와 같다.

상태 1에 대한 주기를 보고싶다면

상태 1로 시작해서 상태 1로돌아오는 경우

1-step: 1 → 1 (가능)
2-step: 1 → 2 → 1 (가능)
3-step: 1 → 2 → 2 → 1 (가능)
4-step: … (가능)

$gcd(1,2,3,...) = 1$ 임으로 상태 1은 Aperiodic하다.

두 번째 예시는 상태가 두 개있고 상태전이행렬이 다음과 같다.

\mathcal{P} = \begin{pmatrix} 0 & 1 \\[0.5ex] 1 & 0 \end{pmatrix}

이를 그림으로 표현하면 아래와 같다.

상태 1에 대한 주기를 보고싶다면

상태 1로 시작해서 상태 1로돌아오는 경우

1-step: 1 → 2 (불가능)
2-step: 1 → 2 → 1 (가능)
3-step: 1 → 2 → 1 → 2 (불가능)
4-step: … (가능)

$gcd(2,4,6...) = 2$ 임으로 상태 1은 Periodic하다.

여기서 2의 의미는 2스텝마다 반드시 돌아온다는 뜻이 아니라, 돌아온다면 그 시점이 반드시 2의 배수라는 뜻이다.

마무리

여기까지 강화학습의 정책을 평가하기 위해 필요한 사전 조건들에 대해서 알아보았다.

정리하면, 정책을 평가한다는 것은 "그 정책을 장기간 따랐을 때 좋은 상태에 얼마나 머무는가"를 따지는 일이었다. 이를 위해 장시간 후의 상태 분포인 극한분포가 필요했고 연산량이 많아짐으로 이를 쉽게 구하기 위해 방정식 $\pi = \pi\mathcal{P}$ 로 구하는 정상분포를 얻었으며, 이 정상분포와 극한분포가 같아지기 위한 자격 조건인 — irreducible, recurrent, aperiodic, 즉 에르고딕 — 까지 확인했다.

이로써 정책이 만들어내는 마르코프 체인을 하나의 값으로 평가할 수 있는 이론적 기반이 마련되었다. 다만 마르코프 체인만으로는 아직 "평가"를 시작할 수 없다. 어떤 상태가 좋은지에 대한 개념(보상)도, 그 상태에 도달하기 위한 행동을 아직 모르기 때문이다.

다음 시간에는 이 두 가지를 얹어, 강화학습의 근간이 되는 MDP(Markov Decision Process)를 진행한다.

[1차시] Markov process

서론

목차

Stochastic process

Markov property

Markov process

Markov Chain

State transition matrix

Initial distribution

1-step distribution

Example

Chapman-Kolmogorov Equation

Example

강화학습은 먼 미래의 분포를 알아야 한다.

Limiting distribution

Example

Stationary distribution

Ergodicity

Ergodic Theorem

1. Reducible / Irreducible

Reducible

Irreducible

2. Recurrent/ transient

3. Aperiodic

마무리

Comment