동적 프로그래밍 — 작은 문제로 큰 문제 풀기

동적 프로그래밍, 줄여서 디피는 엠디피 모델을 완전히 알고 있을 때 최적 정책을 찾는 방법이에요.

그림 왼쪽을 보세요. 디피의 전제 조건이 나와 있어요.

전이 확률 P와 보상 함수 R을 정확히 알아야 해요.

이건 환경과 직접 상호작용하지 않고 모델만으로 푸는 계획 방법이에요.

가운데 박스를 보면 디피의 핵심 아이디어가 정리되어 있어요.

벨만 방정식을 반복적으로 적용해서 가치 함수를 수렴시키는 거예요.

큰 문제를 작은 하위 문제로 쪼개고, 해를 저장해서 재사용해요.

최적 부분 구조와 중복 하위 문제라는 두 조건이 필요한데, 엠디피는 이 조건을 자연스럽게 만족해요.

오른쪽 결과 박스를 보면, 디피의 산출물은 최적 가치 함수 V 스타와 최적 정책 파이 스타예요.

아래 보라색 박스에 두 가지 핵심 알고리즘이 나와 있어요.

폴리시 이터레이션은 정책 평가와 개선을 번갈아 수행해요. 평가를 완전히 수렴시키고 나서 개선하는 방식이에요.

밸류 이터레이션은 평가 한 번에 바로 개선해요. 반복은 많지만 각 반복이 가벼워요.

그림 하단을 보면 디피와 모델 프리 방법의 차이가 나와 있어요.

디피는 모델이 필요하지만 정확한 최적해를 구할 수 있어요.

반면 몬테카를로나 티디 학습은 경험만으로 학습하지만 근사 해를 구하는 거예요.

리처드 벨만이 1957년에 동적 프로그래밍을 제안했고, 하워드가 1960년에 폴리시 이터레이션을 정립했어요.

디피는 강화학습의 이론적 기반이에요. 엠씨와 티디는 디피를 모델 없이 근사하는 방법이라고 볼 수 있어요.

이번 레슨에서 이 두 알고리즘의 동작 원리와 차이점을 자세히 배울 거예요.

디피의 한계인 차원의 저주와 비동기 디피 같은 해결책도 함께 살펴볼게요.

그럼 먼저 폴리시 이터레이션의 전체 구조부터 알아볼게요.