*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다.
|내용 정리|
<Value Iteration: convergence of value iteration>
Value Iteration의 주요 공식
- 는 상태 s에서 k+1 반복에서의 가치 함수
- 는 기대 가치를 최대화하는 행동을 찾는다는 의미
- 는 상태 s에서 행동 a를 취했을 때 상태 s'로 전이될 확률
- 은 즉각적인 보상
- 는 할인 인자
- 는 이전 반복에서의 상태 s'에 대한 가치 함수
간단한 3×3 그리드 월드 예제로 설명:
- 에이전트는 상, 하, 좌, 우 네 방향으로 이동 가능
- 에이전트가 벽에 부딪히면 제자리에 정지
- 목표 상태(오른쪽 하단 모서리)에는 +1 보상
- 위험 상태(중앙 오른쪽)에는 -1 보상
- 다른 모든 전이는 0의 보상
- 할인 인자 γ = 0.9
특정 상태에 대한 방정식에 실제 값을 대입해 보자:
상태 s = (1,1)(중앙 셀)에 대해:
- 행동 a = "오른쪽"
- p((1,2)|(1,1), 오른쪽) = 0.8 (80%의 확률로 오른쪽으로 이동)
- p((1,1)|(1,1), 오른쪽) = 0.2 (미끄러운 바닥으로 인해 20%의 확률로 제자리에 머무름)
- 현재 값들을 가정: V_k((1,1)) = 0.5, V_k((1,2)) = 0.8
행동 "오른쪽"에 대한 V_{k+1}(1,1) 계산:
- Vk+1(1,1))
- = 0.8*0.72+0.2*0.45
상태 (1,1)에서 가능한 모든 행동(상, 하, 좌, 우)에 대해 이를 계산하고 최대값을 V_{k+1}(1,1)의 새로운 값으로 취하며 Value Iteration 알고리즘은 V_{k+1}과 V_k 사이의 차이가 어떤 임계값보다 작아질 때까지, 즉 최적 가치 함수로의 수렴을 나타낼 때까지 모든 상태에 대해 이 과정을 반복한다.
수축 매핑 정리(Contraction Mapping Theorem)
수축 매핑 정리는 완전 거리 공간(complete metric space)에서 수축 매핑(contraction mapping)이 유일한 부동점(fixed point)을 가진다는 것을 보장하는 중요한 수학적 정리이다.
1. Value Iteration
- 이 식은 Value Iteration의 핵심 반복 과정을 나타낸다.
- 는 k번째 반복에서의 가치 함수이다.
- 는 Bellman 최적 연산자로, 현재 가치 함수 에 적용하여 다음 가치 함수을 계산한다.
- 은 가치 함수가 n차원 실수 벡터임을 의미하며, 여기서 n은 상태 공간의 크기이다.
2. metric space 에 대해 는 contraction mapping.
- Bellman 최적 연산자 가 완전 거리 공간 에서 수축 매핑이다.
- 완전 거리 공간은 모든 코시 수열이 수렴하는 공간이다.
- 는 무한 노름에 기반한 거리 함수이다.
3. 무한 노름을 사용한 거리 함수 의 정의
수축 매핑 정리 적용 과정
- 거리 공간 설정
- 가치 함수들의 집합을 공간으로 본다.
- 두 가치 함수 간의 거리를 측정하는 방법으로 무한 노름을 사용한다.
- 이렇게 형성된 는 완전 거리 공간이다.
- Bellman 최적 연산자의 특성 분석
- Bellman 최적 연산자 가 이 공간에서 어떻게 작용하는지 분석한다.
- 두 가치 함수 와 V2에 를 적용한 결과의 차이를 검토한다.
- 수축 매핑 특성 증명
- 에 대한 최적 행동 를 고정하고, 이를 사용하여 계산한다.
- 동일한 행동에 대해 두 가치 함수의 차이를 분석한다.
- 할인 인자 와 전이 확률 의 특성을 활용한다.
- 확률의 합이 1임을 이용하여, 차이의 상한을 도출한다.
- 수축 증명의 완성
- 최종적으로 를 보인다.
- 여기서 이므로, 는 수축 매핑이다.
|인증|
-------
패스트캠퍼스 링크