강화학습 - 2 <MDP를 푸는 Dynamic Programming 기법>

강화학습 문제는 MDP로 정의되는 문제이다. 따라서 강화학습 문제를 풀고 싶으면 MDP 문제를 푸는 기법을 사용하면 된다. MDP 문제는 Agent가 환경을 아는 상황(State Transition Matrix와 Discounted rate를 아는 상황)이냐 그렇지 않느냐에 따라 적용할 수 있는 기법이 다르다. 가장 먼저 환경을 아는 상황에서는 Dynamic Programming 기법 (이하 DP)를 적용할 수 있다.

 

DP를 적용해 문제를 풀기 위해선 문제가 2가지 특성을 가지고 있어야 한다. 첫번째는 Optimal structure이다. 큰 문제의 하위 문제인 작은 문제에서의 최적 값이, 큰 문제에서도 최적값인 것이다. 두번째는 Overlapping problems이다. 큰 문제를 풀기 위해서 작은 문제의 결과들을 재활용하기 때문에, 테이블에 결과를 저장해둔다.  MDP로 정의되는 문제의 Bellman Equation (이하 BE)은 위 2가지 특성을 만족하기 때문에, BE를 푸는데 DP를 사용할 수 있다. (BE를 푼다는 것은 최적 state value function, action value function을 계산할 수 있다는 것이다. = 최적 policy를 계산할 수 있다는 것이다.)

 

DP는 하나의 기법이고 그 종류에는 동기적 DP - 정책 반복(Policy Iteration), 가치 반복 (Value Iteration), 비동기적 DP - In place DP, Prioritized sweeping, Real - time DP 가 있다. 이를 차례대로 하나씩 살펴보자.

 

---

 

1. 정책 반복 (Policy Iteration) - 동기적 DP.

정책 반복 방법은 최적 정책을 찾아가는 과정으로서, 정책 평가 (Policy Evaluation)와 정책 개선 (Policy Improvement)을 반복하는 것이다. 정책 평가 (Policy Evaluation)는 현재의 policy로부터 BE의 state value function을 구하는 방법이다.

정책 평가 (Policy Evaluation) 1. 모든 state 에서 state value function을 0으로 초기화 한다. 2. 모든 state에서 state value function을 다음과 같이 업데이트 한다. (while 문)      state value function_t+1 = ((현재 state value function x transition matrix x discounted rate의 총합 + 현재 state에서 action에 따른 reward) x 현재 state에서 action을 선택할 policy) 현재 state에서 선택가능한 모든 action에 대해 다음 계산의 합 3. state value function의 업데이트 값이 일정 값 이하면 종료

(위 정책 평가 알고리즘은 하나의 최적해로 수렴한다는 것에 대한 증명이 되어 있다.)

 

MDP를 풀기 위해서는 최적 policy를 찾아야 한다. 따라서 정책 평가로 얻은 state value function으로 부터 policy를 다시 업데이트 해야 한다. 이 과정이 정책 개선이다.

정책 개선 (Policy Improvement) 1. 현재 state에서 action에 대한 state action function을 계산한다. 2. 현재 state에서 state action function이 가장 큰 action에 대해서 policy를 1로 업데이트 하고 나머지는 0으로 업데이트 한다.

정책 개선을 통해 업데이트 된 policy는 좋아졌다고 할 수 있을까? 다시말해 state value function이 더 커지는 것일까? 이도 정책 개선 정리 (Policy Improvement theorem)에 의해 정리되어 있다.

 

정책 반복이란 정책 평가와 정책 개선을 반복하는 과정이다.

정책 반복 1. 정책 평가 : 모든 state에서 policy에 따라 state value function 업데이트 2. 정책 개선 : state value function으로부터 state action function을 계산하고 조건문 과정을 통해 policy 업데이트 3. 정책의 Update 정도가 일정 값 이하라면 반복문 탈출

