The complexity of dynamic programming

DOI10.1016/0885-064X(89)90021-6zbMath0685.90098OpenAlexW2006583280MaRDI QIDQ1262227

John N. Tsitsiklis, Chee-Seng Chow

Publication date: 1989

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0885-064x(89)90021-6

zbMATH Keywords

computational complexitystochastic controldiscrete-time, stationary, infinite horizon, discounteddiscrete-time, stationary, infinite horizon, discounted stochastic controltight lower bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Stochastic programming (90C15) Dynamic programming (90C39) Optimal stochastic control (93E20) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (max. 100)

On the complexity of linear quadratic control ⋮ Finite-horizon Gaussianity-preserving event-based sensor scheduling in Kalman filter applications ⋮ A consumption and investment problem via a Markov decision processes approach with random horizon ⋮ Reducing reinforcement learning to KWIK online regression ⋮ Knows what it knows: a framework for self-aware learning ⋮ Dimension reduction and its application to model-based exploration in continuous spaces ⋮ Symmetric Markovian games of commons with potentially sustainable endogenous growth ⋮ A survey of computational complexity results in systems and control ⋮ Policy iteration accelerated with Krylov methods ⋮ Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs ⋮ Risk, uncertainty, and complexity ⋮ Computability, complexity and economics

Cites Work

• Stochastic optimal control. The discrete time case
• The Complexity of Markov Decision Processes
• Convergence of discretization procedures in dynamic programming
• Approximations of Dynamic Programs, I
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of dynamic programming