*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다.
|내용 정리|
<Temporal Difference (TD) Learning>
- TD 학습은 Dynamic Programming (DP)과 Monte-Carlo (MC) 방법을 결합한 방식이다.
- DP의 "모델 기반 계획"과 MC의 "샘플링 기반 학습"의 장점을 통합하여, 부트스트래핑과 샘플 경험을 모두 활용한다.
Dynamic Programming (DP)의 Policy Evaluation
- DP는 환경의 완전한 모델 (상태 전이 확률 p(s′∣s,a)과 보상 함수 R(s,a,s′))을 필요
- 다음 상태의 가치 함수 Vk+1(s)를 계산할 때, 모든 가능한 상태와 행동에 대해 기댓값을 계산
- 단점: 계산 비용이 높고, 환경 모델을 미리 알아야 한다.
Monte-Carlo (MC) Method
- MC는 에피소드의 샘플 경험 (예: 실제 게임 플레이)으로부터 평균 리턴 Gt를 계산
- 다음 상태의 가치 함수 Vk+1(s)를 계산할 때, 모든 가능한 상태와 행동에 대해 기댓값을 계산
- 특징:
- 모델 불필요 (모델-프리).
- 에피소드가 끝나야 학습 가능 (고정된 스텝 크기 없음).
- 단점: 분산이 크고, 에피소드 완료를 기다려야 한다.
TD Learning의 역할
- TD 학습은 DP의 부트스트래핑 (예: V(s)추정 시 V(s′) 활용)과 MC의 샘플링을 결합
- : 학습률, : TD 타겟
- 장점: 에피소드 종료를 기다리지 않으며, 분산을 줄이면서 모델-프리로 학습 가능.
TD Prediction의 기본 개념
- TD 학습은 DP의 부트스트래핑과 MC의 샘플링을 결합.
- 목표: 현재 상태의 가치 V(s)를 다음 상태의 샘플 보상 r과 가치 V(s′)로 업데이트.
- : 할인 계수, E^: 샘플 평균.
TD Error (Temporal Difference Error)
- 정의: 예측값 V(s)와 목표값 r+γV(s′)의 차이.
- 의미:
- δ>0: 현재 가치가 과소평가됨.
- δ<0: 현재 가치가 과대평가됨.
TD 업데이트 규칙
- 정점진적 업데이트: 학습률 α를 사용하여 V(s)를 조정.
- 특징:
- MC와 달리 에피소드 종료를 기다리지 않음.
- DP와 달리 모델 불필요 (샘플 경험만 사용).
TD의 수렴 조건
- 기대값 조건: 최적 가치 함수 Vπ에서 TD Error의 기대값은 0.
- 유도 과정:
TD의 최적화 목표
- MSE 최소화: TD Error의 분산을 최소화하는 V(s)는 DP의 Policy Evaluation과 동일.
- 결론: 충분한 샘플이 주어지면 TD는 DP와 동일한 가치 함수에 수렴
알고리즘: TD Prediction for Policy Evaluation
입력: 평가할 정책 π, 학습률 α, 초기 가치 V(s)
과정:
- 에피소드마다 상태 s초기화.
- 각 스텝에서:
- 행동 a∼π(⋅∣s) 선택.
- 보상 r과 다음 상태 s′ 관측.
- TD Error 계산 후 V(s) 업데이트:
- 종료 상태에서 V(s′)=0 설정.
TD의 특성 요약
DP vs. MC vs. TD 비교
그리드 예제로 보는 DP, MX, TD
간단한 그리드월드 환경 설정
다음과 같은 4x4 그리드월드 환경을 고려해 본다:
여기서:
- S: 시작 지점 (0,0)
- G: 목표 지점 (3,3), 보상 +1
- 그 외 지점: 보상 0
- 행동: 상(↑), 하(↓), 좌(←), 우(→)
- 감마(γ): 0.9 (할인 계수)
- 학습률(α): 0.1 (TD 학습에서 사용)
1. Dynamic Programming (DP) 예제
DP는 환경의 완전한 모델(상태 전이 확률과 보상)을 활용하여 가치 함수를 계산한다.
상태 가치 함수 계산 (Value Iteration)
초기 상태 가치: 모든 상태의 가치를 0으로 초기화
첫 번째 반복:
두 번째 반복 (몇 가지 상태만 보여줌):
수렴 후:
샘플 계산 (예: 상태 (2,2)의 가치 계산)
V(2,2)를 계산하기 위한 벨만 방정식:
V(2,2) = max_a [ Σ p(s'|s,a) * (R(s,a,s') + γ * V(s')) ]
상태 (2,2)에서 오른쪽으로 이동하는 경우:
- 100% 확률로 (2,3)로 이동
- V(2,2) = 1.0 * (0 + 0.9 * 1.0) = 0.9
상태 (2,2)에서 다른 방향(위)으로 이동하는 경우:
- 100% 확률로 (1,2)로 이동
- V(2,2) = 1.0 * (0 + 0.9 * 0.838) = 0.754
최종적으로 가장 큰 값인 0.9를 선택하여 V(2,2) = 0.9
2. Monte Carlo (MC) 예제
MC는 에피소드의 실제 경험을 통해 가치 함수를 추정한다.
에피소드 예시 (상태, 행동, 보상 시퀀스)
에피소드 1:
에피소드 2:
반환값 계산 (Return)
에피소드 1에서 S₄: (2,2)의 반환값: G₄ = R₅ + γR₆ + γ²R₇ = 0 + 0.90 + 0.9²1 = 0.81
에피소드 2에서 S₂: (2,0)의 반환값: G₂ = R₃ + γR₄ + γ²R₅ + γ³R₆ + γ⁴R₇ = 0 + 0.90 + 0.9²0 + 0.9³0 + 0.9⁴1 = 0.6561
여러 에피소드 후 가치 함수 추정
10개 에피소드 후:
3. Temporal Difference (TD) 예제
TD는 부트스트래핑(현재 추정치 사용)과 실제 경험을 결합하여 가치 함수를 업데이트한다.
TD(0) 학습 예시
초기 가치 함수 (모두 0으로 초기화):
첫 번째 에피소드에서 한 단계 이동 후 업데이트 (S₀: (0,0) → A₀: → → S₁: (0,1), R₁: 0):
TD 오류 계산: δ = R₁ + γV(S₁) - V(S₀) = 0 + 0.9*0 - 0 = 0
V(S₀) ← V(S₀) + αδ = 0 + 0.1*0 = 0
더 많은 단계와 에피소드 후: (특정 상태들의 업데이트만 보여줌)
상태 (2,2)에서 (2,3)으로 이동한 후 업데이트:
- V(2,2) = 0.1 (이전 값)
- R = 0
- V(2,3) = 0.3 (이전 값)
- TD 오류: δ = 0 + 0.9*0.3 - 0.1 = 0.17
- V(2,2) ← 0.1 + 0.1*0.17 = 0.117
여러 에피소드 후 가치 함수:
알고리즘 비교 (DP vs. MC vs. TD)
그리드월드 예제에서의 알고리즘 특성 비교
실제 계산 예시: 상태 (1,1)의 가치 추정
DP 계산: V(1,1) = max_a [Σ p(s'|s,a)(R + γV(s'))] = max { 0.90.678 (위로 이동), 0.90.754 (아래로 이동), 0.90.678 (왼쪽으로 이동), 0.90.754 (오른쪽으로 이동) } = 0.9*0.754 = 0.679
MC 계산 (여러 에피소드의 평균):
- 에피소드 1: (1,1)에서 종료까지의 할인된 보상 = 0.9⁴*1 = 0.6561
- 에피소드 2: (1,1)에서 종료까지의 할인된 보상 = 0.9³*1 = 0.729
- 평균: (0.6561 + 0.729) / 2 = 0.69255
TD 계산 (한 스텝 업데이트):
- V(1,1) = 0.65 (현재 추정값)
- 행동: 오른쪽으로 이동
- S' = (1,2), R = 0
- V(1,2) = 0.73 (현재 추정값)
- TD 오류: δ = 0 + 0.9*0.73 - 0.65 = 0.007
- V(1,1) ← 0.65 + 0.1*0.007 = 0.6507
세 가지 강화학습 알고리즘(DP, MC, TD)의 수렴 속도
- Y축(로그 스케일): MSE(Mean Squared Error)를 보여준다. 이는 각 알고리즘의 현재 가치 함수가 최종 수렴값(DP의 최종 결과를 기준으로 함)과 얼마나 차이가 나는지를 측정한다. 값이 낮을수록 최종 솔루션에 가깝다는 의미이다.
- X축: 학습 진행도를 나타낸다. 0에서 시작하여 1에 도달할 때 학습이 완료된다.
- 파란색 선(DP): Dynamic Programming은 처음에는 천천히 수렴하다가 학습이 진행될수록 급격하게 수렴하며, 최종적으로 가장 정확한 결과에 도달한다. 그래프에서 볼 수 있듯이 약 0.7 부근에서 학습이 완료된다.
- 녹색 선(MC)과 빨간색 선(TD): Monte Carlo와 TD 학습은 초기에 빠르게 개선되지만, 그 후 수렴 속도가 느려지고 최종적으로 DP만큼 정확한 결과에 도달하지 못한다. 이들은 학습 과정 내내 일정한 오차를 유지한다.
그래프의 핵심:
- DP의 장점: 환경 모델이 완전히 알려진 경우 DP는 결국 가장 정확한 결과를 제공한다.
- MC와 TD의 한계: 이 두 방법은 샘플링 기반이기 때문에, 한정된 에피소드 수(여기서는 1000개)로는 완벽한 수렴에 도달하지 못한다.
- 초기 학습 속도: MC는 초기에 가장 빠르게 개선되지만, 이후에는 TD와 비슷한 수준으로 유지된다.
- 안정성: DP의 오차는 꾸준히 감소하는 반면, MC와 TD는 약간의 변동을 보인다.
DP는 완전한 모델 정보를 활용하므로 결국 최적에 도달하지만, MC와 TD는 제한된 샘플을 사용하므로 일정 수준의 근사에 머무른다. 제한된 에피소드 수와 불완전한 모델 정보로 인해 TD는 DP만큼 정확한 솔루션에 도달하지 못한다. 하지만 TD는 많은 실제 문제에서 모델 정보가 없을 때도 사용할 수 있는 강력한 방법이다.
|인증|
-------
패스트캠퍼스 링크