[RL] Model-Free Prediction

MDP, DP와 같이 model-based learning에서 agent는 environment에 대한 거의 모든 정보를 갖고 있다. 하지만 그러한 일은 흔치 않으며, 알고 있더라도 environment의 가동은 대부분 굉장히 복잡하다. 이를 대신하여 model-free learning이 존재한다. Q-learning과 같은 model-free learning에서 agent는 environment에 대해 어떠한 정보도 필요로 하지 않고, 어떤 state가 존재하고 action이 가능한지만 안다면 충분하다. 이번 글과 다음 글에서는, MDP를 알지 못하더라도 (reward dynamic, transition probability) value function을 추정할 수 있는 방법들을 알아볼 것이다.

 

 

---

Monte-Carlo Learning

Monte-Carlo method, 몬테카를로 방법이란 수학의 추정 알고리즘 중 하나로, 무작위성이 존재하는 상황에서 사용할 수 있는 알고리즘이다. 예를 들어, 큰 수의 법칙 (Law of large number)에 의해, 확률 변수의 기댓값은 random sample의 표본 평균을 통해 추정할 수 있다. 다음 그림은 Monte-Carlo 방법의 예시 중 하나로, 원주율 $\pi$를 근사적으로 구하는 모습을 보여준다. $[0, 1] \times [0, 1] \in \mathbb{R}^2$ 정사각형에서, uniform하게 좌표 점 $(x, y)$를 샘플링한다. 샘플링한 후 전체 샘플 중 그림에서 원의 중심이 $(0, 0)$에 위치한, 반지름 $1$의 원 안에 존재하는 점들의 비율을 구하면 $\pi$ 값이 큰 수의 법칙에 의해 근사된다.

$\mathbf{Fig\ 1.}$ The process of approximating $\pi$ by Monte-Carlo method

 

 

이와 같이 Monte-Carlo 방법은 닫힌 형태로 표현되지 않거나 계산이 복잡한 값을 근사하고 시뮬레이션하는 알고리즘들을 폭넓게 부르는 용어다. 강화학습에서는, Monte-Carlo 방법을 통해 agent가 MDP transition과 reward를 모른 채로 episode에서 바로 학습해 value function을 추정하도록 한다.  

---

Monte-Carlo Prediction

첫 번째로, $v_\pi$를 episode로부터 학습하기 위해 Monte-Carlo 방법을 고려해보자. Monte-Carlo policy evaluation은 policy $\pi$에 대해 value function $v_\pi = \mathbb{E}_\pi [G_t | S_t = s]$를 다음과 같은 episode로부터 추정하는 것을 목표로 한다:

$$
\begin{aligned}
  S_1, A_1, R_2, \cdots, S_k \sim \pi
\end{aligned}
$$

$\mathbf{Fig\ 2.}$ Monte-Carlo backup

아이디어는 굉장히 간단한데, 기댓값 (expectation) 대신 실험 평균값 (empirical mean)을 사용하는 것이다. Agent가 environment에서 활동하며 생긴 여러 개의 episode를 바탕으로, policy $\pi$를 학습하는 상황을 고려해보자. 이때, 한 episode마다 특정 state $s$를 여러 번 방문할 수 있는데, 이러한 각 state마다 방문 수를 visit이라고 부를 것이다. First-visit Monte-Carlo policy evaluation은 $s$의 첫 번째 방문 시점 $t$에서 return의 평균 값으로 $v_\pi (s)$를 추정한다. 다시 말해 state $s$를 방문하는 episode의 개수를 $N(s)$, 각 episode마다 첫 번째 방문 시점 $t$ 이후의 return의 총합을 $S(s)$라고 하면,  $v_\pi (s) \approx \frac{S(s)}{N(s)}$가 된다. 

 

즉, agent가 어떤 episode에서 state $s$를 방문하며 가장 첫번째에 방문 시점을 $t$라고 한다면, 다음과 같이 $N(s), S(s)$를 업데이트 해주고

