acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 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.

Primary area:
reinforcement learning
Keywords:
Markov Decision Processes, Policy Optimization, Certified Rounding, Sparse Policy Deployment, Bellman Certificates

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_GcryOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies how to convert continuous policy updates into sparse binary policies within finite discounted Markov Decision Processes, considering that only a limited number of state-action pairs can be modified. It establishes reusable Bellman-based sensitivity bounds that provide guarantees on performance loss for a specific rounding algorithm. They also introduce budget aware and candidate-specific certificates, a lower-bound construction that shows the necessary dependence on dimensions, an NP-hardness result for exact exchange curvature, and a new method for integrating curvature based on trajectories.

To back up their theoretical findings, they conducted exact-rational experiments, used structured synthetic MDP benchmarks, and performed validated-arithmetic scaling tests. The results of these experiments indicate improved certification coverage and much tighter bounds that depend on trajectory choice, especially in longer-horizon scenarios.

Critical strengths
  1. Valid Theoretical Contribution: The paper presents a solid method for certifying sparse policy rounding while considering how policies affect state visitation. By combining Bellman sensitivity envelopes with budget aware rounding, it offers a clear performance guarantee. Also, it includes refinements that can be applied again without needing to solve Bellman equations anew. This is the main reason I have a positive view of the work.

  2. Good Analysis of Certificate Tightness: The paper's construction of lower bounds, its complexity, and the rank-two trajectory representation indicate the limits of global curvature bounds. The use of weighted trajectory integration tackles a specific issue related to long-term conservatism. Additionally, employing exact and validated arithmetic boosts the numerical evidence backing the theoretical claims.

Critical weaknesses
  1. The impact of candidate-specific certification hasn’t been completely separated out in the results. In Section 6, there's an improvement in certification coverage from 48.2% to 74.1% when comparing the old uniform method to the candidate-specific one. However, Section 3 also talks about a new, tighter budget-aware uniform method. Since the coverage of this new method isn’t reported using the same structured setup, it is hard to tell how much of the improvement is really due to the candidate-specific information.

  2. We need stronger justification for the practical benefits of pre-rounding certification. While getting a guarantee before rounding sounds good in theory, the experiments show that directly verifying the completed policies works for all 139 active structured cases. Plus, in the exact-rational tests, we can reuse the final endpoint returns for verification. The paper would be even better if it included a clear example where certification is necessary before creating the binary policy. Additionally, it would be helpful to separate the reported reduction in evaluations during the rounding phase from the overall computational cost, which also includes the optimization of continuous candidates.

  3. The experiments predominantly use small synthetic MDPs, which are appropriate for validating the proposed theoretical mechanisms. However, they provide limited evidence about how frequently the resulting certificates are useful in application-derived models. An evaluation on established finite-MDP case studies could strengthen the practical motivation, although this is not essential to the validity of the theoretical contribution.

Questions for authors
  1. What is the pre-rounding certification coverage of the new budget-aware uniform bound on the 139 active structured cases? How many additional cases are certified specifically by exploiting candidate-dependent information?

  2. Can the authors identify a concrete deployment or decision workflow in which certification must precede binary policy construction? What advantage does the proposed pre-rounding certificate offer over direct verification of the rounded policy in that setting?

Reviewer_5i2ZOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how to convert a randomized policy into a policy that makes at most kk complete changes to a baseline policy. It uses Bellman value and visitation bounds to control the return lost during rounding. It also develops sharper bounds for individual candidates and rounding trajectories, proves a dimension lower bound and a hardness result, and evaluates certificate quality and computation cost on finite MDPs.

Critical strengths

The problem is clearly defined and technically meaningful. Restricting how many states can change creates a real difference between continuous optimization and discrete deployment. The analysis accounts for how changing one state affects visits to other states. Also, the paper connects computable Bellman bounds to a constructive rounding guarantee. The candidate-specific bound uses information that the uniform bound discards. The lower-bound example explains why long horizons can make curvature bounds loose, and the hardness result gives additional substance beyond the rounding analysis.

Critical weaknesses

It seems that paper does not show when the extra guarantees are useful in practice. After constructing a rounded policy, its return can be checked directly before deployment. In the experiments, this simple check confirms improvement in more cases, while computing tighter bounds adds cost without changing the final policy. Most experiments also use small, specially designed problems, so it remains unclear how often these guarantees would help in realistic applications.

Questions for authors

Why do the authors defer Algorithm 1 to the appendix even though there is sufficient space in the main text?

Reviewer_fM4tOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper examines the loss in return when mapping a policy in a continuous space to a constrained sparse deployment. The goal is to convert a continuous candidate into a binary policy with a guarantee of return. Pre-rounding certification increases for candidate-specific bounds on the structured suite.

Critical strengths

Well organized with thorough breakdown of all calculations.

Critical weaknesses

Small scope. Only applies to known finite discounted MDP with two actions per editable row.

Questions for authors

What is the significance of your findings to the larger field?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.