*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다.
|내용 정리|
<강화 학습: SARSA 알고리즘 코드 구현 연습>
- 환경 구현(Env 클래스):
- 에이전트가 (0,0)에서 시작하고 목표가 (3,3)인 4x4 그리드 월드
- 위, 오른쪽, 아래, 왼쪽의 네 가지 가능한 행동
- 목표에 도달할 때 +10의 보상, 그 외에는 0
- 환경은 에이전트의 움직임과 경계 확인을 처리함
- SARSA 알고리즘 구현:
- 온폴리시(on-policy) 시간차(temporal difference) 학습 알고리즘
- 가상의 최적 행동이 아닌 실제 취한 행동을 기반으로 Q-값 업데이트
- 핵심 업데이트 공식 사용: Q(s,a) ← Q(s,a) + α[r + γQ(s',a') - Q(s,a)]
- 탐색 전략:
- ε-greedy 정책으로 탐색과 활용의 균형을 맞춤
- ε(탐색률)과 α(학습률) 모두 시간이 지남에 따라 감소
- 탐색은 학습 초기에 환경을 발견하는 데 도움을 줌
- 활용은 학습된 정보를 기반으로 정책을 개선함
실행 구조
프로세스 흐름:
- 모든 상태-행동 쌍에 대한 Q-값을 0으로 초기화
- 각 에피소드마다:
- 환경 초기화(에이전트를 시작 위치에 배치)
- ε-greedy 정책을 사용하여 초기 행동 선택
- 에피소드가 끝날 때까지:
- 행동을 취하고, 보상과 다음 상태 관찰
- ε-greedy 정책을 사용하여 다음 행동 선택
- SARSA 규칙을 사용하여 Q-값 업데이트
- 다음 상태-행동 쌍으로 이동
- 최종 Q-값에서 최적 정책 추출
최적 정책 성능
이 그리드 월드에서 SARSA가 학습한 최적 정책:
- 에이전트를 시작 위치에서 목표 위치로 안내
- 누적 보상을 최대화하기 위해 최단 경로 선택
- 행동은 결정적(학습된 Q-값에 대해 탐욕적)
두 번째 아티팩트의 시각화는 에이전트가 그리드의 모든 위치에서 목표에 도달하기 위해 어떻게 이동하는지 보여준다. 화살표는 각 상태에서 가장 높은 Q-값을 가진 행동을 나타낸다. 이 구현은 다음과 같은 기본 강화학습 원칙을 보여준다:
- 가치 함수 근사
- 시간차 학습
- 탐색과 활용의 균형
- 가치 함수에서 정책 도출
핵심 코드 추출 및 설명
1. 환경(Environment) 클래스 핵심 코드
class Env:
def __init__(self):
# 에이전트와 목표 위치 초기화
self.agent_pos = {'y': 0, 'x': 0}
self.goal_pos = {'y': 3, 'x': 3}
self.y_min, self.x_min, self.y_max, self.x_max = 0, 0, 3, 3
# 상태 공간 설정
self.state = np.zeros([4, 4])
self.state[self.goal_pos['y'], self.goal_pos['x']] = -1
self.state[self.agent_pos['y'], self.agent_pos['x']] = 1
# 가능한 모든 상태 생성
self.state_space = list()
for y in range(4):
for x in range(4):
state = np.zeros([4,4])
state[self.goal_pos['y'], self.goal_pos['x']] = -1
state[y, x] = 1
self.state_space.append(state)
self.action_space = [0, 1, 2, 3] # 위, 오른쪽, 아래, 왼쪽
def step(self, action):
# 행동에 따른 에이전트 위치 업데이트
if action == 0: # 위
self.agent_pos['y'] = max(self.agent_pos['y'] - 1, self.y_min)
elif action == 1: # 오른쪽
self.agent_pos['x'] = min(self.agent_pos['x'] + 1, self.x_max)
elif action == 2: # 아래
self.agent_pos['y'] = min(self.agent_pos['y'] + 1, self.y_max)
elif action == 3: # 왼쪽
self.agent_pos['x'] = max(self.agent_pos['x'] - 1, self.x_min)
# 새로운 상태 생성
prev_state = self.state
self.state = np.zeros([4,4])
self.state[self.goal_pos['y'], self.goal_pos['x']] = -1
self.state[self.agent_pos['y'], self.agent_pos['x']] = 1
# 목표 도달 여부 확인
done = False
if self.agent_pos == self.goal_pos:
done = True
# 보상 계산
reward = self.reward(prev_state, action, self.state)
return reward, self.state, done
def reward(self, s, a, s_next):
reward = 0
y, x = np.where(s == 1)
y_next, x_next = np.where(s_next == 1)
# 목표에 도달했을 경우 보상 10 제공
if ((y_next == self.goal_pos['y'] and x_next == self.goal_pos['x']) and
(y != self.goal_pos['y'] or x != self.goal_pos['x'])):
reward = 10
return reward2. SARSA 알고리즘 핵심 코드
def sarsa(env):
# Q-값 초기화 (행동 가치 함수)
action_value_matrix = np.zeros([len(env.state_space), len(env.action_space)])
# ε-greedy 정책을 사용한 행동 선택 함수
def sample_action(eps, action_value):
a_max = action_value.argmax()
pi = np.zeros([len(env.action_space)])
pi[:] = eps / len(env.action_space)
pi[a_max] = pi[a_max] + 1 - eps
a = np.random.choice(env.action_space, p=pi)
return a
# 탐색률(ε) 계산 함수
def get_eps(total_step_count):
return 1 / (1 + k_eps * total_step_count)
# SARSA 메인 루프
total_step_count = 0
for loop_count in range(50000):
done = False
s = env.reset()
i_s = get_state_index(env.state_space, s)
eps = get_eps(total_step_count)
a = sample_action(eps, action_value_matrix[i_s])
# 에피소드 생성
while not done:
# 행동 실행 및 다음 상태, 보상 관찰
r, s_next, done = env.step(a)
i_s_next = get_state_index(env.state_space, s_next)
# 다음 상태에서 ε-greedy로 다음 행동 선택
eps = get_eps(total_step_count)
a_next = sample_action(eps, action_value_matrix[i_s_next])
# 학습률 계산
alpha = 1 / (1 + k_alpha * loop_count)
# TD 오차 계산 및 Q-값 업데이트
td = r + gamma * action_value_matrix[i_s_next][a_next] - action_value_matrix[i_s][a]
action_value_matrix[i_s][a] = action_value_matrix[i_s][a] + alpha * td
# 목표 상태의 경우 Q-값을 0으로 설정
if done:
action_value_matrix[i_s_next] = 0
# 다음 상태-행동 쌍으로 이동
s = s_next
i_s = i_s_next
a = a_next
total_step_count += 1
# 최적 정책 생성
policy = np.zeros([len(env.state_space), len(env.action_space)])
state_indexes = np.arange(len(env.state_space))
argmax_actions = action_value_matrix.argmax(axis=-1)
policy[state_indexes, argmax_actions] = 1.0
return action_value_matrix, policy코드 상세 설명
1. 환경(Env) 클래스
- 초기화 (__init__):
- 4x4 크기의 그리드 월드 생성
- 에이전트는 (0,0)에서 시작, 목표는 (3,3)에 위치
- 상태는 4x4 배열로 표현: 에이전트 위치는 1, 목표 위치는 -1, 나머지는 0
- state_space는 모든 가능한 상태를 저장 (총 16개의 상태)
- action_space는 가능한 모든 행동(0:위, 1:오른쪽, 2:아래, 3:왼쪽)
- step 함수:
- 주어진 행동(action)에 따라 에이전트의 위치 업데이트
- 경계 밖으로 나가는 것을 방지하는 로직 포함
- 새로운 상태를 생성하고 목표 도달 여부 확인
- reward 함수를 통해 보상 계산 후 반환
- reward 함수:
- 목표에 도달했을 때만 보상 10을 제공, 그 외에는 0
- 단순한 보상 체계로 에이전트가 목표를 찾도록 유도
2. SARSA 알고리즘
- 초기화:
- 모든 상태-행동 쌍에 대한 Q-값을 0으로 초기화
- sample_action 함수:
- ε-greedy 정책을 구현
- 확률 ε으로 무작위 행동 선택
- 확률 1-ε로 Q-값이 가장 높은 행동 선택
- 수식: π(a|s) = ε/|A| + (1-ε) if a = argmax Q(s,a') else ε/|A|
- get_eps 함수:
- 시간에 따라 감소하는 탐색률(ε) 계산
- 수식: ε = 1/(1 + k_ε * total_step_count)
- 초기에는 탐색을 많이 하고 시간이 지남에 따라 학습된 정책에 더 의존
- 메인 루프:
- 환경 초기화 및 시작 상태에서 ε-greedy로 행동 선택
- 상태-행동-보상-다음상태-다음행동 샘플 수집
- TD 오차 계산: δ = r + γQ(s',a') - Q(s,a)
- Q-값 업데이트: Q(s,a) ← Q(s,a) + α * δ
- 다음 상태-행동 쌍으로 이동
- 목표에 도달할 때까지 2-5 반복
- 50,000번의 에피소드 수행
- 학습률(α) 감소:
- 수식: α = 1/(1 + k_α * loop_count)
- 시간이 지남에 따라 학습률 감소로 Q-값의 안정화
- 최적 정책 생성:
- 각 상태에서 Q-값이 가장 높은 행동을 선택하는 결정적 정책
- 모든 상태에 대한 최적 행동을 매핑한 배열 반환
핵심 알고리즘 수식
SARSA의 핵심은 다음 TD 학습 업데이트 규칙이다:
Q(s, a) ← Q(s, a) + α[r + γQ(s', a') - Q(s, a)]
여기서:
- Q(s, a): 상태 s에서 행동 a를 취했을 때의 예상 누적 보상
- α: 학습률(시간에 따라 감소)
- r: 즉각적인 보상
- γ: 할인 계수(0.9로 설정됨)
- s': 행동 a를 취한 후의 다음 상태
- a': 상태 s'에서 ε-greedy 정책에 따라 선택된 다음 행동
이 알고리즘은 실제로 취한 행동(a')의 Q-값을 사용하여 현재 Q-값을 업데이트하는 온폴리시(on-policy) 학습 방법이다. 이는 Q-learning과의 주요 차이점으로, Q-learning은 다음 상태에서 가능한 최대 Q-값을 사용한다.
최종적으로, 충분한 학습 후 각 상태에서 가장 높은 Q-값을 가진 행동을 선택하는 최적 정책이 형성된다. 이 정책은 에이전트를 시작 위치에서 목표까지의 최단 경로로 안내한다.
Policy Iteration과 SARSA 결과값 비교 분석
제공된 두 이미지는 각각 Policy Iteration과 SARSA 알고리즘의 실행 결과를 보여준다. 두 알고리즘의 결과값을 비교해보자.
가치 함수(Value Function) 비교
Policy Iteration 결과 (이미지 1)
초기 결과:
[0.70296524 0.8610546 1.13251421 1.38260723]
[0.8610546 1.13397666 1.66059224 2.25038023]
[1.13251421 1.66059224 2.86659777 4.71086143]
[1.38260723 2.25038023 4.71086143 0. ]최종 결과:
[5.9049 6.561 7.29 8.1 ]
[6.561 7.29 8.1 9. ]
[7.29 8.1 9. 10. ]
[8.1 9. 10. 0. ]SARSA 결과 (이미지 2)
최종 결과:
5.861 6.478 7.246 8.044]
[6.531 7.233 8.076 8.998]
[7.269 8.063 8.989 10.000]
[8.091 8.997 10.000 0.000]최적 행동(Optimal Actions) 비교
SARSA 결과에서 최적 행동 (argmax_actions)
[2 1 2 2]
[2 1 1 2]
[2 1 2 2]
[1 1 1 0]여기서 숫자는 각 상태에서의 최적 행동을 나타낸다:
- 0: 위쪽
- 1: 오른쪽
- 2: 아래쪽
- 3: 왼쪽
핵심 차이점
- 가치 함수 값:
- Policy Iteration은 더 균일하고 정수에 가까운 값(5.9, 6.56, 7.29, 8.1 등)을 생성했다.
- SARSA는 약간 더 세밀한 값(5.861, 6.478, 7.246 등)을 생성했다.
- 목표 상태의 가치:
- 두 알고리즘 모두 목표 상태(오른쪽 하단 코너)의 가치는 0이다.
- 가장 높은 가치:
- 두 알고리즘 모두 목표 바로 옆 상태들에서 10 또는 10에 가까운 가장 높은 가치를 보여준다.
- 수렴 패턴:
- Policy Iteration은 이론적으로 정확한 값으로 더 빠르게 수렴한다.
- SARSA는 시간에 따라 점진적으로 수렴하며, 일부 탐색으로 인해 약간의 값 변동이 있을 수 있다.
- 학습 파라미터:
- SARSA 실행 결과에서는 eps(입실론): 0.0154와 alpha(알파): 0.0196 값이 표시된다.
- 이는 학습이 거의 끝나고 탐색(exploration)이 매우 적게 이루어지는 단계를 보여준다.
결론
두 알고리즘 모두 비슷한 가치 함수와 최적 정책을 학습했지만, 접근 방식에는 차이가 있다:
- Policy Iteration은 환경 모델을 알고 있으므로 정확한 값으로 더 직접적으로 수렴.
- SARSA는 실제 경험을 통해 학습하므로 약간의 노이즈가 있을 수 있지만, 여전히 유사한 최종 결과에 도달.
이 비교는 두 알고리즘이 서로 다른 접근 방식에도 불구하고 같은 문제에 대해 유사한 해결책을 찾을 수 있음을 보여준다. 실제 적용에서는 환경 모델의 가용성, 상태 공간의 크기, 컴퓨팅 리소스 등에 따라 적절한 알고리즘을 선택하는 것이 중요하다.
|인증|
-------
패스트캠퍼스 링크