이 알고리즘의 이름인 SARSA는 학습이 진행되는 과정에서 관측되는
다섯 요소인 상태(St), 행동(At), 보상(Rt+1), 다음 상태(St+1), 그리고 다음 행동(At+1)의 앞 글자를 따서 붙여졌다. 즉, 에이전트는 현재 상태에서 행동을 선택하고, 보상을 받은 뒤 다음
상태로 이동하며, 그 상태에서 다시 행동을 선택하는 과정을 반복하게 된다. 이처럼 상태와 행동이 연속적으로 연결되어 학습이 이루어지기 때문에 SARSA는
실제 행동 경로에 따른 학습을 가능하게 한다.
TD나 몬테카를로 방법은 정책에 따라 하나의 행동만 선택하여 학습했기
때문에, 모든 가능성을 고려한 올바른 정책 평가 수식이라고 보기 어려웠다. 하지만 SARSA는 상태와 행동을 함께 고려하면서 실제 경험을 기반으로
정책을 평가하기 때문에, 모델 프리 환경에서의 정책 평가에 보다 적합한 알고리즘이라고 할 수 있다. 또한, SARSA에서도 정책 제어는 다른 방식들과 마찬가지로 Q함수 값을 최대화하는 방향으로 업데이트되며, 이는 점차 더 나은
정책을 만들어가도록 도와준다.
import numpy as np
import random
# (1) 상태 및 행동 정의
states = ['S', 'R1', 'R2', 'R3', 'F']
state_to_index = {
'S': 0,
'R1': 1,
'R2': 2,
'R3': 3,
'F': 4
}
actions = {} # (2) 각 상태에서 가능한 행동들 저장
# (3) 상태 전이 및 보상을 행동 단위로 정의
transitions = {
'S': [('R1', 0), ('R2', 0)],
'R1': [('R2', 0), ('R3', 0), ('F', 1)],
'R2': [('R3', 0), ('F', 1)],
'R3': [('F', 1)],
'F': []
}
# (4) 행동 가치 함수 Q(s,a) 초기화
Q = {}
for s in states:
Q[s] = {}
for (s_next, _) in transitions[s]:
Q[s][s_next] = 0.0 # 초기 Q값 0
# (5) 학습 파라미터
alpha = 0.1
gamma = 0.9
epsilon = 0.1 # 탐험 확률
episodes = 500
# (6) SARSA 학습 루프
for ep in range(episodes):
state = 'S'
#(7) ε-greedy로 행동 선택
if random.random() < epsilon:
action = random.choice(list(Q[state].keys()))
else:
action = max(Q[state], key=Q[state].get)
while state != 'F':
next_state = action
reward = 0
# (8) 선택된 행동에 따라 다음 상태로 이동
for (s_next, r) in transitions[state]:
if s_next == next_state:
reward = r
break
# (9) 다음 행동 선택 (SARSA 방식)
if next_state != 'F':
if random.random() < epsilon:
next_action = random.choice(list(Q[next_state].keys()))
else:
next_action = max(Q[next_state], key=Q[next_state].get)
td_target = reward + gamma * Q[next_state][next_action]
else:
td_target = reward # 종료 상태
# (10) Q값 업데이트
Q[state][action] += alpha * (td_target - Q[state][action])
# (11) 다음 상태로 이동
state = next_state
if state != 'F':
action = next_action
# (12) 결과 출력
print("행동 가치 함수 Q(s, a):")
for s in Q:
for a in Q[s]:
print(f"Q({s}, {a}) = {Q[s][a]:.2f}")
행동 가치 함수 Q(s, a):
Q(S, R1) = 0.77
Q(S, R2) = 0.57
Q(R1, R2) = 0.61
Q(R1, R3) = 0.90
Q(R1, F) = 0.65
Q(R2, R3) = 0.88
Q(R2, F) = 0.10
Q(R3, F) = 1.00SARSA
간단한 예제를 통해 SARSA 동작 방식을 살펴보자.
(1) 먼저 이 환경에서 사용할 상태들을 정의한다. 시작 상태 S를 포함해 중간 상태
R1, R2, R3, 그리고 종료 상태 F까지 총 다섯 개의 상태가 있으며, 각 상태는 사람이 읽기 쉽게 문자열로 정의된다. 그리고 각 상태에
고유한 인덱스를 직접 지정해 딕셔너리 형태로 저장한다. 이 인덱스는 이후 결과를 확인하거나 시각화할
때 참고용으로 활용될 수 있다.
(2) 각 상태에서 가능한 행동들을 저장할 공간으로 actions라는 빈 딕셔너리를 준비한다. 이 코드는 이후 행동 정의가
필요할 때 사용하기 위한 자리표시자와 같다.
(3) 상태 전이 구조를 정의한다.
딕셔너리 형태로 구성된 이 구조는 각 상태에서 어떤 다른 상태로 이동할 수 있는지를 명시하고, 그
전이에 따른 보상도 함께 정의되어 있다. 예를 들어 S에서 R1이나 R2로 이동할 수 있고, 그
보상은 모두 0이다. 하지만 R3에서 F로 이동하는 전이에서는 보상 1이 주어진다. 이 정의는
SARSA 알고리즘이 환경을 어떻게 인식하고 학습할지를 결정하는 핵심 요소이다.
(4) 행동 가치 함수인 Q함수를
초기화한다. 각 상태별로 가능한 다음 상태들(즉, 행동)에 대해 초기 Q값을 0.0으로 설정하여 딕셔너리로 저장한다. 이는 에이전트가 아직 아무런
경험이 없는 상태에서 출발함을 의미한다.
(5) 학습에 필요한 주요 파라미터를 설정한다. 학습률 알파는 새로운 정보가 기존 Q값에 얼마나 반영될지를 결정하며, 할인율 감마는 미래 보상을 얼마나 중요하게 여길지를 나타낸다. 또한
탐험률 엡실론은 에이전트가 얼마나 자주 새로운 행동을 시도할지를 정한다. 학습은 총 500번의 에피소드를 반복하면서 이루어진다.
(6) 본격적인 SARSA 학습이
시작된다. 각 에피소드마다 에이전트는 항상 시작 상태인 S에서
출발하며, 종료 상태 F에 도달할 때까지 반복적으로 상태를
이동하고 Q값을 갱신한다.
(7) 현재 상태에서 어떤 행동을 선택할지 결정한다. 엡실론 탐험 전략을 사용하여 일정 확률로 무작위 행동을 선택하고, 그렇지
않은 경우에는 현재 상태에서 가장 Q값이 높은 행동을 선택한다. 이를
통해 학습 초기에 다양한 경험을 쌓을 수 있게 하며, 후반으로 갈수록 더 나은 행동을 지속적으로 선택할
수 있도록 유도한다.
(8) 선택된 행동을 바탕으로 다음 상태로 이동하고, 그 전이에 따른 보상을 확인한다. 상태 전이 정보에서 현재 상태와
다음 상태의 쌍을 찾아 해당 보상을 가져온다. 이때 보상은 대부분 0이며, F로 이동하는 전이에서만 1이 주어진다.
(9) 다음 상태가 종료 상태 F가
아니라면, SARSA 방식에 따라 다음 상태에서 취할 다음 행동도 미리 선택한다. 이때도 마찬가지로 엡실론 탐험 전략을 사용하여 무작위 또는 최적 행동을 선택한다. 이후 다음 상태와 다음 행동을 바탕으로 Q값을 업데이트할 때 사용할
타깃 값을 계산한다. 타깃 값은 보상과 다음 상태에서의 예측 Q값을
반영하여 계산된다.
(10) 앞서 계산한 타깃 값을 이용해 현재 상태-행동 쌍의 Q값을 업데이트한다.
SARSA 알고리즘은 실제로 경험한 전이만을 기반으로 Q값을 수정하기 때문에, 한 번의 경험이 학습에 직접적인 영향을 주게 된다.
(11) 에이전트는 다음 상태로 이동하고, 그 상태가 종료 상태가 아니라면 다음 행동도 계속 이어서 수행한다. 이렇게
현재 상태와 행동이 연속적으로 이어지며 (S, A, R, S’, A’) 형태로 반복되기 때문에 이 알고리즘을 SARSA라고 부른다.
(12) 모든 에피소드가 끝난 후,
학습이 완료된 행동 가치 함수 Q를 출력한다. 각
상태에서 가능한 행동과 그에 대한 Q값이 출력되며, 이 값들은
학습을 통해 해당 상태-행동 쌍이 얼마나 좋은지를 나타낸다. Q값이
높을수록 해당 행동이 좋은 결과를 가져올 가능성이 높다는 것을 의미한다. 이를 통해 에이전트는 상태에
따라 어떤 행동을 선택하는 것이 가장 좋은 지 판단할 수 있게 된다.
