강화학습: 정책 이터레이션과 가치 이터레이션

May 2, 2022, midnight

1. 정책 이터레이션이란?

이번 포스트에서는 벨만 기대 방정식을 통한 정책 이터레이션을 통한 순차적 문제 해결에 대해서 알아보겠습니다.

강화학습의 최종 목적은 가장 많은 보상을 얻을 수 있게 하는 정책을 얻는 것입니다. 우리가 원하는 정책을 얻기 위해서는 총 두가지의 과정이 필요합니다. 정책 평가와 정책 발전입니다.

정책 평가는 말 그대로 먼저 현재 정책을 평가합니다. 가치함수를 기반으로 현재 정책을 평가하는데요, 정책 평가를 통해 현재 정책의 참 가치함수를 구하고 이 정책이 참 가치함수를 기반으로 보았을 때 최대의 보상을 얻을 수 있게 하는 정책인지를 평가하는 것입니다.

평가가 완료되면 정책 발전을 실시합니다. 만약 현재 정책이 참 가치함수를 기반으로 최대의 보상을 얻지 못하는 정책이라면, 최대의 보상을 얻을 수 있도록 정책을 수정하는 것이죠.

정책 평가와 정책 발전을 반복하면 최적정책으로 수렴하게 되며 이것이 바로 정책 이터레이션 입니다.

2. 참 가치함수 구하기, 정책 평가

자, 그러면 첫번째 단계로 우리는 현재 정책의 참 가치함수를 구해야 합니다.

이쯤에서 이전에 알아보았던 벨만 기대 방정식을 꺼내보도록 하죠.

$$v_\pi(s) = E_\pi[R_{t+1} + \gamma v_\pi(S_{t+1})|S_t = s]$$

위의 방정식을 정책을 포함해서 표현하면 아래와 같습니다.

