MDP를 완전히 아는 상황, 즉 전이와 보상을 알 때 최적 정책을 계산하는 방법이 동적 계획법(DP)이다. 환경과 상호작용하지 않고 모델만으로 답을 구하므로 계획(planning)이라 부른다. DP가 통하는 이유는 벨만 방정식이 문제를 부분 문제로 쪼개고(최적성 원리), 그 부분해를 가치함수에 저장해 재사용할 수 있기 때문이다.
강의 슬라이드: PDF
동적 계획법이란
이름부터 오해를 부른다. 여기서 “계획법(programming)“은 코드를 짜는 프로그래밍이 아니라, 선형계획법처럼 최적해를 찾는 수학적 최적화를 뜻한다. “동적(dynamic)“은 시간에 걸친 순차적 문제라는 뜻이다. 이름을 붙인 리처드 벨만은, 수학 연구를 못마땅해하던 당시 국방장관의 눈을 피하려고 일부러 그럴듯하고 시비 걸기 힘든 이름을 골랐다는 유명한 뒷이야기가 있다. 그러니 이름의 무게에 겁먹을 필요는 없다.
핵심 아이디어는 단순하다. 큰 문제를 작은 부분 문제로 쪼개 풀고, 그 답을 합쳐 큰 문제를 푼다. 이게 통하려면 두 조건이 필요하다.
- 최적 부분 구조: 전체의 최적해가 부분 문제의 최적해로 쪼개진다(최적성 원리).
- 겹치는 부분 문제: 같은 부분 문제가 여러 번 나타나, 한 번 푼 답을 저장해 재사용할 수 있다.
MDP는 이 둘을 정확히 만족한다. 벨만 방정식이 “지금 상태의 답 = 지금 보상 + 다음 상태들의 답"이라는 재귀 분해를 주고(최적 부분 구조), 그 부분해를 가치함수라는 표에 적어 두고 이웃을 계산할 때마다 다시 꺼내 쓴다(겹치는 부분 문제). 피보나치를 손으로 셀 때 앞의 값을 메모해 두면 지수 시간이 다항 시간으로 줄듯, 여기서도 가치를 메모하는 순간 계산이 감당할 만해진다.
그래서 DP는 강화학습의 가장 이상적인 경우다. 환경(전이와 보상)을 완벽히 안다는 전제 아래, 벨만 방정식을 반복해 풀기만 하면 최적 정책이 나온다. 앞으로의 강들은 이 완벽한 지식을 하나씩 걷어내며, 그래도 배울 수 있는지를 묻는다.
정책 평가
주어진 정책 $\pi$의 가치 $v_\pi$를 구하는 문제다(예측). 벨만 기대 방정식을 갱신 규칙으로 바꿔 반복한다.
$$v_{k+1}(s) = \sum_a \pi(a\mid s)\left(\mathcal{R}_s^a + \gamma\sum_{s'}\mathcal{P}_{ss'}^a\, v_k(s')\right)$$모든 상태를 한꺼번에 갱신하는 동기 백업으로 $k$를 키우면 $v_\pi$로 수렴한다.
실버의 예는 작은 격자 세계다. 4×4 격자에서 양 끝 두 칸이 종료 상태이고, 한 걸음마다 −1의 보상을 준다. 상하좌우를 무작위로 고르는 정책을 두고 반복 평가를 돌리면, 처음엔 다 0이던 가치가 반복할수록 종료에서 멀수록 더 큰 음수로 자리 잡는다. 몇 번만 돌려도 “어느 칸이 종료에서 얼마나 먼가"라는 지도가 드러난다.
좌상단과 우하단이 종료 상태, 한 걸음마다 −1이다. “한 번 반복"을 누를 때마다 모든 칸이 동시에 갱신되며 가치가 수렴해 간다. 화살표는 그 시점의 탐욕 정책이다. 놀랍게도 정책 화살표는 가치가 완전히 수렴하기 훨씬 전에 이미 최적이 된다. 모드를 “가치 반복"으로 바꾸면 최댓값으로 갱신하는 버전을 볼 수 있다.
재미있는 점 하나. 이 평가만으로도, 각 칸에서 가치가 높은 이웃으로 가는 탐욕 정책을 뽑으면 이미 최적 정책이 되어 있곤 한다. 평가와 개선이 자연스럽게 이어지는 대목이다.
정책 반복
최적 정책을 찾는 문제다(제어). 평가와 개선을 번갈아 한다.
- 평가: 현재 정책의 $v_\pi$를 구한다.
- 개선: $v_\pi$에 대해 탐욕적으로 새 정책을 만든다. $\pi'(s) = \arg\max_a q_\pi(s,a)$.
개선된 정책은 결코 나빠지지 않는다(정책 개선 정리). 이 두 단계를 번갈아 하면 최적 정책 $\pi_*$로 수렴한다.
실버가 드는 정책 반복의 예는 잭의 렌터카다. 두 영업소를 오가며 밤사이 차를 옮기고(옮기는 데 대당 비용), 낮에 빌려주면 수입이 생긴다. 수요와 반납은 확률적(푸아송)이다. 정책 반복을 돌리면 “각 영업소에 차가 몇 대일 때 몇 대를 옮길까"라는 정책 지도가, 반복할수록 또렷한 계단 모양으로 다듬어진다.
평가와 개선을 꼭 끝까지 번갈아 할 필요는 없다. 위 격자에서 봤듯 평가를 몇 번만 하고 개선해도, 아예 한 번만 하고 개선해도 수렴한다. 이렇게 평가와 개선을 어떤 식으로 섞어도 최적으로 모이는 큰 그림을 일반화된 정책 반복(GPI)이라 부른다. 앞으로 나올 거의 모든 강화학습 방법이 이 GPI의 변주다.
가치 반복
정책을 명시적으로 두지 않고 벨만 최적 방정식을 바로 반복한다.
$$v_{k+1}(s) = \max_a\left(\mathcal{R}_s^a + \gamma\sum_{s'}\mathcal{P}_{ss'}^a\, v_k(s')\right)$$$v_*$로 수렴하고, 마지막에 탐욕 정책을 뽑으면 그것이 최적 정책이다. 평가를 한 번씩만 하고 곧바로 최댓값을 취하는 셈이라 정책 반복보다 간결하다. 다만 중간 가치가 어떤 실제 정책의 가치가 아닐 수도 있다는 점이 다르다.
직관은 최단 경로 찾기와 같다. 종료(목표) 칸의 가치는 확실하다. 거기서 한 걸음 떨어진 칸, 두 걸음 떨어진 칸으로 정확한 값이 물결처럼 번져 나간다. 반복 한 번이 이 물결을 한 칸씩 넓히는 셈이다. 격자에서 가치 반복을 돌려 보면 목표 주변부터 값이 자리 잡고, 그 파문이 바깥으로 퍼지는 게 눈에 보인다.
왜 수렴하는가
벨만 연산자는 $\gamma$-축약 사상이다. 반복하면 두 가치함수 사이 거리가 매번 $\gamma$배로 줄어, 유일한 고정점으로 수렴한다. 그 고정점이 참 가치함수다. 정책 평가와 정책 반복과 가치 반복이 모두 같은 이유로 수렴한다.
정리와 한계
세 방법 모두 상태 가치 $v$에 기반하고, 매 반복이 전체 상태를 훑는 동기 백업이다. 상태가 많으면 이 한 번의 훑기가 비싸므로, 실버는 필요한 상태만 갱신하는 비동기 DP도 짚는다. 자리에서 바로 덮어쓰기(in-place), 오차가 큰 상태를 먼저 갱신하기(우선순위 스위핑), 에이전트가 실제로 밟는 상태부터 갱신하기(실시간 DP) 같은 변형이다.
그리고 DP의 갱신은 전폭 백업이다. 한 상태를 갱신할 때 갈 수 있는 모든 다음 상태를 빠짐없이 고려한다. 정확하지만 분기 수만큼 비싸고, 전이를 알아야 한다. 다음 강의 모델 프리 방법은 이 자리에 표본 백업을 놓는다. 실제로 겪은 다음 상태 하나만 써서 갱신하는 것이다. 싸고, 모델이 필요 없고, 큰 문제로 확장된다.
DP는 강력하지만 두 가지가 발목을 잡는다. 전이와 보상을 알아야 하고, 상태 수에 비례해 계산이 는다. 다음 강부터는 환경 모델을 모르는 채, 경험만으로 배우는 모델 프리 방법으로 넘어간다.