§ 1동적 프로그래밍이란 무엇인가
동적 프로그래밍(Dynamic Programming, DP)은, 환경의 완벽한 모델이 마르코프 결정 과정(MDP)으로 주어졌을 때 최적 정책을 계산하는 알고리즘 가족을 일컫는다.
고전적 DP는 두 가지 강한 가정 — 완벽한 모델, 그리고 막대한 계산 — 때문에 실제 강화학습에서 직접 쓰이는 일은 드물다. 그럼에도 DP는 이론적으로 결정적으로 중요하다. DP는 이 책 나머지 모든 방법을 이해하기 위한 필수 기초다. 사실, 이후의 모든 방법은 더 적은 계산으로, 완벽한 모델 없이, DP와 같은 효과를 내려는 시도로 볼 수 있다.
3장의 벨만 (최적) 방정식은 가치 함수가 만족해야 할 일관성 조건이었다. DP의 핵심 발상은 단순하다 — 이 방정식을 할당문(assignment)으로, 즉 원하는 가치 함수의 근사를 개선하는 갱신 규칙(update rule)으로 바꾸는 것이다.
그리고 DP의 — 나아가 강화학습 전체의 — 핵심 아이디어는: 가치 함수를 사용해 좋은 정책을 찾는 탐색을 조직하고 구조화하는 것이다.
우리는 환경이 유한 MDP라고 가정한다 — 상태·행동·보상 집합 𝒮, 𝒜, 𝓡이 유한하고, 동역학이 확률들의 집합 p(s′,r|s,a)로 주어진다. 이 장에서 다룰 작업은 둘로 갈린다: 주어진 정책의 가치를 구하는 예측(prediction), 그리고 더 나은 정책을 찾는 제어(control).
§ 2정책 평가 — 정책의 가치를 반복으로 구하다
먼저 임의의 정책 π에 대한 상태-가치 함수 vπ를 계산하는 일을 보자. DP 문헌에서 이를 정책 평가(policy evaluation)라 부르며, 예측 문제라고도 한다.
환경의 동역학을 완전히 안다면, vπ에 대한 벨만 방정식은 |𝒮|개의 미지수에 대한 |𝒮|개의 연립 선형 방정식이다. 원리상 직접 풀 수 있지만, 우리 목적에는 반복적 해법(iterative solution)이 가장 알맞다.
각 갱신은 상태 s의 옛 값을, s의 후속 상태들의 옛 값과 그 길의 기대 보상으로부터 얻은 새 값으로 대체한다. 이런 연산을 기대 갱신(expected update)이라 부른다 — 표본 하나가 아니라 가능한 모든 다음 상태에 대한 기댓값을 쓰기 때문이다. 이렇게 모든 상태를 한 차례 훑는 것을 한 번의 스윕(sweep)이라 한다.
위 모션은 4×4 그리드월드다 — 두 모서리가 종료 상태이고, 매 이동마다 보상 −1이며, 정책은 네 방향을 같은 확률로 고르는 무작위 정책이다. 스윕을 거듭할수록 가치 추정치가 안정된 vπ로 가라앉는다. 각 칸의 색은 가치(낮을수록 붉음, 높을수록 푸름)를 나타낸다.
§ 3정책 개선과 정책 반복
정책의 가치 함수를 구하는 까닭은 — 더 나은 정책을 찾기 위해서다. 결정론적 정책 π에 대해 vπ를 구했다고 하자. 어떤 상태 s에서, 정책이 정한 행동 π(s) 대신 다른 행동 a를 고르도록 바꾸는 것이 나을까?
답을 보는 한 가지 방법: s에서 a를 한 번 고른 뒤 그 후로는 기존 정책 π를 따른다고 하자. 그 가치가 바로 qπ(s, a)다. 핵심 기준은 — 이것이 vπ(s)보다 큰가? 더 크다면, s를 마주칠 때마다 a를 고르는 것이 더 낫고, 새 정책이 전반적으로 더 나은 정책이 되리라 기대할 수 있다.
그렇다면 자연스러운 다음 걸음은 — 한 상태가 아니라 모든 상태에서, 모든 행동에 대해 변경을 고려하는 것이다. 각 상태에서 qπ(s, a)가 가장 커 보이는 행동을 고른다. 이렇게 얻은 새 탐욕적 정책(greedy policy)은 정의상 정책 개선 정리의 조건을 채우므로, 원래 정책만큼 좋거나 낫다.
이제 두 조각을 잇는다. 정책 π를 vπ로 개선해 π′를 얻고, 다시 vπ′를 평가하고, 또 개선해 π″를 얻는다. 이렇게 단조롭게 개선되는 정책과 가치 함수의 사슬이 만들어진다. 이것이 정책 반복(policy iteration)이다.
# 1. 초기화 — 모든 s ∈ 𝒮 에 대해 V(s), π(s)를 임의로 # 2. 정책 평가 반복: Δ ← 0 각 s ∈ 𝒮: v ← V(s) V(s) ← Σs′,r p(s′,r | s, π(s)) [r + γV(s′)] Δ ← max(Δ, |v − V(s)|) until Δ < θ # θ: 정확도를 정하는 작은 양수 # 3. 정책 개선 policy-stable ← true 각 s ∈ 𝒮: old-action ← π(s) π(s) ← argmaxa Σs′,r p(s′,r | s, a) [r + γV(s′)] if old-action ≠ π(s): policy-stable ← false if policy-stable: return V ≈ v∗, π ≈ π∗ else: 2단계로 이동
각 정책 평가는 그 자체가 반복 계산이지만, 이전 정책의 가치 함수에서 출발한다. 정책이 한 단계에서 다음 단계로 거의 변하지 않으므로 가치 함수도 거의 변하지 않고, 그래서 평가의 수렴이 크게 빨라진다. 정책 반복은 종종 놀랍도록 적은 횟수로 수렴한다 — 잭의 렌터카 예제는 5회, 4×4 그리드월드 예제는 단 1회 만에 최적에 닿는다.
§ 4가치 반복과 비동기 DP
정책 반복의 한 가지 흠 — 매 반복마다 정책 평가가 들어가고, 그 자체가 상태 집합을 여러 번 훑는 긴 반복일 수 있다는 점이다. 정확한 수렴은 극한에서만 일어난다. 꼭 끝까지 기다려야 할까?
사실 정책 평가는 수렴 보장을 잃지 않고 여러 방식으로 잘라낼(truncate) 수 있다. 가장 극단적이고 중요한 경우 — 정책 평가를 단 한 번의 스윕 후에 멈추는 것. 이 알고리즘이 가치 반복(value iteration)이다.
가치 반복은 정책 개선과 잘린 정책 평가를 한 번의 갱신으로 합친다. 명시적 정책을 따로 두지 않고, 마지막에 v에 대해 탐욕적인 정책을 한 번 뽑아낸다. 정책 평가와 마찬가지로 형식적 수렴은 무한 반복을 요구하므로, 실제로는 가치 함수가 한 스윕에서 아주 조금만 변할 때 멈춘다.
# 매개변수 θ > 0 — 정확도를 정하는 작은 임계값 # 모든 s ∈ 𝒮⁺ 에 대해 V(s)를 임의로, 단 V(terminal) = 0 반복: Δ ← 0 각 s ∈ 𝒮: v ← V(s) V(s) ← maxa Σs′,r p(s′,r | s, a) [r + γV(s′)] Δ ← max(Δ, |v − V(s)|) until Δ < θ # 결정론적 정책 출력 π(s) ← argmaxa Σs′,r p(s′,r | s, a) [r + γV(s′)]
| 특성 | 정책 반복 | 가치 반복 |
|---|---|---|
| 정책 평가 | 수렴까지 완전히 수행 | 단 한 번의 스윕 |
| 반복당 계산 | 높음 | 낮음 |
| 총 반복 횟수 | 적음 | 많음 |
| 명시적 정책 | 매 반복 유지 | 마지막에만 추출 |
둘 사이에는 무수한 중간 길이 있다. 정책 개선 스윕 사이에 정책 평가 스윕을 여러 번 끼워 넣으면 — 이것이 잘린 정책 반복(truncated policy iteration)이다. max 연산이 평가 스윕 일부에 추가되는 정도의 차이일 뿐이며, 이 모든 변형이 할인된 유한 MDP에서 최적 정책으로 수렴한다.
지금까지의 DP는 상태 집합 전체를 체계적으로 훑는 스윕에 묶여 있다. 상태가 아주 많으면 단 한 번의 스윕조차 엄청나게 비싸다 — 백개먼은 1020 이상의 상태를 가지며, 초당 백만 상태를 갱신해도 한 스윕에 천 년이 넘게 걸린다.
비동기 DP는 스윕을 버린 제자리 반복이다. 상태를 어떤 순서로든, 그때 손에 있는 다른 상태의 어떤 값이든 써서 갱신한다. 어떤 상태는 다른 상태가 한 번 갱신되기 전에 여러 번 갱신될 수도 있다. 단 — 올바르게 수렴하려면 모든 상태를 계속 갱신해야 한다. 어느 시점 이후로 어떤 상태도 영영 무시해서는 안 된다.
§ 5일반화된 정책 반복 — GPI
정책 반복은 동시에 맞물려 도는 두 과정으로 이루어진다 — 가치 함수를 현재 정책과 일치시키는 정책 평가, 그리고 정책을 현재 가치 함수에 대해 탐욕적으로 만드는 정책 개선. 고전적 정책 반복에서 둘은 번갈아 가며, 각자 다른 쪽이 시작되기 전에 완료된다. 그러나 이것은 필수가 아니다.
가치 반복에서는 정책 개선 사이에 평가의 단 한 번 반복만 끼어든다. 비동기 DP에서는 둘이 더 잘게 뒤섞인다 — 때로는 한쪽 과정에서 단 하나의 상태만 갱신하고 넘어간다. 두 과정이 모든 상태를 계속 갱신하는 한, 결국 도달하는 곳은 같다 — 최적 가치 함수와 최적 정책.
일반화된 정책 반복(Generalized Policy Iteration, GPI)은, 두 과정의 입도(granularity)와 세부와 무관하게, 정책 평가와 정책 개선이 상호작용하게 두는 일반적 발상을 가리킨다.
거의 모든 강화학습 방법이 GPI로 잘 설명된다. 모두 식별 가능한 정책과 가치 함수를 가지며 — 정책은 늘 가치 함수에 대해 개선되고, 가치 함수는 늘 그 정책의 진짜 가치 함수 쪽으로 끌려간다.
GPI에서 두 과정은 경쟁하면서 동시에 협력하는 것으로 볼 수 있다. 경쟁 — 정책을 가치 함수에 대해 탐욕적으로 만들면 보통 가치 함수가 그 새 정책에 대해 부정확해지고, 가치 함수를 정책과 일치시키면 보통 그 정책이 더 이상 탐욕적이지 않게 된다. 둘은 반대 방향으로 잡아당긴다. 그러나 협력 — 길게 보면 이 당김이 함께 하나의 공동 해(joint solution)로 수렴한다.
왜 그 공동 해가 최적인가? 평가 과정과 개선 과정이 둘 다 안정화되면 — 더 이상 변화를 만들지 않으면 — 가치 함수는 현재 정책과 일치하고, 정책은 현재 가치 함수에 대해 탐욕적이다. 이 둘이 동시에 성립하는 것은 곧 벨만 최적 방정식이 성립한다는 뜻이며, 따라서 정책과 가치 함수는 최적이다.
DP는 정말 비효율적인가
DP는 아주 큰 문제에는 실용적이지 않을 수 있다. 그러나 MDP를 푸는 다른 방법들과 견주면 사실 상당히 효율적이다. 몇몇 기술적 세부를 무시하면, DP가 최적 정책을 찾는 데 드는 (최악의) 시간은 상태 수 n과 행동 수 k의 다항식이다.
결정론적 정책의 총 개수는 kn이다 — 그런데도 DP는 다항 시간 안에 최적 정책을 찾는다. 이 의미에서 DP는 정책 공간의 직접 탐색보다 지수적으로 빠르다. 선형 계획법도 MDP를 풀 수 있지만, DP보다 훨씬 적은 상태 수에서 비실용적이 된다(약 100배 차이) — 가장 큰 문제에서는 DP만 실현 가능하다.
DP는 차원의 저주(curse of dimensionality) 때문에 적용이 제한된다고 흔히 말한다 — 상태 수가 상태 변수 수에 지수적으로 늘어난다는 사실이다. 그러나 큰 상태 집합이 만드는 어려움은 문제 자체의 본질적 어려움이지, 해법으로서 DP의 결함이 아니다. 오히려 DP는 직접 탐색이나 선형 계획법보다 큰 상태 공간을 다루기에 더 적합하다.