정책 반복 방법은 agent가 탐험할 수 있는 environment의 모든 state 에서의 state value function 그리고 policy를 업데이트해 나가는 방법이다. 정책 반복은 그 자체로 while문이 수행되고 정책 평가 방법에서도 while문이 수행된다. 모든 state 업데이트 + 2번의 while문은 굉장히 heavy한 연산량을 초래하게 된다는 단점이 존재 한다. 이 문제를 해결한 것이 다음에 볼 가치 반복 (Value Iteration)과 비동기적 DP의 방법들이다.

 

 

2. 가치 반복 (Value Iteration)

가치 반복은 정책 반복이 2번의 while문을 수행해야 하는 것을 1번으로 줄인 방법이다. 정책 반복이 state value function를 업데이트한 후 이로부터 Action value function을 구하고, policy를 argmax로 업데이트를 수행하는 방법이었는데, 가치 반복은 state value function을 업데이트 시 argmax를 바로 적용해버린다.

가치 반복 1. 모든 state에서 state value fucntion 초기화 (어느 값이든 상관 없다.) 2. 다음을 반복한다. 모든 상태 s에서 state value function을 Max state action function으로 업데이트 한다. 3. state value function의 업데이트 변화량이 특정 값보다 작으면 종료한다.

 

3. 비동기적 DP 방법

정책 반복과 가치 반복은 모든 state에서의 state value function을 업데이트 한다. 따라서 state가 아주 많은 MDP 문제에서는 연산량이 많아진다. 비동기적 DP란 모든 state에서 계산을 하지 않는 방식이다. 비동기적 DP로는 In place DP, Prioritized sweeping, Real-time DP가 있다.

 

---

 

이렇게 오늘은 MDP로 정의된 강화학습 문제를 풀 때, 환경을 아는 상황이라면 적용할 수 있는 DP 기법들을 알아보았다. 가장 대표적인 방법은 정책 반복 방법. 이 방법은 2개의 While문 및 모든 state를 업데이트 하는 방법이기 때문에, state 증가 시 연산량 매우 증가라는 단점을 가지고 있다. 이 때 while 문 1번으로 문제를 푸는 방법이 가치 반복 방법이다. 그리고 모든 state가 아닌 일부 state만 업데이트하며 답을 찾아가는 방법이 비동기적 DP이다.

 

강화학습 문제를 풀때는 문제를 MDP로 정의하고 이를 푼다. 푼다는 것의 의미는 최적 state value function, state action function을 구한다는 것이다. 이는 다시 최적 policy를 구한다는 것이다. MDP 문제에서 환경(state transition matrix, discounted rate, Reward)을 알고 있다면 DP 기법을 적용해볼 수 있다. DP 기법에는 정책 반복, 가치 반복, 비동기적 DP 방법들이 이 있다.

 

---

본 글에서는 Bellman Equation을 이용한 Dynamic Programming 방법인 정책 반복과 가치 반복을 주로 공부해보았다. 강화학습 방법 공부에서 DP를 공부했지만, 엄밀히 말하면 DP에서 '학습'의 부분은 존재하지 않는다. '계산'할 뿐이다. 그리고 DP는 몇가지 한계를 가지고 있다.

 

첫번째는 DP가 state 증가에 따른 계산 복잡도 증가에 취약하다는 것이다. DP의 계산 복잡도는 상태 크기의 3제곱에 비례한다고 한다.

 

두번째는 state를 구성하는 차원의 개수다. 보통 강화학습은 그리드 맵으로 설명하기 때문에 2차원으로 표현하지만, 문제에 따라서 state 차원은 얼마든지 늘어날 수 있고 이가 계산 복잡도를 증가시킨다.

 

세번째는 환경을 알아야 한다는 것이다. 즉, 환경을 구성하는 P (state transition probability)와 R (reward)를 알아야 한다. 하지만 많은 환경에서 이 정보를 정확하게 알지 못한다.

 

특히 세번째 단점으로 인해, 환경에 대한 이해(P, R을 모를 때)가 없을 때에도 MDP 문제를 풀 수 있는 방법에 대한 필요가 생겼다. 다음 공부에서 알아볼 것은 바로 환경을 모를 때 MDP를 풀 수 있는 방법인 Monte Carlo, Temporal Difference, e-Greedy, SARSA, Q-learning 등에 대해 배운다. 그리고 이 방법이 '강화학습'이다.