Incremental Implementation

$Q_{n}$ 는 action $a$ 를 $n - 1$ 번 선택한 이후의 action-value function 의 추정값을 의미한다.

Q_{n} ≐ \frac{R _{1} + R _{2} + \dots + R _{n - 1}}{n - 1}

이 계산 방법을 실제로 구현하려면, 모든 보상값들을 전부 저장해야 하므로, 많은 메모리가 요구된다.

이러한 현상을 완화하기 위해 다음과 같은 수식이 유도된다.

Q_{n + 1} = \frac{1}{n} i = 1 \sum n R_{i} = \frac{1}{n} (R_{n} + i = 1 \sum n - 1 R_{i}) = \frac{1}{n} (R_{n} + (n - 1) \frac{1}{n - 1} i = 1 \sum n - 1 R_{i}) = \frac{1}{n} (R_{n} + (n - 1) Q_{n}) = \frac{1}{n} (R_{n} + n Q_{n} - Q_{n}) = Q_{n} + \frac{1}{n} [R_{n} - Q_{n}]

$Q_{n} + \frac{1}{n} [R_{n} - Q_{n}]$ 는 다음과 같이 생각할 수 있다.

NewEstimate \leftarrow OldEstimate + StepSize [Target - OldEstimate]

편의를 위해 $Q_{0} ≜ 0$ 로 정의한다.

Zzong's Notes