강화학습 Sutton [Ch4 Dynamic Programming] #5 Asynchronous Dynamic Programming

Asynchronous Dynamic Programming

DP (Dynamic Programming)의 단점은 MDP의 상태 전부를 가지고 하는 연산이다. 즉, 상태 전체에 걸쳐 sweep을 해야한다는 것. 당연히 상태가 매우 커진다면, 계산량이 엄청 많이 필요해지는 건 당연하다. Asynchronous DP는 이를 좀 더 개선하는 방법 중 하나로, 이전처럼 상태 하나하나 순서대로 sweep하는 것 대신, 동시에 비동기적으로 하는 것이다. 물론 어떤 상태는 이미 여러 번 업데이트 된 것일 수 있고, 한 번도 안한 것일 수도 있으나, 반드시 모든 상태에 대해서 계속 iteration을 한다면 수렴한다. Asynchronous DP는 업데이트할 상태를 선택하는 것에 이썽서 굉장히 유연하다. 예를 들어 policy evaluation과 value iteration 업데이트를 섞어서 asynchronous truncated policy iteration도 만들 수 있다. Asynchronous뿐만 아니라, 가치를 업데이트할 때 전파(propagate)한다던지, 순서를 임의로 만든다던지, 업데이트 횟수를 상태마다 조절한다던지 다양한 sweepless DP 알고리즘이 존재한다.

Asynchronous DP의 장점 중에 하나는 실시간으로 환경과 상호작용하면서 가치를 업데이트 할 수 있다는 것이다. 이전에는 가치를 구하고 정책을 개선하고 가치를 구하고 정책을 개선하기를 반복해서 최적의 정책을 구한 뒤에야 움직일 수 있었다. 하지만 Asynchronous DP는 움직여서 얻은 경험으로 어떤 상태의 가치를 업데이트하고 어떻게 정책을 개선해야 하는지 알 수 있고, 동시에 마지막으로 업데이트 되어있는 가치와 정책을 가지고 어떻게 움직일 지 알 수 있다. 예를 들면, agent가 지나간 상태들에 대해서만 가치를 업데이트 하는 것이다. 앞으로 다룰 강화학습 알고리즘들은 이와 비슷하다.