시간차 학습

시간차 학습(Temporal difference learning)은 예측 기반 기계 학습의 한 방법이다. 시간차 학습은 주로 강화 학습 문제에 사용되며, "몬테카를로 방법과 동적 계획법의 조합"이라고 불리기도 한다. 이는 시간차 학습이 어떤 정책에 따라 환경을 표집하여 학습을 진행하는 몬테 카를로 방법의 특징과, 과거에 학습한 추정치를 사용하여 현재의 추정치를 구하는 동적 계획법의 특징을 지니고 있기 때문이다. 시간차 학습 알고리즘은 동물들의 시간차 학습 모델과도 관련이 있다.

시간차 학습은 이어지는 예측들이 어떤 식으로 관련되어 있다고 생각한다. 일반적인 예측 기반 지도 학습에서는 오직 실제로 관측된 값을 통해서만 학습이 이루어진다. 즉, 예측을 하고, 결과가 관측되면, 비로소 관측된 결과에 더 잘 부합하도록 예측 메커니즘이 수정된다. 리처드 서튼이 잘 설명하듯, 시간차 학습의 핵심 아이디어는 예측이 관측된 결과 뿐만이 아니라 미래에 대한 다른 예측에 잘 부합하도록 수정된다는 것이다. 이러한 과정은 부트스트랩이라고 불린다. 다음의 예시를 보자.

"당신이 토요일의 날씨를 예측하고 싶어한다고 해 보자. 그리고 당신은 주간 날씨 정보가 주어졌을 때 토요일의 날씨를 예측할 수 있는 어떤 모델을 가지고 있다고 하자. 일반적인 알고리즘의 경우에, 당신은 토요일까지 기다렸다가 당신의 모델을 한꺼번에 수정할 것이다. 그러나, 가령 금요일이 되었을 때, 당신은 이미 토요일의 날씨가 어떨지 대강 예측할 수 있을 것이다. 따라서 토요일이 되기 전에 월요일의 모델을 수정할 수 있게 될 것이다."

수학적으로 말하면, 일반적인 알고리즘과 시간차 학습 알고리즘은 모두 어떤 확률 변수 $z$의 기댓값 $\mathrm {E} (z)$에 대한 예측의 오차와 관련된 어떤 비용 함수(cost function)를 최적화하려 할 것이다. 그러나, 일반적인 알고리즘은 $\mathrm {E} (z)=z$ ($z$는 관측치)라고 가정하는 반면, 시간차 학습은 어떤 모델을 사용한다. 특별히 시간차 학습이 주요하게 사용되는 강화 학습의 경우에는, 총 보상을 나타내는 $z$에 대하여, $\mathrm {E} (z)$는 보상에 대한 벨만 방정식으로 주어진다.

수식

$r_{t}$를 시간 $t$에 얻는 보상이라고 하자. ${\bar {V_{t}}}$를 미래에 주어질 모든 보상의 감가합(減價合, discounted sum)과 같은 올바른 예측이라고 하자. 감가는 감가인자 $\gamma$의 승수를 곱함으로써 이루어지며, 이를 통해 나중에 얻어지는 보상은 현재의 보상에 비해 덜 중요해진다.

${\bar {V_{t}}}=\sum _{i=0}^{\infty }\gamma ^{i}r_{t+i}$

이 때, $0\leq \gamma <1$이다. 첨자 $i$를 1부터 시작하도록 식을 변형하면,

${\bar {V_{t}}}=r_{t}+\sum _{i=1}^{\infty }\gamma ^{i}r_{t+i}$

을 얻는다. 재차 변형하면,

${\bar {V_{t}}}=r_{t}+\sum _{i=0}^{\infty }\gamma ^{i+1}r_{t+i+1}=r_{t}+\gamma \sum _{i=0}^{\infty }\gamma ^{i}r_{t+i+1}=r_{t}+\gamma {\bar {V}}_{t+1}$

을 얻는다. 따라서, 보상 $r_{t}$는 올바른 다음 예측과 현재의 예측의 차이이다.

$r_{t}={\bar {V_{t}}}-\gamma {\bar {V}}_{t+1}$