목차
In previous posting
이전 posting에서 \(Q=Q^*\)라는 가정이 있다면 \(P(a_t \mid s_t)\)를 구하면 expected return을 최대화할 수 있다고 하였다. 이 posting에서는 \(Q=Q^*\)를 만족하기 위해 이를 구하는 방법에 대해서 얘기할 것이다.
Monte Carlo(MC)
우리는 \(Q^*\)를 구하기 위해서 training을 할 것이다.
Monte Carlo는 큰 수의 법칙이라 불린다.
\(E[X] = \int xp(x) \, dx \approx \frac {1}{N} \overset{N}{\underset{i=1}{\sum}} x_i\)
N이 \(\infty\)라면 동일하고 충분히 큰 수를 이용하면 평균값을 찾을 수 있다.
\(Q(s_t,a_t) \triangleq \int_{s_{t+1}:a_{\infty}}G_t P(s_{t+1}:a_{\infty} \mid s_t, a_t) \, ds_{t+1}:a_{\infty}\)
\(\approx \frac{1}{N} \overset{N}{\underset{i=1}{\sum}}G_i\)
*\(\epsilon\)-greedy를 통해 \(s_t\)지점에서 여러번 탐험을 통해 \(Q^*\)에 가깝도록 만든다.
Temporal Difference(TD)
\(Q(s_t,a_t) = \int_{s_{t+1},a_{t+1}} (R_t + \gamma Q(s_{t+1},a_{t+1})) P(s_{t+1} \mid s_t, a_t) P(a_{t+1} \mid s_{t+1}) \, ds_{t+1},a_{t+1}\)
Q는 next Q로 표현이 가능하고 이를 MC를 이용하면 아래와 같은 수식이 된다.
\(\approx \frac{1}{N} \overset{N}{\underset{i=1}{\sum}} (R^i_t+\gamma Q(s^i_{t+1}, a^i_{t+1})) = \bar{Q}_N\)
*Monte Carlo 와 다르게 1 step 이동 후 update
next Q로 표현된 Q를 MC를 이용한 결과를 \(\bar{Q}_N\)이라고 할 시 \(\bar{Q}_{N-1}\)로 표현이 가능하다.
\(\bar{Q}_N = \frac{1}{N} (\bar{Q}_{N-1} (N-1) + R^N_t + \gamma Q(s^N_{t+1},a^N_{t+1}))\)
\(= \bar{Q}_{N-1} + \frac{1}{N} (R^N_t + \gamma Q(s^N_{t+1},a^N_{t+1}) - \bar{Q}_{N-1})\)
우리는 위와 같은 식을 incremental Monte carlo update라고 부른다.
\(= (1-\alpha)\bar{Q}_{N-1} + \alpha (R^N_t + \gamma Q(s^N_{t+1}, a^N_{t+1}))\)
where \(\frac{1}{N}=\alpha\)
위 식은 state, action, reward, next_state, next_action으로 이루어져 있어 SARSA라고 부른다.
이 때 \(R^N_t + \gamma Q(s^N_{t+1}, a^N_{t+1})\)을 TD target이라 부른다.
Optimal policy는 maximize \(V(s_t)\) function
MC와 TD 비교
MC \(\frac{1}{N} \sum G^i_t\)
- unbiased
- 높은 variance(탐험 범위가 넓어 값이 많아 수렴하기 힘듬)
TD \(\frac{1}{N}\sum(R^i_t + \gamma Q(s^i_{t+1},a^i_{t+1}))\)
- biased
- Q에 expectaion이 있기 때문에 TD가 Q와 완전히 같지 않다.
- 해당 Q가 Optimal Q로 계속 변하여 완벽히 같기 힘듬.
- MC에 비해 낮은 variance