실제 리턴 전체를 기다리지 않고, 다음 상태에서 얻을 예상 값만 보고 미리 업데이트하는 방식이다.
Monte Carlo는 에피소드 끝까지 기다리는 반면 TD는 한 스텝만 보고 즉시 업데이트한다.
TD는 테이블 방식(tabular)으로 값을 갱신하고, 모델 없이(model-free) 학습하는 방법이다. MC 와 마찬가지로 Q-table 에 (s,a) 를 저장하고, 최적값을 계산할 수 없다는 특징을 가진다.
TD 는 one-step transition 기반의 GPI 를 채택한다. Policy Evaluation 에서 Value Function 을 추정하고, Policy Improvement 에서 ε-greedy 등으로 정책을 개선하는 과정을 반복한다. MC 와 다른 점은 한 스텝만 보고도 가치 함수를 갱신할 수 있는 one-step transition 이라는 점이다.
TD는 DP 와 MC 의 장점들을 쏙쏙 뽑아온다.
Bootstraping of DP
DP처럼 한 번에 전체 에피소드를 보지 않아도 값을 업데이트할 수 있다. 미래의 예측값을 현재 값을 이용해 표현할 수 있기 때문에 final outcome 을 기다리지 않아도 된다. 이는 온라인 학습 등에 적합하다.
Sampling of MC
MC처럼 직접 환경에서 샘플을 얻어 학습 가능하기 때문에 model-free 상황에서도 사용 가능하다.
TD 학습의 대표적인 두 가지 방식이다. 두 방식은 On-policy vs Off-policy 차이가 핵심이다.
On-policy 는 자기 자신이 따르고 있는 정책의 결과를 학습하고, Off-policy 는 실행한 정책과는 무관하게 최적의 행동을 가정한다.
앞서 배웠던 MC 와 비교해보며 두 방식을 알아보자.
MC : On-Policy MC Prediction
$$ Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha[G_t-Q(S_t,A_t)] $$
MC 에서 $G_t$ 는 에피소드를 끝까지 보고 계산한 Return 이다. 전체 보상을 보고 Q값을 수정하기 때문에 에피소드가 끝나야 업데이트 가능하다.
SARSA : On-Policy TD Prediction
$$ Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha[R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)] $$
주어진 정책 $\pi$ 를 따라 다음 행동인 $A_{t+1}$ 까지 사용한다. MC 와의 차이는 실제 Reward 를 사용하냐, 아니면 one-step 으로 추정된 Reward 를 사용하냐의 차이다.
Q값을 갱신할 때 에이전트가 실제로 선택한 경로만 반영하기 때문에, 에이전트가 지금 실제로 탐험하고 있는 정책을 기준으로 학습한다.
Q-Learning : Off-Policy TD Prediction
$$ Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha[R_{t+1}+\gamma \max_a Q(S_{t+1},a)-Q(S_t,A_t)] $$
다음 상태에서의 가장 Q가 큰 행동을 사용한다. Q-learning은 현실에서 ε-greedy로 행동하더라도, 학습은 항상 가장 좋은 행동을 가정해서 진행한다. SARSA 처럼 sampling 을 이용하지만, 어떤 action 을 취하는지에서 차이가 발생한다.
Sarsa learns $Q^{\pi}$ (on-policy) by using Bellman expectation equation. Q-learning directly learns $Q^{*}$ (off-policy) by using Bellman optimal equation.