[RL] 3. DP: policy iteration, value iteration

이전 글에서 벨만 방정식에 대해 살펴봤다.

벨만 방정식은 상태 가치 함수를 연립 방정식으로 풀 수 있게 해줬다.

 

하지만, 상태와 행동의 수가 조금이라도 많아지면 감당할 수 없게 된다.

 

DP(Dynamic Programming) 기법을 사용하면 위 한계점을 어느정도 해결할 수 있다.

다시 말해, DP을 사용하면 상태와 행동의 수가 어느정도 많아져도 가치 함수를 구할 수 있다.

 

참고로, DP의 핵심은 1. 중복 계산 방지와 2. 부분 문제로 나누어 푸는 것이다.

---

강화학습에서는 일반적으로 두 가지 문제를 해결해야 한다. 바로, 정책 평가(policy evaluation)와 정책 제어(policy control)다.

정책 평가는 정책 $\pi$의 가치 함수 $v_\pi(s)$, $q_\pi(s, a)$를 구하는 문제고,

정책 제어는 정책 $\pi$를 조정해 최적 정책으로 발전시키는 문제다. 

 

MDP의 목표는 최적 정책을 찾는 것이다. 그러기 위해선, 정책 제어로 정책을 개선시켜야 한다.

하지만, 일반적으로 정책 평가를 진행한 후에 정책 제어로 정책을 개선시킨다.

그래서, 정책 제어 방법 전에 DP로 정책을 평가하는 방법에 대해 알아볼 것이다.

 

물론, 벨만 최적 방정식을 만족하는 연립방정식을 풀어 최적 정책을 직접 구하는 방법도 있다.

하지만, 계산량이 터무니없이 많다. 상태의 크기가 $S$ 행동의 크기가 $A$라고 할 때, $A^S$만큼의 계산이 필요하다.

---

반복적 정책 평가(iterative policy evaluation)

DP로 가치 함수를 구하는 핵심 아이디어는 부트스트래핑(bootstrapping)이다.

벨만 방정식을 갱신식으로 변형한 후, 추정치로 추정치를 개선하는 부트스트래핑을 사용해 가치 함수를 구한다.

 

벨만 방정식으로 갱신식으로 변형하는 과정은 다음과 같다.

$$v_\pi(s) = \sum_a \pi(a|s)\left(R_s^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a v_\pi(s^\prime)\right) \rightarrow V_{k+1}(s) = \sum_a \pi(a|s)\left(R_s^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a V_k(s^\prime)\right)$$

우측 갱신식처럼, 추정치 $V_\pi$를 반복적으로 개선하면 $v_\pi$에 수렴한다는 사실은 이미 증명되었다.

 

갱신식으로 부트스트래핑하여 가치 함수를 구하는 알고리즘은 다음과 같다.

 

 

알고리즘에서 확인할 수 있듯이 효율을 위해, 최대 갱신 크기 $\delta$가 임곗값(threshold) $\epsilon$ 밑으로 떨어질 때까지만 반복한다.

(참고로, 일화성 과제일 때 목표 상태의 가치 함수는 0이다. 목표 지점에 도달하면 에피소드가 끝나고 다음 전개가 없기 때문이다.)

정책 반복법(policy iteration)

지금까지 DP로 정책을 평가하는 방법 즉, 반복적 정책 평가 알고리즘에 대해 알아봤다.

이제부터 정책을 개선하는 방법에 대해 살펴볼 것이다.

 

정책을 개선하는 힌트는 "최적 정책"과 "최적 상태 가치 함수"의 관계에서 찾을 수 있다.

$$\mu_*(s) = \underset{a}{\text{argmax }}R_s^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a v_*(s^\prime)$$

위 수식에 최적 정책 $\mu_*$ 대신 임의의 결정적 정책 $\mu$를 대입해보자.

$$\mu^\prime(s) = \underset{a}{\text{argmax }}R_s^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a v_\mu(s^\prime)$$

그럼, 정책이 $\mu$에서 $\mu^\prime$으로 정책이 갱신된다. 위와 같은 정책 갱신을 "탐욕화"라고 부른다.

 

탐욕화된 정책 $\mu^\prime$에는 두 가지 특징이 있다.

