To facilitate fast solution of deterministic dynamic programming problems, we present a parameter-free variation of the Sampled Fictitious Play (SFP) algorithm. Its random tie-braking procedure imparts a natural randomness to the algorithm which prevents it from “getting stuck” at a local optimal solution and allows the discovery of an optimal path in a finite number of iterations. Furthermore, we illustrate through an application to maritime navigation that, in practice, parameter-free SFP finds a high quality solution after only a few iterations, in contrast with traditional methods.
Citation
Working Paper No. 14-04, Department of Industrial Engineering and Management Sciences Northwestern University, Evanston, Illinois, 60208-3119, U.S.A. November 2014