*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다.
|내용 정리|
<Monte-Carlo Control>
1. Policy Evaluation
- 현재 정책 π에 대한 가치 함수 V를 계산하여 Vπ로 수렴시킴. Monte-Carlo Prediction을 사용하여 경험을 통해 Vπ를 추정
2. Policy Evaluation
- 계산된 가치 함수 를 기반으로 탐욕적(greedy) 정책으로 개선.
- 최적 정책 π∗과 최적 가치 함수 V∗로 수렴.
3. Monte-Carlo Prediction의 한계와 해결책
- 문제:
경험하지 못한 상태 s또는 상태-행동 쌍 (s,a)에 대한 가치 함수를 계산할 수 없음. - 해결책 1: Exploring Start
모든 (s,a)를 경험할 수 있도록 임의의 상태에서 시작.
모든 (s,a)에 대한 action-value 함수 Q(s,a)를 추정 가능.
단, 환경에서 이 기능이 제공되지 않으면 사용 불가. - 해결책 2: ϵ-soft Policy
(1−ϵ)확률로 정책 π를 따르고, ϵ확률로 무작위 행동 선택.
환경의 특별한 기능이 필요 없지만, 최적 정책을 보장하지는 않음.
4. Monte-Carlo Control 알고리즘
- 초기화:
π(s,a), Q(s,a), 빈 리스트 Returns(s,a)를 모든 s∈S와 a∈A에 대해 설정. - 에피소드 생성:
s0와 a0를 선택하고, 정책 π를 사용해 에피소드 e를 생성. - 가치 함수 업데이트:
각 시간 단계 t에서 반환값 gt를 계산하고 Returns(st,at)에 추가.
Q(st,at)를 Returns(st,at)의 평균으로 업데이트. - 정책 개선:
각 상태 st에서 탐욕적 행동을 선택하도록 정책 π를 업데이트:
5. -soft Policy의 수학적 분석
- ε-soft 정책은 대부분(1-ε)의 확률로 최적 행동을 선택하고, 나머지 ε의 확률로 다른 행동을 탐색
- 기대값 계산: 은 -soft 정책으로, 무작위 행동과 탐욕적 행동을 혼합.
- 주요 용어 및 개념
- π(a∣s): 기존 정책 (현재 행동 선택 확률 분포).
- π′(a∣s): ϵ-greedy로 개선된 새 정책.
- Qπ(s,a): 정책 π하에서의 행동 가치 함수 (Action-Value Function).
- Vπ(s): 정책 π하에서의 상태 가치 함수 (State-Value Function).
- ϵ: 무작위 행동 확률 (탐험을 위한 하이퍼파라미터).
- π′은 -greedy 정책이므로 최적 행동 ()을 확률로 선택.
- 나머지 행동은 각각 ϵ∣A∣확률로 선택.
→ 따라서 다음과 같이 표현:
- 기존 정책 π와의 비교해보면 π는 ϵ-soft 정책이므로, 모든 행동에 최소 ϵ∣A∣확률이 부여됩니다.
- π의 가중평균 Qπ(s,a)는 Vπ(s)와 같습니다:
- 새 정책 π′의 기대값이 Vπ(s)보다 크다는 것을 보이기 위해, 다음 부등식을 유도:
- 여기서 는 π에서 ϵ의 영향을 제거한 재조정된 확률 분포.
- maxaQπ(s,a)가 이 재조정된 분포의 기대값보다 크거나 같음을 이용.
- 위 식을 정리하면:
- 남은 항은 Vπ(s)되며
- 다음이 성립:
→ 즉, π′의 기대 가치가 π의 가치보다 항상 크거나 같다.
5. ϵ-soft Policy 업데이트 공식
- 정책 업데이트: 최적 행동에는 높은 확률을 부여하고, 나머지 행동에는 균일한 작은 확률을 부여.
- 정책 개선 정리 검증:
ϵ-soft 정책이 정책 개선 정리의 조건을 만족함. 따라서 Vπ′(s)가 성립.
종합 설명
- Policy Evaluation과 Improvement:
Monte-Carlo 방법으로 가치 함수를 추정하고, 탐욕적 정책으로 개선하는 과정을 반복. - 탐험 문제 해결:
Exploring Start 또는 -soft 정책을 사용하여 모든 상태-행동 쌍을 경험. - 알고리즘 구현:
에피소드 생성 → 가치 함수 업데이트 → 정책 개선의 단계를 반복. - 수학적 보장:
ϵ-soft 정책은 정책 개선 정리를 만족하여 점진적으로 우수한 정책으로 수렴. - 실용적 적용:
-soft 정책은 환경의 제약 없이 탐험을 유지하며, 실용적으로 널리 사용됨.
ε-greedy 강화학습 접근법의 실제 예시
ε-greedy 정책의 작동 방식을 실제 예시로 설명해 드리겠습니다. 간단한 미로 찾기 문제를 통해 살펴보자.
미로 환경 설정
- 5x5 그리드 미로
- 시작 위치: (0,0) (왼쪽 상단)
- 목표 지점: (4,4) (오른쪽 하단)
- 장애물: (1,2), (2,2), (3,2)에 벽이 있음
- 행동: 상, 하, 좌, 우 이동
- 보상: 목표 지점 도달 +10, 장애물 충돌 -1, 다른 이동 -0.1 (시간 패널티)
ε-greedy 정책의 적용 과정
초기 학습 단계 (에피소드 1)
로봇이 미로를 전혀 모르는 상태에서 시작한다. ε = 0.3 (30% 확률로 무작위 행동)으로 설정한다.
- 상태 (0,0)에서:
- Q((0,0), 모든 행동) = 0 (초기 예측값)
- 모든 행동의 가치가 같으므로, 무작위로 '오른쪽' 선택
- 새 위치: (0,1), 보상: -0.1
- 상태 (0,1)에서:
- 랜덤 넘버 0.41 > ε(0.3) → 활용(exploitation)
- 모든 Q값이 0이므로 임의로 '아래' 선택
- 새 위치: (1,1), 보상: -0.1
- 몇 번의 이동 후 (1,1) → (1,0) → (2,0) → (2,1):
- 상태 (2,1)에서
- 랜덤 넘버 0.18 < ε(0.3) → 탐험(exploration)
- 무작위로 '오른쪽' 선택
- 새 위치: (2,2), 보상: -1 (장애물 충돌)
- 장애물 학습 후:
- Q((2,1), 오른쪽)이 업데이트: ≈ -1
- 다른 행동들의 Q값은 여전히 높음
몇 번의 에피소드 후 (예: 에피소드 10)
- 상태 (2,1)에서:
- Q((2,1), 위) ≈ -0.3
- Q((2,1), 아래) ≈ -0.4
- Q((2,1), 왼쪽) ≈ -0.3
- Q((2,1), 오른쪽) ≈ -0.9
- 랜덤 넘버 0.75 > ε(0.3) → 활용
- max Q값은 '위' 또는 '왼쪽' (동일한 경우 임의 선택)
- '위' 선택, 새 위치: (1,1)
- 때때로 비최적 행동:
- 상태 (3,3)에서
- 최적 행동은 '오른쪽'(Q ≈ 8.1)
- 랜덤 넘버 0.22 < ε(0.3) → 탐험
- 무작위로 '왼쪽' 선택 (비최적 행동)
- 이는 새로운 경로 발견 가능성 유지
많은 에피소드 후 (예: 에피소드 100)
- 상태 (3,3)에서:
- Q((3,3), 위) ≈ 5.4
- Q((3,3), 아래) ≈ 6.2
- Q((3,3), 왼쪽) ≈ 4.8
- Q((3,3), 오른쪽) ≈ 8.5
- 70%의 시간 동안 '오른쪽' 선택 (최적)
- 30%의 시간 동안 다른 행동 무작위 탐험
- 전체 미로에서:
- 최적 경로를 대부분 따르지만(70%)
- 여전히 30% 확률로 탐험하여 더 나은 경로 가능성 확인
ε-greedy의 개선 효과
- Exploitation 요소 (1-ε):
- 로봇이 현재 알고 있는 최적 경로((0,0) → (0,1) → ... → (4,4))를 70% 확률로 따름
- 이는 미로를 탈출하는 효율적인 방법 제공
- Exploration 요소 (ε):
- 30% 확률로 무작위 행동 선택
- 예: 장애물 옆 (3,1)에서 무작위로 '위' 선택하여 새로운 경로 발견
- 이전에 발견하지 못한 숨겨진 지름길 발견 가능성 유지
- Q값 수렴:
- 초기: 모든 Q(s,a) = 0
- 중기: 장애물 근처 행동은 낮은 Q값, 목표 근처 행동은 높은 Q값
- 후기: Q값이 안정화되어 최적 경로 형성
개선의 핵심
최적 행동을 주로 선택하면서도(70%), 지속적인 탐험(30%)을 통해:
- 미로의 변화 감지 가능 (예: 장애물 위치 변경)
- 잠재적으로 더 효율적인 경로 발견 가능
- 국소 최적해(local optimum)에 빠지는 것 방지
이런 균형 덕분에 ε-greedy 정책은 미로 찾기와 같은 실제 문제에서 강력하고 적응력 있는 학습 방법이 된다.
|인증|
-------
패스트캠퍼스 링크