SARSA

최적설계 게임 개발 소프트웨어 마지막 수정: 2026-07-29 04:21:53

1. 개요[편집]

Q러닝은 “이론상 최적 경로”를 배우고, SARSA는 “내가 실수할 걸 아는 경로”를 배운다.

SARSA(State–Action–Reward–State–Action)는 행동가치함수 $Q(s,a)$ 를 시간차 갱신으로 학습하는 온-정책(on-policy) 강화 학습 제어 알고리즘이다. 이름은 갱신 한 번에 필요한 오중항 $(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})$ 의 머리글자를 그대로 딴 것으로, 알고리즘 이름 중 손에 꼽게 정직한 작명이다.¹

핵심은 마지막 $a_{t+1}$ 이다. 다음 상태에서 실제로 취할 행동의 가치로 부트스트랩하기 때문에, 학습되는 $Q$ 는 “최적 정책의 가치”가 아니라 “지금 내가 굴리고 있는 탐험 섞인 정책의 가치”가 된다. 이 한 글자 차이가 Q러닝과 SARSA를 완전히 다른 알고리즘으로 갈라놓는다.

2. 갱신식[편집]

SARSA의 갱신은 한 줄이다.

Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha \big[\, r_{t+1} + \gamma\, Q(s_{t+1}, a_{t+1}) - Q(s_t,a_t) \,\big]

대괄호 안이 시간차 학습의 TD 오차 $\delta_t$ 이고, $\alpha$ 는 학습률, $\gamma$ 는 감가율이다. 알고리즘 골격은 다음과 같다.

$s$ 에서 현재 정책(보통 $\epsilon$ -탐욕)으로 $a$ 를 뽑는다.
$a$ 를 실행해 $r$ 과 $s'$ 을 관측한다.
$s'$ 에서 같은 정책으로 $a'$ 을 뽑는다.
위 식으로 $Q(s,a)$ 를 갱신한다.
$s \leftarrow s'$ , $a \leftarrow a'$ . 즉 3에서 뽑은 $a'$ 은 실제로 다음에 실행된다.

3단계에서 뽑은 행동을 버리지 않고 그대로 쓰는 것이 온-정책의 실체다. 표본을 만든 정책과 평가하는 정책이 동일하므로 중요도 보정(importance sampling)이 필요 없다.

3. 온-정책 대 오프-정책[편집]

같은 자리에서 Q러닝은 이렇게 쓴다.

Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha\big[\, r_{t+1} + \gamma \max_{a'} Q(s_{t+1},a') - Q(s_t,a_t)\,\big]

$\max$ 가 들어가는 순간 표적은 “다음 상태에서 탐욕적으로 행동했다면”의 가치가 되고, 실제 행동과 무관해진다. 이것이 오프-정책이다. 정리하면 두 알고리즘은 각각 다른 대상을 학습한다.

항목	SARSA	Q러닝
표적	실제 취한 $a'$ 의 가치	최댓값을 주는 행동의 가치
학습 대상	현재 행동 정책의 $Q^\pi$	최적 $Q^\ast$
리플레이 버퍼	원칙적으로 부적합	자연스럽게 적합
탐험 잡음	가치에 반영됨	무시됨
최댓값 편향	상대적으로 약함	뚜렷함

$\epsilon \to 0$ 이면 행동 정책이 탐욕 정책으로 수렴하므로 SARSA의 학습 결과도 최적 정책으로 간다. 즉 둘의 차이는 탐험이 살아 있는 동안 드러난다.

4. 절벽 걷기 — 교과서 예제[편집]

이 차이를 가장 선명하게 보여주는 것이 서턴·바토 교과서의 절벽 걷기(cliff walking)다. $4\times 12$ 격자에서 왼쪽 아래가 출발, 오른쪽 아래가 목표이고, 그 사이 아랫줄 전체가 절벽이다. 한 걸음마다 보상 $-1$ , 절벽에 빠지면 $-100$ 과 함께 출발점으로 되돌아간다.

