*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다.
|내용 정리|
<n-step TD 강화학습 알고리즘 코드 구조 및 실행 흐름>
환경(Environment) 개요
우선 environment.py는 4x4 그리드 환경을 정의한다:
- 에이전트는 (0,0)에서 시작하여 (3,3)의 목표 위치에 도달해야 한다.
- 상태 공간은 4x4 그리드로 표현된다.
- 행동 공간은 {0: 위, 1: 오른쪽, 2: 아래, 3: 왼쪽}이다.
- 목표에 도달하면 보상 10을 받는다.
n-step TD 학습 알고리즘 핵심 코드
여기서는 두 가지 버전의 n-step TD가 구현되어 있다:
- n_step_td_prediction.py: 일반적인 n-step TD 예측
- episodic_n_step_td_prediction.py: 에피소드 기반 n-step TD 예측
핵심 알고리즘 부분
Return 계산 함수:
def calc_return(gamma, rewards):
n = len(rewards)
rewards = np.array(rewards)
gammas = gamma * np.ones([n])
powers = np.arange(n)
power_of_gammas = np.power(gammas, powers)
discounted_rewards = rewards * power_of_gammas # [r, gamma * r, gamma^2 * r, ... ]
g = np.sum(discounted_rewards)
return g
이 함수는 n-step 리턴(G_t^(n))을 계산한다. 수식으로 표현하면:
n-step TD 업데이트 핵심 부분:
discounted_rewards = calc_return(gamma, trajectory['rewards'])
td = discounted_rewards + (gamma ** n) * value_vector[i_s_t] - value_vector[i_s_t_sub_n]
value_vector[i_s_t_sub_n] = value_vector[i_s_t_sub_n] + alpha * td
이 코드는 n-step TD 업데이트 규칙을 구현한다. 수식으로 표현하면:
여기서:
- 는 상태 의 현재 가치 추정값
- 는 학습률
- 은 n-step 리턴(아래수식):
일반 n-step TD와 에피소드 n-step TD의 차이점
- 일반 n-step TD:
- 경로(trajectory)를 따라가며 n-step 단위로 업데이트
- 종료 상태에서는 추가 처리를 통해 남은 상태들을 업데이트
- 에피소드 n-step TD:
- 전체 에피소드를 생성한 후에 각 상태를 업데이트
- 아래 코드가 핵심:
for t in range(step_count):
alpha = alpha_init / (1 + k_alpha * loop_count)
k_min = min(n, step_count - t)
s_t = episode['states'][t]
i_s_t = get_state_index(env.state_space, s_t)
s_t_k = episode['states'][t + k_min]
i_s_t_k = get_state_index(env.state_space, s_t_k)
discounted_rewards = calc_return(gamma, episode['rewards'][t:t + k_min])
td = discounted_rewards + (gamma ** k_min) * value_vector[i_s_t_k] - value_vector[i_s_t]
value_vector[i_s_t] = value_vector[i_s_t] + alpha * td
에피소드 끝에 가까울 때는 남은 스텝 수만큼만 고려
학습률 감소 전략
코드에서는 학습률을 점진적으로 감소시키는 방식을 사용한다:
일반 n-step TD (n_step_td_prediction.py):
# 루프 내에서 학습률 감소
alpha = alpha_init / (1 + k_alpha * loop_count)
에피소드 n-step TD (episodic_n_step_td_prediction.py):
for t in range(step_count):
alpha = alpha_init / (1 + k_alpha * loop_count)
# ... 나머지 코드
이 코드는 학습률을 반복 횟수(loop_count)에 따라 점진적으로 감소시키는 전략을 구현한다. 수식으로 표현하면:
- = 0.2 (초기 학습률)
- = 0.25 (학습률 감소 계수)
- 는 반복 횟수
이 방식은 초기에는 큰 학습률로 빠르게 학습하다가, 반복 횟수가 증가함에 따라 학습률을 점진적으로 줄여 안정적인 수렴을 돕는 전략이다. 이렇게 학습률을 감소시키는 것은 강화학습에서 흔히 사용되는 기법으로, 초기에는 큰 변화를 허용하고 후반부에는 미세 조정을 가능하게 한다.
실제 변수 할당을 통한 코드 실행 과정
환경 설정 및 경로
시뮬레이션에 사용한 경로는 다음과 같다:
- 시작 상태: (0,0)
- 행동 순서: 오른쪽 → 오른쪽 → 아래 → 아래 → 오른쪽 → 아래
- 목표 도달: (3,3)
- 최종 경로: (0,0) → (0,1) → (0,2) → (1,2) → (2,2) → (2,3) → (3,3)
- 보상: 목표 도달 시 +10, 나머지는 0
- 감가율(γ): 0.9
- 학습률(α): 0.2
n=1 TD (일반 TD) 수행 과정
TD(0)라고도 하는 n=1 TD는 각 상태에서 한 스텝 앞만 보고 업데이트한다:
- 초기 상태 (t=0): 모든 상태의 가치 함수 V(s) = 0으로 초기화
- 각 스텝별 업데이트:
- 스텝 1 (0,0) → (0,1): 보상 0
- TD 업데이트: V(0,0) = 0 + 0.2 × (0 + 0.9×0 - 0) = 0
- 스텝 2 (0,1) → (0,2): 보상 0
- TD 업데이트: V(0,1) = 0 + 0.2 × (0 + 0.9×0 - 0) = 0
- 스텝 3 (0,2) → (1,2): 보상 0
- TD 업데이트: V(0,2) = 0 + 0.2 × (0 + 0.9×0 - 0) = 0
- 스텝 4 (1,2) → (2,2): 보상 0
- TD 업데이트: V(1,2) = 0 + 0.2 × (0 + 0.9×0 - 0) = 0
- 스텝 5 (2,2) → (2,3): 보상 0
- TD 업데이트: V(2,2) = 0 + 0.2 × (0 + 0.9×0 - 0) = 0
- 스텝 6 (2,3) → (3,3): 보상 10
- TD 업데이트: V(2,3) = 0 + 0.2 × (10 + 0.9×0 - 0) = 2.0
- 스텝 1 (0,0) → (0,1): 보상 0
- 최종 가치 함수:
- V(2,3) = 2.0 (목표 직전 상태만 가치가 갱신됨)
- 다른 모든 상태 = 0
n=1 TD의 특징은 한 번의 에피소드에서 목표에 인접한 상태의 가치만 갱신되었다는 점이다. 정보가 한 스텝씩만 거슬러 올라가 전파되므로, 여러 에피소드를 통해 점진적으로 먼 상태들의 가치가 갱신된다.
n=3 TD 수행 과정
n=3 TD는 각 상태에서 세 스텝 앞까지 보고 업데이트한다:
- 초기 상태 (t=0): 모든 상태의 가치 함수 V(s) = 0으로 초기화
- 각 스텝별 업데이트:
- 스텝 1~3 (0,0 → 0,1 → 0,2 → 1,2):
- 이 시점에서 첫 n=3 업데이트 수행
- 3단계 리턴 계산: G = 0 + 0.9×0 + 0.9²×0 = 0
- TD 업데이트: V(0,0) = 0 + 0.2 × (0 - 0) = 0
- 스텝 2~4 (0,1 → 0,2 → 1,2 → 2,2):
- 3단계 리턴 계산: G = 0 + 0.9×0 + 0.9²×0 = 0
- TD 업데이트: V(0,1) = 0 + 0.2 × (0 - 0) = 0
- 스텝 3~5 (0,2 → 1,2 → 2,2 → 2,3):
- 3단계 리턴 계산: G = 0 + 0.9×0 + 0.9²×0 = 0
- TD 업데이트: V(0,2) = 0 + 0.2 × (0 - 0) = 0
- 스텝 4~6 (1,2 → 2,2 → 2,3 → 3,3):
- 3단계 리턴 계산: G = 0 + 0.9×0 + 0.9²×10 = 8.1
- TD 업데이트: V(1,2) = 0 + 0.2 × (8.1 - 0) = 1.62
- 스텝 1~3 (0,0 → 0,1 → 0,2 → 1,2):
- 에피소드 종료 후 남은 상태 업데이트 (에피소드 끝 처리):
- k_min = min(3, 6-5) = 1 (상태 2,2의 경우)
- 1단계 리턴 계산: G = 0 + 0.9×10 = 9.0
- TD 업데이트: V(2,2) = 0 + 0.2 × (9.0 - 0) = 1.8
- k_min = min(3, 6-6) = 0 (상태 2,3의 경우)
- 0단계 리턴 계산: G = 10
- TD 업데이트: V(2,3) = 0 + 0.2 × (10 - 0) = 2.0
- k_min = min(3, 6-5) = 1 (상태 2,2의 경우)
- 최종 가치 함수:
- V(1,2) = 1.62
- V(2,2) = 1.8
- V(2,3) = 2.0
- 다른 상태 = 0
n=3 TD의 특징은 한 번의 에피소드에서도 목표에서 더 멀리 떨어진 상태들의 가치가 갱신된다는 점이다. 이는 더 긴 시퀀스의 보상을 고려하기 때문이다.
특히 주목할 부분은:
- 가치 전파 범위: n=1에서는 목표와 인접한 상태만 가치가 업데이트되었지만, n=3에서는 목표에서 최대 3단계 떨어진 상태까지 가치가 전파됩니다. V(1,2)까지 값이 갱신된 것을 확인할 수 있다.
- 에피소드 끝 처리: n=3 방식에서는 에피소드 끝에 가까워지면 k_min = min(n, T-t) 방식으로 남은 단계만큼만 고려한다. 이로 인해 상태 (2,2)는 2단계 리턴으로, 상태 (2,3)은 1단계 리턴으로 업데이트되었다.
- 감가율 효과: 상태에서 목표까지 거리가 멀수록 감가율(γ)로 인해 가치가 낮아진다. 예를 들어:
- V(2,3) = 2.0 (목표에서 1단계 거리)
- V(2,2) = 1.8 (목표에서 2단계 거리)
- V(1,2) = 1.62 (목표에서 3단계 거리)
n값에 따른 비교 분석
n=1(TD(0))과 n=3의 비교를 통해 다음과 같은 차이점을 관찰할 수 있다:
- 정보 전파 속도:
- n=1: 한 번의 에피소드에서는 목표와 직접 연결된 상태만 업데이트
- n=3: 한 번의 에피소드로 목표에서 최대 3단계 떨어진 상태까지 업데이트
- 가치 추정 정확도:
- n=1: 더 작은 시야로 인해 먼 상태의 가치 추정이 부정확할 수 있음
- n=3: 더 긴 시퀀스를 보기 때문에 먼 상태의 가치를 더 정확하게 추정
- 학습 특성:
- n=1: 편향(bias)은 크지만 분산(variance)은 작음
- n=3: n=1보다 편향은 작지만 분산은 큼
- n이 클수록 몬테카를로 방식에 가까워짐
- 계산 복잡성:
- n=1: 간단한 계산 (다음 상태와 보상만 고려)
- n=3: 더 복잡한 계산 (여러 단계의 보상을 누적해서 계산)
실제 구현에서의 고려사항
실제 n-step TD 알고리즘 구현 시 다음 사항들을 고려해야 한다:
- 메모리 사용:
- n이 클수록 더 많은 전이(상태, 행동, 보상)를 메모리에 저장해야 함
- 에피소드 방식은 전체 에피소드를 메모리에 저장해야 함
- 학습률 감소 전략:
- 코드에서는 alpha = alpha_init / (1 + k_alpha * loop_count) 방식으로 학습률을 감소
- 이를 통해 초기에는 빠르게 학습하고 후반에는 안정적으로 수렴
- 에피소드 끝 처리:
- 에피소드가 끝날 때는 남은 상태들에 대해 k_min = min(n, T-t) 방식으로 업데이트
- 이를 통해 에피소드 끝에 가까운 상태들도 적절하게 업데이트됨
- n값 선택:
- 문제의 특성에 따라 적절한 n값 선택이 중요
- n이 작을수록 편향이 크고, n이 클수록 분산이 커짐
- 실전에서는 여러 n값으로 실험하여 최적의 값 선택
결론
n-step TD 알고리즘은 n값을 조절함으로써 TD(0)와 몬테카를로 방법 사이의 균형점을 찾을 수 있는 유연한 방법이다. 시뮬레이션 결과를 통해 n=3이 n=1보다 한 번의 에피소드에서 더 많은 정보를 전파하고, 더 멀리 있는 상태의 가치를 더 정확하게 추정할 수 있음을 확인했다. 실제 강화학습 시스템을 구현할 때는 편향-분산 트레이드오프, 계산 복잡성, 메모리 요구사항 등을 고려하여 적절한 n값을 선택하는 것이 중요하다.
|인증|
-------
패스트캠퍼스 링크