[RL]Lecture 4. Model-Free Prediction

Youtube에 있는 David Silver의 Reinforcement Learning 강의를 보고 작성하였습니다.

Model Free Prediction

• Model Free : MDP에 대한 정보가 없는 경우, 즉 environment에 대한 정보를 가지고 있지 않다.

• Prediction : value function을 학습하는 것

즉 Model Free Prediction은 MDP에 대한 정보가 없을 때 value function을 학습해야 하는 문제이고, 다음 장에서 Model Free Control에 대해서 알아보도록 한다.

이번 강의에서 소개한 Model Free Prediction 방법으로 크게 Monte-Carlo Learning(MC), Temporal-Difference Learning(TD)가 있다.

Monte-Carlo Learning

몬테 카를로 방법(다음 부터 MC라 부른다.)은 episode들로 부터 직접적으로 학습한다. 즉 모두 종료가 되는 episode들의 return의 평균을 통해서 학습을 진행한다는 것이다. 그러므로 MC는 완전한 episode들로 부터 학습을 하며 이를 no bootstrapping(추측치로 업데이트 하기)이라고 부른다.

• Goal : Prediction 문제이므로 policy는 π로 정해져 있고, 이를 통해 나온 episode들을 통해 vπ 를 학습하는 것

• return은 Gt=Rt+1+γRt+2+ ... + γT−1RT 와 같이 정의 했으며 vπ(s) = Eπ [Gt | St = s] 로 정의했었다.

MC 방법은 state들을 방문한 것을 바탕으로 다시 크게 First와 Every로 나뉘게 된다.

First- Visit MC Policy Evaluation

terminate까지 도달하기 위해서 state들을 여러번 방문할 수 있는데, , 이때 해당 state에 처음 접한 후 얻은 return 값의 평균을 사용하여 구한다.

Every-Visit MC Policy Evaluation

First와는 달리 state들을 방문할 때마다 return을 계산하고 이를 평균을 내는 방식이다. 보통 first-visit을 사용한다고 한다.

Incremental mean

평균을 구하는 식은 다음과 같이 현재의 값을 뺀 평균의 식으로 바꿀 수 있게 된다. 이를 통해 incremental update를 할 수 있게 된다.

따라서 이를 이용해서 MC 방법에서 V를 계산하는데 사용할 수 있다.

N(S)는 episode를 수행한 횟수에 해당하며 에피소드를 수행하고 나서 v(s)를 바로바로 추정가능하게 된다.

non-stationary 문제의 경우에는 평균을 낼 때 이전의 횟수를 사용하는 것이 아니라 일정한 값인 a로 고정해서 계산을 한다.

Temporal-Difference Learning(TD)

TD방식도 episode들로 부터 직접적인 경험을 하면서 학습을 하는 알고리즘이며 model-free에서 사용한다. 하지만 MC와는 다르게 episode들이 완전히 끝나지 않아도 학습이 가능하며 DP에서 사용하던 bootstrapping 방법을 사용한다. 즉 MC방법과 DP 방법을 적절히 조합한 아이디어라고 할 수 있다. 그리고 추측치에서 다음 추측치를 추정함으로써 업데이트가 가능하다.

MC vs TD

MC와 TD에서 가장 다른 부분은 return Gt이다. MC에서는 종료가 된 episode들로 부터 학습을 하기 때문에 정확한 Gt값을 알 수 있다. 하지만 TD는 그렇지 않기 때문에 return Gt를 추정한 값을 사용해야 한다. 따라서 TD(0)이라고 가정했을 때(뒤에서 이 용어에 대해 자세히 설명한다.),Gt 에 해당하는 부분을 Rt+1+γV(St+1)로 바꿔서 사용하도록 한다.

• 빨간색 term을 TD target이라고 부르고, a 뒤에 있는 항을 TD error라고 부른다고 한다.

TD는 final outcome이 나오기 전에 학습을 할 수 있지만 MC는 결과가 나올 때까지 기다려야 한다. 하지만 TD는 바로바로 학습을 하지만 이 episode가 실제로 종료될 것이라는 보장이 없고, MC는 애초에 끝난 결과를 가지고 학습하므로 확실히 종료된다는 보장을 가지고 있게 된다.

Bias/Varaince Trade-off

