Approximate Dynamic Programming
By Warrren B Powell. 2007
2,143 citations recorded by the source corpus.
Preface. Acknowledgments. 1. The challenges of dynamic programming. 1.1 A dynamic programming example: a shortest path problem. 1.2 The three curses of dimensionality. 1.3 Some real applications. 1.4 Problem classes. 1.5 The many dialects of dynamic programming. 1.6 What is new in this book? 1.7 Bibliographic notes. 2. Some illustrative models. 2.1 Deterministic problems. 2.2 Stochastic problems. 2.3 Information acquisition problems. 2.4 A simple modeling framework for dynamic programs. 2.5 Bibliographic notes. Problems. 3. Introduction to Markov decision processes. 3.1 The optimality equations. 3.2 Finite horizon problems. 3.3 Infinite horizon problems. 3.4 Value iteration. 3.5 Policy iteration. 3.6 Hybrid valuepolicy iteration. 3.7 The linear programming method for dynamic programs. 3.8 Monotone policies. 3.9 Why does it work? 3.10 Bibliographic notes. Problems 4. Introduction to approximate dynamic programming. 4.1 The three curses of dimensionality (revisited). 4.2 The basic idea. 4.3 Sampling random variables . 4.4 ADP using the postdecision state variable. 4.5 Lowdimensional representations of value functions. 4.6 So just what is approximate dynamic programming? 4.7 Experimental issues. 4.8 Dynamic programming with missing or incomplete models. 4.9 Relationship to reinforcement learning. 4.10 But does it work? 4.11 Bibliographic notes. Problems. 5. Modeling dynamic programs. 5.1 Notational style. 5.2 Modeling time. 5.3 Modeling resources. 5.4 The states of our system. 5.5 Modeling decisions. 5.6 The exogenous information process. 5.7 The transition function. 5.8 The contribution function. 5.9 The objective function. 5.10 A measuretheoretic view of information. 5.11 Bibliographic notes. Problems. 6. Stochastic approximation methods. 6.1 A stochastic gradient algorithm. 6.2 Some stepsize recipes. 6.3 Stochastic stepsizes. 6.4 Computing bias and variance. 6.5 Optimal stepsizes. 6.6 Some experimental comparisons of stepsize formulas. 6.7 Convergence. 6.8 Why does it work? 6.9 Bibliographic notes. Problems. 7. Approximating value functions. 7.1 Approximation using aggregation. 7.2 Approximation methods using regression models. 7.3 Recursive methods for regression models. 7.4 Neural networks. 7.5 Batch processes. 7.6 Why does it work? 7.7 Bibliographic notes. Problems. 8. ADP for finite horizon problems. 8.1 Strategies for finite horizon problems. 8.2 Qlearning. 8.3 Temporal difference learning. 8.4 Policy iteration. 8.5 Monte Carlo value and policy iteration. 8.6 The actorcritic paradigm. 8.7 Bias in value function estimation. 8.8 State sampling strategies. 8.9 Starting and stopping. 8.10 A taxonomy of approximate dynamic programming strategies. 8.11 Why does it work? 8.12 Bibliographic notes. Problems. 9. Infinite horizon problems. 9.1 From finite to infinite horizon. 9.2 Algorithmic strategies. 9.3 Stepsizes for infinite horizon problems. 9.4 Error measures. 9.5 Direct ADP for online applications. 9.6 Finite horizon models for steady state applications. 9.7 Why does it work? 9.8 Bibliographic notes. Problems. 10. Exploration vs. exploitation. 10.1 A learning exercise: the nomadic trucker. 10.2 Learning strategies. 10.3 A simple information acquisition problem. 10.4 Gittins indices and the information acquisition problem. 10.5 Variations. 10.6 The knowledge gradient algorithm. 10.7 Information acquisition in dynamic programming. 10.8 Bibliographic notes. Problems. 11. Value function approximations for special functions. 11.1 Value functions versus gradients. 11.2 Linear approximations. 11.3 Piecewise linear approximations. 11.4 The SHAPE algorithm. 11.5 Regression methods. 11.6 Cutting planes. 11.7 Why does it work? 11.8 Bibliographic notes. Problems. 12. Dynamic resource allocation. 12.1 An asset acquisition problem. 12.2 The blood management problem. 12.3 A portfolio optimization problem. 12.4 A general resource allocation problem. 12.5 A fleet management problem. 12.6 A driver management problem. 12.7 Bibliographic references. Problems. 13. Implementation challenges. 13.1 Will ADP work for your problem? 13.2 Designing an ADP algorithm for complex problems. 13.3 Debugging an ADP algorithm. 13.4 Convergence issues. 13.5 Modeling your problem. 13.6 Online vs. offline models. 13.7 If it works, patent it!
Subfields: Control and Systems Engineering, Economics and Econometrics, Algorithms & Complexity
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Control and Systems Engineering
- Jan Peters
- Hado van Hasselt
- Yuxi Li
- Sergey Levine
- Mohammad Ghavamzadeh
- Shie Mannor
- Csaba Szepesvari
- Frank L. Lewis
In Economics and Econometrics
- Hado van Hasselt
- Yuxi Li
- Alexander Teytelboym
- Frank L. Lewis
- Kyriakos G. Vamvoudakis
- Mohammad Ghavamzadeh
- Penny Mealy
- Draguna L. Vrabie
In Algorithms & Complexity
- Yuxi Li
- Hado van Hasselt
- Frank L. Lewis
- Jan Peters
- Kyriakos G. Vamvoudakis
- Draguna L. Vrabie
- Lauren Hannah
- Archis Vijay Ghate
Citations in the corpus
- Convex Optimization: Algorithms and Complexity (2015, positive): “Approximate value function methods [Bertsekas and Tsitsiklis, 1996] have proved successful for solving certain large scale problems [Powell, 2011], and policy search has been successfully applied to many robotics tasks [Kober et al., 2013].”
- Reinforcement Learning and Dynamic Programming Using Function Approximators (2010, background): “DP algorithms require a model of the MDP, including the trans ition dynamics and the reward function, to find an optimal policy (Bertsekas , 2007; Powell, 2007).”
- Multi-player non-zero-sum games: Online adaptive learning solution of coupled Hamilton-Jacobi equations (2011, background): “Reinforcement learning (RL) is a sub-area of machine learning concerned with how to methodically modify the actions of an agent (player) based on observed responses from its environment (Lewis & Vrabie, 2009, Powell, 2007, Sutton & Barto, 1998).”
- Reinforcement Learning and Feedback Control: Using Natural Decision Methods to Design Optimal Adaptive Controllers (2012, methodology): “These results are evaluated using a performance index, or value function [5], [6], [11], [17], [18], that quantifies how close the current action is to optimal.”
- Multistage Stochastic Programming: A Scenario Tree Based Approach to Planning under Uncertainty (2011, background): “…— where complex objectives and potentially conflicting requirements have to be taken into account — seems to be growing in the machine learning community , as indicated by a series of advances in approximate dynamic programming motivated by such applications (Powell, 2007; Csáji & Monostori, 2008).”
- A survey on dynamic and stochastic vehicle routing problems (2016, methodology): “This is demonstrated in an excellent tutorial onADPin the field of transportation and logistics in Powell, Simao, and Bouzaiene-Ayari (2012) and illustrated on different problem classes in Powell (2007).”
- A Markov decision process approach to temporal modulation of dose fractions in radiation therapy planning (2009, positive): “ADP methods have recently proven fruitful in computing adaptive fractionation schemes that compensate for dose delivery errors in previous fractions (Sir 2007, Ferris and Voelker 2004).”
- A Third Wave in the Economics of Climate Change (2015, methodology): “Further, new computational techniques, such as approximate dynamic programming approaches (Powell 2007) are helping incorporate more realistic modelling dynamics, while limiting the traditional increase in model dimensionality and state space size (Webster et al. 2012).”