Soopace

Notes

7. n-step Bootstrapping

데이터사이언스 대학원 강화학습 수업을 듣고 정리한 내용입니다. n-step TD 방법은 M...

데이터사이언스 대학원 강화학습 수업을 듣고 정리한 내용입니다. HeadImg

n-step TD 방법은 MC와 one-step TD 사이의 있는 방법이다. n-step TD는 n-step 만큼 bootstrapping 한다. Bootstrap이란 추정된 가치 혹은 수익을 기반으로 value function을 업데이트 한다는 뜻이다.

namenequation
TD(0)1Gt(1)=Rt+1+γV(St+1)G_t^{(1)} = R_{t+1} + \gamma V(S_{t+1})
TD(1)2Gt(2)=Rt+1+γRt+2+γ2V(St+2)G_t^{(2)} = R_{t+1} + \gamma R_{t+2} + \gamma^2 V(S_{t+2})
⋮\vdots⋮\vdots⋮\vdots
MC∞\inftyGt∞=Rt+1+γRt+2+γ2Rt+3+⋯+γt−1RTG_t^{\infty} = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots + \gamma^{t-1} R_T

n-step TD Target

Gt(n)=Gt:t+n=Rt+1+γRt+2+γ2Rt+3+⋯+γn−1Rt+n+γnVt+n−1(St+n)G_t^{(n)} = G_{t:t+n} = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n V_{t+n-1}(S_{t+n})

n-step return 계산시 tt에서 t+1t+1으로 transition될 때 접근할 수 없는 future reward 항이 포함되어 있다 (Rt+1,⋯ ,Rt+n)( R_{t+1}, \cdots, R_{t+n} ). 따라서 t+nt+n 시점에서 업데이트가 진행된다.

Vt+n(St):=Vt+n−1(St)+α[Gt(n)−Vt+n−1(St)],0≤t<TV_{t+n}(S_t) := V_{t+n-1}(S_t) + \alpha \lbrack G_t^{(n)} - V_{t+n-1}(S_t) \rbrack, \quad 0 \leq t \lt T
“n-step TD”
pseudo code

HeadImg

$\tau$는 $t \geq n-1$를 체크하려고 하는 것이다. 즉, $t$가 $n$ 이후에 업데이트를 시작한다. $R_{t+n}$ 이후의 값은 value function $V_{t+n-1}(S_{t+n})$의 값으로 계산된다. 최악의 경우에도 n-step return의 기댓값이 $V_{t+n-1}(s)$에서 추정정되는 값보다 작거나 같다는 특성을 가지고 있으며 이를 **error reduction property**라고 한다.
max⁡s∣Eπ[Gt(n)∣St=s]−vπ(s)∣≤γnmax⁡s∣Vt+n−1(s)−vπ(s)∣ \underset{s}{\max} \vert \Bbb{E}_\pi \lbrack G_t^{(n)} \vert S_t = s \rbrack - v_\pi(s) \vert \leq \gamma^n \underset{s}{\max} \vert V_{t+n-1}(s) - v_\pi(s) \vert

n-step SARSA

n-step return 계산시 state value 대신 action value를 사용한다.

Gt(n)=Gt:t+n=Rt+1+γRt+2+γ2Rt+3+⋯+γn−1Rt+n+γnQt+n−1(St+n,At+n)G_t^{(n)} = G_{t:t+n} = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n Q_{t+n-1}(S_{t+n}, A_{t+n})

그리고 GPI update에도 마찬가지로 q-value function으로 업데이트 한다.

Qt+n(St,At):=Qt+n−1(St,At)+α[Gt(n)−Qt+n−1(St,At)],0≤t<TQ_{t+n}(S_t, A_t) := Q_{t+n-1}(S_t, A_t) + \alpha \lbrack G_t^{(n)} - Q_{t+n-1}(S_t, A_t) \rbrack, \quad 0 \leq t \lt T

다른 states에서는 Qt+n(s,a)=Qt+n−1(s,a)Q_{t+n}(s, a) = Q_{t+n-1}(s, a)로 업데이트 되지 않는다.

“n-step SARSA”
pseudo code

HeadImg

Expected SARSA의 경우에는 Vˉt+n−1(St+n):=∑aπ(a∣s)Qt(s,a)\bar{V}_{t+n-1}(S_{t+n}) := \sum_a \pi(a\vert s) Q_t(s, a)를 사용한다.

n-step Off-Policy Learning

n-step importance sampling ratio를 통해 off-policy learning을 할 수 있다.

ρt:h=∏k=tmin⁡(h,T−1)π(Ak∥Sk)b(Ak∥Sk)\rho_{t:h} = \prod_{k=t}^{\min(h, T-1)} \frac{\pi(A_k \Vert S_k)}{b(A_k \Vert S_k)}

이를 업데이트 규칙에 대입하면 다음과 같다.

Vt+n(St)←Vt+n−1(St)+αρt:t+n−1[Gt:t+n−Vt+n−1(St)],0≤t<TV_{t+n}(S_t) \leftarrow V_{t+n-1}(S_t) + \alpha \rho_{t:t+n-1} \lbrack G_{t:t+n} - V_{t+n-1}(S_t) \rbrack, \quad 0 \leq t \lt T

n-step SARSA의 경우에는 다음과 같다.

Qt+n(St,At)←Qt+n−1(St,At)+αρt+1:t+n−1[Gt:t+n−Qt+n−1(St,At)],0≤t<TQ_{t+n}(S_t, A_t) \leftarrow Q_{t+n-1}(S_t, A_t) + \alpha \rho_{t+1:t+n-1} \lbrack G_{t:t+n} - Q_{t+n-1}(S_t, A_t) \rbrack, \quad 0 \leq t \lt T
“n-step SARSA off-policy learning”
pseudo code

HeadImg

그렇다면 Q-learning은 off-policy 알고리즘인데 왜 importance sampling ratio를 사용하지 않는가1? 두 policy 간의 차이를 줄이기 위해서 importance sampling을 하는데, Q-Learning은 해당 상태에서 주어진 모든 action을 확률적으로 사용하는 것이 아니라 greedy 하게 선택하기 때문에 필요가 없다. 즉, 선택되는 action a′a'의 π(a′∣s′)=1\pi(a' \vert s') = 1이 되고 나머지는 00이 되기 때문이다.

Footnotes

  1. Q-Learning: off-policy TD control ↩