동적 계획법

1. 개요[편집]

동적 계획법 Dynamic Programming (DP)
창시	리처드 벨만 (1953)
핵심 원리	최적성 원리 (principle of optimality)
성립 조건	최적 부분구조 + 중복 부분문제
대표 알고리즘	가치 반복, 정책 반복, 플로이드-워셜, 비터비
최대 약점	차원의 저주

“부분문제를 두 번 풀었다면, 그건 이미 진 것이다.”

동적 계획법(Dynamic Programming, DP)은 큰 문제를 겹치는 작은 부분문제로 쪼갠 뒤, 각 부분문제의 답을 한 번만 계산해 저장하고 재사용하는 알고리즘 설계 기법이다. 1950년대 초 리처드 벨만(Richard Bellman)이 다단계 의사결정 문제를 다루며 정립했고, 이름의 유래는 수학적 의미가 아니라 예산 심사를 통과하기 위한 작명이었다는 전설이 유명하다.¹

이 문서는 푸는 방법을 다룬다. 무엇을 푸는지 — 상태·행동·전이·보상으로 짜인 문제 자체 — 는 마르코프 결정 과정에 있고, 전이 확률을 모른 채 표본으로 같은 일을 하는 방법론은 강화 학습에 있다. DP는 그 사이에 앉아, 모형을 완전히 알 때 정확해를 계산하는 기준선 역할을 한다.

2. 최적성 원리[편집]

벨만이 남긴 한 문장이 전부다.

최적 정책은 다음 성질을 갖는다: 초기 상태와 초기 결정이 무엇이든, 남은 결정들은 첫 결정으로부터 만들어진 상태에 대해 최적 정책을 이루어야 한다.

풀어 쓰면 — 최적 경로의 부분 경로는 그 자체로 최적이다. 서울에서 부산까지의 최단 경로가 대전을 지난다면, 그 경로의 대전-부산 구간은 반드시 대전에서 부산까지의 최단 경로다. 이게 성립해야 “뒤에서부터 접어 오는” 재귀식을 쓸 수 있다.

DP가 먹히려면 두 조건이 동시에 필요하다.

• 최적 부분구조(optimal substructure) — 위 성질. 이게 깨지는 대표 예가 “가장 긴 단순 경로” 문제로, 부분 경로가 최장이라고 전체가 최장이 되지 않는다.
• 중복 부분문제(overlapping subproblems) — 같은 부분문제가 여러 번 등장해야 저장이 이득이 된다. 부분문제가 매번 새롭다면 그냥 분할정복이고, 저장은 메모리 낭비다.

3. 두 가지 구현과 고전 예제[편집]

같은 재귀식을 구현하는 방향이 둘 있다.

• 하향식 메모이제이션 — 재귀를 그대로 쓰되 계산한 값을 표에 캐싱한다. 실제로 필요한 부분문제만 방문한다는 것이 장점. 상태 공간이 성기게(sparse) 쓰일 때 유리하다.
• 상향식 테이블 채우기 — 의존 순서대로 루프를 돌며 표를 채운다. 재귀 호출 오버헤드와 스택 깊이 걱정이 없고, 메모리 접근이 순차적이라 캐시 친화적이다. 게다가 “현재 행을 채우는 데 이전 행만 필요하다”는 구조면 표를 통째로 들고 있을 필요도 없다(rolling array).

고전 예제 몇 개만 짚으면 감이 온다.

문제	상태	점화식의 성격	복잡도
플로이드-워셜 최단경로	(출발, 도착, 경유 허용 집합)	경유점을 하나씩 개방	$O(V^3)$
비터비 복호	(시각, 은닉상태)	시각축을 따라 최대곱	$O(T \cdot N^2)$
0-1 배낭	(물건 인덱스, 남은 용량)	넣는다 / 안 넣는다	$O(nW)$
편집 거리	(문자열 A 접두, B 접두)	삽입/삭제/치환 중 최소	$O(nm)$

