ai theory

강화학습 기초 (7) - 끝까지 기다리지 않고 배우는 TD Learning

Junyoung Park · 2024-04-26 · 6 min

들어가며...

Monte Carlo는 상당히 믿음직한 Target을 사용했다. Episode를 끝까지 진행한 뒤 실제로 받은 Return $G_t$ 를 계산했다.

하지만 Game 한 판이 한 시간 걸리거나 Environment가 끝나지 않는다면 문제가 생긴다. 첫 State에서 한 행동이 괜찮았는지 배우기 위해 한 시간 뒤까지 기다려야 한다. 온도 조절 System처럼 계속 동작하는 환경에서는 Terminal 자체가 없을 수 있다.

Temporal-Difference Learning, 줄여서 TD는 한 Step을 경험할 때마다 바로 학습한다.

S_t \xrightarrow{R_{t+1}} S_{t+1}

Episode 전체의 Return을 아직 모르므로 Next State부터의 미래는 현재의 추정값 $V(S_{t+1})$ 을 빌린다.

\text{TD target} = R_{t+1} + \gamma V(S_{t+1})

실제 Reward 하나와 추정값 하나를 합쳐 현재 추정을 고친다. David Silver 강의의 표현처럼 “추정값을 다른 추정값 쪽으로 Update”하는 방식이다.

Monte Carlo와 TD의 Target

두 방법을 나란히 놓으면 차이가 선명하다.

Monte Carlo

V(S_t) \leftarrow V(S_t) + \alpha \left[ G_t-V(S_t) \right]

Target은 Episode가 끝난 뒤 알 수 있는 실제 Return이다.

TD(0)

V(S_t) \leftarrow V(S_t) + \alpha \left[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right]

Target은 바로 받은 Reward와 Next State의 현재 Value 추정이다.

MC는 실제 Return을 기다리고, TD는 한 Step 뒤의 추정값을 이용해 즉시 Update한다.

TD 뒤의 $(0)$ 은 앞으로 살펴볼 n-step이나 TD( $\lambda$ )와 구분하기 위한 이름이다. 지금은 한 Step만 실제로 보고 나머지를 바로 Bootstrap하는 가장 짧은 TD라고 생각하면 된다.

Bootstrapping은 예상으로 예상을 고치는 일이다

TD target 안에는 $V(S_{t+1})$ 가 들어 있다. 이 값도 아직 정확한 정답이 아니라 학습 중인 추정값이다.

\underbrace{R_{t+1}}_{\text{observed}} + \gamma \underbrace{V(S_{t+1})}_{\text{estimated}}

미래 전체를 실제로 보지 않고 Next State 이후는 기존 추정으로 대신하는 것을 Bootstrapping이라고 한다.

이름이 조금 낯설지만 일상에서도 자주 사용하는 방식이다. 출근 중간 지점까지 실제로 20분이 걸렸고, 그 지점에서 회사까지 평소 15분 걸린다는 예상이 있다면 전체 출근 시간을 $35$ 분으로 다시 예상할 수 있다. 회사에 도착하지 않았지만 중간 관측과 남은 구간의 추정을 합친 것이다.

현재의 추정이 틀렸다면 Next State의 추정을 빌리는 것이 불안해 보일 수 있다. 실제로 TD target에는 Bias가 생길 수 있다. 하지만 경험이 쌓이면서 Next State의 추정도 계속 수정되고, 그 정보가 앞 State로 전파된다.

TD error는 예상이 얼마나 빗나갔는가

TD target과 현재 Value의 차이를 TD error라고 하고 $\delta_t$ 로 적는다.

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

Update 식은 훨씬 짧아진다.

V(S_t) \leftarrow V(S_t) + \alpha\delta_t

숫자를 넣어보자.

현재 예상: $V(S_t)=4$
받은 Reward: $R_{t+1}=2$
Next State 예상: $V(S_{t+1})=5$
Discount factor: $\gamma=0.9$
Learning rate: $\alpha=0.1$

먼저 TD target은 다음과 같다.

2+0.9\times5=6.5

현재 예상 $4$ 와의 차이는,

\delta_t=6.5-4=2.5

다.

TD error가 양수면 예상보다 결과가 좋았다는 뜻이므로 현재 Value를 위로 고친다.

마지막 Update는,

V(S_t) \leftarrow 4+0.1\times2.5 = 4.25

가 된다.

$\delta_t<0$ 이면 Target이 현재 예상보다 작다는 뜻이므로 Value가 내려간다. TD error는 “방금 한 Step에서 미래에 대한 예상이 얼마나 놀랍게 바뀌었는가”를 나타낸다고 볼 수 있다.

왜 한 Step만 보고도 미래를 배울 수 있을까?

처음에는 TD가 너무 성급해 보인다. Next State의 Value도 추정일 뿐인데 어떻게 Terminal Reward의 정보가 멀리 있는 State까지 전달될까?

짧은 Chain을 생각해보자.

A \rightarrow B \rightarrow C \rightarrow \text{Terminal }(+10)

초기 Value가 모두 $0$ 이라고 하자.

