가치 반복

가치 반복

가치 반복(Value Iteration)은 벨만 최적 방정식을 반복적으로 적용하여 최적 가치 함수 \(V^*\)에 수렴하는 동적 프로그래밍 알고리즘이다.

핵심

• 초기 가치 함수 \(V_0\)를 임의로 설정하고, 벨만 업데이트를 반복한다
• 각 반복에서 \(V_{k+1}(s) = R(s) + \max_a \gamma \sum_{s'} P_{sa}(s') V_k(s')\)
• \(\|V_{k+1} - V_k\|_\infty < \epsilon\)이 되면 수렴으로 판단한다
• 유한 상태 공간 MDP에서 최적 정책으로의 수렴이 보장된다
• 수렴 후 최적 정책: \(\pi^*(s) = \arg\max_a \sum_{s'} P_{sa}(s') V^*(s')\)

수식

\[V_{k+1}(s) \leftarrow R(s) + \max_a \gamma \sum_{s'} P_{sa}(s') V_k(s')\]