강화학습 기초 다지기 (1) - 마르코프

마르코프는 강화 학습 기초에 꼭 등장하는 개념이다. 이번 글에서는 마르코프와 관련된 개념들을 정리할 것이다.

 

마르코프 특성 (Markov Property)

'마르코프 하다'라는 것은 미래 상태 $s_{t+1}$은 현재 상태 $s_{t}$에만 의존한다는 것을 의미한다. 다른 말로 하면 현재 상태를 알면, 그 이전의 모든 역사를 아는 것과 동일하게 미래 상태 $s_{t+1}$를 추론할 수 있다는 의미다. 이를 수식으로 표현하면 다음과 같이 나타낼 수 있다. 

$$ P(s_{t+1}|s_{t}) = P(s_{t+1}|s_{t}, s_{t-1},..., s_{0}) $$

 

마르코프 과정 (Markov Process - MP : $<S, P>$)

마르코프 특성을 만족하는 상태의 반복을 마르코프 과정(Markov process)이라고 부른다. 마르코프 특성은 상태 집합 S와 상태 천이 행렬 P으로 이루어진 튜플이다. S는 모든 상태에 대한 집합을 의미하고, 상태 천이 행렬은 현재 상태에서 다음 상태로 이동할 확률을 표현한 행렬이다. 상태가 n 개라면 상태 천이 행렬은 $n \times n$이 된다. 

 

마르코프 보상 과정 (Markov Reward Process - MRP : $<S, P, R,\gamma>$)

마르코프 보상 과정은 마르코프 과정에서 보상 함수 $\textit {R}$ $(R: \textit {S} \to \mathbb {R})$과 감가율 $\gamma \in [0,1]$를 포함한 것이다. 보상 함수와 감가율을 알기 위해서는 리턴 $G_{t}$ 개념을 알아야 한다.

리턴 $G_{t}$는 현재 시점 t부터 전체 미래에 대한 감가 된 보상의 합이다. 수식으로 나타내면 다음과 같이 나타낼 수 있다. 

$$ G_{t} = R_{t+1} + \gamma R_{t+2} + \gamma^{2} R_{t+3} +... = \sum_{a=1}^{\infty} \gamma^{a-1} R_{t+a} $$

이는 나중에 강화 학습 agent가 현재 상태로부터 미래에 일을 고려하여 판단할 수 있게 해주는 좋은 장치로 사용된다. 보상은 agent가 특정 행동을 했을 때 줄 수 있고 감가율 $\gamma$를 조절하며 미래에 대한 보상을 조절할 수 있다. 감가율은 보상이 무한히 커지는 것을 방지하며 너무 먼 미래에 대한 이익보단 가까운 미래에 대한 보상을 최대화하기 위해 사용된다. 

 

가치 함수와 벨만 항등식

가치 함수 V(s)는 현재 상태 s에서 미래의 감가 된 보상의 합 ($G_{t}$)의 기댓값을 의미한다(즉, 리턴의 기댓값). 이는 수식으로 다음과 같이 표현한다.

$$ V(s) = \mathbb {E}[G_{t}|S_{t}=s] $$

가치 함수는 벨만 항등식 (bellman equation)에 의해 다음과 같이 표현될 수 있다.

