Model-Free Policy Evaluation, Monte Carlo와 Temporal Difference에 대하여

이번 포스팅과 다음 포스팅은 유한개의 상태, 유한개의 행동에 대해 환경 모델을 모를 때, sequential decision process를 푸는 방법에 다룹니다. 지난 DP 포스팅에서, policy iteration을 이용하여 MDP를 풀었습니다. 마찬가지로 환경 모델을 알지 못한 경우도 유사하게 접근할 수 있습니다. policy iteration은 policy evaluation과 policy control로 나뉘는데 이번 포스팅은 policy evaluation을 푸는 방법에 다룰 것이고 다음 포스팅은 policy control에 대해 다루도록 하겠습니다. CS234 3강, Deep Mind의 David Silver 강화학습 강의 4강, Richard S. Sutton 교재 Reinforcement Learning: An Introduction의 Chapter 5, 6 기반으로 작성하였습니다.

policy evaluation은 현 정책이 얼마나 좋은지 평가하는 것으로, 현 정책 아래 가치함수를 구하는 것입니다. DP는 환경 모델을 알 때, 벨만 기대 방정식을 이용하여 iterative한 방법으로 현 정책 아래에서 가치함수를 구하는 과정입니다. 현 상태에서 특정 행동을 취할 때, 나올 수 있는 다음 상태와 받을 보상을 알고 있기 때문에 아래 식과 같이 expectation을 직접 “계산”을 할 수 있었습니다.

(이러한 이유로, DP는 learning이 아니라 planning이라 했었습니다.) 그러나 환경 모델을 알지 못할 때, 즉, 상태 변환 모델과 보상 모델을 알지 못할 때 어떻게 정책을 평가할 수 있을까요? 바로 경험(experience)을 직접하는 것입니다. 시퀀스를 직접 밟아 나가면서 가치함수를 학습해 나가는 것입니다. 이 때, 경험을 통해 가치함수를 학습하는 방법을 두가지가 있습니다. Monte Carlo 방식와 Temporal Difference 방식입니다. 먼저, Monte Carlo policy evaluation 부터 알아보겠습니다.

Monte-Carlo Policy Evaluation

Monte-Carlo Policy Evaluation을 살펴보기 전에, Monte-Carlo 방식을 우선 알아보겠습니다.

Monte-Carlo Methods

Monte-Carlo 방법은 무작위 샘플링을 통해 우리가 알아보고자 하는 시스템의 분포를 추정하는 것입니다. 아래 그림은 Monte-Carlo 방식으로 원의 넓이를 추정하는 것입니다.

원의 넓이를 구하는 방법이 너무나 복잡하거나 알 수 없다고 가정해 봅시다. 이런 상황에서 원의 넓이를 가장 쉽게 구하는 방법은 점을 무수히 많이 뿌려본 뒤, 사각형의 넓이 $\times$ (원 안에 들어온 점의 갯수 / 전체 점의 갯수) 로 원의 넓이를 추정할 수 있습니다. 이처럼 Monte-Carlo방식은 점을 무수히 많이 찍는 것처럼 무작위 샘플링으로 데이터를 많이 수집하게 되면 우리가 알고자 하는 시스템의 분포를 추정할 수 있다는 개념입니다.

Monte-Carlo Policy Evaluation

따라서, Monte-Carlo Policy Evaluation이란 에이전트가 환경과 직접 상호작용하여 상태, 행동, 보상으로 이뤄진 시퀀스를 무수히 많이 sampling하여 경험을 얻고, 그 경험을 바탕으로 가치함수를 구하는 것입니다. 즉, 무작위 샘플링을 통해 환경 모델을 내재적으로 추정하는 것이죠. ‘내재적’이라 표현한 이유는 추정하고자 하는 것이 상태 변이 확률 또는 보상 확률이 아니라 value function이기 때문입니다. 결국 value function를 구하기 위해선 환경 정보를 알고 있어야 구할 수 있는데(DP에서의 Policy Evaluation 참고) 샘플링을 통해 이를 구하는 것이 내재적으로 환경모델을 추정하는 거라고 생각할 수 있는 것이죠.

