Bellman-Certified Rounding for Sparse Policy Deployment in MDPs

Zhaojun Peng

cs.LGSep 29, 2026

Bellman-Certified Rounding for Sparse Policy Deployment in MDPs

Authors: Zhaojun Peng

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 $γ=0.95$ , local integration lowers the median bound-to-loss ratio from $402.3$ to $2.08$ on coupled instances.

Figures & tables

Discount	Active	$B_{\rm Bell}$	$B_{\rm cand}$	$B_{\rm trace}$	Direct
$\gamma=1/2$	68	67	68	68	68
$\gamma=4/5$	71	0	35	54	71
All	139	67	103	122	139

Table 1: Certified deployment improvement on the 139 active structured cases. The legacy

B_{\rm Bell}

and

B_{\rm cand}

are pre-rounding certificates, whereas

B_{\rm trace}

is a post-trace audit. Direct reports the exact check

J(y)>J(0)

, with counts deduced from the stored returns.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Domain	$\widehat{\tau}$	$\widehat{\beta}$	$\mathcal{B}_{\mathrm{Bell}}$	$\Delta_{\mathrm{wit}}$	wall
gridworld	$2.159\times 10^{-1}$	$2.819\times 10^{-2}$	$2.405\times 10^{-1}$	$0$	$1.64\,\mathrm{s}$
queue	$4.547\times 10^{-4}$	$2.409\times 10^{-2}$	$2.153\times 10^{-2}$	$3.261\times 10^{-6}$	$2.02\,\mathrm{s}$
maintenance	$1.361\times 10^{-1}$	$1.567\times 10^{-2}$	$1.498\times 10^{-1}$	$0$	$2.45\,\mathrm{s}$
garnet	$1.305\times 10^{-1}$	$6.263\times 10^{-3}$	$1.360\times 10^{-1}$	$0$	$3.11\,\mathrm{s}$

Appendix

Table 2: One case per domain at

d=S=8

k=2

\gamma=1/2

, mixed edits, repair scale

3/5

, and a strong baseline. Each case has

|\mathcal{C}_{k}^{\mathrm{bin}}|=37

$\gamma$	$\mathcal{B}_{\mathrm{Bell}}$	$B_{\mathrm{unif}}$	$B_{\mathrm{cand}}$	$B_{\mathrm{seg}}$	$B_{\mathrm{int}}$	$B_{256}$
0.20	2.8125	1.6875	1.4063	1.0631	1	1.0002
0.50	6	3.6	3	1.6875	1	1.0019
0.80	30	18	15	7.56	1	1.0099
0.95	420	252	210	105.0131	1	1.0439

Appendix

Table 3: Recomputed mechanistic ratios to

\operatorname{Gap}(\mathcal{C}_{k})

, shown at

m=4

. Only the

B_{\mathrm{unif}}

ratio depends on

m

;

B_{256}

uses reliable 256-subinterval upper sums.

Method	Binary optimum	Gap	Queries
Algorithm 1	114/139 (82.0%)	0.185%	6
Top- $k$	61/139 (43.9%)	3.066%	9
Greedy	125/139 (89.9%)	0.178%	26
Random-100	98/139 (70.5%)	0.727%	100

Appendix

Table 4: Deployment baselines on the 139 active structured cases. Gap is the mean normalized binary-optimality gap and Queries is the median number of return evaluations.

Discount	Active	$\mathcal{B}_{\mathrm{Bell}}$	$B_{\mathrm{cand}}$	$B_{\rm trace}$	Direct
$\gamma=1/2$	68	67	68	68	68
$\gamma=4/5$	71	0	35	54	71
All	139	67	103	122	139

Appendix

Table 5: Deployment-improvement coverage on the 139 active structured cases. Direct is inferred from the existing exact-return records.

Axis	$S$	$d$	Total (s)	Interval (s)	RSS (MiB)
A	16	16	0.059	0.007	118.3
A	32	32	0.223	0.030	118.7
A	64	64	0.937	0.122	120.0
A	128	128	4.448	0.553	125.7
B	64	16	0.215	0.012	118.5
B	128	16	0.487	0.019	119.0

Appendix

Table 6: Validated-certification scaling. Times are medians over three fixed seeds. RSS is measured in independent processes.

