The complexity of dynamic programming

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

John N. Tsitsiklis, Chee-Seng Chow

Publication date: 1989

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

zbMATH Keywords

computational complexity; stochastic control; discrete-time, stationary, infinite horizon, discounted; discrete-time, stationary, infinite horizon, discounted stochastic control; tight lower bounds

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C15: Stochastic programming

90C39: Dynamic programming

93E20: Optimal stochastic control

03D15: Complexity of computation (including implicit computational complexity)

Related Items

A survey of computational complexity results in systems and control, Policy iteration accelerated with Krylov methods, Knows what it knows: a framework for self-aware learning, Reducing reinforcement learning to KWIK online regression, Risk, uncertainty, and complexity, Computability, complexity and economics, On the complexity of linear quadratic control, Dimension reduction and its application to model-based exploration in continuous spaces

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