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

Irina S. Dolinskaya*, Marina A. Epelman, Esra Şişikoğlu Sir, Robert L. Smith

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 languageEnglish (US)
Pages (from-to)631-655
Number of pages25
JournalJournal of Optimization Theory and Applications
Volume169
Issue number2
DOIs
StatePublished - May 1 2016

Keywords

  • Dynamic programming
  • Maritime navigation
  • Sampled fictitious play

ASJC Scopus subject areas

  • Control and Optimization
  • Management Science and Operations Research
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Parameter-Free Sampled Fictitious Play for Solving Deterministic Dynamic Programming Problems'. Together they form a unique fingerprint.

Cite this