동적프로그래밍
9장 강화학습과 게임지능
9.3 동적 프로그래밍
- 최적화 문제를 해결하기 위해 사용하는 algorithm
- 상향식 문제해결 방법론(bottom-up) : 문제를 가장 작은 단위까지 분해한 다음 가장 작은 문제부터 해결하여 점점 큰 문제로 진행
- $i$번째 부분 문제의 답을 보고 $i+1$번째 부분 문제의 답을 구하는 algorithm
9.3.1 정책 반복 algorithm
- 정책을 직접적으로 개선해 나가면서 최적의 정책을 찾아가는 접근 방법
- 입력 : 상태전이 확률 분포 (환경에 대한 정보 제공)
- 출력 : 최적 정책, 최적 가치함수
- 가치함수 개선 : 벨만 기대 방정식
- ${\nu}{\pi}(s) = \sum{a \in A(s)} P(a \mid s) \left( r + \gamma {\nu}_{\pi}(s’) \right), \forall s \in S$
- 랜덤 정책으로 초기화
- 정책 평가 : 현재 정책에 따라 가치 함수의 개선과정을 수렴할 때까지 반복 -> 계산량 많음
- 정책 개선 : 심지어 개선된 가치함수를 기반으로 최선의 행동을 선택하여 새로운 정책을 만들고 다시 평가하는 식으로 반복
- ${\nu}{\pi}(s) = \sum{a \in A(s)} P(a \mid s) \left( r + \gamma {\nu}_{\pi}(s’) \right), \forall s \in S$
- 속도문제로 사용되지 않음
9.3.2 가치 반복 algorithm
- 각 상태의 최적 가치 함수를 반복적으로 계산하여 최적의 정책을 결정
- 가치함수 개선 : 벨만 최적 방정식(Bellman optimal equation)(벨만 기대 방정식을 개조)
- $ {\nu}(s) = \max_{a \in A(s)} \left( r + \gamma {\nu}(s’) \right), \forall s \in S $
- 입력 : 상태전이 확률 분포 (환경에 대한 정보 제공)
- 출력 : 최적 가치 함수
- 가치함수를 초기화
- 가치함수 개선, 모든 행동을 고려하여 $r + \gamma {\nu}(s’)$ 최대가 되는 행동을 취했을 때 총보상을 계산함
- 각 상태의 가치를 해당 행동들 중 최대 총 보상을 제공하는 값으로 업데이트 = 개선된 정책으로 변경 후 반복
- 가치 변화가 충분히 작아질 때까지 반복
- 정책을 생략한 채 동작할 수 있어 훨씬 빠름
-
출력한 최적 가치함수를 통해 최적 정책을 쉽게 추론 (최대가 되는 행동을 표에 기록해두고 해당 행동들에 높은 확률을 부여하여 최적 정책 추론)
- 동작에 대한 고찰
- $r + \gamma {\nu}(s’)$ 이웃 상태의 값을 사용 => bootstrap(이웃 상태끼리 영향을 미치는 방식)
- 가치함수를 초기화하고 출발하기 때문에 초기에는 좋은 값이 없음
- 진행해가면서 한 두 개 정확한 정보가 생기고 상태가 서로 영향을 미쳐 수가 점점 늘어나서 수렴에 도달
동적 프로그래밍의 한계
- 가치함수를 저장하기 위해서는 상태의 갯수 만큼의 array가 필요
- 상태 개수가 방대하면 메모리와 계산량이 과다한 문제