5.2 n-step Sarsa

n-step method를 predict하는 것 말고 Control은 어떻게 할까요?

n-step 방법을 지난 챕터에 배웠던 Sarsa에 적용하여 n-step sarsa를 만들어 보도록 하겠습니다.

n-step method를 Sarsa에 적용할 핵심 아이디어는 state-action value를 측정하고 $\epsilon-greedy$를 사용하는 것입니다.

n-step method와 같이 n-step sarsa는 아래의 back-diagram과 같이 생겼습니다.

n-step back-diagram와는 다르게 state-action pair을 update합니다.

n-step sarsa의 target을 식으로 정의하면,

$G_{t:t+n} \doteq R_{t+1}+ \gamma R_{t+2}+...\gamma^{n-1}R_{t+n} + \gamma^nQ_{t+n-1}(S_{t+n},A_{t+n})$ 입니다.

그리고 $t+n\geq T$ 이면 $G_{t:t+n} \doteq G_t$ 입니다.

그러므로 natural algorithm은 다음과 같이 정의할 수 있습니다.

$$Q_{t+n}(S_t,A_t)\doteq Q_{t+n-1}(S_t,A_t) + \alpha[G_{t:t+n}-Q_{t+n-1}(S_t,A_t)]$$

이런 알고리즘을 n-step Sarsa라고 부르고 pseudo code는 아래와 같다.

5.3 n-step Off-policy Learning by Importance Sampling

이번에는 n-step에 on-policy가 아닌 off-policy learning을 적용해보겠다.

off-policy는 policy $\pi$를 따라 학습하면서, 한편으로는 다른 policy $b$를 따르며 학습하는 방법이다.

보통 policy $\pi$ greedy policy이고 policy $b$는 epsilon greedy policy를 사용한다.

policy $b$에서 나온 data를 사용하기 위해서 두 policy의 차이를 계산에 넣어줘야 한다.

이 차이를 계산에 넣기 위해서는 action이 선택될 상대확률을 이용해야 한다.

n-step 에서는 n이 정해져 있기때문에 우리는 n-step으로 갈때까지의 action만 계산에 넣어주면 된다.

예를 들어 time $t$를 업데이트 할때는 $p_{t:t+n-1}$에 의해 weight 되어진다.

(여기서 ${t:t+n-1}$인 이유는 time $t$는 결국 time $t+n$일때 생성되어지기 때문이다. )

n-step에 off-policy learning을 적용한 식은 다음과 같이 정의한다.

$$V_{t+n}(S_t)\doteq V_{t+n-1}(S_t) +\alpha p_{t:t+n-1}[G_{t:t+n} - V_{t+n-1}(S_t)]$$

$p_{t:t+n-1}$을 importance sampling ratio라고 한다. $A_t$부터 $A_{t+n-1}$ 까지 두 policy에 의해 선택되는

n개의 action의 상대확률이다.

importance sampling ration의 정의는 다음과 같다.

$$p_{t:h}\doteq \prod_{k=t}^{min(h,T-1)} \frac{\pi(A_k \mid S_k)}{b(A_k \mid S_k)}$$

예를 들어보면,

policy $\pi$에 의해 한번도 선택되지 못했다면, $\pi(A_k \mid S_k)= 0$이되어 무시되어진다.

반면 action이 polciy $\pi$에 의해 선택되어질 확률이 policy $b$ 보다 훨씬 높을 경우에는 weight가 증가될 것이다.

이 의미는,

우리가 배우고자 하는 $pi$가 $b$에 의해 data가 드물게 생성되기, 이 일이 발생하였을때 over-weight하자 라는 개념이다.

만약 $\pi(A_k \mid S_k)$과 $b(A_k \mid S_k)$의 비율이 같다면 importance sampling ratio는 항상 1이다.

그러므로 off-policy form인 n-step Sarsa update식으로 바꿀수 있다.

$$Q_{t+n}(S_t,A_t)\doteq Q_{t+n-1}(S_t,A_t) +\alpha p_{t+1:t+n-1}[G_{t:t+n} - Q_{t+n-1}(S_t,A_t)]$$

여기서 importance sampling이 다음 스텝에서 시작하는 이유는 이것이 state-action pair의 업데이트식이기 때문이다.

q*를 측정하기 위한 Off-policy n-step Sarsa의 pseudo code는 다음과 같다.

Reference

• Reinforcement Learning: An Introduction Richard S. Sutton and Andrew G. Barto Second Edition, in progress MIT Press, Cambridge, MA, 2017