mlsanityData to 7 Oct 2026

Bellman-Certified Rounding for Sparse Policy Deployment in MDPs

arXiv 2610.00325 ↗First posted 29 Sep 2026cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

28 of 42 references.

References · 28

  1. 2023Policy Gradient for Rectangular Robust Markov Decision Processescited by 29
  2. 2024Robust Markov Decision Processes: A Place Where AI and Formal Methods Meetcited by 18
  3. 2023Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexitycited by 16
  4. 2023Policy Gradient Algorithms for Robust MDPs with Non-Rectangular Uncertainty Setscited by 15
  5. 2019Parameter Synthesis for Markov Models: Covering the Parameter Spacecited by 14
  6. 2025Probabilistic Shielding for Safe Reinforcement Learningcited by 12
  7. 2024Solving Robust Markov Decision Processes: Generic, Reliable, Efficientcited by 11
  8. 2023Safe Policy Improvement for POMDPs via Finite-State Controllerscited by 10
  9. 2024Learning Optimal Deterministic Policies with Stochastic Policy Gradientscited by 10
  10. 2023More for Less: Safe Policy Improvement With Stronger Performance Guaranteescited by 9
  11. 2023A Cubic-regularized Policy Newton Algorithm for Reinforcement Learningcited by 7
  12. 2019A Block Decomposition Algorithm for Sparse Optimizationcited by 6
16 more
  1. 2023On the Second-Order Convergence of Biased Policy Gradient Algorithmscited by 5
  2. 20241-2-3-Go! Policy Synthesis for Parameterized Markov Decision Processes via Decision-Tree Learning and Generalizationcited by 5
  3. 2026Strongly Polynomial Time Complexity of Policy Iteration for L_∞ Robust MDPscited by 5
  4. 2021Smoothing Proximal Gradient Methods for Nonsmooth Sparsity Constrained Optimization: Optimality Conditions and Global Convergencecited by 4
  5. 2023Learning Robust Policies for Uncertain Parametric Markov Decision Processescited by 4
  6. 2024A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processescited by 4
  7. 2025Policy Newton Algorithm in Reproducing Kernel Hilbert Spacecited by 3
  8. 2025Deep SPI: Safe Policy Improvement via World Modelscited by 3
  9. 2016Binary Optimization via Mathematical Programming with Equilibrium Constraintscited by 2
  10. 2024Decision-Point Guided Safe Policy Improvementcited by 2
  11. 2025Generalized Parameter Lifting: Finer Abstractions for Parametric Markov Chainscited by 2
  12. 2025Constrained and Robust Policy Synthesis with Satisfiability-Modulo-Probabilistic-Model-Checkingcited by 2
  13. 2023Efficiently Escaping Saddle Points for Policy Optimizationcited by 1
  14. 2024Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximizationcited by 1
  15. 2025Best-Effort Policies for Robust Markov Decision Processescited by 1
  16. 2026Robust Parameter Learning for Uncertain MDPscited by 1

Built on by

Not cited yet.