Empirical Dynamic Programming
By William Benjamin Haskell, Rahul Jain, Dileep Manisseri Kalathil. 2013
69 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Computer Networks and Communications
In Management Science and Operations Research
Citations in the corpus
- Q-learning with Nearest Neighbors (2018, methodology): “Specific work Method Continuous Unknown Single Online Non-asymptotic state space transition Kernel sample path update guarantees [10], [36], [37] Finite-state approximation Yes No No Yes Yes [43], [22], [41] Q-learning No Yes Yes Yes No [20], [3], [18] Q-learning No Yes Yes Yes Yes [23] Q-learning N”