$$v_\pi (s) = \sum_{a \in A} \pi(a | s)\big(r(s,a) + \gamma \sum_{s' \in S} P^a_{ss'}v_\pi(s')\big)$$

그러나 정책평가 처음에는 이 방정식의 양변이 일치하지 않습니다. 아직 가치함수가 참 가치함수가 아니기 때문인데요. 참 가치함수를 구하기 위해서는 다이내믹 프로그래밍으로 우변을 구한 뒤 좌변에 대입해주는 과정을 수렴할 때까지 반복해야 합니다. 이것이 정책 평가입니다.

즉, 가치함수의 k 번째 이터레이션과 k+1번째 이터레이션의 관계는 아래와 같습니다.

$$v_k+1 (s) = \sum_{a \in A} \pi(a | s)\big(r(s,a) + \gamma \sum_{s' \in S} P^a_{ss'}v_k(s')\big)$$

이때 가치함수가 수렴하도록, 즉 양변이 거의 일치할 때까지 이터레이션을 반복합니다. 완료되면 우리는 정책 평가를 통해 현재 정책에 대한 참 가치함수를 구한 것입니다.

3. 정책 발전

이제 정책을 발전시킬 차례입니다. 가장 간단한 방법은 탐욕 정책 발전입니다. 탐욕 정책 발전이랑 정책 평가를 통해 구한 참 가치함수를 기반으로 현재 정책을 어떤 상태 s에서 가장 큰 큐함수를 얻는 행동을 하도록 바꾸면 됩니다. 잠깐 큐함수의 정의를 보고 가겠습니다.

$$q_\pi(s,a) = E_\pi[R_{t+1} + \gamma q_\pi(S_{t+1}, A_{t+1}) | S_t = s, A_t = a]$$

큐함수란 다음 상태의 가치함수와 받을 보상의 기댓값입니다. 즉, 행동의 가치를 나타내는 함수죠.

제일 좋은 정책은 언제나 제일 큰 큐함수를 얻는 행동을 하는 것이라고 볼 수 있습니다. 즉, 탐욕 정책 발전을 사용해서 각 상태에서 가장 큰 큐함수를 얻게하는 행동을 하도록 해보겠습니다. 예를 들어 현재 상태 s에서 할 수 있는 행동은 4가지 [up, down, left, right]이고 현재 정책은 [0.25, 0.25, 0.25, 0.25] 입니다. 즉, 각 행동을 25%확률로 행하는 정책입니다. 각 행동을 했을 경우 다음 상태 s'의 가치함수는 [0, -1, 2.1, 0.1]이라고, 각 행동을 했을 경우 받는 보상은 [0, 0, 0, 5]이라고 해보겠습니다. 이를 통해 할인율을 0.9라고 했을때 각 행동의 큐함수는 [0, -0.9, 1.89, 5.09] 라는 것을 알 수 있습니다. 여기서 가장 큰 큐함수는 5.09입니다. 즉 right을 행동했을때 얻는 큐함수가 가장 크죠. 이상황에서 탐욕 정책 발전을 적용하면 [0, 0, 0, 1]이 됩니다. 즉, right를 선택하게 되는 것입니다. 만약 큐함수가 [0, 2, 4, 4]와 같이 같은 값이 2개 존재한다면 탐욕 정책 발전을 사용했을 때 [0, 0, 0.5, 0.5]가 됩니다. 보통 이런 걸 argmax 라고 하죠. 업데이트되는 정책을 수식으로 표현하면 아래와 같습니다.

$$\pi'(s) = argmax_{a \in A}q_{\pi}(s,a)$$

위의 3가지 과정을 계속해서 반복하면 가치함수, 큐함수가 수렴하게 되면서 최적 정책을 얻을 수 있게 됩니다.

정책 이터레이션을 요약해 보겠습니다. 정책 이터레이션이란 정책이 있고 이것을 평가하는 도구로써 가치함수를 이용합니다. 현재 정책에 대한 참 가치함수를 구하고 이에 따라 정책을 평가한 후 정책을 발전시킵니다. 이를 반복해서 최적 정책을 만들어 냅니다. 여기서 중요한 점은 정책과 가치함수가 명백히 분리되어있다는 점입니다. 위에서는 예시로 확률적인 정책을 사용했습니다. 그러나 정책으로는 어떤 방법도 가능합니다. 정책과 가치함수가 분리되어 있기 때문이죠.

그러나 여기서 생각해 볼만 한 것은 어차피 정책을 가치함수를 통해 평가한다면 가치함수만 가지고 결정론적으로 정책을 정할 수 있지 않느냐는 것입니다. 굳이 정책을 따로 두지 않고 가치함수만 가지고 내재적인 정책을 가지는 것이죠. 이것이 가치 이터레이션입니다.

4. 가치 이터레이션

가치 이터레이션에서는 가치함수를 업데이트하고 정책을 따로 업데이트하지 않습니다. 가치함수만 반복적으로 발전시켜서 최적으로 만듭니다. 정책은 이에 따라서 정해집니다.

다시 말하면, 이미 정책은 최적 정책입니다. 단지 이에 대한 참 가치함수를 찾기만 하면 되는 것이죠. 이전에 가치 이터레이션에서는 정책 평가 과정에서 다음 상태의 가치함수들의 기댓값으로 가치함수를 업데이트 했다면 이번에는 단지 다음 상태의 가치함수들 중에서 가장 큰 max값으로 가치함수를 업데이트합니다. 참 가치함수를 찾는 수식은 아래와 같습니다.

$$v_{k+1}(s) = max(r_{(s,a)}+\gamma v_k(s'))$$

이것을 수렴할때 까지 반복하면 최적 가치함수를 찾게 됩니다. 최적 가치함수를 찾았다면 이제 각 상태에서 무슨 행동을 해야할지 어떻게 알까요? 정책 이터레이션에서는 정책이 존재했기 때문에 정책에 따라서 행동하면 됩니다. 그렇지만 가치 이터레이션에서는 현재 상태에서 가능한 큐함수를 모두 구한뒤에 가장 큰 큐함수를 갖는 행동을 하면 됩니다. 정책이 따로 필요 없는 것이죠. 정책을 구할 필요도, 발전할 필요도 없습니다.

정책 이터레이션과 가치 이터레이션은 강화학습의 근간이 되는 아이디어 입니다. 이러한 이터레이션 방법은 계산의 복잡도가 매우 큽니다. 모든 상태에 대한 가치함수를 저장해야 하기 때문이죠. 틱택토와 같은 간단한 환경이면 몰라도 오목이나 기타 복잡한 환경에서는 한계가 있습니다. 바둑의 경우의 수는 우주의 원자 수보다도 많다고 하죠. 또한 환경에 대한 정보를 모두 알고있어야 하기 때문에 실생활에 적용하기에는 힘든 아이디어 입니다.

그러나 이를 기반으로 살사, 큐러닝같은 강화학습 알고리즘이 만들어졌기 때문에 이해하고 넘어가야 좋은 부분이라고 생각됩니다.

강화학습 가치함수 큐함수