arXiv：cs.LG（机器学习，全量分类）· Zhaojun Peng·· 14 小时前AI 评分29
有限 MDP 中稀疏策略部署的 Bellman 认证舍入方法
Bellman-Certified Rounding for Sparse Policy Deployment in MDPs
AI 导读
研究在有限 MDP 中把连续行混合策略舍入为稀疏二值策略时能保留多少折扣回报。方法通过 2d+2 次 Bellman 求解导出可复用包络，支持舍入前的统一与候选特定保证，候选特定界将结构化测试集上的认证覆盖率从 48.2% 提升至 74.1%。在 γ=0.95 的耦合实例上，局部积分把界与损失比值的中位数从 402.3 降至 2.08。
正文
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.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.00325 [cs.LG] |
| (or arXiv:2610.00325v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.00325 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Zhaojun Peng [view email]
[v1]
Tue, 29 Sep 2026 07:34:50 UTC (44 KB)
来源：arXiv：cs.LG（机器学习，全量分类） · arxiv.org