From Infinite to Finite Programs: Explicit Error Bounds with Applications to Approximate Dynamic Programming

DOI10.1137/17M1133087zbMath1422.90021arXiv1701.06379OpenAlexW2582186538MaRDI QIDQ4571046

Daniel Kuhn, Peyman Mohajerin Esfahani, Tobias Sutter, John Lygeros

Publication date: 6 July 2018

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1701.06379

zbMATH Keywords

Markov decision processesinfinite-dimensional linear programmingapproximate dynamic programmingrandomized and convex optimization

Mathematics Subject Classification ID

Linear programming (90C05) Dynamic programming (90C39) Semi-infinite programming (90C34) Markov and semi-Markov decision processes (90C40) Randomized algorithms (68W20)

Related Items (10)

Generalized maximum entropy estimation ⋮ The CoMirror algorithm with random constraint sampling for convex semi-infinite programming ⋮ Geometry of information structures, strategic measures and associated stochastic control topologies ⋮ From Infinite to Finite Programs: Explicit Error Bounds with Applications to Approximate Dynamic Programming ⋮ Dual Ascent and Primal-Dual Algorithms for Infinite-Horizon Nonstationary Markov Decision Processes ⋮ Dual-based methods for solving infinite-horizon nonstationary deterministic dynamic programs ⋮ Gradient-bounded dynamic programming for submodular and concave extensible value functions with probabilistic performance guarantees ⋮ Data-driven optimal control with a relaxed linear program ⋮ An inexact primal-dual algorithm for semi-infinite programming ⋮ A Simplex Method for Countably Infinite Linear Programs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Smooth minimization of non-smooth functions
• The stochastic reach-avoid problem and set characterization for diffusions
• First-order methods of smooth convex optimization with inexact oracle
• The Bernstein polynomial basis: a centennial retrospective
• A linear programming formulation for constrained discounted continuous control for piecewise deterministic Markov processes
• Risk-averse dynamic programming for Markov decision processes
• Approximation of Markov decision processes with general state space
• On general minimax theorems
• Approximating integrals of multivariate exponentials: A moment approach
• Stochastic optimal control. The discrete time case
• Extremal points and optimal solutions for general capacity problems
• I-divergence geometry of probability distributions and minimization problems
• Introductory lectures on convex optimization. A basic course.
• Adaptive Markov control processes
• Theory and practice of finite elements.
• Stochastic approximations of constrained discounted Markov decision processes
• Rationally Inattentive Control of Markov Processes
• Finite Linear Programming Approximations of Constrained Discounted Markov Decision Processes
• Motion Planning for Continuous-Time Stochastic Processes: A Dynamic Programming Approach
• Performance Bounds for the Scenario Approach and an Extension to a Class of Non-Convex Programs
• On the convergence rate of a modified Fourier series
• The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs
• Stochastic Control with Imperfect Models
• The Linear Programming Approach to Approximate Dynamic Programming
• Duality for Stochastic Programming Interpreted as L. P. in $L_p $-Space
• Convergence of discretization procedures in dynamic programming
• Multistage Stochastic Programming with Recourse As Mathematical Programming in an $L_p $ Space
• Approximation Schemes for Infinite Linear Programs
• An analysis of temporal-difference learning with function approximation
• Constrained Average Cost Markov Control Processes in Borel Spaces
• OnActor-Critic Algorithms
• From Infinite to Finite Programs: Explicit Error Bounds with Applications to Approximate Dynamic Programming
• Discrete-Time Controlled Markov Processes with Average Cost Criterion: A Survey
• Approximation of average cost Markov decision processes using empirical distributions and concentration inequalities
• On Constraint Sampling in the Linear Programming Approach to Approximate Dynamic Programming

This page was built for publication: From Infinite to Finite Programs: Explicit Error Bounds with Applications to Approximate Dynamic Programming