[강화학습] 06 - 몬테카를로와 시간차 예측

개요 

이전 포스팅에서 강화학습은 환경의 모델 없이 환경과의 상호작용을 통해 최적 정책을 학습한다고 했습니다.

 

이때 에이전트가 환경과의 상호작용을 통해 주어진 정책에 대한 가치함수를 학습하는 것을 "예측"이라고 하고, 가치함수를 토대로 정책을 끊임없이 발전시켜 나가서 최적 정책을 학습하려는 것을 "제어"라고 합니다.

 

지금까지의 내용을 잘 이해했다면, 예측과 제어가 각각 앞에서 배운 정책 이터레이션의 정책 평가와 정책 발전과 비슷하다는 걸 느낄 수 있을 것입니다. 하지만 정책 이터레이션에서는 가치함수나 최적 정책을 계산을 통해 구했다면, 강화학습에서는 에이전트가 겪은 경험으로부터 가치함수를 업데이트합니다.

 

강화학습은 일단 해보고 → 자신을 평가하며 → 평가한 대로 자신을 업데이트하는 과정을 반복합니다.

 

강화학습의 이해를 돕기 위해 정책 이터레이션과 강화학습의 공통점과 차이점을 표로 만들었습니다. 

	정책 이터레이션	강화학습
공통점	현재 정책의 가치함수를 이용해서 정책을 발전시키며 최적 정책을 찾으려고 함
차이점	계산을 통해서 가치함수를 알아냄  계산을 반복함으로써 정확한 참 가치함수 값을 얻음(다이내믹 프로그래밍) 정책 평가와 정책 발전을 합친 것을 정책 이터레이션이라 부름	에이전트가 겪은 경험으로부터 가치함수 업데이트 적당한 추론을 통해 원래 참 가치함수의 값을 예측 예측과 함께 정책을 발전시키는 것을 제어라고 부름

 

이런 강화학습의 예측에는 몬테카를로 예측과 시간차 예측이 있으며, 제어에는 시간차 제어인 살사 그리고 오프폴리시 제어인 큐러닝이 있습니다. 

 

이들은 강화학습의 고전 알고리즘들이지만 수많은 알고리즘의 토대가 되었기 때문에 이 알고리즘들의 차이와 한계를 아는 것은 중요합니다. 

 

이번 포스팅에서는 몬테카를로 예측과 시간차 예측에 대해서 알아보려고 합니다.

 

 

---

몬테카를로 예측

몬테카를로 예측은 몬테카를로 근사를 사용하기 때문에 먼저 몬테카를로 근사가 무엇인지 알아야합니다.

 

몬테카를로 근사

몬테카를로 근사란 무작위로 무엇인가를 해서 원래의 값에 대해 추정하는 것입니다. 예를 들어 아래의 그림에서 사각형 B의 넓이(S(B))를 알고 원의 넓이를 구하는 방정식을 모를 때 4분원 A의 넓이(S(A))를 구한다고 쳐봅시다.

 

저희는 그림 위로 빨간 점들을 계속 뿌린 뒤, 전체 뿌린 점들 중에서 4분원 A에 들어간 점의 비율을 이용하여 S(A)/S(B)를 근사하고 A의 넓이를 구할 수 있습니다. 이때 뿌린 점 하나하나가 "샘플"이고 점을 뿌리는 것을 "샘플링"이라고 합니다.

 

샘플링(점을 뿌리는 것)을 500번 했다고 가정했을 때, 4분원 안에 들어간 샘플(점)이 400개라면 $\frac{S(A)}{S(B)}$는 $\frac{4}{5}$가 될 것입니다.

 

당연한 소리지만 저희는 아래 그림처럼 점을 더 많이 뿌릴수록, 즉 샘플링(n)의 횟수를 늘릴수록 S(A)/S(B)가 원래의 값과 더 근사하게 될 것입니다.  

출처 - 위키백과

그리고 샘플링(n)을 무한으로 한다면 샘플링한 값의 평균은 원래의 값과 동일해질 것입니다. 이를 식으로 나타내면 다음과 같습니다. $$if \ n → ∞, then$$ $$\frac{1}{n}\sum_{i = 1}^{n}I(red\_dot_i ∈ A) = \frac{S(A)}{S(B)}$$

 