다시 정리하면 Monte-Carlo 방식은 환경에 대한 정보없이, 오로지 ‘경험(experience)’를 통해 학습하는 것입니다.

사실 학습은 policy evaluation과 policy control의 상호작용으로 이뤄집니다. 본 포스팅은 학습이라 표현하지만, policy evaluation에 초점을 맞춰 작성하였습니다.

value function의 정의를 다시 살펴보면,

상태 s에서의 return $G_t$ 에 대한 기댓값입니다. Monte-Carlo 방식으로 value function을 구하면 샘플링한 많은 경험들 중에서 상태 s에서부터의 return $G_t$ 를 직접 구한 뒤, 경험의 갯수만큼 나눠주면 됩니다. 즉, return에 대한 기댓값이 아니라 return에 관한 평균값입니다.

Monte-Carlo policy evaluation uses empirical mean return instead of expected return. In other words, Policy is evaluated based on averaging sample returns.

아래 예시를 통해, 어떻게 계산하는지 알아봅시다.

<그림 2>와 같이, C1에서 시작한 시퀀스들에 대한 return 값들이 있습니다. $s_t = C1$ 의 value function을 Monte-Carlo 방식으로 추정하면 (-2.25-3.125-3.41-3.20)/4 = -3.0 이 됩니다.

그러나 Monte-Carlo 방식으로 가치함수를 추정하려면 샘플 시퀀스인 episode가 끝나야 합니다. 즉, 모든 에피소드가 끝나야 Monte-Carlo 방식을 적용할 수 있습니다. 따라서 에피소드가 끝날 때 까지 기다린 후, 평균값을 업데이트하는 방식으로 적용할 수 있습니다.

first-visit MC vs. every-visit MC

Monte-Carlo 방식은 두 가지가 있습니다. first-visit MC와 every-visit MC입니다. 한 에피소드에서 같은 상태를 여러번 반복해서 지나갈 수 있습니다. 이 때, 첫번째 상태에 대한 return값만 value function 업데이트에 이용하고, 나머지는 무시하는 방법이 first-visit MC이고 모든 경우를 고려한 것이 every-visit MC입니다. 아래 그림은 first-visit MC policy evaluation과 every-visit MC policy evaluation 순서입니다.

일반적으로 first-visit MC를 많이 씁니다. 그렇다면 first-visit과 every-visit은 어떤 차이가 있을까요? first-visit MC 같은 경우, 각 상태에 대한 return들은 모두 독립입니다. 왜냐하면 샘플링된 episode가 독립이므로 first-visit만 고려하기 때문에, 각 상태에 대한 return $G_t$ 은 서로 관련이 없고 독립입니다. 즉, 상태 s에 대한 return $G_t$ 는 $v_\pi(s)$ 분포에서, i.i.d성질을 지니게 됩니다(independent and identically distributed). 따라서, 대수 법칙(law of large numbers)에 따라, 상태 s에 대한 return 값을 무수히 많이 샘플링 하게 된다면, return에 대한 평균은 우리가 구하고 싶은 상태 s의 value function 기댓값인 $\mathbb{E_\pi}[G_t \mid s_t=s]$ 에 수렴합니다.

쉽게 다시 설명하겠습니다. 어떤 상태 s에 대한 가치를 구할 때마다 항상 다르게 나올 수 있습니다. 그런데 충분히 많이 상태 s를 밟는다면 대표적으로 많이 나오는 값이나 그 값 주변 값이 자주 등장하겠지요. 즉, 우리는 $v_\pi(s)$ 가 분포를 이룬다고 생각할 수 있습니다. 그런데 우리가 구하고 싶은 건 분포안에서 $v_\pi(s)$ 를 대표하는 값을 찾고 싶은 것입니다. 즉, 자주 등장하는 값을 말입니다. 따라서, 그 분포의 평균인 기댓값 $\mathbb{E_\pi}[G_t \mid s_t=s]$ 을 말입니다. first-visit MC 방식으로 샘플링한 $G_t$ 는 i.i.d성질을 띄기 때문에, 분포를 정확히 모르지만(분포를 안다면 굳이 샘플링 하지 않고 바로 기댓값이 계산이 가능하겠죠?) 결국 $v_\pi(s)$ 분포를 추정할 수 있고, 이는 우리가 구하고 싶은 기댓값에 수렴할 수 있음을 의미합니다.

