강화학습 - (19) SARSA

강화학습

SARSA

SARSA란 일반화된 정책반복 (Generalized Policy Iteration)과 시간차 학습(TD)가 접목된 알고리즘이다.

 

일반화된 정책반복

일반화된 정책반복이란, 정책향상을 하기 위해서 굳이 정책 평가를 끝까지 해보지 않고

적정양의 정책 평가만으로도 정책 향상을 할 수 있다는 개념이었다.

이 과정은 시간차 학습과 만나 더 강력해질 수 있다.

단 한 스텝의 정책 평가 만으로도 정책 향상을 이룰 수 있다.

 

상태가치에서 행동가치로

각 스템의 정책 평가에서 정책 향상을 이루기 위해서는,

상태가치 $V(s)$가 아닌 행동가치 $Q(s,a)$를 사용해야 한다.

이는 위 그림에서 처럼 각 상태 $s$의 가치가 아닌,

각 상태와 행동의 페어 $(s,a)$를 평가해야 함을 의미한다.

 

SARSA 알고리즘

SARSA 알고리즘의 이름은 강화학습의 각 원소에서 따온 이름이다:

상태($S_t$), 행동($A_t$), 보상(R_{t+1}), 다음 상태($S_{t+1}$), 다음 행동($A_{t+1}$)

SARSA는 시간차 학습을 사용해 상태와 행동 페어 $(s, a)$를 예측한다.

 

위 그림에서와 같이 SARSA는 현재 상태 $S_t$에서 행동 $A_t$를 취한 뒤,

보상 $R_{t+1}$과 다음 상태 $S_{t+1}을 받는 것으로 그치지 않는다.

SARSA가 학습하기 위해서는 에이전트가 다음 행동 $A_{t+1}$로 무엇을 취할 것인지 알아야 한다.

다음 행동 $A_{t+1}$은 정책 $\pi$가 취하기 때문에,

$S_{t+1}$만 있다면 $A_{t+1}$가 무엇인지 알 수 있다.

SARSA는 위 행동을 선택하는 정책으로서 $\epsilon$-greedy를 사용한다.

 

에이전트가 행동가치 $Q(S_t, A_t)$를 갱신하기 위한 수식은 다음과 같다:

$Q(S_t, A_t) \leftarrow Q(S_t,A_t) + \alpha (R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)$

위 수식은 시간차 학습 $TD_0$알고리즘 수식과 많이 유사할 것이다.

$TD_0$는 상태가치를 갱신하였다면, SARSA는 행동가치를 갱신한다.

 

행동가치함수와 SARSA

먼저 행동가치 벨만방정식을 살펴보자.

$q_{\pi}(s,a) = \sum_{s',r} p(s',r|s,a) \left (r + \gamma \sum_{a'} \pi(a'|s') q_{\pi} (s',a')\right)$

 

위 수식을 SARSA 알고리즘에 대입하면,

위 수식의 $r$은 다음 상태에서의 작각적인 보상 $R_{t+1}$로, $q_{\pi}(s', a')$의 합은 $Q(S_{t+1},A_{t+1})-Q(S_t,A_t)$이 된다.

$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha (R_{t+1} + \gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t))$

이는 SARSA 알고리즘이 행동가치함수 $q$에 기반한 것을 알 수 있다.

사실 SARSA 알고리즘은 위 행동가치함수를 샘플 기반 기법으로 구현한 알고리즘인 것이다.

 

Expected SARSA

SARSA 알고리즘은 다음 상태에서 취할 하나의 행동만을 샘플링 한다.

그리고 다음 포스팅에서 나올 Q러닝은 최댓값만을 고려한다.

하지만 우리의 에이전트는 정책을 따라 행동하기 떄문에 다음에 취할 행동들의 확률이 얼마인지 미리 알 수 있다.

그렇다면 굳이 하나의 행동만을 샘플링을 할 필요가 있을까?

 

Expected SARSA는 이러한 점을 개선하여, 다음 상태의 모든 행동들을 고려한다.

다음 상태에 취할 수 있는 모든 행동을, 해당 행동을 취할 확률로 가중치를 주어 모두 더한다.

그리고 이를 SARSA의 갱신 수식에 활용한다.

$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha (R_{t+1} + \sum_{a'} \pi(a'|S_{t+1})Q(S_{t+1},a') - Q(S_t,A_t))$

 

SARSA는 다음 행동들 중 하나만 샘플링 했지만, Expected SARSA는 다음의 모든 행동들을 고려한다.

따라서 SARSA보다는 비용이 크고 느리게 갱신되지만, SARSA보다는 안정적인 정책 갱신이 가능한다.