[강화학습8]SARSA

 

 

저번 포스팅에서는 model-free환경에서 정책$\pi$에 대해 가치추정을 할 수 있는 방법인 MC와 TD에 대해서 알아보았다.

이제 우리의 목표는 저 두 방법을 활용해 최적정책$\pi^*$를 찾는 것이다.

MC를 활용한 정책반복

예전포스팅에서 다룬 정책 반복은, 정책 평가와 정책 개선을 반복적으로 수행하며 최적정책을 찾는 방법이다.

MC는 정책평가단계의 기존 방법을 대체할 수 있다. 다만 정책개선 단계 쪽에 작은 문제가 있다. 새로운 정책$\pi'$는 각 상태 $s$에서 $q_{\pi}(s, a)$를 최대화하는 행동 $a$를 선택하는데. 수식으로 표현하면 다음과 같다.

$$\pi'(s) = \underset {a}{\text {argmax}} \, \, q_{\pi}(s, a), \forall s \in S$$

정책반복에서 $q_{\pi}(s, a)$는 벨만 기대방정식을 통해 구할 수 있다

$$q_\pi(s, a) = R(s, a) + \gamma \sum_{s'} P(s' \mid a, s)  v_\pi(s')$$

그러나 우리는 model-free환경에서 우리는 상태전이확률$P(s' \mid a, s)$을 알지 못하기 때문에 $v_\pi(s)$만으로는 $q_\pi(s, a)$를 알 수 없다. 따라서$v_\pi(s)$ 대신 $q_\pi(s, a)$를 직접 학습한다.

가치함수 $q_\pi(s_t, a_t)$는 다음과 같이 정의할 수 있고

$$q_\pi(s_t, a_t) = \mathbb {E}_\pi [G_t]$$

이에 기반한 업데이트식은 다음과 같다

$$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha(G_t - Q(s_t, a_t))$$

탐험

어떤 미식가가 있다 그는 자신이 이미 여러 번 방문한 인증된 맛집에서 주로 식사를 해결하지만 때때로 새로운 맛집을 찾아 새로운 식당에 가고는 한다. 최고의 맛을 찾기 위해서이다. 최고의 정책을 찾는 우리는, 현재 정책개선과정에서 가장 높은 $q(s, a)$ 값을 가지는 행동을 고른다. 이것을 활용(Exploitation)이라고 한다. 그러나 활용만을 반복하다 보면 여러 상태를 충분히 탐색할 수 없을지도 모른다. 그리고 만약 한 번도 가지 못한 상태가 정말 좋은 상태라면 어떨까? 따라서 우리는 행동을 항상 greedy 하게 선택하여서는 안되며, 에이전트의 탐험을 보장해 주어 때때로 가치가 높지 않은 행동들을 선택할 수 있게 해주어야 한다. 이것을 $\epsilon - greedy$전략이라고 하며 $\epsilon$의 확률로 무작위 행동을 한다. 동시에 $1-\epsilon$의 확률로 $q(s, a)$값이 가장 높은 행동을 취한다. 이때 학습초기에는 높은 $\epsilon$값을 설정하고 점차 줄여가는 방식이 효과적이기 때문에 자주 이용된다. 이 전략은 수학적으로 엄밀하게 증명된 것은 아니지만, 많은 실제 적용 사례와 경험적 관찰을 통해 유용성이 인정되었다.

SARSA

이번엔 정책반복에 MC 대신 TD를 이용해 보자. 역시 $v_\pi(s)$대신 $q_\pi(s, a)$를 사용한다 다만, 이 접근법을 가리키는 특별한 이름이 있다. 

에이전트의 경험 시퀀스인 $(S, A, R, S', A')$가 $Q$함수 업데이트에 사용된다. 그래서 알고리즘이름이 SARSA이다.

가치함수 $q_\pi(s_t, a_t)$는 다음과 같이 정의할 수 있고

$$q_\pi(s_t, a_t) = \mathbb {E}_\pi [r_{t+1} + \gamma q_\pi(s_{t+1}, a_{t+1})]$$

이에 기반한 업데이트식은 다음과 같다

$$Q(S, A ) \leftarrow Q(S, A) + \alpha(R + \gamma Q(S', A') - Q(S, A))$$

SARSA는 각 스텝마다 정책평가와 정책개선을 반복한다.