3장 그리드월드와 다이내믹 프로그래밍

Summary

1. 다이나믹 프로그래밍 - MDP를 풀기 위한 방법 (큰 일을 작게 쪼개서 수행하자)
2. 정책 이터레이션
   • 정책 평가
   • 정책 발전
3. 가치 이터레이션

• 전체적으로 다이나믹 프로그래밍의 정책 이터레이션과 가치 이터레이션 문제를 풀어나감 + 코드 설명

• 그리드월드는 다이내믹 프로그래밍의 도식화한 예시

다이나밍 프로그래밍

여기서 프로그래밍은 프로세스가 단계별로 나뉘어져 계획하는 것을 의미하고, 작은 문제가 중첩된 큰 문제일 경우 작은 문제로 쪼개서 푸는 방식.

정책 이터레이션

• 순차적 행동 결정 문제는 MDP를 통해 수학적으로 정의
• 문제의 목표는 에이전트의 보상의 합을 maximize 하는 것

정책은 에이전트가 모든 상태에서 어떻게 행동할지에 대한 정보이고 가장 높은 보상을 얻는 정책을 찾는것이 목표이다. 하지만 컴퓨터가 시작하는 정책은 무작위 정책(Random)이고, 이러한 정책을 정책 평가(Policy Evaluation)과 정책 발전(Policy Improvement)를 무한히 반복하여 최적 정책에 수렴할 수 있도록 하는 것이다. -벨만의 기대방정식을 활용함

• 정책 평가(가치 함수를 활용) - (코드 : Policyiteration 클래스의 poilcy_evaluation)

다이내믹 프로그래밍에서 에이전트는 정보가 없기 떄문에 랜덤 정책에서 시작하게 된다. 따라서 스텝을 밟아가면서 반복을 여러번 하였을때 정책에 대한 올바른 가치 함수를 찾을 수 있게 된다.(아래 수식에서 정책이 k iteration으로 바뀌게된 이유) $v_{k+1}(s) = \sum_{a \in A} \pi(a|s)(R_{s}^a + \gamma \sum_{s' \in S} P_{ss'}^{a} v_{k}(s'))$ 정책 평가의 순서는 다음과 같다. (책의 내용 참조)

1. k 번째 가치함수 행렬에서 현재 상태 s로 갈 수 있는 다음 상태 s’에 저장돼 있는 가치함수 $v_{k}(s’)$ 을 불러온다.
2. $v_{k}(s’)$ 에 감가율 $\gamma$ 를 곱하고 그 상태로 가는 행동에 대한 보상 $R_{s}^{a}$ 를 합한다. - $R_{s}^{a} + \gamma v_{k}(s’)$

3. 정책을 곱한다. - $\pi(a

   s)(R_{s}^{a} + \gamma v_{k}(s’))$

4. 모든 가능한 행동에 대해서 다 구하고 합한다. - $\sum_{a \in A}\pi(a

   s)(R_{s}^{a} + \gamma v_{k}(s’))$

5. 합한 값을 k+1번째 가치함수 행렬 s자리에 저장한다.
6. $s \in S$ 에 대해 반복한다.

• 정책 발전(일종의 weight 업데이트) - (코드 : PolicyIteration 클래스의 poilcy_improvement)) 탐욕 정책 발전(Greedy Policy Improvement)를 활용하여 새로운 정책 업데이트 한다.(상태 중 가장 높은 value function을 가진 상태로 가는 것)

$$\pi ' = greedy(v_{\pi})$$

​ 즉, max 상태 값으로 가는 것이다!!

정책 평가와 정책 발전을 계속적으로 반복하여 가치 함수가 수렴하는 순간을 정책으로 한다

가치 이터레이션

행동가치함수(q함수)를 최대화 하여 벨만의 최적방정식(optimal)을 찾아가는 것이다.

정책이터레이션과 같이 정책 평가, 정책 발전이 이루워지는 것이 아니라 가치이터레이션은 마지막에 구해진 큐함수 값을 보고 max값에 따라 정책을 정한다. 즉, 확률적인 정책으로 정책을 결정하는 정책이터레이션과 달리 가치 이터레이션은 벨만 큐함수의 max값(큐함수간 비교)을 바로 업데이트 한다. 벨만최적방정식과는 다르게 가치 이터레이션 역시 k iteration을 돌려 업데이트해간다.

$$v_{k+1}(s) = \max_{a \in A}(R_{s}^a + \gamma \sum_{s' \in S} P_{ss'}^{a} v_{k}(s'))$$