따라서, first-visit MC 방식에 의한 추정은 unbiased한 성질을 지닙니다. 반면에, every-visit MC 방식에 의한 추정은 biased한 성질을 띕니다. 한 에피소드 내에서 같은 상태를 여러 번 반복해서 지나갔다면, 그 상태들 간은 독립적이지 않고, 상관관계를 가지게 됩니다. 따라서, i.i.d하지 않기 때문에 biased합니다. 그렇기 때문에 MC 방식에 의한 policy evaluation은 first-visit MC를 선호하는 편이라 합니다(sutton and barto교재 및 stanford강의 참고).

Incremental Monte-Carlo Updates

Value function을 업데이트하는 방식을 에피소드가 끝날 때마다 마치 온라인 방식처럼 순차적으로 업데이트할 수 있습니다. 시퀀스 $x_1, x_2, \dots$ 에 대한 평균 $\mu_1, \mu_2, \dots$ 가 있을 때,

입니다. 따라서, episode $S_1, A_1, R_2, \dots, S_T$ 가 끝날 때마다 아래와 같이 업데이트 할 수 있습니다.

두번째 식을 마치 $\left(G_t-V(S_t)\right)$ 를 새로운 데이터와 기존 평균과의 오차 즉 에러항으로 본다면, 기존 평균값을 오차의 방향으로 1/k만큼 수정해 나간다고 해석할 수 있습니다.

위의 업데이트 방식은 맨 처음에 샘플한 에피소드부터, 가장 최근에 샘플한 에피소드까지 모두 중요하게 생각함을 의미합니다. 왜냐하면 동등하게 에피소드 개수만큼으로 나누고 있기 때문입니다. 하지만 시간에 따라 조금씩 변하는 문제 같은 경우(non-stationary)에 위와 같은 업데이트 방식은 적합하지 않습니다. 따라서, 새 에피소드와 기존 평균사이의 오차를 항상 일정 크기만큼 업데이트하여 시간이 지날수록 오래된 과거는 잊고 가장 최근 사건을 좀 더 기억할 수 있게끔 해줍니다.

Temporal-Difference Policy Evaluation

다음은 Temporal-Difference Policy Evaluation에 대해 알아보겠습니다. Temporal-Difference(TD) 도 Monte-Carlo(MC) 와 마찬가지로 환경 모델을 알지 못할 때(model-free), 직접 경험하여 Sequential decision process 문제를 푸는 방법입니다. Temporal-Difference 학습은 Monte-Carlo와 Dynamic Programming을 합쳐 놓은 방식입니다. MC처럼, 환경모델을 알지 못하기 때문에 직접 sampling한 데이터를 통해 학습을 해야 합니다. DP처럼, 에피소드가 끝날 때까지 기다리지 않고 다른 가치 추정치를 가지고 현재 상태 가치를 추정합니다. 이를 bootstrap이라 합니다.

TD는 MC와 다르게 무한한 에피소드에 대해서도 적용할 수 있습니다. 그 이유는 MC는 업데이트를 하기 위해서 한 에피소드가 끝날 때까지 기다려야 합니다. 그래야 return $G_t$ 를 구한 뒤, 업데이트를 할 수 있기 때문입니다. 따라서, MC는 에피소드 샘플링을 통해 실제 return $G_t$ 을 향해 $V(S_t)$ 를 수정해나갑니다.

반면에, TD는 에피소드가 끝날 때까지 기다릴 필요 없이, 다음 상태를 밟을 때까지만 기다렸다가 업데이트합니다. 그렇기 때문에 에피소드가 끝나지 않는 시퀀스에 대해서도 적용할 수 있으며, 시퀀스를 밟아나가면서 그때그때 가치함수를 수정해 나갈 수 있습니다. 이러한 특징으로 인해, TD 방법은 online learning이 가능합니다. 이 부분이 TD의 매우 큰 장점입니다.