v가 실제 Gt에 대해서 unbiased하다고 하면 TD target도 unbiased하다고 할 수 있다. 하지만 TD target은 추정치인 V(St+1)를 사용하기 때문에 bias가 생길 수 밖에 없다.

대신 TD target은 하나의 step에서 계산을 하기 때문에 작은 variance를 가지게 된다. 반면 MC는 episode가 어떤 state sequence로 이루어졌는가에 따라서 value function이 달라지기 때문에 variance가 높게 된다.

즉 종합해보면 MC는 높은 variance를 가지지만 bias가 아예 존재하지 않는다.(정확히 구해진 값들을 사용하기 때문에) 따라서 좋은 수렴 조건을 가지고 있으며, 초기값에 영향을 받지도 않는다.

TD는 낮은 variance를 가지고 있지만 bias가 생기게 된다. 보통 MC보다 더 효과적이고 TD(0)은 수렴을 하지만 항상 그렇다고 볼 순 없다. 또한 초기값에 영향을 받게 된다.

Batch MC and TD

MC, TD 방식 모두 episode를 무한하게 반복하면 실제 value에 수렴할 수 있다. 하지만 batch 방식으로 유한한 episode들을 가지고 학습을 하면 어떻게 될까?

위 예시를 통해서 살펴보도록 한다. 이 예시에서는 8개의 episode들이 있고, 첫번째 episode에서는 A가 reward 0을 받고, B로 가서 reward 0을 받게 된다. 2~7번째 episode들에서는 B에서 reward 1을 받고, 마지막엔 0을 받게 된다.

즉 위 내용을 종합해보면 A는 100% 확률로 B로 가게 될 것이고 이 때 return은 0이 될 것이다.

그러므로 MC에서는 A는 1번 episode에서만 나타나고 이 때 최종 보상이 0이기 때문이다. TD에서는 다른 episode들이 진행이 되면서 A의 value도 같이 업데이트가 될 것이다.

MC는 최종적으로 완료한 episode들의 보상을 사용해서 학습을 하므로 V(A) = 0이 되었다. TD(0) 방식은 max likelihood Markov 방식을 사용하여 수렴하는 알고리즘이기 때문에 V(A) = 0.75가 된다.

이를 보아 TD는 MDP 특성을 가지는 알고리즘이므로 MDP 환경에서 더 유용하고, MC는 그렇지 않기 때문에 MDP가 아닌 환경에서 더 유용하게 된다.

다음은 backup과 bootstrapping에 따른 RL의 분류이다.

TD(λ)

지금까지 설명한 TD들은 TD(0)에 해당하는 것들이었다. 이제 이를 확장해서 TD(λ)로 사용하도록 한다. TD는 guess로 guess를 예측하는 것인데, λ는 steps들에게 얼만큼의 가중치를 부여할지에 대한 값이다. 즉 수식으로 표현하면 다음과 같다.

n=1에 해당하는 것이 우리가 지금까지 보았던 TD(0)에 해당한다. n=2는 G⁽²⁾t와 같이 표현이 될 것이다. 그리고 n이 무한대까지 간다면 이는 종료가 될 때까지 진행한다는 것과 같으므로 MC와 같아지게 된다.

따라서 적당한 n을 잘 선택할 수 있으면 TD와 MC의 장점을 모두 취할 수 있게 된다.

n step에서 n을 고르는 방법은 크게 두 가지 방법이 있다.

• Forward-view TD(λ)

  • MC와 TD의 절충안이 n-step인 것처럼, 여러 개의 n-step을 선택하여 이의 평균을 취하면 각 n-step의 장점을 모두 가질 수 있게 된다. 이 때, 단순히 산술평균을 사용하는 것이 아니라 λ라는 weight를 이용해서 가중 평균을 취하도록하고 이를 Forward-view라고 한다.

    

• Backward-view TD(λ)

  • 이제는 다시 forward-view TD(λ)에서 time-step마다 update할 수 있는 방법을 알아본다. 여기서 eligibility trace라는 개념이 나오게 된다. 이는 과거에 방문했던 state 중에서 현재 얻게 되는 reward에 영향을 주는 state를 판단해, 현재 얻게 되는 reward를 해당 state에 나누는 것이다.

  • 이 때, 영향을 준 것 같은 idx를 credit이라고 하고, 이 credit을 배정할 때 다음 두 개를 사용한다.

    • Frequency heuristic, Recency heuristic