Lecture 4: Model-Free Prediction

이번시간에는 Model-Free(Environment를 알지 못할때)에 대해서 알아보겠습니다.

Monte-Carlo Reinforcement Learning

• Monte-Carlo기법은 에피소드에서의 경험으로부터 직접 배웁니다.
• Monte-Carlo기법은 Model-Free 이며(환경에 대해서 모름), MDP의 변환이나 보상에 대해서 알지 못합니다.
• Monte-Carlo기법은 부트스트랩이 존재하지 않으며 다 끝난 에피소드를 거치면서 배웁니다.
• Monte-Carlo기법은 episodic MDPs에만 Monte-Carlo가 적용가능합니다.
  • 모든 Episode들은 반드시 종료되어야 합니다.

Monte-Carlo Policy Evaluation

• 목표 : 정책 $\pi$에 따른 Episode에서의 경험으로부터 $v_{\pi}$를 배웁니다.

$$S_{1},A_{1},R_{2},...,S_{k}\sim\pi$$

• 반환값은 총 할인된 보상임을 다시 기억하십시요

$$G_{t} = R_{t+1} + \gamma R_{t+2} + ... + \gamma^{T-1} R_{T}$$

• 가치함수는 반환값의 기댓값임을 기억하십시요.

$$v_{\pi}(s) = E_{\pi}[G_{t} \mid S_{t} = s]$$

• Monte-Carlo 정책 평가는 반환값의 기댓값 대신 경험적 평균 반환값을 사용합니다.

First-Visit Monte-Carlo Policy Evaluation

• Monte-Carlo기법에는 2가지 기법이 있습니다.
  • first-visit Monte-Carlo (한 State에 여러번 방문해도 처음 방문할 때만 Count함, 모든 State에 방문한다는 가정이 있어야 함)
  • every-visit Monte-Carlo (한 State에 대해서 여러번 방문한 것도 Count함, 모든 State에 방문한다는 가정이 있어야 함)
  • 증가하는 Counter, $N(s) \leftarrow N(s) + 1$
  • 증가하는 모든 보상, $S(s) \leftarrow S(s) + G_{t}$
  • 가치는 반환값의 평균값으로 추정됩니다. $V(s) = S(s) / N(s)$
  • 대수의 법칙에 의해, $V(s) \rightarrow v_{\pi}(s)\ as\ N(s) \rightarrow \infty$

Every-Visit Monte-Carlo Policy Evaluation

• 이번엔 Every-visit Monte-Carlo에 대해 알아보겠습니다.
• every-visit Monte-Carlo (한 State에 대해서 여러번 방문한 것도 Count함, 모든 State에 방문한다는 가정이 있어야 함)
• 증가하는 Counter, $N(s) \leftarrow N(s) + 1$
• 증가하는 모든 보상, $S(s) \leftarrow S(s) + G_{t}$
• 가치는 반환값의 평균값으로 추정됩니다. $V(s) = S(s) / N(s)$
• 대수의 법칙에 의해, $V(s) \rightarrow v_{\pi}(s)\ as\ N(s) \rightarrow \infty$

Blackjack Example

• 다음은 MC에 대한 예시입니다.

Blackjack Value Function after Monte-Carlo Learning

• 위 그림은 블랙잭 게임의 가치함수값을 Monte-Carlor기법으로 분석한 것입니다.

Incremental Mean

• 평균 $\mu_{1}, \mu_{2},...$은 수열 $x_{1}, x_{2}, ...$는 점진적으로 계산됩니다.

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

Incremental Monte-Carlo Updates

• Episode $S_{1}, A_{1}, R_{2}, ..., S_{T}$후에 $V(s)$를 점진적으로 업데이트합니다
• 각 State $S_{t}$에 따른 기댓값 $G_{t}$

$$N(S_{t}) \leftarrow V(S_{t}) + \alpha (G_{t} - V(S_{t}))$$

$$V(S_{t}) \leftarrow V(S_{t}) + \frac{1}{N(S_{t})}(G_{t} - V(S_{t}))$$

• 비정상적인 문제에서는 평균을 추적하는 것이 유용할 수 있습니다.

$$V(S_{t}) \leftarrow V(S_{t}) + \alpha(G_{t} - V(S_{t}))$$

Temporal-Difference Learning

• TD 방법은 에피소드에서의 경험으로부터 직접 학습합니다.
• TD 방법도 Model-Free이며 MDP의 변환이나 보상에 대해서 지식이 필요 없습니다.
• TD 방법은 bootstrapping을 통해 완전하지 않은 에피소드로부터 배웁니다.
• TD 방법은 추측을 이용해 추측을 업데이트 해 나갑니다.