TD policy evaluation을 상세히 살펴보면, DP에서의 벨만 기대 방정식을 이용한 policy evaluation과 유사한 것을 보실 수 있습니다.

그러나 DP는 환경모델을 알기 때문에, 다음 상태가 될 수 있는 모든 후보들을 고려하여 가중 평균을 한 추정값으로 다음 상태의 가치 추정값만을 가지로 현재 상태의 가치를 업데이트합니다. 반면에, TD는 환경에 대한 정보가 없기 때문에 다음 상태까지 직접 밟아보는 것입니다. 이것을 ‘다음 상태 s’를 직접 샘플링하였다’라고 합니다. 그러나 DP처럼 다른 상태의 추정값을 가지고 현재 상태값을 수정하고자 합니다. 이를 bootstrap이라 합니다. 즉, TD에서의 bootstrap은 아래 그림 처럼 이해할 수 있습니다.

따라서, MC는 실제 return $G_t$ 를 향해 $V(S_t)$ 를 수정해 나가지만 TD는 estimate $G_t$ 을 향해 $V(S_t)$ 를 고쳐나가면서 시퀀스를 진행합니다.

• MC Policy Evaluation :
  update value $V(S_t)$ toward actual return $G_t$
• TD Policy Evaluation :
  update value $V(S_t)$ toward estimated return $R_{t+1} + \gamma V(S_{t+1})-V(S_t)$

General form of update rule

위의 MC/TD 업데이트 식은 일반적으로 아래와 같은 형태를 띕니다.

$\left[Target - OldEstimate\right]$ 는 오차를 나타냅니다. MC와 TD 모두 Target을 향해 기존 Estimate을 업데이트합니다. 그러나, 기존 estimate을 새로운 target으로 교체하는 건 위험합니다. 왜냐하면 초기단계에서는 새로운 target이 우리가 찾는 정답이 아닐 수도 있기 때문에, target과 기존 estimate의 오차의 일부만큼만 조금씩 수정해 나갑니다. MC target은 $G_t$ 이고, TD target은 $R_{t+1}+\gamma V(S_{t+1})$ 입니다. 또한, MC error는 $G_t - V(S_t)$ 이고, TD error는 $R_{t+1}+\gamma V(S_{t+1}) - V(S_t)$ 입니다. 보통 TD error는 $\delta_t$ 로 표현합니다. 왜냐하면, 같은 에피소드 내에서, TD error는 매 t step마다 다르기 때문입니다.

Temporal Difference Policy Evaluation Algorithm

TD policy evaluation 알고리즘 순서도는 아래와 같습니다.

일정 정책 $\pi$ 아래, (S, A, R, S’)를 샘플링하고, 업데이트합니다. 그런 다음 (S’, A’, R, S’‘)를 샘플링하고 업데이트합니다. 이 과정을 V(S)가 수렴할 때까지 반복합니다. 여기서 한가지 의문점이 있습니다. MC방식은 unbiased estimator이기 때문에 대수의 법칙에 따라, true expected estimate에 수렴한다고 하였습니다. 과연 TD방식은 수렴할까요? 이는 다음 포스팅 Model-Free Control에서 다루도록 하겠습니다.

TD policy evaluation 예를 살펴보겠습니다.

먼저 $(s_3, a_1, 0, s_2)$ 에 대해 $v(s_3)$ 를 업데이트하고, 그 다음 $(s_2, a_1, 0, s_2)$ 에 대해 $v(s_2)$ 를, $(s_2, a_1, 0, s_1)$ 에 대해 $v(s_2)$ 를, 마지막으로 $(s_1, a_1, 1, terminal)$ 에 대해 $v(s_1)$ 을 업데이트하면 한 에피소드에 대해 업데이트를 완료하게 됩니다.

Monte-Carlo vs. Temporal-Difference

