들어가며...

Monte Carlo와 TD(0)는 Value를 학습하는 두 끝점처럼 보였다.

TD(0)

한 Step의 Reward만 실제로 보고 바로 Bootstrap한다.

$$G_t^{(1)} = R_{t+1} + \gamma V(S_{t+1})$$

Monte Carlo

Terminal까지 실제 Reward를 모두 본다.

$$G_t = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{T-t-1}R_T$$

둘 중 하나만 선택해야 할까?

두 Step까지 실제 Reward를 본 뒤 Bootstrap하거나, 다섯 Step을 본 뒤 Bootstrap할 수도 있다. 실제 경험을 얼마나 볼지 정하는 $n$이 생기면 TD와 MC 사이에 여러 Target을 만들 수 있다.

이번 글에서는 n-step Return으로 두 방법을 연결하고, 여러 길이를 한꺼번에 섞는 TD($\lambda$), 그 계산을 Online으로 구현하는 Eligibility trace를 살펴본다.

n-step Return

$n$-step Return은 앞으로 $n$개의 Reward를 실제로 본 뒤 $S_{t+n}$의 Value로 나머지 미래를 Bootstrap한다.

$$\begin{aligned} G_t^{(n)} =& R_{t+1} + \gamma R_{t+2} + \cdots \\ & + \gamma^{n-1}R_{t+n} + \gamma^n V(S_{t+n}) \end{aligned}$$

각 항을 시간 순서로 읽으면 된다.

• 첫 Reward는 그대로 사용한다.
• 두 번째 Reward에는 $\gamma$를 한 번 곱한다.
• $n$번째 Reward에는 $\gamma^{n-1}$을 곱한다.
• 그 이후의 미래는 $\gamma^n V(S_{t+n})$로 접는다.

Update는 Target만 $G_t^{(n)}$으로 바뀐다.

$$V(S_t) \leftarrow V(S_t) + \alpha \left[ G_t^{(n)} - V(S_t) \right]$$

n=1과 n=∞

$n=1$을 대입하면,

$$G_t^{(1)} = R_{t+1} + \gamma V(S_{t+1})$$

이므로 TD(0)의 Target과 같다.

$n$이 Episode의 끝까지 길어지면 Bootstrap할 Value가 남지 않는다.

$$G_t^{(\infty)} = G_t$$

이 값이 Monte Carlo Return이다.

$$\text{TD(0)} \longleftrightarrow \text{n-step TD} \longleftrightarrow \text{Monte Carlo}$$

$n$은 실제 Reward와 추정값을 어느 비율로 믿을지 조절하는 손잡이다.

3-step Return을 계산해보기

앞으로 세 Reward가,

$$R_{t+1}=1, \quad R_{t+2}=2, \quad R_{t+3}=3$$

이고,

$$V(S_{t+3})=5, \qquad \gamma=0.9$$

라고 하자.

3-step Return은,

$$\begin{aligned} G_t^{(3)} &= 1 + 0.9\times2 + 0.9^2\times3 + 0.9^3\times5 \\ &= 1+1.8+2.43+3.645 \\ &= 8.875 \end{aligned}$$

이다.

첫 세 Reward는 실제로 관찰했고, 네 번째 Step 이후의 미래는 $V(S_{t+3})=5$라는 현재 추정을 빌렸다.

만약 세 번째 Reward 뒤에 바로 Terminal에 도착했다면 마지막 Bootstrap 항은 $0$이 된다.

$$G_t^{(3)} = 1+1.8+2.43 = 5.23$$

n이 커지면 무조건 정확할까?

$n$이 커지면 실제 Reward를 더 많이 사용하므로 Bootstrapping Bias는 줄어드는 경향이 있다. 하지만 더 많은 Action, Transition, Reward의 무작위성에 영향을 받아 Variance는 커질 수 있다.

환경과 Value 추정의 정확도에 따라 좋은 $n$이 달라진다.

초기 Value가 매우 부정확하면 한 Step 뒤의 추정을 바로 빌리는 TD(0)가 잘못된 정보를 빠르게 퍼뜨릴 수 있다. 반대로 Episode가 길고 Reward Noise가 크면 큰 $n$의 Return이 심하게 흔들릴 수 있다.

여러 n-step Return을 섞을 수 없을까?

하나의 $n$을 고르는 대신 여러 길이의 Return을 평균낼 수 있다.

예를 들어 2-step과 4-step을 절반씩 섞으면,

$$\frac{1}{2}G_t^{(2)} + \frac{1}{2}G_t^{(4)}$$

