Solving Factored MDPs with Hybrid State and Action Variables

Abstract

Efficient representations and solutions for large decision problems with continuous and discrete variables are among the most important challenges faced by the designers of automated decision support systems. In this paper, we describe a novel hybrid factored Markov decision process (MDP) model that allows for a compact representation of these problems, and a new hybrid approximate linear programming (HALP) framework that permits their efficient solutions. The central idea of HALP is to approximate the optimal value function by a linear combination of basis functions and optimize its weights by linear programming. We analyze both theoretical and computational aspects of this approach, and demonstrate its scale-up potential on several hybrid optimization problems.

References in corpus (7)

• Value-Function Approximations for Partially Observable Markov Decision Processes
• Planning under Continuous Time and Resource Uncertainty: A Challenge for AI
• A Method for Using Belief Networks as Influence Diagrams
• Solving MAP Exactly using Systematic Search
• Metrics for Markov Decision Processes with Infinite State Spaces
• Approximating MAP using Local Search
• Approximate Linear Programming for First-order MDPs

Cited by in corpus (9)

• Ergodic Control and Polyhedral approaches to PageRank Optimization
• Symbolic Dynamic Programming for Discrete and Continuous State MDPs
• A Heuristic Search Approach to Planning with Continuous Resources in Stochastic Domains
• Factored Value Iteration Converges
• Bounded Approximate Symbolic Dynamic Programming for Hybrid MDPs
• Approximate Dynamic Programming via Sum of Squares Programming
• Partitioned Linear Programming Approximations for MDPs
• A Cross Entropy based Stochastic Approximation Algorithm for Reinforcement Learning with Linear Function Approximation
• Hybrid Planning for Dynamic Multimodal Stochastic Shortest Paths