[강화학습6]정책 반복(Policy Iteration)

정책반복은 가치반복과 마찬가지로 강화학습 알고리즘 중 하나이다.

정책반복은 다음과 같은 절차로 진행된다.

그림1

 

초기정책 설정

모든 상태에 대해 임의의 행동을 선택하는 정책을 설정한다.

정책 평가

1. 모든 상태가치를 0으로 초기화한다.
2. 가치함수의 업데이트는 벨만 기대방정식을 사용하여 수행된다. 업데이트는 다음수식을 사용하여 계산된다.
   $$ v_{k+1}(s) = \sum_{a}\pi(a \mid s) \sum_{s', r} P(s', r \mid s, a) [ r + \gamma v_k(s') ]$$
   $k$번의 반복을 거치면서 $v_k$는 실제 가치함수에 점점더 가까워지게 된다.
   이과정에 대한 증명은 전포스팅의 가치반복 증명과정과 유사해 생략했다.
3. 가치함수의 변화가 특정 임계값보다 작아지면, 정책평가 과정을 종료한다. 이 임계값에 대한 마땅한 기준은 없으나,
   가치함수의 업데이트가 너무 적게 이루어지면 제대로 된 정책평가가 이루어지지 않아 올바른 최적정책이 유도되지 않을 수도 있다.

정책 개선

1. 새로운 정책$\pi'$ 설정
   정책개선의 목적은 현재 정책 $\pi$를 개선하여 더 높은 보상을 얻을 수 있는 새로운 정책 $\pi'$를 찾는 것이다. 새로운 정책$\pi'$는 각 상태 $s$에서 $q_{\pi}(s, a)$를 최대화하는 행동 $a$를 선택하는 것이다. 수식으로 표현하면 다음과 같다.
   $$\pi'(s) = \underset {a}{\text {argmax}} \, \, q_{\pi}(s, a), \forall s \in S$$
   이때 각 정책에 대한 가치함수는 다음과 같이 유도된다. 
   $v_{\pi'}(s) = \underset {a}{\max} q_{\pi}(s, a)$
   $v_\pi(s) = \sum_{a}\pi(a \mid s) q_\pi(s, a)$
   이를 바탕으로 한 정책 간의 관계는 다음과 같다.
   $v_{\pi'}(s) \geq v_{\pi}(s)$
   $ \therefore \pi' \geq \pi$
2. 정책의 수렴 검사
   만약 새로운 정책 $\pi'$가 현재 정책 $\pi$와 동일하다면
   $v_{\pi}(s) = \underset {a}{\max} q_{\pi}(s, a)$
   이것은 벨만최적방정식의 형태와 같다.
   $v^*(s) = \underset {a}{\max} q^*(s, a)$
   이때 $\pi$는 최적정책이라고 간주할 수 있으므로 정책반복을 종료한다.
   만약 새로운 정책 $\pi'$가 이전 정책 $\pi$와 동일하지 않다면  새로운 정책을$\pi'$를 현재 정책$\pi$로 설정하고, 정책평가 단계로 되돌아간다.

---

가치 반복과 정책 반복은 최적의 정책을 도출하기 위한 방법론이다. 그러나 중요한 점은, 이 방법들이 100% 확률로 최적의 정책을 찾아주는 것은 아니라는 것이다.
실제 환경에서 구현 시, 무한한 계산 리소스가 없기 때문에 가치 함수를 무한히 업데이트할 수 없다. 따라서, 우리는 실제 가치 함수를 기반으로 한 근사치를 정책 수립에 사용하게 된다. 따라서 결과가 최적의 정책이라고 확신할 수 없다.
이론적인 상황에서, 가치 함수를 무한히 업데이트할 수 있다고 가정한다면, 가치 함수의 추정값이 실제 가치 함수에 수렴하여, 이로 인해 최적의 정책을 찾아낼 확률이 크게 상승한다. 그렇지만 여전히, 가치 함수의 추정값이 실제 가치 함수와 같지 않기 때문에 100% 확률로 최적의 정책을 찾아낼 수 있다고는 보장할 수 없다.
정리하자면, 가치 반복과 정책 반복 방법을 통해 얻은 정책이 항상 최적이라고 말할 수는 없으나, 가치함수의 업데이트 반복 횟수가 늘어날수록 가능성은 점점 높아진다.