*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다.
|내용 정리|
<Policy Improvement Theorem>
1. Policy Improvement란?
강화학습(RL)에서 Policy Improvement(정책 개선)은 주어진 정책 를 더 나은 정책 로 개선하는 과정으로 즉, 기존 정책보다 더 높은 보상을 받을 수 있도록 행동을 조정하는 방법이다.
2. 정책 개선을 위한 업데이트 수식
주어진 정책 의 Action-Value Function 를 알고 있다면,
이를 이용해 정책을 아래와 같이 개선할 수 있다.
3. 정책 개선의 조건
정책이 개선되려면, 새로운 정책 가 기존 정책 보다 더 높은 기대 보상을 가져야 한다. 즉, 아래 부등식이 성립해야 한다.
이 부등식을 풀어보면,
여기서 의 정의를 대입하면,
이제 정리하면,
4. Policy Improvement Theorem (정책 개선 정리)
정책 개선 과정에서 중요한 수학적 원리는 다음과 같다.
- 첫 번째 식: π'가 각 상태에서 더 높은 Q(특정 상태에서 특정 행동을 선택했을 때의 기대 보상을 나타내는 함수 - 행동가치함수)값을 갖는 행동에 더 많은 확률을 부여한다는 것을 의미. 즉, π'는 더 좋은 행동을 선택하는 정책
- 두 번째 식: 벨만 방정식의 기본 형태로, 상태 가치 함수는 그 상태에서의 행동 가치 함수의 기댓값과 같다는 것을 나타내며 정책 π의 가치 함수가 새로운 정책 π'에 따라 행동을 선택했을 때의 Q값 기댓값보다 작거나 같다는 것을 명시
- 세 번째 식: 앞서 증명한 두 번째 줄의 부등식 부분만을 분리해서 강조한 것입니다. 모든 상태 s에 대해 성립함을 명시
- 마지막 식: 앞의 부등식들로부터 정책 π'의 가치 함수가 정책 π의 가치 함수보다 크거나 같다는 것을 증명
즉, 새로운 정책 가 기대 가치가 더 크거나 같다면,
즉, 모든 상태 에 대해
이면 정책 가 보다 더 나은 정책이라는 것이다.
5. 예제: 정책 개선 적용
(1) Q 값 예제
어떤 환경에서 아래와 같은 Q-값이 있다고 가정한다.
기존 정책 가 균등한 확률로 행동을 선택한다고 가정하면,
(2) 정책 개선 적용
- 가장 좋은 행동은 (Q-값이 10으로 가장 큼).
- 정책을 개선하여 를 만들면:
이제 정책이 업데이트되어 최적 행동 가 더 자주 선택된다.
(3) 정책 개선 후 기대 보상 비교
기존 정책의 기대 보상:
개선된 정책의 기대 보상:
즉, 개선된 정책의 기대 보상이 기존 정책보다 높아졌다.
조건을 만족하므로 정책이 개선되었다고 볼 수 있다.
6. 결론
- Policy Improvement는 현재 정책보다 더 나은 정책을 만들어내는 과정이다.
- 행동 가치 함수 를 활용하여 더 좋은 행동을 더 자주 선택하는 방향으로 정책을 수정한다.
- 수학적으로 아래의 식을 만족해야 한다.
<ε-탐욕 정책 개선(ε-greedy policy improvement) - 벨만 부등식>
앞의 정책 개선 정리로, 개선된 정책 π'가 기존 정책 π보다 더 나은 성능을 보장한다는 것을 증명했다면 상태 가치와 행동 가치 간의 관계를 설명한다. 이를 통해서 새 정책 π'이 기존 정책 π보다 더 높은 가치를 가진다는 것을 수학적으로 보여줌으로써, 정책 반복(policy iteration) 알고리즘의 이론적 근거를 제공한다.
- 𝑉𝜋(𝑠𝑡)는 정책 𝜋하에서 상태 𝑠𝑡의 가치 함수이다.
- 𝑄𝜋(𝑎𝑡,𝑠𝑡)는 정책 𝜋하에서 상태 𝑠𝑡에서 행동 𝑎𝑡를 선택했을 때의 가치 함수이다.
- 이 부등식은 정책 𝜋′가 𝜋보다 더 나은 행동을 선택할 수 있음을 나타낸다.
- 𝑄𝜋(𝑎𝑡,𝑠𝑡)는 상태 𝑠𝑡에서 행동 𝑎𝑡를 선택했을 때의 보상 기댓값을 나타낸다.
- 𝑃(𝑠𝑡+1∣𝑠𝑡+2)는 상태 전이 확률이며, 𝑅(𝑠𝑡𝑎𝑡𝑠𝑡+1)은 보상 함수이다
- 𝑟𝑡+1은 시간 𝑡+1에서의 보상이며, 할인 계수 𝛾가 적용된 다음 상태의 가치 함수를 포함한다.
- 이 식은 정책 𝜋′하에서의 기댓값을 나타낸다.
- 이 부등식은 가치 함수와 Q 함수 간의 관계를 재귀적으로 확장합니다.
- 정책 𝜋′가 𝜋보다 더 나은 행동을 선택할 때마다 부등식이 성립함을 보여줍니다.
- 시간 단계를 더 확장하여 할인된 보상과 가치 함수를 포함한다.
- 무한히 많은 시간 단계를 고려할 때, 정책 𝜋′의 가치 함수가 정책 𝜋의 가치 함수보다 큼을 나타낸다.
- 모든 상태 𝑠에 대해 정책 𝜋′의 가치 함수가 정책 𝜋의 가치 함수보다 크거나 같음을 결론짓는다. 이는 정책 개선의 이론적 근거를 제공한다.
- 각 상태에서 Q값이 최대가 되는 행동만 선택하는 새로운 정책을 만든다면, 원래 정책보다 더 좋은 정책을 얻을 수 있다.
이 과정을 반복하면- 현재 정책 의 가치 함수 를 계산한다.
- 각 상태에서 가 최대가 되는 행동 를 선택하는 새로운 정책 을 만든다.
- 이 과정을 반복한다.
" 결론적으로 이 부등식을 활용하여 반복적으로 최대값을 뽑아내는 과정이 Policy Iteration의 핵심이며, 이것이 Bellman Optimality Equation으로 수렴하게 되어 최적의 정책에 도달하게 된다는 것이다."
<Policy Improvement Theorem과 Policy Iteration의 실제 예시>
이론적인 수식이 실제로 **강화 학습(Reinforcement Learning, RL)**에서 어떻게 사용되는지, 구체적인 예시와 함께 알아보자.
1. Policy Improvement Theorem의 활용
목표: 현재 정책(𝜋)보다 더 나은 정책(𝜋′)을 찾기
예시: 그리드 월드(Grid World) 문제
- 환경: 3x3 그리드, 에이전트는 출발지(S)에서 목표지(G)로 이동해야 함.
- 보상:
- 목표 도달: +10
- 벽 충돌: -1
- 일반 이동: 0
- 현재 정책(𝜋): 무작위로 이동 (↑, ↓, ←, → 각각 25% 확률).
- 할인 계수(𝛾): 0.9
(1) 현재 정책 𝜋의 가치 함수 𝑉𝜋(𝑠) 계산
- 반복적인 평가를 통해 각 상태의 𝑉𝜋(𝑠)를 계산 (예: Dynamic Programming).
- 예: 𝑉𝜋(중앙) (목표에 가까울수록 값 ↑).
(2) 더 나은 정책 𝜋′생성 (Greedy Policy)
- 각 상태에서 가장 높은 Q값을 주는 행동을 선택
- 예: 중앙 상태에서 𝑄𝜋(→) (가장 높음) → 𝜋′는 "오른쪽으로 이동"을 100% 선택.
(3) Policy Improvement Theorem 적용
- 𝜋′는 𝜋보다 항상 같거나 더 좋음
- 실제로 𝜋′는 무작위 정책보다 목표 도달 시간이 짧아짐.
2. Policy Iteration의 활용
목표: 최적 정책(𝜋∗)을 찾기
예시: Frozen Lake 환경 (OpenAI Gym)
- 환경: 얼음 호수에서 구멍(Hole)을 피해 목표지(G) 도달.
- 보상:
- 목표 도달: +1
- 구멍 추락: 0
- 그 외: 0
- 할인 계수(𝛾): 0.99
(1) 정책 평가 (Policy Evaluation)
- 현재 정책 𝜋𝑘에 대해 𝑉𝜋𝑘(𝑠)를 반복 계산.
- 예: 𝑉𝜋𝑘(시작점) (초기에는 낮음).
(2) 정책 개선 (Policy Improvement)
- Greedy 정책으로 업데이트
- 예: 구멍 근처에서 "위쪽 이동" 대신 "왼쪽 이동" 선택.
(3) 수렴 확인
- 더 이상 𝑉𝜋𝑘(𝑠)가 변하지 않을 때까지 반복.
- 최종적으로 최적 정책 𝜋∗획득:
- 모든 상태에서 최적 행동을 선택 (예: 구멍 회피 경로).
결과:
- 초기 정책: 30% 성공률 → 최적 정책: 90% 성공률.
3. 실제 적용 사례
- 로봇 경로 계획
- Policy Iteration을 사용해 장애물을 피하는 최적 경로 학습.
- 게임 AI (예: 체스, 알파고)
- 현재 전략(𝜋)보다 더 나은 전략(𝜋′)을 반복적으로 탐색.
- 자율 주행
- 정책 평가 → 개선 과정을 통해 안전한 주행 정책 도출.
|인증|
-------
패스트캠퍼스 링크