[RL] Lec.4 Model-Free Prediction 강의 정리

큰 그림을 이야기하면

Lec.3 : Planning by Dynamic Programming 은 알고 있는 MDP를 푸는 것

Lec.4 : Model-free Prediction 은 모르는 MDP의 가치 함수를 추정하는 것

Lec.5 : Model-free Control은 모르는 MDP의 가치 함수를 최적화 하는 것이다.

 

Model-free Prediction은 크게 Monte-Carlo RL과 Temporal Difference Learning(시간차 학습) 있는가보다.

---

Monte-Carlo Reinforcement Learning

 MC의 특징은 경험이 끝나야 학습을 할 수 있다는 점, model-free라서 MDP의 전이와 보상에 대해 모른다는 것이다. 그리고 가치 평가에 평균(mean)을 사용한다는 점이다.

목표 : MC의 정책 평가(Policy Evaluation)은 policy $\pi$에서의 경험의 단편에서 가치 함수 $v_\pi$를 학습시키는 것이다.

출력(return)은 총 할인된 보상이다.

$G_t = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma ^{T-1} R_T$

가치 함수는 예상되는 출력(Expected return)이다.

$v_\pi (s) = \mathbb{E} _\pi [G_t | S_t = s]$

MC 정책 평가는 예상되는 출력 대신 경험적 평균 출력(Empirical mean return)을 사용한다.

 

First-Visit/Every-Visit Monte-Carlo Policy Evaluation

상태 $s$를 평가하고자,

하나의 단편 중에 상태 $s$를 방문하는 첫 시간 스텝 $t$/매 시간 스텝 $t$에서

카운터를 증가시키고 $N(s) \leftarrow N(s) + 1$

총 출력을 증가시킨다 $S(s) \leftarrow S(s) + G_t$

가치는 평균 출력으로 추정된다. $V(s) = S(s)/N(s)$

그러면 카운터가 무한대로 가면 가치 함수는 정책을 따르는 가치 함수에 가까워진다.

$N(s) \rightarrow \infty$ as $V(s) \rightarrow v_\pi (s)$

Incremental Monte-Carlo

점진적 MC를 소개하기 전에, 점진적 평균(Incremental Mean)을 알고 가자.

순서 $x_1 , x_2, \cdots$의 평균 $\mu_1 ,\mu_2 \cdots$는 점진적으로 계산될 수 있다.

표현이 어려운데, 상태가 추가되면 추가되는대로 전의 평균 $\mu_{k-1}$을 가지고 현재의 평균 $\mu_k$을 구하는 방법을 나타낸 것이다.

$\mu _k =\frac{1}{k} \sum_{j=1}^k x_j =\frac{1}{k} \left( x_k + \sum_{j=1} ^{k-1} x_j \right)=\frac{1}{k} \left( x_k + (k-1) \mu_{k-1} \right)$

$\therefore ) \boldsymbol{\mu_k} = \mu_{k-1} + \frac{1}{k} \left( x_k - \boldsymbol{\mu_{k-1}} \right)$

비슷한 맥락으로 Incremental Monte-Carlo Update를 해보면

매 단편 $S_1 , A_1, R_2, \cdots , S_T$ 이후에 $V(s)$를 점진적으로 갱신해준다.

그러면 출력이 $G_t$인 각각의 상태 $S_t$에 대해

$N(S_t) \leftarrow N(S_t) +1$

$V(S_t) \leftarrow V(S_t) + \frac{1}{N(S_t)} \left(G_t - V(S_t) \right)$

비정상적인(Non-stationary) 문제의 경우, 움직이는 평균을 따라가는게 효과적일 수 있다.

$V(S_t) \leftarrow V(S_t) +\alpha (G_t - V(S_t))$

---

Temporal-Difference Learning (시간차 학습)

 시간 차 학습은 경험이 완전히 끝나지 않아도 학습하며, MC와 동일하게 model-free하다. 또한 추측하는 쪽으로 추측을 갱신한다.

목표 : policy $\pi$에서의 경험에서 실시간으로 가치 함수 $v_\pi$를 학습시키는 것이다.

Incremental every-visit Monte-Carlo는 요약하면, 실제 출력 $G_t$를 통해 가치 $V(S_t)$를 갱신한다.

$V(S_t) \leftarrow V(S_t) + \alpha ($ $G_t$ $- V(S_t))$

Simplest temporal-diffrence learning algorithm TD(0)은 추정된 출력 $R_{t+1}+\gamma V(S_{t+1})$으로 $V(S_t)$를 갱신한다.

$V_(S_t) \leftarrow V(S_t) +\alpha ($ $R_{t+1} +\gamma V(S_{t+1}) $ $-V(S_t) )=V(S_t)+\alpha \delta_t$ 

$R_{t+1} +\gamma V(S_{t+1}) $은 TD 표적(target)이라 한다.

$\delta_t = R_{t+1} +\gamma V(S_{t+1}) -V(S_t) $는 TD 오차(error)이라 한다.

 

Bias/Variance Trade-Off

출력 $G_t$는 $v_\pi (S_t)$의 비편향(Unbiased) 추정이다.

True TD 표적 $R_{t+1}+\gamma v_\pi (S_{t+1})$은 $v_\pi (S_t)$의 비편향 추정이다.

TD 표적은 $R_{t+1}+\gamma V (S_{t+1})$는 $v_\pi (S_t)$의 편향된(Biased) 추정이다.

TD 표적은 출력보다 작은 분산을 가진다. 왜냐하면 출력은 여러 행동, 전이, 보상에 영향을 받지만 TD 표적은 하나의 행동, 전이, 보상에 영향을 받는다.

Return     : $(G_t = R_{t+1}+\gamma R_{t+2} +\cdots + \gamma ^{T-1} R_T)$

TD Target : $R_{t+1} +\gamma V(S_{t+1}) $