02. Multi-step TD

nawnoes·2020년 7월 24일
0

Reinforcement Learning

목록 보기
2/3

Multi-step TD

Model-Free prediction

MDP를 모르는 경우에도 어떻게 prediction을 하고 어떻게 control을 할지.
prediction은 value를 찾는 문제. MC와 TD가 있다.

MC(Monte-Carlo Leanring)

에피소드를 끝까지 수행하고 얻은 결과에 대해 평균으로 value를 취한다. 실제 수행한 값의 평균을 취한다.

  • 목표: Policy π\pi 를 따라 수행한 에피소드로 부터 VπV_{\pi}를 학습하는것
  • return은 discounted reward의 총합
  • (Vt)(V_t) 는 실제 에피소드가 끝나고 얻은 반환 값 GtG_t을 향해 업데이트

    V(St)V(St)+α(GtV(St))V(S_t) {\leftarrow} V(S_t) + \alpha( G_t - V(S_t))

TD(Temporal-Difference Learning)

에피소드를 끝까지 수행하지 않고, 추측한 값을 통해 보상을 업데이트 하는것.

TD(0)TD(0)

: 한스텝 앞(t+1)을 보고 현재(t)의 V(St)V(S_t)를 업데이트 하는것. n-step TD는 N 스텝 앞을 보고 현재의 V(St)V(S_t)를 업데이트 하는것. 현재의 가치를 예측한 추측값을 한스템 더 가서 추측한 값으로 업데이트를 하는것.

V(St)V(St)+α(Rt+1+γV(st+1)V(St))V(S_t) {\leftarrow} V(S_t) + \alpha(R_{t+1} + \gamma V(s_{t+1}) - V(S_t))

  • TD target: Rt+1+γV(st+1)R_{t+1} + \gamma V(s_{t+1})
  • TD error: Rt+1+γV(st+1)V(St)R_{t+1} + \gamma V(s_{t+1}) - V(S_t)

MC와 TD의 차이

MC

  • complete
  • function approximation에서 Vπ(S)V_{\pi}(S)에수렴을 잘한다.
  • 초기값에 덜 민감
  • 사용과 이해에 편하다.

TD는

  • in-complete
  • function approximation에서 Vπ(S)V_{\pi}(S)에 수렴을 못할 수도 있다.
  • 초기값에 민감

N-Step TD

  • Bootstrapping: 추측치로 추측치를 업데이트 하는것을 bootstrapping 이라 한다. 업데이트에 etstimate가 포함된다. (Depth 관점)
  • Sampling: 탐색에 있어 너비에 대해 샘플링 하였는지. (Width 관점)

N-step TD

N 스텝의 값으로 업데이트를 하는것이 n-step TD

TD와 MC의 반환값
  • n=1 (TD) ---- Gt1=Rt+1+γV(St+1)G^{1}_t = R_{t+1} + \gamma V(S_{t+1})
  • n=2 ---- Gt2=Rt+1+γRt+2+γ2V(St+2)G^{2}_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 V(S_{t+2})
    ...
  • n=\infin (MC) ---- Gt=Rt+1+γRt+2+...+γT1V(ST)G^{\infin}_t = R_{t+1} + \gamma R_{t+2} + ... + \gamma^{T-1} V(S_{T})
n-step의 반환값
  • Gt(n)=Rt+1+γRt+2+...+γn1Rt+n+γnV(St+n)G^{(n)}_t = R_{t+1} + \gamma R_{t+2} + ... + \gamma^{n-1} R_{t+n} +\gamma^{n} V(S_{t+n})

이외의 TD

  • Average n-step
  • TD(λ)\lambda)
    • forward-view TD(λ)\lambda)
    • backward-view TD(λ)\lambda)

업데이트 방법

  • Online: 에피소드의 매 스텝마다 업데이트가 되는것
  • Offline: 에피소드가 끝나고 난 후 업데이트 되는것

Reference

0개의 댓글