해당 글은 강화 학습의 개념 전반에 대해 순차적으로 다룰 예정입니다.

이번 포스팅에서는 주어진 환경을 모를 때 최적 정책을 예측하는 Monte Carlo 알고리즘에 대해 설명하겠습니다.

Monte Carlo Algorithm

Monte Carlo Algorithm은 환경에 대한 정보가 주어지지 않은 상황에서 최적 정책을 예측하기 위해 고안된 알고리즘이다.

환경에 대한 정보가 없다는 것은 특정 액션에 대한 보상 $R_s^a$와 상태 천이 함수 $P_{ss'}^a$를 모른다는 것이다. (이 때, 주어진 환경 자체는 MDP가 맞다고 생각하자.) 이 문제를 해결하기 위한 방법으로, 다양한 에피소드를 수행하면서 그 결과를 sampling하여 가치를 계산하는 방법이 제안되었다. 이 방법이 바로 Monte Carlo 알고리즘이다.

Terms

• transit
  특정 상태 $S$에서 액션 $a$를 취해 보상 $R$을 받는 일련의 과정
• episode
  agent가 동작을 시작하여 끝낼 때 까지의 transit의 집합

이제, Monte Carlo 알고리즘을 통해 최적 정책을 계산하는 방법에 대해 더 깊이 생각해보자. 우선 고려해야 할 것은 $v_ t(s)=E[G_t|S_t=s]$가 성립한다는 점이다. 즉, 특정 상태에서의 가치는 해당 상태에서의 리턴의 기댓값이라는 것이다. 결국, 주어진 환경에서 성립하는 에피소드를 반복하면서 경험을 통해 획득한 리턴값을 사용하여 각 상태의 가치를 업데이트하다보면 최적 가치 함수 $v_\pi(s)$를 찾을 수 있다는 것이다. (이 때 하나 주의해야 할 점은 가치 업데이트에 사용하는 리턴값은 반드시 동작이 끝까지 마무리된 에피소드를 사용한 정보여야 한다는 점이다.)

각 상태에서의 리턴값을 통해 가치를 업데이트한다는 사실을 알았으니깐, 이제는 실질적으로 동작하는 식을 사용해서 생각해보자.

$N(s) = N(s)+1\\ S(s)=S(s)+G_t\\ V(s)=S(s)/N(s)\\$

위 식은 각각 상태 $s$에 대해 Monte Carlo Algorithm을 통해 계산한 sample 수, 토탈 리턴값, 그리고 가치(리턴값의 평균)이다.식을 보면 sample이 업데이트될 때 $N(s)$는 1, $S(s)$는 $G_t$만큼 증가하고, $V(s)$는 업데이트된 $N(s)$와 $S(s)$를 통해 계산한 새로운 가치이다.

Monte Carlo Example 1

아래처럼 주어진 에피소드를 따라 동작을 수행한 경우가 존재한다고 가정하자. (이 때, 상태는 1~10과 터미널, 액션은 1~4까지 존재)

$Episode1 : (s_1, a_1, 3)(s_3, a_2, 2) (s_9, a_3, 10) (s_2, a_1, 2) (s_4, a_4, 1)\\ N(s) = 0,\ S(s) = 0,\ V(s) = 0 \ for \ all \ s$

이 에피소드를 따라 에이전트가 동작을 완료했다고 할 때, 각 상태의 리턴값은 마지막 transit부터 역순으로 거슬러 올라가며 계산할 수 있다. $s_4$은 1, $s_2$는 3, $s_9$는 13, $s_3$은 15, $s_1$는 18이 될 것이다. (뒤에서부터 보상을 누적해가며 더하는 간단한 연산이다.) 따라서 해당 에피소드를 수행한 후 각 상태의 가치 $V(s)$는 $V(s_4)=1,\ V(s_2)=3,\ V(s_9)=13,\ V(s_3)=15,\ V(s_1)=18$임을 알 수 있다. (이러한 일련의 계산 과정에서 주의해야 할 점은, 웬만하면 마지막 transit부터 역순으로 계산을 진행하는 것이 효율적이라는 점이다. 이는 감쇠 함수 $\gamma$가 1이 아닌 경우, 정방향보다 역순으로 했을 때의 연산량이 훨씬 적기 때문이다.)

따라서, 이처럼 완료된 에피소드를 통해 획득한 경험을 통해 각 상태의 가치를 업데이트할 수 있는 것이다. 앞에서도 줄곧 언급했지만, 이러한 동작을 반복하며 가치를 업데이트하다보면 가치가 특정 값들로 수렴하게 되는데, 이 값들의 집합이 바로 우리가 찾는 최적 가치 함수 $v_\pi(s)$가 되는 것이다.

First-Visit & Every-Visit

이번에 고려할 사항은 하나의 에피소드에서 동일한 상태를 중복해서 거쳐가는 경우의 조치 방법에 대한 것이다.

앞의 예시를 통해, 우리는 Monte Carlo 알고리즘이 어떻게 동작하는지 이해할 수 있었다. 하지만 이 예시는 매우 기본적인 Monte Carlo 알고리즘의 형태일 뿐이다. 우리가 필요한 것은 이보다 훨씬 복잡한 실제 환경에서의 활용이라는 것을 잊지 말자. 그 목표를 위한 첫 걸음으로, 우리가 생각해볼 것은 하나의 에피소드에서 동일한 상태를 중복해서 지나가는 경우이다.

이 경우 다들 생각할 수 있는 가장 간단한 선택지는 중복에 관계없이 모든 transit에 대한 업데이트를 전부 수행해주는 것이다. 이것이 바로 Every-Visit 방식이다. 한편, 굳이 하나의 선택지를 여러 번 업데이트할 필요는 없을 것이라는 판단으로 첫 번째로 나온 transit만 업데이트 하는 방식이 First-Visit 방식이다. 굳이 이 상황을 두 가지 경우로 나눠서 설명하긴 했지만, 결론부터 말하자면 무슨 방식을 사용하든 우리가 획득하는 최적 가치 함수는 동일하다. 어차피 가치 함수가 수렴하는 수준까지 에피소드를 수행하면 업데이트를 한, 두 번 더 한들 차이가 나지 않게 되는 것이다. 그래서 이렇게 두 개념을 분리시켜서 무슨 이득이 있는지는 잘 모르겠지만, 상황에 따라 최적 가치 함수를 얻는 효율이 달라질 수 있으니 숙지하고 있자.

Incremental Mean

앞의 Monte Carlo 식은 업데이트 해야 할 변수가 3가지나 되기 때문에 계산이 귀찮다. 이 문제를 해결하기 위해 하나의 식으로 해결할 수 있는 Incremental Mean 방식이 고안되었다.

Incremental Mean 방식은 가치에 해당하는 기댓값이 재귀적으로 표현 가능하다는 사실로부터 착안된 방식이다. Incremental Mean 방식의 식은 아래와 같이 도출해낼 수 있다.

$\mu_k = \frac 1k \sum_{j=1}^k x_j\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \frac 1k(x_k + \sum_{j=1}^{k-1} x_j)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\frac 1k(x_k + (k-1)\mu_{k-1})\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\mu_{k-1} + \frac 1k(x_k - \mu_{k-1})\\$

위 식을 Monte Carlo 알고리즘에 대입하면 아래와 같이 나타낼 수 있다.

$V(S_t)=V(S_t) + \frac 1{N(S_t)}(G_t - V(S_t))$

따라서 우리는 위 수식 하나만 사용해도 새로운 가치를 업데이트할 수 있으므로 앞선 수식의 토탈 리턴값에 대한 정보를 계산하지 않아도 되는 것이다. 여기서 더 식을 간단하게 만들 수도 있는데, $\frac 1{N(S_t)}$는 업데이트 횟수를 나눠준 값인데, 해당 항은 learning rate $\alpha$라는 상수로 선언해주어도 기존의 식과 결과 측면에서 차이가 거의 없다. 따라서 최종적으로 우리는 아래와 같은 식을 통해 가치를 계산할 수 있다는 결론을 내릴 수 있다.

$V(S_t)=V(S_t) + \alpha (G_t - V(S_t))$

즉, 이제는 업데이트 전의 가치와 해당 transit의 리턴값만 알고 있으면 바로 가치를 업데이트할 수 있게 된 것이다.

Monte Carlo for Action-Value Evaluation

마지막으로 Monte Carlo 방식을 통해 상태 가치 함수에서 나아가 액션 가치 함수를 계산하는 방법에 대해 이야기 하겠다.

상태 가치 함수 $v(s)$를 계산할 때에는 $N(s), S(s), V(s)$의 3가지 항을 사용해서 가치를 계산했다. 이 방식과 액션 가치 함수의 차이점은 각 항의 매개변수를 $s, a$의 두 가지 항으로 사용한다는 점이다. 즉, $N(s)$는 $N(s, a)$, $S(s)$는 $Q(s,a)$, $V(s)$는 $q_\pi(s, a)$로 변환해서 나타내는 것이다. 이 때 주의해야 할 점은, 매개변수가 2개이므로 $s$와 $a$가 모두 같은 $N(s,a), Q(s, a), q_\pi(s, a)$를 업데이트 해줘야 한다는 것이다. 물론 액션 가치 함수 역시 기존의 Monte Carlo 방식과 마찬가지로 Incremental Mean 방식으로 아래처럼 나타낼 수 있다.

$q_\pi(s_1, a_2) = q_\pi(s_1, a_2) + \alpha (G_t - q_\pi(s_1, a_2))$