$$
\begin{align}
  & N(s) \longleftarrow N(s) + 1 \\
  & S(s) \longleftarrow S(s) + G_t \\
\end{align}
$$

한 episode가 끝나면 모든 state $s$에 대해 value 값을 업데이트 해주는 방식이다. 그리고 이러한 추정 값 $V(s)$의 $N(s) \to \infty$에 따른 $v_\pi (s)$로의 수렴성은 큰 수의 법칙에 의해 보장된다. 

$$
\begin{aligned}
  V(s) = \frac{S(s)}{N(s)}
\end{aligned}
$$

 

반드시 첫 번째 방문만 따질 필요는 없다. Every-visit Monte-Carlo policy evaluation은 한 episode 당 모든 방문을 고려한다. 한 episode $\left\langle S_1, A_1, R_2, \cdots, S_T \right\rangle$ 이후, 각 state $S_t$과 그에 상응하는 return $G_t$에 대해, 

$$
\begin{aligned}
  & N(S_t) \longleftarrow N(S_t) + 1 \\
  & V(S_t) \longleftarrow V(S_t) + \frac{1}{N(S_t)} (G_t - V(S_t)) 
\end{aligned}
$$

 

평균 값 계산이 와닿지 않을 수 있는데, 이는 다음과 같은 online average 계산법에 따른 것이다.

$$
\begin{aligned}
  \mu_k & = \frac{1}{k} \sum_{i=1}^k x_i \\
  & = \frac{1}{k} ( x_k + \sum_{i=1}^{k-1} x_i ) \\
  & = \mu_{k-1} + \frac{1}{k} (x_k - \mu_{k-1}) 
\end{aligned}
$$

 

이러한 계산방법은 non-stationary, 번역하자면 비정상적인 문제(예를 들어, policy improvement처럼 policy가 반복적으로 변경되는 상황)에서 평균값을 추적하는 데 유용하다. 특히 이 계산법은 뒤에서 다룰 TD learning의 중요한 아이디어이므로 기억해둘 필요가 있다. 

$$
\begin{aligned}
  V(S_t) \longleftarrow V(S_t) + \alpha (G_t - V(S_t)) 
\end{aligned}
$$

 

 

MC prediction의 특성 중 하나는 각 state마다 여러 개의 state-value 추정 값들이 있을텐데, 이들은 서로 독립적이라는 것이다. 이는 추정 값을 바탕으로 다시 추정 (이를 bootstrap이라고 한다), 다시 말해 추정값을 재사용하지 않기 때문이다. 이 특성은 Monte-Carlo 방법과 Temporal Difference 방법을 나누는 중요한 특징이 된다. 아래의 다이어그램은 Monte-Carlo prediction을 요약하는 backup diagram이다. 검은색 점은 action, 흰 원은 state를 나타내는 node이다. 

$\mathbf{Fig\ 3.}$ The backup diagram for Monte-Carlo prediction of $v_\pi$. The trajectory must be complete.

아래는 first-visit MC prediction의 pseudocode이다.

$\mathbf{Fig\ 4.}$ The first-visit MC method for estimating $v_\pi$.

 

---

Temporal-Difference Learning

Temporal-Difference Learning은 강화학습의 핵심적인 아이디어 중 하나로, Monte-Carlo 방법과 dynamic programming이 결합된 방법이다. 줄여서 TD Learning이라고도 하는데, TD 방법 역시 Monte-Carlo 방법과 동일하게 agent가 MDP transition과 reward dynamics를 모른 채로 episode에서 바로 학습해낸다. 하지만 Monte-Carlo Learning은 한 episode 단위로 학습하는 반면, TD learning은 한 timestep마다 학습할 수 있는 방법으로써 학습을 위해 episode가 끝날 때까지 기다릴 필요가 없다. 즉 TD는 불완전한 episode로부터 bootstrapping (부트스트랩, 추정에 추정을 더하면서 새로운 추정값을 얻어냄)을 통해 학습한다. 아직은 무슨 뜻인지 잘 와닿지 않는데, 더 자세하게 알아보자.

---

Temporal-Difference Prediction

