[RL] Lecture 4: Model-Free Prediction

1. Introduction

1.1 Model-Free

• Environment의 MDP에 대한 정보를 알지 못하는 상황
• MDP를 모른다
  • Agent가 어떤 action을 했을 때 얻는 Reward \(R_t\)를 사전에 알지 못한다. → 직접 경험해 봐야 함
  • Agent가 어떤 action을 했을 때 어떤 next-state로 transition할지를 결정하는 probability \(P_{ss'}^a\)를 알지 못한다.
    • 직접 경험해봐야 어떤 next-state에 도달했는지를 알 수있다.
    • 많이 경험하더라도 어떤 정확한 “확률 분포”를 알 수 없다.

1.2 Model-Free일 때 문제의 종류

• Prediction 문제 : MDP를 모를 때, Value function을 측정하는 과정
• Control 문제 : MDP를 모를 때, Optimal value function, policy를 찾는 과정 → Next lecture

---

2. Monte-Carlo Learning

2.1 Monte-Carlo Reinforcement Learning

Monte-Carlo 방식 : 계속된 실행으로 도출한 실제 값들을 통해서 추정하는 방식

• MC는 “경험”을 통해 직접 배운다.
• MC는 Model-free : MDP transitions, rewards를 모른다
• MC는 완료된 episode로 부터 배운다
• episode가 끝날 때 까지의 reward의 cumulative sum이 return, 그 값을 평균낸 것이 value
• 종료된 episode에 대해서만 적용이 가능하므로, 모든 episode는 종료되어야 한다.

2.2 Monte-Carlo Policy Evaluation

• Goal : Policy \(π\) 에서 경험을 통해 \(v_π\)를 배운다.

• return : 모든 discounted reward의 cumulative sum

• Value function : return의 기대값이다. (같은 policy에서도 episode마다 value가 다르기 때문에 확률변수 → 기대값)

• Monte-Carlo policy evaluation은 return 기대값 대신에 empirical mean을 사용한다.
  (기대값이 아닌 실제 경험의 평균)

2.3 Monte-Carlo Policy Evaluation

• 모든 State를 방문한다는 가정하에 적용할 수 있다.
  • 우리는 모든 State의 value를 평가하는 것이 목적이기 때문.

First-Visit MC update : Agent가 해당 State에 처음 방문 했을 때만, Counter 증가, return을 더한다.

• Counter 증가 : \(N(s)\) ← \(N(s) + 1\)
• total return 증가 : \(S(s)\) ← \(S(s)\) + \(G(t)\)
• Value : \(V(s)\) = \(S(s)/N(s)\)
• 큰 수의 법칙에 의해, \(N(s)\) → \(∞\) 이면 \(V(s)\) → \(v_π(s)\) 이다.

Every-Visit MC : Agent가 해당 State에 방문할 때 마다, Counter 증가, return을 더한다.

• Counter 증가 : \(N(s)\) ← \(N(s) + 1\)
• total return 증가 : \(S(s)\) ← \(S(s)\) + \(G(t)\)
• Value : \(V(s)\) = \(S(s)/N(s)\)
• 마찬가지로 큰 수의 법칙에 의해, \(N(s)\) → \(∞\) 이면 \(V(s)\) → \(v_π(s)\) 이다.

2.4 Incremental Monte-Carlo

한번에 평균을 구하여 업데이트를 하는 것이 아니라 하나의 episode가 끝날때마다 조금씩 평균을 업데이트 하는 방법

• Incremental Mean
  • 점진적으로 평균을 구하는 방법
  • 값이 들어올 때마다 평균을 구하는 것이 아니라, 직전 값까지 평균\(_{(1)}\)을 구해놓고, 새로운 값에 대한 증감분\(_{(2)}\)만 평균에 적용한다.

  • 이렇게 되면 모든 State의 값을 저장해 두고 나중에 모든 값을 불러와 평균을 계산하는 것이 아니라, 바로 계산을 진행해 값을 저장해둘필요가 없다.

    

• MC Update
  • Incremental Mean을 이용하면 \(V(s)\)를 episode 하나가 끝난 뒤에 incrementally update할 수 있다.

  • for each state \(S_t\) with return \(G_t\)

    

  • 실제값 \(G_t\)와 학습중인 Value \(V(S_t)\)의 차이인 error만큼 조금씩 업데이트

    

\(N(S_t)\)를 사용하지 않는 경우

• \(1/N(S_t)\)가 아닌, 어떤 고정 상수 \(α\)를 곱해서 업데이트 하는 방법
• \(1/N(S_t)\)는 방문한 State가 많아 질수록 작아지기 때문에 최신 episode보다 과거의 episode를 더 중요하게 판단한다. (전체 값에 영향을 많이 미친다.)
• 고정 상수 \(α\)를 곱해서 업데이트하면 과거의 episode를 forget하는 효과를 보일 수 있다.
• non-stationary probelm문제에서 이 방식이 더 효과적일 수 있다.
  • MDP가 일정하지 않고 조금씩 변화하는 문제 (Policy가 변한다)

---

3. Temporal-Differance Learning

• TD는 “경험”을 통해 직접 배운다.
• TD는 Model-Free : MDP를 모른다, transitions / rewards
• TD는 종료되지 않은 incomplete episode를 통해서도 배울 수 있다. (MC와의 차이점)
• TD updates a guess towards a guess

3.1 MC and TD

• Goal : Policy \(π\)를 통해 경험한 episode를 이용해서 \(v_π\)를 찾는 것

• MC Policy evaluation : Value를 실제 return \(G_t\)과의 차이를 이용해 update

• TD Learning algorithm : Value를 1-step을 더 진행했을 때, 추정된 return를 이용해 update
  • TD error : TD target과 실제 값의 차이

  

  • 1-step을 더 진행하면 1-step만큼의 정확한 실제 정보(=reward)가 반영되기 때문에 더 정확한 Value를 가지고 있을 것이다.

3.2 Advantages and Disadvantages of MC vs. TD

• TD는 final outcome이 나오기 전에 Learn할 수 있다.
  • TD는 매 단계마다 Learn이 가능
  • MC는 episode가 끝날 때 까지 기다렸다가 Learn해야한다.
• TD는 final outcome 없이도 Learn할 수 있다.
  • TD는 incomplete sequences를 통해서도 Learn 할 수 있다.
  • MC는 complete sequences를 통해서만 Learn 할 수 있다.
  • TD는 continuing(non-terminating) 환경에서도 가능하다.
  • MC는 episodic(terminating) 환경에서만 가능하다.

bias와 variance

• bias

  • return \(G_t\)는 \(v_π(S_t)\)에 대한 unbiased estimate이다.
    즉, value function의 정의에 따라 \(G_t\)를 계속 sampling하면 결국 \(v_π(S_t)\)에 수렴할 것이다.

  • true TD target \(R_{t+1}+γv_π(S_{t+1})\)은 \(v_π(S_t)\)에 대한 unbiased estimate이지만, 우리는 \(v_π\)의 실제 값을 알지 못한 상태에서 계산하기 때문에 TD target은 \(R_{t+1}+γV(S{t+1})\)은 biased estimate이다.

  • 추정값을 이용하여 갱신하기 때문에 발생하는 bias가 존재하고 따라서 수없이 많이 반복하더라도 TD target이 실제 \(v_π(S_t)\)에 정확히 수렴하리라는 보장은 가질 수 없다.

• variance
  • TD target은 반드시 return보다 더 작은 variance를 가진다.
    • Return은 수많은 랜덤한 action, transition, reward를 이용하여 계산되지만 TD target은 딱 한번의 랜덤한 action, transition, reward에 의해 계산되기 때문이다.
      → 1-step에서 발생할 수 있는 랜덤성은 episode가 끝날 때까지 발생할 수 있는 랜덤성보다 훨씬 작다.
  • variance가 클수록 그 확률분포에서 어떤 것을 sampling 했을 때 뽑힌 sample들에대한 편차가 클 수 있다. → 정확성이 떨어진다.

---

• MC : high variance, zero bias
  • (function approximation에서도) 수렴성이 좋다.
  • initial value에 그다지 민감하지 않다. (episode가 terminate하고 update하기 때문)
  • 이해하고 사용하기 간단하다.
• TD : low variance, some bias
  • MC보다 대부분 더 효율적이다.
  • TD(0)은 \(v_π(s)\)로 수렴하긴 하지만, function approzimation에서는 수렴함이 보장되지 않는다.
  • MC에 비하여 더 initial value에 민감하다. (step마다 update하기 때문에 초기값이 중요)
  • bias를 가진 알고리즘이 동작을 하는 것은 맞나? ⇒ Luckily Yes!

3.3 Batch MC and TD

• MC와 TD가 무한대로 experience했을 때 수렴하는 것은 자명하다.
• 하지만 K개의 유한한 episode만을 가지고 있다면 MC와 TD는 수렴할까?

AB Example

MC와 TD에서의 Value

• MC : V(A) = 0
  • 전체 episodes 중에서 A에 도달한 경우 1번, reward 0
• TD : V(A) = 0.75
  • TD에서의 V(A) = reward + B에서의 Value이다. 즉 V(B)의 Value인 0.75로 갱신
• Certainty Equivalence
  • MC : minimum MSE

  

  • TD(0) : max likelihood Markov model

  

⇒ 한정된 개수의 episode를 이용할 때는 MC와 TD를 사용하여 계산했을 때 value에 차이가 발생한다.

• TD는 Markov property를 사용하여 value를 추측한다. → Markov 환경에서 더 효율적이다.
• MC는 Markov property를 사용하지 않고 value를 추측한다. → non-Markov 환경에서 더 효율적이다.

3.4 More Difference

• Backup 방법의 차이

  • Monte-Carlo Backup : DFS

    

  • Temporal-Differnce Backup : (1-step) Bootstraping

    

  • Dynamic Programming Backup : BFS

    

Bootstrapping : estimate로 update (Depth 관점)

• MC : Bootstrap X (MC는 Terminate까지 감)
• DP : Bootstrap O
• TD : Bootstrap O

Sampling : expectation으로 update (Width 관점)

• MC : Sampling O
• DP : Sampling X
• TD : Sampling O

• full backups : MDP를 알기 때문에(Model-based) 가능하다.
• Exhausive search : 사실상 모든 경우의 수를 다 찾는 것 = 비효율적, 의미가 없다

---

4. TD(λ)

4.1 n-Step Prediction

TD를 적용할 때는 1-step만 진행하고 바로 update를 진행할 수도 있지만
N의 step을 진행하고 나서 그 때의 값을 이용하여 update하는 방법을 사용할 수도 있다.
→ 이때 terminal state까지의 step을 경험한뒤에 update하는 방법은 MC와 같은 방식

• n-step TD learning
  • n-step TD target : \(G_t^{(n)}\)
  • n-step TD error : \(δ_t=G_t^{(n)}−V(S_t)\) : target과 실제 값의 차이

TD(0)과 MC사이에는 둘의 효과를 극대화할 수 있는 가장 적절한 sweet-spot이 존재한다.

4.2 Forward-View TD(λ)

• Averaging n-step Returns
  • 여러가지의 n-step을 따라 수행해서 구한 return이 있을 때, 각각의 return을 평균한 값을 사용하여 학습해도 된다

• 2-step 과 4-step의 return을 평균을 구해도됨.

Forward-View TD(λ)

• TD(λ) : TD(0) ~ MC까지 모든 것을 평균내도 됨
• λ-return : TD(0) ~ MC까지 진행했을 때의 모든 return의 평균 \(G_t^λ\)
• 각 n-step return \(G_t^{(n)}\)에 대하여 \((1−λ)λ^{(n−1)}\) weight를 적용하여 계산한다.
• n이 커질수록 λ가 계속해서 곱해지게 되므로 더 작은 가중치를 가지게 된다.

TD(λ) weight function

Geometry Mean을 쓰는 이유

• 계산적으로 편하다.
• Momoryless하게 학습이 가능하다.
• TD(0)와 같은 비용으로 TD(λ)를 계산할 수 있다.

Forward-View TD(λ)

TD(λ) : TD(0) ~ TD(∞) MC의 평균

• MC와 똑같이 episode가 끝나고 나서야 계산이 가능하다.
  • MC를 구해야 하기 때문에 끝까지 계산을 해야한다.

  ⇒ TD(0)의 장점이 사라짐

4.3 Backward-View TD(λ)

• TD(0)의 장점도 챙기기 위해 등장

• Eligibility trace \(E_t(s)\)
  • 어떤 사건이 일어났을 때, 그 사건에 대한 책임이 가장 큰 요소를 더 많이 update하는 방법
• 책임이 큰 것을 판단하는 방법
  • Frequency heuristic : 가장 빈도가 높은 State의 책임이 크다
  • Recency heuristic : 가장 최근의 State의 책임이 크다

⇒ Eligibility traces : 두 heuristics를 합친 것

• TD(0)와 TD(\(λ\))의 장점을 모두 가진다.
  • online(매 step)마다 update할 수 있다.
  • episode가 끝나지 않는 환경에서도 사용할 수 있다.
• t 일때의 TD-error에 대해 그 상황에서의 eligibility trace값을 곱한만큼 update한다.
  → 수학적으로 TD(\(λ\))와 동일함

4.4 Relationship Between Forward and Backward TD

• TD(\(λ\)) and TD(0)
  • \(λ\) = 0일때, 오직 current state만이 update된다.

  

  • TD(0) update

  

• TD(\(λ\)) and MC
  • \(λ\)=1이면 TD(λ)는 MC처럼 에피소드 종료 후 한 번에 업데이트한다.
    • \(λ\) = 1, credit(reward)은 episode가 끝날때 까지 유예된다.
  • 오프라인 업데이트는 에피소드가 끝난 후 수행된다.
  • TD(1)과 MC는 에피소드 당 동일한 총 업데이트를 수행한다.

  

맨 위로 이동하기

RL 카테고리 내 다른 글 보러가기