데이터사이언스 대학원 강화학습 수업을 듣고 정리한 내용입니다.
n-step TD 방법은 MC와 one-step TD 사이의 있는 방법이다. n-step TD는 n-step 만큼 bootstrapping 한다. Bootstrap이란 추정된 가치 혹은 수익을 기반으로 value function을 업데이트 한다는 뜻이다.
name n equation TD(0) 1 G t ( 1 ) = R t + 1 + γ V ( S t + 1 ) G_t^{(1)} = R_{t+1} + \gamma V(S_{t+1}) G t ( 1 ) = R t + 1 + γ V ( S t + 1 ) TD(1) 2 G t ( 2 ) = R t + 1 + γ R t + 2 + γ 2 V ( S t + 2 ) G_t^{(2)} = R_{t+1} + \gamma R_{t+2} + \gamma^2 V(S_{t+2}) G t ( 2 ) = R t + 1 + γ R t + 2 + γ 2 V ( S t + 2 ) ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ MC ∞ \infty ∞ G t ∞ = R t + 1 + γ R t + 2 + γ 2 R t + 3 + ⋯ + γ t − 1 R T G_t^{\infty} = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots + \gamma^{t-1} R_T G t ∞ = R t + 1 + γ R t + 2 + γ 2 R t + 3 + ⋯ + γ t − 1 R T
n-step TD Target
G t ( n ) = G t : t + n = R t + 1 + γ R t + 2 + γ 2 R t + 3 + ⋯ + γ n − 1 R t + n + γ n V t + n − 1 ( S t + 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}) G t ( n ) = G t : t + n = R t + 1 + γ R t + 2 + γ 2 R t + 3 + ⋯ + γ n − 1 R t + n + γ n V t + n − 1 ( S t + n ) n-step return 계산시 t t t t + 1 t+1 t + 1 ( R t + 1 , ⋯ , R t + n ) ( R_{t+1}, \cdots, R_{t+n} ) ( R t + 1 , ⋯ , R t + n ) t + n t+n t + n
V t + n ( S t ) : = V t + n − 1 ( S t ) + α [ G t ( n ) − V t + n − 1 ( S t ) ] , 0 ≤ t < T V_{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 V t + n ( S t ) := V t + n − 1 ( S t ) + α [ G t ( n ) − V t + n − 1 ( S t )] , 0 ≤ t < T pseudo code
$\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 π [ G t ( n ) ∣ S t = s ] − v π ( s ) ∣ ≤ γ n max s ∣ V t + 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 s max ∣ E π [ G t ( n ) ∣ S t = s ] − v π ( s ) ∣ ≤ γ n s max ∣ V t + n − 1 ( s ) − v π ( s ) ∣ n-step SARSA
n-step return 계산시 state value 대신 action value를 사용한다.
G t ( n ) = G t : t + n = R t + 1 + γ R t + 2 + γ 2 R t + 3 + ⋯ + γ n − 1 R t + n + γ n Q t + n − 1 ( S t + n , A t + 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}) G t ( n ) = G t : t + n = R t + 1 + γ R t + 2 + γ 2 R t + 3 + ⋯ + γ n − 1 R t + n + γ n Q t + n − 1 ( S t + n , A t + n ) 그리고 GPI update에도 마찬가지로 q-value function으로 업데이트 한다.
Q t + n ( S t , A t ) : = Q t + n − 1 ( S t , A t ) + α [ G t ( n ) − Q t + n − 1 ( S t , A t ) ] , 0 ≤ t < T Q_{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 Q t + n ( S t , A t ) := Q t + n − 1 ( S t , A t ) + α [ G t ( n ) − Q t + n − 1 ( S t , A t )] , 0 ≤ t < T 다른 states에서는 Q t + n ( s , a ) = Q t + n − 1 ( s , a ) Q_{t+n}(s, a) = Q_{t+n-1}(s, a) Q t + n ( s , a ) = Q t + n − 1 ( s , a )
pseudo code
Expected SARSA의 경우에는 V ˉ t + n − 1 ( S t + n ) : = ∑ a π ( a ∣ s ) Q t ( s , a ) \bar{V}_{t+n-1}(S_{t+n}) := \sum_a \pi(a\vert s) Q_t(s, a) V ˉ t + n − 1 ( S t + n ) := ∑ a π ( a ∣ s ) Q t ( s , a )
n-step Off-Policy Learning
n-step importance sampling ratio를 통해 off-policy learning을 할 수 있다.
ρ t : h = ∏ k = t min ( h , T − 1 ) π ( A k ∥ S k ) b ( A k ∥ S k ) \rho_{t:h} = \prod_{k=t}^{\min(h, T-1)} \frac{\pi(A_k \Vert S_k)}{b(A_k \Vert S_k)} ρ t : h = k = t ∏ m i n ( h , T − 1 ) b ( A k ∥ S k ) π ( A k ∥ S k ) 이를 업데이트 규칙에 대입하면 다음과 같다.
V t + n ( S t ) ← V t + n − 1 ( S t ) + α ρ t : t + n − 1 [ G t : t + n − V t + n − 1 ( S t ) ] , 0 ≤ t < T V_{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 V t + n ( S t ) ← V t + n − 1 ( S t ) + α ρ t : t + n − 1 [ G t : t + n − V t + n − 1 ( S t )] , 0 ≤ t < T n-step SARSA의 경우에는 다음과 같다.
Q t + n ( S t , A t ) ← Q t + n − 1 ( S t , A t ) + α ρ t + 1 : t + n − 1 [ G t : t + n − Q t + n − 1 ( S t , A t ) ] , 0 ≤ t < T Q_{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 Q t + n ( S t , A t ) ← Q t + n − 1 ( S t , A t ) + α ρ t + 1 : t + n − 1 [ G t : t + n − Q t + n − 1 ( S t , A t )] , 0 ≤ t < T “n-step SARSA off-policy learning”
pseudo code
그렇다면 Q-learning은 off-policy 알고리즘인데 왜 importance sampling ratio를 사용하지 않는가1 a ′ a' a ′ π ( a ′ ∣ s ′ ) = 1 \pi(a' \vert s') = 1 π ( a ′ ∣ s ′ ) = 1 0 0 0
← 이전 글 6. Temporal-Difference Learning 다음 글 → 8. Planning and Learning with Tabular Methods 
