*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다.
|내용 정리|
<TD Learning의 업데이트>
- TD Learning의 업데이트 수식
- 설명: 이 수식은 Temporal Difference (TD) Learning에서 상태 s의 가치 함수 V(s)를 업데이트하는 방법을 나타낸다. 현재 상태 s에서의 가치 함수는 즉시 보상 r과 다음 상태 의 할인된 가치 γV(St+1)의 기대값으로 추정된다.
- 기호 의미:
- E^: 샘플 평균을 통한 기대값 추정.
- γ: 할인 계수 (미래 보상의 현재 가치 반영).
- 무한한 샘플에서의 기대값
- 설명: 샘플이 무한히 많을 때, 샘플 평균은 실제 기대값으로 수렴한다. 이는 정책 π하에서 상태 전이 확률 p(s′∣s,a)와 보상 r을 고려한 Bellman 방정식의 형태이다.
- 모든 상태에 대한 벡터 형태의 업데이트
- 설명: 모든 상태 s에 대해 가치 함수를 업데이트하는 과정을 벡터 V로 표현한 것이다. Tπ는 정책 π에 대한 Bellman 연산자로, 현재 가치 벡터 Vk를 입력으로 받아 새로운 가치 벡터 Vk+1를 출력한다.
1. 기호 설명
- V(s) : 상태 s의 가치 함수 (value function)
- E^: 샘플 평균을 통한 기대값 추정
- : 할인 계수 (discount factor) - 미래 보상의 현재 가치 반영 (0~1 사이 값)
- : 보상 (reward)
- : 시간 에서의 상태
- : 다음 상태
- : 상태 에서 행동 를 취했을 때 상태 로 전이할 확률
- : 상태 에서 행동 를 선택할 정책(policy)의 확률
- : 정책 에 대한 Bellman 연산자
- : 번째 반복에서의 가치 함수 추정값
2. 수식의 의미
TD Learning의 업데이트 수식
이 수식은 현재 상태의 가치를 즉각적인 보상과 다음 상태의 추정 가치를 통해 업데이트하는 방법. TD Learning은 실제 경험에서 얻은 샘플을 사용하여 이 업데이트를 수행.
무한한 샘플에서의 기대값
샘플이 무한히 많을 때, 샘플 평균은 실제 기대값으로 수렴. 이는 정책 하에서 상태 전이 확률 와 보상 을 고려한 Bellman 방정식의 형태.
모든 상태에 대한 벡터 형태의 업데이트
모든 상태 에 대해 가치 함수를 업데이트하는 과정을 벡터 로 표현. 는 정책 에 대한 Bellman 연산자로, 현재 가치 벡터 를 입력으로 받아 새로운 가치 벡터 을 출력.
3. 예제
그리드월드 예제로 TD Learning 업데이트를 살펴보자:
- 상태 공간: 2x2 그리드 ()
- 행동 공간: 상, 하, 좌, 우
- 보상: 목표 상태 에 도달하면 +1, 그 외에는 0
- 할인 계수
초기 가치 함수:
수식:
- V(s): 현재 상태 s의 가치 추정값
- r: 즉각적인 보상
- γ: 할인 계수 (미래 가치의 중요도)
- V(s'): 다음 상태 s'의 가치 추정값
- α: 학습률 (새로운 정보를 얼마나 반영할지)
에이전트가 경로 s₁ → s₂ → s₄를 경험했다고 가정:
- s₁에서 s₂로 이동 (보상 r = 0) TD 업데이트:
- 현재 상태 s₁의 가치는 0
- 받은 보상은 0
- 다음 상태 s₂의 가치도 아직 0
- TD 오차 = 0 이므로 업데이트 없음
2. s₂에서 s₄로 이동 (보상 r = +1) TD 업데이트:
- 현재 상태 s₂의 가치는 0
- 받은 보상은 1 (목표 상태 도달)
- 다음 상태 s₄의 가치는 0
- TD 오차 = 1, 따라서 V(s₂)를 0.1로 업데이트
3. 다음 에피소드에서 같은 경로를 다시 경험:
- 이제 s₂의 가치가 0.1로 업데이트됨
- s₁에서는 보상이 없지만(0), s₂로 가면 가치가 있음을 인식
- 0.9(할인 계수) × 0.1(s₂의 가치) = 0.09의 기대 가치
- 학습률 0.1을 적용해 0.009만큼 업데이트
"
이 과정은 "가치의 역전파"를 보여준다. 처음에는 목표 상태(s₄)에 도달해야만 보상을 받지만, 학습이 진행되면서 그 보상의 영향이 이전 상태들(s₂, s₁)로 점차 전파된다. 여러 에피소드를 반복하면, 에이전트는 최종 목표에서 멀리 떨어진 상태에서도 올바른 행동을 선택할 수 있게 된다.
이것이 TD Learning의 핵심이며, 경험을 통해 점진적으로 가치 함수를 개선하는 방식이다.
"
<Contraction Mapping>
1. Contraction Mapping의 정의
- 의미:
- 연산자 Tn이 γ-contraction임을 의미.
- 두 벡터 V1과 V2에 Tn을 적용한 결과의 거리(∥⋅∥∞)가 원래 거리의 γ배 이하로 감소.
- γ가 1보다 작으므로, Tn을 반복 적용하면 Vk가 점점 수렴.
2. Complete Metric Space에서의 Contraction Mapping Theorem
- 공간 설정:
- (Rn,d∞)는 완비 거리 공간(complete metric space)이다.
- d∞(V1,V2)=∥V1−V2∥∞ (최대 놈 기준 거리).
- 모든 코시 수열(Cauchy sequence)이 수렴하는 공간.
- (Rn,d∞)는 완비 거리 공간(complete metric space)이다.
- 고정점 정리(Banach Fixed-Point Theorem):
- 완비 거리 공간에서 정의된 contraction mapping은 유일한 고정점(unique fixed point)을 가지며, 임의의 초기값에서 반복 적용 시 이 고정점으로 수렴한다.
3. Tn의 반복 적용과 수렴 과정
- 초기값 V0에서 시작하여 Tn을 반복 적용:
- 두 초기값 V1,V2에 대한 거리 변화:
- Tn을 n번 반복 적용한 경우:
- γn이 n→∞일 때 0으로 수렴하므로, 두 값의 차이도 0으로 수렴.
- 극한에서의 동일한 고정점 도달:
- 서로 다른 초기값에서 시작해도 동일한 V∗로 수렴.
4. TD Learning과의 연결
- Bellman 연산자 Tπ의 Contraction 성질:
- Tπ도 γ-contraction이므로, 가치 반복(Value Iteration)이 수렴함이 보장.
- RL에서의 의미:
- 정책 평가(Policy Evaluation) 시 Vπ로의 수렴이 보장.
- γ가 클수록(1에 가까울수록) 수렴 속도가 감소.
정리
TD Learning의 업데이트 과정과 Contraction Mapping은 다음과 같이 연결된다:
- 이론적 수렴 보장: TD Learning이 수렴하는 이유는 Bellman 연산자가 contraction mapping이기 때문이다. 반복적으로 적용하면 항상 유일한 해(최적 가치 함수)에 도달한다.
- 수렴 속도: Contraction factor γ(할인 계수)가 작을수록 수렴 속도가 빨라진다. 이는 TD Learning에서 할인 계수가 작을수록 학습이 빨리 진행되는 것과 일치한다.
- 반복적 개선: TD Learning의 업데이트 공식이 실질적으로 Bellman 연산자를 샘플 기반으로 근사하는 방식이다:
|인증|
-------
패스트캠퍼스 링크