몬테카를로 근사의 장점은 방정식을 몰라도 원래 값을 추정할 수 있다는 것입니다. 어떤 괴상한 도형이 나와도 샘플링을 많이 한다면 그 도형의 넓이를 근사할 수 있는 것이죠. 

 

저희는 이 몬테카를로 근사의 장점을 강화학습에 사용하려고 합니다. 강화학습에서는 환경의 모델을 모르기 때문에 가치함수의 식을 정확히 알지 못합니다.

 

따라서 저희는 몬테카를로 근사를 사용해서 가치함수를 추정할 것입니다. 

 

샘플링과 몬테카를로 예측

모르는 도형의 넓이를 구할 때 점을 뿌리는 것이 샘플링이었다면, 강화학습에서는 에이전트가 환경에서 에피소드를 한 번 진행하는 것이 샘플링입니다. 이 샘플링을 통해 얻은 샘플의 평균으로 참 가치함수의 값을 추정합니다. 이를 몬테카를로 예측이라고 합니다. 

 

가치함수의 정의는 현재 상태에서 앞으로 받을 보상의 기댓값입니다. $$v_π(s) = \sum_{a∈A} π(a | s) (r(s,a) + γ\sum_{s'∈S}P_{ss'} ^a v_π(s'))$$

정책 이터레이션에서는 위의 식인, 가치함수를 변형한 벨만 기대 방정식을 이용해서 참 가치함수를 구했습니다. 하지만 저희는 환경의 모델인 보상함수($r(s,a)$)와 상태 변환 확률($P_{ss'}$)을 모르기 때문에 가치함수 값을 정확히 구할 수 없을 뿐더러 강화학습에서는 계산을 사용하지 않습니다. 

 

계산을 하지 않고 현재 정책에 따른 가치함수를 구하려면 현재 정책에 따라서 계속 행동해 보면 됩니다. 행동을 하면 그에 따른 보상을 받을 것이고 받은 보상들을 할인해서 더한 값을 우리는 반환값이라고 배웠습니다.  $$G_t = R_{t+1} + γR_{t+2} + ... + γ^{T-t+1}R_T$$ 이 반환값들의 평균값을 이용해서 참 가치함수를 추정하는 것이죠.

 

반환값은 에피소드 동안 지나쳐 왔던 각 상태마다 존재합니다. 예를 들어 아래 그림과 같이 첫 번째 에피소드에서 에이전트가 상태 $s_1, s_2, s_3$를 지나쳐 마침 상태 T로 왔다면 반환값은 지나쳐 왔던 $s_1, s_2, s_3$에 각각 존재하는 것이죠.

 

$$G(S_1) = r_1 + γr_2 + γ^2 r_3$$ $$G(S_2) = r_2 + γr_3$$ $$G(S_3) = r_3$$

각 상태에 대한 참 가치함수를 반환값들의 평균값을 이용해서 추정하기 때문에 특정 상태에서의 반환값이 많이 모여야 합니다. 그럴려면 당연히 에이전트는 많은 에피소드를 진행 즉 샘플링(n)을 많이 해야겠죠.

 

여러 번의 에피소드에서 s라는 상태에서 반환값의 평균을 이용해 참 가치함수를 추정하는 식은 다음과 같습니다. $$v_π(s) ∽ \frac{1}{N(s)}\sum^{N(s)}_{i = 1}G_i(s)$$ N(s)는 상태 s를 에피소드 동안 방문한 횟수입니다. $G_i(s)$는 그 상태를 방문한 i번째 에피소드에서의 s의 반환값입니다. 

 

 

위 그림은 상태 $s_1$을 지나는 에피소드의 반환값을 나타낸 것입니다. 총 4개의 에피소드에서 상태 $s_1$를 방문했으므로 이 상태에서 추정된  $s_1$의 참 가치함수 $v_π(s_1)$는 $\frac{G_i(s_1) + G_2(s_1) + G_3(s_1) + G_4(s_1)}{4}$가 됩니다. 물론!! 참 가치함수에 근사하기 위해서는 더 많은 반환값들이 필요하겠죠.

 

참 가치함수를 추정하는 식을 자세히 살펴봅시다. 편의한 상태에 대한 표현은 생략하고, n개의 반환값을 통해 평균을 취한 가치함수를 $V_{n+1}$이라고 해봅시다.

 

가치함수가 대문자인 이유는 참 가치함수가 아닌 오차가 포함된 가치함수라는 의미입니다. 추정된 가치함수 $V_{n+1}$를 현재 받은 반환값 $G_n$과 이전에 받았던 반환값의 합 $\sum^{n-1}_{i = 1}G_i$를 더한 값의 평균으로 바꿀 수 있습니다. $$V_{n+1} = \frac{1}{n}\sum^{n}_{i = 1}G_i = \frac{1}{n}(G_n + \sum^{n-1}_{i = 1}G_i)$$

이전 반환값들의 합 $\sum^{n-1}_{i = 1}G_i$을 n-1을 곱하고 나눠도 원래 식은 유지됩니다. $$V_{n+1} =\frac{1}{n}\sum^{n}_{i = 1}G_i = \frac{1}{n}(G_n + (n-1)\frac{1}{n-1}\sum^{n-1}_{i = 1}G_i)$$

$\frac{1}{n-1}\sum^{n-1}_{i = 1}G_i$은 이전의 가치함수 $V_n$입니다. 따라서 이를 치환하고 식을 정리하면 수식이 다음과 같아집니다.

$$V_{n+1} = \frac{1}{n}(G_n + (n-1)V_n)$$ $$ = V_n + \frac{1}{n}(G_n - V_n)$$ 최종적으로 다음 수식이 가치함수의 업데이트 식이 됩니다. $$V(s) \leftarrow V(s) + \frac{1}{n}(G(s) - V(s))$$ 이 식은 에피소드를 진행하다가 어떤 상태 s에 새로운 반환값이 들어오면 원래 가지고 있던 가치함수 $V(s)$에 $\frac{1}{n}(G(s) - V(s))$을 더함으로써 업데이트한다는 뜻입니다.

 

수식에서 $G(s) - V(s)$를 오차라고 하며 $\frac{1}{n}$은 스텝사이즈로서 일반적으로 $α$라고 표현하며 업데이트할 때 오차의 얼마를 가지고 업데이트할지 정하는 것입니다. 

 

스텝사이즈는 $\frac{1}{n}$처럼 시간에 따라 변할 수도 있고, 변하지 않는 일정한 숫자일 수도 있습니다. 샘플링 횟수(n)가 많아질수로 스텝사이즈($α$)가 작아지므로 현재 얻은 반환값이 과거에 얻은 값에 비해 업데이트에 끼치는 영향이 작아지게 됩니다. 

 

따라서 현재 에피소드로부터 얻은 반환값을 중요하게 보는 경우 스텝사이즈를 상수로 고정시킵니다. 이 책에서는 스텝사이즈를 상수로만 사용합니다.

 

아래 그림에서 알 수 있듯이 가치함수 입장에서 업데이트를 통해 도달하려는 목표는 현재 얻은 반환값입니다. 하지만 한 번에 목표점으로 가는 것이 아니라 스텝사이즈를 곱한 만큼만 가는 것이죠. 

1. $G(s) = $업데이트 목표

2. $α(G(s) - V(s)) = $업데이트의 크기

 

하나의 에피소드에서 에이전트가 마침 상태에 도착하면 에이전트는 지나온 모든 상태의 가치함를 위의 식을 이용해서 업데이트합니다.

 

이후 에이전트는 새로운 에피소드를 진행하고 이러한 과정을 반복하면서 상태들의 참 가치함수를 추정하는 것이 몬테카를로 예측입니다.  

 

이런 몬테카를로 예측에는 하나의 큰 단점이 존재하는데 그것은 가치함수를 업데이트하려면 하나의 에피소드가 끝날 때까지 기다려야 한다는 것입니다.

 

가치함수를 업데이트할 때 반환값을 이용했는데, 이 반환값은 에피소드가 끝나야지만 계산할 수 있기 때문입니다.

 

만약 에피소드의 끝이 없거나 에피소드의 길이가 긴 경우에는 이 몬테카를로 예측은 적합하지 않는 것이죠. 이 단점을 보완한 것이 바로 시간차 예측입니다.

 

시간차 예측

몬테카를로 예측의 단점을 보완하기 위해서 시간차 예측은 타임스텝마다 가치함수를 업데이트합니다.

 

저희는 앞에서 가치함수 식을 변형할 때 반환값 $G_t$를 $R_{t+1} + γv(S_{t+1})$로 바꾸어서 사용하였습니다.

 

이처럼 몬테카를로 예측이 반환값 $G_t$를 사용한 것을, 시간차 예측에서는 $R_{t+1} + γv(S_{t+1})$식을 샘플링해서 현재의 가치함수를 업데이트합니다. 이 식을 이용한다면 에피소드가 끝날 때까지 기다릴 필요가 없겠죠.

 

반환값 $G_t$가 $R_{t+1} + γv(S_{t+1})$로만 바뀌었기 때문에 가치함수의 업데이트 식도 몬테카를로 예측의 가치함수 업데이트 식에서 반환값 $G_t$만 $R_{t+1} + γv(S_{t+1})$로 바꿔주면 됩니다. $$V(S_t) \leftarrow V(S_t) + α(R_{t+1} + γV(S_{t+1}) - V(S_t))$$ 달라진 점은 시간차 예측에서는 가치함수의 업데이트가 실시간으로 이뤄지며 한 번에 하나의 가치함수만 업데이트한다는 점입니다.

 

시간차 예측에서의 업데이트 목표와 크기는 다음과 같습니다.

 

시간차 예측의 가치함수 업데이트

1. $R_{t+1} + γV(S_{t+1}) = $업데이트 목표

2. $α(R_{t+1} + γV(S_{t+1}) - V(S_t)) = $업데이트의 크기

 

$R_{t+1} + γV(S_{t+1}) - V(S_t)$을 시간차 에러라고 합니다. 시간차 예측에서 업데이트의 목표는 반환값과 달리 실제의 값이 아닙니다. $V(S_{t+1})$을 사용하는데 이 값은 참 가치함수가 아닌 단지 현재 에이전트가 참이라고 예측하고 있는 값을 가져다 쓰기 때문입니다. 

 

이렇게 다른 상태의 가치함수 예측값을 통해 지금 상태의 가치함수를 예측하는 이러한 방식을 부트스트랩이라고 합니다. 

 

에이전트는 어떤 상태에서 행동을 하면 보상과 다음 상태를 알게 됩니다. 시간차 예측은 다음 상태의 가치함수 예측값과 알게 된 보상을 이용해서 상태의 가치함수를 업데이트합니다. 이후 또다시 행동을 선택하고 이 과정이 반복되면서 참 가치함수를 추정하게 됩니다.

 

시간차 예측은 많은 샘플링을 통해서 업데이트하면 많은 경우 몬테카를로 예측보다 더 효율적으로 빠른 시간 안에 참 가치함수에 근접합니다. 하지만 초기 가치함수 값에 따라 예측 정확도가 많이 달라진다는 단점이 있습니다.

 

---

지금까지 저희는 주어진 정책에 대한 가치함수를 학습하는 2가지 예측 방법에 대해서 알아봤습니다.

 

다음 포스팅에서는 이 방법들을 이용해서 강화학습에서 에이전트가 어떻게 정책을 발전시키고 최적 정책을 학습하는지에 대해서 설명하고 실제 강화학습 알고리즘인 살사에 대해서 그리드월드 코드예시와 함께 살펴보겠습니다.

 

오늘도 끝까지 읽어주셔서 감사합니다~!!

 

 

http://www.yes24.com/Product/Goods/44136413

파이썬과 케라스로 배우는 강화학습 - YES24

※ 이 글은 위의 책 내용을 바탕으로 작성한 글입니다.