주어진 policy $\pi$에 대해 $v_\pi$를 추정하는 policy evaluation, 또는 prediction 문제를 생각해보자. 강화학습에서 자주 사용되는 용어인데, policy나 value 등 특정 값을 추정하는 문제를 prediction, 특정 값을 최적화하는 문제를 control이라고 부른다. Monte-Carlo prediction의 경우 return 값을 얻기 위해 한 trajectory가 끝날 때까지 기다려야 한다는 단점이 있었다. Temporal Difference 방법은 return을 계산할 필요가 없기 때문에, trajectory를 기다릴 필요없이 매 시점마다 value function을 업데이트할 수 있다. Temporal Difference 방법은 Bellman expectation equation을 기반으로 하는데, $v_\pi (s)$에 대한 Bellman expectation equation를 떠올려보자:

$$
\begin{aligned}
  v_\pi (s) & = \sum_{a \in \mathcal{A}} \pi (a | s) ( \mathcal{R}_s^a + \gamma \sum_{s^\prime \in \mathcal{S}} \mathcal{P}_{ss^\prime}^a v_\pi (s^\prime)) \\
  & = \sum_{a \in \mathcal{A}} \pi (a | s) ( \mathcal{R}_s^a + \gamma \mathbb{E}_{s^\prime \sim \mathcal{P}_{ss^\prime}^a} [v_\pi (s^\prime)])
\end{aligned}
$$

 

TD 방법은 $\mathbb{E}_{s^\prime \sim \mathcal{P}_{ss^\prime}^a} [v_\pi (s^\prime)]$을 오직 하나의 샘플의 표본 평균으로 추정하는데, 샘플 한 개의 표본 평균이므로 샘플의 값 자체로 value를 추정하는 것과 같다. 다시 말해, $s^\prime$을 $\mathcal{P}_{ss^\prime}^a$에서 샘플로 하나 추출하여 그 샘플 state에 해당하는 value 값으로 $\mathbb{E}_{s^\prime \sim \mathcal{P}_{ss^\prime}^a} [v_\pi (s^\prime)]$를 대체한다:

$$
\begin{aligned}
  v_\pi (s) & = \sum_{a \in \mathcal{A}} \pi (a | s) ( \mathcal{R}_s^a + \gamma v_\pi (s^\prime)) = \mathbb{E}_\pi [\mathcal{R}_s^a + \gamma v_\pi (s^\prime)] \text{ where } s^\prime \sim \mathcal{P}_{ss^\prime}^a \\
\end{aligned}
$$

그러면 이제 $\mathcal{R}_s^a + \gamma v_\pi (s^\prime)$는 $v_\pi (s)$의 unbiased estimator (비편향 추정량, 불편 추정량이라고 부르는 것 같은데, 영어식 표현이 익숙해 따로 번역하지 않겠다) 가 된다. 그리고 이것이 TD learning의 motivation이 되는데, TD learning은 $\mathcal{R}_s^a + \gamma v_\pi (s^\prime) \text{ where } s^\prime \sim \mathcal{P}_{ss^\prime}^a$를 update target으로 두고 다음과 같은 update rule을 따른다. 다음 update rule은 가장 기본적인 TD learning의 형태로 $\text{TD}(0)$라고 부른다. 일반형으로 $\text{TD}(\lambda)$가 존재하는데 글의 마지막 부분에서 다뤄볼 것이다. 

$$
\begin{aligned}
  V(S_t) \longleftarrow V(S_t) + \alpha (R_{t+1} + \gamma V(S_{t+1}) - V(S_t))
\end{aligned}
$$

 

$\mathbf{Fig\ 5.}$ Temporal-Difference backup

