Abstract
In this paper, we present a parameter-free variation of the Sampled Fictitious Play algorithm that facilitates fast solution of deterministic dynamic programming problems. Its random tie-breaking 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, a parameter-free Sampled Fictitious Play algorithm finds a high-quality solution after only a few iterations, in contrast with traditional methods.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 631-655 |
| Number of pages | 25 |
| Journal | Journal of Optimization Theory and Applications |
| Volume | 169 |
| Issue number | 2 |
| DOIs | |
| State | Published - May 1 2016 |
Funding
The authors would like to thank Okey Nwogu and Fernando Tavares for their assistance with implementation and numerical results. This work was supported in part by the Office of Naval Research through the Multidisciplinary University Research Initiative (MURI) Optimum Vessel Performance in Evolving Nonlinear Wave Fields Grant (N00014-05-1-0537).
Keywords
- Dynamic programming
- Maritime navigation
- Sampled fictitious play
ASJC Scopus subject areas
- Control and Optimization
- Applied Mathematics
- Management Science and Operations Research