# Bellman-Certified Rounding for Sparse Policy Deployment in MDPs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 42 references that are in the map.
- First posted on arXiv 29 Sep 2026.

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

- [Policy Gradient for Rectangular Robust Markov Decision Processes](https://mlsanity.com/paper/2301.13589/) (2023)
- [Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet](https://mlsanity.com/paper/2411.11451/) (2024)
- [Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity](https://mlsanity.com/paper/2306.11626/) (2023)
- [Policy Gradient Algorithms for Robust MDPs with Non-Rectangular Uncertainty Sets](https://mlsanity.com/paper/2305.19004/) (2023)
- [Parameter Synthesis for Markov Models: Covering the Parameter Space](https://mlsanity.com/paper/1903.07993/) (2019)
- [Safe Policy Improvement for POMDPs via Finite-State Controllers](https://mlsanity.com/paper/2301.04939/) (2023)
- [Learning Optimal Deterministic Policies with Stochastic Policy Gradients](https://mlsanity.com/paper/2405.02235/) (2024)
- [Probabilistic Shielding for Safe Reinforcement Learning](https://mlsanity.com/paper/2503.07671/) (2025)
- [Solving Robust Markov Decision Processes: Generic, Reliable, Efficient](https://mlsanity.com/paper/2412.10185/) (2024)
- [More for Less: Safe Policy Improvement With Stronger Performance Guarantees](https://mlsanity.com/paper/2305.07958/) (2023)
- [A Cubic-regularized Policy Newton Algorithm for Reinforcement Learning](https://mlsanity.com/paper/2304.10951/) (2023)
- [A Block Decomposition Algorithm for Sparse Optimization](https://mlsanity.com/paper/1905.11031/) (2019)
- [On the Second-Order Convergence of Biased Policy Gradient Algorithms](https://mlsanity.com/paper/2311.02546/) (2023)
- [1-2-3-Go! Policy Synthesis for Parameterized Markov Decision Processes via Decision-Tree Learning and Generalization](https://mlsanity.com/paper/2410.18293/) (2024)
- [Strongly Polynomial Time Complexity of Policy Iteration for L_∞ Robust MDPs](https://mlsanity.com/paper/2601.23229/) (2026)
- [Smoothing Proximal Gradient Methods for Nonsmooth Sparsity Constrained Optimization: Optimality Conditions and Global Convergence](https://mlsanity.com/paper/2104.13782/) (2021)
- [Learning Robust Policies for Uncertain Parametric Markov Decision Processes](https://mlsanity.com/paper/2312.06344/) (2023)
- [A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processes](https://mlsanity.com/paper/2406.00274/) (2024)
- [Policy Newton Algorithm in Reproducing Kernel Hilbert Space](https://mlsanity.com/paper/2506.01597/) (2025)
- [Deep SPI: Safe Policy Improvement via World Models](https://mlsanity.com/paper/2510.12312/) (2025)
- [Binary Optimization via Mathematical Programming with Equilibrium Constraints](https://mlsanity.com/paper/1608.04425/) (2016)
- [Decision-Point Guided Safe Policy Improvement](https://mlsanity.com/paper/2410.09361/) (2024)
- [Generalized Parameter Lifting: Finer Abstractions for Parametric Markov Chains](https://mlsanity.com/paper/2504.05965/) (2025)
- [Constrained and Robust Policy Synthesis with Satisfiability-Modulo-Probabilistic-Model-Checking](https://mlsanity.com/paper/2511.08078/) (2025)
- [Efficiently Escaping Saddle Points for Policy Optimization](https://mlsanity.com/paper/2311.08914/) (2023)
- [Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization](https://mlsanity.com/paper/2409.14325/) (2024)
- [Best-Effort Policies for Robust Markov Decision Processes](https://mlsanity.com/paper/2508.07790/) (2025)
- [Robust Parameter Learning for Uncertain MDPs](https://mlsanity.com/paper/2605.01339/) (2026)

## Abstract (arXiv)

Continuous policy optimization may spread an update across many states, even when deployment permits only a few complete state-level changes. We study how much discounted return can be retained when continuous row mixtures are rounded to sparse binary policies in finite MDPs. Policy-dependent visitation couples the row edits, while long horizons make global curvature bounds conservative. From 2d+2 Bellman solves, we derive reusable envelopes that support uniform and candidate-specific guarantees before rounding. A rank-two rational representation of each exchange further permits weighted curvature integration along the realized trajectory. We prove that linear dimension dependence is unavoidable when the budget scales, and that exact global curvature thresholding is hard. Candidate-specific bounds raise pre-rounding certification coverage from 48.2% to 74.1% on the structured suite. At γ=0.95, local integration lowers the median bound-to-loss ratio from 402.3 to 2.08 on coupled instances.