Empirical dynamic programming
From MaRDI portal
Publication:2806811
simulationdynamic programmingMarkov decision processesrandom operatorsempirical methodsprobabilistic fixed points
Numerical mathematical programming methods (65K05) Empirical decision procedures; empirical Bayes procedures (62C12) Dynamic programming (90C39) Stochastic programming (90C15) Simulation of dynamical systems (37M05) Dynamic programming in optimal control and differential games (49L20) Markov and semi-Markov decision processes (90C40) Optimal stochastic control (93E20) Random linear operators (47B80) Random operators and equations (aspects of stochastic analysis) (60H25) Random dynamical systems (37H99)
Abstract: We propose empirical dynamic programming algorithms for Markov decision processes (MDPs). 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 5957196 (Why is no real title available?)
- scientific article; zbMATH DE number 3361677 (Why is no real title available?)
- 10.1162/153244303768966102
- A Stochastic Approximation Method
- A survey of some simulation-based algorithms for Markov decision processes
- Actor-Critic--Type Learning Algorithms for Markov Decision Processes
- Analysis of recursive stochastic algorithms
- Approximate Fixed Point Iteration with an Application to Infinite Horizon Markov Decision Processes
- Approximate policy iteration: a survey and some new methods
- Approximations of Dynamic Programs, I
- Approximations of Dynamic Programs, II
- Associative search network: A reinforcement learning associative memory
- CONVERGENCE OF SIMULATION-BASED POLICY ITERATION
- Comparison methods for stochastic models and risks
- Convergence rate of linear two-time-scale stochastic approximation.
- Finite-time bounds for fitted value iteration
- Functional Approximations and Dynamic Programming
- Learning algorithms for Markov decision processes with average cost
- Neural Network Learning
- Performance guarantees for empirical Markov decision processes with applications to multiperiod inventory models
- Q-Learning for Risk-Sensitive Control
- Simulation-based optimization of Markov decision processes: an empirical process theory approach
- Simulation‐based Uniform Value Function Estimates of Markov Decision Processes
- Stochastic Estimation of the Maximum of a Regression Function
- Stochastic Games
- The Complexity of Markov Decision Processes
- The O.D.E. Method for Convergence of Stochastic Approximation and Reinforcement Learning
- Using Randomization to Break the Curse of Dimensionality
- \({\mathcal Q}\)-learning
Cited in
(13)- Some limit properties of Markov chains induced by recursive stochastic algorithms
- scientific article; zbMATH DE number 1195626 (Why is no real title available?)
- Dynamic policy programming
- Robustness to incorrect models and data-driven learning in average-cost optimal stochastic control
- A concentration bound for contractive stochastic approximation
- Stochastic and adaptive optimal control of uncertain interconnected systems: a data-driven approach
- A simulation-based approach to stochastic dynamic programming
- Convergence of Recursive Stochastic Algorithms Using Wasserstein Divergence
- Empirical \(Q\)-value iteration
- Gradient-bounded dynamic programming for submodular and concave extensible value functions with probabilistic performance guarantees
- Mean-field controls with Q-learning for cooperative MARL: convergence and complexity analysis
- Distributionally robust optimization for sequential decision-making
- Anderson acceleration for partially observable Markov decision processes: a maximum entropy approach
This page was built for publication: Empirical dynamic programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2806811)
