Optimization Online


Parameter-free Sampled Fictitious Play for Solving Deterministic Dynamic Programming Problems

Irina Dolinskaya(dolira***at***northwestern.edu)
Marina Epelman(mepelman***at***umich.edu)
Esra Sisikoglu(esras***at***antalya.edu.tr)
Robert L. Smith(rlsmith***at***umich.edu)

Abstract: 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.

Keywords: Sampled Fictitious Play, Dynamic Programming, Maritime navigation

Category 1: Network Optimization

Category 2: Other Topics (Dynamic Programming )

Category 3: Applications -- OR and Management Sciences (Transportation )

Citation: Working Paper No. 14-04, Department of Industrial Engineering and Management Sciences Northwestern University, Evanston, Illinois, 60208-3119, U.S.A. November 2014

Download: [PDF]

Entry Submitted: 11/20/2014
Entry Accepted: 11/21/2014
Entry Last Modified: 11/20/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society