Empirical Dynamic Programming
Authors:
- 1 May 2016
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 41 (2) , 402-429
Abstract
We propose empirical dynamic programming algorithms for Markov decision processes. In these algorithms, the exact expectation in the Bellman operator in classical value iteration is replaced by an empirical estimate to get “empirical value iteration” (EVI). Policy evaluation and policy improvement in classical policy iteration are also replaced by simulation to get “empirical policy iteration” (EPI). Thus, these empirical dynamic programming algorithms involve iteration of a random operator, the empirical Bellman operator. We introduce notions of probabilistic fixed points for such random monotone operators. We develop a stochastic dominance framework for convergence analysis of such operators. We then use this to give sample complexity bounds for both EVI and EPI. We then provide various variations and extensions to asynchronous empirical dynamic programming, the minimax empirical dynamic program, and show how this can also be used to solve the dynamic newsvendor problem. Preliminary experimental results suggest a faster rate of convergence than stochastic approximation algorithms.Keywords
All Related Versions
This publication has 32 references indexed in Scilit:
- Simulation-based optimization of Markov decision processes: An empirical process theory approachAutomatica, 2010
- Simulation‐based Uniform Value Function Estimates of Markov Decision ProcessesSIAM Journal on Control and Optimization, 2006
- Convergence rate of linear two-time-scale stochastic approximationThe Annals of Applied Probability, 2004
- CONVERGENCE OF SIMULATION-BASED POLICY ITERATIONProbability in the Engineering and Informational Sciences, 2003
- Using Randomization to Break the Curse of DimensionalityEconometrica, 1997
- Finite time analysis of the pursuit algorithm for learning automataIEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 1996
- Analysis of recursive stochastic algorithmsIEEE Transactions on Automatic Control, 1977
- Functional Approximations and Dynamic ProgrammingMathematical Tables and Other Aids to Computation, 1959
- Stochastic Estimation of the Maximum of a Regression FunctionThe Annals of Mathematical Statistics, 1952
- A Stochastic Approximation MethodThe Annals of Mathematical Statistics, 1951