동적 계획법

동적 계획법

• 큰 문제를 작은 문제로 나누고, 작은 문제의 답을 저장·재사용하여 전체 답을 구하는 방법
• 특히 최적화 문제에서 다음 성질을 활용:
  • 최적 부분 구조(optimal substructure): 전체 문제의 최적해가 부분 문제의 최적해로 구성됨
  • 중복되는 부분 문제(overlapping subproblems): 같은 부분 문제의 답이 여러 계산에 필요함

예시: 최단거리 문제

아래 그래프에서는 A, B, C, D 순서로 각 정점까지의 최단거리 계산 가능

• 최적 부분 구조: A에서 D까지의 최단 경로가 C를 지난다면, 그 경로에서 A부터 C까지도 최단 경로
• 중복되는 부분 문제: A에서 B까지의 최단거리를 C와 D의 후보 경로 계산에 재사용

flowchart LR
    A((A)) -->|2| B((B))
    A -->|5| C((C))
    B -->|1| C
    B -->|4| D((D))
    C -->|1| D

• 간선의 숫자: 두 정점 사이를 이동하는 비용
• 목표: 시작점 A에서 각 정점까지의 최소 비용 계산

• 최단 경로: A → B → C → D
• 전체 비용: 2 + 1 + 1 = 4
• 핵심: 마지막 간선 비용만 비교하지 않고, 앞 정점까지의 최단 비용에 그 간선 비용을 더해 비교

MDP와 동적 계획법

• 최적 가치: 상태 $s$에서 가능한 행동을 비교할 때 다음 상태 $s^{\prime }$의 최적 가치를 이용해 표현
• 정책 가치: 정책 $\pi$를 정하면 다음 상태의 정책 가치를 이용해 현재 상태의 가치를 표현
• 상태 재사용: 여러 경로가 같은 상태에 도달하거나 상태를 다시 방문하면, 그 상태의 가치 추정치를 여러 계산에서 사용
• 환경의 전이·보상 모델을 알 때 이러한 관계를 이용해 가치를 계산 가능

동적 계획법을 통한 가치 추정

• 목표: 정해진 정책 $\pi$를 따를 때의 상태 가치 $v_{\pi }(s)$ 추정
• 필요 정보: 정책의 행동 선택 확률과 환경의 전이·보상 모델
• 계산: 각 경우의 $r+\gamma v_{\pi }(s^{\prime })$에 발생 확률을 곱한 값의 합
  • $\gamma$: 미래 보상에 적용하는 할인율
• 상태 가치가 서로를 참조하거나 자기 자신을 참조할 수 있으므로, 초기 추정치에서 시작해 반복적으로 갱신

반복적 정책 평가법

• 반복적 정책 평가법(iterative policy evaluation): 정해진 정책을 유지한 채 상태 가치를 반복 갱신
• 부트스트래핑(bootstrapping): 가치를 임의로 정한 뒤, 새 가치를 계산할 때 기존의 다음 상태 가치 추정치를 사용

• 종료되지 않은 상태의 가치를 0 등으로 정한 뒤, 이전 추정치로 모든 상태의 가치를 반복 갱신
• 상태 수가 정해져 있고 보상이 일정 범위 안에 있으며 $0\le \gamma <1$이면, 정책 가치로 수렴