4. Monte Carlo Methods and Temporal Difference Learning in Policy Evaluation
RECALL
* Policy Evaluation
MDP와 policy $\pi$가 주어졌을 경우, Bellman equation을 이용해 Policy Evaluation을 할 수 있다.
* DP for Policy Evaluation
State-value function을 0으로 초기화하고, 수렴할때까지 state-value function을 업데이트했다.
$\gamma<1$ and $T^{\pi}_{ss'}<1$ 이면 수렴한다.
MDP처럼 모델이 주어졌다면, 위 방식을 따라 policy를 평가할 수 있지만, 일반적인 경우에 Transition model T나 Reward model R이 주어지지 않는 경우가 많다. 이럴 때는 Model-free policy evaluation 방법을 사용한다. MC와 TD가 있다.
1. Monte Carlo Policy Evaluation
(1) Generate and log episodes under $\pi$
$i^{th}$ episode: $s_{i, 1}, a_{i, 1}, r_{i, 1}, \cdots, s_{i, Terminate}$
(2) Calculate $G_{t}$ for each episode
(3) MC policy evaluation estimates $V^{\pi}(s)=E_{\pi}[G_{t}|s_{t}=s]$ by iterations using
- Empirical average : sampled episode란 state s를 방문하는 episode다. Episode가 많을수록 estimate of $V^{\pi}$를 업데이트 한다.
- Importance sampling : reweighted empirical average
Transition dynamics나 Reward가 필요 없다.
Bootstrapping도 아니다.
Markov 상태도 필요없다.
다만, 생성된 episode는 terminate되야 한다.
완성된 episode에 대한 $G_{t}$를 구해야하기 때문이다.
이는 online learning이 불가능함을 뜻한다.
2. First-Visit MC on policy evaluation
(1) 모든 state에 대해, $N(s)=0, G(s)=0$
(2) Loop
1) Generate episode
2) t에 $i^{th}$ episode에 대한 return, $G_{t}$을 구한다.
3) 어떤 $i^{th}$ episode에서 state s에 First(처음) 방문할때마다,
- 첫 방문 횟수 : $N(s)+=1$
- return : $G(s)+=G_{i, t}$
- update estimate : $V^{\pi}(s) = G(s)/N(s)$
3. Every-Visit MC on policy evaluation
(1) 모든 state에 대해, $N(s)=0, G(s)=0$
(2) Loop
1) Generate episode
2) t에 $i^{th}$ episode에 대한 return, $G_{t}$을 구한다.
3) 어떤 $i^{th}$ episode에서 state s에 Every(매번) 방문할때마다,
- s 방문 횟수 : $N(s)+=1$
- return : $G(s)+=G_{i, t}$
- update estimate : $V^{\pi}(s) = G(s)/N(s)$
4. Incremental MC on policy evaluation
(1) 모든 state에 대해, $N(s)=0, G(s)=0$
(2) Loop
1) Generate episode
2) t에 $i^{th}$ episode에 대한 return, $G_{t}$을 구한다.
3) 어떤 $i^{th}$ episode에서 state s에 Every(First) 방문할때마다,
- Every(First) s 방문 횟수 : $N(s)+=1$
- return : $G(s)+=G_{i, t}$
- update estimate :
$V^{\pi}(s) = [V^{\pi}(s)(N(s)-1)+G_{i,t}]/N(s)$
$V^{\pi}(s) = V^{\pi}(s)+[G_{i,t}-V^{\pi}(s)]/N(s)$
$\alpha$는 learning rate라고 한다. $1/N(s)$보다 크면 새롭게 들어오는 data에 더 weigh를 주게 된다. 이는 non-stationary domain에 효과적이다.
| First-visit MC | Every-visit MC |
| unbiased estimator 모집단의 통계값을 정확하게 측정할 수 있다. $N(s)->inf$, $V^{\pi}(s)->E_{\pi}[G_{t}|s_{t}=s]$ |
biased estimator 모집단의 통계값을 정확하게 측정할 수 없다. sampling에 따라 결정된다. |
일반적으로 높은 variance를 가지는 estimator다.
5. Limitation of MC policy evaluation
episode가 terminate해야만 사용이 가능다. 이에 따라 online learning이 불가능한데, 이를 해결하기 위해 조건을 추가하고 만든 것이 Temporal Difference(TD)이다.
6. TD learning for Estimating Value function
MDP model을 안다면, Bellman equation을 이용한다.
MDP model을 모른다면, incremental every-visit MC를 변형해서 사용한다.
7. TD(0) learning
$i^{th}$ episode: $s_{i, 1}, a_{i, 1}, r_{i, 1}, \cdots, s_{i, Terminate}$에 대해서, (s, a, r, s')의 쌍을 반복해서 이용한다.
TD(0)는 online learning이 가능하다. (s, a, r, s')만 있으면 되기 때문에, episode가 terminate하는 것을 기다릴 필요가 없다.
$G_{t}$의 estimator로 $r_{t}+\gamma V^{\pi}(s_{t+1})$를 사용했기 때문에, Bootstrapping 했다.
8. MC vs TD
| MC | TD |
| offline learning terminated episode episodic env. High variance, unbiased initial value에 둔함 수렴 잘함 Simple Markov env. |
online learning incomplete sequences non-episodic env. Low variacne, biased initial value에 민감함 $V_{\pi}(s)$로 수렴함(항상 그렇지는 않음) MC보다 효과적임 non-Markov env. |
9. TD($\lambda$)
$G_{t}$를 n step에 대해 구하고, 이를 learning rate와 함께, TD target으로 사용하는 것을 TD($\lambda$)이라고 한다.
모든 $G_{t}^{(i)}$를 합치면 다음과 같다.
만약 $\lambda$=0이면, TD(0)이 된다.
TD($\lambda$)의 error는 다음과 같다. 전개해서 풀면 된다.
만약 $\lambda$=1이면, Every-visit MC와 비슷해진다.
10. Epsilon-Soft Random Action
policy가 deterministic인 경우 stochastic으로 바꿔서, data 양을 늘리는 방법이다. 많은 양의 data가 필요한 MC에 효과적이다.
$\epsilon$은 random action을 수행하는 경우라고 생각하면 된다. 자연스럽게 1-$\epsilon$은 action a를 수행하는 경우이다.
'Study > Reinforcement Learning' 카테고리의 다른 글
| [project] QMIX review (0) | 2023.05.01 |
|---|---|
| 3. Policy Improvement by Iterative Method (0) | 2023.05.01 |
| 2. Bellman equation and MDP (0) | 2023.05.01 |
| 1.Introduction (0) | 2023.05.01 |