Distributed dynamic programming
By Dimitri P. Bertsekas. 1981
We consider distributed algorithms for solving dynamic programming problems whereby several processors participate simultaneously in the computation while maintaining coordination by information exchange via communication links. A model of asynchronous distributed computation is developed which requires very weak assumptions on the ordering of computations, the timing of information exchange, the amount of local information needed at each computation node, and the initial conditions for the algorithm. The class of problems considered is very broad and includes shortest path problems, and finite and infinite horizon stochastic optimal control problems. When specialized to a shortest path problem the algorithm reduces to the algorithm originally implemented for routing of messages in the ARPANET.
Subfields: Natural Language Processing, Algorithms & Complexity
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Natural Language Processing
- John N. Tsitsiklis
- Timothy P. Lillicrap
- Koray Kavukcuoglu
- David Silver
- Mehdi Mirza
- Alex Graves
- Volodymyr Mnih
- Tim Harley
In Algorithms & Complexity
- John N. Tsitsiklis
- David Silver
- Dimitri P. Bertsekas
- Koray Kavukcuoglu
- Volodymyr Mnih
- Adrià Puigdomènech Badia
- Angelia Nedić
- Asuman E. Ozdaglar
Citations in the corpus
- Asynchronous Methods for Deep Reinforcement Learning (2016, background): “Even earlier, (Bertsekas, 1982) studied the related problem of distributed dynamic programming.”
- Distributed asynchronous computation of fixed points (1983, background): “Actually the problem above is representative of a broad class of dynamic programming problems which can be viewed as special cases of the fixed point problem (6) and can be correctly solved by using the distributed algorithm of this paper (see [ 4 ]).”
- Concurrent Reinforcement Learning from Customer Interactions (2013, background): “Perhaps the best known approach is distributed dynamic programming (Bertsekas, 1982; Archibald, 1992), in which Bellman backups can be applied to different states, in parallel and asynchronously; the value function is then communicated between all processors.”
- Asynchronous stochastic approximation and Q-learning (1993, methodology): “In particular, we can prove convergence for undiscounted problems without assuming that all policies must lead to a zero-cost absorbing state; we allow the costs per stage to be unbounded random variables; we allow the decision on which action to simulate next to depend on past experience, and, fina”