On distributed dynamic programming

An asynchronous implementation of the value-iteration algorithm of dynamic programming for the expected average cost criterion is presented. The situation where the task of performing each iteration is divided among a number of processors is considered. Each processor iterates on a different set of components of the value function vector using the information it obtains from other processors concerning the remaining components of the vector. The proposed asynchronous algorithm is shown to converge when the processors iterate at different speeds, some performing more iterations than others, when the information received by a processor regarding the other components of the vector may be outdated or may have been received out of order, or when there may be an unpredictable delay in obtaining information from other processors