Constraint-Generation Policy Optimization (CGPO): Nonlinear Programming
  for Policy Optimization in Mixed Discrete-Continuous MDPs
Michael Gimelfarb Ayal Taitler Scott Sanner
We propose Constraint-Generation Policy Optimization (CGPO) for optimizing
policy parameters within compact and interpretable policy classes for mixed
discrete-continuous Markov Decision Processes (DC-MDPs). CGPO is not only able
to 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 bi-level mixed-integer nonlinear
optimization framework for optimizing policies within defined expressivity
classes (i.e. piecewise (non)-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 explicit marginalization (where applicable) or
chance-constraints, providing high-probability policy performance guarantees.
We also present a road-map for understanding the computational complexities
associated with different expressivity classes of policy, reward, and
transition dynamics. We experimentally demonstrate the applicability of CGPO in
diverse domains, including inventory control, management of a system of water
reservoirs, and physics control. In summary, we provide a solution for deriving
structured, compact, and explainable policies with bounded performance
guarantees, enabling worst-case scenario generation and counterfactual policy
diagnostics.