[Reinforcement Learning] SARSA (On-policy TD Control)

2025.06.29 - [Data & Research] - [Reinforcement Learning] Table of Contents

---

1. SARSA: On-Policy TD Control

SARSA라는 이름은 Q값을 한 번 업데이트하는 데 필요한 데이터 튜플(tuple)의 순서에서 유래했습니다.

\((S, A, R, S', A')\)

이는 State, Action, Reward, 다음 State, 그리고 그 다음의 Action을 의미합니다.

SARSA의 핵심 업데이트 규칙은 다음과 같습니다. TD(0)의 \(V\)함수 업데이트 규칙을 \(Q\)함수로 확장한 형태입니다.

\[ Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t) \right] \]

• TD target: \(R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})\)
• TD error: \([R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)]\)

여기서 중요한 부분은 TD 타겟을 계산할 때, 다음 상태 \(S_{t+1}\)에서 실제로 다음에 할 행동 \(A_{t+1}\)의 \(Q\)값인 \(Q(S_{t+1}, A_{t+1})\)를 사용한다는 점입니다. 이 때문에 SARSA를 On-Policy(정책 기반) 알고리즘이라고 부릅니다. 이 내용은 뒤에서 Off-Policy정책기반 알고리즘을 이야기할 때 다시 언급하도록 하겠습니다. 

 

• On-Policy : 에이전트가 현재 행동하고 있는 정책의 가치를 학습하고, 그 정책을 점진적으로 개선하는 방식입니다. (행동하는 정책 = 학습하는 정책)
• Off-Policy : 에이전트는 하나의 정책(행동 정책)으로 자유롭게 행동하면서, 그 경험을 바탕으로 자신과는 다른 별개의 정책(타겟 정책, 보통 최적의 탐욕 정책)을 학습하는 방식입니다. (행동하는 정책 ≠ 배우는 정책)

 

 

2. SARSA 알고리즘의 전체 흐름

1. 모든 \(Q(s,a)\)를 0 또는 임의의 값으로 초기화합니다.
2. Loop (각 에피소드마다 반복):
   1. 상태 \(S\)를 에피소드의 시작 상태로 초기화합니다.
   2. 현재 \(Q\)값에 대한 ε-Greedy 정책에 따라 \(S\)에서 행동 \(a\)를 선택합니다.
   3. Loop (에피소드가 끝날 때까지 스텝마다 반복):
      1. 행동 \(a\)를 수행하여, 보상 \(R\)과 다음 상태 \(S'\)를 관찰합니다.
      2. (가장 중요한 부분) 다음 상태 \(S'\)에서, 현재 Q값에 대한 ε-Greedy 정책에 따라 다음 행동 \(a'\)를 미리 선택합니다.
      3. 이제 우리는 \((S, A, R, S', A')\) 튜플을 모두 확보했습니다. 이 정보로 \(Q(S,A)\)를 업데이트합니다.
         \(Q(S, A) \leftarrow Q(S, A) + \alpha [R + \gamma Q(S', A') - Q(S, A)]\)
      4. 다음 스텝을 위해 상태와 행동을 업데이트합니다: \(S \leftarrow S'\), \(A \leftarrow A'\)

 

3. N-step SARSA

SARSA의 중요 특징이 TD의 컨셉을 행동가치함수로 가져온 것이라는 거죠? 그럼 TD에서 N-step TD를 생각했던 것처럼 여기서도 동일한 개념을 생각해 볼 수 있을 것 같습니다. 앞에서 살펴본 것처럼 핵심은 TD target \(q_t^{(n)}\)을 어떻게 정의하는가에 달려 있습니다.

\[ Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left( q_t^{(n)} - Q(S_t, A_t) \right) \]

 

• 1-step SARSA (표준 SARSA):
  1 step의 실제 보상과 바로 다음 스텝의 \(Q\)값 추정치를 사용합니다.
  \[ q_t^{(1)} \overset{\text{def}}{=} R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) \]
• 2-step SARSA:
  2 step의 실제 보상을 경험한 후, 2 step 뒤의 \(Q\)값으로 Bootstrapping합니다.
  \[ q_t^{(2)} \overset{\text{def}}{=} R_{t+1} + \gamma R_{t+2} + \gamma^2 Q(S_{t+2}, A_{t+2}) \]
• 3-step SARSA:
  \[ q_t^{(3)} \overset{\text{def}}{=} R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 Q(S_{t+3}, A_{t+3}) \]
• ...
• ∞-step SARSA (MC Control):
  에피소드가 끝날 때까지의 모든 실제 보상의 합, 즉 전체 리턴을 사용합니다. 이는 MC control과 동일합니다.
  \[ q_t^{(\infty)} \overset{\text{def}}{=} R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{T-1-t}R_T \]

