[강화학습: RL] 3-1. Dynamic Programmin(DP, 동적 계획법)

단단한 강화 학습 4장 '동적 프로그래밍'과 인터넷 강의를 참고해서 만든 게시글입니다.

이전의 내용은 아래의 링크를 참고해주세요.

[강화학습: RL] 2-2. 마르코프, Markov(MDP)

---

이전 게시글에서 Bellman Optimality Equation(BOE) 즉, 벨만 최적 방정식은 직접해가 있기 때문에 반복적 알고리즘을 통해 계산해야 한다고 명시했다. 따라서 이번에는 MDP를 푸는 방법(BOE를 통해 최적 정책을 찾는 과정)인 DP에 대해서 다뤄보도록 하겠다.

 

MDP를 푸는 방법에는 여러가지가 있는데, 환경을 알 때 모를 때로 나눌 수 있다. 환경을 아는 경우에는 DP, 모르는 경우는 MC, TD를 사용한다.

 

개념

Dynamic Programming은 복잡한 문제를 작은 문제로 나눈 후 작은 문제의 해법을 조합해 큰 문제의 해답을 구하는 기법이다. 

 

정책 평가(policy evaluation: PE)

벨만 기댓값 방정식의 해를 구하는 방법 중 하나이다. 벨만 (기댓값) 방정식은 BOE와 다르게 직접해가 존재하는데 왜 정책평가로 풀어야 할까에 대한 의문이 들 수 있다. state, action에 대한 종류가 많아지면, 역행렬을 구하기 어렵고, 불가능할 수 있다. 때문에, 이런 경우 정책평가로 벨만 기댓값 방정식을 풀 수 있다.

 

알고리즘

대략적으로 알고리즘을 설명하면, 평가 하고싶은 정책 $\pi$를 가지고 있다고 하자. 그 정책 가치 값을 임으로 0으로 두고(어떤 값을 넣어도 상관없음), 모든 상태에 대해 반복문 반복 벨만 기댓값 방정식을 활용해 t+1에서의 가치를 파악한다.

반복 이전과 반복 이후의 가치함수 차이를 계산한다. 입실론(아주 작은 값)보다 차이가 작다면 반복한다.

 

초기화 $V_0^{\pi}(s) )\leftarrow0$ 모든 $s \in S$ 반복 (모든 상태 s에 대해):    $V^{\pi}_{t+1}(s)\leftarrow \Sigma_{a \in A} \pi(a|s)( R_s^a + \gamma \Sigma_{S' \in S}P_{ss'}^aV_t^{\pi}(S'))$ 반복 조건 $max_{s\in S}|V^{\pi}_{t+1}(s)-V^{\pi}_{t}(s) |\le \epsilon$이면 다시 반복

 

정책 개선(policy improvement: PI)

벨만 최적 방정식의 해를 구하는 방법이다. 정책 개선 알고리즘은 현재 정책 $\pi$로부터 개선된 정책 $\pi'$을 구하는 알고리즘이다. 정책 개선을 사용하기 위해서는 해당 정책에 대한 가치 함수가 필요한데, 이전 정책 평가에서 계산한 가치 함수를 사용하겠다.

 

1. $Q^{\pi}(s,a)=R_s^a + \gamma \Sigma_{S' \in S}P_{ss'}^aV^{\pi}(S')$                                                                                                *$V^{\pi}(S')$는 정책 평가에서 만들어진 함수 2. 만약 $Q^{\pi}(s,a)$값이 최대가 되는 행동 a가 있다면, 1을 리턴하고 나머지 action들에게는 0을 리턴한다.

 

정책 반복(policy iteration)

정책 반복은 정책 평가와 정책 개선을 적용해서 bellman 방정식을 푼다.

1. 정책 평가를 적용해 $V^{\pi}(s)$를 계산한다.

2. 정책 개선을 적용해 $\pi'$을 계산한다.

즉, 정책평가와 정책 개선을 계속해서 반복해 최적의 정책을 만들어낸다.

 

최종적으로, DY는 BOE를 풀기 위해 큰 문제를 정책 평가와 정책 개선인 하위 문제로 나눠 풀어간다. 

다음 게시글에서는 DY를 보다 더 효율적으로 풀어낸 비동기적 동적 계획법에 대해 게시하겠다.