[강화학습] 가치 반복과 정책 반복

정책 반복(Policy Iteration)

정의 및 과정 설명

정책 반복은 강화학습에서 주어진 환경의 최적 정책을 찾기 위한 방법 중 하나입니다. 이 방법은 크게 두 단계로 나눌 수 있습니다.

정책 평가

정책 평가 단계에서는 현재의 정책 하에서 각 상태의 가치를 계산합니다. 이는 벨만 기대 방적식을 사용하여 수행됩니다. 수식으로 표현하면 다음과 같습니다:

V^\pi(s) = \sum_{a \in A} \pi(a|s) \sum_{s', r} P(s', r | s, a)[r + \gamma V^\pi(s')]

여기서 $V^\pi(s)$ 는 상태 $s$ 에서 정책 $\pi$ 를 따랐을 때의 가치이며, $\pi(a|s)$ 는 상태 $s$ 에서 행동 $a$ 를 선택할 정책의 확률입니다. $P(s', r | s, a)$ 는 상태 $s$ 에서 행동 $a$ 를 취했을 때 상태 $s'$ 로 이동하고 보상 $r$ 을 받을 확률입니다.

정책 개선

정책 개선 단계에서는 계산된 가치를 기반으로 현재 정책을 개선하여 더 좋은 정책을 만듭니다. 모든 상태에 대해 다음과 같이 새로운 정책을 선택합니다:

\pi'(s) = \arg\max_a \sum_{s', r} P(s', r | s, a)[r + \gamma V^\pi(s')]

새로운 정책 $\pi'$ 는 현재 가치 함수를 최대화하는 행동을 선택합니다.

정책 반복 알고리즘 작동 원리

정책 반복은 정책 평가와 정책 개선을 반복하면서 최적 정책을 찾아갑니다. 일반적으로 초기에 임의의 정책에서 시작하여, 정책 평가를 통해 현재 정책의 가치 함수를 계산하고, 그 가치 함수를 기반으로 정책 개선을 진행합니다. 이 과정을 정책의 변화가 없을 때까지 반복합니다.

정책 반복의 장점과 한계

장점:

정확성: 반복을 거듭하면 최적 정책에 수렴합니다.
계산 효율성: 많은 상황에서 가치 반복에 비해 빠른 수렴을 보입니다.

한계:

정책 평가 단계에서 모든 상태의 가치를 정확히 계산해야 하는데, 이는 상태 공간이 매우 큰 문제에서 계산 부담이 될 수 있습니다.

가치 반복(Value Iteration)

정의 및 과정 설명

가치 반복은 강화학습에서 최적 가치 함수를 추정하고, 이를 바탕으로 최적 정책을 도출하는 방법입니다. 기본적으로 가치 함수를 직접 반복적으로 개선하여 최적 가치 함수를 찾아내는 과정으로 구성됩니다.

가치 함수의 근사를 통해 최적의 가치 함수 추정

V_{k+1}(s) = \max_a \sum_{s', r} P(s', r | s, a)[r + \gamma V_k(s')]

이 수식은 각 상태에 대해 가치 함수를 최대화하는 행동을 선택함으로써 가치 함수를 반복적으로 개선합니다.

최적 가치 함수를 바탕으로 최적 정책 도출

최적 가치 함수가 수렴한 뒤, 다음과 같은 방정식을 사용하여 최적 정책을 도출할 수 있습니다:

\pi^*(s) = \arg\max_a \sum_{s', r} P(s', r | s, a)[r + \gamma V^*(s')]

여기서 $V^*$ 는 최적 가치 함수입니다.

가치 반복 알고리즘 작동 원리

가치 반복은 각 반복에서 모든 상태에 대해 가치 함수를 업데이트함으로써 작동합니다. 이 업데이트는 모든 가능한 행동을 고려하여 해당 상태의 기대 리턴을 최대화하는 방식으로 진행됩니다. 반복이 충분히 이루어지면 가치 함수는 최적 가치 함수에 수렴하고, 이를 통해 최적 정책을 도출할 수 있습니다.

가치 반복의 장점과 한계

장점:

구현의 단순성: 가치 반복은 정책 평가와 정책 개선을 명시적으로 분리하지 않으므로 구현이 비교적 간단합니다.
빠른 수렴: 가치 함수가 직접 업데이트되므로 일반적으로 수렴 속도가 빠릅니다.

한계:

근사값의 사용: 가치 함수의 업데이트가 근사적이기 때문에, 경우에 따라 정책 반복에 비해 최적 정책을 찾는데 더 많은 반복이 필요할 수 있습니다.
계산 부담: 상태 공간이 매우 클 경우, 모든 상태에 대해 최대화 계산을 수행해야 하므로 계산 비용이 매우 높을 수 있습니다.