4.5 비동기 동적 프로그래밍

DP 방법의 주요 단점은 DP 가 MDP 의 전체 상태에 대한 계산 과정을 포함한다는 것이다. 다시 말해, 상태 집합에 대한 일괄 계산이 필요하다는 점이다. 상태 집합의 크기가 매우 크다면 한 번의 일괄 계산도 할 수 없을 정도로 계산량이 많을 수 있다. 

 

비동기 asynchronous DP 알고리즘은 상태 집합에 대해 체계적인 일괄 계산을 수행하지 않는 개별적인 반복 DP 알고리즘이다.

이 알고리즘은 상태의 가치를 갱신하는 순서가 무엇이든 개의치 않고, 다른 상태의 가치를 이용할 수 있는 상황이라면 그 값이 무엇이든 상관없이 다른 상태의 가치를 이용하여 해당 상태의 가치를 갱신한다. 

어떤 상태의 가치가 한 번 갱신될 동안 다른 상태의 가치는 여러 번 갱신될 수도 있다. 하지만 정확하게 수렴하기 위해 비동기 알고리즘은 모든 상태의 가치가 갱신될 때까지 갱신을 계속 수행해야 한다. 

 

일괄 계산을 하지 않는다고 해서 적은 양의 계산으로도 반드시 좋은 결과를 낼 수 있다는 뜻은 아니다. 단지 일괄 계산에만 집착할 필요가 없다는 것, 

알고리즘의 수렴 속도 향상을 목표로 갱신을 적용할 대상 상태를 선택하므로써 유연서의 혜택을 얻고자 할 수도 있다. 또는 갱신의 순서를 조정하려고 할 수도 있다. 심지어는 어떤 상태의 갱신을 건너뛸 수 있다. 

 

비동기 알고리즘을 사용하면 실시간으로 상호작용하며 계산 과정을 섞어서 수행하는 것도 더 쉽게 할 수 있다.