인공지능

[강화학습] Monte Carlo & Temporal Difference

반달링 2025. 4. 5. 23:49

강화학습의 가장 기초적인 알고리즘으로 자주 소개되는 Dynamic Programming(DP) 은 매우 강력하지만 한 가지 큰 전제가 필요하다. environment의 $P(s′∣s,a)$ 와  $R(s,a)$를 모두 알고 있어야 한다는 점이다. 예를 들어, FrozenLake 환경에서 '오른쪽으로 가면 80% 확률로 미끄러지고, 20%는 멈춘다'는 사실을 DP는 미리 알고 있어야 한다. (앞서 구현했던 예제에서는 미끄러지지 않는 환경이었다.)

하지만 실제 현실 세계에서 그런 확률이나 보상을 정확히 알 수 있는 경우는 거의 없다. 이러한 모델 기반(Model-Based) 접근 방식의 한계를 극복하기 위해 등장한 것이 바로 Monte Carlo 방식의 Model-Free 강화학습이다. dynamic programming처럼 model이 있다면 state만으로 policy를 구할 수 있다. 하지만 이처럼 model이 없으면 policy를 구하기 위해 action을 추정해야 한다. Monte Carlo 방식은 model을 사용하지 않고, episode 단위로 실제 sample을 얻어 Return $G_t$을 바탕으로 value function을 학습하는 방법이다. 특정 state에 도달하고나서 실제 environment의 return $G_t$를 관찰하여 $V(s_t)$를 업데이트하며, 여기서 $G_t$는 episode의 나머지에서 실제로 받은 return이므로 episode가 끝날 때까지 기다려서 전체 return을 계산한 후 한 번에 업데이트한다. $$V(s_t) \leftarrow V(s_t) + \alpha (G_t - V(s_t))$$ 이때, first-visit은 하나의 episode 내에서 어떤 state가 처음 등장했을 때에만 $V(s)$를 업데이트하는 것이고 every-visit은 state가 등장할 때마다 매번 $V(s)$를 업데이트하는 것이다. 이렇게 실제 visit한 $(s,a)$에 대한 return을 바탕으로 추정하기 때문에 return이 없으면 다른 action에 대한 추정은 업데이트될 수 없으므로 모두 가봐야 한다. 이를 위해 exploration을 해야 하므로 maintaining exploration 문제가 있다. 이렇게 value function을 추정하는 것이 Monte Carlo Prediction이다.

반면, Monte Carlo Control은 policy $\pi$도 학습하여 optimal policy를 찾는 것이다. exploration을 위해 추정한 value function을 바탕으로 greedy policy를 추정하고 policy improvement를 진행한다. policy iteration의 Monte Carlo 버전이라고도 할 수 있다. 하지만 이 또한 계속 exploration해야 하며 이에 따라 suboptimal policy가 아닌 그 policy의 value function으로 수렴하는 한계가 있다. 

이때까지는 현재의 policy $\pi$를 그대로 따르는 on-policy 방식을 사용하였다. 하지만 경우에 따라 학습하는 policy와 value를 추정하는 policy를 다르게 사용하고 싶은 경우가 있다. 이를 off-policy라고 하고 data로부터 학습하는 policy를 behavior policy, 추정하는 policy를 target policy라 한다. 다만 두 policy가 다르므로 이를 맞춰주기 위해 importance sampling을 사용한다. 평균을 구할 때 $\Sigma x * p(x)$였던 것을 $q(x)$로 추정하려고 하니까 distribution은 달라지지 않으면서 $q(x)$를 확률로 사용하기 위해 $\Sigma (x*\frac{p(x)}{q(x)})q(x)$로 변환하여 맞춰주는 것이다. 곱해주는 $\frac{p(x)}{q(x)}$를 importance ratio라고 한다. off-policy를 사용하면 실컷 exploration하면서 greedy policy로 sample을 얻을 수 있다. 또한 보다 나은 방법으로 target policy를 만들어서 value function을 재평가할 수 있다. 이때 behavior policy와 target policy가 너무 다르게 되면 variance가 커지는 문제가 있다.

그렇다면 Monte Carlo 방법은 수렴성을 보장할까? 직관적으로 on-policy보다 off-policy의 수렴성을 보장하기 더 어려울 것 같으니 off-policy Monte Carlo 방법으로 확인해보자.

앞서 다뤘던 Banach fixed point theorem을 사용할 수 있을까? $Q$ value function를 업데이트하는 식을 살펴보자. $W,C,G$는 랜덤 변수이므로 contraction mapping인지 판단이 불가하다. 즉, stochastic하므로 Banach theorem을 사용할 수 없다.

수렴성을 따지기 위해서는 Robbins-Monro를 이용해야 한다. 이는 stochastic approximation이라고도 불린다. $\epsilon_n$이 finite variance와 zero mean을 갖는 noise일 때 어떤 iteration을 고려하자.

$$\theta_n = \theta_{n-1} - \gamma_n \left[ h(\theta_{n-1})+\epsilon_n\right]$$

$h(\theta)=0$이 유일한 해 $\theta^*$를 가지고 learning rate sequence ${\gamma_n}$에 대해 $\Sigma \gamma_n = \infty, \Sigma \gamma_n^2 < \infty$를 만족할 때 $\theta_n$은 $\theta^*$으로 수렴한다. 

이를 바탕으로 위의 MC prediction을 Robbins-Monro iteration으로 나타낼 수 있는지 확인해보자.

$$Q_{n+1}(s_t,a_t) = Q_n(s_t,a_t) + \frac{W_n}{C(s_t,a_t)}\left[G-Q_n(s_t,a_t)\right]$$

