From Continuous Policy Optimization to Sparse Deployment: Bellman-Certified Rounding for MDPs

Policy optimization often produces diffuse or randomized updates, while deployment may allow changes to only a small number of complete state-level decisions. We study how to bridge this optimization-to-deployment gap in finite discounted MDPs: given a continuous policy update, can it be converted into a sparse binary update while provably controlling the loss in return? Our key observation is that all fractional row mixtures are policies of a single auxiliary two-action MDP. Extremal Bellman value functions over this MDP yield uniform first- and second-order sensitivity bounds, giving a reusable rounding certificate with only $2d+2$ Bellman solves. For a given continuous candidate, we further derive a sharper pre-rounding bound that exploits its fractional support and rounding geometry without additional Bellman solves. We show that linear dependence on the number of editable rows is unavoidable for this class of curvature-based guarantees, while exact exchange curvature is computationally intractable. On a structured suite with genuinely fractional candidates, the sharper bound raises the fraction of deployments certified to improve over the baseline from \(48.2%\) to \(74.1%\). Validated outward-rounded arithmetic further extends sound certification beyond exact enumeration.