[강화학습] Dynamic Programming (동적 계획법)

What is Dynamic Programming?

Dynamic Programming (동적 계획법)이란 복잡한 문제를 다음과 같은 방법으로 푸는 것을 말한다.

• Sub-Structure : 상위 문제를 하위 문제로 쪼갠다
• Table-Structure : 각 하위 문제를 해결한 후 계산된 해를 테이블에 저장하여 여러 번 재사용
• Bottom-up Computation : 작은 하위 문제의 해를 결합하여 더 큰 하위 문제를 해결하고 원래 문제에 접근

동적 계획법은 다음과 같은 조건 하에서 풀린다.

1. Optimal Sub-structure : 원 문제의 최적해는 하위 문제들의 최적해들로부터 도출된다
2. Overlapping Sub-problems : 동일한 하위 문제의 해가 반복적으로 필요하므로 계산된 해를 테이블에 저장하여 재계산을 피할 수 있다.

"MDP는 위 두 가지 조건을 모두 충족 시킨다"
1) Bellman 방정식은 재귀적 분해 과정으로 해결된다
2) Value Function은 해를 저장하고 재사용한다.

 

출처 : https://yasir-tobbileh.medium.com/dynamic-programming-techniques-with-examples-89b684f406ec

 

Value Iteration

 

다음과 같은 단일 수렴을 반복적으로 계산한다.

$$V_{k+1}(s) = max_{a} \sum_{s',r} p(s', r | s, a)[r + \gamma V_{k}(s')]$$

 

(1) $V_0(S)$ 값 초기화

(2) 모든 $V_k(s')$ 값들로부터 $V_{k+1}(s)$ 업데이트

 

[문제 예시]

출처 : https://www.youtube.com/watch?v=rC6xkxS_myY&list=PLvbUC2Zh5oJtYXow4jawpZJ2xBel6vGhC&index=8

 

위의 예시에서 $V_2 (\text{Warm})$의 결과를 분석해보자. $V_2 (\text{Warm})$은 state가 'Warm'일 경우 2번째 Iteration 후의 ㄸExpected Value를 찾는 함수이다. 

 

우선 $S_1 = \text{Warm}$이라고 했을 때 현재 state에서 취할 수 있는 action은 'Slow'와 'Fast' 두 가지이다. 이제 각 action에 대하여 Expected Value를 계산해보자. ($\gamma = 1$ 가정)

 

1) Action = 'Slow' :

$V_2(s) =  p(\text{'Cool'} | \text{'Warm', 'Slow'}) * (r_1 + V_1(\text{'Cool'}))$

$+ p(\text{'Warm'} | \text{'Warm', 'Slow'}) * (r_2 + V_1(\text{'Warm'}))$

$= 0.5(1 + 2) + 0.5(1 + 1) = 2.5$

 

2) Action = 'Fast' :

$V_2(s) =  p(\text{'Overheated'} | \text{'Warm', 'Fast'}) * (r_1 + V_1(\text{'Cool'}))$

$+ p(\text{'Warm'} | \text{'Warm', 'Fast'}) * (r_2 + V_1(\text{'Warm'}))$

$= 1.0(-10 + 0) = -10$

 

$$∴ V_2(Warm) = max{2.5, -10} = 2.5$$

 

(3) Optimal Policy 계산

$$\pi_{*} (s) = arg max_{a} \sum_{s',r}p(s', r | s, a)[r + \gamma V_{*}(s')]$$