$\gamma$	$B_{\mathrm{cand}}/L_{\rm rnd}$	$B_{\mathrm{trace}}/L_{\rm rnd}$	$B_{\mathrm{loc}}/L_{\rm rnd}$	Candidate	Local
$1/2$	5.05	3.82	1.81	8/8	8/8
$4/5$	24.68	13.56	1.96	1/8	8/8
$19/20$	402.31	170.93	2.08	0/8	8/8

Appendix

Table 7: New coupled suite. Ratios are medians of bound divided by actual rounding loss. Coverage counts certified baseline improvements. Each discount has eight instances. Local and hybrid bounds coincide here and use the trajectory.

Method	Total (ms)	Binary optimum	Mean gap (%)
Direct rounding	7.60	20/24	0.088
Rank-two direct	9.43	20/24	0.088
Global certificate + rank-two	19.14	20/24	0.088
Local integration	36.19	20/24	0.088
Hybrid integration	48.81	20/24	0.088
Candidate top- $k$	4.33	21/24	0.169

Appendix

Table 8: Complete costs on the new 24-instance suite. The normalized gap is

(J_{\rm bin}^{\star}-J(y))/(J_{\rm bin}^{\star}-J(0))

, averaged across instances.

$S$	$d$	$B_{\mathrm{cand}}/L_{\rm rnd}$	$B_{\mathrm{loc}}/L_{\rm rnd}$	Direct	Rank-two	Local
16	8	123.30	1.60	0.022	0.034	0.681
32	8	121.92	2.35	0.099	0.133	0.473
64	16	291.73	1.55	1.562	1.898	4.109

Appendix

Table 9: Exact scaling checks. Ratios use realized rounding loss. Rounding times are in seconds and are single-run measurements.

Markov Decision Processes

Markov decision processes model sequential choices under uncertainty, linking actions, state transitions, and rewards to planning and reinforcement learning.

See all 157 papers

Primal-Dual Representation Learning for Low-Rank Constrained MDPs
Oct 22, 2026Chenhao Zhou, Chao Zhang, Wensong Bai +2Markov Decision Processes Constrained RL
College of Computer Science and Technology, Zhejiang University
Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs
May 12, 2026Michael Lu, Max Qiushi Lin, Mo Chen +1Markov Decision Processes Last-Iterate Convergence
Simon Fraser University
Learning Chance-Constrained MDPs with Bellman Distributional Certificates
Sep 25, 2026Chenbei Lu, Hongyu YiMarkov Decision Processes Constrained RL
Cornell University AI for Science Institute Cornell University Ithaca, NY, USA · Department of Electrical & Computer Engineering University of Washington Seattle, WA, USA

Oct 22, 2026J/K move · Enter open · S save

Primal-Dual Representation Learning for Low-Rank Constrained MDPs

Chenhao Zhou, Chao Zhang, Wensong Bai, Hanbin Zhao+1

College of Computer Science and Technology, Zhejiang University

Markov Decision Processes Constrained RL Representation Learning for RL Model-Based RL

Open paper AskPDF arXiv

Representation learning has substantially improved the efficiency of unconstrained continuous-state Markov Decision Processes (MDPs), but its extension to Constrained MDPs (CMDPs) is difficult because the transition representation must be learned while constraint violation is controlled. In this paper, we study representation learning for low-rank CMDPs with continuous state spaces, and propose REP-PD-TEG for the soft cumulative-violation setting. In the feature learning period, the algorithm interacts with the environment using a decaying-

ε

-greedy mixture execution policy, and uses the collected samples to learn transition features by maximum likelihood. Based on the learned features, it constructs uncertainty bonuses and plans with an optimistic Lagrangian objective to obtain the return policy. We prove regret and soft-violation guarantees for the return policies, and quantify the influence of the decaying-

ε

-greedy exploration. In particular, REP-PD-TEG achieves the optimal

\widetilde O(\sqrt K)

return policy bound, and gives a

\widetilde O(K^{3/4})

overall sample bound when exploratory actions are charged. For the stricter hard cumulative violation, where feasibility must be verified episode by episode, we propose REP-PD-H-TEG. It plans under a bonus-corrected lower-confidence utility certificate with the learned representation, and performs a stabilized dual search to obtain the return policy, yielding regret and hard-violation bounds. Together, these results give the first theoretically guaranteed representation-learning method for low-rank continuous-state CMDPs with both soft cumulative guarantees and certified hard-violation control.

Abstract

Markov Decision Processes

Explore similar work

Primal-Dual Representation Learning for Low-Rank Constrained MDPs

Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs

Learning Chance-Constrained MDPs with Bellman Distributional Certificates