IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v169y2016i2d10.1007_s10957-015-0798-5.html
   My bibliography  Save this article

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

Author

Listed:
  • Irina S. Dolinskaya

    (Northwestern University)

  • Marina A. Epelman

    (University of Michigan)

  • Esra Şişikoğlu Sir

    (Office of Access Management, Mayo Clinic)

  • Robert L. Smith

    (University of Michigan)

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.

Suggested Citation

  • Irina S. Dolinskaya & Marina A. Epelman & Esra Şişikoğlu Sir & Robert L. Smith, 2016. "Parameter-Free Sampled Fictitious Play for Solving Deterministic Dynamic Programming Problems," Journal of Optimization Theory and Applications, Springer, vol. 169(2), pages 631-655, May.
    • Handle: RePEc:spr:joptap:v:169:y:2016:i:2:d:10.1007_s10957-015-0798-5
    DOI: 10.1007/s10957-015-0798-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-015-0798-5
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10957-015-0798-5?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Jeffrey M. Alden & Robert L. Smith, 1992. "Rolling Horizon Procedures in Nonhomogeneous Markov Decision Processes," Operations Research, INFORMS, vol. 40(3-supplem), pages 183-194, June.
    2. Theodore J. Lambert & Marina A. Epelman & Robert L. Smith, 2005. "A Fictitious Play Approach to Large-Scale Optimization," Operations Research, INFORMS, vol. 53(3), pages 477-489, June.
    3. Alfredo Garcia & Stephen D. Patek & Kaushik Sinha, 2007. "A Decentralized Approach to Discrete Optimization via Simulation: Application to Network Flow," Operations Research, INFORMS, vol. 55(4), pages 717-732, August.
    4. Philpott, A. B. & Sullivan, R. M. & Jackson, P. S., 1993. "Yacht velocity prediction using mathematical programming," European Journal of Operational Research, Elsevier, vol. 67(1), pages 13-24, May.
    5. Garcia, Alfredo & Reaume, Daniel & Smith, Robert L., 2000. "Fictitious play for finding system optimal routings in dynamic traffic networks," Transportation Research Part B: Methodological, Elsevier, vol. 34(2), pages 147-156, February.
    6. Monderer, Dov & Shapley, Lloyd S., 1996. "Fictitious Play Property for Games with Identical Interests," Journal of Economic Theory, Elsevier, vol. 68(1), pages 258-265, January.
    7. Anastassios N. Perakis & Nikiforos A. Papadakis, 1989. "Minimal Time Vessel Routing in a Time-Dependent Environment," Transportation Science, INFORMS, vol. 23(4), pages 266-276, November.
    8. Stuart E. Dreyfus, 1969. "An Appraisal of Some Shortest-Path Algorithms," Operations Research, INFORMS, vol. 17(3), pages 395-412, June.
    9. Archis Ghate & Shih-Fen Cheng & Stephen Baumert & Daniel Reaume & Dushyant Sharma & Robert Smith, 2014. "Sampled fictitious play for multi-action stochastic dynamic programs," IISE Transactions, Taylor & Francis Journals, vol. 46(7), pages 742-756.
    10. Chung-Yee Lee & Eric V. Denardo, 1986. "Rolling Planning Horizons: Error Bounds for the Dynamic Lot Size Model," Mathematics of Operations Research, INFORMS, vol. 11(3), pages 423-432, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Irina S. Dolinskaya, 2012. "Optimal path finding in direction, location, and time dependent environments," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(5), pages 325-339, August.
    2. Swenson, Brian & Murray, Ryan & Kar, Soummya, 2020. "Regular potential games," Games and Economic Behavior, Elsevier, vol. 124(C), pages 432-453.
    3. Enrique Campos-Nañez & Alfredo Garcia & Chenyang Li, 2008. "A Game-Theoretic Approach to Efficient Power Management in Sensor Networks," Operations Research, INFORMS, vol. 56(3), pages 552-561, June.
    4. Alfredo Garcia & Stephen D. Patek & Kaushik Sinha, 2007. "A Decentralized Approach to Discrete Optimization via Simulation: Application to Network Flow," Operations Research, INFORMS, vol. 55(4), pages 717-732, August.
    5. Berger, Ulrich, 2005. "Fictitious play in 2 x n games," Journal of Economic Theory, Elsevier, vol. 120(2), pages 139-154, February.
    6. Ulrich Berger, 2004. "Two More Classes of Games with the Fictitious Play Property," Game Theory and Information 0408003, University Library of Munich, Germany.
    7. Suresh Chand & Vernon Ning Hsu & Suresh Sethi, 2002. "Forecast, Solution, and Rolling Horizons in Operations Management Problems: A Classified Bibliography," Manufacturing & Service Operations Management, INFORMS, vol. 4(1), pages 25-43, September.
    8. Ryan, Sarah M., 1998. "Forecast frequency in rolling horizon hedging heuristics for capacity expansion," European Journal of Operational Research, Elsevier, vol. 109(3), pages 550-558, September.
    9. Theodore J. Lambert & Marina A. Epelman & Robert L. Smith, 2005. "A Fictitious Play Approach to Large-Scale Optimization," Operations Research, INFORMS, vol. 53(3), pages 477-489, June.
    10. Ulrich Berger, 2004. "Some Notes on Learning in Games with Strategic Complementarities," Game Theory and Information 0409001, University Library of Munich, Germany.
    11. Marden, Jason R. & Shamma, Jeff S., 2015. "Game Theory and Distributed Control****Supported AFOSR/MURI projects #FA9550-09-1-0538 and #FA9530-12-1-0359 and ONR projects #N00014-09-1-0751 and #N0014-12-1-0643," Handbook of Game Theory with Economic Applications,, Elsevier.
    12. Berger, Ulrich, 2007. "Two more classes of games with the continuous-time fictitious play property," Games and Economic Behavior, Elsevier, vol. 60(2), pages 247-261, August.
    13. Anthonisen, Niels, 1997. "On the Convergence of Beliefs within Populations in Games with Learning," Journal of Economic Theory, Elsevier, vol. 76(1), pages 169-184, September.
    14. Benaïm, Michel & Hofbauer, Josef & Hopkins, Ed, 2009. "Learning in games with unstable equilibria," Journal of Economic Theory, Elsevier, vol. 144(4), pages 1694-1709, July.
    15. Eugenio Vecchia & Silvia Marco & Alain Jean-Marie, 2012. "Illustrated review of convergence conditions of the value iteration algorithm and the rolling horizon procedure for average-cost MDPs," Annals of Operations Research, Springer, vol. 199(1), pages 193-214, October.
    16. Stanislaw Bylka, 1997. "Strong turnpike policies in the single‐item capacitated lot‐sizing problem with periodical dynamic parameter," Naval Research Logistics (NRL), John Wiley & Sons, vol. 44(8), pages 775-790, December.
    17. Shuaian Wang & Dan Zhuge & Lu Zhen & Chung-Yee Lee, 2021. "Liner Shipping Service Planning Under Sulfur Emission Regulations," Transportation Science, INFORMS, vol. 55(2), pages 491-509, March.
    18. Pijls, Wim & Post, Henk, 2009. "A new bidirectional search algorithm with shortened postprocessing," European Journal of Operational Research, Elsevier, vol. 198(2), pages 363-369, October.
    19. Rossella Argenziano & Itzhak Gilboa, 2012. "History as a coordination device," Theory and Decision, Springer, vol. 73(4), pages 501-512, October.
    20. Hopkins, Ed, 1999. "Learning, Matching, and Aggregation," Games and Economic Behavior, Elsevier, vol. 26(1), pages 79-110, January.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joptap:v:169:y:2016:i:2:d:10.1007_s10957-015-0798-5. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.