비터비 알고리즘은 특히 이 위키와 궁합이 좋다. 은닉 마르코프 모형에서 가장 그럴듯한 상태열을 찾는 이 알고리즘은, 확률의 곱을 로그 합으로 바꾸면 그냥 층상 그래프 위의 최장경로 DP다. 칼만 필터가 선형-가우시안 세계의 순방향 필터링이라면, 비터비는 이산 상태 세계의 최적 경로 복원인 셈.

4. MDP를 푸는 DP — 가치 반복과 정책 반복[편집]

가치 반복(value iteration)은 벨만 최적 방정식을 그대로 대입 반복으로 돌린다.

$$V_{k+1}(s) = \max_{a} \sum_{s'} P(s' \mid s, a)\left[\, R(s) + \gamma\, V_k(s') \,\right]$$

이 갱신을 연산자 $T$로 보면, $T$는 최대 노름에 대해 $\gamma$-수축 사상이다.

$$\lVert TV - TU \rVert_{\infty} \le \gamma \, \lVert V - U \rVert_{\infty}$$

증명은 한 줄짜리다 — $\max$끼리의 차는 각 항 차의 최대를 넘지 못하고, 확률 가중합은 볼록 조합이라 노름을 키우지 못한다. 바나흐 고정점 정리에 의해 고정점 $V^*$가 유일하게 존재하고, 어떤 초기값에서 출발해도 수렴하며, 오차는 $\gamma^k$로 줄어든다. 위 시뮬레이션 하단의 잔차 스파크라인이 로그 스케일에서 직선이 되는 것이 바로 이 기하급수적 수렴이고, 그 기울기가 $\log_{10}\gamma$다. 초기 추정을 아무렇게나 줘도 되는 반복법이라는 점에서, 수렴성을 보장받는 몇 안 되는 마음 편한 솔버에 속한다.

정책 반복(policy iteration)은 두 단계를 번갈아 돈다. (1) 현재 정책 $\pi$를 고정하고 선형 연립방정식 $V^\pi = R^\pi + \gamma P^\pi V^\pi$를 풀어 정확한 가치를 얻는다(정책 평가 — 여기서 가우스 소거법이나 크리로프 부분공간법이 등장한다). (2) 그 가치로 탐욕 정책을 다시 뽑는다(정책 개선).

정책 반복이 유한 번에 정확히 끝나는 이유가 재미있다. 정책 개선 정리에 의해 매 라운드 정책이 강하게 좋아지고, 결정론적 정상 정책은 최대 $|\mathcal{A}|^{|\mathcal{S}|}$개뿐인 유한 집합이므로, 같은 정책이 두 번 나오지 않는 이상 언젠가 멈춘다. 반면 가치 반복은 원리적으로 무한히 수렴만 할 뿐 정확히 도달하지 않는다.² 실무에서는 둘을 섞은 수정 정책 반복(정책 평가를 몇 스윕만 근사로 하고 개선)이 제일 흔하다.

5. 차원의 저주와 근사 동적 계획법[편집]

DP의 사망 원인은 언제나 같다. 상태 변수가 $d$개이고 각각 $n$개 격자로 이산화되면 상태 수는 $n^d$ — 벨만 본인이 붙인 이름 그대로 차원의 저주다. 관절 6개짜리 로봇 팔의 위치·속도를 각 20단계로 쪼개면 상태가 $20^{12} \approx 4\times10^{15}$개. 표를 저장할 메모리가 지구에 없다.

탈출로는 셋뿐이고, 셋 다 정확성을 판다.

• 함수 근사 — $V(s)$를 표가 아니라 파라미터화된 함수 $V_\theta(s)$로 둔다. 선형 기저, 대리 모델, 가우시안 프로세스, 신경망 순으로 표현력이 올라가고 이론적 보장은 내려간다. 이 계열 전체를 근사 동적 계획법(ADP)이라 부른다.
• 표본 기반 백업 — 모든 $s'$에 대한 기대값 합을 표본 하나로 대체한다. 이 순간 DP는 강화 학습의 시간차 학습이 된다. 몬테카를로 트리 탐색도 관련 상태만 표본으로 훑어 저주를 우회하는 계열이다.
• 구조 활용 — 문제에 특별한 구조(선형 동역학, 이차 비용, 분해 가능성)가 있으면 표 자체를 안 만들어도 된다. 아래 절이 그 이야기.

6. 제어에서의 DP[편집]

제어 이론에서 DP는 다른 이름으로 살아 있다. 상태가 연속이고 동역학이 선형, 비용이 이차형식이면(LQR) 가치함수가 정확히 이차형식 $V(x) = x^\top S x$임을 보일 수 있고, 벨만 방정식은 행렬 하나에 대한 대수 리카티 방정식으로 축약된다.

$$S = A^{\top} S A - A^{\top} S B\left(R + B^{\top} S B\right)^{-1} B^{\top} S A + Q$$

$n^d$개의 표가 $n \times n$ 대칭행렬 하나로 줄어든 것 — 구조를 알면 저주가 사라진다는 가장 극적인 예다. 비선형 시스템에서는 궤적 주변에서 동역학을 선형화하고 비용을 이차 근사한 뒤 LQR을 반복 적용하는 DDP / iLQR이 표준이 됐다. 매 반복이 국소 이차 모형을 푸는 구조라 뉴턴-랩슨법이나 신뢰 영역 방법과 사촌지간이고, 유한 지평선만 최적화한 뒤 첫 입력만 쓰고 다시 푸는 방식이 모델 예측 제어다.

시간 간격을 0으로 보내면 벨만 방정식은 편미분방정식이 된다. 해밀턴-야코비-벨만 방정식이다.

$$-\frac{\partial V}{\partial t} = \min_{u}\left\{\, \ell(x,u) + \nabla_x V \cdot f(x,u) \,\right\}$$

이 방정식은 해밀토니안 역학의 해밀턴-야코비 방정식과 형태가 같고, 실제로 최소작용 원리와 최적성 원리는 같은 뿌리다. 문제는 해가 대개 미분 불가능해서 점성해(viscosity solution) 개념이 필요하고, 수치적으로 푸는 데는 레벨셋 방법류의 편미분방정식 기법이 동원된다는 것.³ 요컨대 DP는 알고리즘 수업의 배낭 문제부터 최적제어의 PDE까지 한 줄로 꿰어져 있다.⁴

7. 관련 문서[편집]

• 마르코프 결정 과정 — DP가 푸는 문제의 정식화
• 강화 학습 — 모형 없이 표본으로 하는 DP
• 몬테카를로 트리 탐색 · 미니맥스 알고리즘
• 반복법 · 수렴성 · 크리로프 부분공간법
• 신뢰 영역 방법 · 뉴턴-랩슨법
• 해밀토니안 역학 · 편미분방정식
• 내비게이션 메시 — 게임 길찾기에서의 최단경로

8. Footnotes[편집]

1. 벨만 본인의 회고에 따르면, 당시 국방부 장관이 “research”라는 단어를 병적으로 싫어해서 수학 연구처럼 들리지 않는 이름이 필요했다고 한다. “dynamic”은 시간에 따라 변한다는 뜻도 담고 있지만, 무엇보다 아무도 반대할 수 없는 형용사였다는 게 선정 이유. 학계 최고의 네이밍 정치 사례로 지금도 인용된다. ↩

2. 다만 $\varepsilon$-최적 정책을 얻는 데 필요한 반복 수가 $O(\log(1/\varepsilon)/(1-\gamma))$로 알려져 있고, 잔차가 $\varepsilon$ 이하면 정책의 가치 손실이 $2\gamma\varepsilon/(1-\gamma)$ 이내라는 깔끔한 정지 조건이 있다. 실무에서는 이 경계로 스윕을 끊는다. ↩

3. HJB를 격자로 직접 풀면 다시 차원의 저주다. 5차원 넘어가면 사실상 불가능해서, 결국 다시 함수 근사로 돌아온다. 인생은 돌고 돈다. ↩

4. 시험 문제로서의 DP는 “점화식을 세우는 것이 90%, 코딩이 10%“라는 말이 있다. 문제는 그 90%가 안 떠오르면 나머지 10%도 못 한다는 것. 상태를 무엇으로 잡을지 정하는 감각은 결국 마르코프 결정 과정에서 “무엇이 충분통계량인가”를 묻는 감각과 정확히 같다. ↩