3. DP (Dynamic Programming)
Known MDP에서 벨만 방정식을 이용해 최적 정책을 찾는 동적 계획법, 정책 반복, 가치 반복을 정리한다.
0. MDP를 푸는 두 가지 접근법: 계획과 학습
앞 글에서 벨만 방정식은 MDP를 풀기 위한 핵심 도구라고 정리했습니다. 그렇다면 MDP를 푼다는 것은 정확히 무엇일까요?
결국 MDP를 푼다는 것은 장기적인 반환값을 최대로 만드는 최적 정책($\pi^{\ast}$)을 찾는 것입니다. 이때 우리가 환경 모델을 알고 있는지에 따라 접근법이 크게 둘로 나뉩니다.
0.1 모델 기반 (Model-Based) 접근법
모델 기반 접근법은 환경의 규칙, 즉 상태 전이 확률($P$)과 보상 함수($R$)를 알고 있거나 먼저 추정한 뒤 문제를 푸는 방식입니다.
환경 모델을 알고 있으므로 실제로 행동을 해보기 전에 계산을 통해 최적 가치 함수와 정책을 찾을 수 있습니다. 이런 과정을 계획(Planning)이라고 부르며, 이번 글에서 다룰 동적 계획법(Dynamic Programming, DP)이 대표적인 방법입니다.
0.2 모델 프리 (Model-Free) 접근법
모델 프리 접근법은 환경의 규칙을 모르는 상태에서 시작합니다. 에이전트가 직접 행동하고, 보상을 받고, 다음 상태를 관찰하면서 경험을 쌓아 가치 함수나 정책을 학습합니다.
Q-Learning, SARSA, DQN 같은 알고리즘들이 여기에 속합니다. 이 내용은 다음 글에서 본격적으로 다루고, 이번 글에서는 환경 모델을 알고 있는 Known MDP에 집중합니다.
1. 동적 계획법 (Dynamic Programming)이란?
동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 작은 하위 문제들로 나누고, 그 결과를 재사용하여 전체 문제를 푸는 최적화 기법입니다.
강화학습에서는 환경 모델을 알고 있는 Known MDP에서 벨만 방정식을 이용해 최적 가치 함수와 최적 정책을 계산하는 계획 기법으로 사용됩니다.
1.1 DP의 핵심 아이디어
DP의 이름은 다소 오해의 소지가 있습니다.
- Dynamic (동적): 시간이 흐름에 따라 상태가 변하는 순차적인 문제를 의미합니다.
- Programming (계획법): 코딩이 아니라 표(table)를 채우며 해를 계산하는 계획 절차를 의미합니다.
DP는 벨만 방정식을 기반으로 현재의 가치 추정치를 이용해 더 나은 가치 추정치를 반복적으로 계산합니다. 이렇게 자신의 추정값을 다시 업데이트에 사용하는 방식을 부트스트래핑(Bootstrapping)이라고 합니다.
1.2 DP의 가장 중요한 전제 조건: 완벽한 환경 모델
DP를 사용하려면 환경의 규칙을 알고 있어야 합니다. 즉, 문제는 Known MDP여야 합니다.
- 상태 전이 확률($P(s^{\prime} \mid s, a)$): 상태 $s$에서 행동 $a$를 했을 때 다음 상태 $s^{\prime}$로 이동할 확률
- 보상 함수($R(s, a)$): 상태 $s$에서 행동 $a$를 했을 때 받을 보상
이 두 정보를 알고 있으면 에이전트가 직접 시행착오를 겪지 않아도 벨만 방정식을 이용해 최적 정책을 계산할 수 있습니다. 이것이 경험을 통해 배우는 Model-Free 강화학습과 DP를 구분하는 가장 큰 차이입니다.
이제 DP를 구현하는 대표적인 두 방법인 정책 반복(Policy Iteration)과 가치 반복(Value Iteration)을 보겠습니다.
2. 정책 반복 (Policy Iteration)
정책 반복은 현재 정책을 평가하고, 그 평가 결과를 바탕으로 정책을 개선하는 과정을 반복해서 최적 정책에 도달하는 방법입니다.
- 정책 평가(Policy Evaluation): 현재 정책 $\pi$를 따를 때 각 상태가 얼마나 가치 있는지 계산합니다.
- 정책 개선(Policy Improvement): 평가된 가치 함수를 바탕으로, 각 상태에서 더 좋은 행동을 선택하도록 정책을 업데이트합니다.
이 두 과정을 반복하면 정책은 점점 좋아지고, 최종적으로 최적 정책에 도달합니다.
2.1 정책 개선 정리 (Policy Improvement Theorem)
정책 반복이 작동하는 이유는 정책 개선 정리 때문입니다. 이 정리는 현재 정책 $\pi$의 가치 함수를 기준으로 탐욕적으로 만든 새로운 정책 $\pi^{\prime}$이 기존 정책보다 나빠지지 않는다는 것을 보장합니다.
즉, 모든 상태에서 다음 관계가 성립합니다.
\[v_{\pi^{\prime}}(s) \ge v_\pi(s)\]따라서 평가와 개선을 반복하면 정책은 점점 좋아지고, 더 이상 개선되지 않는 지점에서 최적 정책에 도달합니다.
2.2 정책 반복 (Policy Iteration)의 예시
이 Grid World 예제는 무작위 정책에서 시작해 최적 정책으로 수렴하는 과정을 보여줍니다.
가정은 단순합니다. 각 행동의 보상은 -1이고, 목표 지점에 도달하면 에피소드가 종료됩니다.
2.2.1 정책 평가 (Policy Evaluation) 과정 (왼쪽 열 $V_k$)
왼쪽 열은 현재 정책의 가치 함수가 어떻게 계산되는지 보여줍니다.
- k = 0: 모든 상태의 가치를 0으로 초기화하며 시작합니다.
- k = 1: 벨만 기대 방정식을 한 번 적용합니다. 목표 지점 바로 옆 상태들은 목표까지 한 번에 도달할 수 있으므로 가치가 먼저 갱신됩니다.
- k = 2, 3, 10, …: 반복이 늘어날수록 목표 근처의 가치 정보가 점점 멀리 전파됩니다.
- $k = \infty$: 충분히 반복하면 현재 정책에 대한 참 가치 함수 $v_\pi$로 수렴합니다.
2.2.2 정책 개선 (Policy Improvement) 과정 (오른쪽 열, greedy policy)
오른쪽 열은 계산된 가치 함수를 보고 더 나은 정책을 만드는 과정입니다.
- Greedy Policy: 각 상태에서 다음 상태의 가치가 가장 높아지는 행동을 선택합니다.
- 정책의 발전:
- $k = 1$일 때는 가치 함수가 아직 거칠지만, 정책은 목표 방향을 조금씩 반영합니다.
- $k$가 커질수록 가치 함수가 정교해지고, 그에 따라 탐욕 정책도 최적 정책에 가까워집니다.
- 최적 정책 도달: 수렴한 가치 함수 $v_\infty$를 기준으로 탐욕 정책을 만들면 최적 정책($\pi^{\ast}$)에 도달합니다.
2.2.3 결론: 이 그림이 보여주는 것
이 예시는 정책 반복의 핵심 흐름을 잘 보여줍니다.
- 평가: 하나의 정책을 고정하고 그 정책의 가치를 계산합니다.
- 개선: 계산된 가치 함수를 바탕으로 더 나은 탐욕 정책을 만듭니다.
평가와 개선을 반복할수록 정책은 점점 좋아지고, 결국 최적 정책에 수렴합니다.
정책의 조기 수렴: 중요한 시사점
그림에서 주목할 점은 정책이 가치 함수보다 빨리 안정될 수 있다는 것입니다. 예를 들어 정책은 이미 최적에 가까워졌는데, 정책 평가 단계는 원칙적으로 가치 함수가 충분히 수렴할 때까지 계속됩니다. 이 부분은 계산 비용 측면에서 비효율이 될 수 있습니다.
이 비효율을 줄이려는 아이디어가 바로 가치 반복(Value Iteration)으로 이어집니다.
2.3 정책 반복 (Policy Iteration)의 장점과 단점
- 장점: 정책 자체는 비교적 빠르게 수렴하는 경우가 많습니다. 상태 공간이 작고 정책 평가 비용이 크지 않다면 효율적입니다.
- 단점: 매 반복마다 정책 평가를 충분히 수행해야 하므로 한 번의 반복이 무거울 수 있습니다. 상태 공간이 커질수록 계산 부담이 커집니다.
이 문제를 완화하기 위해 정책 평가와 정책 개선을 더 가볍게 섞은 수정된 정책 반복(Modified Policy Iteration) 같은 방법도 사용됩니다.
3. 가치 반복 (Value Iteration)
가치 반복은 정책 평가와 정책 개선을 한 단계로 합친 방법입니다. 현재 정책을 명시적으로 평가하기보다, 곧바로 최적 가치 함수($v^{\ast}$)를 향해 값을 업데이트합니다.
업데이트 규칙은 벨만 최적 방정식을 그대로 사용합니다. 각 상태에서 가능한 행동 중 가장 큰 가치를 주는 행동을 기준으로 상태 가치를 갱신합니다.
이 과정을 반복하면 가치 함수는 최적 가치 함수($v^{\ast}$)로 수렴합니다. 수렴한 뒤에는 이 가치 함수를 기준으로 최선의 행동을 선택하여 최적 정책을 얻을 수 있습니다.
3.1 가치 반복 (Value Iteration)의 예시
3.1.1 가치 반복의 과정: 최적 가치 함수($v^{\ast}$)의 발견
가치 반복은 벨만 최적 방정식을 반복적으로 적용하여 최적 가치 함수($v^{\ast}$)를 찾아갑니다.
- 초기 상태: 모든 상태의 가치를 0으로 시작합니다.
- 반복 업데이트: 각 상태에서 가능한 행동들을 비교하고, 가장 큰 값을 주는 행동을 기준으로 가치를 갱신합니다.
- 결과: 반복이 충분히 진행되면 목표에 가까운 상태는 높은 가치, 함정에 가까운 상태는 낮은 가치를 갖게 됩니다.
3.1.2 최적 정책($\pi^{\ast}$)의 도출: 왜 Q-value가 유용한가?
최적 가치($v^{\ast}$)를 찾은 뒤에는 각 상태에서 어떤 행동을 선택할지 결정해야 합니다. 이때 $v$ 값과 $q$ 값의 차이가 드러납니다.
- V-value에서 정책 찾기: 상태 가치($v^{\ast}$)만으로는 최적 행동을 바로 알 수 없습니다. 각 행동이 어떤 다음 상태로 이어지는지 환경 모델을 이용해 계산해야 합니다.
- Q-value에서 정책 찾기: 행동 가치($q^{\ast}$)는 상태와 행동의 조합에 대한 가치를 직접 담고 있습니다. 따라서 각 상태에서 가장 큰 Q값을 가진 행동을 고르면 됩니다.
다만 Q-value는 행동별 값을 모두 저장해야 하므로, 행동 공간이 커질수록 테이블이나 함수 근사의 부담도 함께 커집니다.
3.1.3 결론: 본문 내용과의 연결
이 예시는 가치 반복의 핵심을 보여줍니다.
- 가치 반복은 최적 상태 가치 함수($v^{\ast}$)를 찾아갑니다.
- $q^{\ast}$를 알면 각 상태에서 가장 좋은 행동을 더 직접적으로 선택할 수 있습니다.
- Q-Table은 상태-행동 쌍의 가치를 표 형태로 저장한 것입니다.
3.2 가치 반복 (Value Iteration)의 장점과 단점
장점: 가치 반복은 구현이 단순하고 한 번의 반복이 비교적 가볍습니다. 정책을 따로 평가하지 않고 벨만 최적 방정식으로 바로 값을 갱신하기 때문입니다.
단점: 가치 함수가 점진적으로 수렴하기 때문에, 실제로는 정책이 이미 안정되었는데도 값의 미세한 변화 때문에 반복을 계속할 수 있습니다. 또한 종료 조건을 어떻게 잡을지도 중요합니다. 기준이 너무 엄격하면 오래 걸리고, 너무 느슨하면 충분히 좋은 정책을 얻기 전에 멈출 수 있습니다.
정책 반복은 정책 수렴이 빠른 대신 한 번의 반복이 무겁고, 가치 반복은 한 번의 반복이 가벼운 대신 값이 충분히 수렴할 때까지 반복해야 합니다. 두 방법 모두 유한한 상태-행동 공간에서는 최적 정책으로 수렴함이 보장됩니다.
4. 정리하며: 다음 단계로
이번 글에서는 Known MDP에서 벨만 방정식을 이용해 최적 정책을 계산하는 DP를 정리했습니다.
- DP는 환경 모델($P$, $R$)을 알고 있을 때 사용하는 계획 방법입니다.
- 정책 반복은 정책 평가와 정책 개선을 반복합니다.
- 가치 반복은 벨만 최적 방정식으로 값을 직접 갱신합니다.
- 두 방법 모두 최적 정책에 수렴하지만, 계산 비용과 반복 방식에서 차이가 있습니다.
하지만 현실에서는 상태 전이 확률과 보상 함수를 정확히 모르는 경우가 훨씬 많습니다. 다음 글에서는 이런 Unknown MDP에서 경험을 통해 가치를 학습하는 강화학습 방법들을 살펴보겠습니다.