The Linear Programming Approach to Approximate Dynamic Programming

DOI10.1287/opre.51.6.850.24925zbMath1165.90666OpenAlexW1745373831MaRDI QIDQ3637395

Benjamin van Roy, D. P. de Farias

Publication date: 9 July 2009

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.51.6.850.24925

Mathematics Subject Classification ID

Dynamic programming in optimal control and differential games (49L20) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Dynamic programming (90C39)

Related Items (86)

Least squares policy iteration with instrumental variables vs. direct policy search: comparison against optimal benchmarks using energy storage ⋮ Ambiguous partially observable Markov decision processes: structural results and applications ⋮ Smoothing and parametric rules for stochastic mean-CVaR optimal execution strategy ⋮ Practical solution techniques for first-order MDPs ⋮ Approximate dynamic programming for stochastic linear control problems on compact state spaces ⋮ A new learning algorithm for optimal stopping ⋮ On the computational complexity and generalization properties of multi-stage and stage-wise coupled scenario programs ⋮ Technical Note—Product-Based Approximate Linear Programs for Network Revenue Management ⋮ APPROXIMATE DYNAMIC PROGRAMMING TECHNIQUES FOR THE CONTROL OF TIME-VARYING QUEUING SYSTEMS APPLIED TO CALL CENTERS WITH ABANDONMENTS AND RETRIALS ⋮ A Polyhedral Approach to Online Bipartite Matching ⋮ ONLINE CAPACITY PLANNING FOR REHABILITATION TREATMENTS: AN APPROXIMATE DYNAMIC PROGRAMMING APPROACH ⋮ Approximate linear programming for networks: average cost bounds ⋮ Accelerated modified policy iteration algorithms for Markov decision processes ⋮ Unnamed Item ⋮ Symmetric approximate linear programming for factored MDPs with application to constrained problems ⋮ From Infinite to Finite Programs: Explicit Error Bounds with Applications to Approximate Dynamic Programming ⋮ Queueing Network Controls via Deep Reinforcement Learning ⋮ Partially observable multistage stochastic programming ⋮ Viability, viscosity, and storage functions in model-predictive control with terminal constraints ⋮ A variable neighborhood search based algorithm for finite-horizon Markov decision processes ⋮ Dynamic inventory control with payment delay and credit limit ⋮ A perspective-based convex relaxation for switched-affine optimal control ⋮ The policy graph decomposition of multistage stochastic programming problems ⋮ SOS-based policy iteration for H_∞ control of polynomial systems with uncertain parameters ⋮ Decomposable Markov Decision Processes: A Fluid Optimization Approach ⋮ State partitioning based linear program for stochastic dynamic programs: an invariance property ⋮ Unnamed Item ⋮ From Reinforcement Learning to Deep Reinforcement Learning: An Overview ⋮ Reductions of non-separable approximate linear programs for network revenue management ⋮ Network revenue management with inventory-sensitive bid prices and customer choice ⋮ MF-OMO: An Optimization Formulation of Mean-Field Games ⋮ Minimizing total tardiness in a stochastic single machine scheduling problem using approximate dynamic programming ⋮ Stochastic control via direct comparison ⋮ Managing Patient Admissions in a Neurology Ward ⋮ A framework and a mean-field algorithm for the local control of spatial processes ⋮ Randomized Linear Programming Solves the Markov Decision Problem in Nearly Linear (Sometimes Sublinear) Time ⋮ Approximate dynamic programming for capacity allocation in the service industry ⋮ Approximations to Stochastic Dynamic Programs via Information Relaxation Duality ⋮ Computational bounds for elevator control policies by large scale linear programming ⋮ Multiagent Mechanism Design Without Money ⋮ Computing Controlled Invariant Sets from Data Using Convex Optimization ⋮ Relationship between least squares Monte Carlo and approximate linear programming ⋮ Linear programming formulation for non-stationary, finite-horizon Markov decision process models ⋮ Large-scale unit commitment under uncertainty: an updated literature survey ⋮ Shape constraints in economics and operations research ⋮ Network-Based Approximate Linear Programming for Discrete Optimization ⋮ Toward Breaking the Curse of Dimensionality: An FPTAS for Stochastic Dynamic Programs with Multidimensional Actions and Scalar States ⋮ An approximate dynamic programming approach for sequential pig marketing decisions at herd level ⋮ A dynamic programming approach to the multiple-choice multi-period knapsack problem and the recursive APL2 code ⋮ An Approximation Approach for Response-Adaptive Clinical Trial Design ⋮ Strategic capacity decision-making in a stochastic manufacturing environment using real-time approximate dynamic programming ⋮ Relaxation Analysis for the Dynamic Knapsack Problem with Stochastic Item Sizes ⋮ Convergence rates of moment-sum-of-squares hierarchies for optimal control problems ⋮ Quadratic approximate dynamic programming for input‐affine systems ⋮ A column and constraint generation algorithm for the dynamic knapsack problem with stochastic item sizes ⋮ Dynamic multi-appointment patient scheduling for radiation therapy ⋮ Partially observable Markov decision process approximations for adaptive sensing ⋮ A linear programming methodology for approximate dynamic programming ⋮ Decomposition of large-scale stochastic optimal control problems ⋮ A dynamic programming framework for optimal delivery time slot pricing ⋮ Reductions of Approximate Linear Programs for Network Revenue Management ⋮ Was Angelina Jolie Right? Optimizing Cancer Prevention Strategies Among BRCA Mutation Carriers ⋮ Dynamic programming and suboptimal control: a survey from ADP to MPC ⋮ Linear Programming and the Control of Diffusion Processes ⋮ A polyhedral approach to online bipartite matching ⋮ An AO^* Based Exact Algorithm for the Canadian Traveler Problem ⋮ An iterative approach to the optimal co-design of linear control systems ⋮ A dynamic programming extension to the steady state refinery-LP ⋮ Computing Near-Optimal Policies in Generalized Joint Replenishment ⋮ Semi-Infinite Relaxations for the Dynamic Knapsack Problem with Stochastic Item Sizes ⋮ An LP based approximate dynamic programming model to address airline overbooking under cancellation, refund and no-show ⋮ Exploiting bounded rationality in risk-based cyber camouflage games ⋮ Gradient-bounded dynamic programming for submodular and concave extensible value functions with probabilistic performance guarantees ⋮ Data-driven optimal control with a relaxed linear program ⋮ Transmission scheduling for multi-process multi-sensor remote estimation via approximate dynamic programming ⋮ An approximate dynamic programming approach for the vehicle routing problem with stochastic demands ⋮ Performance bounds and suboptimal policies for linear stochastic control via LMIs ⋮ A Continuous-Time Markov Decision Process for Infrastructure Surveillance ⋮ SDDP.jl: A Julia Package for Stochastic Dual Dynamic Programming ⋮ A Finite Time Analysis of Temporal Difference Learning with Linear Function Approximation ⋮ Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs ⋮ Dynamic node packing ⋮ Approximate dynamic programming via iterated Bellman inequalities ⋮ Randomized methods for design of uncertain systems: sample complexity and sequential algorithms ⋮ Unnamed Item ⋮ Large-scale unit commitment under uncertainty

This page was built for publication: The Linear Programming Approach to Approximate Dynamic Programming