*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다.
|내용 정리|
<n-step TD 학습 알고리즘 2>
n-step TD 업데이트 공식
- 기본 업데이트 (t ≥ n일 때)
V(s_{t-n}) = V(s_{t-n}) + α[∑_{k=1}^{n} γ^{k-1}r_{t-n+k} + γ^n V(s_t) - V(s_{t-n})]이 공식은 다음과 같은 의미를 가진다:
- V(s_{t-n}): n 스텝 이전 상태의 가치 함수를 업데이트
- α: 학습률(learning rate)
- 대괄호 안의 표현식: TD 오차
- ∑_{k=1}^{n} γ^{k-1}r_{t-n+k}: n개의 할인된 보상 합계
- γ^n V(s_t): 현재 상태의 할인된 가치 추정값
- -V(s_{t-n}): 이전 상태의 가치 추정값
- 에피소드 종료 시 처리 (done일 때)
k_{min} = min(t, n-1)
for i ∈ 1 : k_{min}
V(s_{t-i}) = V(s_{t-i}) + α[∑_{k=1}^{i} γ^{k-1}r_{t-i+k} + γ^n V(s_t) - V(s_{t-i})]
V(s_t) = 0 (종료 상태의 가치는 0)이 부분은 에피소드가 종료되었을 때 남아있는 상태들의 가치를 업데이트하는 방법이다:
- k_{min}: 업데이트할 수 있는 최대 스텝 수 결정 (t와 n-1 중 작은 값)
- 순환문을 통해 최근 k_{min}개의 상태 가치를 업데이트
- 마지막으로 종료 상태의 가치를 0으로 설정
에피소드 기반 n-step TD 알고리즘
- 완전한 에피소드(episode) 기반 n-step TD 알고리즘이다
Input a policy to be evaluated, π
Initialize α > 0 and V(s) for all s ∈ S
While True
Generate an episode e = (s_0, a_0, r_1, s_1, ..., s_{T-1}, a_{T-1}, r_T, s_T) using π
For t ∈ 0 : T-1
k_{min} = min(n, T-t)
δ_t^{k_{min}} = ∑_{k=1}^{k_{min}} γ^{k-1}r_{t+k} + γ^{k_{min}}V(s_{t+k_{min}}) - V(s_t)
V(s_t) = V(s_t) + αδ_t^{k_{min}}이 알고리즘의 주요 특징:
- 정책 π를 사용하여 완전한 에피소드를 생성
- 에피소드의 각 타임스텝 t에 대해:
- k_{min}: 현재 위치에서 가능한 최대 스텝 수 계산 (n과 남은 에피소드 길이 중 작은 값)
- δ_t^{k_{min}}: n-step TD 오차 계산
- 현재 상태의 가치 함수 업데이트
여기서의 접근 방식은 에피소드 전체를 생성한 후 처음부터 끝까지 한 번에 업데이트한다는 점이 이전 알고리즘과 다르다.
이미지 3: n-step TD의 확장 및 이점
세 번째 이미지는 n-step TD 학습의 확장과 이점에 대해 설명한다:
n-step TD에서 n이 크면 수렴 속도가 빠르다는 주장과 단점
- 있음, 학습동안 value 값이 더 많이 됨 (variance가 큼)
- Sample이 많다면 이 문제가 완화됨 (큰 수의 법칙)
다양한 n을 함께 사용하는 방법
G_t^{(n)} = ∑_{k=1}^{n} γ^{k-1}r_{t+k} + γ^n V(s_{t+n})이라 할 때, 예를 들면:
V(s_t) = Ê[0.3G_t^{(3)} + 0.3G_t^{(5)} + 0.4G_t^{(8)}]여기서는 서로 다른 n 값(3, 5, 8)의 반환값을 가중 평균하는 방식을 보여준다:
- 3-step TD의 반환값에 0.3 가중치
- 5-step TD의 반환값에 0.3 가중치
- 8-step TD의 반환값에 0.4 가중치
이와 관련된 설명:
- 가능! 다음 chapter에서 일반적으로 많이 쓰는 방법을 배움
- 단, 섞어서 쓸 때 각 step에 대한 weight는 양수이며, 합이 1이 되어야 함
n-step TD 학습의 주요 특징 및 고려사항
- n 값의 선택과 트레이드오프:
- n이 작을수록: 낮은 분산(variance)이지만 높은 편향(bias)
- n이 클수록: 낮은 편향이지만 높은 분산
- n=1: 일반적인 TD(0) 학습 (낮은 분산, 높은 편향)
- n=∞: 몬테카를로 방법 (높은 분산, 낮은 편향)
- 다양한 n 사용의 이점:
- 다양한 n 값의 추정치를 혼합하면 편향과 분산 사이의 더 나은 균형을 이룰 수 있음
- 예제에서 본 것처럼 3-step, 5-step, 8-step의 가중 평균을 사용
- 가중치의 합은 1이어야 하고, 모든 가중치는 양수여야 함
- 실용적 고려사항:
- 메모리 요구 사항: n이 클수록 더 많은 경험을 저장해야 함
- 계산 복잡성: n이 클수록 더 많은 계산이 필요함
- 샘플 효율성: n이 크면 샘플 효율성이 더 높을 수 있음
- 온라인 vs 오프라인 학습:
- 첫 번째 알고리즘: 온라인 학습 방식 (TD 오차를 즉시 계산하고 업데이트)
- 두 번째 알고리즘: 오프라인/에피소드 단위 학습 방식 (에피소드 완료 후 일괄 업데이트)
n-step TD 학습은 TD 학습과 몬테카를로 방법 사이의 중간 지점을 제공하며, 적절한 n 값 선택 또는 다양한 n 값의 혼합을 통해 학습 성능을 최적화할 수 있다.
그리드 월드로 보는 수식 정의
다음과 같은 4x4 그리드 월드를 가정한다:
+---+---+---+---+
| S | O | O | O |
+---+---+---+---+
| O | O | X | O |
+---+---+---+---+
| O | O | O | O |
+---+---+---+---+
| O | O | O | G |
+---+---+---+---+여기서:
- S: 시작 위치 (0,0)
- G: 목표 위치 (3,3), 보상 +1
- X: 장애물 (1,2), 진입 불가
- O: 빈 공간, 보상 0
n-step TD 수식 적용 (n=3 예시)
1. 초기화
- 모든 상태 s에 대해 V(s) = 0으로 초기화
- 학습률 α = 0.1
- 할인율 γ = 0.9
2. 에피소드 생성
예를 들어, 다음과 같은 에피소드가 생성되었다고 가정합니다:
- s₀ = (0,0), a₀ = 오른쪽, r₁ = 0, s₁ = (0,1)
- s₁ = (0,1), a₁ = 아래쪽, r₂ = 0, s₂ = (1,1)
- s₂ = (1,1), a₂ = 오른쪽, r₃ = 0, s₃ = (1,3) (장애물 우회)
- s₃ = (1,3), a₃ = 아래쪽, r₄ = 0, s₄ = (2,3)
- s₄ = (2,3), a₄ = 아래쪽, r₅ = 1, s₅ = (3,3) (목표 도달)
3. 3-step TD 업데이트 수식 적용
n=3일 때의 업데이트 공식:
예제 경로에 이 공식을 적용해보자.
첫 번째 가능한 업데이트 (t=3)
상태 s₀에 대해:
수치를 대입하면:
두 번째 업데이트 (t=4)
상태 s₁에 대해:
수치를 대입하면:
세 번째 업데이트 (t=5)
상태 s₂에 대해:
수치를 대입하면:
목표 상태의 가치 V(3,3)은 일반적으로 0으로 설정된다 (종료 상태).
4. 에피소드 종료 후 처리
에피소드가 종료되면 (t=5, done=True), 아직 업데이트되지 않은 상태들을 처리한다:
따라서 i=1,2에 대해:
i=1 (상태 s₄)
i=2 (상태 s₃)
5. 다양한 n 값을 사용한 혼합 방식
이미지 3에서 본 것처럼, 다양한 n 값의 반환값을 혼합하여 사용할 수 있다:
예를 들어, n=3, n=5, n=8을 혼합하면:
위의 예제에서 t=0일 때 이 식을 적용해보면:
- G₀^(3) = r₁ + γr₂ + γ²r₃ + γ³V(s₃) = 0 + 0 + 0 + 0.9³×0 = 0
- G₀^(5) (에피소드 길이가 5이므로) = r₁ + γr₂ + γ²r₃ + γ³r₄ + γ⁴r₅ + γ⁵V(s₅) = 0 + 0 + 0 + 0 + 0.9⁴×1 + 0 = 0.9⁴ = 0.6561
- G₀^(8)는 에피소드 길이(5)를 초과하므로, G₀^(5)와 동일합니다 = 0.6561
따라서:
수렴 특성
- n이 큰 경우: 수렴 속도가 빠르지만 분산(variance)이 큼
- 샘플이 많을수록: 큰 수의 법칙에 의해 분산 문제가 완화됨
- 혼합 접근법: 여러 n 값을 조합하여 편향(bias)과 분산(variance) 사이의 균형을 이룸
이렇게 n-step TD 학습은 1-step TD 학습과 몬테카를로 방법 사이의 유연한 중간점을 제공하며, 문제와 환경에 맞게 n 값을 조정하거나 여러 n 값을 혼합하여 성능을 최적화할 수 있다.
|인증|
-------
패스트캠퍼스 링크