강화학습 기본 알고리즘(1)

 1. 마르코프 결정 과정(Markov Decision Process)

마르코프 결정 과정(MDP)는 마르코프 보상 과정(MRP)에 행동(A : Acton)과 정책($\pi$ : Policy) 가 추가된 개념이다.

MDP에서는 Action이 추가되었기 때문에

이에 따른 상태 전이 확률과 보상함수를 새로 정의하여야 한다.

MDP에서 상태 전이 함수는 특정 상태(s)에서 행동(a)를 취했을 때

다음 상태(s')으로 전이되는 확률이다.

$$P_{ss'}^a = P[S_{t+1} = s' \mid S_t = s, A_t = a]$$

마찬가지로 보상함수는특정 상태(s)에서 행동(a)를 취했을 때

t+1에서 받을 수 있는 보상의 기댓값이므로 다음과 같다.

$$R_s^a = E[R_{t+1} \mid S_t = s, A_t = a]$$

Agent가 Action을 선택하는 확률을 정책이라 한다.

정책은 $\pi$로 나타내며 다음과 같이 정의된다.

$$\pi = P[A_t = a \mid S_t = s]$$

식 그대로 상태 s에서 행동 a를 할 확률이다.

이때 Agent가 특정 상황에서 취할 수 있는 모든 정책의 합

즉, 각각의 행동을 할 확률의 합은 1이다.

따라서 MRP와 MDP에서 모두 특정 상태에서 다음 상대로 전이되는 확률은 같다.

이는 다음 그림을 보면 이해가 쉬울것이다.

MRP에서 상태 $s_1$에서 상태 $s_2$로 이전할 확률은 $p_1$이고

MDP에서는 다음과 같다.

$$\pi_1 p_1 + \pi_2 p_1 = (\pi_1 + \pi_2) p_1 = p_1$$

이와 같은 원리가 보상함수에서도 성립한다.

이를 수식으로 나타내면 다음과 같다.

$$P_{ss'}^{\pi} = \sum_{a \in A} \pi(a \mid s) P_{ss'}^a \\ R_{ss'}^{\pi} = \sum_{a \in A} \pi(a \mid s) R_s^a$$

MDP에서 상태가치 함수를 구해보자

$$\begin{matrix}v_{\pi}(s) &=& E[R_{t+1} + \gamma v_{\pi}(S_{t+1}) \mid S_t = s, \pi] \\ &=& \sum_{a \in A} \pi(a \mid s) \left( R_s^a + \gamma \sum_{s' \in S} P_{ss'}^a v_{\pi}(s') \right) \\ &=& \sum_{a \in A} \pi(a \mid s) R_s^a + \gamma \sum_{a \in A} \pi(a \mid s) \sum_{s' \in S} P_{ss'}^a v_{\pi}(s') \end{matrix}$$

이를 정리하면

$$v_{\pi} = R^{\pi} + \gamma P^{\pi} v_{\pi} \\ \rightarrow v_{\pi} = (1-\gamma P^{\pi})^{-1} R^{\pi}$$

로 정리되며 행렬 연산에 보다 간편하게 이용 가능하다.

2. MDP 행동 가치 함수

상태 가치 함수로는 MDP의 행동과 정책을 평가할 수 없다.

따라서 행동에 따른 가치를 평가하기 위하여 행동 가치 함수(Q : Action Value Function)를 정의한다.

$$\begin{matrix} q_{\pi}(s, a) &=& E[R_{t+1} + \gamma q_{\pi}(S_{t+1}, A_{t+1}) \mid S_t = s, A_t = a, \pi] \\ &=& R_s^a + \gamma \sum_{s' \in S} \sum_{a' \in A}P_{ss'}^a \pi(a' \mid s') q_{\pi}(s', a') \\ &=& R_s^a + \gamma \sum_{s' \in S} P_{ss'}^a v_{\pi}(s') \end{matrix}$$

$$(\because \sum_{a' \in A} \pi(a' \mid s') q_{\pi}(s', a') = v_{\pi}(s'))$$

이때 상태 가치 함수 식과 비교해보자

$$v_{\pi}(s) = \sum_{a \in A} \pi(a \mid s) R_s^a + \gamma \sum_{a \in A} \pi(a \mid s) \sum_{s' \in S} P_{ss'}^a v_{\pi}(s')$$

따라서 다음과 같은 관계가 성립한다.

$$v_{\pi}(s) = \sum_{a \in A} \pi(a \mid s) q_{\pi}(s) \\ $$

3. MDP 최적 가치 함수(Optimal Value Function)

MDP에서 가장 효과적인 정책을 구하기 위하여 최적 가치 함수를 정의한다.

최적 가치 함수는 상태 가치 함수와 행동 가치 함수에 모두 적용할 수 있다.

$$v^*(s) = \underset{\pi}{\max} v_{\pi}(s) \\ q^*(s, a) = \underset{\pi}{\max} q_{\pi}(s, a)$$

위 수식의 의미는 상태가치함수 혹은 행동가치함수가 최대가 되는 정책에서의 값을 의미한다.

이를 이용하여 최적 정책(Optimal policy)를 정의할 수 있다.

최적의 가치를 얻도록 행동하는 정책이 최적 정책이다.

4. 강화학습에 사용되는 용어

4.1 정책 평가(Policy Evaluation)와 정책 제어(Policy Control)

정책 평가란 상태 가치 함수를 구하는 것이고 정책 제어에서 이 가치를 최대화 하기위한 정책을 찾는다.

4.2 모델 기반(Model Based)과 모델 프리(Model Free)

환경에 대한 모든 정보를 알고 있는경우를 모델 기반, 그렇지 않는 경우 모델 프리라고 한다.