Update rule은 앞서 보았던 moving average 계산법을 따른 것이다. 다만 $0 < \alpha \leq 1$ 값을 통해, 기존 $V(S_t)$의 추정량에서 새로운 추정값 $R_{t+1} + \gamma V (S_{t+1})$을 얼마나 더해줄 것인지를 조절하는 것이다. 한 가지 드는 의문은 $V(S_t)$를 업데이트하기 위해 $V(S_{t+1})$을 알아야 한다는 것인데, 여기서 bootstrap의 의미를 알 수 있는데, $V(S_{t+1})$의 추정량을 사용하기 때문이다. 즉 $V(S_t)$를 추정하기 위해 또 다른 추정량 $V(S_{t+1})$을 사용한다는 의미에서 흔히 TD 방법을 bootstrapping으로 부르는 것이다.

 

우리는 $R_{t+1} + \gamma V (S_{t+1})$의 기댓값인 $V(S_t)$를 추정하는 것을 목표로 하고, $V(S_t)$를 $R_{t+1} + \gamma V (S_{t+1})$의 근사값으로 사용한다. 따라서 $R_{t+1} + \gamma V (S_{t+1})$를 TD target이라고 부르고, $V(S_t)$의 추정값을 업데이트하는 정도 $\delta = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$를 TD error라고 부른다. 한 가지 짚고 넘어갈 것은 TD learning은 bootstrapping에 기반을 두기 때문에 TD target은 MC 방법처럼 unbiased estimator가 될 수 없고, MC 방법과 TD 방법의 가장 큰 차이점이 된다. 아래의 다이어그램은 Temporal Difference prediction의 backup diagram을 나타낸다. 오직 $R_{t+1}$과 $S_{t+1}$이 update에 필요한 모든 것이므로, 한 timestep만 기다리면 되는 것이다.

 

$\mathbf{Fig\ 6.}$ The backup diagram for TD prediction of $v_\pi$

 

아래는 $\text{TD}(0)$의 pseudocode이다.

 

$\mathbf{Fig\ 7.}$ $\text{TD}(0)$ for estimating $v_\pi$

 

---

MC v.s. TD 

이번 섹션에서는 MC와 TD 방법의 차이점들을 이론적으로 비교해보고자 한다. 

---

Bias-Variance Tradeoff

가장 큰 이론적인 차이점으로 MC와 TD의 bias-variance tradeoff을 꼽을 수 있다. MC 방법은 $v_\pi$를 return $G_t$들의 표본 평균으로 추정하고, $v_\pi$는 $G_t$의 기댓값이기 때문에 unbiased estimation이 된다. 반면에 TD 방법은 $v_\pi$를 TD target $R_{t+1} + \gamma V (S_{t+1})$를 통해 학습한다. 이때 $V (S_{t+1})$도 추정량이므로, 일반적으로 TD 방법은 biased estimation이 된다. 

 

한편 TD learning의 장점은, TD target이 return에 비해 분산 (variance)이 훨씬 작다는 것이다. Return은 한 trajectory의 결과 값이므로 일련의 무작위한 (우리는 MDP를 모르기 때문에 agent 입장에선 무작위하다고 할 수 있다) action, transition, reward에 영향을 받는다. 하지만 TD target은 오직 한 timestep에만 의존하기 때문에 가해진 무작위성이 return에 비해 덜하다. 또한 TD 방법이 biased estimation이긴 해도, $v_\pi$로의 수렴성은 보장되어 있어 MC 방법과 더불어 많이 사용되는 알고리즘이다. 다음 글에서 다룰 SARSA, Q-learning 역시 Temporal Difference learning의 일종이다.

---

Sampling & Bootstrapping

Monte Carlo 업데이트의 target은 $\mathbb{E} [G_t \| S_t = s]$로 이를 추정하기 위해 return $G_t$를 사용하는 반면, Dynamic Programming을 이용한 방법은 $\mathbb{E} [R_{t+1} + \gamma v_\pi (S_{t+1}) \| S_t = s]$를 target으로 한다. Temporal Difference 방법은 Monte Carlo 방법 (큰 수의 법칙을 이용한 추정)과 Dynamic Programming의 target을 합쳐, $R_{t+1} + \gamma v_\pi (S_{t+1})$를 통해 value 값 $v_\pi (S_t)$를 추정한다. 

 