이제까진 MC와 TD방식으로 policy evaluation하는 것을 보았습니다. 그러면 두 방식의 특성을 비교하겠습니다.

Bias/Variance Trade-Off

MC와 TD의 특징을 bias-variance trade-off 관점에서 보겠습니다. MC는 위에서 설명한 것처럼, return $G_t$ 는 $v_\pi(S_t)$ 의 unbiased estimate 입니다. 따라서 MC는 low bias의 특징을 띕니다. 반면에, TD는 bootstrap 기반이기 때문에 TD target $R_{t+1} + \gamma V(S_{t+1})$ 은 $v_\pi(S_t)$ 의 biased estimate 입니다. 따라서 TD는 high bias 특징을 가집니다.

그러나, variance관점에서 두 방식은 반대입니다. MC같은 경우, 한 에피소드가 끝날 때까지 계속 샘플링을 해야합니다. 이로인해, random성이 많이 증가하게 되죠. 반면에, TD같은 경우 업데이트를 위해 (s, a, r, s’)을 한번만 샘플링 하기 때문에 MC에 비해 random성이 작습니다. 이러한 특징으로 인해, MC는 high variance를, TD는 low variance를 갖습니다.

• Return depends on many random actions, transitions, rewards
• TD target depends on one random action, transition, reward

Properties of MC and TD

위의 bias-variance trade-off 성질로 인해 MC와 TD는 아래와 같은 특성을 같습니다.

MC : high variance and zero bias
MC는 zero bias이기 때문에 초기값에 상관없이 항상 수렴하게 됩니다. 이러한 수렴을 잘하는 특징 덕분에 좋은 근사 가치 함수도 갖게 됩니다(value function approximation, 추후에 포스팅 예정). 그러나, high variance인해 항상 true expected value에 수렴함에 불구하고, 언제 수렴할지는 불분명합니다. 왜냐하면, high variance로 인해 수렴할 때까지 굉장히 많은 에피소드 샘플링이 필요하기 때문입니다. 그리고 한 에피소드가 끝날 때까지 기다려야 하는데, 에피소드의 길이가 긴 경우 더욱 적용하기 어렵습니다. 따라서 실용성 측면에서 떨어지는 단점이 있습니다.

MC가 zero bias를 가질 수 있는 이유는 $G_t$ 가 i.i.d성질을 가지기 때문이라고 설명하였습니다. 이는 $V(S_t)$ 를 계산하는데 $S_t$ 의 markov property를 이용하지 않음을 뜻합니다. 따라서, Markov domain인 아닌 경우 MC를 적용하여 문제를 해결할 수 있습니다(handling non-markovian domains).

TD : low variance and high bias
반면에 TD는 low variance로 인해 수렴이 가능하다면, MC에 비해 수렴지점까지 빨리 도달할 수 있습니다(그림 11,12 참고). 하지만 초기값에 따라 수렴여부가 달라지고(sensitive to initial value), 그리고 근사 가치 함수를 찾지 못할 수도 있습니다. 하지만, on-line 학습이 가능하기 때문에, 따라서 쉽게 적용할 수 있습니다.

TD는 $V(S_t)$ 를 계산하기 위해서 $V(S_{t+1})$ estimate 을 이용합니다(bootstrap). 이는 MC와는 다르게 markov property를 이용합니다. 따라서, TD는 Markovian domain에서 적용가능합니다.

위에서 설명한 MC와 TD의 특성을 정리하면 아래와 같습니다.

위 표에서 마지막 특성에 관하여 MC, TD와 DP 사이의 관계를 back-up diagram과 함께 잘 나타낸 그림이 있습니다.

DP같은 경우, 환경 모델을 잘 알기 때문에 다음 스텝에 대해 full backup을 그린 관계와 같습니다. 그러나 에피소드가 끝날 때까지 backup을 그릴 필요가 없기 때문에 shallow-backup이고, bootstrap을 이용합니다. 반면에, TD같은 경우, 다음 상태에 대해 한 상태에 대해서만 샘플링을 하기 때문에 sample-backup이며, DP와 마찬가지로 한 스텝만 내다보기 때문에 shallow-backup이며 bootstrap을 이용합니다. 마지막으로 MC같은 경우, 모든 에피소드가 끝날 때까지 기다려야 하기 때문에 deep-backup이고, 샘플링을 하여 경험을 쌓기 때문에 sample-backup입니다. 그러나 bootstrap을 이용하지 않습니다.

