*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다.
|내용 정리|
< Policy Evaluation (정책 평가)>
1. Policy Evaluation (정책 평가)
수식 및 개념:
- 정책 평가란 주어진 정책(policy) 의 **가치 함수(value function) **를 계산하는 방법을 의미함.
- 이를 위해 동적 계획법(dynamic programming, DP)을 활용.
- 동적 계획법(DP)은 1950년 Richard Bellman에 의해 고안된 최적화 방법으로, 큰 문제를 작은 문제로 쪼개고 재귀적인(recursive) 형태로 해결하는 방식.
2. Action-Value Function 업데이트
수식 및 개념:
Bellman 방정식을 이용하여 Action-Value Function 를 업데이트:
여기서,
- 는 상태 에서 행동 를 했을 때 다음 상태 로 전이될 확률.
- 는 보상 함수(reward function).
- γ는 할인율(discount factor), 미래 보상을 현재 가치로 환산하는 역할.
수렴 조건:
반복적으로 값을 업데이트하다가 값의 변화량이 특정 임계값(threshold) 이하가 되면 멈춤.
즉, 변화량이 충분히 작아지면 최적 Q 함수 에 수렴했다고 판단.
수렴 성질:
만약 일 경우, 무한히 반복하면 실제 Action-Value Function 에 수렴:
요약
- Policy Evaluation (정책 평가)
- 정책 의 가치 함수 를 계산하는 과정.
- 동적 계획법(DP)을 이용하여 해결.
- Bellman 방정식을 통해 가치 함수 갱신.
- Action-Value Function 업데이트
- 상태-행동 가치 함수 를 Bellman 방정식으로 반복 업데이트.
- 값이 충분히 수렴하면 멈춤.
- 일 경우, 최적 Q 함수 에 수렴
|응용|
정책 평가(Policy Evaluation)의 실제 예시
그리드월드 예시
4x4 그리드월드 환경을 생각해보자:
- 에이전트는 상, 하, 좌, 우로 이동할 수 있습니다.
- 오른쪽 아래 코너(3,3)에 +1 보상이 있는 목표 상태가 있습니다.
- 왼쪽 아래 코너(3,0)에 -1 보상이 있는 함정이 있습니다.
- 다른 모든 상태의 보상은 0입니다.
- 감마(γ)값은 0.9입니다.
현재 에이전트의 정책 π는 모든 상태에서 네 방향으로 균등하게 확률 0.25로 이동하는 것이다(무작위 정책).
정책 평가 과정
- 초기화: 모든 상태의 가치 함수 V(s)를 0으로 초기화한다.
- 반복적 업데이트: Bellman 방정식을 사용하여 각 상태의 가치를 계산한다. V₁(s) = ∑ π(a|s) ∑ p(s'|s,a)[R(s,a,s') + 0.9·V₀(s')] 예를 들어, 상태 (1,1)에서:
- 상: 25% 확률로 (0,1)로 이동, 보상 0
- 하: 25% 확률로 (2,1)로 이동, 보상 0
- 좌: 25% 확률로 (1,0)로 이동, 보상 0
- 우: 25% 확률로 (1,2)로 이동, 보상 0
- 수렴까지 반복: 각 반복마다 모든 상태의 가치가 업데이트됩니다. 목표 상태와 가까운 상태들부터 점점 더 높은 가치를 갖게 된다.
최초의 가치함수:
이제 가치함수 업데이트 예시를 들어보면:
첫 번째 반복 (k=1)
상태 (2,2)의 계산 과정:
V₁(2,2) = ∑ π(a|s) ∑ p(s'|s,a)[R(s,a,s') + 0.9·V₀(s')]
- 상 방향 (25% 확률): (1,2)로 이동, 초기 가치 0 0.25 × (0 + 0.9 × 0) = 0
- 하 방향 (25% 확률): (3,2)로 이동, 초기 가치 0 0.25 × (0 + 0.9 × 0) = 0
- 좌 방향 (25% 확률): (2,1)로 이동, 초기 가치 0 0.25 × (0 + 0.9 × 0) = 0
- 우 방향 (25% 확률): (2,3)로 이동, 초기 가치 0 0.25 × (0 + 0.9 × 0) = 0
V₁(2,2) = 0 + 0 + 0 + 0 = 0
목표 상태 근처인 (2,3)의 계산:
V₁(2,3) = 0.25 × (0 + 0.9 × 0) + 0.25 × (0 + 0.9 × 1) + 0.25 × (0 + 0.9 × 0) + 0.25 × (0 + 0.9 × 0) V₁(2,3) = 0 + 0.225 + 0 + 0 = 0.225
두 번째 반복 (k=2)
(2,2)의 계산:
- 상 방향: (1,2)로 이동, V₁(1,2) = 0 0.25 × (0 + 0.9 × 0) = 0
- 하 방향: (3,2)로 이동, V₁(3,2) = 0.225 0.25 × (0 + 0.9 × 0.225) = 0.05
- 좌 방향: (2,1)로 이동, V₁(2,1) = 0 0.25 × (0 + 0.9 × 0) = 0
- 우 방향: (2,3)로 이동, V₁(2,3) = 0.225 0.25 × (0 + 0.9 × 0.225) = 0.05
V₂(2,2) = 0 + 0.05 + 0 + 0.05 = 0.1
두 번째 반복 후 그리드:
세 번째 반복 (k=3)
(2,2)의 계산:
- 상 방향: (1,2)로 이동, V₂(1,2) = 0.051 0.25 × (0 + 0.9 × 0.051) = 0.011
- 하 방향: (3,2)로 이동, V₂(3,2) = 0.328 0.25 × (0 + 0.9 × 0.328) = 0.074
- 좌 방향: (2,1)로 이동, V₂(2,1) = 0 0.25 × (0 + 0.9 × 0) = 0
- 우 방향: (2,3)로 이동, V₂(2,3) = 0.429 0.25 × (0 + 0.9 × 0.429) = 0.097
V₃(2,2) = 0.011 + 0.074 + 0 + 0.097 = 0.182
세 번째 반복 후 그리드:
그 후 더 많은 반복 후:
|인증|
-------
패스트캠퍼스 링크