Abstract
Optimizing public policy decisions, such as police redistricting, involves navigating high-dimensional spaces governed by complex, often implicit constraints. Traditional Bayesian Optimization (BO) methods struggle when feasibility cannot be easily expressed mathematically. This paper introduces CageBO (Conditional And Generative Black-box Optimization), a novel framework that leverages a Conditional Variational Autoencoder (CVAE) to learn a low-dimensional, constraint-free latent representation of the feasible decision space. By performing optimization within this latent manifold, CageBO efficiently identifies high-performing policies while maintaining feasibility. We provide theoretical "no-regret" guarantees and demonstrate CageBO's superior performance on synthetic benchmarks and a real-world police redistricting task for the Atlanta Police Department.
1. Introduction and Problem Statement
Public policy optimization is a high-stakes domain where the "best" solution must satisfy a myriad of requirements. Consider the task of redrawing police patrol zones to balance workloads. While some constraints are explicit (e.g., geographic contiguity), many are implicit and difficult to formalize. A proposed plan might be technically valid but practically infeasible due to unmodeled factors like highway access, natural barriers, or sensitive socio-economic boundaries.
Standard Black-Box Optimization (BBO) treats the objective function as an unknown to be queried. However, when constraints are implicit, the search space becomes a minefield of invalid solutions. Furthermore, the high dimensionality of policy decisions—often involving thousands of variables (e.g., assigning every city block to a specific precinct)—makes traditional search algorithms painfully slow or prone to failure.
2. The CageBO Framework
To address these hurdles, the authors propose CageBO. The core innovation lies in transforming a constrained, high-dimensional search problem into an unconstrained, low-dimensional one using a generative approach.
The framework operates in three main stages:
- Learning the Feasible Manifold: CageBO employs a Conditional Variational Autoencoder (CVAE). By training on a dataset of labeled "feasible" and "infeasible" decisions, the CVAE learns a mapping from the complex decision space $\mathcal{X}$ to a compressed, low-dimensional latent space $\mathcal{Z}$. This latent space is designed to represent only the feasible regions of the original space.
- Latent Bayesian Optimization: The actual optimization happens in this tiny, constraint-free latent space. CageBO uses a Gaussian Process (GP) as a surrogate model to predict the objective value and an acquisition function (Lower Confidence Bound) to decide where to sample next.
- Post-Decoding Refinement: When the CVAE "decodes" a latent point back into a real-world plan, there is a chance the result might still slightly violate a constraint. CageBO includes a post-decoding process that projects these "near-miss" solutions to the closest known feasible point in the training set, ensuring every evaluation is valid.
Crucially, the authors provide a theoretical proof that CageBO is a no-regret algorithm, meaning that as the algorithm runs, it is guaranteed to converge toward the global optimal solution.
3. Experimental Evaluation
The researchers validated CageBO on both synthetic benchmarks and high-stakes real-world data:
- Synthetic Functions: 30-dimensional versions of Keane’s bump and Michalewicz functions, which are standard "stress tests" for constrained optimization.
- Atlanta Police Department (APD) Case Study: A massive real-world dataset involving 78 service regions in Atlanta, Georgia, to be divided into 6 zones. This used historical 911-call data from 2021-2022 to estimate workloads and minimize variance across precincts.
4. Key Results and Insights
CageBO demonstrated significant improvements over existing methods, including standard BO, Simulated Annealing, and other VAE-guided methods:
- Superior Convergence: In 30-dimensional synthetic tests, CageBO consistently found better objective values faster than all baseline methods.
- Police Redistricting Efficiency: In the Atlanta case study, CageBO produced districting plans with the lowest workload variance.
- Real-World Alignment: Interestingly, the plans generated by CageBO closely aligned with actual heuristic policies used by human policymakers but optimized them further, suggesting the model successfully captured the "implicit" logic of city planning.
- Scalability: The latent space approach allowed the model to handle the 78x6 decision matrix of Atlanta far more efficiently than Mixed-Integer Linear Programming (MILP), which often struggles with the non-linear nature of workload calculations.
5. Conclusion and Future Work
CageBO represents a significant step forward in applying AI to complex public policy problems. By treating feasibility as a learnable latent feature, it bridges the gap between mathematical optimization and human-centric constraints.
However, the framework relies on having a rich repository of historical decisions to train the CVAE. The authors also touch on the ethical implications of using historical 911 data, noting that it can reinforce existing policing biases. Future work should integrate debiasing techniques directly into the optimization loop to ensure that "optimal" policies are also equitable ones. Finally, extending this to "human-in-the-loop" systems, where the feasibility oracle is a live expert, remains an exciting frontier.
Summary updated