$C$ 에서 Terminal로 이동하면 $+10$ 을 관찰해 $V(C)$ 가 올라간다.
다음 Episode에서 $B$ 에서 $C$ 로 이동하면 높아진 $V(C)$ 를 Target으로 사용해 $V(B)$ 가 올라간다.
이후 $A$ 에서 $B$ 로 이동할 때 $V(B)$ 를 빌려 $V(A)$ 가 올라간다.

Reward 정보가 실제 경험을 따라 한 Step씩 뒤로 전파된다. DP의 반복 Backup과 비슷하지만 모든 Next State를 확률로 합산하지 않고 실제로 관찰한 Transition 하나를 사용한다.

MC와 TD의 Bias-Variance 차이

MC와 TD 중 어느 쪽이 항상 좋다고 말하기는 어렵다.

Monte Carlo target

G_t = R_{t+1} + \gamma R_{t+2} + \cdots

실제 Return을 사용하므로 현재 Value 추정에 의한 Bias가 없다. 하지만 많은 Action, Transition, Reward의 무작위성에 영향을 받아 Variance가 크다.

TD target

R_{t+1} + \gamma V(S_{t+1})

현재 추정 $V(S_{t+1})$ 을 사용하므로 Bias가 있을 수 있다. 대신 무작위 결과를 한 Step만 거치므로 대체로 Variance가 낮다.

항목	Monte Carlo	TD(0)
Update 시점	Episode 종료 후	매 Step
Target	실제 Return $G_t$	$R_{t+1}+\gamma V(S_{t+1})$
Bootstrapping	하지 않음	사용
Episodic task	가능	가능
Continuing task	그대로는 어려움	가능
일반적 성향	낮은 Bias, 높은 Variance	Bias 가능, 낮은 Variance

실제 문제에서는 이 Trade-off가 학습 속도와 안정성에 영향을 준다.

DP, MC, TD를 Sampling과 Bootstrapping으로 보기

세 방법을 두 질문으로 구분하면 전체 구조가 정리된다.

가능한 Next State를 전부 평균내는가, 실제 Transition 하나를 Sample로 사용하는가?
실제 Return을 끝까지 사용하는가, 추정값으로 Bootstrap하는가?

방법	Sampling	Bootstrapping	Model 필요
Dynamic Programming	하지 않음	사용	필요
Monte Carlo	사용	하지 않음	불필요
Temporal-Difference	사용	사용	불필요

DP는 Model을 이용해 모든 결과의 Expectation을 계산한다. MC는 실제 Episode 하나를 Sample하고 끝까지 확인한다. TD는 실제 Transition 하나를 Sample하면서 Next State 이후는 추정값으로 접는다.

이 표를 기억해두면 이후 Algorithm이 무엇을 근사하는지 찾기 쉬워진다.

Online learning이 가능한 이유

TD는 Episode가 끝나기 전에 매 Step Update할 수 있다.

(S_t,R_{t+1},S_{t+1})

이 세 정보와 현재 Value table만 있으면 Update가 가능하다. 전체 Episode를 Memory에 저장해둘 필요도 없다.

이는 다음 환경에서 특히 유용하다.

Episode가 매우 긴 Game
끝나지 않는 Process control
실시간으로 상태 평가를 바꿔야 하는 System
Episode 중간에 잘리거나 일부 경험만 수집되는 환경

Monte Carlo가 완성된 영화의 결말까지 본 뒤 평점을 고친다면, TD는 장면 하나를 볼 때마다 다음 장면에 대한 기존 예상과 비교해 평점을 조금씩 고친다.

TD Prediction에서 TD Control로

지금까지는 정해진 Policy $\pi$ 의 State value를 추정했다.

V(s) \approx v_\pi(s)

좋은 Policy를 찾으려면 Action value를 학습하고 Policy를 개선해야 한다.

State value의 TD Update에서 $V(S_t)$ 를 $Q(S_t,A_t)$ 로 바꾸면 다음 형태가 된다.

Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha \left[ \text{Target} - Q(S_t,A_t) \right]

다음 글의 핵심은 Target에 어떤 Q값을 넣는가다.

SARSA: 실제로 선택한 Next Action의 $Q(S_{t+1},A_{t+1})$
Q-Learning: 가능한 Next Action 중 가장 큰 $\max_{a'}Q(S_{t+1},a')$

Update의 겉모습은 같지만 빌려오는 미래가 다르다.

이번 글에서 기억할 것

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

TD는 한 Step의 실제 Reward와 Next State의 Value 추정을 합친 Target으로 매 Step 학습한다.

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

TD target은 $R_{t+1}+\gamma V(S_{t+1})$ 다.
추정값으로 다른 추정값을 고치는 것을 Bootstrapping이라고 한다.
TD error는 Target과 현재 예상의 차이다.
TD는 Episode 종료를 기다리지 않고 Online update가 가능하다.
MC보다 Bias가 생길 수 있지만 일반적으로 Variance가 낮다.
TD는 Sampling과 Bootstrapping을 모두 사용한다.

다음 글에서는 TD를 Control 문제로 확장한다. SARSA와 Q-Learning의 수식을 나란히 놓고, On-policy와 Off-policy라는 말이 실제로 어떤 Next Action의 값을 Target에 넣는지 살펴볼 예정이다.