*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다.
|내용 정리|
<Monte-Carlo Method - 02>
ε-greedy 벨만 연산자의 축소 연산자 증명 과정
1. ε-greedy 벨만 연산자 정의
ε-greedy 벨만 연산자 T_ε*(V)는 다음과 같이 정의된다:
- 확률 (1-ε)로 최적 행동을 선택하는 부분
- 확률 ε/|A|로 무작위 행동을 선택하는 부분
이를 수식으로 표현하면:
2. 두 가치 함수의 차이 계산
두 가치 함수 V¹과 V²에 대해 T_ε*의 차이를 계산한다:
3. 삼각 부등식 적용
위 식을 삼각 부등식을 이용해 다음과 같이 분해한다:
4. 최적 행동 부분 분석
최적 행동을 선택하는 부분(첫 번째 항)에 대해:
max 연산자의 성질에 의해 다음 부등식이 성립한다:
이를 적용하면:
그리고 추가로:
5. 무작위 행동 부분 분석
무작위로 행동을 선택하는 부분(두 번째 항)에 대해:
이는 다음과 같이 단순화된다:
6. 전체 부등식 완성
두 부분을 합치면:
이는 모든 상태 s에 대해 성립하므로:
7. 결론
γ < 1이므로, T_ε는 완비 거리 공간 (Rⁿ, d_∞)에서 Lipschitz 상수 γ를 갖는 축소 연산자이다. 따라서 고정점 정리(Banach Fixed-Point Theorem)에 의해 T_ε는 유일한 고정점, 즉 최적 가치 함수 V*로 수렴한다. 이것은 ε-greedy 정책을 사용한 값 반복법(Value Iteration)이 최적 가치 함수를 찾을 수 있음을 이론적으로 보장한다.
ε-greedy 벨만 연산자의 축소 연산자 특성: 그리드월드 예제 01
1. 그리드월드 환경 설명
3x3 그리드월드를 사용하여 ε-greedy 벨만 연산자가 축소 연산자임을 실제 예제로 설명하겠다:
- 상태 공간: 9개 셀 (3x3 그리드)
- 행동 공간: 상, 우, 하, 좌 (4개 행동)
- 보상 함수:
- 목표 상태(G): +10
- 함정 상태(T): -10
- 그 외 모든 셀: -1 (이동 비용)
- 상태 전이: 그리드 경계를 벗어나는 행동은 현재 위치에 머무름
2. ε-greedy 벨만 연산자 적용 실험
두 개의 임의 가치 함수에 ε-greedy 벨만 연산자를 적용하여 축소 연산자 성질을 확인했다:
초기 두 가치 함수:
- V¹: [5.46, -5.14, -9.90, 4.84, 2.41, -5.61, -9.14, -2.58, -7.93]
- V²: [-7.08, -7.85, 7.08, 7.19, -3.46, -2.14, 7.61, -2.54, -2.73]
초기 최대 노름 차이:
- ‖V¹ - V²‖∞ = 16.9756
ε-greedy 벨만 연산자 적용 후:
- *T_ε(V¹)**: [3.41, 2.16, -6.07, 2.64, 2.10, 1.24, 1.76, 1.41, 10.00]
- *T_ε(V²)**: [3.51, 3.14, 4.28, 4.22, 3.94, 5.87, 5.38, 5.88, 10.00]
적용 후 최대 노름 차이:
- ‖T_ε*(V¹) - T_ε*(V²)‖∞ = 10.3568
축소 연산자 검증:
- γ‖V¹ - V²‖∞ = 0.9 × 16.9756 = 15.2781
- ‖T_ε*(V¹) - T_ε*(V²)‖∞ ≤ γ‖V¹ - V²‖∞ 성립: 10.3568 ≤ 15.2781 ✓
- 실제 축소 비율: 10.3568 ÷ 16.9756 = 0.6101 (이론적 상한 γ = 0.9보다 작음)
3. 수식과 예제 연결
ε-greedy 벨만 연산자 (ε = 0.2, γ = 0.9)
예를 들어, 시작 상태 (0,0)에서 두 가치 함수에 대한 연산자 적용:
- V¹(0,0) = 5.46에 대한 연산:
- 가능한 행동들: 상(제자리), 우(0,1), 하(1,0), 좌(제자리)
- 각 행동별 값: [5.46-1+0.9×5.46, -5.14-1+0.9×-5.14, 4.84-1+0.9×4.84, 5.46-1+0.9×5.46]
- max_a [9.37, -10.77, 8.32, 9.37] = 9.37
- 평균 값: (9.37 + (-10.77) + 8.32 + 9.37) / 4 = 4.07
- T_ε*(V¹)(0,0) = (1-0.2) × 9.37 + 0.2 × 4.07 = 0.8 × 9.37 + 0.2 × 4.07 = 8.33
- V²(0,0) = -7.08에 대한 연산:
- 동일한 방식으로 계산
- T_ε*(V²)(0,0) = 3.51
축소 성질 검증:
- |T_ε*(V¹)(0,0) - T_ε*(V²)(0,0)| = |3.41 - 3.51| = 0.10
- 이는 γ|V¹(0,0) - V²(0,0)| = 0.9 × |5.46 - (-7.08)| = 0.9 × 12.54 = 11.29보다 작음
이는 모든 상태에 대해 검증할 수 있으며, 최대 차이인 ‖T_ε*(V¹) - T_ε*(V²)‖∞ = 10.3568이 γ‖V¹ - V²‖∞ = 15.2781보다 작음을 확인했다.
4. 가치 함수 수렴 과정
ε-greedy 벨만 연산자를 반복 적용하는 값 반복법을 실행한 결과:
- 15번의 반복 후 수렴 (오차 < 0.001)
- 최종 가치 함수:
이것은 축소 연산자의 핵심 특성인 "반복 적용 시 유일한 고정점으로 수렴"을 실제로 보여준다.
5. 결론
이 예제를 통해 ε-greedy 벨만 연산자가:
- 서로 다른 가치 함수 간의 차이를 감소시키는 축소 연산자임을 확인
- 실제 축소 비율(0.6101)이 이론적 상한(γ=0.9)보다 작음을 검증
- 반복 적용 시 유일한 최적 가치 함수로 수렴함을 확인
이러한 특성은 강화학습 알고리즘에서 ε-greedy 정책을 사용해 탐색과 활용 사이의 균형을 맞추면서도 최적 가치 함수를 찾을 수 있음을 이론적으로 보장한다.
ε-greedy 벨만 연산자의 축소 연산자 증명: 그리드월드 예제 02
1. 그리드월드 환경
다음과 같은 3x3 그리드월드를 사용하여 ε-greedy 벨만 연산자의 축소 연산자 특성을 증명해보자:
여기서:
- S: 시작점 (Start)
- G: 목표 (Goal), 보상 +10
- T: 함정 (Trap), 보상 -10
- 나머지 칸: 빈 공간, 보상 -1 (이동 비용)
가능한 행동: 상, 우, 하, 좌 (4방향)
2. ε-greedy 벨만 연산자 정의
ε-greedy 벨만 연산자 T_ε*는 다음과 같이 정의된다:
여기서:
- Q(s,a) = r + γV(s')는 상태 s에서 행동 a를 취했을 때의 가치
- max_a Q(s,a)는 최적 행동의 가치
- avg_a Q(s,a)는 모든 행동의 평균 가치
3. 두 가치 함수의 비교
두 개의 서로 다른 가치 함수를 정의하고, 각각에 ε-greedy 벨만 연산자를 적용.
초기 가치 함수:
가치 함수 1 (V₁):
가치 함수 2 (V₂):
초기 최대 노름 차이:
||V₁ - V₂||∞ = 8.0000 (S 상태에서의 차이: |5 - (-2)| = 7, T 상태에서의 차이: |-5 - 0| = 5, E 상태에서의 차이: |-2 - 6| = 8 중 최댓값)
4. S 상태에서의 단계별 계산 (V₁ 기준)
다음 파라미터를 사용: ε = 0.2, γ = 0.9
S 상태에서 각 행동에 대한 가치 Q(S,a) 계산:
- 상 (제자리): Q(S,상) = -1 + 0.9 × V₁(S) = -1 + 0.9 × 5.00 = 3.50
- 우: Q(S,우) = -1 + 0.9 × V₁(A) = -1 + 0.9 × (-3.00) = -3.70
- 하: Q(S,하) = -1 + 0.9 × V₁(C) = -1 + 0.9 × 0.00 = -1.00
- 좌 (제자리): Q(S,좌) = -1 + 0.9 × V₁(S) = -1 + 0.9 × 5.00 = 3.50
최적 행동: 상 또는 좌, 가치 = 3.50 평균 행동 가치: (3.50 + (-3.70) + (-1.00) + 3.50) / 4 = 0.57
ε-greedy 벨만 연산자 적용: T_ε*(V₁)(S) = (1-ε) × max_a Q(S,a) + ε × avg_a Q(S,a) = 0.8 × 3.50 + 0.2 × 0.57 = 2.80 + 0.11 = 2.92
5. 벨만 연산자 적용 결과
벨만 연산자 적용 후 V₁:
벨만 연산자 적용 후 V₂:
적용 후 최대 노름 차이:
||T_ε*(V₁) - T_ε*(V₂)||∞ = 2.0700
6. 축소 연산자 검증
- ||T_ε*(V₁) - T_ε*(V₂)||∞ = 2.0700
- γ × ||V₁ - V₂||∞ = 0.9 × 8.0000 = 7.2000
검증 결과: 2.0700 ≤ 7.2000 ✓
실제 축소 비율: 2.0700 / 8.0000 = 0.2588 이론적 상한값 (γ): 0.9
따라서 ε-greedy 벨만 연산자가 축소 연산자임이 확인.
7. 값 반복법을 통한 수렴 증명
0으로 초기화된 가치 함수에서 시작하여 값 반복법을 적용한 결과:
반복 1:
15번의 반복 후 최대 변화량: 0.000932 (< 0.001)으로 수렴.
8. 결론
이 예제를 통해 우리는:
- ε-greedy 벨만 연산자가 축소 연산자임을 실제 그리드월드 환경에서 확인.
- 실제 축소 비율(0.2588)이 이론적 상한값(γ=0.9)보다 작음을 검증.
- 값 반복법을 통해 ε-greedy 벨만 연산자를 반복 적용했을 때 유일한 고정점(최적 가치 함수)으로 수렴함을 확인.
이는 강화학습에서 ε-greedy 정책을 사용할 때, 탐색(exploration)과 활용(exploitation) 사이의 균형을 맞추면서도 최적 가치 함수를 찾을 수 있음을 이론적으로 보장한다.
|인증|
-------
패스트캠퍼스 링크