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

5. 다이내믹 프로그래밍(Dynamic Programming)

다이내믹 프로그래밍이란 환경에 대한 모든 정보를 알고 있는 Model Based 기법이다.

따라서 S, A, P, R, $\gamma$를 알고 있는 상황이다.

이를 활용하여 각 상태에서 가치를 구하여 정책 평가를 한 뒤

이를 활용하여 탐욕적으로 정택을 갱신하여 정책 제어를 한다.

6. 몬테카를로 방법(MC : Monte-Carlo Prediction)

몬테카를로 방법에서는 모델을 알 수 없는 Model Free 에서 사용하는 기법이다.

우선 다음 수식을 보자.

$$v_{\pi}(s) = V(s)\ when\ N(s)\ \rightarrow\ \infty \\ N(s) \leftarrow N(s) + 1 \\ S(s) \leftarrow S(s) + G_t \\ V(s) \leftarrow V(s)/N(s)$$

위와 같이 MC에서는 누적된 반환값을 카운트로 나누어 상태 가치 함수를 구한다.

하지만 위와 같은 방법으로는 프로그램 상에서 비효율적이므로

증분평균(Incremental Mean) 개념을 이용하여 계산한다.

증분 평균이란 평균을 구할 때 이전에 계산한 값을 활용하여 누적 계산하는 방법이다.

$$\begin{matrix} \mu_k &=& {1 \over k} \sum_{j = 1}^k x_j \\ &=& {1 \over k} \left( x_k + \sum_{j = 1}^{k-1} x_j \right) \\ &=& {1 \over k} \left(x_k + \left({k-1 \over k-1}\right) \sum_{j=1}^{k-1} x_j \right) \\ &=& {1 \over k}(x_k + (k - 1) \mu_{k - 1}) \\ &=& \mu_{k-1} + {1 \over k}(x_k - \mu_{k - 1}) \\ &\approx& \mu_k + {1 \over k} \left(x_k - \mu_k \right) \end{matrix}$$

위 식을 이용하여 MC에서 증분평균을 구하면

$$V(s) = V(s) + {1 \over N(s)}(G_t - V(s))$$

가 된다.

최종적으로는 $G_t = V(s)$가 되어 상태가치 함수가 변하지 않는것이 목표이다.

프로그램을 보다 수월하게 하기 위하여 $1/N(s)$을 $\propto$로 변경할 수 있다.

$\propto$은 0과 1 사이의 값의 상수로 고정한다.

$$V(s) = V(s) + \propto(G_t - V(s))$$

7. 시간차 학습(TD : Temporal Difference Learning)과 살사(SARSA)

7.1 TD

MC에서는 에피소드가 완료 된 후에 상태가치 함수를 계산하였다.

이로인해 학습이 느리기 때문에 이를 보완하기 위하여 TD를 정의하였다.

MC에서 정의한 상태 가치 함수 식을 변형해보자.

$$V(s_t) = V(s_t) + \propto(G_t - V(s_t)) \\ V(s_t) = V(s_t) + \propto (R_{t+1} + \gamma V(s_{t+1}) - V(s_t))$$

TD는 에피소드가 끝나지 않아도 계산 가능한 특징때문에

끝이 정해지지 않은 환경에서도 적용 가능하다.

현재상태에서 할 수 있는 행동을 모두 하면서

가장 큰 행동 가치 함수를 찾아 가는 정책을 찾아나가는 것이 TD이다.

7.2 SARSA

TD에서는 정책을 평가할 때 상태 가치 함수를 사용했고

정책 제어시에만 행동 가치 함수를 사용하였다.

하지만 Q함수만으로도 정책을 평가하고 제어하는 것이 가능하다.

$$Q(S, A) = Q(S, A) + \propto (R_{t+1} + \gamma Q(S', A') - Q(S, A))$$

8. Q-learning

8.1 온 폴리시(On Policy)와 오프 폴리시(Off Policy)

SARSA의 경우 정책에 사용되는 정책과 정책을 제어하는 정책이 같았다.

이를 온 폴리시라고 한다.

반면 정책에 사용되는 정책과 정책을 제어하는 정책이 서로 다른 경우를 오프 폴리시라 한다.

8.2 중요도 샘플링(Importance Sampling)

중요도 샘플링이란 기댓값을 계산 할 때 계산하고자 하는 확률 분포를 알지만

그 확률분포의 샘플을 구할 수 없을때 다른 확률 분포에서 구한 샘플로 구하고자 하는 기댓값을 구하는 기법이다.

구하는 방법은 다음과 같다.

$$\sum P(X)f(X) = \sum Q(X) \left[ {P(X) \over Q(X)} f(X) \right]$$

위에서 $P(X)$는 구하고자 하는 기댓값의 확률 분포,

$Q(X)$는 샘플링을 구할 수 있는 확률 분포이다.

8.3 Q Learning

$$Q(S, A) = Q(S, A) + \propto (R_{t+1} + \gamma \underset{a'} \max Q(S', A') - Q(S, A))$$