Q러닝은 절벽 바로 옆을 지나는 최단 경로를 학습한다. $\max$ 표적은 “탐험 실수 따위 없다”고 가정하므로, 절벽 옆 칸의 가치가 깎이지 않는다.
SARSA는 절벽에서 한 줄 위로 우회하는 안전 경로를 학습한다. $\epsilon$ -탐욕이 가끔 아래로 떨어뜨리고, 그 $-100$ 이 $a'$ 을 통해 절벽 옆 칸의 $Q$ 로 역전파되기 때문이다.

결과적으로 $\epsilon = 0.1$ 로 계속 굴리면 온라인 누적 보상은 SARSA가 더 높다. Q러닝이 배운 정책이 더 “최적”인데도 실제 성능은 나쁜, 강화 학습 입문자 전용 낚시 문제다.² 물론 $\epsilon$ 을 서서히 0으로 줄이면 둘 다 최적 경로로 수렴한다.

이 성질은 시뮬레이션이 아니라 실물을 굴릴 때 의미가 커진다. 실기 로봇이나 모델 예측 제어와 병용되는 시스템에서는 “탐험 잡음까지 포함한 정책의 가치”가 오히려 우리가 알고 싶은 값이다.

5. 변형 — 기대 SARSA와 SARSA(λ)[편집]

기대 SARSA(Expected SARSA)는 $a'$ 을 한 번 뽑는 대신 정책 하에서의 기댓값을 직접 취한다.

