티스토리 뷰

인공지능/RL

Lecture 4: Model-Free Prediction

로또_ 2020. 3. 16. 19:22

Lecture 4 : Model-Free Prediction

-Introduction

-Monte-Carlo Learning

-Blackjack Example

-Incremental Monte-Carlo

-Temporal-Difference Learning

-Driving Home Example

-Random Walk Example

-Batch MC and TD

-Unified View

-TD(λ)

-n-Step TD

-Forward View of TD(λ)

-Backward View of TD(λ)

-Relationship Between Forward and Backward TD

-Forward and Backward Equivalence

Model-Free Reinforcement Learning

Monte_Carlo Reinforcement Learning

Monte-Carlo Policy Evaluation

First-Visit Monte-Carlo Policy Evaluation

단 First-Visit이나 Every-Visit이나 모든 state를 방문해야 합니다.

Every-Visit Monte-Carlo Policy Evaluation

Blackjack Example

Blackjack Value Function after Monte-Carlo Learning

상단의 2개의 그림은 ace가 있을때의 state이고, 아래의 2개는 ace카드가 없을때의 state입니다.

Incremental Mean

각 states들을 방문했을때 평균값을 다 저장해야합니다. 그리고 만번 방문했으면 만번방문의 평균을 내야합니다. 하지만 incremental mean을 쓰면 저장하지 않아도 그때 새로운 값이 나올때마다 incremental하게 교정해주면 됩니다.

Incremental Monte-Carlo Updates

Gt -V(St)는 error입니다. 또 N이 커지게 되면 1/N은 점점 작아지게 됩니다. 하지만 저희는 알파로 고정시켜 사용할 수도 있습니다. 이렇게 고정시키면 예전에 했는 경험들을 잊어버리게 됩니다. 이러한것은 non stationary problem에서는 좋을 수 있습니다.(MDP가 조금씩 바뀌는 상황입니다.)

Temporal-Difference Learning

MC와 같이 경험적으로 배웁니다. 또한 MDP에 대한 지식이 필요없습니다. 하지만 다른점은 incomplete episode를 통해서 배울 수 있습니다.

MC and TD

MC는 G방향으로 업데이트를 하였으나, TD는 R + V 방향으로 업데이트합니다.

Driving Home Example

Elapsed time은 실제 지난 시간, predicted는 말그대로 예측시간입니다. state는 총 6개입니다

Driving Home Example: MC vs. TD

그래프는 predicted total time입니다. MC는 43으로 집에 도착했으므로 각 state를 43으로 update합니다. TD는 다음 state값으로 update를 해줍니다.

Advantages and Disadvantages of MC vs. TD

TD는 마지막 결과가 나오기전에 학습이 가능합니다. MC는 반드시 기다렸다가, 에피소드가 끝난후 값을 return합니다. 그러므로 TD는 continuing한 상황에서도 학습할 수 있습니다. 실시간 학습이 가능하다는 말인가???(non-terminating 환경) MC는 terminating 환경에서만 학습할 수 있습니다.

BIas/Variance Trade-Off

Gt는 V파이의 unbiased estimate입니다. 이건 당연한 말인것이, Gt의 기댓값이 V파이(St)입니다. 그래서 Gt를 계속 샘플링하면 V파이(St)에 수렴한다는 것입니다. 정확한 V파이를 알고있다면 True TD target은 unbiased합니다. 왜냐하면 벨만 equation이 보장해줍니다. 그러나 우리는 정확한 V파이를 알지 못하므로 추측치인 V를 업데이트 합니다. 하지만 이것은 biased value입니다. biased관점에서는 TD는 적절하지 못합니다. 하지만 variance 관점에서 보면 TD가 variance가 훨씬 낮습니다.

Advantages and Disadvantages of MC vs. TD (2)

현재는 table에 기록하는 방법으로 MC와 TD를 하고 있습니다. 하지만, 문제가 커져서 state가 많아지면 table에 적을 수 없습니다. 그래서 function approximator가 들어옵니다. 그게 뉴럴 넷입니다.(딥러닝) 이 부분에 대해서는 5장과 6장에서 자세히 나옵니다.

TD는 initial value에 민감합니다. initial value를 이용해서 V를 update하기 때문입니다. 그래서 추측치가 잘 정해져있으면, 수렴을 잘 합니다. 그러면 의문을 제기할 수 있는것이, biased 된 value가 정확한 알고리즘이냐 하는 것입니다. 이에 대해서 실버 교수님 다행이 맞다고 말합니다.

Random Walk Example

양방향으로 random하게 움직이는 policy가 있다고 했을때, 그 policy를 이용해서 각각의 state를 평가하고 싶습니다. 여기서 이용한것은 TD입니다. 결국엔 100번째의 episode에서는 true value에 수렴합니다.

Random Walk: MC vs. TD

에피소드가 진행됨에 따라RMS 오류가 줄어듭니다. 다시 오류가 늘어나는건 알파가 너무 커서 그렇습니다. 진동하는겁니다.

Batch MC and TD

Episode가 무한번 반복하였을때 MC와 TDrk V파이로 수렴하는 것을 알고 있습니다. 만일 k 개의 제한된 episode만 있을때, MC와 TD는 같은 곳에 수렴을 할것인가?

AB Example

저희는 model-free이므로 주어진 에피소드만 있고 model을 모릅니다.

AB Example

이 에피소드들로부터 오른쪽의 MDP를 추측할 수 있습니다. MC를 이용하여 V(A)학습하면, V(A)는 0입니다. 하지만 TD를 이용하여 학습하면

Certainty Equivalence

여기서 다시 MC로하면 V(A) = 0 이되고, TD(0)은 V(A) = 0.75가 됩니다. 다시한번 언급하지만, 여기의 상황은 episode를 무한정 뽑을 수 있는것이 아닌 k개로 한정된 상황입니다.

Advatages and Disadvantages of MC vs. TD (3)

TD는 markov property를 exploits 하므로 markov environment에서 효과적입니다. 하지만 MC는 Markov property를 사용하지 않고 그냥 mean squre error를 minimize합니다.

Monte-Carlo Backup

Temporal-Difference Backup

부트 스트랩핑이라고도 합니다.(추측치를 추측치로 업데이트 합니다.)

Dynamic Programming Backup

Bootstrapping and Sampling

Bootstrapping은 추측치를 가지고 추측치를 계산합니다. MC는 bootstraping을 하지 않습니다. MC는 끝까지 가보기 때문입니다. (depts 관점에서 바라본것입니다.) DP는 모든 가능한 action들을 다 해보므로 sampling을 하지 않습니다.

Unified View of Reinforcement Learning

model을 알때는 full backup이 가능하며, 모를때는 불가능합니다.

n-Step Prediction

n-Step Return

Large Random Walk Example

다음은 TD(1)부터 TD(1000)까지의 성능을 분석한것입니다. x축은 알파값을 바꿔가면서 하였습니다. on-line은 움직이는 도중에 업데이트를 하고, off-line은 움직임이 끝난후에 업데이트를 합니다. 너무 높다고 좋지도 않습니다. 그래프를 보시면 3에서 5사이정도가 좋은 결과값을 반환합니다.