[강화학습: RL] 3-2. Asynchronous Dynamic Programmin(비동기적 동적 계획법)

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

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

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

---

DP보다 더 효율적인 Asynchronous DP(비동기적 동적 계획법)에 대해서 다루겠다.

 

기존의 DP는 정책 평가를 반복하고, 정책평가가 수렴한 뒤 정책 개선을 반복했다.

즉, 정책 반복 안에서 정책 평가, 정책 개선 2개의 반복문이 돌아야했다.

Asynchronous DP는 2개의 반복문을 하나로 합쳐 효율성을 높였다.

 

가치반복(Value Iteration: VI)

두 단계를 거치지 않고, 하나의 단계로 최적의 정책을 구할 수 있다.

https://wordbe.tistory.com/entry/RL-%EA%B0%95%ED%99%94%ED%95%99%EC%8A%B5-part2-Dynamic-programming-Monte-Carlo-Method

MDP를 입력으로 넣으면 최적 가치 함수를 찾은 후, 최적 정책을 찾는다.

 

알고리즘

가치 반복을 시작하기 위해 가치 함수를 임의로 초기화하고, 모든 상태에 대해서 가치함수를 Bellman optimal backup을 이용해서 정의한다. 새롭게 구해진 가치함수(새로운 정책)가 이전에 만들어진 가치함수(이전 정책)과 거의 동일할 떄까지 반복한다. 반복이 종료되면 최적 정책을 출력한다.

 

초기화 $V_0^{\pi}(s) )\leftarrow0$ 모든 $s \in S$   반복 (모든 k에 대해):      $V_{k+1}(s)\leftarrow \max_{a \in A} ( R_s^a + \gamma \Sigma_{S' \in S}P_{ss'}^aV_k(S'))$      모든 상태 s에 대해서, $V_{k+1}(s)$와 $V_k(s)$가 거의 비슷할 때 까지 반복한다. $V^*(s)\leftarrow V{k+1}$로 최적 가치함수를 변환시킨다.

아직까지 비동기적 DP에 대해서는 게시하지 않았다. 가치함수 또한 동기적 DP로 돌린다고 생각해보자.

그러기 위해서는 기존의 DP는 기존의 정책값(가치)를 알고있어야 했고, 새로운 정책값 또한 메모리에 저장해야했다. 때문에 2배의 메모리가 필요하며, 학습시간 또한 2배로 오래걸린다.

가치 함수를 비동기적 DP로 돌린다면, 메모리나 학습시간이 배로 늘어날 필요없이 효율적으로 학습할 수 있다.

 

---

비동기적 DP (Asynchronous DP)

DP는 모든 상태를 거쳐 연산을 하기 때문에, 상태가 커지면 계산량이 어마어마하게 많아질 수 있다. Asynchronous DP는 더욱 효율적인 방법으로, 모든 상태를 하나하나 거치는것 대신 비동기적으로 연산한다. 때문에 어떤 상태는 여러번 업데이트 될수도, 업데이트를 아예 못할수도 있으나, 계속 반복한다면 수렴된 결과를 가져온다는 개념이다.  

 

종류

더 많은 종류가 있지만 3개의 종류에 대해서만 간략하게 소개하겠다.

- in-place DP: t, t+1에서의 V를 따로 관리하지 않고, t+1에서의 V를 이용해 새로운 값을 만들어낸다.

- Prioritized sweeping: 가치 함수를 업데이트할 때 벨만 에러가 큰 상태부터 업데이트한다.

- Real-time DP: 강화학습의 에이전트가 현재 겪는 상황만 업데이트한다. 모든 state를 다루지 않고, 범위를 제한함으로써 학습을 보다 효율적으로 할 수 있다.