$$ \begin {align*} V(s) &= \mathbb {E}[G_{t}|S_{t}=s] \\ &= \mathbb {E}[R_{t+1} + \gamma R_{t+2} + \gamma^{2} R_{t+3} +.. | S_{t}=s] \\ &= \mathbb {E}[R_{t+1} + \gamma (R_{t+2} + \gamma R_{t+3} +... )|S_{t} = s] \\ &= \mathbb {E}[R_{t+1} + \gamma G_{t+1} | S_{t} = s]  \\ &= \mathbb {E}[R_{t+1}+\gamma V(S_{t+1})|S_{t} = s]  \\ &= R(s) + \gamma \sum_{s' \in S_{t+1}} P_{ss'} V(s') \end {align*} $$

마지막 벨만 방정식은 선형 연립방정식을 통해 다음과 같이 표현이 가능하다.

$$ v = R + \gamma Pv $$

이를 통해 $ v = (I-\gamma P)^{-1} R$ 로 해를 구할 수 있다. 하지만 상태 개수(n)가 커질수록 직접적으로 문제를 푸는 것이 어려워져서 dynamic programming, monte carlo, temporal difference 등의 방법을 이용하여 문제를 풀게 된다.

 

마르코프 결정 과정 (Markov Decision Process - MDP : $<S, A, P, R,\gamma>$)

마르코프 결정 과정은 MRP에 행동을 추가한 확률 과정이다. 행동 집합 $A$가 추가되었으므로 상태 천이 행렬 P과 보상 함수 R도 상태 s뿐 아니라 행동 a까지 고려하여야 한다. $$P_{ss'}^{a} = P [S_{t+1}=s' | S_{t} = s, A_{t} = a]$$

$$ R: S \times A \to \mathbb {R} $$

이제는 상태가 주어졌을 때, 행동을 하여 미래의 상태와 보상을 바꿀 수 있게 되었다.

 

정책 함수

정책 함수 $\pi$는 현재 상태에서 수행할 행동의 확률 분포를 나타낸다.

$$ \pi(a|s) = P(A_{t}=a|S_{t}=s) $$

마르코프 특성을 가정하여 현재 상태만을 가지고 의사결정을 한다. 좋은 $\pi$를 가지고 있으면 많은 보상을 얻을 수 있다.

 

상태 가치 함수와 행동 가치 함수

상태 가치 함수는 $V_{\pi}(s) = \mathbb {E}_{\pi}[G_{t}|S_{t}=s]$으로 표현된다. 현재 상태 s에서 정책 $\pi$를 따른다면 얻을 수 있는 미래 가치의 감가 총합을 나타낸다.

행동 가치 함수는 $Q_{\pi}(s, a) = \mathbb {E}_{\pi}[G_{t}|S_{t}=s, A_{t}=a]$으로 표현된다. 현재 상태 s에서 a라는 행동을 취한 후, 정책 $\pi$를 따른다면 얻을 미래 가치의 감가 총합을 나타낸다.

당연히 상태 가치 함수와 행동 가치 함수는 관련되어 있고 서로를 다음과 같이 표현할 수 있다.

$$ V_{\pi}(s) = \sum_{a \in A} \pi(a|s) Q_{\pi}(s, a) $$

(현재 상태 s에서 a라는 행동을 할 확률이 $\pi(a|s)$이므로, 각 상태와 행동에 대한 가치 $Q_{\pi}$를 $\pi(a|s)$로 평균을 내면 현재 상태의 가치 $V_{\pi}(s)$가 된다.)

$$ Q_{\pi}(s, a) = R_{s}^{a} + \gamma \sum_{s' \in S} P_{ss'}^{a} V_{\pi}(s') $$

(현재 상태 s에서 a라는 행동을 하면, $R_{s}^{a}$의 보상을 받고 확률적으로 어떤 s'들에 도달하게 된다. 각 도달한 s'에서 각각의 가치 $V_{\pi}(s')$과 s'을 얻을 확률 $P_{ss'}$를 곱하여 모두 더해 s'에서 얻을 기댓값을 구하고 $\gamma$만큼 감가 한다.)

 

최적 가치 함수와 최적 정책

최적 상태 가치 함수는 $ V^{*}(s) = max_{\pi} V_{\pi} (s) $ 로 정의할 수 있다. 이는 존재하는 모든 정책들 중에 모든 상태 s에서 가장 높은 $V_{\pi}(s)$를 만드는 $\pi$를 적용했을 때 얻는 $V_{\pi}$(s)를 의미한다. 

최적 행동 가치 함수는 $ Q^{*}(s, a) = max_{\pi} Q_{\pi}(s, a) $ 로 정의할 수 있다. 이는 존재하는 모든 정책들 중에 모든 상태, 행동 조합에서 가장 높은 $Q_{\pi}(s, a)$를 만드는 $\pi$를 적용했을 때 얻는 $Q_{\pi}(s, a)$를 의미한다.

MDP를 풀기 위해서는 최적 가치 함수를 찾거나 그것을 만드는 최적 정책 $\pi$를 찾아야 한다.