[강화학습] 동적 계획법 - 정책 반복(Policy Iteration)

 

 

 

정책 반복(Policy Iteration)

 

 

이전 글에서 최적 정책을 구하는 3가지 방법이 존재한다고 했고, 그 중에서 Dynamic Programming(둥적 계획법)의 Iterative Policy Evaluation(반복 정책 평가) 내용을 다루었다.

2024.10.12 - [Data Science/강화학습] - [강화학습] 동적 계획법 - 반복 정책 평가 (Iterative Policy Evaluation)

[강화학습] 동적 계획법 - 반복 정책 평가 (Iterative Policy Evaluation)

강화학습 종류, 그 중에서 Dynamic Programming, DP를 다뤄보는 중

 

이번 포스팅에서는 Policy Iteration (정책 반복) algorithm에 대해 다루어보고자 한다.

 

 

 

정책 반복이란? (Policy Iteration)

 

이전에 다루었던 반복 정책 평가(Iterative Policy Evaluation)에서는 한 state에서 할 수 있는 모든 action들의 가치들을 종합해  sweep, update를 반복하여 가치함수(value function)가 현재의 정책을 잘 따르도록 만들었다고 할 수 있다.

 

하지만 정책 반복(Policy Iteration)에서는 하나의 공정이 더 들어가진다고 할 수 있다.

반복 정책 평가에서와 달리 탐욕적인 정책을 만들어 최적의 정책(optimal policy)을 찾는 과정이라고 할 수 있다.

반복 정채개 평가에서는 가치함수를 update 했지만 정책 반복에서는 state value와 policy, 두 table을 update 하게 된다.

 

여기서 greedy 하다는 것은 action을 할 때 근처 state들의 value 중에서 가장 높은 값으로 이동하는 것을 greedy한 action, greedy한 policy라고 할 수 있다.

value function 관점으로 보았을 때, current state → next state로 움직이는 기준은 goal 최종지점의 기준으로 보았을 때의 가치가 가장 높은 state로 이동하게 된다.

이 둘은 엄연한 차이가 존재한다.

이에 대한 내용은 다음 글에서 정리를 했었다.

2024.10.03 - [Data Science/강화학습] - [강화학습] 가치함수(Value Function)

[강화학습] 가치함수(Value Function)

 

 

 

다음과 같이 policy table(π table), state value table(V table) 두 테이블이 존재한다.

π를 통해서 V를 평가한 후 업데이트 하고(evaluation), 

그 업데이트 된 V를 통해서 다시 greedy한 policy π로 업데이트한다(improvement).

 

state value를 업데이트 하는것을 evaluation

π를 greedy하게 바꾸는 것을 improvement 라고 한다.

 

 

 

최초의 정책인 $ \pi _{0} $를 통해서 state들을 평가한 후 state value들을 evaluation 한다.

그 값은 $ \upsilon _{\pi _{0}} $ 가 된다.

이 value 값들을 기반으로 만들어진 greedy policy를 $ \pi _{1} $로 improvement 한다.

 

1. $ \pi _{0} $를 통해서 value function을 통해서 evaluation한다.
2. 1번 과정을 통해서 policy $ \upsilon _{\pi _{0}} $를 생성 
3. $ \upsilon _{\pi _{0}} $ 를 기반으로 greedy policy $ \pi _{1} $를 생성
4. 위 과정 무한반복,,,
5. optimal policy에 수렴된다.

이 과정을 거치는 것을 Policy Iteration 이라고 하는 것이다.

결과적으로 stochastic policy는 deterministic policy로 바뀌게 된다.

 

위 방법은 세부 사항에 관계 없이 두 과정이 서로 상호작용 되는 일반적인 방법으로, 거의 모든 강화학습 방법을 설명할 수 있다.

 Calculate $ \nu _{\pi } $ → make greedy → repeat 

 

 

아래 그은 초기 value function과 policy가 optimal한 방향으로 수렴되는 과정을 보여주는 그림이다.

state value, policy가 optimal하게 수렴되는 과

처음 value function을 업데이트를 하게 되면 현재의 정책을 따르는 가치함수 $ \upsilon _{\pi _{0}} $ 가 된다.

이는 정책이 greedy하지 않은 상태이다.

 

이를 다시 greedy하게 업데이트 하는 과정이 두번째 화살표 과정이 된다.

이는  가치함수 $ \upsilon _{\pi _{0}}(s) $ 는 정책 π에 대해 부정확해진다.

그렇기 때문에 바뀐 policy를 통해서 value function을 업데이트 한다.

 

최종적으로는 optimal policy에 수렴되는데, 자기 자신의 가치함수에 대해 탐욕적인 정책을 찾을 때만 수렴이 가능해진다.

 

 

 

Policy Iteration - pseudo code

 

Policy Iteration에서 이루어지는 코드를 psudo 형태로 나타낸 것이다.

나는 주로 파이썬으로 위 psudo code를 구현한다.

policy iteration pseudo code

 

일단 총 3단계로 구성되어 있다.

 

1 : V table, π table 두개를 만든 후 초기화

2: Iterate policy evaluation과 같은 과정을 looping

3: policy가 stable할 때(old action = π(s) )까지 looping이 돌려진다. Bellman 최적 방정식을 통해서 optimal policy를 정의한 후 looping 종료. / unstable할 시 2단계 진행