Bayesian Exploration for Approximate Dynamic Programming

Ilya O. Ryzhov (), Martijn R. K. Mes (), Warren B. Powell () and Gerald van den Berg ()
Additional contact information
Ilya O. Ryzhov: Robert H. Smith School of Business, University of Maryland, College Park, Maryland 20742; Institute for Systems Research, A. James Clark School of Engineering, University of Maryland, College Park, Maryland 20742
Martijn R. K. Mes: Industrial Engineering and Business Information Systems, University of Twente, 7500 AE Enschede, Netherlands
Warren B. Powell: Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08540
Gerald van den Berg: Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08540

Operations Research, 2019, vol. 67, issue 1, 198-214

Abstract: Approximate dynamic programming (ADP) is a general methodological framework for multistage stochastic optimization problems in transportation, finance, energy, and other domains. We propose a new approach to the exploration/exploitation dilemma in ADP that leverages two important concepts from the optimal learning literature: first, we show how a Bayesian belief structure can be used to express uncertainty about the value function in ADP; second, we develop a new exploration strategy based on the concept of value of information and prove that it systematically explores the state space. An important advantage of our framework is that it can be integrated into both parametric and nonparametric value function approximations, which are widely used in practical implementations of ADP. We evaluate this strategy on a variety of distinct resource allocation problems and demonstrate that, although more computationally intensive, it is highly competitive against other exploration strategies.

Keywords: approximate dynamic programming; optimal learning; Bayesian learning; correlated beliefs; value of information (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/opre.2018.1772 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:67:y:2019:i:1:p:198-214

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().