The Linear Programming Approach to Approximate Dynamic Programming
Operations ResearchPublished 1 December 2003
Daniela Pucci de Farias, Benjamin Van Roy
Citations709
SJR quartileQ1
SJR score2.56
SNIP1.83
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An efficient method based on linear programming for approximating solutions to large-scale stochastic control problems by "fits" a linear combination of pre-selected basis functions to the dynamic programming cost-to-go function.
Abstract
The curse of dimensionality gives rise to prohibitive computational requirements that render infeasible the exact solution of large-scale stochastic control problems. We study an efficient method based on linear programming for approximating solutions to such problems. The approach “fits” a linear combination of pre-selected basis functions to the dynamic programming cost-to-go function. We develop error bounds that offer performance guarantees and also guide the selection of both basis functions and “state-relevance weights” that influence quality of the approximation. Experimental results in the domain of queueing network control provide empirical support for the methodology.
Keywords
Computer ScienceDecision SciencesBusiness, Management and Accounting
Choice Reviews OnlineNeural networks for pattern recognition
18,687 Citations1994
This is the first comprehensive treatment of feed-forward neural networks from the perspective of statistical pattern recognition, and is designed as a text, with over 100 exercises, to benefit anyone involved in the fields of neural computation and pattern recognition.
Neural Networks for Pattern Recognition
12,198 Citations1995Chris Bishop
Machine LearningLearning to Predict by the Methods of Temporal Differences
3,894 Citations1988Richard S. Sutton
This article introduces a class of incremental learning procedures specialized for prediction-that is, for using past experience with an incompletely known system to predict its future behavior, and proves their convergence and optimality for special cases and relate them to supervised-learning methods.
Review of Financial StudiesValuing American Options by Simulation: A Simple Least-Squares Approach
3,260 Citations2001Francis A. Longstaff, Eduardo S. Schwartz
The key to this approach is the use of least squares to estimate the conditional expected payoff to the optionholder from continuation, which makes this approach readily applicable in path-dependent and multifactor situations where traditional finite difference techniqes cannot be used.
Machine LearningLearning to predict by the methods of temporal differences
2,758 Citations1988Richard S. Sutton
Communications of the ACMTemporal difference learning and TD-Gammon
1,485 Citations1995Gerald Tesauro
The domain of complex board games such as Go, chess, checkers, Othello, and backgammon has been widely regarded as an ideal testing ground for exploring a variety of concepts and approaches in artificial intelligence and machine learning.
IEEE Transactions on Automatic ControlAn analysis of temporal-difference learning with function approximation
1,202 Citations1997John N. Tsitsiklis, Benjamin Van Roy
It is proved that divergence may occur when updates are not based on trajectories of the Markov chain, which reconciles positive and negative results that have been discussed in the literature, regarding the soundness of temporal-difference learning.
IEEE Transactions on Neural NetworksRegression methods for pricing complex American-style options
636 Citations2001John N. Tsitsiklis, Benjamin Van Roy
A simulation-based approximate dynamic programming method for pricing complex American-style options, with a possibly high-dimensional underlying state space, and a related method which uses a single (parameterized) value function, which is a function of the time-state pair.
Improving Elevator Performance Using Reinforcement Learning
495 Citations1995Robert H. Crites, Andrew G. Barto
Results in simulation surpass the best of the heuristic elevator control algorithms of which the author is aware and demonstrate the power of RL on a very large scale stochastic dynamic optimization problem of practical utility.
IEEE Transactions on Automatic ControlDynamic instabilities and stabilization methods in distributed real-time scheduling of manufacturing systems
359 Citations1990P. R. Kumar, Thomas I. Seidman
IEEE/ACM Transactions on NetworkingCongestion-dependent pricing of network services
354 Citations2000Ioannis Ch. Paschalidis, John N. Tsitsiklis
It is shown analytically and computationally, that the performance of an optimal pricing strategy is closely matched by a suitably chosen static price, which does not depend on instantaneous congestion, which indicates that the easily implementable time-of-day pricing will often suffice.
Journal of Mathematical Analysis and ApplicationsGeneralized polynomial approximations in Markovian decision processes
349 Citations1985Paul J. Schweitzer, Abraham Seidmann
Machine LearningThe convergence of TD(?) for general ?
279 Citations1992Peter Dayan
Watkins' theorem that Q-learning, his closely related prediction and action learning method, converges with probability one is adapted to demonstrate this strong form of convergence for a slightly modified version of TD.
Mathematical ProgrammingSolution of large-scale symmetric travelling salesman problems
273 Citations1991Martin Grötschel, Olaf Holland
The implementation is based on a fast LP-solver (IBM's MPSX) and makes effective use of polyhedral results on the symmetric travelling salesman polytope and describes the important ingredients of the code.
Management ScienceA Probabilistic Production and Inventory Problem
203 Citations1963F. d'Epenoux
This paper presents a synthesis of both dynamic and linear programming methods applicable to the same kind of model for the case of time discounting, and gives order quantities as a function of initial stock levels.
Operations ResearchApplying Experimental Design and Regression Splines to High-Dimensional Continuous-State Stochastic Dynamic Programming
150 Citations1999Victoria C. P. Chen, David Ruppert +1 more
This paper describes a method for estimating the future value function by multivariate adaptive regression splines (MARS) fit over a discretization scheme based on orthogonal array (OA) experimental designs and shows that this method is accurately able to solve higher dimensional SDP problems than previously possible.
Management ScienceLinear Programming and Markov Decision Chains
146 Citations1979Arie Hordijk, L. C. M. Kallenberg
It is shown that for a finite Markov decision process an average optimal policy can be found by solving only one linear programming problem.
Research Showcase @ Carnegie Mellon University (Carnegie Mellon University)Approximate Solutions to Markov Decision Processes
142 Citations2018Geoffrey J. Gordon
This thesis aims for a middle ground, between algorithms that don't scale well because they use an impoverished representation for the evaluation function and algorithms that the authors can't analyze because they used too complicated a representation.
The Annals of Applied ProbabilityPerformance of Multiclass Markovian Queueing Networks Via Piecewise Linear Lyapunov Functions
135 Citations2001Dimitris Bertsimas, David Gamarnik +1 more
A deeper connection between stability and performance of Markovian multiclass queueing networks is established by showing that if there exist linear and piecewise linear Lyapunov functions that show stability, then these Lyap unov functions can be used to establish geometric-type lower and upper bounds on the tail probabilities, and thus boundson the expectation of the queue lengths.
Probability Theory and Related FieldsA convex analytic approach to Markov decision processes
108 Citations1988Vivek S. Borkar
Management ScienceOn Linear Programming in a Markov Decision Problem
100 Citations1970Eric V. Denardo
Neural Information Processing SystemsHigh-Performance Job-Shop Scheduling With A Time-Delay TD(λ) Network
92 Citations1995Wei Zhang, Thomas G. Dietterich
Experimental tests show that this TDNN-TD(λ) network can match the performance of the previous hand-engineered system, and both neural network approaches significantly outperform the best previous (non-learning) solution to this problem.
DSpace@MIT (Massachusetts Institute of Technology)Learning and value function approximation in complex decision processes
80 Citations1998Benjamin Van Roy, John N. Tsitsiklis
This thesis provides an analysis (a proof of convergence, together with bounds on approximation error) of temporal-difference learning in the context of autonomous (uncontrolled) systems as applied to the approximation of an infinite horizon discounted rewards and average and differential rewards.
Macroeconomic DynamicsSPLINE APPROXIMATIONS TO VALUE FUNCTIONS
80 Citations1997Michael A. Trick, Stanley E. Zin
The properties of algorithms that characterize the solution of the Bellman equation of a stochastic dynamic program, as the solution to a linear program, are reviewed, showing that fitting this approximation through linear programming provides upper and lower bounds on the solutions to the original large problem.
Queueing SystemsValue iteration and optimization of multiclass queueing networks
76 Citations1999Rong‐Rong Chen, Sean Meyn
Journal of Optimization Theory and ApplicationsOn the Existence of Fixed Points for Approximate Value Iteration and Temporal-Difference Learning
70 Citations2000Daniela Pucci de Farias, Benjamin Van Roy
It is shown that, in general, the modified dynamic programming operator need not possess a fixed point; therefore, approximate value iteration should not be expected to converge and a variant of approximatevalue iteration is proposed for which the associated operator is guaranteed to possess at least one fixed point.
Direct value-approximation for factored MDPs
69 Citations2001Dale Schuurmans, Relu Patrascu
This paper presents a simple approach for computing reasonable policies for factored Markov decision processes (MDPs), when the optimal value function can be approximated by a compact linear form.
Journal of Optimization Theory and ApplicationsNew Linear Program Performance Bounds for Queueing Networks
58 Citations1999James R. Morrison, P. R. Kumar
A systematic procedure for choosing different quadratic functions on the relative interiors of faces to serve as surrogates of the differential costs in an inequality relaxation of the average cost function leads to linear program bounds.