# Constraint-Generation Policy Optimization (CGPO): Nonlinear Programming for Policy Optimization in Mixed Discrete-Continuous MDPs

arXiv: https://arxiv.org/abs/2401.12243 · HTML: https://mlsanity.com/paper/2401.12243/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 54 references that are in the map.
- First posted on arXiv 20 Jan 2024.

## Builds on (most cited first, 12 of 12)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Monte Carlo Tree Search: A Review of Recent Modifications and Applications](https://mlsanity.com/paper/2103.04931/) (2021)
- [A Survey of Algorithms for Black-Box Safety Validation of Cyber-Physical Systems](https://mlsanity.com/paper/2005.02979/) (2020)
- [Iterative Bounding MDPs: Learning Interpretable Policies via Non-Interpretable Methods](https://mlsanity.com/paper/2102.13045/) (2021)
- [Policy Optimization for Constrained MDPs with Provable Fast Global Convergence](https://mlsanity.com/paper/2111.00552/) (2021)
- [Chance Constrained Policy Optimization for Process Control and Optimization](https://mlsanity.com/paper/2008.00030/) (2020)
- [Scalable Planning with Tensorflow for Hybrid Nonlinear Domains](https://mlsanity.com/paper/1704.07511/) (2017)
- [pyRDDLGym: From RDDL to Gym Environments](https://mlsanity.com/paper/2211.05939/) (2022)
- [Optimal Decision Tree Policies for Markov Decision Processes](https://mlsanity.com/paper/2301.13185/) (2023)
- [Sample-efficient Iterative Lower Bound Optimization of Deep Reactive Policies for Planning in Continuous MDPs](https://mlsanity.com/paper/2203.12679/) (2022)
- [A mixed-integer programming model for identifying intuitive ambulance dispatching policies](https://mlsanity.com/paper/2202.09387/) (2022)

## Abstract (arXiv)

We propose the Constraint-Generation Policy Optimization (CGPO) framework to optimize policy parameters within compact and interpretable policy classes for mixed discrete-continuous Markov Decision Processes (DC-MDP). CGPO can not only provide bounded policy error guarantees over an infinite range of initial states for many DC-MDPs with expressive nonlinear dynamics, but it can also provably derive optimal policies in cases where it terminates with zero error. Furthermore, CGPO can generate worst-case state trajectories to diagnose policy deficiencies and provide counterfactual explanations of optimal actions. To achieve such results, CGPO proposes a bilevel mixed-integer nonlinear optimization framework for optimizing policies in defined expressivity classes (e.g. piecewise linear) and reduces it to an optimal constraint generation methodology that adversarially generates worst-case state trajectories. Furthermore, leveraging modern nonlinear optimizers, CGPO can obtain solutions with bounded optimality gap guarantees. We handle stochastic transitions through chance constraints, providing high-probability performance guarantees. We also present a roadmap for understanding the computational complexities of different expressivity classes of policy, reward, and transition dynamics. We experimentally demonstrate the applicability of CGPO across various domains, including inventory control, management of a water reservoir system, and physics control. In summary, CGPO provides structured, compact and explainable policies with bounded performance guarantees, enabling worst-case scenario generation and counterfactual policy diagnostics.