Dynamic Programming for Structured Continuous Markov Decision Problems
This work addresses computational efficiency in continuous MDPs for researchers and practitioners in reinforcement learning, though it appears incremental as it builds on existing dynamic programming and POMDP techniques.
The paper tackles the problem of solving continuous Markov Decision Processes by dynamically partitioning the state space into regions with uniform value functions, using piecewise constant and linear representations. It shows that this approach efficiently computes optimal solutions for complex, structured problems.
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.