강화학습 기초 다지기 (2) - 강화학습 문제 풀이 기법 (DP, MC, TD)

강화 학습은 최적 가치 함수를 찾거나 그것을 만드는 좋은 정책을 찾는 것을 목표로 한다. 하지만 이는 쉽지 않다. 이를 풀기 위한 여러 가지 방법이 있는데 유명한 방법 몇 개만 정리한다.

 

첫 번째로 환경에 대해서 알 때 동적 계획법(Dynamic Programming: DP) 방법을 사용할 수 있다. '환경'에 대해서 안다는 것은 상태와 행동에 대한 보상 함수 R과 상태천이 행렬 P를 안다는 의미다. 이는 현실적이지 않다는 단점이 존재하지만 매우 효율적이고 문제를 해결하기 쉽다는 장점이 있다. 

동적 계획법은 큰 문제를 분할한 작은 문제의 최적 값이 큰 문제에서도 최적 값이어야 한다. 또한 큰 문제의 해를 구하기 위해서, 작은 문제의 최적 해를 재사용할 수 있어야 한다. 이때, 정책 평가(Policy Evaluation: PE), 정책 개선(Policy Improvement: PI)을 사용하여 해결한다.

정책 평가 알고리즘은 $ V_{0}^{\pi}(s) $에서 시작하며, 반복해서 $ V_{t+1}^{\pi}(s) \leftarrow \sum_{a \in \textit {A}} \pi(a|s) (R_{s}^{a} + \gamma \sum_{s' \in S} P_{ss'}^{a} V_{t}^{\pi} (s')) $를 만들어내며 $ V_{t}^{\pi}(s) $와 비교하여 error가 일정 이하일 때까지 반복하는 것을 실행한다. 여기서 가치 함수 $ V^{\pi}(s) $를 받아 정책 개선 알고리즘을 실행한다. 정책 개선 알고리즘은  $ Q^{\pi}(s, a) = R_{s}^{a} + \gamma \sum_{s' \in S} P_{ss'}^{a} V^{\pi} (s') $를 이용해 $Q^{\pi}(s, a)$를 계산하고 이를 이용해 정책 $ \pi $를 $ \pi^{'} $로 업데이트한다. 마지막으로 이 두 알고리즘을 계속 반복하는 것을 정책 반복(Policy iteration)이라고 부른다. 정책 개선 정리로 얻은 개선된 정책 $ \pi^{'} $이 $ \pi $ 보다 더 좋다는 것은 정책 개선 정리에 의해 증명되어 있으나 여기서는 생략한다. 정책 평가 알고리즘이 과연 유일한 하나의 값으로 수렴할까 의문이 들 수 있는데 이 또한 바나흐 고정점 정리에 의해 증명될 수 있다.

 

한편 환경(R, P)에 대해 모르는 대부분의 현실적 상황에서는 동적 계획법을 사용할 수 없다. 이때는 Monte Carlo(MC), Temporal-Difference(TD) 같은 방법을 사용할 수 있다. TD기법은 현재 상태가 다음 상태에 영향을 주는 방법으로 Bootstrap 방법이다. 한편 MC 방법은 직접 계산하기 어려운 값을 많은 시행을 통해 추산하는 방법이다.

 

먼저 MC 방법은 $G_{t}$를 여러 번 시뮬레이션해서 그 시뮬레이션 값의 평균을 계산하면 $ V_{\pi}(s) $와 비슷해진다는 점을 이용하는 것이다. MC는 불편 추정기법이라 시뮬레이션 횟수가 적으면 추정치의 불확실성이 커지며 횟수가 늘어날수록 분산이 줄고 참 값과 같아진다. 시뮬레이션 하나하나를 에피소드라고 부르며 에피소드마다 (상태, 행동, 보상)을 정책 $ \pi $를 이용해 생성한다. 이를 이용해 각 state에 대한 평균을 구해 $ V^{\pi}(s) $를 계산한다. MC를 여러 번 반복할 때 기존의 $ G_{t} $를 이용해야 하므로 메모리가 많이 필요할 수 있다. 그래서 다음과 같은 방법을 사용한다.

$$ \begin {align*} \mu_{k} &= \frac {1}{k} \sum_{j=1}^{k} x_{j} \\ &= \frac {1}{k} (x_{k}+\sum_{j=1}^{k-1} x_{j}) \\ &= \frac {1}{k} (x_{k}+(k-1)\mu_{k-1}) \\ &= \mu_{k-1} + \frac {1}{k} ( x_{k} - \mu_{k-1})   \end {align*} $$

이는 기존에 알던 지식 + 새로 알게 된 지식으로 해석할 수 있다. 기존 지식을 다 저장하지 말고 $\mu_{k-1}$만 알고 있다면 메모리를 많이 쓰지 않을 수 있다. MC 방법은 환경에 대한 지식이 필요 없고 직관적이라는 장점이 있다. 다만 episode가 끝나야 적용할 수 있고, 각 상태와 행동의 관계에 대해 전혀 활용하지 않으며 정확한 값을 얻기 위해서는 시뮬레이션을 여러 번 반복해야 한다는 단점이 존재한다.

 

세 번째로, Temporal-Difference(TD) 방법은 현재 알고 있는 값을 활용해 모르는 값을 추정하는 방법이다. MC와 같이 환경에 대한 지식이 필요 없으며, DP처럼 각 상태와 행동의 관계를 최대한 이용해 계산량을 줄일 수 있다는 장점이 있다. 대신 불편 추정량은 아니고 markovian을 가정하므로 추산 오차가 발생할 수 있다. MC 비해서는 추정치의 분산이 낮아 빠른 속도로 좋은 추정치를 얻을 수 있다.

MC 방법과 달리 markov를 가정하여 $ G_{t} = R_{t+1} + \gamma V(S_{t+1}) $으로 Return을 구할 수 있다. 이런 경우를 1-step TD라고 부르며 n-step TD의 경우 $ G_{t}^{(n)} = R_{t+1} + \gamma R_{t+2} +.. + \gamma ^{n-1} R_{t+n} + \gamma^{n} V(S_{t+n}) $ 로 나타낼 수 있다. Return을 이용하여 $ V(s) \leftarrow V(s) + \alpha (G_{t} - V(s)) $ 로 가치 함수를 업데이트한다. 이 식은 MC에서도 사용할 수 있는데, 적당히 작은 $ \alpha $에 대해 참값으로 수렴함이 증명되어 있다. 식을 보면 $ V(s) $가 $ R_{t+1} + \gamma V(S_{t+1}) $에 가깝게 만드는 것이 목표다.