강화학습 Chapter 04) Model-free Prediction

 

강화학습 Chapter 04) Model-free Prediction

 

• Model-Free: 환경에 대한 model를 모르기 때문에, agent는 외부적인 상호작용을 통해 그 model에 대해 계산한다
  1. Monte Carlos
  2. Temporal Difference
• → Model free 방법에는 2가지 존재

• Prediction :현재 optimal하지 않는 어떤 policy에 대해서 sampling을 통해 value function을 구하기 ( = evaluation)

 

 

1. Monte Carlos Prediction

⇒ "(1) episode를 끝까지 가본 후에 받은 reward들로 (2) 각 state의 value function들을 거꾸로 계산하여 Mean Return 받는 것 " [Update value V(St) toward actual return G_t]

1) Monte Carlos란?

 

⇒ "Monte-Carlo : 무엇인가를 random하게 측정하는 것"

 

• (1) episode를 끝까지 가본 후에(initial state S1에서부터 시작해서 terminal state St까지) 한 time step마다 받은 reward들로 (2) 각 state의 value function들을 거꾸로 계산해보는 것= "no boostrapping"→ " value == mean return " [Update value V(St) toward actual return G(t)]
  • (1) 그렇기 때문에 complete episodes에서만 사용 가능! = only for episodic MDPs
  • (2) 순간 순간 받았던 reward들을 시간 순서대로 discount시켜서 sample return을 구할 수 있다 (expected return 아님! mean return임 ㅇㅇ)

 

 

2) First-Visit MC vs Every-Visit MC

⇒ " 한 episode에서 어떤 state에 대해 return을 계산해놨는데, 다른 episode에서도 그 state를 지나가서 다시 새로운 return을 얻었을 경우에 그 두 개의 return을 평균을 취해준다! "

⇒ " 그러면 만약에 한 episode내에서 어떠한 state를 두 번 방문한다면 어떻게 해야 할까? "

 

 

• First-visit은 한 에피소드에서 처음 방문한 state만 인정하는 것(두 번째 그 state 방문에 대해서는 return을 계산하지 않는다)

 

• every-visit은 방문할 때마다 따로 따로 return을 계산하는 방법

⇒ 모든 State가 Unique하게 나타나는 경우, Every-Visit Monte-Carlo Policy Evaluation과 Single-Visit Monte-Carlo Policy Evaluation 중 어느 것을 활용해도 학습에서 큰 차이가 나타나지 않는다

 

3) Incremental Mean

⇒ "여러 개를 모아 놓고 한 번에 평균을 취하는 것이 아니고 하나 하나 더해가며 평균을 계산한다"

 

 

 

• 분수로 가 있는 N(St)가 점점 무한대로 가게 되는데 이를 알파(더 오래된 data를 잊도록/맨 처음 정보들에 대해서 가중치를 덜 주는 형태)로 고정해 놓으면 효과적으로 평균을 취할 수 있게 된다
  • ⇒ 매 episode마다 새로운 policy를 사용하기 때문에 non-stationary problem이므로 update하는 상수를 일정하게 고정하는 것

 

2. Temporal Difference Prediction

⇒ "(1) Time Step마다 현재의 value function을 계산하는데 (2) 주변의 state들의 value function을 사용하여 업데이트" [Update value V(St) toward estimated return R_t+1 + r V(S_t+1)]

• 여러 TD Learning 방법이 있지만 그중에서 제일 간단한 것이 TD(0) (우리가 배운 건 TD(0), 또는 one-step TD라고 한다 )

 

• "(1) Time Step마다 현재의 value function을 계산하는데 (2) 주변의 state들의 value function을 사용하여 업데이트"⇒ "bootstrapping"⇒ [Update value V(St) toward estimated return R_t+1 + r V(S_t+1)]
  • TD Target : R_t+1 + r V(S_t+1)
  : every-visit MC에서는 실제 에피소드가 끝나고 받게되는 보상을 사용해서 value function을 업데이트 하였습니다. 하지만 TD에서는 실제 보상과 다음 step에 대한 미래추정가치를 사용해서 학습을 하게 됩니다.이때 사용하는 보상과 value function의 합
  • TD Error : R_t+1 + r V(S_t+1) - V(S_t)
  • : 이 TD target과 실제 V(S)와의 차이를 TD error
• (2) 주변의 state들의 value function을 사용하여 업데이트
• (1) 한 episode가 다 끝나지 않아도 time step마다 학습 가능
• TD는 Online 학습이 가능하다

 

 

• V(s_t ) ← V(s_t )+ α[r+ γV(s_(t+1) )- V(s_t )], 식에서 α 값이 1이라면 V(s_t )는 TD Target(r+ γV(s_(t+1) ))과 같고, 이는 곧 업데이트 전의 V(s_t ) 값을 반영하지 않겠다는 것과 같다

 

 

 

 

3. MC vs TD (vs DP)

 

 

 

Bias / Variance Trade-Off

⇒ "MC는 Variance가 높고 bias는 0 / TD는 Variance가 낮고 bias가 있다"

 

 

• bais가 높다 : 중앙이 있다면 중앙으로부터 전체적으로 많이 벗어나게 됨
• variance가 높다 : 가운데로부터 벗어난 것이랑 관계없이 전체적으로 많이 퍼져있다

 

• True TD target은 V(s)의 unbiased estimate이다
• TD target은 V(S)의 biased estimate이다
• TD target은 return보다 훨씬 낮은 variance를 갖는다
• MC : variance가 높은 이유는 에피소드마다 학습하기 때문에 처음에 어떻게 했냐에 따라 전혀 다른 experience를 가질 수가 있기 때문 / 초기 value에 민감하지 않다 / 잘 수렴한다
• TD : 한 episode 안에서 계속 업데이트를 하는데 보통은 그 전의 상태가 그 후에 상태에 영향을 많이 주기 때문에 학습이 한 쪽으로 치우쳐지게 된다 / 초기 값에 매우 민감하다 / 항상 잘 수렴하지는 않는다

 

 

 

• TD가 Markov 구조에 알맞고, MC는 Markov 속성을 가지지 않은 환경에서 더 효율적이다

• Sampling : 모든 것을 알 필요가 없이 실제로 경험한 정보들을 사용함으로서 처음부터 environment에 대해서 파악함 (Model-free)
• Bootstrapping: 다른 추정치들을 기반으로 추정치들을 update한다 (그 이전에 계산해둔 것들을 현재 계산에 활용한다)
• DP : sampling 안 함 / bootstrap함
• MC : sampling 함 / bootstrap 안 함
• TD : sampling 함 / bootstrap 함