그렇기 때문에 TD 방법은 Monte Carlo 방법의 sampling과 DP의 bootstrapping이 합쳐진 알고리즘으로, 다음 timestep으로부터 $R_{t+1}$를 sampling하여 value $V(S_t)$에 대한 추정 값을 $R_{t+1} + \gamma V(S_{t+1})$ 쪽으로 update한다. 이제 bootstrapping과 sampling의 개념이 완벽히 이해되었길 바란다. 요약하자면,

 

• Bootstrapping: update involves an estimate 
  
  • MC doesn't bootstrap  
  • DP bootstraps
  • TD bootstraps
• Sampling: update samples an expectation 
  
  • MC samples
  • DP doesn't sample 
  • TD samples 

 

$\mathbf{Fig\ 8.}$ Unified view of Reinforcement Learning.

 

---

TD($\lambda$)

그렇다면 MC와 TD의 장단점을 서로 합칠 수 있을까? 한 가지 가능한 방법은 $n$-step return을 고려하는 것이다. $n$-step return $G_t^{(n)}$이란, 현재 시점 $t$에서, trajectory의 끝까지가 아닌 $n$ timestep 이후까지의 return을 의미한다:

$$
\begin{aligned}
  G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n V(S_{t+n})
\end{aligned}
$$

즉, 각 $n = 1, 2, \cdots$에 대해 $n$-step return $G_t^{(n)}$은 다음과 같이 정의된다.

$$
\begin{alignat*}{2}
  &n = 1 \text{ (TD) } &&\longrightarrow G_t^{(1)} = R_{t+1} + \gamma V (S_{t+1}) \\
  &n = 2               &&\longrightarrow G_t^{(2)} = R_{t+1} + \gamma R_{t+2} + \gamma^2 V (S_{t+2}) \\
  &\quad \vdots \\
  &n = \infty \text{ (MC) } &&\longrightarrow G_t^{(\infty)} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{T-1} R_T \\
\end{alignat*}
$$

 

따라서 $n$의 값이 커질수록 return 값 $G_t$는 TD target으로 근사될 수 있게 된다! 반면 $n$이 커지더라도 어쨌든 끝이 보장되어 있으므로, 언제 끝날지 모르는 Monte-Carlo learning과 달리, continuous task에도 사용할 수 있게 된다.

하지만 여기서 문제는, $n$은 hyperparameter로써 우리가 조절할 수 있으나 어떤 $n$이 가장 적합한지 알 수 없다. 따라서, 각기 다른 $n$에 대한 $n$-step return들을 다음과 같이 평균낼 수 있다.

$$
\begin{aligned}
  \frac{1}{N} \sum_{k=1}^N G_t^{(i_k)}
\end{aligned}
$$

위와 같은 $n$-step return들의 평균이 곧 $\text{TD}(\lambda)$의 핵심 아이디어이다. $\text{TD}(\lambda)$은 $\lambda$-return $G_t^\lambda$라는 것을 사용하는데, 모든 $n$-step returns $G_t^{(n)}$을 기하급수적으로 가중 평균을 내는 것이다:

$$
\begin{aligned}
  G_t^\lambda = \sum_{n=1}^\infty (1 - \lambda) \lambda^{n-1} G_t^{(n)}
\end{aligned}
$$

가중치 $(1 - \lambda) \lambda^{n-1}$들의 합이 $1$인 것을 직접 확인해볼 수 있다.  이때 $\lambda \in (0, 1)$ 역시 hyperparameter로써 우리가 조절할 수 있다. 

---

Reference

[1] Reinforcement Learning: An Introduction. Richard S. Sutton and Andrew G. Barto, The MIT Press.

Reinforcement Learning

[2] Introduction to Reinforcement Learning with David Silver

Introduction to Reinforcement Learning with David Silver

[3] A (Long) Peek into Reinforcement Learning

A (Long) Peek into Reinforcement Learning

[4] What exactly is bootstrapping in reinforcement learning?

What exactly is bootstrapping in reinforcement learning?

[5] Wikipedia, Temporal difference learning

Temporal difference learning - Wikipedia