가 된다.

TD($\lambda$)는 모든 n-step Return을 기하급수적으로 가중 평균한다.

$$G_t^\lambda = (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_t^{(n)}$$

$n$번째 Return의 가중치는,

$$(1-\lambda)\lambda^{n-1}$$

이다.

$0\leq\lambda\leq1$이고, $\lambda$가 작으면 짧은 Return에 무게가 몰린다. $\lambda$가 $1$에 가까우면 긴 Return의 비중이 커진다.

Episodic task에서는 Terminal까지의 마지막 Monte Carlo Return에 남은 Weight를 붙여 전체 가중치의 합이 $1$이 되도록 처리한다.

λ의 양 끝

$\lambda=0$이면 첫 번째 Return만 남는다.

$$G_t^0 = G_t^{(1)}$$

이 경우가 TD(0)이다.

$\lambda$가 $1$에 가까워지면 Episode 끝까지 이어지는 Return에 대부분의 Weight가 모여 Monte Carlo와 가까워진다.

$$\lambda=0 \quad\Rightarrow\quad \text{short backup}$$ $$\lambda\rightarrow1 \quad\Rightarrow\quad \text{long backup}$$

$\gamma$가 미래 Reward의 시간적 중요도를 정한다면, $\lambda$는 학습 Target에서 몇 Step짜리 Return을 얼마나 섞을지 정한다.

둘은 역할이 다르다.

• $\gamma$: 문제의 목표에서 미래 Reward를 얼마나 중요하게 보는가?
• $\lambda$: Value 학습에서 긴 Backup을 얼마나 사용할 것인가?

Forward View와 계산상의 문제

지금까지의 TD($\lambda$)를 Forward view라고 한다. 현재 시점에서 앞으로 펼쳐진 여러 n-step Return을 바라보기 때문이다.

$$G_t^{(1)}, G_t^{(2)}, G_t^{(3)}, \ldots$$

개념적으로는 이해하기 쉽지만 $G_t^\lambda$를 정확히 계산하려면 미래 Reward가 필요하다. Episode가 끝날 때까지 기다려야 하므로 TD의 Online 장점이 사라지는 것처럼 보인다.

같은 효과를 과거 방향에서 계산하는 방법이 Backward view다. 지금 발생한 TD error를 최근 방문한 State들에 나눠 전달한다.

여기서 Eligibility trace가 등장한다.

Eligibility trace는 지나온 State에 남는 흔적이다

각 State $s$마다 Trace $E_t(s)$를 유지한다.

처음에는 모두 $0$이다.

$$E_0(s)=0$$

시간 $t$에 State $S_t$를 방문하면 해당 State의 Trace에 $1$을 더하고, 이전 Trace들은 $\gamma\lambda$만큼 감쇠한다.

$$E_t(s) = \gamma\lambda E_{t-1}(s) + \mathbf{1}(S_t=s)$$

$\mathbf{1}(S_t=s)$는 Indicator function이다.

• 현재 State가 $s$이면 $1$
• 아니면 $0$

방금 방문한 State는 Trace가 크고, 오래전에 방문한 State는 시간이 지날수록 작아진다. 같은 State를 여러 번 방문하면 Trace가 누적된다.

David Silver 강의에서는 이를 Recency heuristic과 Frequency heuristic의 결합으로 설명한다.

• 최근 방문한 State일수록 Trace가 크다.
• 자주 방문한 State는 Trace가 여러 번 더해진다.

TD error를 모든 Trace에 전달하기

현재 Step의 TD error는 TD(0)와 같다.

$$\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$$

하지만 현재 State 하나만 Update하지 않고 모든 State를 Trace에 비례해 Update한다.

$$V(s) \leftarrow V(s) + \alpha \delta_t E_t(s) \qquad \forall s$$

예를 들어 현재 $\delta_t=2$이고 세 State의 Trace가,

$$E_t(A)=0.1, \quad E_t(B)=0.4, \quad E_t(C)=1.0$$

이라면 $\alpha=0.1$일 때 Update 크기는,

$$\Delta V(A)=0.1\times2\times0.1=0.02$$ $$\Delta V(B)=0.1\times2\times0.4=0.08$$ $$\Delta V(C)=0.1\times2\times1.0=0.2$$

다.

현재 State와 가까운 C가 가장 크게 고쳐지고 오래된 A는 조금만 고쳐진다.

Credit assignment 문제

Episode 끝에서 큰 Reward가 나타났을 때 어떤 과거 State와 Action에 공을 돌려야 할까?

TD(0)는 Reward 정보를 한 Step씩 뒤로 전달한다. 멀리 있는 State까지 가려면 여러 Episode가 필요할 수 있다.

Eligibility trace를 사용하면 현재 TD error가 최근 방문한 여러 State에 한 번에 전달된다. Reward가 늦게 나타나는 환경에서 Credit을 더 빠르게 퍼뜨릴 수 있다.

다만 $\lambda$가 너무 크면 오래된 많은 State가 한 Update의 영향을 받아 Variance가 커질 수 있다. 너무 작으면 TD(0)처럼 Credit이 천천히 이동한다.

결국 $\lambda$도 Bias와 Variance, Credit 전달 속도 사이의 Hyperparameter다.

Accumulating trace와 Replacing trace

앞에서 사용한 식은 방문할 때 $1$을 더하는 Accumulating trace다.

$$E_t(s) = \gamma\lambda E_{t-1}(s) + 1 \qquad \text{if }S_t=s$$

같은 State를 짧은 시간 안에 반복 방문하면 Trace가 $1$보다 커질 수 있다.

Replacing trace는 방문한 State의 Trace를 $1$로 교체한다.

$$E_t(s)=1 \qquad \text{if }S_t=s$$

나머지 State의 Trace는 계속 $\gamma\lambda$로 감쇠한다.

두 방식은 반복 방문을 얼마나 강하게 반영할지에서 차이가 있다. 처음에는 TD($\lambda$)의 핵심 구조를 이해한 뒤 구현 단계에서 구분해도 충분하다.

Forward view와 Backward view가 같은 이유

Forward view는 여러 n-step Return을 가중 평균해 현재 State를 Update한다.

Backward view는 매 Step 발생한 TD error를 Eligibility trace를 통해 과거 State에 나눠 전달한다.

겉모습은 반대지만 적절한 조건 아래 Episode 전체에서 누적되는 Update는 같은 결과를 만든다.

David Silver 강의의 표현처럼 Forward view는 이론을 제공하고 Backward view는 Mechanism을 제공한다.

SARSA(λ)로 확장하기

State value의 Trace를 State-Action pair로 확장하면 SARSA($\lambda$)를 만들 수 있다.

$$E_t(s,a) = \gamma\lambda E_{t-1}(s,a) + \mathbf{1}(S_t=s,A_t=a)$$

SARSA의 TD error는,

$$\delta_t = R_{t+1} + \gamma Q(S_{t+1},A_{t+1}) - Q(S_t,A_t)$$

이고 모든 State-Action value를 Trace에 비례해 Update한다.

$$Q(s,a) \leftarrow Q(s,a) + \alpha\delta_tE_t(s,a)$$

현재 경험의 TD error가 최근 지나온 여러 State-Action pair에 전달된다.

이번 글에서 기억할 것

이번 글의 핵심은 다음과 같다.

n-step TD는 실제 Reward를 몇 Step 볼지 조절하고, TD($\lambda$)는 여러 길이의 Return을 섞으며, Eligibility trace는 그 효과를 과거 방향으로 Online 계산한다.

조금 더 나누면 다음과 같다.

1. $n$-step Return은 $n$개의 Reward 뒤에 $V(S_{t+n})$로 Bootstrap한다.
2. $n=1$은 TD(0), Episode 끝까지 가면 Monte Carlo다.
3. 작은 $n$은 낮은 Variance, 큰 $n$은 작은 Bootstrapping Bias의 경향이 있다.
4. $\lambda$-return은 모든 n-step Return의 가중 평균이다.
5. Eligibility trace는 최근·빈번하게 방문한 State에 큰 Credit을 준다.
6. Forward view는 의미를, Backward view는 Online 계산 방법을 보여준다.

여기까지가 Table로 Value를 저장하는 Model-free RL의 기본 흐름이다. 하지만 이미지, 연속적인 Robot 자세처럼 State가 너무 많으면 State마다 $V(s)$나 $Q(s,a)$를 한 칸씩 저장할 수 없다.

다음 글에서는 Value table을 Parameter를 가진 Function으로 바꾸는 Value Function Approximation을 살펴본다. 이 단계부터 Linear function과 Neural Network가 강화학습 안으로 들어온다.

참고 자료

• David Silver, Lecture 4: Model-Free Prediction
• David Silver, Lecture 5: Model-Free Control
• 서울대학교 DSBA 연구실, Introduction of Reinforcement Learning
• Sutton & Barto, Reinforcement Learning: An Introduction, 2nd Edition