TD가 MC보다 수렴이 더 빠른 것에 대해 수학적으로 증명된 적은 없습니다. 그러나, 실험적으로 확인했을 때 TD가 MC보다 수렴이 빠릅니다. 이에 관해 Sutton과 berto교재에 MC와 TD의 수렴에 관한 예제가 있습니다.

위의 예는 C에서 시작하여 각 스텝마다 왼쪽 또는 오른쪽으로 0.5의 확률로 동일하게 갈 수 있다고 할 때, 양 끝의 사각형에 도달하면 에피소드가 끝나는 문제입니다. 각 상태 A, B, C, D, E에서 value를 MC와 TD를 이용하여 구한 결과는 아래와 같습니다. 이때, 각 상태에서의 true value는 1/6, 2/3, 3/6, 4/6, 5/6입니다.

왼쪽 그림은 TD(0)를 여러 에피소드를 거쳤을 때, 각 상태에서의 value입니다. 100 에피소드 정도 진행했을 때, true value에 수렴하는 것을 확인할 수 있습니다. 오른쪽 그림은 step size $\alpha$ 를 달리했을 때 각각 MC와 TD에서의 RMS error 입니다. 실험적으로 TD가 MC보다 더 빨리 수렴합니다.

differences between MC and TD trough Batch Update
MC와 TD의 작동원리를 보여주는 사례를 하나 더 소개하겠습니다. 먼저 그전에 batch update에 대해 설명하도록 하겠습니다. k개의 에피소드 또는 k개의 스텝을 미리 샘플링 해 놓은 뒤, k개의 MC 또는 TD 방식의 error를 각각 구해서 다 합한 후, 한 번 update를 하는 방식을 batch update이라 합니다. 아래 예를 각각 MC와 TD 방식의 batch update로 풀어보겠습니다.

아래와 같이 8개의 에피소드가 있습니다. 첫번째 에피소드는 A에서 시작해서 reward를 0을 받고, 그 다음 B로 가고 reward를 0을 받고 끝납니다. 그 다음 여섯개 에피소드는 B에서 시작해서 reward를 1을 받고 끝납니다. 마지막 하나는 B에서 시작해서 reward를 1을 받고 끝납니다. 이때, MC와 TD방식으로 V(A), V(B)가 각각 어떻게 될까요 ?

MC방식으로 한다면, $V(A)=0, V(B)=\frac{3}{4}$ 입니다. 그러나 TD방식으로 한다면 $V(B)=0$ 이지만 $V(A)=\frac{3}{4}$ 입니다. $V(A)$ 에서 차이가 나는 이유는 MC는 mean squared error를 최소화하는 방식으로 해답을 구하지만, TD는 markov model의 likelihood를 최대화하는 방식으로 해답을 구하기 때문입니다.

• MC converges to solution with minimum mean-squared error
• Best fit to the observed returns

MC는 관측된 return이 true value estimate과의 차이가 최소화시키는 방향으로 갑니다. 반면에, TD는 markov property 성질을 이용하기 때문에 MDP를 해결하는 방향으로 갑니다. 실제 구현은 아니지만 내재적으로는 마치 환경모델의 transition model과 reward model의 maximum likelihood를 구한 뒤 DP를 푸는 방식과 유사하게 작동하는 것입니다. 실제로 위의 예제를 아래 방식으로 환경 모델을 구한 뒤 DP로 접근하면 똑같은 해답을 구할 수 있습니다.

• TD(0) converges to solution of max likelihood Markov model
• Solution to the MDP $<S, A, \hat P, \hat R, \gamma >$ that best fits the data

이상으로 이번 포스팅을 마치겠습니다. 다음 포스팅은 Model-Free Control에 대해 진행하겠습니다.