Safety
Bellman-Certified Rounding for Sparse Policy Deployment in MDPs
arXiv:2610.00325v1 Announce Type: new Abstract: Continuous policy optimization may spread an update across many states, even when deployment permits only a few complete state-level changes. We study h
arXiv:2610.00325v1 Announce Type: new Abstract: 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 gamma=0.95, local integration lowers the median bound-to-loss ratio from 402.3 to 2.08 on coupled instances.
Related
- Audit-First VAPO: Risk-Certified Selective Updates under Imperfect Verification
- Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs
- Policy Optimization Achieves Data-Dependent Regret Bounds in MDPs with Unknown Transitions
- End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions
- Last-Iterate Guarantees for Online Reinforcement Learning in Structured Constrained MDPs
Source: arXiv cs.LG | 2026-10-02