*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다.
|내용 정리|
<Value Iteration: convergence of value iteration 2>
28일차에 이어서 수식을 정리한다
1. 첫 번째 수식
1. 부등식
- 의미: T∗(V′(s))의 값이 하한 Ci와 상한 T∗(V′(s) 사이에 있음
- 용도: T∗연산 결과의 범위를 제한하는 보조 정리
2. 거리 비교
- 의미: 첫 번째 부등식: 자기 자신과의 차이는 Ci와의 차이보다 작음 (의미상 중복 또는 오타). 두 번째 부등식: γ∥V′−V2∥∞로 상한 설정.
- 핵심: 의 출력 차이가 할인 계수 γ로 축소됨을 보임.
3. 최대 기대값 차이:
2. 두 번째 수식
1. 최적 행동 정의
- 의미: v2를 기반으로 한 최적 행동 amax2 선택
2. Bellman 연산자와의 관계
- 의미: 특정 행동 amax2의 기대값이 T∗ 연산 결과보다 작거나 같음
3. 축소 성질 증명
- 의미: 상태 간 T∗ 출력 차이가 γ로 상한 제한됨.
3. 세 번째 수식
1. Bellman 연산자 차이
- 의미: T∗ 적용 후 차이가 할인된 가치 함수 차이보다 작음
2. 무한대 노름 도출
- 의미: 최종적으로 T가 -축소 매핑임을 보임
4. 네 번째 수식
1. 축소 매핑 정리 적용
- 의미: (또는 T∗)가 -축소 매핑임을 공식화
2. 부등식 확장:
- 의미: 모든 상태에서 최대 차이가 γ배 감소.
5. 결론
- 목적: Value Iteration의 수렴성 보장.
- 핵심 단계:
- T∗ 또는 Γ∗가 -축소임을 보임.
- 무한대 노름 을 사용해 차이를 측정.
- 할인 계수 γ가 오차를 기하급수적으로 감소시킴을 확인.
- 결론:
모든 수식은 Bellman 연산자의 축소 성질을 증명하여, Value Iteration이 최적 가치 함수 V∗로 수렴함을 보장.
기본 부등식 (C_i ≤ T*(V'(s)) ≤ T*(V'(s)))의 인자들
- C_i: 가치 반복(value iteration) 알고리즘에서 반복 i에서의 하한값. 이는 벨만 최적성 방정식의 수렴 과정에서 나타나는 중간값으로, 현재 반복에서의 최소 가치 추정치를 의미.
- T*: 최적 벨만 연산자(Optimal Bellman Operator)로, 가치 함수를 새로운 가치 함수로 매핑하는 연산자. 이 연산자는 현재 가치 함수를 받아 한 단계 업데이트된 가치 함수를 반환.
- V'(s): 상태 s에서의 가치 함수. 특정 상태에서 시작하여 최적 정책을 따를 때 얻을 수 있는 기대 누적 보상의 값.
수식에 대한 구조도
- 기본 부등식: 가치 함수에 대한 기본적인 부등식 관계를 보여준다. (Ci ≤ T*(V'(s)) ≤ T*(V'(s)))
- 거리 비교: 서로 다른 가치 함수에 대한 벨만 연산자의 결과 간 거리 관계를 보여준다.
- 최대 기대값 차이: 서로 다른 정책에 대한 기대 보상의 차이를 표현한다.
- 최적 행동 정의: v² 가치 함수를 기반으로 한 최적 행동(a²_max)의 정의를 보여준다.
- Bellman 연산자와의 관계: 최적 행동의 기대값과 벨만 연산자 결과의 관계를 보여준다.
- 축소 성질 증명: 벨만 연산자의 축소 성질(contraction property)에 대한 수학적 증명을 나타낸다.
- 무한대 노름 도출: 최종적으로 무한대 노름(infinity norm)을 사용한 부등식으로 정리된다.
수식들의 핵심 의미
- 기본 부등식: 현재 계산된 가치의 최소값은 최적 전략의 실제 가치보다 작거나 같습니다. 예를 들어 체스에서 현재 예측한 승률이 실제 최적 전략의 승률보다 낮거나 같다는 것을 보장합니다.
- 거리 비교: 서로 다른 가치 함수에 대한 벨만 연산 결과의 차이는 할인 인자를 곱한 원래 가치 함수들 간의 최대 차이보다 작습니다. 이는 벨만 연산이 반복될수록 가치 함수가 수렴함을 보여줍니다.
- 최적 행동 정의: 최적 행동은 현재 상태에서 취할 수 있는 모든 행동 중 기대 보상(현재 보상 + 할인된 미래 보상)이 가장 큰 행동입니다.
- 축소 성질: 벨만 연산자는 "축소 맵핑"으로, 반복 적용할수록 어떤 가치 함수든 최적 가치 함수로 수렴하게 됩니다. 이는 강화학습 알고리즘의 이론적 기반이 됩니다.
구조도에 추가된 기타 주요 용어들
- γ(감마): 할인 인자(discount factor)로, 미래 보상의 중요도를 조절. 0과 1 사이의 값을 가지며, 값이 클수록 미래 보상을 더 중요하게 고려.
- s, s': 환경의 상태(state)와 다음 상태를 표시.
- a: 에이전트가 취할 수 있는 행동(action).
- p(s'|s,a): 상태 전이 확률로, 현재 상태 s에서 행동 a를 취했을 때 다음 상태가 s'가 될 확률.
- r: 에이전트가 행동을 취한 후 받는 보상(reward).
예제로 보는 수식
1. 기본 부등식
- 원래 수식:
```
C_i ≤ T*(V'(s)) ≤ T*(V'(s))
```
- 직관적 표현:
```
현재_반복의_최소값 ≤ 최적_벨만_연산(가치함수) ≤ 최적_벨만_연산(가치함수)
```
- 실제 예시:
게임에서 특정 상태(예: 체스판 위치)에 대해 현재까지 계산된 최소 가치(승리 가능성)는 최적의 행동을 했을 때의 실제 가치보다 작거나 같다.
##
2. 거리 비교
원래 수식:
```
|T*(V'(s)) - T*(V'(s))| ≤ |C_i - T*(V'(s))| ≤ γ||V' - V²||∞
```
직관적 표현:
```
|최적_벨만_연산(가치함수A) - 최적_벨만_연산(가치함수B)| ≤ |현재_반복의_최소값 - 최적_벨만_연산(가치함수)| ≤ 할인인자 × 두_가치함수의_최대_차이
```
실제 예시:
두 다른 전략에 대한 가치 평가의 차이는 현재 추정치와 최적 추정치의 차이보다 작으며, 이는 결국 할인 인자를 곱한 원래 가치함수 차이의 최댓값보다 작다.
##
3. 최대 기대값 차이
- 원래 수식:
```
max_a ∑_s' P(s'|s,a)[r + γV'(s')] - max_a ∑_s' P(s'|s,a)[r + γV'(s')]
```
- 직관적 표현:
```
전략A의_최대_기대_보상 - 전략B의_최대_기대_보상
```
- 실제 예시:
체스에서 현재 위치에서 최적의 행동(예: 퀸 이동)을 선택했을 때 얻는 기대 보상과 다른 행동(예: 폰 이동)을 선택했을 때 얻는 기대 보상의 차이.
##
4. 최적 행동 정의
- 원래 수식:
```
a²_max = arg max_a ∑_s' p(s'|s,a)[r + γv²(s')]
```
- 직관적 표현:
```
최적_행동 = 가장_높은_기대_보상을_주는_행동
```
- 실제 예시:
로봇이 미로에서 현재 위치에서 취할 수 있는 모든 행동(전진, 좌회전, 우회전) 중에서 미래 보상을 포함한 총 기대 보상이 가장 높은 행동을 선택.
##
5. Bellman 연산자와의 관계
- 원래 수식:
```
∑_s' p(s'|s,a²_max)[r + γv²(s')] ≤ T*(v²(s))
```
- 직관적 표현:
```
최적_행동의_기대_보상 ≤ 최적_벨만_연산_결과
```
- 실제 예시:
게임에서 현재 알고 있는 최선의 전략에 따라 행동했을 때 얻는 기대 보상은 실제 최적의 전략을 따랐을 때 얻을 수 있는 이론적 최대 보상보다 작거나 같다.
##
6. 축소 성질 증명
- 원래 수식:
```
|T*(v²(s)) - T*(v²(s'))| ≤ γ|∑_s' p(s'|s,a²_max)[v²(s') - v(s')]|
```
- 직관적 표현:
```
|두_상태의_최적값_차이| ≤ 할인인자 × |두_가치함수_차이의_기대값|
```
- 실제 예시:
자율주행 차량에서 두 다른 도로 상태에 대한 최적 행동 가치의 차이는, 할인 인자를 고려한 미래 상태들의 가치 차이의 기대값보다 크지 않다.
##
7. 무한대 노름 도출
- 원래 수식:
```
≤ γ max_s' |v'(s') - v²(s')| = γ||v' - v²||∞
```
- 직관적 표현:
```
≤ 할인인자 × 두_가치함수의_최대_차이
```
- 실제 예시:
두 다른 전략 간의 가치 차이는 할인 인자를 고려한 모든 가능한 상태에서의 최대 가치 차이보다 크지 않다. 예를 들어, 두 다른 체스 전략의 가치 차이는 어떤 체스판 상태에서도 원래 전략 가치 차이의 γ(감마)배를 넘지 않는다.
|인증|
-------
패스트캠퍼스 링크