벨만 방정식은 dynamic programming(DP)로 풀 수 있고, 이는 정책 이터레이션(Policy Iteration)과 가치 이터레이션(Value Iteration)으로 나뉜다.
Policy Iteration
정책 이터레이션은 탐욕적인 search 방법론이다.
이는 정책에 따라 목표에 빠르게 도달했던 경우에 수행했던 행동(action)을 중요한 것으로 보고, 이 때의 행동을 앞으로도 취할 수 있도록 정책을 수정하는 방법이다.
즉, 결과가 좋았던 경우에 취했던 행동을 중시하는 것이다.
정책 이터레이션은 정책 평가와 정책 발전으로 이루어져 있으며, 정책을 평가 할 때 벨만 방정식을 이용하며, 정책을 발전할 때는 가치함수를 바탕으로 최대의 보상을 얻게하는 행동을 선택하는 탐욕 정책 발전을 이용한다 (여기서 탐욕적이라는 말은 무조건 보상이 제일 컸을 때의 행동을 선택하기 때문이다). 따라서, 전체적인 루프는 평가 -> 발전 -> 평가 -> 발전 -> ... 하여 정책과 가치함수가 수렴할 때까지 반복한다. 이때, 수렴성을 판단하는 부분은 정책이 특정 값 이상으로 업데이트가 되지 않으면 수렴하였다고 보고 이터레이션을 중단한다.
Value Iteration
가치 이터레이션은 목표 지점으로부터 거슬러 올라가며 목표 지점과 가까운 상태로 에이전트를 유도하는 방법이다.
최적 정책을 가정하고 벨만 최적 방정식을 이용해 순차적 행동 결정 문제에 접근한다.
정책 이터레이션과 달리 정책이 직접적으로 주어지지 않으며 행동의 선택은 가치 함수를 통해 이루어지게 된다. 또한, 평가 -> 발전의 루프 대신 매 iteration 마다 value function을 업데이트하며, 최적 가치함수가 될 때까지 업데이트 후 그 때의 policy를 가져와 최적 policy로 사용한다.
Dynamic Programming의 단점
Dynamic Programming을 통해 최적 정책을 구하는 과정은 다음과 같은 단점이 있다.
- 문제의 규모가 늘어나게 되면 계산만으로 풀어내기에는 한계가 있다.
- 그리드 월드 같은 경우 상태의 차원은 2차원이지만, 상태의 차원이 늘어나게 되면 가능한 상태의 수가 기하급수적으로 늘어나게 된다(차원의 저주).
- 보상과 state transition의 확률(환경의 모델)을 안다는 가정하에서 DP 적용이 가능하다.
이러한 단점을 극복하기 위해서 강화학습이 제시되었다.