Q(s,a) \leftarrow Q(s,a) + \alpha\Big[\, r + \gamma \sum_{a'} \pi(a'\mid s')\,Q(s',a') - Q(s,a) \,\Big]

$a'$ 추출에서 오는 분산이 통째로 사라지므로 같은 $\alpha$ 에서 더 안정적이고, 계산 비용은 행동 수만큼 곱해질 뿐이다. 재미있는 것은 $\pi$ 를 탐욕 정책으로 두면 이 식이 정확히 Q러닝이 된다는 점 — 기대 SARSA는 SARSA와 Q러닝을 한 식 안에 품는 상위 개념이고, 표적 정책을 행동 정책과 다르게 두면 오프-정책으로도 쓸 수 있다.

**SARSA(λ)**는 적격 흔적 $e(s,a)$ 를 도입해 한 번의 TD 오차를 과거의 여러 상태-행동 쌍에 한꺼번에 뿌린다.

e_t(s,a) = \gamma\lambda\, e_{t-1}(s,a) + \mathbf{1}[s=s_t, a=a_t], \qquad Q(s,a) \leftarrow Q(s,a) + \alpha\, \delta_t\, e_t(s,a)

$\lambda=0$ 이면 원래 SARSA, $\lambda=1$ 이면 몬테카를로에 가까워진다. 보상이 희소한 문제에서 신용 할당 속도가 눈에 띄게 빨라지며, 누적 흔적(accumulating)과 대체 흔적(replacing) 중 후자가 표에서 보통 더 안정적이다.

$n$ -단계 SARSA는 그 중간을 정수 눈금으로 끊는다. 표적을 $\sum_{k=0}^{n-1}\gamma^k r_{t+k+1} + \gamma^n Q(s_{t+n}, a_{t+n})$ 으로 두면 되고, $n=1$ 이 원래 SARSA, $n\to\infty$ 가 몬테카를로 제어다. 온-정책이라 중요도 보정 없이 그냥 $n$ 을 늘릴 수 있다는 것이 오프-정책 대비 실질적 이점이며, 실무에서는 $n=4{\sim}10$ 부근이 무난하다.

6. 수렴 조건[편집]

표 형태(tabular) SARSA는 다음 두 조건 아래 최적 행동가치함수 $Q^\ast$ 로 확률 1 수렴한다.

로빈스-먼로 스텝 조건: $\sum_t \alpha_t(s,a) = \infty$ , $\sum_t \alpha_t^2(s,a) < \infty$ . 모든 $(s,a)$ 가 무한히 자주 방문돼야 한다는 요구가 여기에 숨어 있다. 자세한 확률근사 이론은 로빈스-먼로 알고리즘 참고.
GLIE(Greedy in the Limit with Infinite Exploration): 모든 상태-행동 쌍을 무한히 방문하면서, 정책은 극한에서 탐욕 정책으로 수렴해야 한다. $\epsilon_k = 1/k$ 가 전형적인 구현이다.

두 번째 조건이 SARSA에만 붙는 부담이다. Q러닝은 표적에 행동 정책이 안 들어가므로 “무한 방문”만 있으면 되지만, SARSA는 정책 자체가 탐욕으로 수렴해야 한다. 온-정책의 대가다.

함수근사를 붙이면 이야기가 또 달라지는데, 역설적으로 여기서는 SARSA가 유리하다. 선형 함수근사 + 온-정책 조합은 유계 오차 내 수렴이 알려져 있는 반면, “함수근사 + 부트스트랩 + 오프-정책”의 죽음의 삼중주에 걸리는 Q러닝은 발산 예제가 존재한다.³

7. 실무 감각[편집]

표 크기가 $|S|\times|A|$ 로 폭발하므로 순수 표 SARSA는 격자세계·간단한 보드게임 규모에서 멈춘다. 그 위로는 타일 코딩이나 신경망 근사가 필요하다.
리플레이 버퍼와 궁합이 나쁘다. 버퍼 안의 $a'$ 은 옛 정책이 뽑은 것이라 온-정책 가정이 깨진다. 심층 강화 학습이 Q러닝·액터-크리틱 계열로 기운 실무적 이유 중 하나다.
안전이 중요한 문제(로봇 실기, 공정 제어)에서는 SARSA의 “겁 많은 정책”이 오히려 요구사항에 맞는다. 시뮬레이터 안에서 최적을 노릴 때만 Q러닝이 이긴다.⁴
$\epsilon$ 감쇠 스케줄이 결과를 지배한다. 너무 빨리 줄이면 GLIE의 무한 탐험 조건이 사실상 깨져 엉뚱한 정책에 눌러앉고, 너무 느리게 줄이면 학습된 $Q$ 가 계속 탐험 잡음에 눌린 값에 머문다. 같은 문제에서 SARSA와 Q러닝을 비교할 때는 반드시 같은 스케줄로 맞춰야 공정한 비교가 된다.
초기값 $Q_0$ 를 크게 잡는 낙관적 초기화는 SARSA에서도 유효한 탐험 장치다. 방문하지 않은 행동의 가치가 부풀려져 있으므로 에이전트가 스스로 훑고 지나간다. $\epsilon$ 을 낮추면서 탐험을 유지하는 값싼 수법.

8. 관련 문서[편집]

원래 Rummery와 Niranjan(1994)이 붙인 이름은 “수정 연결주의 Q러닝”(Modified Connectionist Q-Learning)이었다. 지금 이름은 리치 서턴이 오중항을 보고 제안한 것으로, 원저자들의 작명보다 훨씬 성공했다. ↩
“최적 정책을 배웠는데 성적이 더 나쁘다”는 이 상황은 버그가 아니다. Q러닝이 학습한 $Q^\ast$ 는 탐험이 없는 세계의 값이고, 채점은 탐험이 있는 세계에서 하기 때문이다. 시험 범위와 출제 범위가 다르면 원래 이런 일이 생긴다. ↩
베어드의 반례(Baird’s counterexample, 1995)가 그 유명한 발산 사례다. 상태가 7개뿐인 장난감 MDP에서 선형 근사 오프-정책 TD의 파라미터가 지수적으로 발산한다. 문제가 작다고 안전한 게 아니다. ↩
그래서 “안전한 강화 학습” 문헌은 SARSA를 은근히 좋아한다. 리스크 회피를 별도 제약으로 넣지 않아도, 탐험 정책 자체가 기대값 안에 위험을 섞어 넣어 주기 때문이다. 공짜 보험이 아니라 탐험 확률로 지불하는 보험이다. ↩