1. $\forall s(v_{\mu^\prime}(s) = v_\mu(s))$이면, $\mu(s)$는 이미 최적 정책이다. $\mu(s) = \underset{a}{\text{argmax }} q_\mu(s, a)$을 만족하기 때문이다.

2. $\mu^\prime$은 $\mu$보다 개선된 정책($\forall s(v_{\mu^\prime}(s) \ge v_\mu(s))$)이다.

이 사실은 개선 정리(policy improvement theorem)에 의해 밝혀졌다. 

결론, 탐욕화로 정책 개선을 할 수 있다.

 

반복적 정책 평가와 탐욕화로 최적 정책을 구하는 알고리즘은 다음과 같다.

 

 

환경 모델이 알려져 있다면 에이전트는 아무런 행동 없이 가치 함수를 평가할 수 있다. 즉, 정책 반복법으로 최적 정책도 찾을 수 있다.

이처럼, 에이전트가 실제 행동을 하지 않고 최적 정책을 찾는 문제를 계획 문제(planning problem)라고 한다.

반면, 대부분의 경우 환경 모델을 알 수 없기 때문에 에이전트가 실제로 행동을 취해 경험 데이터를 쌓으면서 최적 정책을 찾아야 한다.

가치 반복법(value iteration)

우선, 일반화한 정책 반복(generalized policy iteration)이 무엇인지 살펴보자.

"일반화한 정책 반복"은 평가를 완전히 끝내기 전에 개선 단계로 전환하고, 개선을 완전히 끝내기 전에 평가 단계로 전환하는 알고리즘이다.

 

그런 면에서, 정책 반복법은 평가와 개선을 각각 "최대한"으로 하고 번갈아 수행하는 알고리즘이다.

즉, 정책 반복법을 일반화 정책 반복의 한 종류로 볼 수 있다.

 

반면, 가치 반복법은 평가와 개선을 각각 "최소한"으로 수행하는 알고리즘이다.

구체적으로, 가치 반복법은 개선 단계에서 상태 하나만 개선하고 곧장 평가 단계로 넘어간다. 평가 단계에서도 해당 상태 하나의 가치 함수를 한 번만 갱신한다. (참고로, 어느 단계를 먼저 진행하던 상관없다.)

 

가치 반복법의 개선 단계도 "탐욕화"를 사용한다.

$$\mu^\prime(s) = \underset{a}{\text{argmax }}R_s^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a V(s^\prime)$$

물론, 반복적 정책 평가 알고리즘으로 정책을 평가한다.

$$V_{k+1}(s) = \sum_a \pi(a|s)\left(R_s^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a V_k(s^\prime)\right)$$

 

개선 단계에서 탐욕 행동을 찾아 정책을 개선하고, 평가 단계에서 찾은 탐욕 행동으로 정책을 평가한다.

이때 놀랍게도, 개선 단계와 평가 단계에서 똑같은 계산을 수행하고 있음을 알 수 있다.

이를 하나로 묶으면 다음과 같이 표현할 수 있다.

$$V_{k+1}(s) = \underset{a}{\max} \left(R_s^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a V_k(s^\prime)\right)$$

$\max$로 정책 등장 없이 정책을 개선시킴과 동시에 평가를 수행했다.

 

해당 갱신식을 무한히 반복하면 최적 가치 함수를 구할 수 있다.

알고리즘은 다음과 같다.

 

 

이때도 알고리즘에서 확인할 수 있듯이 효율을 위해, 최대 갱신 크기 $\delta$가 임곗값(threshold) $\epsilon$ 밑으로 떨어질 때까지만 반복한다. 이후, 반복문이 끝나면 $\mu_*(s) \leftarrow \underset{a}{\text{argmax }}R_s^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a V_*(s^\prime)$로 최적 정책을 찾는다.

 

 

정책 반복법과 가치 반복법 모두 갱신식을 사용하기 때문에 DP 알고리즘에 속한다고 본다.

구체적으로, $V_i$를 구하기 위해선, $V_{i-1}$이 있어야 한다. 이때, 이를 미리 저장해놔 중복 계산을 방지했다. 따라서 DP 알고리즘에 속한다고 볼 수 있다.