MC(Monte-Carlo) and TD(Temporal-Difference)

• 정책 $\pi$로부터 경험을 통해서 $v_{\pi}$를 실시간으로 배웁니다.
• 점진적인 every-visit Monte-Carlo
  • 행동 반환값 $G_{t}$를 통해 $V(S_{t})$를 업데이트 합니다.
• 간단한 시간차 학습 알고리즘: TD(0)
  • 추정한 반환값 $R_{t+1} + \gamma V(S_{t+1})$을 통해서 $V(S_{t})$값을 업데이트 합니다.

$$V(S_{t}) \leftarrow V(S_{t} = \alpha(R_{t+1} + \gamma V(S_{t+1} - V(S_{t}))$$

• $R_{t+1} + \gamma V(S_{t+1})$는 TD의 타겟이라고 불립니다.
• $\delta = R_{t+1} + \gamma V(S_{t+1}) - V(S_{t})$는 TD오류라고 불립니다.
• TD를 간단히 설명하자면 다음 스텝의 예측치를 통해서 현재 상태의 값을 업데이트 하는 방식입니다.

Driving Home Example

• 위의 예시는 TD에 대한 예시입니다.

Driving Home Example: MC vs. TD

Advantages and Disadvantages of MC vs. TD

• MC는 에피소드가 끝난 후에 그 값들을 이용해서 업데이트하지만 ,TD는 최종 출력이 나오기 전에 값을 업데이트 합니다.
  • TD는 매스텝마다 실시간으로 학습합니다.
  • MC는 에피소드가 끝나고 반환값을 알기 전까지 기다려야 합니다.
• TD는 최종 출력 없이 배울 수 있습니다.
  • TD는 불완전한 수열로부터 학습합니다.
  • MC는 완전한 수열로만 학습합니다.
  • TD는 지속적인 환경에서 작동합니다. (도착점이 아닌)
  • MC는 episodic한 환경에서만 작동합니다. (도착점)

Bias/Variance Trade-off

• 반환값 $G_{t} = R_{t+1} + \gamma R_{t+2} + ... + \gamma^{T-1}R_{T}$는 $v_{\pi}(S_{t})$ 에 대한 불편향값입니다.
• True TD target $R_{t+1} + \gamma v_{\pi}(S_{t+1})$은 $v_{\pi}(S_{t})$ 값에 대한 불편향 추정값입니다.
• TD target $R_{t+1} + \gamma V(S_{t+1})$은 $v_{\pi}(S_{t})$의 편향된 추정값입니다.
• TD target은 반환값보다 훨씬 낮은 분산입니다.
  • 반환값은 많은 무작위 행동, 변환률, 보상에 따라서 달라집니다.
  • TD target은한개의 무작위 행동, 변환률, 보상에 따라 다릅니다.

Advantages and Disadvantages of MC vs. TD (2)

• MC는 분산이 크고, 0의 편향을 가지고 있습니다.
  • 수렴 성질이 좋습니다.
  • 함수 근사 기법을 써도 수렴 성질이 좋습니다.
  • MC는 initial value에 민감하지 않습니다.
  • 이해하기 매우 쉽고 사용하기도 매우 쉽습니다.
• TD는 낮은 분산을 가지고 있고, 조금의 편향을 가지고 있습니다.
  • 주로 MC보다 더 효과적입니다.
  • TD(0)은 $v_{\pi}(s)$로 수렴합니다.
  • 하지만 항상 근사함수와 함께 해야합니다.
  • initial value에 조금 더 민감합니다.

Random Walk Example

Random Walk: MC vs. TD

Batch MC and TD

• MC와 TD의 수렴성 : $V(s) \rightarrow v_{\pi}(s)$ 을 무한번 경험할 수 있으면 수렴을 하지만, 제한된 k개의 에피소드가 있을 때 MC와 TD가 같은 값에 수렴을 할까?

AB Example

• 원래대로라면 B의 V(B)값은? -> 총 8번의 시행중에서 6번의 1이 나왔으니 6/8 = 3/4로 생각할 수 있다.
• 그렇다면 A의 V(A)값은?????

AB Example

• 위의 그림을 예시로 저희는 이 식의 MDP를 추측할 수 있습니다.
  • A는 무조건 B로 갑니다.(100%)
  • B에서는 75%의 확률로 1로 가기 때문에 Reward를 1을 받고 25%확률로 0을 받습니다.
• MC를 통해 학습한 결과는 V(A)는 0이 됩니다. ( 반환값이 0이 되기 때문)
• TD는 V(A)가 0.75가 됩니다.

Certainty Equivalence

Advantages and Disadvantages of MC vs. TD (3)

• TD는 Markov 확률을 이용해서 Value를 추측하는 방식입니다.
  • 대부분 Markov 환경에서 더 효율적입니다.
• MC는 Markov 확률을 이용하지 않습니다.(Mean Squared error를 minimize하는 것입니다.)
• 대부분 non-Markov 환경에서 효과적입니다.

Monte-Carlo Backup

• 확률을 따져보자면 $S_{t}$에서 오른쪽으로 내려갔을 때의 확률은 1/2 확률로 선택할 수 있습니다. 하지만 MC의 경우는 한가지 경우의 수를 끝까지 가본 후에 값을 업데이트 하는 방식입니다.

Temporal-Difference Backup

• TD의 경우는 한 step만 가보고 추측해서 그것으로 대체해 버립니다.(이것을 BootStrap이라고 합니다.)
• 추측치로 추측치를 업데이트 하는 것 : BootStrapping

Dynamic Programming Backup

• DP는 Full sweep을 통해 value값을 업데이트합니다.

Bootstrapping and Sampling

• BootStrapping : 추측치로 추측치를 업데이트 하는 것
  • MC의 경우에서는 Bootstrap을 사용하지 않음 (끝까지 가보기 때문임)
  • DP와 TD는 Bootstrap을 사용합니다.(한스텝만 가고 업데이트)
• Sampling : 한가지의 샘플을 가지고 업데이트를 수행하는 것
  • MC와 TD는 한가지의 샘플을 가지고 업데이트를 수행합니다.(했던 것을 가지고 업데이트를 하기 때문)
  • DP의 경우는 해당 State에서 가능한 모든 행동을 수행하기 때문에 Sampling에 해당하지 않습니다.

Unified View of Reinforcement Learning

n-Step Prediction

n-Step Return

Large Random Walk Example

Averaging n-Step Reutrns

• 우리는 다른 스텝에 대한 평균을 낸것으로 수행하면 안되는가?
  • 결론은 수행해도 됩니다.

$\lambda$-return

• 심지어 TD(1)부터 끝까지 모두 평균을 내도 됩니다.
• 현 식을 모두 더하게 되면 1이 됩니다.($\lambda$값이 0에서 1사이의 값이라는 가정하에)
• TD($\lambda$)는 두가지로 나뉩니다
  • Forward-view TD($\lambda$) : 나의 미래를 보는 것
  • Backward-view TD($\lambda$) : 나의 과거를 보는 것

TD($\lambda$) Weighting Functing

• 시간이 지날수록 가중치가 줄어드는 것을 볼 수 있습니다.(Geometric Mean 사용)

Forward-viw TD($\lambda$)

Forward-View TD($\lambda$) on Large Random Walk

Backward View TD($lambda$)

• 매 스텝마다 업데이트가 가능하고, Complete Sequence가 아니여도 업데이트가 가능합니다.

Eligibility Traces

• 사건의 책임 추척인데, 책임을 물어 책임이 큰 친구한테 업데이트를 많이 해주는 것
• 책임을 많이 일어난 친구한테 많이 물어야 하는 방법
• 최근에 일어난 친구한테 많이 물어야 하는 방법

$$E_{0}(s) = 0$$

$$E_{t}(s) = \gamma \lambda E_{t-1}(s) + 1(S_{t} = s)$$

• 간단하게 그림은 방문할 떄마다 1을 올리고 방문하지 않을 때마다 0.9씩 줄여주고 이런 방식을 계속 반복합니다.

Backward View TD($\lambda$)

• 각 State s에 대한 모든 사건 책임
• 모든 State s에 대해 값 $V(s)$를 업데이트 수행
• TD-error는 $\delta_{t}$ 및 사건 책임 추적성 $E_{t}(s)$에 비례합니다.

$$\delta_{t} = R_{t+1} + \gamma V(S_{t+1}) - V(S_{t})$$

$$V(s) \leftarrow V(s) + \alpha \delta_{t} E_{t}(s)$$

TD($\lambda$) and TD(0)

• $\lambda = 0$일 때 TD(0)과 값이 똑같다.

$$E_{t}(s) = 1(S_{t} = s)$$

$$V(s) \leftarrow V(s) + \alpha \delta_{t} E_{t}(s)$$

• 이것은 TD(0)값을 업데이트한거랑 정확히 맞습니다.

$$V(S_{t}) \leftarrow V(S_{t}) + \alpha \delta_{t}$$

TD($\lambda$) and MC

• $\lambda = 1$일 경우 MC와 같습니다.