[강화학습] 최적의 행동은 어떻게 찾을까? _ 동적계획법 (feat 정책반복)

이전에는 마르코프 결정 과정 (MDF :  Markov Decision Process)을 통해

강화학습의 문제가 결국 "행동을 선택하는 최적의 정책" π*을 찾는 것이라고

어렴풋이 알게 되었다.

 

마르코프과정 정리 내용☜

 

하지만, π*는 정해진 해가 없기 때문에 특정 알고리즘을 통해 최적해를 찾아가야하는 문제가 남아있다.

동적계획법(DP : Dynamic Programming)은 마르코프 결정 과정에서 최적의 정책을 찾기 위한

문제풀이방법 중 하나이다,

---

동적계획법(DP : Dynamic Programming) 

=> 복잡한문제를 작은문제로 쪼개서 답을 구하는 방법을 뜻한다

 

큼 음식을 한번에 먹는 것이 아니라, 그것을 1000조각을 내서

작은 음식을 1000번 먹으면 되는 것처럼

 

복잡한 문제를 한번에 해결하는 것이아닌, 작고 쉬운 문제로 쪼개어 그것을

여러번 해결하는 방법이다.

아이에게는 너무 커보이는 햄버거지만, 잘게 쪼개면 먹을 수 있다.

동적계획법이 해결할 수 있는 문제의 특징

• 최적하위구조 (Optimal substructure) : 분할한 작은 문제의 최적값이 큰 문제에서의 최적값 => 음식을 아무리 쪼개도 맛있는 부위는 같다
• 중복하위문제 (Overlapping problems) : 따라서, 큰 문제의 해를 구하기 위해서 작은 문제의 최적 해를 재사용

※ MDP에서 π*를 찾는 것은 이 특성을 만족한다

---

동적계획법으로 π* 찾기 = 정책반복 = 정책평가 + 정책개선

 

1. 정책평가(PE : Policy Evaluation)

의미 : 현재의 행동정책π 에서 얻을 수 있는 최대의 가치  max(Vπ(s, a)) 계산

 

가치의 계산은  Bellman expectation backup operator 를 사용하여 계산

위의 식을 분석해 보면

다음가치 = (1) + γ*(2)*이전가치

(1) 현재 상태(s) 주어진 행동 정책을 따랐을 때 에서 얻을 수 있는 보상의 총합

(2) 주어진 행동 정책을 따랐을 때, 현재 상태 이후로 얻어질 보상의 총합

 

따라서  Bellman expectation backup operator 가 말하는 "가치" 란

 

"주어진 행동 정책에 따랐을 때, 현재와 미래의 모든 상태에서 얻어지는 보상의 현재가치의 합"

---

알고리즘 Part

정책 평가 알고리즘

2. 정책개선(PI : Policy Improvement)

의미: 지금보다 더 높은 가치Vπ(s, a) 를 창출 할 수 있는 새로운 정책 π'를 계산

3. 정책 반복

=> 정책평가와 정책개선을 반복 => 수렴값 π*

=> 정책평가 : 임의의 π에 대해 최대 상태 가치 계산

=> 정책개선 : 더 높은 상태 가치를 가지는 새로운 π'을 계산

언제까지?

이전의 행동정책으로 부터의 가치와

새로운 행동정책으로 부터의 가치 차이가 거의 같아질때 까지

"결국 최대 상태가치를 가지는 π*에 수렴"

---

배운것 소화하기

 

결국 찾고자 하는 것은 주어진 환경에서 최적의 행동 정책(π*)을 찾는 것이다.

행동 정책이란, 어떻게 행동 해야하는지를 표현한 것인데

수학적으로는 특정 행동이 일어날 가능성들의 집합을 뜻한다.

 

주어진 환경이란

• 상태들 S
• 각 상태에서 취할 수 있는 행동들 A
• 각각의 상태s 에서 어떤 행동a 을 취했을 때 얻을 수 있는 보상 R

동적계획법이란, 최적의 행동을 찾을 때 사용하는 하나의 방법론 이다.

동적계획법은

• 큰 문제를 작고 쉬운 문제들로 쪼개어 최적해를 구하는 방법이다
• 풀이 과정이 반복적인 경우 효과적이다

 

동적계획법을 이용하여 최적의 행동을 찾기 위해 다음과 같은 방법(정책 반복)을 쓴다

1. 정책평가 : 주어진 π에 대해 최대 상태 가치 계산 
2. 정책개선 : 더 높은 상태 가치를 가지는 새로운 정책 π'를 계산
3. 1)번과 2)번을 반복한다

끝.