SARSA 알고리즘

고영민·2023년 8월 16일

강화학습

목록 보기

3/4

SARSA 알고리즘은 앞에서 학습한 REINFORCE 알고리즘(정책경사 사용))과는 달리 가치 함수를 학습하는 알고리즘이다. SARSA 알고리즘에서는 $Q^\pi(s,a)$ 를 학습하며, 심층신경망을 사용할 경우에는 신경망이 이를 근사하게 된다. 가치함수 중에서도 상태 가치 함수가 아닌 상태-행동 가치 함수를 근사하는 이유는 추후에 가치 함수에서 정책을 추출할 때 더 용이하기 때문이다. 만약 $V(s)$ 를 근사하게 되면, 가능한 모든 행동 $a$ 에 대해서 이후에 나올 상태 $s'$ 을 추론하고, 이에 대해서 $V(s')$ 을 모두 계산하여 최대값을 찾아야 하는데, 이러한 과정이 상태-행동 가치함수를 사용할 경우 매우 간소화된다. 하지만 상태-행동 쌍에 대해서 학습을 진행하기 때문에 상태 데이터에 대해서만 학습을 진행하는 $V(s)$ 보다 데이터가 더 많이 필요하고 학습이 어렵다는 단점이 있다.

SARSA 등의 가치 기반 알고리즘에서는 시간차 학습(Temporal Difference, TD)를 이용하여 학습을 진행하는 경우가 많다. 시간차 학습은 앞서 나왔던 몬테칼로 방법을 대체하며, 다음과 같은 벨만 방정식을 사용한다.

Q^\pi (s,a) = E_{s'\sim p(s'|s,a), r\sim R(s,a,s')}[r+\gamma E_{a'\sim \pi (s')}[Q^\pi (s',a')]]

몬테칼로 방법에서는 가치함수를 할인된 이득의 합으로 정의하여 에피소드에 대한 궤적을 저장하고, 이를 이용하여 신경망 업데이트 등의 학습을 진행한다. 하지만 이 경우에는 에피소드가 종료되어야만 업데이트가 1번 발생하기 때문에 에피소드가 너무 길거나, 종료 조건이 없는 경우에는 사용되기 어렵다. 시간차 학습에서는 모든 상태-행동 쌍이 학습을 위한 데이터로 사용될 수 있어 업데이트를 위해 에피소드 종료를 기다리지 않아도 된다.

시간차 학습에서는 $Q$ 함수를 나타내는 신경망(또는 근사함수) $Q_\theta$ 가 있을 경우 위 식의 우변을 신경망으로 추정하여 타겟 $Q$ 함수 $Q^{\pi}_{tar}(s_t,a_t)$ 를 계산한다. 이때 첫번째 기대값은 다음 상태와 보상에 대한 기대값으로 실제 관측된 데이터 $(s,a,r,s')$ 만을 고려함으로써 다음과 같이 첫번째 기대값을 제거할 수 있다.

Q^{\pi}_{tar}(s_t,a_t) = r+\gamma E_{a'\sim \pi (s')}[Q^{\pi}_\theta (s',a')]

두번째 기대값을 제거하는 방법은 여러가지가 있을 수 있다. 특히 SARSA에서는 첫번째 기대값에서와 마찬가지로 실제로 관측된 데이터만을 고려하여 기대값을 처리할 수 있고, 나중에 학습할 DQN(Q learning)에서는 $Q$ 함수의 최대값을 이용한다.

\begin{aligned} SARSA &: Q^\pi (s,a) \approx r + \gamma Q^\pi (s',a') = Q^{\pi}_{tar:SARSA}(s,a) \\ DQN &: Q^\pi (s,a) \approx r + \gamma \max_{a'_i} Q^\pi (s',a'_i) = Q^{\pi}_{tar:DQN}(s,a) \end{aligned}

여기서 SARSA 방법은 타겟 $Q$ 함수를 구하기 위해 $(s,a,r,s',a')$ 의 데이터가 필요하기 때문에 SARSA라는 이름이 붙었고, 또한 활성정책 알고리즘이라는 것을 알 수 있다. 활성 정책 알고리즘이란 여기에서 설명했듯이 알고리즘이 학습하며 향상 시키고자 하는 정책과 데이터 수집 시에 사용되는 정책이 같은 알고리즘으로 SARSA는 대표적인 활성 정책 알고리즘이다. 만약 향상하고자 하는 정책이 $\pi_1$ , 데이터 수집 시에 사용된 정책이 $\pi_2$ 인 것처럼 서로 다르다고 하자. SARSA에서 TD 업데이트는 $E_{a'_1\sim \pi_1 (s')}[Q^{\pi_1}_\theta (s',a'_1)]$ 와 같이 정책 $\pi_1$ 에 대한 기대값을 계산해야한다. 이때, 데이터 수집 시에도 $\pi_1$ 를 사용하였다면 올바르게 기대값이 계산되겠지만, 만약 $\pi_2$ 을 사용한다면 $\gamma Q^{\pi_1} (s',a'_2)$ 와 같이 $\pi_2$ 를 통해 행해진 행동 $a'_2$ 를 사용하여 기대값이 계산되기 때문에 올바른 업데이트를 할 수 없다(다만 DQN은 비활성 정책 알고리즘으로 그 차이점은 다음 글에서 설명한다).

시간차 학습 방법은 부트스트랩 학습 방법으로, DP에서와 마찬가지로 이전에 계산된(학습된) 가치함수를 이용한다. 따라서 매 에피소드마다 데이터를 새로 수집하여 타겟을 변경하는 몬테칼로 방법에 비해 추정값의 분산이 적다.(타겟 $Q$ 함수 또한 신경망으로 근사된 $Q$ 함수 값을 이용하기 때문에 보상값 정도의 차이만 생긴다.)

이러한 SARSA 방법 등의 시간차 학습 방법은 선형 함수 근사 등에 대해서는 그 수렴성이 증명되어 있으며(증명은 TBD, https://www.youtube.com/playlist?list=PL_iWQOsE6TfURIIhCrlt-wj9ByIVpbfGc, q-learning paper 등 참고), 직관적으로 처음에는 신경망으로 근사된 $Q_\theta$ 가 엉망이기 때문에 타겟 $Q$ 함수 또한 정확하지 않지만, 매 step 마다 취득된 보상값을 통해 정확한 가치 함수의 값으로 수렴하게 된다.