동적 프로그래밍에 대해 알아보자.
동적 계획법 (1950)
동적 계획법 (Dynamic Programming) 이란, 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다.
쉽게 말해, "N번째 답을 구하기 위해 N-1번째 답을 활용하는 방식의 접근법" 이라고 이해할 수 있다.
N번째 답이 N-1번째 답에서 도출될 수 있다면, N-1번째 답은 N-2번째 답에서 도출되고, N-2번째 답은 N-3번째에서.. 하는 방식으로 나아가게 될 것이다.
결국 2번째 답은 1번째 답을 활용해서 구할 수 있으므로,
1번째 답만 구해놓고 dp를 활용하면 원하는 N이 무엇이든 답을 얻을 수 있게 된다.
대표 논문: "The Theory of Dynamic Programming" by Richard Bellman (1954) 링크
중요성: Richard Bellman이 개발한 동적 프로그래밍은 강화학습의 이론적 기초를 마련했다. Bellman 방정식과 마르코프 결정 과정(MDPs)의 도입은 최적 제어 문제를 해결하는 수학적 프레임워크를 제공했으며, 이후 모든 강화학습 알고리즘의 기반이 되었다. 이 접근법은 상태 가치 함수와 최적 반환 함수의 개념을 사용하여 순차적 의사결정 문제를 해결하는 방법을 제시했다.
용어 설명:
- 마르코프 결정 과정(MDPs)이란?
마르코프 성질을 따른다는 것은 미래의 상태가 현재 상태에만 의존한다는 것을 의미한다. 마르코프 체인은 마르코프 성질을 따른다. 마르코프 체인은 이전 상태가 아닌, 현재 상태에만 의존하여 다음 상태를 예측하는 확률적 모델이다.
예를 들어, 현재 날씨가 흐리면 곧 비가 올 것으로 예측할 수 있다. 과거의 상태가 화창했을 지라도 현재 상태가 흐리다는 사실만으로 다음 상태를 예측하는 모델인 것이다.
마르코프 성질은 주사위를 던져서 나오게 될 숫자와 같은 독립변수에는 영향을 주고받지 않는다.
- Bellman 방정식이란?
벨만 방정식은 시점 t에서의 밸류와 시점 t+1에서의 밸류 사이의 관계를 다룬다.
- 상태 가치 함수란?
에이전트가 특정한 상태(state)에 있을 때 얼마나 좋은지를 평가하는 함수이다.
가치함수는 현재의 정책에 따라 행동할 때 기대할 수 있는 보상의 합으로 계산한다.
따라서, 가치함수는 정책에 따라 달라진다.
가치함수는 보상의 총 기댓값과 같으며, 대개 v(s)로 표시한다.
최적 가치함수(optimal value function)는 다른 가치함수에 비해 모든 상태, 모든 행동에 대하여 가장 높은 보상의 기댓값을 가지는 것이고, 최적 정책(optimal policy)은 최적 가치함수를 따르는 정책이다.
- 최적 반환 함수란?
수학적 원리:
코드 예제:
출처 및 레퍼런스
- https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95
- Google Gemini
- Manus
- 기술 면접 대비 CS전공 핵심요약집, 이수진 저
- 강화학습 입문 : 파이썬 예제와 함께하는, 김승현,김태우,이정원,이주행 공저
