강화학습 - (12) 정책 반복

강화학습

정책 향상

강화학습의 궁극적인 목표중 하나인 제어(Control)를 하기 위해서는 정책 향상이 필요하다.

이미 최적 가치를 알고 있고, 탐욕적인 정책을 사용했다고 가정했을 때 벨만 방정식은 다음과 같다:

$\pi_*(s) = argmax_a \sum_{s'} \sum_{r} p(s', r | s, a) [r + \gamma v_*(s')]$

 

만약 $v_*$가 아닌 $v_\pi$를 따른다고 가정해 보자:

$\pi(s) = argmax_a \sum_{s'} \sum_{r} p(s', r | s, a) [r + \gamma v_*(s')]$ 

만약 위와 같은상황에서 모든 상태에 대해서 위 탐욕적 수식이 정책을 변동시키지 않는다면,

해당 정책은 벨만최적방정식에 위배되고, 이는 이미 이 정책이 최적임을 증명하는 것이 된다.

정책 향상 정리 (Policy Improvement Theorem)

$q_{\pi}(s, \pi'(s)) \ge q_{\pi}(s, \pi(s))$ for all $s \in S$

then $\pi' \ge \pi$

 

정책 향상 정리는 한 정책이 다른 정책보다 낫다는 것을 정의한다.

만약 $\pi'$을 따라 한 행동이, $\pi$를 따라 한 행동들보다, 

모든 상태에서 더 나은 가치를 준다면 $\pi' \ge \pi$ 를 만족한다는 것이다.

 

정책 반복 (Policy Iteration)

정책 $\pi$가 이미 최적 정책이 아닌 이상, 

정책 향상 법칙은 $\pi$보다 $\pi'$가 확실히(strictly) 낫다는 것을 증명한다.

정책 반복이란, 정책 평가를 통해서 정책 향상을 하는 것을 반복하는것을 의미한다.

다시 정리하면, 정책 평가는 먼저 정책을 통해 가치를 얻는 과정,

그리고 정책 향상은 얻어진 가치를 통해 정책을 평가하고 가치를 통해 더 탐욕적으로 선택해 반영,

그리고 이것이 최적 정책이 될 떄 까지 반복하는것이 정책 반복이다.

(정책 평가) $\pi_1 \xrightarrow{\text{E}} v_{\pi_1}$

(정책 향상) $v_{\pi_1} \xrightarrow{\text{I}} \pi_2$, ($\pi_2 > \pi_1$)

(정책 평가) $\pi_2 \xrightarrow{\text{E}} v_{\pi_2}$

(정책 향상) $v_{\pi_2} \xrightarrow{\text{I}} \pi_3$, ($\pi_3 > \pi_2$)

...

(정책 향상) $v_{\pi_{k-1}} \xrightarrow{\text{I}} \pi_*$

(정책 평가) $\pi_* \xrightarrow{\text{E}} v_{\pi_*}$

(정책 향상) $v_* \xrightarrow{\text{I}} \pi_*$

 

또한 위에 보이는 것 처럼, $\pi_*$는 더이상 정책이 향상되지 않을 때 구해졌음을 알 수 있다.

그리고 위에 보이는 모든것은 확정적인 정책 (Deterministic Policy)를 가정한다.

이는 또한 다음과 같이 $v_*$와 $\pi_*$를 이뤄질때까지 위($v$) 아래($\pi$)로 튕기며 향상하는 것 같이 표현될 수 있다.

다이나믹 프로그래밍으로 정책 향상을 하는 것은 더 나은 정책을 검색하는 것과 같다.

더 간단히 표현하면, 위의 모든 점들은 정책들이다.

그리드월드의 다이나믹 프로그래밍 상황에서는 이들은 가치를 통해 환산된 다음 셀로 가는 방향일 것이다.

이 방향들은 행렬과 같은 데이터 집합에 저장된다.

정책 향상을 통해 가치 갱신하면, 이를 통해 통해 이 방향들은 바뀔 수 있다.

그리고 더이상 모든 셀들의 방향이 바뀌지 않을 때, 이를 $\pi_*$라고 말할 수 있다.

정책 향상 알고리즘(Pseudo-code)는 다음과 같다: