Temporal Difference: Intro

Human Being·2022년 8월 17일

Reinforcement Learning

목록 보기

10/22

Monte Carlo와 Dynamic programming의 결합

model-free

예측 문제 즉, 주어진 policy ${\pi}$ 에 대해 value function $v_{\pi}$ 를 추정

제어 문제 즉, 최적 정책을 찾기 위해 DP, MC, TD 방법이 모두 GPI를 일부 변형한 형태로 사용한다.

Prediction: MC & TD

여기서 prediction은
policy $\pi$ 하에서 경험한 $v_{\pi}$ 를 학습한다고 하자

( $\alpha$ 는 작은 step의 크기/간격을 의미한다)

Monte-Carlo
- (Incremental every-visit), (stationary $\alpha$ MC)
- 갱신한 value $v_n(S_t)$ 는 표본집단의 반환값인 $G_t$ 를 향한다
- $v_{n+1}(S_t) = v_n(S_t) + \alpha (\overbrace{G_t}^{target} - v_n(S_t))$
Temporal Difference
- (TD(0))
- 갱신한 value $v_n(S_t)$ 는 표본집단의 반환값인 $R_{t+1} +\gamma v_t(S_{t+1})$ 를 향한다
- $v_{n+1}(S_t) = v_n(S_t) + \alpha \underbrace{(\overbrace{R_{t+1} +\gamma v_t(S_{t+1})}^{target} - v_n(S_t))}_{TD\ error\ =\ \delta_t }$

MC의 단점을 보완한 TD

$G_t = R_{t+1} + \gamma R_{t+1}+\gamma ^2R_{t+1}+ ...$
이 계산을 하려면
이전의 모든 보상값들을 다 알아야 한다

그래서 Monte Carlo의 단점은
한 에피소드가 끝날 때까지 기다려야 한다는 점이다

이를 개선하기 위해
Temporal Difference는
$G_t$ 대신 $R_{t+1} +\gamma v_t(S_{t+1})$ 를 사용한다

여기서는 reward를 $R_{t+1}$ 하나만 얻고
그간 누적된 값을 $v_t$ 에서 가져오기에
끝까지 기다리지 않아도 된다

Backup Diagram

DP, MC, TD의 backup diagram을 이해하기 위해
backup diagram을 설명해보자면,

backup (보강)이란
next_state (or state_action_pairs)의 value를
현재 state (or state_action_pairs)에게
전이/대입하는 것이다

Backup Diagram 구성

backup diagram의 요소는 다음과 같다
사진 속 max action value는 optimal action을 의미한다
state transition은 state transition probability $P^a_{ss'}$ 를 의미한다

여기에는 없지만 만약 말단 node가
원이 아닌 직사각형이라면
terminal state를 의미한다.

backup diagram 예시.
색상이 모두 검정색이어야 하는데 이해를 돕기 위해 다르게 색칠됐다
1. (큰 흰색 원) - 각 state는
2. (초록 화살표) - policy $\pi(a|s)$ 가 구한 각 action의 확률값을 기반으로 action을 선택한다
3. (작은 검정색 원) - 그 action을 행하고
4. (파란 화살표) - 이로 인해 다음 state로 넘어갈 확률에 따라
5. (큰 빨간색 원) - 결정된 state로 진행한다