4. 동적 프로그래밍, DP

dynamic Programming 은 마르코프 결정 과정 MDP 같은 환경 모델이 완벽하게 주어졌을 때 최적 정책을 계산하기 위해 사용될 수 있는 일군의 알고리즘을 가리킨다.

고전적인 DP 알고리즘은 완벽한 모델과 많은 양의 계산이 필요하다는 점 때문에 활용도가 제한되었지만 이론적으론 여전히 중요,, 

환경이 유한 MDP 로 모델링된다고 가정, 즉, 환경의 상태 S, 행동 A, 보상 R 의 집합이 유한 집합이고 환경의 동역학이 모든 s, a, r, s' 에 대한 확률 p(s', r | s, a) 로 주어진다고 가정한다. DP 의 개념을 상태와 행동의 연속적 공간을 다루는 문제에 적용할 수는 있지만, 정확한 해는 특별한 경우에 대해서만 구할 수 있다. 

 

상태와 행동의 연속적 공간을 다루는 문제의 근사적인 해를 구하는 보통의 방법은 상태와 행동의 공간을 양자화하여 유한 DP 방법을 적용하는 것이다. 

 

DP 의 핵심 개념, 좀 더 일반적으로 강화학습의 핵심 개념은 좋은 정책을 찾는 과정을 체계적으로 구조화하기 위해 가치 함수를 사용한다는 것이다. 

 

일단 최적 가치 함수 v, q 를 구하고 나면 최적 정책은 쉽게 구할 수 있다. 최적 가치 함수는 벨만 방정식을 만족한다.

이와 같은 벨만 방정식을 목표 가치 함수에 대한 근사를 향상시키기 위한 할당 assignment 의 형식, 즉 갱신 규칙으로 변환함으로써 DP 알고리즘을 얻을 수 있다.