https://youtu.be/vfLrBPYwuFA?si=Gs3LH3C7i-NgzAGa
TD (Temporal difference) 방법이란?
MC (Monte Carlo) 방법은 전체 에피소드가 끝난 후에 최종 보상을 바탕으로 학습을 진행한다. 이와 달리 TD (Temporal difference) 방법은 에피소드가 끝날 때까지 기다리지 않고, 상태의 값을 점진적으로 업데이트한다.
MC 방법은 다음 식과 같이 나타낼 수 있다.
$$ Q(S_{t}, a_{t}) \approx \frac{1}{N}\sum_{i=1}^N(R_{t+1}^{(i)}+ \gamma Q(S_{t+1}^{(i)}, a_{t+1}^{(i)})) = \overline{Q}_{N} $$
위의 식을 아래와 같이 정리 할 수 있는데, 이것이 TD 방법을 나타낸 식이다. (정확히는 1-step TD를 나타낸 식)
$$ = \frac{1}{N}(\overline{Q}_{N-1}(N-1) + R_{t+1}^{(N)}+ \gamma Q(S_{t+1}^{(N)}, a_{t+1}^{(N)})) $$
$$ = \overline{Q}_{N-1} +\frac{1}{N}( R_{t+1}^{(N)}+ \gamma Q(S_{t+1}^{(N)}, a_{t+1}^{(N)}) - \overline{Q}_{N-1}) $$
이와 같이 MC를 전개하면 TD 식이 나온다. 따라서 MC와 TD는 식에서는 다른 점이 없으며, 두 방법에서의 차이는 업데이트가 되는 시점이다.
Incremental Monte Carlo updates
다음 식이 Incremental Monte Carlo updates이다.
$$ \overline{Q}_{N}= \overline{Q}_{N-1} +\frac{1}{N}( R_{t+1}^{(N)}+ \gamma Q(S_{t+1}^{(N)}, a_{t+1}^{(N)}) - \overline{Q}_{N-1}) $$
위의 식에서 $\frac{1}{N}$을 $\alpha$로 놓는다면, 다음과 같이 나타낼 수 있다.
$$ =(1-\alpha) \overline{Q}_{N-1} +\alpha( R_{t+1}^{(N)}+ \gamma Q(S_{t+1}^{(N)}, a_{t+1}^{(N)})) $$
식을 보면, N개의 sample의 평균을 구할 때 N-1개의 sample의 평균 값과 N번째 sample의 값을 이용한다. 즉 incremental하게 값을 구해나갈 수 있음을 보여준다.
여기서 TD target 과 TD error라는 용어를 짚고 넘어가자. TD target은 예상되는 목표 값이고 TD error는 현재 상태 값과 target 간의 차이이다. 따라서 위의 식에서 $R_{t}^{(N)}+ \gamma Q(S_{t+1}^{(N)}, a_{t+1}^{(N)})$는 TD target이 되고, $R_{t}^{(N)}+ \gamma Q(S_{t+1}^{(N)}, a_{t+1}^{(N)}) - \overline{Q}_{N-1}$는 TD error가 된다.
SARSA
SARSA는 현재 상태와 행동 $(S_{t}, A_{t})$에서 시작해, 다음 상태와 행동 $(S_{t+1}, A_{t+1})$까지의 관계를 바탕으로 Q값을 업데이트한다. (중간에, 현재 행동에 따른 보상 $R_{t+1}$을 얻음)
$$ \overline{Q}_{N}=(1-\alpha) \overline{Q}_{N-1} +\alpha( R_{t+1}^{(N)}+ \gamma Q(S_{t+1}^{(N)}, a_{t+1}^{(N)})) $$
이 식을 보면, $\overline{Q}_{N-1}$ 가 현재 state ($S_{t}$), 현재 action ($A_{t}$)에 대한 정보를 담고 있고, $R_{t+1}^{(N)}$ 가 현재 행동에 따른 보상 ($R_{t+1}$)이며, $Q(S_{t+1}^{(N)}, a_{t+1}^{(N)})$가 다음 state ($S_{t+1}$)와 다음 action ($A_{t+1}$)에 대한 정보를 담고 있다.
결론
- TD(Temporal Difference) 방법은 MC(Monte Carlo) 방법과 달리, 에피소드가 끝날 때까지 기다리지 않고, 상태 값을 점진적으로 업데이트한다.
- 두 방법의 차이는 업데이트 시점에 있으며, TD는 더 실시간적인 학습을 지원한다.
- TD 방법의 핵심은 TD target과 TD error를 통해 값을 지속적으로 보정하는 데 있다.
- SARSA는 TD 학습의 대표적 알고리즘으로, 현재 상태와 행동, 다음 상태와 행동 간의 관계를 바탕으로 Q 값을 업데이트한다.