Dynamic Programming for Structured Continuous Markov Decision Problems

By Zhengzhu Feng, Richard Dearden, Nicolas Meuleau, Richard Washington. 2004

114 citations recorded by the source corpus.

We describe an approach for exploiting structure in Markov Decision Processes with continuous state variables. At each step of the dynamic programming, the state space is dynamically partitioned into regions where the value function is the same throughout the region. We first describe the algorithm for piecewise constant representations. We then extend it to piecewise linear representations, using techniques from POMDPs to represent and reason about linear surfaces efficiently. We show that for complex, structured problems, our approach exploits the natural structure so that optimal solutions can be computed efficiently.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Vaishak Belle
2. Davide Nitti
3. Martijn van Otterlo
4. Paolo Traverso
5. Malik Ghallab
6. Dana S. Nau
7. Luc De Raedt
8. Angelika Kimmig

In Computational Theory and Mathematics

1. Vaishak Belle
2. Paolo Traverso
3. Dana S. Nau
4. Luc De Raedt
5. Malik Ghallab
6. Martijn van Otterlo

Citations in the corpus

• Learning World Graphs to Accelerate Hierarchical Reinforcement Learning (2019, neutral): “, in our case, dynamic programming (Sutton; Feng et al., 2004).”
• Automated Planning and Acting (2016, methodology): “[188], and parametric function approximation by Liu and Koenig [390] and Kveton et al.”
• Solving Relational and First-Order Logical Markov Decision Processes: A Survey (2012, background): “A third instantiation of IDP are the (hyper)-rectangular partitions of continuous state spaces (Feng et al, 2004).”
• Planning in Discrete and Continuous Markov Decision Processes by Probabilistic Programming (2015, background): “In a related effort [4], hybrid MDPs are solved using dynamic programming, but assuming that transition model and reward is piecewise constant or linear.”