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.
Introduction
Markov Decision Processes (MDPs) provide a robust mathematical framework for sequential decision-making under uncertainty. However, standard algorithms typically assume discrete state and action spaces. Many real-world applications—such as climate control in server rooms or fluid routing in irrigation networks—naturally involve continuous variables. Traditional approaches often rely on discretization, which leads to an exponential "curse of dimensionality" as the number of variables grows.
To address this, the authors focus on Factored MDPs, where the state and action spaces are decomposed into sets of variables. Figure 1 illustrates a simple factored representation for a network administration problem.
Hybrid Approximate Linear Programming (HALP)
The proposed Hybrid Approximate Linear Programming (HALP) framework approximates the optimal value function as a linear combination of basis functions and optimizes their weights via a linear program (LP). This approach bypasses the need for numerical integration by using transition models based on mixtures of Beta distributions and basis functions that are polynomials or piecewise-linear, allowing expectations to be computed analytically.
Constraint Space Approximations
The HALP formulation involves an infinite number of constraints (one for each continuous state-action pair). To solve the LP, the authors introduce three solvers:
- MC-HALP: Uses Monte Carlo sampling for constraints.
- $\epsilon$-HALP: Employs a grid-based discretization and a cutting-plane method.
- MCMC-HALP: This novel approach treats the search for the most violated constraint as an inference problem in a graphical model.
By framing the search for violated constraints as finding the Maximum A Posteriori (MAP) configuration in a graphical model (as shown in Figure 2), the authors use Metropolis-Hastings MCMC to efficiently search the continuous space. This allows the solver to achieve polynomial time complexity relative to the problem's treewidth, successfully breaking the curse of dimensionality.
Experimental Evaluation
The HALP framework was evaluated on two primary simulated environments: a Network Administration problem (4-ring topology) and a complex Irrigation Network Operator problem involving continuous water levels and discrete pump modes across various topologies.
Key Results
- Scalability: On the 4-ring network, HALP matched the performance of high-resolution grid-based value iteration but was orders of magnitude faster (under 1 second vs. 577 seconds).
- Linear Scaling: MCMC-HALP demonstrated linear scaling with the number of variables $n$ in complex irrigation networks.
- High Treewidth Performance: In a 3x3 grid irrigation problem (treewidth 6), $\epsilon$-HALP's complexity exploded ($O(1/\epsilon^7)$), while MCMC-HALP remained tractable and produced higher-quality policies.
Conclusion
HALP provides a scalable, principled approach to solving hybrid factored MDPs. By leveraging analytic integrals and MCMC-based constraint generation, it successfully bypasses the limitations of traditional discretization. Future work includes automating basis function selection and extending the framework to other distribution families like Normal or Gamma.
Summary updated