A Floyd-Warshall Approach to Value Computation in Markov Decision Processes

This paper revisits the value and policy iteration paradigm and examines a depth-first search strategy that reformulates the average reward computation as an integral over (future) paths that is better expressed in the formalism of weighted automata.