*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다.
|내용 정리|
<Policy Iteration(정책 반복법)>
Policy Iteration은 **정책 평가(Policy Evaluation)**와 **정책 개선(Policy Improvement)**을 반복하며 최적 정책을 찾는 강화학습 알고리즘을 말한다.
여기서 사용되는 주요 기호의 의미:
- π: 정책(policy)
- V: 가치 함수(value function)
- s, s': 상태(state)
- a: 행동(action)
- p(s'|s,a): 상태 s에서 행동 a를 취했을 때 상태 s'로 전이될 확률
- R(s,a,s'): 상태 s에서 행동 a를 취해 상태 s'로 이동했을 때 받는 보상
- γ: 감가율(discount factor)
- δ: 수렴 임계값(convergence threshold)
- Δ: 가치 함수 업데이트 간의 최대 차이
1. Policy Iteration 과정의 수식 표현
- 초기 정책(π₀)부터 시작해서 정책 평가(PE)와 정책 개선(PI)을 반복적으로 수행하여 최적 정책(π*)과 최적 가치 함수(V^π*)에 도달
2. Policy Iteration 과정의 수식 표현
- 의미:
- 𝑉𝑘+1(𝑠): 상태 𝑠의 새로운 가치 함수
- 𝑝(𝑠′∣𝑠,𝑎): 상태 𝑠에서 행동 𝑎를 취했을 때 상태 𝑠′로 전이할 확률
- 𝜋(𝑎∣𝑠): 정책 𝜋에 따라 상태 𝑠에서 행동 𝑎를 선택할 확률
- 𝑅(𝑠,𝑎,𝑠′): 상태 𝑠에서 행동 𝑎를 취해 상태 𝑠′로 전이할 때의 보상
- 𝛾: 할인 계수(Discount Factor)
- 𝑉𝑘(𝑠′): 이전 단계에서 계산된 상태 𝑠′의 가치 함수
- 목적: 현재 정책 𝜋에 대한 가치 함수 𝑉를 반복적으로 계산하여 정확도를 높인다.
2. Policy Iteration 알고리즘 단계
1. Δ 계산
- 의미: 현재 가치 함수 𝑉𝑘와 이전 가치 함수 𝑉사이의 최대 차이를 계산
- 목적: 가치 함수의 변화량이 충분히 작은지(Δ ≤ δ) 확인하여 수렴 여부를 판단
2. 가치 함수 업데이트
- 조건: Δ > δ일 때만 실행
- 의미: Policy Evaluation 단계에서 계산된 𝑉𝑘를 새로운 가치 함수 𝑉로 업데이트
3. 정책 개선
- : 상태 𝑠에서 최적의 행동으로, 기대 보상 ∑𝑠′𝑝(𝑠′∣𝑠,𝑎)[𝑟+𝛾𝑉(𝑠′)]를 최대화하는 행동 𝑎
- 𝑝(𝑠′∣𝑠,𝑎): 상태 전이 확률, 𝑟: 보상, 𝛾 할인 계수.
4. 정책 업데이트
- 의미: 상태 𝑠에서 𝑎max를 선택할 확률을 1로 설정 (Deterministic Policy)
5. 반복 또는 종료
- 반복 조건: Δ > δ인 경우, Policy Evaluation 단계(2)로 돌아가 반복
- 종료 조건: Δ ≤ δ인 경우, 현재 가치 함수 𝑉와 정책 𝜋를 반환
그리드 월드 예제로 Policy Iteration 수식 재현
그리드 월드 설정
- 4x4 그리드 월드 (총 16개 상태)
- 행동: 상(0), 우(1), 하(2), 좌(3) 네 방향으로 이동 가능
- 목표 상태: (3,3) 위치의 상태 15에 도달하면 +1 보상
- 함정 상태: (1,1) 위치의 상태 5에 빠지면 -1 보상
- 그 외 이동에는 보상 0
- 감마(할인율): 0.9
Policy Iteration 알고리즘 단계
1. 초기화
2. Policy Evaluation
상태 (0,0)(상태 번호 0)에서의 가치 함수 업데이트 계산:
여러 번의 반복 후 가치 함수가 수렴하기 시작한다. 예를 들어 목표 상태(15) 근처의 상태(14)에서는:
반복이 진행될수록 목표 상태에서 먼 상태들도 점점 적절한 가치로 수렴
3. Policy Improvement
가치 함수가 수렴한 후, 각 상태에서 최적 행동을 선택하는 정책 개선을 수행
예를 들어, 상태 (2,2)(상태 번호 10)에서:
만약 Q(10, 하)가 최대값이라면
4. 반복 및 수렴
정책이 더 이상 변하지 않을 때까지 정책 평가와 정책 개선을 반복
최종적으로, 우리는 다음과 같은 결과를 얻는다:
- 최적 정책: 각 상태에서 목표로 가는 최단 경로를 따르는 행동을 선택하고, 함정을 피하는 정책
- 최적 가치 함수: 각 상태에서의 기대 누적 보상을 나타내는 값
예를 들어, 최적 정책은 다음과 같을 수 있다:
여기서 'G'는 목표 상태이고, 함정 상태 주변에서는 함정을 피하는 행동을 선택한다. 이 구현에서는 결정론적 환경을 사용했지만, 실제 강화학습에서는 확률적 환경에서도 적용 가능하다. 시뮬레이션을 실행하면 반복이 진행됨에 따라 가치 함수와 정책이 어떻게 변화하는지 확인할 수 있다.
추가) Generalized Policy Iteration (일반화된 정책 반복)
Generalized Policy Iteration (GPI, 일반화된 정책 반복)은 강화학습에서 정책을 최적화하는 핵심 원리이다. GPI는 임의의 정책 평가(Policy Evaluation)와 정책 개선(Policy Improvement) 알고리즘을 활용하여 정책을 반복적으로 개선하는 방법이며 이는 기존의 엄격한 Policy Iteration의 일반화된 형태로 볼 수 있다.
GPI의 주요 특징:
- 유연한 상호작용: 정책 평가와 정책 개선이 완전히 수렴할 때까지 기다리지 않고 상호작용하며 진행된다.
- 점진적 개선: 정책 평가에서는 현재 정책 π에 대한 가치 함수 V^π를 추정하고, 정책 개선에서는 이 가치 함수를 바탕으로 greedy(V)를 통해 더 나은 정책 π'을 생성한다.
- 수렴 과정: V₀, π₀에서 시작하여 여러 번의 반복을 통해 최적 가치 함수 V와 최적 정책 π로 수렴한다.
GPI의 두 가지 핵심 과정:
- Policy Evaluation (정책 평가):
- 임의의 정책 평가 알고리즘을 사용하여 V^π 추정
- 완전한 수렴이 아닌 부분적 평가도 가능
- Policy Improvement (정책 개선):
- 임의의 정책 개선 알고리즘을 사용하여 π' ≥ π 관계를 만족하는 새로운 정책 생성
- 주로 greedy(V) 방식을 사용 (각 상태에서 현재 가치 함수를 최대화하는 행동 선택)
GPI의 장점은 완전한 정책 평가나 정책 개선을 기다리지 않고도 점진적으로 최적 정책을 향해 나아갈 수 있다는 것이다. 이러한 유연성은 특히 대규모 상태 공간이나 복잡한 환경에서 계산 효율성을 높이며, 실용적인 강화학습 알고리즘의 기반이 된다.
|인증|
-------
패스트캠퍼스 링크