ㅁ 정책 기법

1. Value Iteration

ㅇ 정의:
마르코프 결정 과정(MDP)에서 각 상태의 가치를 반복적으로 업데이트하여 최적 정책을 도출하는 동적 계획법 기법. 벨만 최적 방정식을 이용해 수렴 시 최적 가치 함수와 정책을 동시에 얻는다.

ㅇ 특징:
– 모든 상태에 대해 가치 함수를 반복 계산
– 수렴 시점에서 정책 추출 가능
– 초기 정책 불필요, 가치 함수만으로 진행
– 계산량이 많지만 수렴 보장이 있음

ㅇ 적합한 경우:
– 상태/행동 공간이 유한하고 명시적 전이 확률을 알고 있는 경우
– 정책 평가와 개선을 동시에 수행하고 싶은 경우
– 학습보다는 계획(planning)에 가까운 문제

ㅇ 시험 함정:
– Policy Iteration과 혼동: Policy Iteration은 정책 평가와 정책 개선을 번갈아 수행하지만, Value Iteration은 가치 함수 업데이트만 반복 후 정책 도출
– Q-learning과의 차이: Q-learning은 모델 프리, Value Iteration은 모델 기반
– 수렴 조건을 묻는 문제에서 할인율(γ) < 1 조건을 빠뜨리기 쉬움 ㅇ 시험 대비 "패턴 보기" 예시: O: "벨만 최적 방정식을 반복 적용하여 상태 가치 함수를 갱신한다" O: "정책 없이도 가치 함수로부터 최적 정책을 도출할 수 있다" X: "Value Iteration은 정책 평가 단계와 정책 개선 단계를 명확히 구분하여 수행한다" X: "Value Iteration은 환경 모델 없이 동작하는 대표적인 강화학습 알고리즘이다" ㅁ 추가 학습 내용 Value Iteration의 상태 가치 갱신은 다음과 같이 수행된다. V(s) ← max_a Σ_{s'} P(s'|s,a)[R(s,a,s') + γV(s')] 수렴 속도를 높이기 위해 상태를 순차적으로 갱신하는 스윕 순서를 조정하거나, 우선순위 큐를 사용하는 Prioritized Sweeping 기법을 활용할 수 있다. 상태 공간이 매우 큰 경우에는 근사 방법(Approximate Value Iteration)과 함수 근사(Function Approximation)를 적용해야 하며, 이 경우에는 수렴 보장이 약화될 수 있다. 시험에서는 다음과 같은 구분이 자주 출제된다. - Value Iteration과 Policy Iteration의 시간 복잡도 차이 - 모델 기반(Model-based) 여부와 모델 프리(Model-free) 여부 - 할인율(γ)의 역할과 수렴성 관련 조건 - 실제 환경에서의 적용 가능성, 예를 들어 전이 확률을 모를 경우 적용 불가 여부