이 식을 Robbins-Monro iteration에 맞춰 조정해보자. $$\gamma = \frac{1}{C(s_t,a_t)},$$ $$h(Q_n(s_t,a_t)) = W_n(Q_n(s_t,a_t)-Q(s_t,a_t)),$$ $$\epsilon_n = W_n(G-Q(s_t,a_t))$$라 해보자. 이때 $Q(s_t,a_t)$는 true 값이다. 그러면 식을 아래와 같이 조정할 수 있다.

$$Q_{n+1}(s_t,a_t) = Q_n(s_t,a_t) + \frac{1}{C(s_t,a_t)}\left[W_n(G-Q(s_t,a_t)) - W_n(Q_n(s_t,a_t)-Q(s_t,a_t)\right]$$

여기서 조건은 $\epsilon_n$이 finite variance와 zero mean을 갖는 noise여야 하고 $h(Q)=0$이 유일한 해 $Q^*$를 가지고 learning rate sequence ${\gamma_n}$에 대해 $\Sigma \gamma_n = \infty, \Sigma \gamma_n^2 < \infty$을 만족해야 한다.

  1. $\epsilon_n$이 finite variance와 zero mean을 갖는 noise여야 한다.
    • $\mathbb{E}_b \left[G-Q(s_t,a_t)\right] = 0$
      • $\because Q(s_t,a_t) = \mathbb{E}_{s_{t+1}:a_\infty}G$
    • $\mathbb{E}_b \left[\epsilon_n\right] = \mathbb{E}_b \left[WG-WQ(s_t,a_t)\right]=0$
      • $\therefore$ zero mean을 갖는다.
    • $\mathbb{V}_b \left[ \epsilon_n \right] = \mathbb{E}_b \left[ || \epsilon_n ||^2\right] < \infty$
      • finite reward라 가정
  2. $Q(s_t,a_t)$이 $h(Q_n(s_t,a_t))$의 유일해이다.
  3. learning rate sequence $\gamma = \frac{1}{C(s_t,a_t)}$
    • Robbins-Monro conditions 
      • $\Sigma\frac{1}{C(s_t,a_t)}=\infty$
      • $\Sigma\left(\frac{1}{C(s_t,a_t)}\right)^2 < \infty$

Robbins-Monro conditions만 만족한다면 $Q(s_t,a_t)$로 수렴함을 보장한다. 즉, Monte Carlo 방법은 수렴한다.

Monte Carlo 방식은 앞서 말한 것처럼 전체 episode가 끝나야 업데이트가 가능하다는 단점이 있다. 이를 보완하기 위해 등장한 것이 Temporal Difference (TD) learning이다. TD는 episode가 끝나지 않아도 다음의 정보를 사용하여 바로 업데이트할 수 있는 bootstrap의 구조이고, 특히 1-step TD는 한 스텝 뒤의 정보를 바탕으로 업데이트하는 방식이다. 모든 스텝을 보기 때문에 unbiased sample인 대신 variance가 큰 Monte Carlo 방식과 달리 TD는 다음 꺼만 보기 때문에 biased sample이지만 variance는 작다.

TD(0)도 수렴성을 따져보자.

$$V_{n+1}(s) \leftarrow V_n(s) + \alpha \left[ R+ \gamma V_n(s') - V_n(s)\right]$$

이 식을 Robbins-Monro iteration에 맞춰 조정해보자. $$\gamma =\alpha,$$ $$h(V_n(s)) = TV_n(s)-V_n(s),$$ $$\epsilon_n = R + \gamma V_n(s') - TV_n(s)$$라 해보자. 이때 $Q(s_t,a_t)$는 true 값이다. 그러면 식을 아래와 같이 조정할 수 있다. 이때, $TV_n(s) = R+ \gamma V_n(s')$이고 $T$는 contraction mapping이므로 유일해를 가진다.

  1. $\epsilon_n$이 finite variance와 zero mean을 갖는 noise여야 한다. $\rightarrow$ 만족
    •  
  2. $TV_n(s)$가 유일해를 가지므로 $h(V_n(s))=0$도 유일해를 가진다. $\rightarrow$ 만족
  3. learning rate sequence $\gamma = \alpha$
    • Robbins-Monro conditions 
      • $\Sigma\alpha=\infty$
      • $\Sigma\alpha^2 < \infty$

따라서, TD(0)도 Robbins-Monro conditions를 만족하면 수렴한다.

위의 강화학습 알고리즘은 exploration과 수렴의 균형을 맞추기 위해 GLIE (Greedy in the Limit with Infinite Exploration) 조건을 따른다. 이는 모든 $(s,a)$ 쌍이 무한히 자주 방문되어야 하며 결국에는 greedy policy로 수렴해야 한다는 조건이다. 이 GLIE 조건과 Robbins-Monro 조건을 함꼐 만족하면 MC와 TD 알고리즘은 모두 $Q^*$, $\pi^*$로 수렴함이 보장된다.

간단히 지금까지 다룬 알고리즘을 비교해보자면 아래의 그림과 같다.

DP는 연산량이 너무 많고 dynamics를 알아야 하는 model 기반의 방식이었다면, MC와 TD는 model을 알지 못해도 sample만으로 value function과 policy를 학습할 수 있었다. 하지만 MC는 unbiased sample인 대신 cost와 variance가 크고 TD는 bootstrap 구조로 biased sample인 대신 variance가 작다.

다음은 앞서 잠시 언급했던 on/off-policy 개념을 바탕으로 SARSA와 Q-learning을 다루겠다.

이 글은 Sutton & Barto의 Reinforcement Learning 5,6장을 바탕으로 작성되었다.

저작자표시 (새창열림)