\[ q_t^{(n)} \overset{\text{def}}{=} R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{n-1}R_{t+n} + \gamma^n Q(S_{t+n}, A_{t+n}) \]

 

TD(λ)와 마찬가지로, 특정 n을 고르는 대신 모든 N-step 타겟을 기하급수적으로 감소하는 가중치를 주어 평균내는 방식이 SARSA(λ)입니다. 그 목표값을 SARSA(λ) 리턴, \(q_t^\lambda\)라고 합니다.

\[ q_t^\lambda \overset{\text{def}}{=} (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} q_t^{(n)} \quad (0 \le \lambda \le 1) \]

이 \(q_t^\lambda\)를 업데이트 타겟으로 사용합니다.

\[ Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left( q_t^\lambda - Q(S_t, A_t) \right) \]

여기서도 마찬가지로, \(\lambda=0\)이면 1-step SARSA와 동일해지고, \(\lambda=1\)이면 몬테카를로 제어와 동일한 특성을 갖게 되어, \(\lambda\)값을 통해 편향-분산 트레이드오프를 부드럽게 조절할 수 있습니다. 실제 구현에서는 이 공식을 직접 계산하는 Forward-view 대신, Eligibility Traces을 사용하는 효율적인 Backward-view 방식이 사용됩니다. 

 

4. 왜 SARSA는 On-Policy인가? (다른 정책으로 학습할 수 없는 이유)

SARSA가 On-Policy인 이유는 가치 함수를 업데이트하는 목표값, 즉 'TD 타겟'을 계산하는 방식에 근본적인 원인이 있습니다. 

(1) 가치 계산과 정책 의존성

SARSA는 행동 가치 함수 \(Q(s,a)\)를 추정하며, 그 이론적 기반은 아래와 같은 벨만 기대 방정식입니다.

\[ q_{\pi}(s,a) = r_s^a + \gamma \sum_{s' \in \mathcal{S}} P_{ss'}^a \sum_{a' \in \mathcal{A}} \pi(a'|s') q_{\pi}(s', a') \]

이 식에서 가장 중요한 부분은 아래 주황색으로 표시한 부분 입니다. 

\(\sum_{a' \in \mathcal{A}} \pi(a'|s') q_{\pi}(s', a')\)

이 항은 다음 상태 \(s'\)의 기댓값을 나타내는데, 보시다시피 정책 \(\pi\)의 확률 \(\pi(a'|s')\)로 가중 평균해서 계산됩니다. 즉, 이 벨만 방정식 자체가 '정책 \(\pi\)를 따랐을 때'라는 조건 하에 성립하는 것입니다. 가치 계산이 특정 정책 \(\pi\)에 의존하고 있음을 알 수 있습니다.

2025.06.08 - [Data & Research] - [Reinforcement Learning] 강화학습 문제의 세팅

 

(2) 실제 SARSA 업데이트 규칙과의 연결

위 이론적인 벨만 방정식은 실제 SARSA의 샘플 기반 업데이트 규칙으로 이어집니다. SARSA는 \((S, A, R, S', A')\)라는 샘플을 사용하여 \(Q\)값을 업데이트합니다.

\[ Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t) \right] \]

여기서 TD 타겟은 \(R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})\) 입니다. 이 타겟값이 왜 정책 \(\pi\)에 의존적일까요?

바로 다음 행동 \(A_{t+1}\) 때문입니다. SARSA 알고리즘에서 다음 행동 \(A_{t+1}\)은 현재 에이전트가 따르고 있는 정책 \(\pi\)(예: ε-Greedy)에 의해 직접 샘플링된(선택된) 행동입니다. 따라서, TD 타겟에 포함된 \(Q(S_{t+1}, A_{t+1})\) 값은 정책 \(\pi\)가 실제로 선택한 행동에 대한 가치입니다. 이는 위 벨만 방정식의 기댓값 \(\sum_{a'} \pi(a'|s') q_{\pi}(s', a')\)을 model-free세팅에서 샘플링한 것과 같습니다. 즉, 업데이트의 목표값 자체가 현재 행동 정책 \(\pi\)의 결과물인 것입니다.

 

(3) 왜 다른 정책의 경험을 쓸 수 없는가?

만약 우리가 과거의 정책 \(\pi_{old}\)가 생성한 경험 데이터 \((S, A, R, S', A')\)를 가지고 현재의 새로운 정책 \(\pi_{new}\)를 학습시키려 한다고 가정해봅시다. 이 값으로 TD 타겟을 만들어 행동가치 함수를 업데이트한다면, 우리는 여전히 과거 정책인 \(\pi_{old}\)의 가치를 배우는 셈이지, \(\pi_{new}\)의 가치를 배우는 것이 아닙니다.